第五章整數(shù)規(guī)劃

1、第五章整數(shù)規(guī)劃主要內(nèi)容：1、分枝定界法；2、割平面法；3、0 1型整數(shù)規(guī)劃；4、指派問題。重點與難點：分枝定界法和割平面法的原理、求解方法， 0-1型規(guī)劃模型的建立及求解步驟，用 匈牙利法求解指派問題的方法和技巧。要 求：理解本章內(nèi)容，熟練掌握求解整數(shù)規(guī)劃的方法和步驟，能夠運用這些方法解決實際問題。§ 1 問題的提出要求變量取為整數(shù)的線性規(guī)劃問題，稱為整數(shù)規(guī)則問題（簡稱 IP）。如果所有的變量都要求為（非負）整數(shù)，稱之為純整數(shù)規(guī)劃或全整數(shù)規(guī)劃；如果僅一部分變量要求為整數(shù)， 稱為混合整數(shù)規(guī) 劃。例1求解下列整數(shù)規(guī)劃問題maxz 二 20x< 10x25x14x2 蘭 24I2x5

2、x2 ' 13x2 - 0x1, x2為整數(shù)如果不考慮整數(shù)約束，就是一個線性規(guī)劃問題（稱這樣的問題為原問題相應(yīng)的線性規(guī)劃問題）很容易求得最優(yōu)解為：& = 4.8 , x 0 , maxz= 96。用圖解法將結(jié)果表示于圖中畫“ +”號的點都是可行的整數(shù)解，為滿足要求，將等值線向原點方向移動，當?shù)谝淮斡龅健?+ ”號點(x = 4 , x2 = 1)時得最優(yōu)解為為=4 , X2 = 1， 最優(yōu)值為z=90。由上例可看出，用枚舉法是容易想到的，但常常得到最優(yōu)解比較困難，尤其是遇到變量的取值 更多時，就更困難了。下面介紹幾種常用解法。§ 2分枝定界法分枝定界法可用于解純整數(shù)或

3、混合的整數(shù)規(guī)劃問題。 基本思路：設(shè)有最大化的整數(shù)規(guī)劃問題 A， 與之相應(yīng)的線性規(guī)劃問題B,從解B開始，若其最優(yōu)解不符合 A的整數(shù)條件，那么B的最優(yōu)值必* 一 *是A的最優(yōu)值 Z 的上界，記為 Z ;而A的任意可行解的目標函數(shù)值是 Z 的一個下界 Z，采取將B的可行域分枝的方法，逐步減少Z和增大z，最終求得z*?，F(xiàn)舉例說明：例2求解Amaxz 二 40xi 90x29x1 7x2 乞 567x120x2 豈 70XM - 0x1,x2為整數(shù)解：先不考慮條件，即解相應(yīng)的線性規(guī)劃B (-)，得最優(yōu)解 Xi = 4.81, X2二1.82,Zo356 （見下圖）。顯然，它不符合整數(shù)條件。這時，Zo為問

4、題A的最優(yōu)值z*的上界，記Z = Zo，而為=0, X2 =0顯然是問題A的一個整數(shù)可行* *解，這時z=0，是z的一個下界，記z = 0，即0乞z < 256。X2H8、分枝定界法的解法，首先注意其中一個非整數(shù)變量的解，如 x1，在B中x1=4.81，于是對原問題增 加兩個約束條件：乞4、xi 一5，可將原問題分解為兩個子問題 Bi、B2 （即兩枝），給每枝增加一 個約束條件，如圖。問題B1冋題B2乙=349z2 =341% =4xi = 5X2 =2.1X2 =1.57012345678910x1不考慮整數(shù)條件解問題B2得到最優(yōu)解：顯然未得到全部變量是整數(shù)解，* ZiZ2 , 將 z

