運(yùn)籌學(xué)-整數(shù)規(guī)劃

1、上頁(yè)下頁(yè)返回整數(shù)規(guī)劃（整數(shù)規(guī)劃（integer programming)1.幾個(gè)實(shí)例幾個(gè)實(shí)例2.整數(shù)規(guī)劃的算法整數(shù)規(guī)劃的算法分支定界法和割平面方法分支定界法和割平面方法3.Lingo/Lindo求解整數(shù)規(guī)劃求解整數(shù)規(guī)劃上頁(yè)下頁(yè)返回例例1。人員安排問(wèn)題。人員安排問(wèn)題整數(shù)規(guī)劃整數(shù)規(guī)劃 某賓館一天各時(shí)段需要的人數(shù)如下所示。按規(guī)定，某賓館一天各時(shí)段需要的人數(shù)如下所示。按規(guī)定，服務(wù)員連續(xù)工作八小時(shí)為一服務(wù)員連續(xù)工作八小時(shí)為一 班。現(xiàn)要求安排服務(wù)員的班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使所需服務(wù)員總數(shù)最少。工作時(shí)間，使所需服務(wù)員總數(shù)最少。上頁(yè)下頁(yè)返回時(shí)段始末時(shí)間所需服務(wù)員人數(shù)16:008:00628:0010

2、:0012310:0012:00 10412:0014:00 8514:0016:00 9616:0018:00 14718:0020:00 8820:0022:00 6922:0024:00 4 某賓館一天各時(shí)段需要的人數(shù)如下所示。按規(guī)定，某賓館一天各時(shí)段需要的人數(shù)如下所示。按規(guī)定，服務(wù)員連續(xù)工作八小時(shí)為一服務(wù)員連續(xù)工作八小時(shí)為一 班?，F(xiàn)要求安排服務(wù)員的班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使所需服務(wù)員總數(shù)最少。工作時(shí)間，使所需服務(wù)員總數(shù)最少。上頁(yè)下頁(yè)返回 解：設(shè)解：設(shè)xj 表示第表示第j時(shí)段開始上班的服務(wù)員人數(shù)。由于時(shí)段開始上班的服務(wù)員人數(shù)。由于每?jī)尚r(shí)為一時(shí)段，所以第每?jī)尚r(shí)為一時(shí)段，所以第j

3、時(shí)段開始上班的服務(wù)員將時(shí)段開始上班的服務(wù)員將在第在第j+3時(shí)段結(jié)束時(shí)下班。因此只考慮時(shí)段結(jié)束時(shí)下班。因此只考慮6,.,3, 2, 1xxxx 相應(yīng)的模型為：相應(yīng)的模型為：61miniixz) 1(61時(shí)段x)2(1221時(shí)段 xx)3(10321時(shí)段xxx時(shí)段始末時(shí)間所需服務(wù)員人數(shù)16:008:00628:0010:0012310:0012:0010412:0014:008514:0016:009616:0018:0014718:0020:008820:0022:006922:0024:004上頁(yè)下頁(yè)返回6,.,1, 0468146656546543ixxxxxxxxxxxi84321xxxx

4、95432xxxx時(shí)段始末時(shí)間所需服務(wù)員人數(shù)16:008:00628:0010:0012310:0012:0010412:0014:008514:0016:009616:0018:0014718:0020:008820:0022:006922:0024:004第第4階段階段5階段階段6階段階段7階段階段7階段階段9階段階段上頁(yè)下頁(yè)返回621.minxxxz6,.,2 , 10468149810126. .665654654354324321321211ixxxxxxxxxxxxxxxxxxxxxxxxxtsi且為整數(shù)，整數(shù)規(guī)劃整數(shù)規(guī)劃上頁(yè)下頁(yè)返回利用數(shù)學(xué)軟件利用數(shù)學(xué)軟件lingo可求得一個(gè)最優(yōu)

5、解為：可求得一個(gè)最優(yōu)解為： X1 = 12.000000 X2 = 0.000000 X3 = 6.000000 X4 = 2.000000 X5 = 1.000000 X6 = 5.000000 最優(yōu)值為最優(yōu)值為 26，具體過(guò)程如下：，具體過(guò)程如下：上頁(yè)下頁(yè)返回求解程序?yàn)榍蠼獬绦驗(yàn)長(zhǎng)iti1aMIN =x1+x2+x3+x4+x5+x6; x16; x1+x212; x1+x2+x310; x1+x2+x3+x48; x2+x3+x4+x59; x3+x4+x5+x614; x4+x5+x68; x5+x66; x64;gin(x1);gin(x2);gin(x3);gin(x4);gin(

6、x5);gin(x6);end6,.,2 , 10468149810126. .665654654354324321321211ixxxxxxxxxxxxxxxxxxxxxxxxxtsi且為整數(shù)，621.minxxxz上頁(yè)下頁(yè)返回OBJECTIVE FUNCTION VALUE (1) 26.00000 VARIABLE VALUE X1 12.000000 X2 0.000000 X3 6.000000 X4 2.000000 X5 1.000000 X6 5.000000 另一最優(yōu)解為另一最優(yōu)解為 OBJECTIVE FUNCTION VALUE 1) 26.00000 VARIABLE

