運籌學整數規(guī)劃

運籌帷幄之中決勝千里之外運籌學課件整數規(guī)劃IntegralLinearProgramming1整數規(guī)劃(IntegerProgramming)整數規(guī)劃的模型分支定界法割平面法0－1整數規(guī)劃指派問題2（一）、整數規(guī)劃問題實例例一、合理下料問題設用某型號的圓鋼下零件A1,

A2,…,Am的毛坯。在一根圓鋼上下料的方式有B1,B2,…Bn種，每種下料方式可以得到各種零件的毛坯數以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件方毛坯數式零件零件需求數一、整數規(guī)劃的模型3設：xj

表示用Bj(j=1.2…n)種方式下料根數模型：例二、某公司計劃在m個地點建廠，可供選擇的地點有A1,A2…Am，他們的生產能力分別是a1,a2,…am（假設生產同一產品）。第i個工廠的建設費用為fi

(i=1.2…m),又有n個地點B1,B2,…Bn需要銷售這種產品，其銷量分別為b1.b2…bn

。從工廠運往銷地的單位運費為Cij。試決定應在哪些地方建廠，即滿足各地需要，又使總建設費用和總運輸費用最?。?單銷地廠址價生產能力建設費用銷量5設：

xij

表示從工廠運往銷地的運量(i=1.2…m、j=1.2…n),1在Ai建廠又設Yi＝（i=1.2…m）

0不在Ai建廠模型：6例三、機床分配問題設有m臺同類機床，要加工n種零件。已知各種零件的加工時間分別為a1,a2,…an，問如何分配，使各機床的總加工任務相等，或者說盡可能平衡。設：1分配第i臺機床加工第j種零件；

xij＝（i=1.2…m,j=1.2…n）0相反。于是，第i臺機床加工各種零件的總時間為：又由于一個零件只能在一臺機床上加工，所以有7

因此，求xij，使得8（二）、整數規(guī)劃的數學模型一般形式依照決策變量取整要求的不同，整數規(guī)劃可分為純整數規(guī)劃、全整數規(guī)劃、混合整數規(guī)劃、0－1整數規(guī)劃。9

純整數規(guī)劃：所有決策變量要求取非負整數（這時引進的松弛變量和剩余變量可以不要求取整數）。全整數規(guī)劃：除了所有決策變量要求取非負整數外，系數aij和常數bi也要求取整數（這時引進的松弛變量和剩余變量也必須是整數）。混合整數規(guī)劃：只有一部分的決策變量要求取非負整數，另一部分可以取非負實數。0－1整數規(guī)劃：所有決策變量只能取0或1兩個整數。10（三）、整數規(guī)劃與線性規(guī)劃的關系

從數學模型上看整數規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎上，通過舍入取整，尋求滿足整數要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數）也不一定就是最優(yōu)解，有時甚至不能保證所得倒的解是整數可行解。舉例說明。11例：設整數規(guī)劃問題如下首先不考慮整數約束，得到線性規(guī)劃問題（一般稱為松弛問題）。12用解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)現求整數解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數規(guī)劃的最優(yōu)解。按整數規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內且為整數點。故整數規(guī)劃問題的可行解集是一個有限集，如圖所示。圖13

因此，可將集合內的整數點一一找出，其最大目標函數的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。

目前，常用的求解整數規(guī)劃的方法有：

分支定界法和割平面法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。14（一）、基本思路

考慮純整數問題：整數問題的松弛問題：二、分枝定界法15

1、先不考慮整數約束，解(

IP)的松弛問題(LP)，可能得到以下情況之一：

⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計算。

⑵.若(LP)有最優(yōu)解，并符合(IP)的整數條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。

⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數條件，轉入下一步。為討論方便，設(LP)的最優(yōu)解為：

162、定界：記(

IP)的目標函數最優(yōu)值為Z*,以Z(0)作為Z*的上界，記為＝Z(0)。再用觀察法找的一個整數可行解X′，并以其相應的目標函數值Z′作為Z*的下界，記為Z＝Z′，也可以令Z＝－∞，則有：

Z≤Z*≤

3、分枝：在(LP)的最優(yōu)解X(0)中，任選一個不符合整數條件的變量，例如xr=（不為整數），以表示不超過的最大整數。構造兩個約束條件