5、改為349 ( z =349),0乞匚349。繼續(xù)對問題Bi、B2進行分解zZ2，-先分解Bi為兩枝，增加條件X2蘭2的問題稱為B3 ；增加條件X2 - 3的問題稱為B4。在上圖中再去掉X2 2與x 3之 間的可行域，再求解問題 B3、B4，其結(jié)果列在下圖中，可見問題 B3的解已都是整數(shù)，它的目 標函數(shù)值Z3二340，取Z =340,而它大于z4二327，所以再分解B4已無必要，而問題B2*的Z2二341，所以z可能在340蘭z*蘭341之間有整數(shù)解，于是再對B?分解，得問題 B5，B6， B5 為非整數(shù)解，且 Z 二 308 Z3， 問題B6為無可行解，于是可斷定：*z3 二 z = Z 二

6、 340，x廠 4, x2 -2為最優(yōu)整數(shù)解。二 356z = 349由以上解題過程可得到分枝定界法的求解步驟:1. 給定原問題的初始上界z解與原問題A相應(yīng)的線性規(guī)劃問題B，可能出現(xiàn)以下情況之一： B沒有可行解，這時A也沒有可行解，則停止； B有最優(yōu)解，并符合A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止； B有最優(yōu)解，但不符合A的整數(shù)條件，記它的目標函數(shù)值 z0為Z o2. 給定原問題的初始下界z用觀察法找出問題A的一整數(shù)可行解，一般取Xj =0, j =1,2/ ,n。求得其目標函數(shù)值，記作Z o 這樣，就有z乞Z o3. 分枝在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量 Xj，其值為bj，

7、以bj表示小于bj的最大整 數(shù)，構(gòu)造兩個約束條件：Xj 打bj和 Xj -bj 1并將其分別加入問題B，求兩個后繼規(guī)劃問題B!、B2，不考慮整數(shù)條件，解這兩個后繼問題。4. 定界（修改上、下界）以每個后繼問題為一分枝標明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標函數(shù)值最大者作為新的上界z，從已符合整數(shù)條件的各分支中，找出目標函數(shù)值的最大者作為新的下界zo5. 比較與剪枝各分枝的最優(yōu)目標函數(shù)值中若有小于 z者，則剪掉這枝，以后不再考慮了，若大于 z，且不符合整數(shù)條件，則繼續(xù)分枝直到得到 zz為止，求得最優(yōu)整數(shù)解X* （j =12，n）§ 3割平面法這個方法的基礎(chǔ)仍是用解線性規(guī)劃的

8、方法去解整數(shù)規(guī)劃問題，首先不考慮變量xj是整數(shù)這個條件，但增加線性約束條件（用幾何術(shù)語，稱為割平面）使得由原可行域中切割掉一部分，這部分 只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解。 這個方法就是指出怎樣找到適當?shù)母钇矫?（不見 得一次就找到），使切割后最終得到這樣的可行域，它的一個有整數(shù)坐標的極點恰好是問題的最優(yōu) 解。例3求解max z = xi X2一捲+x2蘭13捲+x2蘭4 x1,x2'0 x1,x2整數(shù)3 710x1, x2, max z 二4 44將原問題化為標準型如不考慮條件，求得相應(yīng)的線性規(guī)劃的最優(yōu)解：就是圖中可行域R的極點A，不符合整數(shù)條件maxz =捲 x2 0x3

9、 0x4L-XI +x2 +x3 =13為 +x2 +x4 =4Xj >0 j =1,2,4xj為整數(shù)j =1,2，,4不考慮整數(shù)條件，用單純形法求解相應(yīng)線性規(guī)劃的最優(yōu)解。初始表最終表1100CbXbBX1X2X3X40X31-11100X443101111X13/410-1/41/41X27/4013/41/4-1/2-1/25x1max z =2由最終表中得到變量間的關(guān)系式:X2tX3V4將系數(shù)和常數(shù)項都分解為整數(shù)和非負真分數(shù)之和，并移項變?yōu)? （3 J 、Xi - X3X3 X44 144 丿彳 33*1'X2 -1X3X4244 34 4現(xiàn)考慮整數(shù)條件，X1,X2為非負整

