《整數(shù)規(guī)劃.ppt》由會員分享，可在線閱讀，更多相關《整數(shù)規(guī)劃.ppt（41頁珍藏版）》請在匯文網(wǎng)上搜索。

1、整數(shù)規(guī)劃的模型整數(shù)規(guī)劃的模型分支定界法分支定界法0 01 1 整數(shù)規(guī)劃整數(shù)規(guī)劃指派問題指派問題整數(shù)規(guī)劃例例1 1：合理下料問題：合理下料問題設用某型號的圓鋼下零件設用某型號的圓鋼下零件A A1 1,A A2 2,A,Am m 的毛坯。在一根的毛坯。在一根圓鋼上下料的方式有圓鋼上下料的方式有B B1 1,B,B2 2,B,Bn n 種，每種下料方式可以得種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。怎到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件 方 個數(shù)

2、式零件零 件毛坯數(shù)整數(shù)規(guī)劃的模型 設：設：xj 表示用表示用Bj(j=1.2n)種方式下料根數(shù)種方式下料根數(shù) 模型：模型：整數(shù)規(guī)劃的模型例例2、某廠擬用集裝箱托運甲、乙兩種貨、某廠擬用集裝箱托運甲、乙兩種貨物，每箱的體積，重量，可獲利潤以及物，每箱的體積，重量，可獲利潤以及托運所受限制如下表：托運所受限制如下表：貨物貨物 體積（體積（m3/箱）箱）重量（重量（100斤斤/箱）箱）利潤（百元利潤（百元/箱）箱）甲甲 5 2 20 乙乙 4 5 10托運限制托運限制 24 13 max z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x1,x2為整數(shù)為整數(shù)解：先不考慮整

3、數(shù)條件，解上述問題的松弛問題，先不考慮整數(shù)條件，解上述問題的松弛問題，得最優(yōu)解得最優(yōu)解:x1=4.8,x2=0,max z=96 8-7-6-5-4-3-2-1-1 2 3 4 5 6 7 8 9 10BXX1AC z=20 x1+10 x20整數(shù)規(guī)劃一般形式整數(shù)規(guī)劃一般形式依依照照決決策策變變量量取取整整要要求求的的不不同同，整整數(shù)數(shù)規(guī)規(guī)劃劃可可分分為為純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、01整數(shù)規(guī)劃。整數(shù)規(guī)劃。整數(shù)規(guī)劃的數(shù)學模型部分或者全部為整數(shù)部分或者全部為整數(shù)純純整整數(shù)數(shù)規(guī)規(guī)劃劃：所所有有決決策策變變量量要要求求取取非非負負整整數(shù)數(shù)（這這時時引引進進的的松松弛弛變變量量

4、和和剩剩余余變變量量可以不要求取整數(shù)）?？梢圆灰笕≌麛?shù)）。混混合合整整數(shù)數(shù)規(guī)規(guī)劃劃：只只有有一一部部分分的的決決策策變變量量要要求求取取非非負負整整數(shù)數(shù)，另另一一部部分分可可以以取取非非負負實數(shù)。實數(shù)。01整整數(shù)數(shù)規(guī)規(guī)劃劃：所所有有決決策策變變量量只只能能取取 0 或或 1 兩個整數(shù)。兩個整數(shù)。整數(shù)規(guī)劃的數(shù)學模型從從數(shù)數(shù)學學模模型型上上看看整整數(shù)數(shù)規(guī)規(guī)劃劃似似乎乎是是線線性性規(guī)規(guī)劃劃的的一一種種特特殊殊形形式式，求求解解只只需需在在線線性性規(guī)規(guī)劃劃的的基基礎礎上上，通通過過舍舍入入取取整整，尋尋求求滿滿足足整整數(shù)數(shù)要要求求的的解解即即可可。但但實實際際上上兩兩者者卻卻有有很很大大的的不不同同