xr≤和xr≥＋117如此反復進行，直到得到Z＝Z*＝為止，即得最優(yōu)解X*

。將這兩個約束條件分別加入問題(

IP)，形成兩個子問題(

IP1)和(

IP2)，再解這兩個問題的松弛問題(LP1)和(LP2)。4、修改上、下界：按照以下兩點規(guī)則進行。⑴.在各分枝問題中，找出目標函數值最大者作為新的上界；⑵.從已符合整數條件的分枝中，找出目標函數值最大者作為新的下界。5、比較與剪枝：

各分枝的目標函數值中，若有小于Z者，則剪掉此枝，表明此子問題已經探清，不必再分枝了;否則繼續(xù)分枝。18例一：用分枝定界法求解整數規(guī)劃問題（用圖解法計算）記為（IP）解：首先去掉整數約束，變成一般線性規(guī)劃問題記為（LP）（二）、例題

19用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2

≤3，x2

≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。20有下式：現在只要求出（LP1）和（LP2）的最優(yōu)解即可。21x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如圖所示。此時B在點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數解，問題已探明，此枝停止計算。11同理求（LP2）,如圖所示。在C點取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)

<Z(1)＝－16∴原問題有比（－16）更小的最優(yōu)解，但x2不是整數，故利用

3≥10/3≥4加入條件。BAC22加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。23x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數，可繼續(xù)分枝。即3≤x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。24在（LP3）的基礎上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。25x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時E在點取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數解，問題已探明，此枝停止計算。E求（LP6），如圖所示。此時F在點取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如對Z(6)繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。26至此，原問題（IP）的最優(yōu)解為：

x1=2，x2=3,

