《运筹》教学课件整数规划第四章（三）割平面法.ppt

《《运筹》教学课件整数规划第四章（三）割平面法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、割平面法一、基本思想················割平面割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.问题：如何寻找割平面？增加的约束方程须满足什么条件才能使：1、割掉

2、松弛规划的最优解2、保留所有的整数解二、割平面法L0的最优单纯形表：x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0源方程------对应于生成行i的割平面L0的最优单纯形表：x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1

3、nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0生成行对应于生成行i的割平面非基变量b010.500-0.5100-1.75103.255.500-1011310-0.25000.751.500-0.500-1.5z-9对应第2行的割平面：对应第4行的割平面：非基变量如何求解？x1…xi…xmxm+1…xm+j…xn解检0…0…0c1…cm+j…cnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰

4、︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0ss0…0…0-fim+1…-fim+j…-fin1–fi000︰0︰0对偶单纯刑法四、割平面计算步骤：第一步：用单纯刑法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。停止若L0有最优解X0:(1)X0是整数解，则X0也是IP的最优解，停止(2)X0不是整数解，转第二步第二步：求割平面方程第三步：将割平面加到L0得L1第四步：解L1在L0的最优单纯型表中增加一行一列，得L1的单

5、纯型表，用对偶单纯刑法求解，若其解是整数解，则该解也是原整数规划的最优解否则将该解记为X0，返回第二步例用割平面法求解IP解：IP问题的松弛规划的标准型：X1X2X3X400-2.25-1.75Z-37.5X2010.25-0.251.5X1100.1250.3753.75X5000X500-0.125-0.3751-0.75X1X2X3X4X5ZX2X1X4000.3331-2.6672100013010.3330-0.667200-1.6670-4.667z-34整数最优值：Z=34例：用割平面法求解解：I

6、P的松弛规划的标准型X1X2X3X400-28/11-15/11Z-63X2017/221/227/2X110-1/223/229/2X500-7/22-1/221-1/2X5000X1X2X3X4X5X2X1X30011/7-22/711/71001/7-1/732/7010013000-1-8Z-59非整数X1X2X3X4X5X2X1X30011/7-22/711/71001/7-1/732/7010013000-1-8Z-59X6000-1/7-6/71-4/7X60000X1X2X3X4X5X60000

7、-2-7Z-55X20100113X11000-114X30010-411X400016-74整数最优值：Z=55作业：分别用分枝定界法和割平面法求解以下整数规划：最优值为：Z=4