5、，通通過過舍舍入入得得到到的的解解（整整數(shù)數(shù)）也也不不一一定定就就是是最最優(yōu)優(yōu)解解，有有時時甚至不能保證所得倒的解是整數(shù)可行解。甚至不能保證所得倒的解是整數(shù)可行解。整數(shù)規(guī)劃與線性規(guī)劃的關系例：設整數(shù)規(guī)劃問題如下例：設整數(shù)規(guī)劃問題如下 首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。稱為松弛問題）。整數(shù)規(guī)劃與線性規(guī)劃的關系且為整數(shù) 用圖解法求出最優(yōu)解用圖解法求出最優(yōu)解x x1 13/2,3/2,x x2 2=10/3=10/3且有且有Z=29/6Z=29/6x1x233(3/2,10/3)現(xiàn)現(xiàn)求求整整數(shù)數(shù)解解（最最優(yōu)優(yōu)解解）：如如用用“舍舍入入

6、取取整整法法”可可得得到到4個個點點即即(1，3),(2，3),(1，4),(2，4)。顯顯然然，它它們們都都不不可可能能是是整整數(shù)數(shù)規(guī)規(guī)劃劃的的最最優(yōu)解。優(yōu)解。按按整整數(shù)數(shù)規(guī)規(guī)劃劃約約束束條條件件，其其可可行行解解肯肯定定在在線線性性規(guī)規(guī)劃劃問問題題的的可可行行域域內(nèi)內(nèi)且且為為整整數(shù)數(shù)點點。故故整整數(shù)數(shù)規(guī)規(guī)劃劃問問題題的的可可行行解解集集是是一一個個有有限限集集，如圖所示。如圖所示。整數(shù)規(guī)劃與線性規(guī)劃的關系因因此此，可可將將集集合合內(nèi)內(nèi)的的整整數(shù)數(shù)點點一一一一找找出出，其其最最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如如上上例例：其其中中（2 2，

7、2 2）（3 3，1 1）點點為為最最大大值值，Z=4Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃的方法有：分支定界法和割平面法；分支定界法和割平面法；對對于于特特別別的的0 01 1規(guī)規(guī)劃劃問問題題采采用用隱隱枚枚舉舉法法和和匈匈牙利法。牙利法。整數(shù)規(guī)劃與線性規(guī)劃的關系考慮純整數(shù)問題：考慮純整數(shù)問題：整數(shù)問題的松弛問題：整數(shù)問題的松弛問題：分枝定界法1、先先不不考考慮慮整整數(shù)數(shù)約約束束，解解(IP)的的松松弛弛問問題題(LP)，可可能得到以下情況之一：能得到以下情況之一：.若若(LP)沒沒有有可可行行解解，則則(IP)也也沒沒有有可可行行解解，停停止計算。止計算。.若若

8、(LP)有有最最優(yōu)優(yōu)解解，并并符符合合(IP)的的整整數(shù)數(shù)條條件件，則則(LP)的最優(yōu)解即為的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。的最優(yōu)解，停止計算。.若若(LP)有有最最優(yōu)優(yōu)解解，但但不不符符合合(IP)的的整整數(shù)數(shù)條條件件，轉(zhuǎn)入下一步。為討論方便，設轉(zhuǎn)入下一步。為討論方便，設(LP)的最優(yōu)解為：的最優(yōu)解為：分枝定界法 2、定界：、定界：記記(IP)的的目目標標函函數(shù)數(shù)最最優(yōu)優(yōu)值值為為Z*,以以Z(0)作作為為Z*的的上上界界，記記為為 Z(0)。再再用用觀觀察察法法找找的的一一個個整整數(shù)數(shù)可可行行解解 X，并并以以其其相相應應的的目目標標函函數(shù)數(shù)值值 Z作作為為Z*的的下下界界，記記為為

9、Z Z，也可以令，也可以令Z，則有，則有:Z Z*3、分枝：、分枝：在在(LP)的的最最優(yōu)優(yōu)解解 X(0)中中，任任選選一一個個不不符符合合整整數(shù)數(shù)條條件件的的變變量量，例例如如xr=br（不不為為整整數(shù)數(shù)），以以br 表表示示不不超過超過br 的最大整數(shù)。構(gòu)造兩個約束條件的最大整數(shù)。構(gòu)造兩個約束條件 xr br 和和xr br 1分枝定界法 將將這這兩兩個個約約束束條條件件分分別別加加入入問問題題(IP)，形形成成兩兩個個子子問問題題(IP1)和和(IP2)，再再解解這這兩兩個個問問題題的的松松弛弛問問題題(LP1)和和(LP2)。4、修改上、下界：按照以下兩點規(guī)則進行。、修改上、下界：按照