Z*=Z(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.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃27練習：用分枝定界法求解整數規(guī)劃問題

（圖解法）

28LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃29LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9LP3x1=33/14,x2=2Z(3)＝61/14LP4無可行解LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃303200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對應的(LP)問題,如表所示,獲得最優(yōu)解。初始表最終表例二、用分枝定界法求解整數規(guī)劃問題（單純形法）

31x1=13/4

x2=5/2Z(0)=59/4≈14.75

選x2進行分枝，即增加兩個約束，2≥x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計算。即x2+x5=2,－x2+x6=－3

得下表:3232000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2

Z(1)=29/2=14.5繼續(xù)分枝，加入約束

3≥x1≥4LP13332000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考慮分枝34接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進行計算。35CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2

Z(3)=13找到整數解，問題已探明，停止計算。LP336CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4,x2=1

Z(4)=14找到整數解，問題已探明，停止計算。LP437樹形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4＃＃＃38練習：用分枝定界法求解整數規(guī)劃問題

（單純形法）39cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/11040LP1x1=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.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃41（一）、計算步驟：1、用單純形法求解(IP)對應的松弛問題(LP)：⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計算。⑵.若(LP)有最優(yōu)解，并符合(IP)的整數條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數條件，轉入下一步。三、割平面法422、從(LP)的最優(yōu)解中，任選一個不為整數的分量xr,,將最優(yōu)單純形表中該行的系數和分解為整數部分和小數部分之和，并以該行為源行，按下式作割平面方程：3、將所得的割平面方程作為一個新的約束條件置于最優(yōu)單純形表中（同時增加一個單位列向量），用對偶單純形法求出新的最優(yōu)解，返回1。的小數部分的小數部分43例一：用割平面法求解整數規(guī)劃問題解：增加松弛變量x3和x4，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/444此題的最優(yōu)解為：X＊(1,3/2)Z=3/2但不是整數最優(yōu)解，引入割平面。以x2為源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我們已將所需要的數分解為整數和分數，所以，生成割平面的條件為:也即：45將x3=6-3x1-2x2,x4=3x1-2x2,帶入中，得到等價的割平面條件：x2≤

1見下圖。x1x2⑴⑵33第一個割平面46Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40現將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-147此時，X1

＝(2/3,1),Z=1,仍不是整數解。繼續(xù)以x1為源行生成割平面，其條件為：用上表的約束解出x4和s1，將它們帶入上式得到等價的割平面條件：x1≥x2，見圖：x1x2⑴⑵33第一個割平面第二個割平面48將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/249CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10至此得到最優(yōu)表，其最優(yōu)解為X＊=(1,1),Z=1,這也是原問題的最優(yōu)解。有以上解題過程可見，表中含有分數元素且算法過程中始終保持對偶可行性，因此，這個算法也稱為分數對偶割平面算法。50例二：用割平面法求解數規(guī)劃問題Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最優(yōu)表51在松弛問題最優(yōu)解中，x1,x2

均為非整數解，由上表有：將系數和常數都分解成整數和非負真分數之和52以上式子只須考慮一個即可，解題經驗表明，考慮式子右端最大真分數的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數相等，可任選一個考慮。現選第二個式子，并將真分數移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。53Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/60Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－3－Z－40000－1/2﹡得到整數最優(yōu)解，即為整數規(guī)劃的最優(yōu)解，而且此整數規(guī)劃有兩個最優(yōu)解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。

5455CBXBbx1x2x3x4x50x34001-1/34/34x24/30102/9-5/911x18/31001/92/9－Z000-19/9-2/9CBXBbx1x2x3x4x5s10x30001-1064x230101/20-5/211x121000010x530001/21-9/2－Z000-20-1（2，3）560－1整數規(guī)劃是一種特殊形式的整數規(guī)劃，這時的決策變量xi只取兩個值0或1，一般的解法為隱枚舉法。例一、求解下列0－1規(guī)劃問題四、0－1整數規(guī)劃57

解：對于0－1規(guī)劃問題，由于每個變量只取0，1兩個值，一般會用窮舉法來解，即將所有的0，1組合找出，使目標函數達到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基礎上，通過加入一定的條件，就能較快的求得最優(yōu)解。x1.x2.x3約束條件滿足條件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15 ×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×58由上表可知，問題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一個可行解，為盡快找到最優(yōu)解，可將3

x1－2x2＋5x3≥5作為一個約束，凡是目標函數值小于5的組合不必討論，如下表。x1.x2.x3約束條件滿足條件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×59例二、求解下列0－1規(guī)劃問題解：由于目標函數中變量x1,x2,

x4

的系數均為負數，可作如下變換：令x1＝1－x1′

,x2=1-x2′,x3=x3′,x4=1-x4′帶入原題中，但需重新調整變量編號。令x3′

=x1′,x4′=x2′得到下式。60可以從(1.1.1.1)開始試算，x′(3)＝(1.1.0.1)最優(yōu)解?！鄕(3)＝(1.0.1.0)是原問題的最優(yōu)解，Z*=－261例三、求解下列0－1規(guī)劃問題令y1=x5,y2=x4,y3=x2,y4=x3,y5=x1得到下式62y1.y2.y3.y4.y5約束條件滿足條件Z值(1)(2)是∨否×(0.0.0.0.0)00×(1.0.0.0.0)1-1×(0.1.0.0.0)-11×(0.0.1.0.0)-21×(0.0.0.1.0)4-4∨8(0.0.0.0.1)3-2×所以，

Y*=（0.0.0.1.0），原問題的最優(yōu)解為：

X*＝（0.0.1.0.0），Z*=863（0.1.1.0.0）練習：用隱枚舉法求解0—1規(guī)劃問題64

在實際中經常會遇到這樣的問題，有n項不同的任務，需要n個人分別完成其中的一項，但由于任務的性質和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產生了一個問題，應指派哪個人去完成哪項任務，使完成n項任務的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。（一）、指派問題的數學模型設n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第I個人去做第j件工作的的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設Cij≥0。問應如何分配才能使總效率（時間或費用）最高？五、指派問題65設決策變量1分配第i個人去做第j件工作

xij=0相反(I,j=1.2.…n)其數學模型為：66（二）、解題步驟：指派問題是0-1規(guī)劃的特例，也是運輸問題的特例，當然可用整數規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數矩陣中獨立0元素的最多個數等于能覆蓋所有0元素的最少直線數。

第一步：變換指派問題的系數矩陣（cij）為(bij)，使在(bij)的各行各列中都出現0元素，即(1)從（cij）的每行元素都減去該行的最小元素；(2)再從所得新系數矩陣的每列元素中減去該列的最小元素。67第二步：進行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為：(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務已指派完，不必再考慮別人了。(2)給只有一個0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．(3)反復進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。68(4)若仍有沒有劃圈的0元素，且同行(列)的