10、數(shù)，那么X3,X4也是非負整數(shù)。對上式，從等式左邊看是整數(shù),等式右邊的（）是正數(shù)，所以等式右邊定一為負數(shù)，即-X3 X4 <04144整理得：3x3 X4 一 3切割方程將新的約束方程，引入松馳變量，得到 -3x3 -x4 x5 = -3，將其列入最終表11000CbXbbX1X2X3X4X51X13/4-11-1/41/401X27/4313/41/400X5-300-3-11-1/2 - 1/21X111001/31/121X2101001/40X31001-1-1/3-1/3-1/6*T最優(yōu)解 X =（1,1,1,0,0）T，最優(yōu)值 z=2一、割平面法的解題步驟：1. 若aj,b中

11、有分數(shù)，先全部整數(shù)化，而后引入松馳變量，暫不考慮整數(shù)約束條件，用單純形 法求出相應(yīng)線性規(guī)劃的最優(yōu)解。2. 求切割方程 令人是相應(yīng)線性規(guī)劃最優(yōu)解中為分數(shù)值的一個基變量，由最終單純形表得到Xi 、ajkXk 二 bj（ 1）k其中：Q（Q指構(gòu)成基變量下標的集合）K（ K指構(gòu)成非基變量下標的集合） 將bj和ajk都分解成整數(shù)部分N與真分數(shù)f之和，即bj =Nj fj，其中 0 ： fj ：1（2）ajk 二 Njk fjk，其中 0< fjk 1而N表示不超過b的最大整數(shù)，如：若 b=2.35，則 N=2f=0.35b= - 0.45,則 N= - 1f=0.55將（2）代入（1）得X 

12、9; NjkXk - Nj = ££kXkkk 現(xiàn)在提出變量為整數(shù)的條件，上式由左邊看必是整數(shù)，由右邊看，因為0： fj <1所以不能為正，即fj 一 fjkXk -0 割線方程k3. 把切割方程作為新的約束條件，并入單純形最優(yōu)表。繼續(xù)換算，取得最優(yōu)解。割平面法的性質(zhì)1. 害IJ平面法割去了整數(shù)規(guī)劃原問題相應(yīng)的線性規(guī)劃問題的最優(yōu)解。2. 割平面未割去整數(shù)規(guī)劃原問題的任一可行解，即未割去其相應(yīng)的線性規(guī)劃問題的任一整數(shù) 可行解。§ 40- 1 規(guī)戈I、0-1變量及其應(yīng)用0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，它的變量洛僅取值0或1,這時Xi稱為0-1變量，或 稱二

13、進制變量。0-1變量作為邏輯變量(logical variable)，常用來表示系統(tǒng)是否處于某個特定狀態(tài), 或者決策時是否取某個特定方案。例如1當決策取方案P時X =一0當決策不取方案P時(即取P時)當問題含有多項要素，而每項要素皆有兩種選擇時，可用一組0-1變量來描述。一般地，設(shè)問題有有限項要素 巳也,，En，每項Ei有兩種選擇A和Ai(i =1,2,n),則可令若Ei選擇Ai 若Ei選擇Ai(i =1,2/ , n)那么，向量(X1,X2，,Xn)T就描述了問題的特定狀態(tài)或方案，即'(1,1,1,1)T,若選擇(A,A2,A代)丁(1,1，,1,0)T,若選擇(宀,A?,An 丄

14、An)T(X1,X2，,Xn)T = *(1,0，,0,0)T,若選擇(A1, A2,Nn_l,Nn)T(0,0，,0,0)T,若選擇(A1, A2,，And, An)T1、選址問題-相互排斥的計劃例4某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個位置Ai (i =1,2，,7)可供選擇,規(guī)定在東區(qū)，由A,A2,A3三個點中至多選兩個;在西區(qū)，由A4,A5兩個點中至少選一個；在西區(qū)，由A6, A7二個點中至少選一個。如選用A點，設(shè)備投資估計為bi元，每年可獲利潤估計為Ci元，但投資總額不能超過 B元, 問應(yīng)選擇哪幾個點可使利潤為最大？解：先引入0- 1變量Xj(i=1,2,7)Xi,當Ai

