第三节-割平面法

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

割平面法的基本思想是:首先不考虑整数条件,增加另外的约束条件,把原来的可行域切掉一部分,被切掉的部分不包含任何整数可行解.经过有限次的切割,最终得到某个顶点的坐标恰好是整数,并且是问题的最优解.3.3割平面法例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(34,74)A(11,)C例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(34,74)A(11,)C例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(11,)C割平面整数规划(A)松弛问题(B)1maxnjjjScx1(1,,)nijjijaxbim0jx且为整数1maxnjjjScx1(1,,)nijjijaxbim0jx回到一般问题上:设松弛问题(B)的最优单纯形表为:11immnxxxxx00010000mnSbbb1101111mnxbbb011iiiminxbbb011mmmmmnxbbb0ib设不是整数,01niijjijmxbxb再设000[],[],ijijijiiibbfbbf0011[][]nniijjijjiijmjmxbxfxbf表3-1即0011[][]nniijjijjiijmjmxbxfxbf0011[][]nniijjiiijjjmjmxbxbffx0(0,1)iijff整数010niijjjmffx若要决策变量都取整数,则10nijjjmfx01if011niijjjmffx即0011[][]nniijjijjiijmjmxbxfxbf0011[][]nniijjiiijjjmjmxbxbffx0(0,1)iijff整数010niijjjmffx若要决策变量都取整数,则对上式引入松弛变量iy010niijjijmffxy割平面不等式01nijjiijmfxyf割平面方程例1用割平面法求解整数规划问题12max79Sxx且为整数(I)(II)解(1)把约束条件中的系数化为整数,加上松弛变量,去掉整数约束,得到相应的松弛问题12123xx12157xx12,0xx12max79Sxx23136xxx124735xxx14,,0xx(II).用单纯形法求解问题,得最优单纯形表(II)S2x9210-12232272017221221x-6300-2811-1511最优解为,不是整数1292,72xx(2)引进以所在行为来源行的割平面:2x3412722122xx表3-2010niijjjmffx20233244()0ffxfxS2x9210-12232272017221221x-6300-2811-1511选择割平面的经验规则:①选择的值大的;②若相等,则选择小的.01niijjmff0if表3-2102012ff13142122322=2422ff2324722122=822ff√S2x9210-12232272017221221x-6300-2811-1511最优解为,不是整数1292,72xx(2)引进以所在行为来源行的割平面:2x3412722122xx表3-2010niijjjmffx20233244()0ffxfx割平面不等式3412722122xx加入松弛变量,得割平面方程1y34172212212xxy将割平面方程表达的约束条件加到单纯形表的最后一行,并把松弛变量补到最后一列S2x9210-1223220720172212201x-6300-2811-151101y1200-722-1221表3-33472212212xxS2x9210-1223220720172212201x-6300-2811-151101y1200-722-1221表3-3用对偶单纯形法求解,得最终单纯形表S2x32710017-173010011x-59000-1-83x11700117-227表3-4S2x32710017-173010011x-59000-1-83x11700117-227以为来源行得割平面不等式:1x414717670xy引进松弛变量,得割平面方程2y412176747xyy如前所述,修改单纯形表表3-4010niijjjmffx10133144()0ffxfxS2x32710017-17030100101x-59000-1-803x11700117-22702y47000-17-671S2x1x550000273x4x4100011301001010010414000167换基迭代,得124,3,55xxS表3-5表3-6请练习:100页习题三第3题(用割平面法求解)答案:122,14xxZ作业:用割平面法求解整数规划问题12121212max7936735,0Zxxxxxxxx且为整数答案:124,3,55xxZ胡运权习题集5.8(a)

1 / 18
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功