M002 - 整数规划 (ILP)
定义
数学规划中二点变量（部分或全部）限制位整数时，称为整数规划。
若在线性规划模型中，变量限制为整数，则称为整数线性规划。
分类
变量全限制为整数时，称纯（完全）整数规划。
变量部分限制为整数的，称混合整数规划。
特点
原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况
原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
整数规划无可行解。
有可行解（当然就存在最优解），但最优解值变差。
整数规划最优解不能按照实数最优解简单取整而获得。
相关问题
e.g. 合理下料
e.g. 建厂问题
e.g. 指派问题
e.g. 投资问题
e.g. 互斥约束问题
e.g. 固定费用问题
具体分析
依照决策变量取整要求的不同， 整数规划可分为
纯整数规划: 所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。
全整数规划: 除了所有决策变量要求取非负整数外，系数\(a_{ij}\)和常数\(b_i\)也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。
混合整数规划: 只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。
0-1整数规划: 所有决策变量只能取 0 或 1 两个整数。
整数规划与线性规划的关系
整数规划可行解是松弛问题可行域中的整数格点；
ILP最优值小于或等于松弛问题的最优值；
松弛问题无可行解， 则整数规划无可行解；
松弛问题最优解满足整数要求， 则该最优解为整数规划最优解；
整数线性规划的求解方法
从数学模型上看整数规划似乎是线性规划的一种特殊形式，
求解只需要在线性规划的基础上通过舍入取整，寻求满足整数要求的解即可。
分支定界算法
不考虑整数限制先求出相应松弛问题的最优解，
若松弛问题无可行解， 则ILP无可行解；
若求得的松弛问题最优解符合整数要求， 则是ILP的最优解；
若不满足整数条件， 则任选一个不满足整数条件的变量\(x_{i}^{0}\)
来构造新的约束添加到松弛问题中形成两个子问题\(x_i \le [x_{i}^{0}] \ ;\ x_i \ge [x_{i}^{0}] + 1\)
依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，直到子问题无解或有整数最优解（被查清）。
割平面算法
如果松弛问题(P0)无解， 则(P)无解；
如果(P0)的最优解为整数向量，则也是(P)的最优解；
如果(P0)的解含有非整数分量，则对(P0)增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(P)的可行解，得到问题(P1)，重复上述的过程。
割平面算法基本步骤
求解线性规划最优解
\[x_i + \sum a_{ik}x_k = b_i
\]
\[a_{ik} = [a_{ik}] + (a_{ik} - La_{ik}) = [a_{ik}] + f_{ik}
\]
\[b_i = [b_i] + (b_i - Lb_i) = [b_i] + f_i
\]
\[x_i + \sum [a_{ik}]x_k + \sum [f_{ik}]x_k = [b_i] + f_i
\]
\[x_i + \sum [a_{ik}x_k - [b_i] = - \sum [f_{ik}]x_k + f_i
\]
互斥约束的推广
从下述p个约束条件中恰好选择q个约束条件\(\displaystyle\sum_{j=1}^{n} a_{ij}x_j \le b_i (i = 1, 2, \cdots, p)\)
\[\begin{cases}
\displaystyle\sum_{j=1}^{n} a_{ij}x_j \le b_i + My_i \\
\displaystyle\sum_{i=1}^{p} y_i = p - q
\end{cases}
(i = 1, 2, \cdots, p)
\]
指派问题的标准形式
有n个人和n项工作，已知第i个人做第j项工作的代价为\(c_{ij} (i, j=1, \cdots, n)\),
要求每项工作只能交与其中一人完成，每个人只能完成其中一项工作，问如何分配可使总代价最少？
指派问题的系数矩阵:
\[C = (c_{ij})_{n \times n} =
\begin{bmatrix}
{c_{11}}&{c_{12}}&{\cdots}&{c_{1n}}\\
{c_{21}}&{c_{22}}&{\cdots}&{c_{2n}}\\
{\vdots}&{\vdots}&{\ddots}&{\vdots}\\
{c_{n1}}&{c_{n2}}&{\cdots}&{c_{nn}}\\
\end{bmatrix}
\]
i行元素 —— 第i个人完成各项任务的代价
j列元素 —— 各人完成第j项工作的代价
指派问题的数学模型
\[x_{ij} =
\begin{cases}
1 \quad 第i个人做第j项工作 \\
0 \quad 第i个人不做第j项工作
\end{cases} \\
(i, \quad j = 1, \cdots, n)
\]
指派问题的解矩阵
\[X = (x_{ij})_{n \times n} =
\begin{bmatrix}
{c_{11}}&{c_{12}}&{\cdots}&{c_{1n}}\\
{c_{21}}&{c_{22}}&{\cdots}&{c_{2n}}\\
{\vdots}&{\vdots}&{\ddots}&{\vdots}\\
{c_{n1}}&{c_{n2}}&{\cdots}&{c_{nn}}\\
\end{bmatrix}
\]
\[min z = \displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n c_{ij}x_{ij}
\]
\[s.t.
\begin{cases}
\displaystyle\sum_{j=1}^n x_{ij} = 1 \quad (i = 1, \cdots, n) \\
\displaystyle\sum_{i=1}^n x_{ij} = 1 \quad (i = 1, \cdots, n) \\
x_{ij} = 0或1 \quad (i, j = 1, \cdots. n)
\end{cases}
\]
指派问题可行解中，每行每列有且仅有一个1
非标准形式的指派问题
最大化指派问题
\(C = (c_{ij})_{n \times n}\)中最大元素为m，令\(B=(b_{ij})_n \times n = (m - c_{ij})_{n \times n}\)
人数和工作数不等
人多工作少: 添加虚拟的'人'，代价为0
人少工作多: 添加虚拟的'工作'，代价为0
一个人可以做多件工作
该人可化为几个相同的'人'
某工作一定不能由某人做
该人做该工作的相应代价取足够大M
指派问题的匈牙利算法的一般步骤
变换指派问题的系数(也称效率)矩阵(\(c_{ij}\))为(\(b_{ij}\))，使在(\(b_{ij}\))的各行各列中都出现0元素，即
(1) 从(\(c_{ij}\))的每行元素都减去该行的最小元素；
(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。
进行试指派，以寻求最优解。
在(\(b_{ij}\))中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(\(x_{ij}\))中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：
(1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎ 所在列(行)的其它0元素，记作Ø；这表示这列所代表的任务已指派完，不必再考虑别人了。
(2) 给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø；
(3) 反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
(4) 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。 然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。
(5) 若◎元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m < n,则转入下一步。
作最少的直线覆盖所有0元素。
(1)对没有◎的行打√号；
(2)对已打√号的行中所有含Ø元素的列打√号；
(3)再对打有√号的列中含◎ 元素的行打√号；
(4)重复(2)，(3)直到得不出新的打√号的行、 列为止；
(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数1。1应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若1 = m < n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。
变换矩阵(bij)以增加0元素。
在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。
指派问题的计算机解法
c = [3 8 2 10 3; 8 7 2 9 7; 6 4 2 7 5; 8 4 2 3 5; 9 10 6 9 10];
c = c(:) % 把矩阵c转化为向量
a = zeros(10, 25) % 10行25列
for i = 1:5
a(i, (i-1)*5 + 1:5*1) = 1;
a(5+i, i:5:25) = 1
end % 此循环把指派问题转化为线性规划问题
b = ones(10, 1)
[x, y] = linprog(c, [], [], a, b, zeros(25, 1), ones(25, 1));
X = reshape(x, 5, 5)
opt = y
求得最优指派方案为\(x_{15} = x_{23} = x_{32} = x_{44} = x_{51} = 1\), 最优值为21