运筹学教程 第2版 教学课件 作者 邱菀华 冯允成 第4章.ppt

《运筹学教程 第2版 教学课件 作者 邱菀华 冯允成 第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整数线性规划第四章整数线性规划4.1整数线性规划4.2分枝定界法4.3割平面法4.1整数线性规划例4-1某厂生产A、B两种产品，单件工时定额及利润等见表4-1。试求最优产品组合的生产计划。表4-1已知数据表定额工时产品部门AB可用工时制造部门/h9756装配部门/h72070利润/元4090p（最大）第一节整数线性规划解　按照生产计划问题的通常解法。设x１和x２分别表示计划生产A和B的件数，可建立下列线性规划模型：问题１：maxp=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥04.1整数线性规划用单纯形法求得

2、问题１的最优解为。这个解不满足取整数的实际要求，故本例的正确提法应为解下列整数线性规划问题。问题２：maxp＝４０x１＋９０x２s．t．９x１＋７x２≤５６７x１＋２０x２≤７０x１，x２为非负整数4.1整数线性规划问题２与问题１的差别仅在于增加了解答整数限制。这一差异使两者具有了本质的不同。从图4-1可以看出，问题１的可行域是图中的阴影部分，而问题２的可行域由图中画＋号的离散点组成。这表明整数线性规划是一个离散最优化问题。由图4-1可知，点A是问题２的最优解。它既不是问题１的最优解点B的近似值（x１≈５，x２≈２的点，连可行解都不是），也不是可行

3、域的顶点。但是，问题１与问题２具有解之间的紧密关系：问题２的可行域包含在问题１的可行域之中。因此，问题１的最优值是问题２的目标值的上界（对最大问题）。4.1整数线性规划将整数线性规划的整数性限制去掉后，得到的线性规划问题，称为原整数线性规划的松弛问题。求解松弛问题可提供原问题目标值的上界（对于求极大问题）或下界（对于求极小问题）。4.2分枝定界法分枝定界法是求解整数线性规划的一个重要方法。我们结合上例进行介绍。用分枝定界法求解例4-1的问题２。其对应的松弛问题的最优解不是整数，因而不是原问题的解。但由此可知，对于原问题的解，或者x１≤４，或者x１≥５

4、。因而在原问题的约束条件中分别加上上述两个不等式，就将它分成以下两枝求解（注意：可以用x２作节点分枝，解法同样，不再赘述）。4.2分枝定界法分枝问题１maxp＝４０x１＋９０x２s．t．９x１＋７x２≤５６７x１＋２０x２≤７０x１≤４x１，x２≥０分枝问题２maxp＝４０x１＋９０x２s．t．９x１＋７x２≤５６７x１＋２０x２≤７０x１≥５x１≥０，x２≥０4.2分枝定界法这两个分枝问题至少有一个含有原问题的解。事实上，产生分枝问题就是将松弛问题的可行域进行分割，舍去那些不含原问题解的区域（见图4-2）。也可以这样体会：产生分枝问题，就把原问题的

5、可行域（整数解）分成若干部分，每一部分是一个分枝问题的可行域。于是，对于原问题的求解，就转换成分别对分枝问题进行求解了。由于任一分枝问题解的目标值都代表该分枝问题所含整数解的目图4-2分枝问题的可行域标值上界，故所有分枝问题解中最优者，如为整数解，则必为原问题的最优解。此外，若所有分枝问题均无可行解，则原问题也无可行解。4.2分枝定界法求解分枝问题１和２，所得结果列表5-2中。从该表中可以看出，分枝问题１的解优于分枝问题２的解，但仍不是整数解。于是对分枝问题１的解x２再进行分枝：x２≤２和x２≥３，并将它们分别加到分枝问题１的约束条件中，得到新的分枝

6、问题３和分枝问题４。这两个分枝问题的求解结果列于表4-3中。4.2分枝定界法表4-2分枝问题解表一表4-3分枝问题解表二分枝问题1分枝问题2分枝问题3分枝问题4x1=4x1=5x1=4x1=1.428x2=2.1x2=1.571x2=2x2=3P=349P=341.428P=340P=327.1434.2分枝定界法分枝问题３的解为整数解，但它不优于分枝问题２的解，故还不能断定是否是原问题的最优解。比较分枝问题２、３和４（因分枝问题３已得整数解，故求解结束了）可知，接下去对问题２的x２进行分枝，分别将x２≤１和x２≥２加入原问题的约束条件得新的分枝问题

7、５和分枝问题６。求解这两个分枝得的解列于表4-4中。分枝问题5分枝问题6x1=5.444无解x2=1P=307.7784.2分枝定界法再比较分枝问题３、４和５，分枝问题３的解最优且为整数，故为整数线性规划的最优解。综上所述，可得分枝定界法的计算步骤如下：１）解对应整数线性规划的松弛问题（以下简记为问题B），若B无解，则原问题也无解，计算结束；若B有解，转２）。２）检查B的最优解，若它满足整数条件，则它就是原问题的最优解，计算结束；否则转３）。３）任选B的最优解中不满足整数条件的一个变量xi，设xi的值为。构造两个新分枝问题，它们是对问题B分别各增

8、加以下一个约束条件而得：4.2分枝定界法上式中的为小于的最大整数，并求解这两个分枝问题，转入下步。４）将无解