10、以下兩點規(guī)則進行。.在在各各分分枝枝問問題題中中，找找出出目目標標函函數(shù)數(shù)值值最最大大者者作作為為新的上界；新的上界；.從從已已符符合合整整數(shù)數(shù)條條件件的的分分枝枝中中，找找出出目目標標函函數(shù)數(shù)值值最大者作為新的下界。最大者作為新的下界。5、比較與剪枝、比較與剪枝：各各分分枝枝的的目目標標函函數(shù)數(shù)值值中中，若若有有小小于于Z 者者，則則剪剪掉掉此此枝枝，表表明明此此子子問問題題已已經(jīng)經(jīng)探探清清，不不必必再再分分枝枝了了;否否則則繼繼續(xù)續(xù)分枝。分枝。如此反復進行，直到得到如此反復進行，直到得到ZZ*為止，即得最優(yōu)解為止，即得最優(yōu)解 X*。分枝定界法例一：用分枝定界法求解整數(shù)規(guī)劃問題例一：用分枝定

11、界法求解整數(shù)規(guī)劃問題記為（記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（記為（LP）分枝定界法用圖解法求（用圖解法求（LP）的最）的最優(yōu)解，如圖所示。優(yōu)解，如圖所示。x1x233(18/11,40/11)對于對于x118/111.64，取值取值x1 1，x1 2對于對于x2=40/11 3.64，取值取值x2 3，x2 4先將（先將（LP）劃分為（）劃分為（LP1）和（）和（LP2）,取取x1 1,x1 2 x118/11,x2=40/11 Z(0)=218/11(19.8)即即Z 是（是（IP）最小值的下限。）最小值的下限。分枝定界法有

12、下式：有下式：現(xiàn)在只要求出（現(xiàn)在只要求出（LP1）和（）和（LP2）的最優(yōu)解即可。）的最優(yōu)解即可。分枝定界法x1x233(18/11,40/11)先求（先求（LP1）,如圖所示。如圖所示。此時此時B 在點取得最優(yōu)解。在點取得最優(yōu)解。x11,x2=3,Z(1)16找到整數(shù)解，問題已探明，找到整數(shù)解，問題已探明，此枝停止計算。此枝停止計算。11同理求（同理求（LP2）,如圖所示。如圖所示。在在C 點取得最優(yōu)解。點取得最優(yōu)解。即即x12,x2=10/3,Z(2)56/318.7 Z2 Z116 原問題有比（原問題有比（16）更小的最優(yōu)解，但更小的最優(yōu)解，但 x2 不是整數(shù)，利用不是整數(shù)，利用 3 1

13、0/34 加入條件。加入條件。BAC分枝定界法加入條件：加入條件：x23,x24 有下式：有下式：只要求出（只要求出（LP3）和（）和（LP4）的最優(yōu)解即可。）的最優(yōu)解即可。分枝定界法x1x233(18/11,40/11)11BAC先求（先求（LP3）,如圖所示。此如圖所示。此時時D 在點取得最優(yōu)解。在點取得最優(yōu)解。即即 x112/52.4,x2=3,Z(3)-87/5-17.4 Z(5)F如如對對 Z(6)繼繼續(xù)續(xù)分分解解，其其最最小小值值也也不不會會低低于于15.5，問題探明問題探明,剪枝。剪枝。分枝定界法 至至此此，原原問問題題（IP）的的最最優(yōu)優(yōu)解解為：為：x1=2，x2=3,Z*=Z

14、(5)17以以上上的的求求解解過過程程可可以以用用一一個個樹樹形形圖表示如右：圖表示如右：LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4無可無可行解行解LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11x12x23x24x12x13分枝定界法 01 整整數(shù)數(shù)規(guī)規(guī)劃劃是是一一種種特特殊殊形形式式的的整整數(shù)數(shù)規(guī)規(guī)劃劃，這這時時的的決決策策變變量量xi 只只取取兩兩個個值值0或或1，一一般般的的解解法法為為隱枚舉法。隱枚舉法

