運(yùn)籌學(xué)——整數(shù)規(guī)劃PPT課件

1、 對(duì)于對(duì)于0 01 1 規(guī)劃問(wèn)題，由于每個(gè)變量只取規(guī)劃問(wèn)題，由于每個(gè)變量只取0 0，1 1兩個(gè)值，一般會(huì)用窮舉法來(lái)解，即將所有的兩個(gè)值，一般會(huì)用窮舉法來(lái)解，即將所有的0 0，1 1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過(guò)加入一定的條隱枚舉法就是在此基礎(chǔ)上，通過(guò)加入一定的條件，就能較快的求得最優(yōu)解。件，就能較快的求得最優(yōu)解。第1頁(yè)/共23頁(yè)第2頁(yè)/共23頁(yè)第3頁(yè)/共23頁(yè)第4頁(yè)/共23頁(yè)第5頁(yè)/共23頁(yè)第6頁(yè)/共23頁(yè)第7頁(yè)/共23頁(yè)第8頁(yè)/共23頁(yè)第

2、9頁(yè)/共23頁(yè)第10頁(yè)/共23頁(yè)第11頁(yè)/共23頁(yè)第12頁(yè)/共23頁(yè)第13頁(yè)/共23頁(yè) 例例3、求解下列、求解下列01 規(guī)劃問(wèn)題規(guī)劃問(wèn)題4 . 3 . 2 . 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：由于目標(biāo)函數(shù)中變量解：由于目標(biāo)函數(shù)中變量x1, x2 , x4 的系數(shù)均為負(fù)數(shù)，的系數(shù)均為負(fù)數(shù)，可作如下變換：可作如下變換： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4帶入原題帶入原題中，但需重新調(diào)整變量編號(hào)。令中，但需重新調(diào)整變量編號(hào)。令 x3 = x1, x4 = x2得到下

3、式。得到下式。第14頁(yè)/共23頁(yè) 1 0,435 2 461 2 1173max4321432432143214321或或xxxxxxxxxxxxxxxxxxxZ 可以從可以從( )開(kāi)始試算，開(kāi)始試算， x(3)( 1.1.0.1 )最優(yōu)解。最優(yōu)解。 x(3)( 1.0.1.0 )是原問(wèn)題的最優(yōu)解，是原問(wèn)題的最優(yōu)解，Z* =2第15頁(yè)/共23頁(yè)例例4、求解下列、求解下列01 規(guī)劃問(wèn)題規(guī)劃問(wèn)題 )5 . 4 . 3 . 2 . 1( 1054 24423 248510min543215432154321jxxxxxxxxxxxxxxxxZj或或令令 y1=x5, y2=x4, y3=x2, y4

4、=x3, y5=x1 得到下式得到下式 )5 . 4 . 3 . 2 . 1( 10(2) 524(1) 4342 108542min543215432154321jyyyyyyyyyyyyyyyyZj或或第16頁(yè)/共23頁(yè)y1 . y2. y3 . y4. y5約束條件約束條件滿足條件滿足條件Z 值值 (1) (2)是是 否否( 0. 0. 0. 0. 0 ) 0 0( 1. 0. 0. 0. 0 ) 1 -1( 0. 1. 0. 0. 0 ) -1 1 ( 0. 0. 1. 0. 0 ) -2 1( 0. 0. 0. 1. 0 ) 4 -48( 0. 0. 0. 0. 1 ) 3 -2 所以，所以， Y*= （），原問(wèn)題的最優(yōu)解為：（），原問(wèn)題的最優(yōu)解為： X* （），（），Z* =8第17頁(yè)/共23頁(yè)練習(xí)：用隱枚舉法求解練習(xí)：用隱枚舉法求解0101規(guī)劃問(wèn)題規(guī)劃問(wèn)題 )5 , 2 , 1( 1 01 2 02236224 53 31075min5432543215432154321jxxxxxxxxxxxxxxxxxxxxZj或或第18頁(yè)/共