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

1、精品課程運籌學(xué)2.1 gomory割平面法的基本思想割平面法的基本思想2.2 gomory割平面法計算步驟割平面法計算步驟精品課程運籌學(xué)2.1 gomory割平面法的基本思想割平面法的基本思想 考慮純整數(shù)線性規(guī)劃問題考慮純整數(shù)線性規(guī)劃問題 )(p可行區(qū)域記為可行區(qū)域記為d (p)的松弛問題的松弛問題 )(0p可行區(qū)域可行區(qū)域 0d由有限個或可數(shù)的格點由有限個或可數(shù)的格點構(gòu)成的集合構(gòu)成的集合 多面凸集多面凸集 為為整整數(shù)數(shù)向向量量xxbaxtsxct0.min 0.min xbaxtsxct精品課程運籌學(xué)的關(guān)系的關(guān)系和和0dd0dd ； 若若)(0p無可行解，則無可行解，則)(p無可行解；無可行

2、解； )(0p的的最最優(yōu)優(yōu)值值是是)(p的的最最優(yōu)優(yōu)值值的的一一個個下下界界； 若若)(0p的的最最優(yōu)優(yōu)解解0 x是是整整數(shù)數(shù)向向量量，則則0 x是是)(p 的的最最優(yōu)優(yōu)解解. 精品課程運籌學(xué)割平面法的基本思想割平面法的基本思想用單純形法先解松弛問題用單純形法先解松弛問題)(0p， 若， 若)(0p的最優(yōu)解的最優(yōu)解0 x是整數(shù)向量， 則是整數(shù)向量， 則0 x是是 ilp 問題問題)(p的最優(yōu)解，的最優(yōu)解，計算結(jié)束；計算結(jié)束； 費用減小方向費用減小方向0 x精品課程運籌學(xué)0 x若若0 x的的分分量量不不全全是是整整數(shù)數(shù)， 則則對對)(0p增增加加一一個個割割平平面面條條件件，將將)(0p的的可可

3、行行區(qū)區(qū)域域0d割割掉掉一一塊塊，0 x恰恰好好在在被被割割掉掉的的區(qū)區(qū)域域內(nèi)內(nèi)，而而原原 ilp 問問題題的的任任何何一一個個可可行行解解（格格點點）都都沒沒有有被被割割去去. 精品課程運籌學(xué)1x把把增增添添了了割割平平面面條條件件的的問問題題記記為為)(1p， 用用對對偶偶單單純純形形法法求求解解 lp 問問題題)(1p.若若)(1p的的最最優(yōu)優(yōu)解解1x是是整整數(shù)數(shù)向向量量，則則1x是是原原 ilp 問問題題)(p的的最最優(yōu)優(yōu)解解，計計算算結(jié)結(jié)束束； 精品課程運籌學(xué)否則對問題否則對問題)(1p在增加一個割平面條件，形成問在增加一個割平面條件，形成問題題)(2p，如此繼續(xù)下去，通過求解不斷改

4、進，如此繼續(xù)下去，通過求解不斷改進的松弛的松弛 lp 問題，知道得到最優(yōu)整數(shù)解為止問題，知道得到最優(yōu)整數(shù)解為止. *x精品課程運籌學(xué)生成割平面條件的代數(shù)方法生成割平面條件的代數(shù)方法(gomory)用用單單純純形形方方法法解解)(p的的松松弛弛問問題題)(0p 最優(yōu)基本可行解最優(yōu)基本可行解0 x ),(1mbbaab mbbxx,1基變量的下標(biāo)集合為基變量的下標(biāo)集合為 s非基變量的下標(biāo)集合為非基變量的下標(biāo)集合為 s最后一張單純形表中問題最后一張單純形表中問題)(0p的典式為的典式為 sjjjzxz0 sjijijbmibxaxr, 1,令令 zxb 0jja 000zb 精品課程運籌學(xué)如果如果m

5、ibi, 1 , 0, ，全是整數(shù)，我們已經(jīng)得到了，全是整數(shù)，我們已經(jīng)得到了ilp 問題問題)(p的最優(yōu)解的最優(yōu)解0 x. 否則至少有一個否則至少有一個lb不是整數(shù)不是整數(shù))0(ml ，設(shè)，設(shè)lb所對所對應(yīng)的約束方程是應(yīng)的約束方程是 sjljljbbxaxllllijljljfbbsjfaa ,sjflj , 1010 lf精品課程運籌學(xué) sjjljsjjljxaxa sjljljbbxaxllllijljljfbbsjfaa ,sjflj , 1010 lf sjljljbbxaxl sjljljbbxaxl)(llsjjljljbbxaa 相減相減精品課程運籌學(xué)lsjjljfxf sjjl

6、jsjjljxaxa sjljljbbxaxl sjljljbbxaxl)(llsjjljljbbxaa 相減相減gomory割平面條件割平面條件 lsjjljfsxf 割平面割平面 精品課程運籌學(xué)定理定理 3.2.13.2.1如如果果把把割割平平面面lsjjljfsxf 加加到到松松弛弛問問題題)(0p的的最最優(yōu)優(yōu)單單純純形形表表里里，那那么么沒沒有有割割掉掉原原ilp 的的任任何何整整數(shù)數(shù)可可行行點點，當(dāng)當(dāng)lb不不是是整整數(shù)數(shù)時時，新新表表里里是是一一個個原原始始基基本本不不可可行行解解和和對對偶偶可可行行解解. 精品課程運籌學(xué)證證 由由于于割割平平面面lsjjljfsxf 是是由由原原

7、ilp 的的整整數(shù)數(shù)約約束束推推出出來來的的，所所以以它它不不會會割割掉掉整整數(shù)數(shù)可可行行解解；松松弛弛變變量量 s是是新新的的基基變變量量， 并并且且它它與與原原來來的的基基變變量量mbbxx,1一一起起構(gòu)構(gòu)成成了了新新松松弛弛問問題題的的基基變變量量，當(dāng)當(dāng) lb不不是是整整數(shù)數(shù)時時，0 lf，因因此此新新松松弛弛問問題題的的基基本本解解中中有有0 lfs，因因此此它它對對應(yīng)應(yīng)的的是是新新松松弛弛問問題題的的原原始始基基本本不不可可行行解解.由由于于表表中中第第 0 行行（檢檢驗驗數(shù)數(shù)行行）沒沒有有改改變變，所所以以它它仍仍保保持持對對偶偶可可行行性性. 精品課程運籌學(xué)2.2 gomory割

8、平面法計算步驟割平面法計算步驟 第第1步步 用單純形法解用單純形法解 ilp 問題問題)(p 的松弛問題的松弛問題)(0p .若若)(0p 沒有最優(yōu)解，則計算停止，沒有最優(yōu)解，則計算停止，)(p 也沒有最優(yōu)也沒有最優(yōu)解解.若若)(0p 有最優(yōu)解有最優(yōu)解0 x ，假若，假若0 x 是整數(shù)向量，則是整數(shù)向量，則0 x 是是)(p 的最優(yōu)解，計算停止，輸出的最優(yōu)解，計算停止，輸出0 x ；否則轉(zhuǎn)第；否則轉(zhuǎn)第2 步步. 第第2步步 求割平面方程求割平面方程 lsjjljfsxf 精品課程運籌學(xué)第第3步步 將將割割平平面面方方程程lsjjljfsxf 加加到到第第 1 步步所所得得最最優(yōu)優(yōu)單單純純形形表

9、表中中，用用對對偶偶單單純純形形法法求求解解這這個個新新的的松松弛弛問問題題.若若其其最最優(yōu)優(yōu)解解為為整整數(shù)數(shù)解解，則則它它是是問問題題)(p的的最最優(yōu)優(yōu)解解，計計算算停停止止，輸輸出出這這個個最最優(yōu)優(yōu)解解；否否則則將將這這個個最最優(yōu)優(yōu)解解重重新新記記為為0 x，返返回回第第 2 步步.若若對對偶偶單單純純形形算算法法發(fā)發(fā)現(xiàn)現(xiàn)了了對對偶偶問問題題是是無無界界的的，此此時時原原 ilp 問問題題是是不不可可行行的的，計計算算停停止止. 精品課程運籌學(xué)例例3.2.13.2.1 求解求解ilp問題問題 max x21x2x0123123解解 這個問題及其松弛這個問題及其松弛lp問問題的可行區(qū)域如圖所

10、示題的可行區(qū)域如圖所示 整數(shù)整數(shù), 0,023623.max2121212 xxxxxxtsx精品課程運籌學(xué)增增加加松松弛弛變變量量3x和和4x，得得到到了了松松弛弛 lp 問問題題的的第第一一張張單單純純形形表表 000236012301010434321 xxzrhsxxxx精品課程運籌學(xué)經(jīng)過兩次旋轉(zhuǎn)變換得到最優(yōu)單純形表為經(jīng)過兩次旋轉(zhuǎn)變換得到最優(yōu)單純形表為 23414110161610123414100214321xxzrhsxxxx tx 23, 10最最優(yōu)優(yōu)解解為為23 z最最優(yōu)優(yōu)值值為為21414143 xx精品課程運籌學(xué)000236012301010434321 xxzrhsxxx

11、x21414143 xx213236xxx 21423xxx 12 x max x21x2x0123123精品課程運籌學(xué)經(jīng)過兩次旋轉(zhuǎn)變換得到最優(yōu)單純形表為經(jīng)過兩次旋轉(zhuǎn)變換得到最優(yōu)單純形表為 23414110161610123414100214321xxzrhsxxxx tx)23, 1(0 23 z21414143 xx21434343 xx342 x12 x精品課程運籌學(xué)214141143 sxx2114141002304141101061610123041410012114321 sxxzrhssxxxx精品課程運籌學(xué)利用對偶單純形算法解上表中的松弛問題利用對偶單純形算法解上表中的松弛問題)(1p， 得到， 得到關(guān)于問題關(guān)于問題)(1p的最優(yōu)單純形表為的最優(yōu)單純形表為 24110011001032323100111000032114321 xxxzrhssxxxx精品課程運籌學(xué)24110011001032323100111000032114321 xxxz