2整數(shù)規(guī)劃(研究生)

1、整數(shù)規(guī)劃南京航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院 教授、博士生導(dǎo)師 管理科學(xué)與工程系主任 1第五章 整數(shù)規(guī)劃 在線性規(guī)劃問題中，所有的解都假設(shè)為具有連續(xù) 型的數(shù)值，即解可以是整數(shù)、分?jǐn)?shù)或帶有小數(shù)點(diǎn)的實(shí) 數(shù)。但對于某些具體的問題，常要求最優(yōu)解是整數(shù)的 情形。例如，所求的解是機(jī)器臺數(shù)，完成工作的人數(shù) 或裝貨的車數(shù)等，這時，分?jǐn)?shù)或小數(shù)的解答就不符合 要求。為了滿足整數(shù)解的要求，初看起來，似乎只要 把已求得的解經(jīng)過“舍入化整”就可以，但這常常是不 可行的。因為化整后不見得是可行解?；螂m然是可行 解，但不一定是最優(yōu)解。因此，對求最優(yōu)整數(shù)解的問題，有必要另行研究。我們稱這樣的問題為整數(shù)規(guī)劃 (Integer Pro

2、gramming)，簡稱為 I P 。2整數(shù)規(guī)劃中，如果所有的變量都要求是（非負(fù)） 整數(shù)，就稱為純整數(shù)規(guī)劃(Pure Integer Programming) 或全整數(shù)規(guī)劃(All Integer Programming)；如果僅是 其中一部分變量取值為整數(shù)，則稱為混合整數(shù)規(guī)劃( Mixed Integer Programming )。 3第2章 整數(shù)規(guī)劃例1、集裝箱運(yùn)貨 貨物 體積(米3/箱) 重量(百公斤/箱) 利潤(千元/箱) 甲 5 2 20 乙 4 5 10 裝運(yùn)限制 24 13 2.1 數(shù)學(xué)模型4解：設(shè)X1 , X2 為甲、乙兩貨物各托運(yùn)箱數(shù)5X1+4X2 242X1+5X2 13

3、X1 , X2 0X1 , X2為整數(shù)maxZ = 20 X1 + 10 X25例2、背包問題背包可再裝入8單位重量，10單位體積物品物品 名稱 重量 體積 價值 1 書 5 2 20 2 攝像機(jī) 3 1 30 3 枕頭 1 4 10 4 休閑食品 2 3 18 5 衣服 4 5 15 6解：Xi為是否帶第 i 種物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi為0, 17一般形式：,整數(shù)8(1)、 Xi為i 物品攜帶數(shù)量 ai為i 物品單位重量 ci為i 物品重要性估價 b

4、為最大負(fù)重(2)、 投資決策 Xi為在i 地區(qū)建廠規(guī)模 ai為在i 地區(qū)建廠基建費(fèi)用 ci為在i 地區(qū)建廠單位利潤 b為最大資本(3)、 Xi 取0或1時，可作項目投資模型9例3、選址問題A1A3B2B4B3B1A2Ai: 可建倉庫地點(diǎn)，容量ai ,投資費(fèi)用bi ，建2個Bj: 商店，需求dj ( j=14 )Cij: 倉庫 i 到商店 j 的單位 運(yùn)費(fèi)問：選擇適當(dāng)?shù)攸c(diǎn)建倉庫，在滿足商店需求條件下，總費(fèi)用最小。10解：設(shè)Xi ( i=1,2,3)為是否在 Ai 建倉庫 yij ( i=1,2,3, j=14)由 i倉庫向 j商店運(yùn)貨量y11 + y21 = d1y12 + y22 + y32

5、= d2y23+ y33 = d3y14 + y24 + y34 = d4x1 + x2 + x3= 2y11 + y12 + y14 a1x1y21 + y22 + y23 + y24a2x2y32 + y33 + y34 a3x3xi 為01， yij 0混合整數(shù)規(guī)劃1101決策變量的應(yīng)用 可用于相互排斥計劃中例1、運(yùn)輸方式：火車、船。 火車：5X1+4X2 24 (體積) 船： 7X1+3X2 45 (體積)12maxZ=20X1 + 10X2 2X1+5X2 135X1+4X2 24+MX37X1+3X2 45+M(1-X3 )X1 , X2 0 整數(shù)X3為0或1 M0當(dāng) X3 =0

