发布时间 : 星期三 文章第11章 整数规划方法更新完毕开始阅读
第十一章 整数规划方法
11.1 整数规划的模型
如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题，其模型称为整数规划模型。
如果整数规划的目标函数和约束都是线性的，则称此问题为整数线性规划问题。在里我们只就整数线性规划问题进行讨论，整数线性规划的一般模型为：
max(min)z??cjxjj?1n
（11.1） ?nax?(?,?)b(i?1,2,???,m)i??ijjs.t.?j?1?x?0,x为整数(j?1,2,???,n)j?j 对于实际中的某些整数规划问题，我们有时候可以想到先略去整数约束的条件，即视为
一个线性规划问题，利用单纯形法求解，然后对其最优解进行取整处理。实际上，这样得到的解未必是原整数规划问题的最优解，因此，这种方法是不可取的，但可借鉴于这种思想。 整数规划求解方法总的基本思想是：松弛问题(11.1)中的约束条件（譬如去掉整数约束条件），使构成易于求解的新问题――松弛问题(A)，如果这个问题(A)的最优解是原问题(11.1)的可行解，则就是原问题(11.1)的最优解；否则，在保证不改变松弛问题(A)的可行性的条件下，修正松弛问题(A)的可行域(增加新的约束)，变成新的问题（B），再求问题(B)的解，重复这一过程直到修正问题的最优解在原问题(11.1)的可行域内为止，即得到了原问题的最优解。
注意到: 如果每个松弛问题的最优解不是原问题的可行解时，则这个解对应的目标函数值z一定是原问题最优值z的上界(最大化问题)，即z?z，或下界(最小化问题)，即z?z。
***11.2 整数规划的分枝定界法
11.2.1. 分枝定界法的基本思想
将原问题（11.1）中整数约束去掉变为问题（A），求出问题（A）的最优解，如果它不是原问题（11.1）的可行解，则通过附加线性不等式约束（整数），将问题（A）分枝变为若干子问题(Bi)(i?1,2,???,I)，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，就得两个子问题，继续求解定界，重复下去，直到得到最优解为止。
· ·166
例11.1 用分枝定界法求解下列整数规划问题
maxz?40x1?90x2（A） ??9x1?7x2?56
?7x1?20x2?70?x,x?0,且为整数?12 解（1）去掉x1,x2为整数的约束，变为问题(A0)，求解可得(A0)的最优解为
x1?4.81,x2?1.82,z0?356?z，令z?0，且0?z?z*?z?356。显然不是（A）的
可行解。
（2）分枝：对x1?4.81附加约束条件x1?4,x1?5，将（A）分为两个子问题(B1)和
(B2)：
maxz?40x1?90x2?9x1?7x2?56 (B2) (B1) ?7x?20x?70?12?0?x?4,x?012?是问题（A）的可行解，取z?349,z?0。
（3）对问题(B1)，(B2)分枝：
对问题(B1):x2?2.1附加约束x2?2,x2?3分为问题(C1)，(C2) 对问题(B2):x2?1.57附加约束x2?1,x2?2分为问题(C3)，(C4)
maxz?40x1?90x2?9x1?7x2?56??7x1?20x2?70?x?5,x?02?1
求解可得(B1)：x1?4,x2?2.1,z1?349，(B2)：x1?5,x2?1.57,z2?341。仍不
maxz?40x1?90x2?9x1?7x2?56 (C2) (C1) ?7x?20x?70?12?0?x?4,0?x?212?maxz?40x1?90x2?9x1?7x2?56 ?7x?20x?70?12?0?x?4,x?312?maxz?40x1?90x2?9x1?7x2?56(C3) ??7x1?20x2?70?x?5,0?x?12?1分别求解可得：
maxz?40x1?90x2 (C4) ??9x1?7x2?56?7x1?20x2?70?x?5,x?22?1
(C1):x1?4,x2?2,z3?340； (C2):x1?1.42,x2?3,z4?327； (C3):x1?5.44,x2?1,z5?308； (C4)：无可行解。
因为(C1)的解为（A）的可行解，故取z?340,z?341，注意到z4,z5?z?340，则对(C2)和(C3)无需再分枝，将其剪掉。由z?340?z*?z?341可知，已得到了问题（A）
·167·
**的最优解x1?4,x2?2,z*?340。
11.2.2 分枝定界法的一般步骤
（1）将原整数规划问题（11.1）去掉所有的整数约束变为线性规划问题（A），用线性规划的方法求解问题（A），则有下列情况：
1） 问题（A）无可行解，则原问题（11.1）也无可行解，停止计算；
2）问题（A）有最优解X，并是原问题（11.1）的可行解，则此解就是（A）的最优解，计算结束；
3） 问题（A）有最优解X，但不是原问题（11.1）的可行解，转下一步。
（2）将X代入目标函数，其值记为z，并用观察法找出原问题（11.1）的一个可行解（整数解，不妨可取xj?0(j?1,2,???,n)），求得目标函数值（下界值），记为z，则原问题（11.1）的最优值记为z，即有z?z*?z，转下一步；
（3）分枝：在问题（A）的最优解中任选一个不满足整数约束的变量xj?bj（非整数），附加两个整数不等式约束：xj?[bj]和xj?[bj]?1，分别加入到问题（A）中，构成两个新的子问题(B1)和(B2)，仍不考虑整数约束，求问题(B1)和(B2)的解。
定界：对每一个子问题的求解结果，找出最优值的最大者为新的上界z，从所有符合整数约束条件的分枝中找出目标函数值最大的一个为新的下界z。
（4）比较与剪枝：将各分枝问题的最优值同z比较，如果其值小于z，则这个分枝可以剪掉，以后不再考虑。如果其值大于z，且又不是原问题（11.1）的可行解，则继续分枝，返回（3），直到最后得到最优解使z*?z，即xj(j?1,2,???,n)为原问题（11.1）的最优解。
*****11.3 整数规划的割平面法
11.3.1 割平面法的基本思想
首先把原整数规划问题（11.1）去掉整数约束条件变为线性规划问题（A），然后引入线性约束条件（称为Gomory约束，几何术语割平面）使问题（A）的可行域逐步缩小（即切割掉一部分），每次切割掉的是问题的非整数解的一部分，不切掉任何整数解，直到最后使得目标函数达到最优的整数解（点）成为可行域的一个顶点为止，这就是原问题（11.1）的最优解。即利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。
例11.2 用割平面法求解下列整数规划问题
· ·168
maxz?x1?x2 ???x1?x2?1
?3x1?x2?4?x,x?0,且为整数?12maxz?x1?x2将其化为标准型
（A） ???x1?x2?x3?1
?3x1?x2?x4?4?x,x,x,x?0,且为整数?1234去掉整数约束条件，用单纯形法求解相应的线性规划问题，可得非整数的最优解为
x1?375,x2?,x3?x4?0,z?，由变量之间的关系可以得到关系式 442113?x?x?x???143444 ?
?x?3x?1x?7?1?3234?4444??3?31?x?x??x?x4??33?1444???将整数与真分式分开有?
31??x?1?3??x?x4??23?4?44?? 因为x1,x2,x3,x4?0，且为整数，即左端为整数，右端也必为整数，所以
3?31???x3?x4??0，即?3x3?x4??3为所求的切割方程。将其加到问题的约束条件之4?44?中，构成新的问题（B），求解引入松弛变量x5，则有?3x3?x4?x5??3，即求问题
maxz?x1?x2??x1?x2?x3?1? （B） ?3x1?x2?x4?4
???3x3?x4?x5??3??x1,x2,x3,x4,x5?0 用单纯形法求解，则可得到问题（B）的最优解为x1?x2?x3?1，显然是原问题的可行解，即为所求的最优解，其最优值为z?2。
·169·