7、VALUE X1 6.000000 X2 6.000000 X3 0.000000 X4 0.000000 X5 3.000000 X6 11.000000最優(yōu)解不唯一最優(yōu)解不唯一liti1b上頁(yè)下頁(yè)返回OBJECTIVE FUNCTION VALUE 1) 26.00000 VARIABLE VALUE REDUCED COST X1 12.000000 1.000000 X2 0.000000 1.000000 X3 6.000000 1.000000 X4 2.000000 1.000000 X5 1.000000 1.000000 X6 5.000000 1.000000 上頁(yè)下頁(yè)返回

8、例2（布線問(wèn)題）解決某市消防站的布線解決某市消防站的布線 問(wèn)題。該城市共有問(wèn)題。該城市共有6個(gè)區(qū)，每個(gè)區(qū)個(gè)區(qū)，每個(gè)區(qū)都可以建立消防站，市政府希望設(shè)置的消防站最少，但都可以建立消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地方發(fā)生火警時(shí)，消防車要在必須滿足在城市任何地方發(fā)生火警時(shí)，消防車要在15分分鐘之內(nèi)趕到現(xiàn)場(chǎng)，根據(jù)實(shí)地考察，各區(qū)之間消防車行駛鐘之內(nèi)趕到現(xiàn)場(chǎng)，根據(jù)實(shí)地考察，各區(qū)之間消防車行駛的時(shí)間見下表的時(shí)間見下表請(qǐng)幫助該市制定一個(gè)最節(jié)省的計(jì)劃。請(qǐng)幫助該市制定一個(gè)最節(jié)省的計(jì)劃。上頁(yè)下頁(yè)返回地區(qū)地區(qū)1 地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū) 5地區(qū)地區(qū)6地區(qū)地區(qū)101016282720

9、地區(qū)地區(qū)210024321710地區(qū)地區(qū)316240122721地區(qū)地區(qū)428321201525地區(qū)地區(qū)527172715014地區(qū)地區(qū)620102125140各區(qū)之間消防車行駛的時(shí)間表各區(qū)之間消防車行駛的時(shí)間表上頁(yè)下頁(yè)返回解：每個(gè)地區(qū)是否設(shè)消防站可用一個(gè)解：每個(gè)地區(qū)是否設(shè)消防站可用一個(gè)0-1變量來(lái)表示。變量來(lái)表示。令令不設(shè)消防站，地區(qū)設(shè)消防站地區(qū)iixi0, 1i=1,2,6本題要求消防站的個(gè)數(shù)最少，故目標(biāo)函數(shù)為：本題要求消防站的個(gè)數(shù)最少，故目標(biāo)函數(shù)為：654321minxxxxxxz約束條件為：約束條件為：上頁(yè)下頁(yè)返回1612 xxx143 xx1534xxx1645xxx1526xxx6

