整数规划

【定义】若在线性规划模型中，部分或全部变量限制为整数时，称为整数规划。

0.情景代入

钢铁厂常把圆钢零件下料成毛坯。设用某型号圆钢下零件 $A_1, A_2, \cdots, A_m$ 的毛坯，在一根圆钢上下料的方式有 $B_1, B_2, \cdots, B_n$ 种。每种下料方式可以得到各种零件的毛坯数以及每种零件的需求量如下表，问如何下料可以使得在满足需求量的条件下下料最少？

产出毛坯 \ 下料方式	$B_1$	$B_2$	$\cdots$	$B_n$	毛坯需求
$A_1$	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$	$b_1$
$A_2$	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$	$b_2$
$\cdots$
$A_m$	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$	$b_m$

1. 为什么需要整数规划

钢铁厂在下料时，只能一根一根下料，不可以下小数根；得到的毛坯也必须时整数，不会出现分数个毛坯。再比如，钢铁厂由于产能升级，要购进新的生产设备。设备有不同型号，不同型号的设备价格不同，耗能不同，占地面积不同，产能也不同。此时在做选购设备的规划时，设备台数就不能包含小数。

像机器台数，产品个数，生产计划这类具有实际意义的问题，答案往往只能为整数，所以此时就需要整数规划。

2. 整数规划模型的一般形式

建立整数规划模型与建立线性规划模型过程基本一致，只是多了对变量的整数约束。

设： $x_j$ 表示 $B_j$ 方式下料的根数，决策向量为 $X$ ， $x_j \in X$ 。
首先，要使毛坯总产量满足需求，就有： $\sum_{j = 1}^{n} a_{ij}x_j \geq b_i \; (i = 1, 2, \cdots, m)$ 。
其次，规划目标是要使总下料最少，于是有： $min\ Z = \sum_{j = 1}^{n} x_j$ 。
最后，整个规划具有实际意义且满足整数规划： $x_j \geq 0 \; (j = 1, 2, \cdots, n)$ 且为整数。
整理得:
$min\ Z = \sum_{j = 1}^{n} x_j$

$\left\{ \begin{aligned} \sum_{j = 1}^{n} a_{ij}x_j &\geq b_i \; (i = 1, 2, \cdots, m) \\ x_j &\geq 0 \; (j = 1, 2, \cdots, n) \; \\ \mathbf{intcon} & : x_1, x_2, \cdots, x_n\\ \end{aligned} \right.$

3. 模型建立

在Matlab中，整数规划的求解使用到了 $intlinprog()$ 函数。Matlab默认的整数规划的一般形式为：
$\min_x \ f^Tx \ \left\{ \begin{aligned} \mathbf{intcon} & : x_1, x_2, \cdots, x_n \\ A \cdot x &\leq b \\ Aeq \cdot x &= beq \\ lb \leq x &\leq ub \\ \end{aligned} \right.$
与之对应， $intlinprog()$ 函数的带参形式为：

$x = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, x_0)$

其中 $intcon$ 为整数约束组成的向量，储存需要取整的 $x$ 分量的下标。如： $intcon =$ $[1, 2, 7]$ 表示决策变量 $x_1, x_2, x_7$ 受整数约束。 $x_0$ 为初始点，是决策向量的初始值，算法将从 $x_0$ 点开始整数规划。 $f$ 、 $A$ 、 $Aeq$ 、 $b$ 、 $beq$ 、 $lb$ 、 $ub$ 的含义与整数规划相同。

以上函数返回值之后决策向量 $x$ ，还有另一种返回值可以选择：
$[x, fval, exitflag, output] = intlinprog(\cdots)$
其中 $fval$ 为目标值，是决策向量 $x$ 处的目标函数值。 $exitflag$ 算法停止条件， $output$ 求解过程摘要。具体详细信息可以移步到这里MathWork混合整数线性规划。

4. 模型求解（Matlab编程）

求解：
$\max_x \ 3x_1 + 2x_2 + x_3 \ s.t. \left\{ \begin{aligned} &\mathbf{intcon} : x_3 \\ &x_1 + x_2 + x_3 \leq 7 \\ &4x_1 + 2x_2 + x_3 = 12 \\ &x_1, x_2, x_3 \geq 0 \\ \end{aligned} \right.$

代码：

f = [-3;-2;-1];        %求目标函数最大值需要将系数取反
intcon = 3;            %x3为整数
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [];

[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

代码中有大量与线性规划相同的部分，具体请移步到这里。

5. 整数规划的特点

原线性规划有最优解，当自变量限制为整数后，其整数规划解可能出现下述情况：

原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

这种情况非常好理解，当线性规划最优解恰为整数时，该解也是整数规划的解。

若整数规划存在可行解，则最优解相对于线性规划会变差。

若有可行解，说明有多个解都可以满足约束，说明线性规划的最优解被这几个可行解包围（在几个可行解的范围内），故整数规划的最优解变差。

整数规划可能没有可行解（也就没有最优解）。
若有诸如 $3.3 \leq x_3 \leq 3.9$ 这类不存在整数的约束条件，则整数规划无解。

6. 整数规划的理解误区

为什么不可以直接将线性规划的最优解四舍五入取整得到整数规划的解？

首先，因为在整数规划中，最优解是被几个可行解包围的，所以几个可行解都可能为最优解，需要比较才知道。比如线性最优解为 $[3.7, 4.4, 5.6]$ ，而整数最优解为 $[3, 5, 6]$ ，显然简单的舍入规则是不保证得到最优解的。原因是从线性最优解找整数最优解的过程，本质是对线性最优解的移动，因为整数可行解原则上都有可能是整数最优解，所以该移动的方向是任意的。而像四舍五入这类单一的舍入规则，对解的移动方向是固定的（比如四舍五入就是只能将解在 $y = x$ 附近的方向上移动），所以不能保证找到最优解。