15、。例一、求解下列例一、求解下列01 規(guī)劃問題規(guī)劃問題01 整數(shù)規(guī)劃 解解：對對于于0 01 1 規(guī)規(guī)劃劃問問題題，由由于于每每個個變變量量只只取取0 0，1 1兩兩個個值值，一一般般會會用用窮窮舉舉法法來來解解，即即將將所所有有的的0 0，1 1 組組合合找找出出，使使目目標標函函數(shù)數(shù)達達到到極極值值要要求求就就可可求求得得最最優(yōu)優(yōu)解解。但但此此法法太太繁繁瑣瑣，工工作作量量相相當當大大。而而隱隱枚枚舉舉法法就就是是在在此此基基礎上，通過加入一定的條件，就能較快的求得最優(yōu)解。礎上，通過加入一定的條件，就能較快的求得最優(yōu)解。x1.x2.x3約束條件約束條件滿足條件滿足條件Z 值值 (1)(2)(

16、3)(4)是是 否否(0.0.0 )0 0 0 00(0.0.1)1 1 0 15(0.1.0)2 4 1 42(1.0.0)1 1 1 03(0.1.1)1 5(1.0.1)0 2 1 18(1.1.0)3(1.1.1)2 601 整數(shù)規(guī)劃由上表可知，問題的最優(yōu)解為由上表可知，問題的最優(yōu)解為 X*=(x1=1 x2=0 x3=1)由由上上表表可可知知：x1=0 x2=0 x3=1 是是一一個個可可行行解解，為為盡盡快快找找到到最最優(yōu)優(yōu)解解，可可將將3 x12 x25 x3 5 作作為為一一個個約約束束，凡凡是是目目標標函函數(shù)數(shù)值值小小于于5 的的組組合合不不必必討論，如下表。討論，如下表。x

17、1.x2.x3約束條件約束條件滿足條件滿足條件Z 值值(0)(1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 0 00(0.0.1)5 1 1 0 15(0.1.0)-2(0.1.1)3(1.0.0)3(1.0.1)8 0 2 1 18(1.1.0)1(1.1.1)401 整數(shù)規(guī)劃 指派問題的數(shù)學模型指派問題的數(shù)學模型設設n 個個人人被被分分配配去去做做n 件件工工作作，已已知知第第i 個個人人去去做做第第j 件件工工作作的的的的效效率率為為Cij(i=1.2n;j=1.2n)并并假假設設Cij 0。問問應應如如何分配才能使總效率（何分配才能使總效率（時間或費用）最高？時間或費用）

18、最高？指派問題設決策變量設決策變量 1 分配第分配第i 個人去做第個人去做第j 件工作件工作 xij=0 相反相反 (I,j=1.2.n)解題步驟：解題步驟：第第一一步步：變變換換指指派派問問題題的的系系數(shù)數(shù)矩矩陣陣（cij）為為(bij)，使使在在(bij)的各行各列中都出現(xiàn)的各行各列中都出現(xiàn)0元素，即元素，即(1)從（從（cij）的每行元素都減去該行的最小元素；）的每行元素都減去該行的最小元素；(2)再再從從所所得得新新系系數(shù)數(shù)矩矩陣陣的的每每列列元元素素中中減減去去該該列列的的最小元素。最小元素。第二步：進行試指派，以尋求最優(yōu)解。第二步：進行試指派，以尋求最優(yōu)解。在在(bij)中中找找盡

19、盡可可能能多多的的獨獨立立0元元素素，若若能能找找出出n個個獨獨立立0元元素素，就就以以這這n個個獨獨立立0元元素素對對應應解解矩矩陣陣(xij)中中的的元元素素為為1，其其余余為為0，這這就就得得到到最最優(yōu)優(yōu)解解。找找獨獨立立0元元素素，常用的步驟為：常用的步驟為：指派問題(1)從從只只有有一一個個0元元素素的的行行(列列)開開始始，給給這這個個0元元素素加加圈圈，記記作作。然然后后劃劃去去 所所在在列列(行行)的的其其它它0元元素素，記記作作；這這表表示示這這列列所所代代表表的的任任務已指派完，不必再考慮別人了。務已指派完，不必再考慮別人了。(2)給給只只有有一一個個0元元素素的的列列(行

20、行)中中的的0元元素素加加圈圈，記記作作；然然后后劃劃去去 所在行的所在行的0元素，記作元素，記作 (3)反反復復進進行行(1)，(2)兩兩步步，直直到到盡盡可可能能多多的的0元元素素都都被被圈圈出出和和劃劃掉掉為止。為止。(4)若若仍仍有有沒沒有有劃劃圈圈的的0元元素素，且且同同行行(列列)的的0元元素素至至少少有有兩兩個個，則則從從剩剩有有0元元素素最最少少的的行行(列列)開開始始，比比較較這這行行各各0元元素素所所在在列列中中0元元素素的的數(shù)數(shù)目目，選選擇擇0元元素素少少的的那那列列的的這這個個0元元素素加加圈圈(表表示示選選擇擇性性多多的的要要“禮禮讓讓”選選擇擇性性少少的的)。然然后

21、后劃劃掉掉同同行行同同列列的的其其它它0元元素素?？煽煞捶磸蛷瓦M進行行，直直到到所所有有0元元素素都已圈出和劃掉為止。都已圈出和劃掉為止。（5）若）若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n，那么這指派問題的最，那么這指派問題的最優(yōu)解已得到。若優(yōu)解已得到。若m n,則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。指派問題第三步：作最少的直線覆蓋所有第三步：作最少的直線覆蓋所有0元素。元素。(1)對沒有對沒有的行打的行打號；號；(2)對已打?qū)σ汛蛱柕男兄兴泻柕男兄兴泻氐牧写蛟氐牧写蛱?；號?3)再對打有再對打有號的列中含號的列中含 元素的行打元素的行打號；號；(4)重復重復(2)，(3)

