《北邮运筹学ch5-3_割平面法》由会员分享，可在线阅读，更多相关《北邮运筹学ch5-3_割平面法（11页珍藏版）》请在金锄头文库上搜索。
1、5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 1 of 112013-5-17 设纯整数规划 njxbxaxcZ ji n j jij n j jj , 10max 11 且为整数， 松弛问题 njxbxaxcZ ji n j jij n j jj , 10max 11 ， 的最优解 T m T bbbbBbbBX),()0 ,( 21 11 设xi不为整数， 为非基变量 k k kikii xxabx 运筹学 北京邮电大学 k 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integ
2、er Programming Page 2 of 112013-5-17 将分离成一个整数与一个非负真分数之和： iki ab及 10 , 10 , ikiikikikiii fffaafbb 则有 kikkijiii xfxafbx 则有 kk k k ikik k ijii xffxabx 等式两边都为整数并且有 1fxff 运筹学 北京邮电大学 1 ik k iki fxff 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 3 of 112013-5-17 0 k k iki xff 则 加入松弛变量si得 k
3、 加松弛变量 i得 ik k iki fxfs k 此式称为以x行为源行（来源行）的割平面或分数切割式此式称为以xi行为源行（来源行）的割平面，或分数切割式， 或R.E.Gomory(高莫雷)约束方程。 将Gomory约束加入到松弛问题的最优表中，用对偶单纯 形法计算，若最优解中还有非整数解，再继续切割，直到全 运筹学 北京邮电大学 部为整数解。 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 4 of 112013-5-17 3 5 46 1 36 5 1 xxx 例如 3 2 43 1 33 2 2 xxx 例如
4、， 255 3 2 46 5 36 5 1 1)1(xxxx1行： 移项 552 1xxxx移项： 4636341 1xxxx 令0 46 5 36 5 3 2 xx令0 46363 xx 加入松弛变量s1得 3 2 46 5 36 5 1 xxs 346361 同理，对于x2行有： 211 运筹学 北京邮电大学 3 2 43 1 33 1 2 xxs 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 5 of 112013-5-17 如果在对偶单纯形法中原切割方程的松弛变量仍为基 变量，则此松弛变量所在列化为单位向量
5、后就可以去掉该 行该列，再切割。 【例】已知整数规划【例】已知整数规划 23max 21 xxz 为整数 92 1432 21 21 xx xx 且为整数0, 21 xx 【解】不考虑整数约束，松弛问题的最优表如下 运筹学 北京邮电大学 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 6 of 112013-5-17 3200 最优表 cj3200 b CBXBx1x2x3x4 2x2011/21/25/2 3x1101/43/413/4 1 j001/45/4 最优解 T 不满足整数要求选最优解X=(1/2，3/4
6、，0，0)T，x1 、x2不满足整数要求，选 择x2行进行分割： 2 5 42 1 32 1 2 xxx 242322 2 1 42 1 432 1 2 2xxxx 运筹学 北京邮电大学 2 1 42 1 32 1 5 xxx得到Gomory约束添加到最优表中，得 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 7 of 112013-5-17 cj32000 bCXxxxxxbCBXBx1x2x3x4x5 2x2011/21/205/2 3x101/43/4013/43x1101/43/4013/4 0 x5001
7、/21/211/2 001/45/40j001/45/40 2x201012 3x110011/27/2 0 x3001121 j00011/2 x行 71 xxx 运筹学 北京邮电大学 x1行： 2 7 52 1 41 xxx Gomory约束 2 1 52 1 6 xx添加到最优表中，得 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 8 of 112013-5-17 cj320000 b CXxxxxxx b CBXBx1x2x3x4x5x6 2x2010102 310011/407/33x110011/407
8、/3 0 x30011101 0 x600001/211/2 j00011/20 2x20101021 3x11001014 0 x30011043 0 x60000121 运筹学 北京邮电大学 6 j000101 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 9 of 112013-5-17 得到整数最优解：X(4，1)，Z14 注1 511 xxx注1： 242322 xxx 0 42 1 32 1 2 1 xx 1 435 xxx Gomory约束可写为 注2：Gomory约束只是割去线性规划可行域的一部分，
9、保 留了全部整数解。留部数解 用图解法表示： 运筹学 北京邮电大学 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 10 of 112013-5-17 1122 21 xx 13/4,5/2 松弛问题 第次切割 松弛问题 第一次切割 x +x 5 4,1 第二次切割 x1+x25 运筹学 北京邮电大学 第二次切割 5.3 割平面法割平面法 Cutting-plane Method Ch5 Integer Programming Page 11 of 112013-5-17 1.领会割平面法的基本原理 1.分离源行，求出Gomory约束1.分离源行，求出Gomory约束 2.在最优表中增加Gomory约束，用 对偶单纯形法迭代 作业教材P134 T5 3作业：教材P134 T5.3 01规划指派问题 E it 运筹学 北京邮电大学 01规划指派问题 Exit