6、火車 X3 =1 船 13例2、ai1x1+ai2x2 +ainxn bi (i=1,m)互相排斥m個約束，只有一個起作用ai1x1+ainxn bi+yi M (i=1,m)y1 + ym =m-1yi為0或1 M0142.2 整數(shù)規(guī)劃解法(一)、整數(shù)規(guī)劃的解：可行域為其相應(yīng)線性規(guī)劃問題的可行域的子集例1、LP:X=(4.8,0) maxZ=96 ILP:X=(4,1) maxZ=90 x1x262O6.5(4.8,0)15(1)、四舍五入法 可估近似解，例中X=(4,0), Z=80 80 Z* 96 0Z*- 80S0 且解為整數(shù)解，令ScS0 且解為非整數(shù)解，令(C)，(D)取代(B)

7、 返回(4)(6)、全部枝剪完，停25優(yōu)點(diǎn)：(1)、任何模型均可用；(2)、思路簡單、靈活；(3)、速度快；(4)、適合上機(jī)。26分枝定界法注意事項：(1)、分枝變量選擇原則： 按目標(biāo)函數(shù)系數(shù)：選系數(shù)絕對值最大者變 量先分。 對目標(biāo)值升降影響最大。 選與整數(shù)值相差最大的非整數(shù)變量先分枝。 按使用者經(jīng)驗，對各整數(shù)變量排定重要性 的優(yōu)先順序。27(2)、分枝節(jié)點(diǎn)選擇： 廣探法： 選目標(biāo)函數(shù)當(dāng)前最大值節(jié)點(diǎn)，找到的整數(shù) 解質(zhì)量高。慢。 深探法(后進(jìn)先出法)： 最后打開的節(jié)點(diǎn)最先選，盡快找到整數(shù)解。 整數(shù)解質(zhì)量可能不高。2801問題的分枝定界法（背包問題)例： maxZ=12X1 + 12X2 + 9X

8、3 + 15X4 + 90X5 + 26X6+ 112X7 (A)3X1 + 4X2 + 3X3 + 3X4 + 15X5 + 13X6+ 16X7 35Xj為0或1，(j=17)松弛問題(B)為同于(A)約束，目標(biāo)0 Xj 1 (j=17)29解:“單位重量價值大的先放” 重量 價值 價/重 1 3 12 4 2 4 12 3 3 3 9 3 4 3 15 5 5 15 90 6 6 13 26 2 7 16 112 7 30(0)Z=221 X7=X5=X4=1X1=1/3(9)217 X1=X4=X7=1X5=13/5(10)217 X1=X7=X5=1X2=1/4(5)216X3=X7

9、=X5=1X4=1/3(6)219 X7=X5=X4=1X6=1/13(1)219 X1=X7=X5=1X4=1/3(7)174 X6=X7=1X5=6/15(8)217 X7=X5=X4=1(2)220X7=X5=X4=1X2=1/4(3)214 X2=X7=X5=1(4)220 X7=X5=X4=1X3=1/3X1=1X1=0 X2=1X2=0X3=1X3=0X4=1X4=0X6=1X6=031隱枚舉法(一)、基本思想：對maxZ=CXAX=bX為0的2n個可能解，只檢查其中一部分例：maxZ = 2x1+4x2 +x33x1 - 8x2+5x3 -1x1 , x2 , x3為 0 ,1