22、直到得不出新的打直到得不出新的打號的行、列為止；號的行、列為止；(5)對對沒沒有有打打號號的的行行畫畫橫橫線線，有有打打號號的的列列畫畫縱縱線線，這這就就得得到到覆覆蓋蓋所所有有0元元素素的的最最少少直直線線數(shù)數(shù) l。l 應應等等于于m，若若不不相相等等，說說明明試試指指派派過過程程有有誤誤，回回到到第第二二步步(4)，另另行行試試指指派派；若若 lm n，須須再再變變換換當當前前的的系系數(shù)數(shù)矩矩陣陣，以以找找到到n個獨立的個獨立的0元素，為此轉(zhuǎn)第四步。元素，為此轉(zhuǎn)第四步。指派問題第四步：變換矩陣第四步：變換矩陣(b bijij)以增加以增加0 0元素。元素。在在沒沒有有被被直直線線覆覆蓋蓋的

23、的所所有有元元素素中中找找出出最最小小元元素素，然然后后打打各各行行都都減減去去這這最最小小元元素素；打打各各列列都都加加上上這這最最小小元元素素（以以保保證證系系數(shù)數(shù)矩矩陣陣中中不不出出現(xiàn)現(xiàn)負負元元素素）。新新系系數(shù)數(shù)矩矩陣陣的的最最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。任務任務人員人員ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119指派問題2497指派問題42指派問題 指派問題有有一一份份中中文文說說明明書書，需需譯譯成成英英、日日、德德、俄俄四四種種文文字字，分分別別記記作作A A、B B、C C、D D?，F(xiàn)現(xiàn)有有甲甲、乙乙、丙丙、丁丁

24、四四人人，他他們們將將中中文文說說明明書書譯譯成成不不同同語語種種的的說說明明書書所所需需時時間間如如下下表表所所示，問如何分派任務，可使總時間最少？示，問如何分派任務，可使總時間最少？任務任務人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982指派問題求解過程如下：求解過程如下：第一步，變換系數(shù)矩陣：第一步，變換系數(shù)矩陣：5第二步，試指派：第二步，試指派：找到找到 3 個獨立零元素個獨立零元素 但但 m=3 n=4指派問題 第三步，作最少的直線覆蓋所有第三步，作最少的直線覆蓋所有0元素：元素：獨立零元素的個數(shù)獨立零元素的個數(shù)m等于最少直線數(shù)等于最少直線數(shù)l，即，即lm=3n=4；第四步，變換矩陣第四步，變換矩陣(bij)以增加以增加0元素：沒有被直線覆蓋的所有元元素：沒有被直線覆蓋的所有元素中的最小元素為素中的最小元素為1，然后打，然后打各行都減去各行都減去1；打；打各列都加上各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派：得如下矩陣，并轉(zhuǎn)第二步進行試指派：指派問題000 0 00得得到到4個個獨獨立立零零元元素素，所所以以最最優(yōu)優(yōu)解解矩陣為：矩陣為：15 指派問題