15、點被選用 .0 ,當Ai點未被選用(i7于是冋題可列成：max z 八 CiXii 47bXi蘭Bi 二捲 + x2 + X3 蘭 2« X4 + X5 王 1X6 + x7 >1Xj = 0或 12、相互排斥的約束條件例5.某廠決定生產(chǎn)兩種產(chǎn)品，有兩種加工方法可供選用，已知設(shè)備供應(yīng)情況:方法 產(chǎn)品III每日可供使用工時ABABd1543212d2128問選用哪種加工方法收益最大。解：設(shè)A產(chǎn)品的日產(chǎn)量為X1, B產(chǎn)品的日產(chǎn)量為X2若采用I,其約束條件：5x1 4x<<12若米用II，其約束條件：3x1 2x2 < 12x1 2x2 三 8由于最終只能選用一種方

16、法，我們引入0-1變量和一個任意大的正數(shù) M1 ,選用I時0 ,選用II時于是，上述約束條件可變?yōu)椋?x1 4x2 乞 12 (1 -y)M3x1 2x2 <12 yMx1 2x2 咗8 yM若選用第一種方法生產(chǎn)，則y=1，約束條件就變成5為*4x2乞12，其余的約束條件就失去了作 用；若選用第二種方法生產(chǎn)，則 y=0,第一個約束條件由于右側(cè)多了一個 M成了多余的限制。注意：引入的變量y不必出現(xiàn)在目標函數(shù)內(nèi)，即認為在目標函數(shù)中y的系數(shù)為0。3、關(guān)于固定費用問題(Fixed cost Problem)例6某廠生產(chǎn)某種產(chǎn)品，有幾種生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高(自動化程度 高的設(shè)備

17、)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低，反之，分配到每件產(chǎn)品的變動 成本就可能增加，所以應(yīng)全面考慮。設(shè)有三種方式可供選擇，令Xj表示采用第j種方式時的產(chǎn)量Cj表示采用第j種方式時每件產(chǎn)品的變動成本 kj表示米用第j種方式時的固定成本則采用各種方式的總成本分別為= 1,2,3kj + q Xj , xj > 0 Pj =0Xj =0引入0-1變量和任意大的正數(shù) M，令1 ,采用第j種生產(chǎn)方式，即xj > 0 Vi =一一0 ,不采用第j種生產(chǎn)方式，即Xj =0于是目標函數(shù)m i 0 = (k1 y1 c1x1) (k2y2 c2x2) (k3y3 c3x3)約束條件xj

18、< yiM , j =1,2,3當Xj 0時， =1 ；當Xj =0時，yi =0，才有意義。二、0- 1規(guī)劃的解法解0-1規(guī)劃最容易想到的方法，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的20個組合。對于變量個數(shù)0較大(如0>10)時, 是不可能的。因此，人們設(shè)計一種方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解， 這種方法稱為隱舉法(Implicit Enumeration)，下面舉例說明這種方法。例 7 maxz =3x1 -2x2 5x3X12 X2 - X3 込 2(1 )X14 xx 3 _ 4(2)X1x

19、 2 _ 3(3)4x1X3- 6(4)X1 , X2 , X3 = 0 或 1(5)解題時，先通過試探的方法找一個可行解，容易看出（xX2，X3）=（1,0,0）就適合（1） - （5）條件，計算出相應(yīng)的目標函數(shù)值z=3。我們求最優(yōu)解，對于極大化問題，當然希望 z_3，于是增加一個約束條件：3x1 - 2x2 5x3 _ 3（ 0）后加的條件稱為過濾條件（Filtering Constraint），這樣，原問題的線性約束條件就變成 5個，若 用全部枚舉的方法，3個變量8個解，原來4個約束條件，共需32次運算；現(xiàn)增加了過濾條件， 如按隱枚舉法，就可減少運算次數(shù)。將5個約束條件按（0）-（ 4）

20、順序排好，對每個解，依次代入約束條件左側(cè)，求出數(shù)值，看 是否適用不等式條件，如某一條件不適合，同行以下各條件就不必再檢查，因而就減少了運算次數(shù)。 計算過程列表如下：占八、條件是否滿足條件？ 是（2）否（X）Z值(0)(1)(2)(3)(0,0,0)0X(0,0,1)5-1101V5(0,1,0)-2X(0,1,1)315X(1,0,0)31110V3(1,0,1)80211V8(1,1,0)1X(1,1,1)626X最優(yōu)解（x1, x2, x3） = （1,0,1），最優(yōu)值 max z = 8注意：在計算過程中，若遇到Z值已超過條件（0）右邊的值，應(yīng)改變條件（0）,使右邊為當前為 止最大者，如

