课程笔记

04整数规划

Lingfeng 2025-03-26

04整数规划

1. 分支定界法

Definition (分支定界法)

定界：记目标函数的最优值为 $Z^{*}$ ，设 LP 作为 $Z^{*}$ 的上界，记为 $\bar{Z}$ 。用观察法找到可行解，对应目标函数值作为下界，记为 $\underline{Z}$ ，则有 $\underline{Z}\leq Z^{*}\leq \bar{Z}$
分支：在 LP 的最优解中，任选一个不符合整数条件的变量 $X_{r}=b_{r}$ ，构造 $X_{r}\leq [b_{r}],\quad X_{r}\geq [b_{r}]+1$ 将这两个约束条件分别加入 LP 构成 LP1 和 LP2
修改上下界：在各分支中找到目标函数最大值。在已符合整数条件的分支中，找到目标函数最大者作为新下界。更新 $\bar{Z}=\min\{ Z(\mathrm{LP_{1}}),Z(\mathrm{LP_{2}}) \}$
比较与剪枝：若分支最优解小于 $\underline{Z}$ ，则剪枝。直到 $\underline{Z}=Z^{*}=\bar{Z}$ 为止

2. 割平面法

Definition (割平面法)

用单纯型法求解松弛问题 LP
在 LP 最优解中，任选一个不为整数的分量 $x_{r}$ ，将最优单纯型表中该行的系数 $a_{rj}$ 和 $b_{r}$ 分解为整数部分和小数部分之和，作割平面方程为 $f_{r}-\sum_{j = m+1}^{n} f_{rj}x_{j}\leq 0$ 其中 $f_{r}$ ， $f_{rj}$ 分别是 $b_{r}$ ， $a_{rj}$ 的小数部分。

3. 指派问题

Definition (指派问题)

\begin{align*} &\min\sum_{i = 1}^{n} \sum_{j = 1}^{n} c_{ij}x_{ij}\\ &\mathrm{s.t.}\begin{cases} \sum_{i = 1}^{n} x_{ij}=1, & i=1,2,\dots,n\\ \sum_{j = 1}^{n} x_{ij}=1,&j=1,2,\dots,n \\ x_{ij} \in \{ 0,1 \},\forall i,j\end{cases} \end{align*}

3.1 匈牙利算法

3.2 表上作业法

指派问题是特殊的运输问题，所以可以使用表上作业法。

4. 非标准的指派问题

4.1 最大化指派问题

设最大化指派问题系数矩阵为 $C$ ，最大元素为 $m$ 。只需令 $B=m-C$ 即可。

4.2 人数和事数不等的指派问题

人少事多：添加虚拟的人，虚拟人做事的费用为 0
事多人少：添加虚拟的事，被人做的费用为 0。

4.3 一个人可能几件事的指派问题

若一个人可做几件事，则把人化为相同的几个人即可。

4.4 某事一定不能由某人做

若某事一定不能有某人做，则将相应费用系数取作足够大的数 $M$ 。