第二節(jié)Gomory割平面法ppt課件

1、 Gomory 割平面法基本思想 Gomory 割平面法計算步驟0PP整數(shù)規(guī)劃整數(shù)規(guī)劃松弛的線性規(guī)劃問題松弛的線性規(guī)劃問題( )( )為整數(shù)xxbAxtsxc, 0. .zmin兩個問題具有如下明顯關(guān)系：(1) ( )的可行域 是( )的可行域的子集;(2) 假設(shè)( )無可行解，那么( )無可行解；(3) ( )的最優(yōu)值優(yōu)于( )的最優(yōu)值的；(4) 假設(shè)( )的最優(yōu)解是整數(shù)向量，則它也是( )的最優(yōu)解.0PPP0P0PP0PP 由松弛問題的可行由松弛問題的可行域向整數(shù)規(guī)劃的可域向整數(shù)規(guī)劃的可行域逼近行域逼近 方法方法利用超平面切利用超平面切除除 要求要求 整數(shù)解保留整數(shù)解保留 松弛問題最優(yōu)值增

2、松弛問題最優(yōu)值增加加。 。 。0 x（松弛問題最優(yōu)解）（松弛問題最優(yōu)解）1x*x費用減少方向費用減少方向(整數(shù)規(guī)劃最優(yōu)解整數(shù)規(guī)劃最優(yōu)解)割割平平面面生生成成方方法法條件條件-保留整數(shù)解刪除非整數(shù)最優(yōu)解保留整數(shù)解刪除非整數(shù)最優(yōu)解!下面是求下面是求 P P的松弛問題最后一張單純形表：的松弛問題最后一張單純形表：rNjjrjrbxaxNB1I0N0BbBcB101bbBBxNx它所對應(yīng)的約束方程為不是整數(shù)，的最優(yōu)解；否則設(shè)分量也是是一個整數(shù)向量，則它如果rbb(P)rNjjrjrbxaxrNjjrjrbxax rNjjrjrbxax01,rjrjrjrjaaffrjrjaa01,rrrrbbff r

3、rbb rNjjrjrbxaxrNjjrjrbxax rrNjjrjrjbbxaa)(,rrrjrjrjrfaafbb加入松弛變量加入松弛變量s srjjrrj Nf xsf 割平面即即1xnx2x1mxmx0111 ma01m00110nna11mmamna1bmbrx011rmarnarbbBcB1不是整數(shù)不是整數(shù)P0最終表最終表1xnx2x1mxmx0111 mabBcB101m00110nna11mmamna1bmbrx011rmarnarbrs000011rmarna1 rb1xnx2x1mxmx0111 ma01m00110nna11mmamna1bmbrx011rmarnarbr

4、s000011rmrmaarnrnaa1 rrbbbBcB101xnx2x1mxmx0111 ma01m00110nna11mmamna1bmbrx011rmarnarbrs00001rmfrnf1rfbBcB100rf用對偶單純形法求解用對偶單純形法求解定理定理3.2.1 如果把割平面如果把割平面加到松弛問題的最優(yōu)單純形表里，那么沒有割加到松弛問題的最優(yōu)單純形表里，那么沒有割掉原掉原ILP的任何整數(shù)可行點；當?shù)娜魏握麛?shù)可行點；當bi不是整數(shù)不是整數(shù)時，新表是一個原始基本不可行解和對偶可行時，新表是一個原始基本不可行解和對偶可行解。解。rjjrj Nf xsf 求松弛問題的求松弛問題的最優(yōu)基可

5、行解最優(yōu)基可行解判斷是否判斷是否為整數(shù)解為整數(shù)解是是得到最優(yōu)解得到最優(yōu)解否否在單純性表中加入在單純性表中加入一行利用對偶單純一行利用對偶單純形算法求最優(yōu)解形算法求最優(yōu)解rjjrrj Nf xsf 例例3.2.13.2.1 求解求解ILPILP問題問題整數(shù), 0,023623. .max2121212xxxxxxtsx(1,1.5)松弛問題的最優(yōu)解是松弛問題的最優(yōu)解是1，1.5), 不是整數(shù)解不是整數(shù)解,從圖中看從圖中看出出(1，1)是是ILP問題的最優(yōu)解，問題的最優(yōu)解，212312412343263200max. .,xxxxs txxxxxxx下面用割平面法求解整數(shù)規(guī)劃下面用割平面法求解整數(shù)

6、規(guī)劃1、先求其松弛問題的最優(yōu)解、先求其松弛問題的最優(yōu)解1x3x2x4x010 0031206310021x3x2x4x005 . 0061165 . 15 . 000105 . 132zxx34zxx1x3x2x4x006/16/1414/12/3101104/14/12/300112zxx松弛問題的最優(yōu)解是松弛問題的最優(yōu)解是1，3/2),最優(yōu)值為最優(yōu)值為Z*= 3/2，不是整數(shù)解。，不是整數(shù)解。006/16/1414/12/ 3101104/14/12/30000101112zxx1x3x2x4x1s以第二行生成割平面以第二行生成割平面割平面方程為割平面方程為將其加到表中得將其加到表中得34

7、1111442xxs 1x3x2x4x1s006/16/1414/12/ 3101104/14/12/30001 4/1 2/10121zxxs01 4/利用對偶單純形法求解利用對偶單純形法求解得得1x3x2x4x003/1101011s3/2024011001103/20011x3x2x4x006 / 16 / 1 4 14 / 12 / 3101104 / 1 4 / 1 2 / 3 1s00002 / 1 14 / 1 4 / 1 012zxx123zxxx它的最優(yōu)解為它的最優(yōu)解為(2/3,1), 仍不是整數(shù)解。仍不是整數(shù)解。以第一行生成的割平面方程為以第一行生成的割平面方程為41222

8、2333xss 加到表中，得用對偶單純形法求解得用對偶單純形法求解得1x3x2x4x003/1101011s3/2024011001103/20012s000023323210001232sxxzx將將1x3x2x4x00101011s01501001100012s002/ 300011102/ 3012/ 11最優(yōu)解為1，1）.1234xxzxx(1,1.5)21x 12xx第一個割平面條件第一個割平面條件 第二個割平面條件第二個割平面條件21x ，12xx書書P99習題習題31212121252840min. .,zxxxxs txxxx且為整數(shù)且為整數(shù)解：（解：（1）(16/3, 4/3

9、)4 5 6 7 84最優(yōu)解為最優(yōu)解為x*=（5,1），），最優(yōu)值最優(yōu)值z*=0, 125xxh（2引入松弛變量引入松弛變量x3、剩余變量、剩余變量x4和人工變量和人工變量x5, 原問題的松弛問題轉(zhuǎn)化為原問題的松弛問題轉(zhuǎn)化為12123124512528240min. .,zxxxxxs txxxxxx用兩階段法，先用兩階段法，先求解下模型，列求解下模型，列單純形表單純形表注意本題不能用注意本題不能用對偶單純形法對偶單純形法125123124512528240minmin. .,zxxgxxxxs txxxxxxx1x2x3x4x5RHSz-150000g0000-10 x3121008x51-10-114z-150000g1-10-104x3121008x51-10-114z040-114g0000-10 x30311-14x11-10-114x1x2x3x4RHSz040-14x303114x11-10-14z00-4/3-7/3-4/3x2011/31/34/3x1101/3-2/316/3 0 -1 5在上表中加入割平面方程在上表中加入割平面方程 -1/3x3-1/3x4+s1=-1/3,繼續(xù)迭代，繼續(xù)迭代，x1x2x3x4