1、第 五 章 整 数 规 划w 求解整数规划问题的分枝定界法w 求解整数规划问题的割平面法w 求解 0 1规划问题的隐枚举法w 求解指派问题的匈牙利法w 软件使用本章内容重点 考虑带有取整要求的线性规划问题 分类：纯整数规划、混合整数规划 处理方法：四舍五入、截尾取整：如何？ 例第一节 整数规划问题的提出货 物 每箱体 积 每箱重量 每箱利 润甲 5 2 20乙 4 5 10托运限制 24 13问：两种货物各托运多少，可以使总利润最大？第一节 整数规划问题的提出Max z =20x1+10x2 5x1+4x2 242x1+5x2 13x1 ,x2 0, 且取整 解得： x1 4.8, x2 0,
2、z 96。四舍五入： x1 5, x2 0；截尾取整： x1 4, x2 0,z 80。非 可行解非 最优解基本思想第二节 分枝定界法Max z =40x1+90x2 9x1+ 7x2 567x1+20x2 70x1 ,x2 0, 且取整 （ A）Max z =40x1+90x2 9x1+ 7x2 567x1+20x2 70x1 ,x2 0 （ B）通过求解（ B） 来求解（ A）。定界 ：观察出（ A） 最优目标值的一个下界；（ B）的 最优值给出（A） 最优值的一个上界。当上下界相等时达到最优。否则分枝 ：将（ B） 的可行域中不可能产生（ A）可行解的区域去掉，从而将（ B） 分为两个问
3、题，分别求其最优解。之后，再定界 。可以求解纯整数规划以及混合整数规划BX1 4.81， X2 1.81Z 356B1X1 4.00， X2 2.10Z 349B2X1 5.00， X2 1.57Z 341B11X1 4.00， X2 2.00Z 340B12X1 1.42， X2 3.00Z 327B21X1 5.44， X2 1.00Z 308B22无可行解0 z 3560 z 349340 z 341340 z 340X1 4 X1 5X2 2 X2 3X2 1 X2 2第三节 割平面法 割平面法的基本思想 这里仅介绍求解纯整数规划的割平面法 基本步骤：设整数规划问题（ IP），对应的松
4、弛问题为（ P） 用单纯形法求解问题（ P），设得到（ P）的最优解。 若（ P）的最优解符合取整约束，则停止；否则，必有一个基变量 Xi取值为分数。 任取一个基变量取值为分数的约束，构造切割平面（新约束）。 将新约束加入到原约束中，求解新的松弛问题（ P）。用灵敏度分析的方法求解问题（ P），转 。第三节 割平面法 例：求解Max z x1 x2 x1+x213x1+x24x1、 x20，且取整注意：要求每个 bi，以及 aij必须取整。否则，可以对相应的约束乘上一个数，使其变为整数。Max z x1 x2 x1+x2 x3 13x1+x2 x4 4x1， x2， ， x40，且取整用单纯形法求解之，得到最终单纯形表。第三节 割平面法Cj 1 1 0 0 CB XB b X1 X2 X3 X411X1X23/47/41 0 -1/4 1/40 1 3/4 1/4z 5/2 0 0 -1/2 -1/2 若 bi不是整数，则取出将 bi、 aik都分解为整数与非负真分数之和，即则，该约束可以写成第三节 割平面法Cj 1 1 0 0 CB XB b X1 X2 X3 X411X1X23/47/41 0 -1/4 1/40 1 3/4 1/4z 5/2 0 0 -1/2 -1/2 有切割方程：或：