10、32(二)、簡單隱枚舉法(max)原則：(1)、用試探法，求出一個可行解，以它的目標(biāo)值作為當(dāng)前最好值Z0(2)、增加過濾條件Z Z0(3)、將xi 按ci由小大排列33例：maxZ = 3x1 -2x2+5x3x1 +2x2 - x3 2 x1 +4x2 +x3 4 x1 + x2 3 4x2+x3 6 x1 , x2 , x3為0或1解：觀察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3過濾條件：3x1 - 2x2+5x3 3 將(x1 x2 x3 ) (x2 x1 x3 ) 34解(x2 x1 x3 ) 目標(biāo)值 Z0 當(dāng)前最好值 (0 ,0 ,0) 0 5 (0 ,1

11、,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1 ,0) 1 (1 ,1 ,1) 6 最優(yōu)解 x = (1 ,0 ,1 )T Z=835割平面法3637x1 xr xm ym+1 ym+2 yn RHS0 0 0 m+1 m+2 nf*x1.xr.xm1 0 0 a1m+1 a1m+2 a1n .0 1 0 ar m+1 ar m+2 ar n .0 0 1 am m+1 a m m+2 am nb1.br.bm38394041x1 x2 x3 x4RHS0 0 -1/2 -1/2-5/2x1x21 0 -1/4 1/40 1 3/4 1/43/47/44243得到

12、新的對偶單純形表x1 x2 x3 x4 x5 RHS0 0 -1/2 -1/2 0-5/2x1x2x31 0 -1/4 1/4 0 0 1 3/4 1/4 0 0 0 -3/4 -1/4 1 3/4 7/4 -3/4 44進(jìn)一步得到最優(yōu)單純形表:x1 x2 x3 x4 x5 RHS0 0 0 -1/3 -2/3-2x1x2x31 0 0 1/3 -1/30 1 0 0 10 0 1 1/3 -4/311145指派問題一、指派問題的數(shù)學(xué)模型 在生活中經(jīng)常會遇到這樣的問題，某單位需要指派 n 個人去完成 n 項任務(wù)，每個人只做一項工作，同時，每項工作只由一個人完成。由于各人的專長不同，每個人完成各

13、項任務(wù)的效率也不同。于是產(chǎn)生了應(yīng)指派哪一個人去完成哪一項任務(wù)，使完成 n 項任務(wù)的總效率最高（如所用的時間為最少）。我們把這類問題稱之為指派問題或分派問題(Assignment Problem)。46例 1 :有一份中文說明書,需要譯成英、日、德、俄四 種文字，分別記作 E、J、G、R ?，F(xiàn)有 甲、乙、丙丁四人，他們將中文說明書翻譯成不同文字說明書所 需要的時間如表41所示。問應(yīng)指派何人去完成哪一 項工作，使所需的總時間最少？ 表41 任務(wù)人員EJGR甲215134乙1041415丙9141613丁7811947 類似的有：n 項加工任務(wù)，怎樣指派到 n 臺機(jī)床上分別完成的問題；n 條航線，怎

14、樣指定 n 艘船去航 行的問題等等。對應(yīng)每個指派問題, 都有類似表4 1那樣的表格，我們稱之為效率矩陣或系數(shù)矩陣，某 元素 cij ( i , j = 1,2, , n ) 表示指派第 i 個人去完成 第 j 項任務(wù)時的效率(或時間、成本等)。解題時需要 引入變量 xij ；其取值只能是 1 或 0，并令 ：48 當(dāng)問題是要求極小化時的數(shù)學(xué)模型是：49 指派問題的解矩陣應(yīng)當(dāng)是每行或每列只能有一個 元素為1，其余均為 0 的 n 階方陣。如下就是例1 的 一個 解矩陣： 指派問題是 01規(guī)劃的特例，也是運(yùn)輸問題的特 例；即 m = n ，ai = bj = 1。我們利用指派問題的特點(diǎn) 可以有更為

15、簡便的求解方法。50 定理 設(shè) (cij)是指派問題的系數(shù)矩陣, cij 0，i , j = 1 , 2, , n 。若從(cij)的某一行（列）各元素中分別減 去該行（列）的最小元素而得到的新矩陣 (bij) ，那么 以新矩陣 (bij) 為系數(shù)矩陣的指派問題與原問題具有相 同的最優(yōu)解。 庫恩（W.W.Kuhn）于1955年提出了指派問題的解法，他引用了匈牙利數(shù)學(xué)家康尼（D.Knig) 一個關(guān) 于矩陣中 0 元素的定理：系數(shù)矩陣中獨(dú)立 0 元素的最 多個數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。這個解 法稱之為匈牙利法。51 以下用例 1 來說明指派問題的解法。 第一步：使指派問題的系數(shù)矩陣，