10、,.,110ixi，或 時(shí)間時(shí)間1234 56地區(qū)地區(qū)101016282720地區(qū)地區(qū)210024321710地區(qū)地區(qū)316240122721地區(qū)地區(qū)428321201525地區(qū)地區(qū)527172715014地區(qū)地區(qū)620102125140各區(qū)之間消防車行駛的時(shí)間表各區(qū)之間消防車行駛的時(shí)間表約束條件為：約束條件為：) 1( 121確保地區(qū) xx上頁(yè)下頁(yè)返回 111111.5266455344362121xxxxxxxxxxxxxxxxts6,.,110ixi，或654321minxxxxxxz 時(shí)間時(shí)間1234 56地區(qū)地區(qū)101016282720地區(qū)地區(qū)210024321710地區(qū)地區(qū)3162

11、40122721地區(qū)地區(qū)428321201525地區(qū)地區(qū)527172715014地區(qū)地區(qū)620102125140OBJECTIVE FUNCTION VALUE 1) 2.000000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 1.000000 1.000000 X3 0.000000 1.000000 X4 1.000000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000min =x1+x2+x3+x4+x5+x6;x1+x21;x1+x2+x61;x3+x41;x3+x4+x

12、51;x4+x5+x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);end計(jì)算程序?yàn)橛?jì)算程序?yàn)榍蠼鈭?bào)告為求解報(bào)告為最優(yōu)方案為最優(yōu)方案為x2=x4=1,即在第即在第2區(qū)和第區(qū)和第4區(qū)設(shè)置消防站即可。區(qū)設(shè)置消防站即可。liti3bin(x)-表示表示x取值為取值為0或或1上頁(yè)下頁(yè)返回例3（最優(yōu)裝載問(wèn)題）例例3（美國(guó)（美國(guó) 1988 年大學(xué)生建摸競(jìng)賽年大學(xué)生建摸競(jìng)賽B題題) 要把七種規(guī)格的包裝箱裝到兩輛平板車上去，箱子的要把七種規(guī)格的包裝箱裝到兩輛平板車上去，箱子的寬、高、相同，而厚度和重量不同。下表給出了他們的厚寬、高、相同

13、，而厚度和重量不同。下表給出了他們的厚度和重量及數(shù)量。度和重量及數(shù)量。第i種箱子1234567 厚度t（厘米）48.752.061.372.048.752.064.0 重量w（千克）200030001000 5004000 2000 1000數(shù)量n8796648上頁(yè)下頁(yè)返回每輛平板車有每輛平板車有10.2米的地方用于裝箱，載重米的地方用于裝箱，載重40噸。由噸。由于貨物的限制，對(duì)于第于貨物的限制，對(duì)于第5、6、7三種包裝箱的裝載有三種包裝箱的裝載有如下約束：它們所占的空間（厚度）不得超過(guò)如下約束：它們所占的空間（厚度）不得超過(guò)302.7厘米，試把這些包裝箱裝到平板車上去，使浪費(fèi)的厘米，試把這些

14、包裝箱裝到平板車上去，使浪費(fèi)的空間最小?？臻g最小。 解：容易計(jì)算出所有的包裝箱的厚度為解：容易計(jì)算出所有的包裝箱的厚度為27.495米，而米，而兩倆平板車共有兩倆平板車共有20.4米長(zhǎng)的地方，所以不可能都裝上。米長(zhǎng)的地方，所以不可能都裝上。 記表中所給出的第記表中所給出的第i種箱子的厚度、重量和數(shù)量分別為種箱子的厚度、重量和數(shù)量分別為ti 、 wi 和和 ni （i=1,2,.,7),又記第又記第i種箱子裝到第種箱子裝到第1、2輛平板輛平板車上的數(shù)量分別為車上的數(shù)量分別為 xi1 ,xi2（i=1,2,.,7)上頁(yè)下頁(yè)返回第i種箱子1234567 厚度ti（厘米）48.752.061.3 72

