1. 课程导入与整数规划全景

在运筹学与优化建模的实践中，我们经常遇到一类问题：决策变量只能取整数，甚至只能取 0 或 1。例如，一个工厂本月要开启几条生产线、某条配送路线是否启用、某个班次安排几名员工、某个项目是否投资。这类"不能切半"的决策，正是整数规划（Integer Programming, IP）与混合整数规划（Mixed Integer Programming, MIP）要处理的核心对象。

本课程围绕整数规划与混合整数规划的应用展开，共 30 章。第一章的目标不是立刻求解模型，而是先建立一张"全景地图"：弄清 IP 与 MIP 的定义边界、它们与线性规划的本质差异、典型应用场景，以及后续章节的知识路线。只有先看清整体结构，后续学习建模技巧、求解算法与工程实现时才不会迷失方向。

一、什么是整数规划与混合整数规划

先给出严格定义。一个数学规划问题若其全部决策变量都被约束为整数，称为纯整数规划；若只有部分变量要求整数、其余变量可取连续值，称为混合整数规划。当整数变量进一步被限制为只能取 0 或 1 时，称为0-1 规划或二进制整数规划，它是 MIP 中最常见也最重要的一类。

用统一形式表达，MIP 的标准模型可写为：

min  cᵀx + dᵀy
s.t. A x + B y ≤ b
     x ∈ ℤⁿ⁺（整数变量）
     y ∈ ℝᵐ⁺（连续变量）

其中 x 为整数决策向量，y 为连续决策向量。若 m = 0，模型退化为纯整数规划；若所有整数变量都是 0-1 变量，则为 0-1 规划。理解这个统一形式很重要：它说明 IP 与 MIP 并不是两套割裂的方法，而是同一框架下整数约束范围不同的两种情形。

二、与线性规划的关键区别

线性规划（LP）的可行域是一个多面体（凸集），最优解若存在，必可在某个顶点取得，因此求解高效、理论成熟。整数约束的加入彻底改变了这一图景：可行域从连续多面体变成多面体内的离散格点集合，凸性被破坏，最优解不再能简单地从顶点读取。

这一变化带来两个直接后果。第一，求解难度跃升。LP 可在多项式时间内求解，而一般整数规划属于 NP-hard 问题，规模增大时求解时间可能急剧上升。第二，"舍入"不可靠。一个常见的错误做法是先解 LP 松弛（把整数约束放松为连续约束），再把小数解四舍五入。这样做既可能破坏约束可行性，也可能远离真正最优解。下面的示意图对比了两种模型的可行域结构与求解路径差异。

图中左侧 LP 的最优解落在多面体顶点；右侧加入整数约束后，可行域收缩为格点，最优解必须在这些离散点中寻找，且往往不等于 LP 松弛解就近舍入的结果。这正是整数规划需要专门算法的根本原因。

三、典型应用场景

整数规划的价值在于它能精确刻画"离散选择"与"逻辑条件"。以下几类场景最具代表性：

• 生产与排程：某车间有 3 条产线，每条线开启与否用 0-1 变量表示，产量用连续变量表示，形成典型 MIP；换型顺序、班次安排则涉及排序与指派。
• 物流与选址：从若干候选仓库中选建若干个（0-1 选址变量），再决定各客户由哪个仓库供货（指派变量），目标是最小化建设与运输总成本。
• 资源指派与排班：护士排班、课程表编排、设备任务分配，本质是把任务指派给人员或时段，满足覆盖与工时约束。
• 投资与项目选择：在预算约束下从多个项目中选组合，常带互斥、依赖等逻辑关系，用 0-1 变量与大 M 约束表达。
• 网络与路径：车辆路径、最短路径中的"是否经过某边"、背包问题中的"是否装入某物"，都是经典 0-1 模型。

可以看到，这些场景的共同点是：决策本身是"选或不选""开几条""派给谁"，而不是"取多少连续量"。识别出这种离散结构，是判断一个问题是否该用整数规划建模的第一步。

四、课程路线图

本课程 30 章按"基础—建模—算法—实现—应用"的逻辑递进组织。第一章建立全景认知；随后进入模型基础，讲清变量、约束、目标与标准形式；接着系统训练建模技巧，包括 0-1 建模、逻辑约束表达、大 M 方法、线性化技巧等；再深入求解算法，理解分支定界、割平面、分支切割以及 LP 松弛与界的作用；之后进入工程实现，讨论建模语言、求解器调用、模型调试与性能优化；最后通过选址、排程、路径、背包等综合案例完成应用闭环。

需要强调的是，整数规划并非"更难的线性规划"这么简单。它要求建模者同时具备两种能力：一是业务抽象能力，能把现实中的选择、互斥、依赖、覆盖关系转成整数变量与约束；二是算法意识，知道模型规模、变量类型与约束结构会如何影响求解时间，从而在建模阶段就为可解性做设计。本章的全景图正是为这两种能力打底。

接下来，课程将从最基础的模型要素开始，逐步把这张地图上的每个区域展开为可操作的知识与技能。