16、經(jīng)變換，在各行各 列中都出現(xiàn) 0 元素。為此分如下兩步進(jìn)行：（1）將系數(shù)矩陣的每行元素減去該行的最小元素；（2）再從所得的系數(shù)矩陣中，將每列減去該列的最 小元素。（若該行或列已有 0 元素，則就不必計算） 第二步：進(jìn)行試指派以尋求最優(yōu)解。為此按如下 5 個 分步驟進(jìn)行：（1）從只有一個 0 元素的行（列）開始，給這個0 元 素加圈，記為 。然后劃去 所在的列（行）的其它 0 元素，記為 。這表示該列所代表的任務(wù)已指派 完，不必再考慮別人。52 （2）給只有一個 0 元素的列的 0 元素加圈，記為 ；然后劃去 所在行的 0 元素，記為 。（3）重復(fù)進(jìn)行（1）、（2）兩步，直到所有 0 元素 都被

17、圈出和劃掉為止。（4）若仍然有沒有被劃圈的 0 元素，且同行（列） 的 0 元素至少有兩個（表示對這個人可以從兩項任務(wù) 中指派其一），則可用不同的方案去試探。從所剩 0 元素最少的行或列開始，比較該行或列各 0 元素所在列或行中 0 元素的數(shù)目，選擇 0 元素少的那一列或行 的這個 0 元素加圈（表示選擇性多的要“禮讓”選擇性 少的）。然后劃掉同行或列的其它 0 元素。反復(fù)進(jìn)行 直到所有 0 元素都已被圈出和劃掉為止。（5）若 元素的數(shù)目 m 等于矩陣的階數(shù) n ,那么這個指派問題的最優(yōu)解已得到。若 m n,則轉(zhuǎn)入下一 步：5354 這時我們已經(jīng)找到了4個不同行不同列的 0 元 素，所以，該問

18、題的最優(yōu)解矩陣是： 這表示：指定甲翻譯俄文，乙翻譯日文，丙翻譯英文 ，丁翻譯徳文。所需總時間最少為：55 例：求如下系數(shù)矩陣所對應(yīng)的指派問題： 解：按第一、二步將系數(shù)矩陣進(jìn)行變換和試指派：56 這里獨(dú)立 0 元素的個數(shù) m = 4 5 ；所以解題沒有完 成，這時，應(yīng)按以下步驟進(jìn)行： 第三步：作最少的直線覆蓋所有的 0 元素，以確定該 系數(shù)矩陣中能找到最多的獨(dú)立 0 元素。為此按以下步 驟進(jìn)行：57（1）對沒有 的行打 ；（2）對已打 的行中包含有 0 元素的列打 ；（3）再對有打 的列中含有的 的行打 ；（4）重復(fù)（2）、（3）直到得不出新的打 的行、 列為止； （5）對沒有打 的行畫一橫線，

19、對打 的列畫一縱 線，這就得到了能夠覆蓋所有 0 元素的最少直線數(shù)。 令這直線數(shù)為 l 。若 l n ，則說明必須再變換當(dāng) 前的系數(shù)矩陣，才能找到 n 個獨(dú)立的 0 元素，為此轉(zhuǎn) 第四步；若 l = n ，應(yīng)回到第二步，另行試探。58 在例中，對由第一、二步所求得的矩陣進(jìn)行第 三步的工作： l = 4 5 ，所以應(yīng)繼續(xù)對上述矩陣進(jìn)行變換，轉(zhuǎn) 第四步；59 第四步：對于上述矩陣進(jìn)行行變換的目的是增加 0 元素。為此，在沒有被直線覆蓋的部分中找出最小元素， 然后在打 行各元素中都減去該最小元素，而在打 列的各元素中都加上該最小元素，以保證原來的 0 元 素的位置在經(jīng)過變換之后仍然還是 0 元素。這樣得到 的新系數(shù)矩陣與原問題具有相同最優(yōu)解。由此若能得 到 n 個獨(dú)立的 0 元素，則已得到最優(yōu)解；否則返回到 第三步重復(fù)進(jìn)行。 對于上例，我們繼續(xù)進(jìn)行計算如下：6061 這時我們已經(jīng)找到了 n 個不同行不同列的 0 元素 ，