15、.0 48.7 52.0 64.0 重量wi(噸）2310.5421數(shù)量ni8796648上頁(yè)下頁(yè)返回 問(wèn)題要求浪費(fèi)的空問(wèn)題要求浪費(fèi)的空間最小，即裝載所間最小，即裝載所占的空間最大，故占的空間最大，故目標(biāo)函數(shù)為：目標(biāo)函數(shù)為： 7121maxijijixtz約束條件為：約束條件為：厚度約束：厚度約束：2 , 1,102071jxtiiji重量約束：重量約束：712 , 1,40iijijxw第i種箱子1234567厚度ticm48.752.061.372.048.752.064.0 重量wi(t）2310.5421數(shù)量ni8796648每輛平板車有每輛平板車有10.2米的地方用于米的地方用于裝箱

16、，載重裝箱，載重40噸噸記第記第i種箱子裝到第種箱子裝到第1、2輛平板車上的輛平板車上的數(shù)量分別為數(shù)量分別為 （i=1,2,.,7)21,iixx上頁(yè) 下頁(yè) 返回?cái)?shù)量約束：數(shù)量約束：217,.,2 , 1,jiijinx特殊約束：特殊約束：7521, 7 .302)(iiiixxt2 , 1, 7 .30275jxtiiji或或第i種箱子1234567厚度ticm48.752.061.372.048.752.064.0 重量wi(t）2310.5421數(shù)量ni8796648第第5、6、7三種包裝箱的裝載有三種包裝箱的裝載有如下約束：它們所占的空間如下約束：它們所占的空間（厚度）不得超過(guò)（厚度）

17、不得超過(guò)302.7厘米，厘米，(每輛平板車不每輛平板車不超過(guò)超過(guò)302.7cm)上頁(yè)下頁(yè)返回 7121maxijijixtz71752121712, 1,10207 .302)(7,.,2, 1,2, 1,40.iijiiiiijiijiijijxtxxtinxjxwts為為整整數(shù)數(shù), 2 , 1, 7,.,1i , 0 jxij故得到兩個(gè)整數(shù)規(guī)劃模型為：故得到兩個(gè)整數(shù)規(guī)劃模型為：(IP1)(IP2) 7121maxijijixtz 717521712, 1,10202, 1,7 .3027,.,2, 1,2, 1,40.iijijijijiijiijijxtjxtjnxjxwts為為整整數(shù)數(shù)

18、, 2 , 1, 7,.,1i , 0 jxij上頁(yè)下頁(yè)返回現(xiàn)解第一個(gè)問(wèn)題：現(xiàn)解第一個(gè)問(wèn)題：(IP1) 7121maxijijixtz 71752121712, 1,10207 .302)(7,.,2, 1,2, 1,40.iijijiiijiijiijijxtxxtjnxjxwts為為整整數(shù)數(shù), 2 , 1, 7,.,1i , 0 jxijLiti3.ltxLiti3.txt上頁(yè)下頁(yè)返回利用利用lindo 求解得到最優(yōu)解為：求解得到最優(yōu)解為：平板 車 1平 板 車 2箱子類型c1c2c3c4c5c6c7c1c2c3c4c5c6c7最優(yōu)值解10 5 6 0 0 0 08 2 7 0 2 0 0

19、 2039.4解28 5 6 0 0 0 00 2 3 6 3 3 0 2039.4解30 6 9 0 0 3 08 1 0 6 3 0 0 2039.4解45 1 9 1 2 0 03 6 0 5 1 3 0 2039.4上頁(yè)下頁(yè)返回MAX 48.7x11+48.7x12+52.0 x21+52.0 x22+61.3x31+61.3x32+72.0 x41+72.0 x42+48.7x51+48.7x52 +52.0 x61+52.0 x62+64x71+64x72st 48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x711020 48.7x12+5

20、2x22+61.3x32+72x42+48.7x52+52x62+64x721024 2x11+3x21+x31+0.5x41+4x51+2x61+x7140 2x12+3x22+x32+0.5x42+4x52+2x62+x7240 x11+x128 x21+x227 x31+x329x11+x128 x21+x227 x31+x329 x41+x426 x51+x526 x61+x624 x71+x728 48.7x51+48.7x52+52.0 x61+52.0 x62+64.0 x71+64.0 x72302.7 END GIN 14 上頁(yè)下頁(yè)返回 objective function

21、value 1) 2039.400variable value reduced cost x11 5.000000 -48.700001 x12 3.000000 -48.700001 x21 1.000000 -52.000000 x22 6.000000 -52.000000 x31 9.000000 -61.299999 x32 0.000000 -61.299999 上頁(yè)下頁(yè)返回 X41 1.000000 -72.000000 X42 5.000000 -72.000000 X51 2.000000 -48.700001 X52 1.000000 -48.700001 X61 0.00

22、0000 -52.000000 X62 3.000000 -52.000000 X71 0.000000 -64.000000 X72 0.000000 -64.000000MAX= 48.7*x11+48.7*x12+52.0*x21+52.0*x22+61.3*x31+61.3*x32+72.0*x41+72.0*x42+48.7*x51+48.7*x52+52.0*x61+52.0*x62+64*x71+64*x72;48.7*x11+52*x21+61.3*x31+72*x41+48.7*x51+52*x61+64*x711020;48.7*x12+52*x22+61.3*x32+72

23、*x42+48.7*x52+52*x62+64*x721024;2*x11+3*x21+x31+0.5*x41+4*x51+2*x61+x7140;2*x12+3*x22+x32+0.5*x42+4*x52+2*x62+x7240; x11+x128; x21+x227; x31+x329; x41+x426; x51+x526; x61+x624; x71+x728; 48.7*x51+48.7*x52+52.0*x61+52.0*x62+64.0*x71+64.0*x72302.7;gin(x11);gin(x12);gin(x21);gin(x22);gin(x31);gin(x32);

24、gin(x41);gin(x42);gin(x51);gin(x52);gin(x61);gin(x62);gin(x71);gin(x72); END model:!平板車裝載問(wèn)題平板車裝載問(wèn)題;sets: box/1.7/:t,w,n; car/1,2/; links(box,car):x;endsets!目標(biāo)函數(shù)目標(biāo)函數(shù); max=sum(links(i,j): t(i)*x(i,j);!厚度約束厚度約束; for(car(j): sum(box(i): t(i)*x(i,j)=1020;);!重量約束重量約束; for(car(j): sum(box(i): w(i)*x(i,j)=4

25、0;);!數(shù)量約束數(shù)量約束; for(box(i):x(i,1)+x(i,2)=n(i););!特殊約束特殊約束; sum(box(i)|i#ge# 5:t(i)*x(i,1)+t(i)*x(i,2)2x3+x5+x6+x8+x93x4+x6+x7+x922x3-x1-x20 x4-x702x5-x1-x20 x6-x70 x8-x502x9-x1-x26/5分支得兩個(gè)線性分支得兩個(gè)線性規(guī)劃：規(guī)劃：上頁(yè)下頁(yè)返回2 , 1, 0183210434min) 1(2212121ixxxxxxxxfPi2 , 1, 0283210434min)2(2212121ixxxxxxxxfPi和和解（解（P1

26、)得最優(yōu)解為得最優(yōu)解為12),1 ,(),(1491211fxx再將（再將（P1)利用利用 x1 9/4和和x1 9/4進(jìn)行進(jìn)行分支得：分支得：上頁(yè)下頁(yè)返回2134minxxf183210422121xxxxx2 , 1, 021ixxi（s.t.)(P3)2134minxxf183210422121xxxxx2 , 1, 031ixxi(S.t.)(P4)上頁(yè)下頁(yè)返回解（解（P3)得最優(yōu)解為得最優(yōu)解為11),1 , 2(),(33231fxx而而(P4)無(wú)可行解。無(wú)可行解。再回頭解一下（再回頭解一下（P2),得最優(yōu)解為得最優(yōu)解為10),2 , 1 (),(22221fxx比較得最優(yōu)解為比較得

27、最優(yōu)解為11),1 , 2(),(*2*1fxx 割平面法的基本思想：割平面法的基本思想： 若整數(shù)規(guī)劃若整數(shù)規(guī)劃IP的松弛規(guī)劃的松弛規(guī)劃P0的最優(yōu)解不是整數(shù)解，的最優(yōu)解不是整數(shù)解，對(duì)對(duì)P0增加一個(gè)約束條件，得線性規(guī)劃增加一個(gè)約束條件，得線性規(guī)劃P1，此過(guò)程縮小，此過(guò)程縮小了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的同時(shí)，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃同時(shí)，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃IP的解均在的解均在P1中，若中，若P1的最優(yōu)解為整數(shù)解，則得的最優(yōu)解為整數(shù)解，則得IP的最的最優(yōu)解。若優(yōu)解。若P1的最優(yōu)解不是整數(shù)解，重復(fù)以上步驟

28、，由的最優(yōu)解不是整數(shù)解，重復(fù)以上步驟，由于可行解域在不斷縮小，且保留于可行解域在不斷縮小，且保留IP所有的整數(shù)解，總所有的整數(shù)解，總可以在有限次后得到可以在有限次后得到IP的最優(yōu)解的最優(yōu)解.為整數(shù)：對(duì)整數(shù)規(guī)劃問(wèn)題jxXbAXtsCXzIP0.min割平面法 由松弛問(wèn)題的可行域向整數(shù)規(guī)劃的可行域逼近 方法利用超平面切除 要求整數(shù)解保留 松弛問(wèn)題最優(yōu)值向最優(yōu)解逼近 目標(biāo)得到的新的可行域的某個(gè)整數(shù)坐標(biāo)的極點(diǎn)恰好是問(wèn)題的最優(yōu)解為整數(shù)：對(duì)整數(shù)規(guī)劃問(wèn)題jxXbAXtsCXzIP0.max0.minXbAXtsCXz其松弛問(wèn)題0.min:1XbAXtsCXzP線性規(guī)劃0jRjijixff4715.2 割平面

29、解法v例例1 1 求解 目標(biāo)函數(shù) min z=-x1-x2 約束條件： -x1+x21 3x1+x24 (15-1) x1，x20 x1，x2 整數(shù) 48v先不考慮整數(shù)約束，求得相應(yīng)的線性規(guī)劃的最優(yōu)解為： x1=34，x2=74，min z=-104 最優(yōu)解是下圖中域R的極點(diǎn)A，但不符合整數(shù)約束條件。min z=-x1-x2 約束條件： -x1+x21 3x1+x24 (15-1) x1，x20 4915.2節(jié) 割平面解法v現(xiàn)設(shè)想，如能找到像CD那樣的直線去切割域R(圖5-6)，去掉三角形域ACD，那么具有整數(shù)坐標(biāo)的C點(diǎn)(1，1)就是域R的一個(gè)極點(diǎn)。 如在域R上求解，而得到的最優(yōu)解又恰巧在C點(diǎn)

30、就得到原問(wèn)題的整數(shù)解，所以解法的關(guān)鍵是怎樣構(gòu)造一個(gè)這樣的“割平面”CD，盡管它可能不是唯一的，也可能不是一步能求到的。圖5-6x1 xixmxm+1xm+jxn解x11 00y1m+1y1m+jy1nb1xi0 10yim+1yim+jyinbixm0 01ymm+1ymm+jymnbm0為整數(shù)：對(duì)整數(shù)規(guī)劃問(wèn)題jxXbAXtsCXzIP0.min0.min0XbAXtsCXzL其松弛問(wèn)題0, 0 ,100mibbbXL 的最優(yōu)解是分?jǐn)?shù)其中0ibL0的最優(yōu)單純形表：的最優(yōu)單純形表：對(duì)應(yīng)于生成行對(duì)應(yīng)于生成行i的方程的方程0.min:1XbAXtsCXzL線性規(guī)劃0jRjijixffjijijibx

31、yx)45(v(15-2.3) 將bi和yik都分解成整數(shù)部分N與非負(fù)真分?jǐn)?shù)f之和，即jijijibxyx3 . 215(10 ,iiiiffbb而a表示不超過(guò)a的最大整數(shù)。例如： 若b=2.35，則b=2，f=0.35 若b= 0.45，則b= 1,f=0.55 代入(15-2.3)式得10 ,ijijijijffyyjjjijiijikixffbxyx)4 . 2 .15(jjjijiijikixffbxyx)4 . 2 .15(10if10ijfnixi,.,2 , 10 均為整數(shù)，且0jjijixff將上述約束加到將上述約束加到原約束中去，得原約束中去，得到等價(jià)的整數(shù)規(guī)到等價(jià)的整數(shù)規(guī)劃劃為整數(shù)jRjjijixXxffbAXtsCXzIP00.min:1用割平面