21、當檢查點（0,0,1）時，因z=5（3），所以將條件（0）換成3% - 2x2 5x3 一 5（0）'這樣對過濾條件的改進，更可以減少計算量。§ 5指派問題在實際工作中經(jīng)常遇到這樣的問題：某單位需完成 n項任務(wù)，恰好有n個人可承擔這些任務(wù)。 由于每人的專長不同，各人完成任務(wù)不同（或所費時間），效率也不同。于是產(chǎn)生應(yīng)指派哪個人去 完成哪項任務(wù)，使完成n項任務(wù)的總效率最高（或所需時間最少）的問題， 這類問題稱為指派問題 或分派問題。一、指派問題的數(shù)學(xué)模型例8有一份說明書，需譯成英、日德、俄四種文字。現(xiàn)有甲、乙、丙、丁四人，他們將說明 書翻譯成不同文字所需時間（單位：小時）如下表，

22、問應(yīng)指派何人去完成何工作，使所需總時間最 少？任務(wù) 人員、央日德俄甲215134乙1041415丙9141613丁78119類似有：有n項加工任務(wù)，怎樣指派到n臺機床上分別完成的問題；有n條航線，怎樣指定n 艘船去航行問題等等。對應(yīng)每個指派問題，需有類似上表的數(shù)表，稱之為效率矩陣或系數(shù)矩陣，其元素 Cj 0（i, j =1,2,，n）表示指派第i個人去完成第j項工作時的效率（或時間、成本）。我們引入0- 1變量，令Xj；1 ,指派第i人去完成第j項任務(wù)0，不指派第i人去完成第j項任務(wù)數(shù)學(xué)模型（當問題要求極小化時）：min z = ' ' cij xiji j區(qū) xij =1 ,

23、 j =1,2,，n(1)=1吃 Xj =1 , i =1,2，,n(2)jXj 1 或 0(3)約束條件（1）說明第j種任務(wù)只能由1人去完成；約束條件（2）說明第i個人只能完成1項 任務(wù)。二、指派問題的解法1. 指派問題最優(yōu)解的性質(zhì)：若從系數(shù)矩陣（Cj）的一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣（勺）,那么以Q）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。根據(jù)這個性質(zhì)，可使原系數(shù)矩陣變換為每行每列中均有0元素的新系數(shù)矩陣，并使這幾個 0元素位于不同行或不同列，則令相應(yīng)的 Xj =1,其余的Xj全為0,這樣就得到了最優(yōu)解，這種解法稱為匈牙利法。2. 解指派問題的步驟

24、：（1）使系數(shù)矩陣經(jīng)變換各行各列中都出現(xiàn) 0元素每行各元素減去該行最小元素;每列各元素減去該列最小元素。若某行（列）已有 0元素，就不必再減了min-2151314(Cj )=10414159141613-78119 一2-04 t 6907衛(wèi)13 1120 10 11574142一42 min0 136 00 5衛(wèi) 1二(bj)(II)（2）用最少的直線劃去所有0元素，當所劃直線數(shù)l=n （矩陣階數(shù)）時，就可得到最優(yōu)方案初始指派。用最少的直線畫去II中的所有0元素76301305101920(III)l=n=4，已得到最優(yōu)方案若得不到最優(yōu)方案，需進行改進A、未被劃去的所有元素減去其中最小元素，以便得到新的0元素102 53-400 0 40 0 4 013 20才03 2 0 00 14 2 0 14 28 0 4 0：_8 0 4 0 一B、橫、豎直線交叉處的所有元素增加 A中所減的最小元素（以避免重復(fù)指派和消除等不正當 指派），得到新矩陣，并以最少直線劃去所有 0元素。如：（3）最優(yōu)方案的確定0元素所在格的