運(yùn)籌學(xué)第五章整數(shù)規(guī)劃

1、薛威薛威2012015 5年年4 4月月運(yùn)籌學(xué)運(yùn)籌學(xué)第五章整數(shù)規(guī)劃第五章整數(shù)規(guī)劃 Textmasterformate durch Klicken bearbeiten Zweite EbeneDritte Ebene Vierte Ebene Fnfte Ebene【教學(xué)目的】【教學(xué)目的】 通過(guò)本單元的通過(guò)本單元的學(xué)習(xí)，使學(xué)習(xí)，使學(xué)生掌握整數(shù)問(wèn)題的概念，學(xué)生掌握整數(shù)問(wèn)題的概念，類型和模型的建立，能夠運(yùn)用分支界定法求解一般整數(shù)類型和模型的建立，能夠運(yùn)用分支界定法求解一般整數(shù)問(wèn)題，并掌握問(wèn)題，并掌握0-10-1整數(shù)規(guī)劃和指派問(wèn)題的基本求解方法。整數(shù)規(guī)劃和指派問(wèn)題的基本求解方法?！窘虒W(xué)重點(diǎn)教學(xué)重點(diǎn)】

2、建立整數(shù)規(guī)劃模型建立整數(shù)規(guī)劃模型掌握分支界定法掌握分支界定法【教學(xué)難點(diǎn)教學(xué)難點(diǎn)】0-10-1整數(shù)規(guī)劃、指派整數(shù)規(guī)劃、指派問(wèn)題的求解問(wèn)題的求解第五章整數(shù)規(guī)劃 整數(shù)規(guī)劃問(wèn)題介紹 整數(shù)規(guī)劃算法分枝定界法 整數(shù)規(guī)劃算法割平面法 0-1整數(shù)規(guī)劃 指派問(wèn)題(分派問(wèn)題)線性規(guī)劃模型：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx實(shí)際問(wèn)題要求xi為整數(shù)！如機(jī)器的臺(tái)數(shù)，人數(shù)等整數(shù)規(guī)劃線性整數(shù)規(guī)劃非線性整數(shù)規(guī)劃簡(jiǎn)稱整數(shù)規(guī)劃整數(shù)線性規(guī)劃問(wèn)題純整數(shù)規(guī)劃的數(shù)學(xué)模型：nnxcxcxcz2211maxmnmnmm

3、nnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx取整數(shù)nxxx,210-1規(guī)劃的數(shù)學(xué)模型：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx1 ,0,21nxxx整數(shù)規(guī)劃純整數(shù)規(guī)劃01規(guī)劃混合型整數(shù)規(guī)劃例1.勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子售價(jià)30元/個(gè)，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4個(gè)小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3個(gè)小時(shí)，油漆工1小時(shí)。該廠每月可用木工

4、工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷(xiāo)售收入最大？每月的銷(xiāo)售收入生產(chǎn)椅子的數(shù)量生產(chǎn)桌子的數(shù)量解：設(shè)Zxx21,213050maxxxZ求12034.21xxt s50221 xx0,21xx為整數(shù)21,xx純整數(shù)規(guī)劃例2.某服務(wù)部門(mén)各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)見(jiàn)下表。按規(guī)定，服務(wù)員連續(xù)工作8小時(shí)（即4個(gè)時(shí)段）為一班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門(mén)服務(wù)員總數(shù)最少。 時(shí)段12345678服務(wù)員最少數(shù)目10891113853解 設(shè)在第j時(shí)段開(kāi)始時(shí)上班的服務(wù)員人數(shù)是xj。由于第j時(shí)段開(kāi)始時(shí)上班的服務(wù)員將在第（j+1）時(shí)段結(jié)束時(shí)下班，所以決策變量只

5、需考慮x1，x2 ，x3 ，x4 ，x5。該問(wèn)題的數(shù)學(xué)模型是，且均為整數(shù)035813119810. .min5, 4, 3, 2, 15545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxz最?。渴箍偨ㄔO(shè)費(fèi)和總運(yùn)輸費(fèi)的需求，又建廠，使得既滿足各地。試決定應(yīng)在哪些地方費(fèi)為的單位運(yùn)運(yùn)往銷(xiāo)地。從工廠，其銷(xiāo)售量分別為品需要銷(xiāo)售這種產(chǎn)，個(gè)地點(diǎn)。又有，分別是建設(shè)費(fèi)，生產(chǎn)能力分別是它們生產(chǎn)同一種產(chǎn)品，地點(diǎn)有地點(diǎn)建廠，可供選擇的例：某公司計(jì)劃在幾個(gè)ijjinnmmmcBAbbbBBBnfffaaaAAA2121212121,解：的運(yùn)量運(yùn)往商店表示工廠

6、設(shè)jiijBAx則總運(yùn)費(fèi)為mi 1nj 1ijijxc個(gè)地點(diǎn)建廠不在第個(gè)地點(diǎn)建廠在第設(shè)iiyi01則總建廠費(fèi)為miiiyf1混合型整數(shù)規(guī)劃數(shù)學(xué)模型：111minmnmijijiiijiZc xy f 0ijx1 ,0iymiaxt sinjij,2 , 1.1總結(jié)整數(shù)規(guī)劃的可行域包含在其對(duì)應(yīng)的一般線性規(guī)劃可行域之內(nèi)；整數(shù)規(guī)劃的最優(yōu)解可能不是其對(duì)應(yīng)的一般線性規(guī)劃的頂點(diǎn)；整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其對(duì)應(yīng)的線性規(guī)劃的最優(yōu)解。分支定界法1、基本思路 且為整數(shù)且為整數(shù))2 . 1( , 0)2 . 1( )IP(min11mjxmibxaxczjnjijijnjjj考慮純整數(shù)問(wèn)題：考慮純整數(shù)問(wèn)題：整數(shù)問(wèn)題

7、的松弛問(wèn)題： ),2 . 1( , 0),2 . 1( )LP(min11mjxmibxaxczjnjijijnjjj （1）先不考慮整數(shù)約束，解( IP )的松弛問(wèn)題( LP )，可能得到以下情況之一： 若( LP )沒(méi)有可行解，則( IP )也沒(méi)有可行解，停止計(jì)算。 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。 為討論方便，設(shè)( LP )的最優(yōu)解為： 不不全全為為整整數(shù)數(shù)其其中中目目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值為為), 2 , 1(.)0 , 0 ,( )0

8、(21)0(mibzbbbbXiTmr （2）分支： 在在( LP )的最優(yōu)解的最優(yōu)解 X(0)中，任選一個(gè)不符合整數(shù)條件的變量，中，任選一個(gè)不符合整數(shù)條件的變量，例如例如xr= br （不為整數(shù)），以（不為整數(shù)），以br表示不超過(guò)表示不超過(guò)br的最大整數(shù)。的最大整數(shù)。構(gòu)造兩個(gè)約束條件構(gòu)造兩個(gè)約束條件 xr br 和和 xr br1 將這兩個(gè)約束條件分別加入問(wèn)題將這兩個(gè)約束條件分別加入問(wèn)題( IP ) ，形成兩個(gè)子問(wèn)題，形成兩個(gè)子問(wèn)題( IP1)和和( IP2 ) ，再，再解這兩個(gè)子問(wèn)題的松弛問(wèn)題解這兩個(gè)子問(wèn)題的松弛問(wèn)題( LP1)和和( LP2) 。 （3）定界：記( IP )的目標(biāo)函數(shù)最優(yōu)

9、值為 ,以 作為 的下界，記為 。令 ，則有)0(zz zzzz *z)0(z*z （4）修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。 在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最小者作為新的下界； 從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最小者作為新的上界。 （5）比較與剪枝 ： 各分枝的目標(biāo)函數(shù)值中，若有大于 者，則剪掉此枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。 如此反復(fù)進(jìn)行，直到得到如此反復(fù)進(jìn)行，直到得到 為止，為止，即得最優(yōu)解即得最優(yōu)解 X* 。2、例題 max Z=40X1 + 90X2 9X1+7X2 567X1+20X2 70X1 , X2 0 X1 , X2為為整數(shù)整數(shù)解：先解該整數(shù)

10、規(guī)劃對(duì)應(yīng)的松弛問(wèn)題解：先解該整數(shù)規(guī)劃對(duì)應(yīng)的松弛問(wèn)題X* =4.8091.817Z* =355.890， 上界上界Z* 選選X1分枝分枝問(wèn)題問(wèn)題(2)(1)X1 4問(wèn)題問(wèn)題(3)(1)X1 5問(wèn)題問(wèn)題2解為解為X1 =4X2 =2.1Z=349.0解為解為X1 =5X2 =1.571Z=341.39問(wèn)題問(wèn)題3選選(2)繼續(xù)分枝繼續(xù)分枝問(wèn)題問(wèn)題(4)(2)X2 2問(wèn)題問(wèn)題(5)(2)X2 3分支定界過(guò)程分支定界過(guò)程(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7

11、)無(wú)解無(wú)解X1 4X1 5X2 2X2 1X2 2X2 3:0L討論松弛問(wèn)題無(wú)最優(yōu)解，、01L無(wú)最優(yōu)解則)(IP結(jié)束002010),*,*(*2zxxxXon最優(yōu)值，、最優(yōu)解為整數(shù)解0*) 1 ( X的最優(yōu)解為，則)(*0IPX結(jié)束中至少有一個(gè)是分?jǐn)?shù)，0*)2(X是分?jǐn)?shù)設(shè)01*x：分枝x1x*01x1x*01+1:1L子問(wèn)題無(wú)最優(yōu)解，、11L剪枝1112111),*,*(*2zxxxXn最優(yōu)值，、最優(yōu)解為整數(shù)解1*) 1 ( X為下界1,z關(guān)閉中至少有一個(gè)是分?jǐn)?shù)：1*)2(X繼續(xù)分枝:2L子問(wèn)題總結(jié)割平面法割平面法的基本思想： 若整數(shù)規(guī)劃IP的松弛規(guī)劃L0的最優(yōu)解不是整數(shù)解，對(duì)L0增加一個(gè)約束

12、條件，得線性規(guī)劃L1，此過(guò)程縮小了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的同時(shí)，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃IP的解均在L1中，若L1的最優(yōu)解為整數(shù)解，則得IP的最優(yōu)解。若L1的最優(yōu)解不是整數(shù)解，重復(fù)以上步驟，由于可行解域在不斷縮小，且保留IP所有的整數(shù)解，總可以在有限次后得到IP的最優(yōu)解.原最優(yōu)解要被割去可行域中割去一部分，割去部分不含整數(shù)解，割平面法原理：計(jì)算步驟：（1）用單純形法求解( IP )對(duì)應(yīng)的松弛問(wèn)題( LP )： 若( LP )沒(méi)有可行解，則( IP )也沒(méi)有可行解，停止計(jì)算。 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( I

13、P )的最優(yōu)解，停止計(jì)算。 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。 （2）從(LP)的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量xr,將最優(yōu)單純形表中該行的系數(shù) 和 分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程： 1rnmjjrjfxf rja 的小數(shù)部分的小數(shù)部分rjarb 的小數(shù)部分的小數(shù)部分rb （3）將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用單純形法求出新的最優(yōu)解，返回1。例例：用割平面法求解整數(shù)規(guī)劃問(wèn)題用割平面法求解整數(shù)規(guī)劃問(wèn)題 且為整數(shù)且為整數(shù)0,023623 max2121212xxxxxxxZ解

14、：解：增加松弛變量增加松弛變量x3和和x4 ，得到，得到(LP)的初始單純形表和最的初始單純形表和最優(yōu)單純形表：優(yōu)單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00 -1/4 -1/4 此題的最優(yōu)解為：此題的最優(yōu)解為：X= (1 , 3/2) Z = 3/2 但不是整數(shù)最但不是整數(shù)最優(yōu)解，引入割平面。以優(yōu)解，引入割平面。以x2 為源行生成割平面。為源行生成割平面。 此題的最優(yōu)解為：此題的最優(yōu)解為：X= (1 , 3/2) Z = 3/2

15、但不是整數(shù)最但不是整數(shù)最優(yōu)解，引入割平面。以優(yōu)解，引入割平面。以x2 為源行生成割平面，由于為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 生成割平面的條件為生成割平面的條件為: Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00 -1/4 -1/421414143 xx0-1整數(shù)規(guī)劃10,64342422.253max3213221321321321或例：求xxxxxxxxxxxxxt sxxxZ枚舉法：檢驗(yàn)可行解：32次運(yùn)算計(jì)算目標(biāo)函數(shù)值：8次（x1 x2 x3)Z值 約束條件（1）（2）（3）（4）過(guò)濾條件（

16、0 0 0）（0 0 1）（0 1 0）（1 0 0）（1 0 1）（1 1 0）（1 1 1）0-2531836 Z0Z5運(yùn)算次數(shù)：21（0 1 1）01 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xi 只取兩個(gè)值0或1，一般的解法為隱枚舉法。是否能對(duì)上述方法進(jìn)行優(yōu)化，使得運(yùn)算量進(jìn)一步減少呢？根據(jù)上述算法的特點(diǎn)，可以按目標(biāo)函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以使最優(yōu)解盡可能早出現(xiàn)。試用改進(jìn)的算法求解下題：1234123412341241234min3721. .64835,01zxxxxxxxxst xxxxxxxx x x x 或 在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n 項(xiàng)不同的任

17、務(wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。指派問(wèn)題設(shè)決策變量設(shè)決策變量 1 分配第分配第i 個(gè)人去做第個(gè)人去做第j 件工作件工作 xij = 0 相反相反 ( i, j=1.2. n )其數(shù)學(xué)模型為：其數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或指派問(wèn)題的性質(zhì)定理：定理：對(duì)于指派

18、問(wèn)題，成本矩陣的任一對(duì)于指派問(wèn)題，成本矩陣的任一行行(或列或列)減去減去(或加上或加上)一個(gè)相同的數(shù)得到一個(gè)相同的數(shù)得到的新指派問(wèn)題與原問(wèn)題同解的新指派問(wèn)題與原問(wèn)題同解解題步驟： 指派問(wèn)題是0-1 規(guī)劃的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃的解法去求解，但運(yùn)算繁瑣。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法(匈牙利數(shù)學(xué)家D.Konig提出) ，即系數(shù)矩陣中獨(dú)立 0 元素的最多個(gè)數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。 第一步：變換指派問(wèn)題的系數(shù)(也稱效率)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 (1) 從（cij）的每行元素都減去該行的最小元素； (2)

19、 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。 第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為： (1)從只有一個(gè)0元素的行(列)開(kāi)始，給這個(gè)0元素加圈，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 (2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。 (4)若仍有沒(méi)有

20、劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。 （5）若 元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有0元素。 (1)對(duì)沒(méi)有的行打號(hào)； (2)對(duì)已打號(hào)的行中所有含元素的列打號(hào)； (3)再對(duì)打有號(hào)的列中含 元素的行打號(hào)； (4)重復(fù)(2)，(3)直到得不出新的打號(hào)的行、列為止； (5)對(duì)沒(méi)有打號(hào)的行畫(huà)橫線

21、，有打號(hào)的列畫(huà)縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。l 應(yīng)等于m，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)，另行試指派；若 lm n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后打各行都減去這最小元素；打各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。 例：求費(fèi)用矩陣為右表的 指派問(wèn)題的最優(yōu)解費(fèi)用工作人甲乙丙丁戊A B C D E12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10

22、4 10 7 10 661071041066141512141217766698979712C第一步：每行減去最小元素，每列減掉最小元素;第二步：對(duì)零元素畫(huà)圈打;第三步: 劃線覆蓋零元素;61071041066141512141217766698979712C-7-6-7-6-426360400895751000003220205得4個(gè)，且不存在沒(méi)打的0502 0 2230 0 00 10 5 7 5980 0 4063 6 2第四步：在沒(méi)有被直線復(fù)蓋的元素中找出最小元素，讓打號(hào)的列加上這個(gè)元素，打號(hào)的行減去這個(gè)元素。70202430000835311800404140匈牙利法的具體步驟：第一

23、步：變換指派問(wèn)題的費(fèi)用矩陣，使其在各行各列都出現(xiàn)0元素；方法：首先每行元素減去該行的最小元素，然后每列減去該列的最小元素第二步：進(jìn)行試指派（畫(huà)）方法：從含0元素最少的行或列開(kāi)始，圈出一個(gè)0元素，用 表示，然后劃去該所在的行和列中的其余0元素，用表示，依次類推。若矩陣中的的個(gè)數(shù)等于n，則得最優(yōu)解若矩陣中的的個(gè)數(shù)n，則進(jìn)行第三步第三步：做能復(fù)蓋所有0元素的最小直線集合：1）對(duì)沒(méi)有的行打號(hào)2）對(duì)打號(hào)的行上所有0元素的列打號(hào)3）再對(duì)打號(hào)的列上所有的行打號(hào)4）重復(fù)以上步驟直到得不出新的打號(hào)為止5）對(duì)沒(méi)有打號(hào)的行畫(huà)橫線，所有打號(hào)的列畫(huà)縱線，所得到的直線既是復(fù)蓋所有0元素的最小直線集合第四步：在沒(méi)有被直線復(fù)

24、蓋的元素中找出最小元素，讓打號(hào)的列加上這個(gè)元素，打號(hào)的行減去這個(gè)元素。取整數(shù)求例21332142132121,0,5.1645.1432.2030maxxxxxxxxxxxxxtsxxz混合型0,5.1645.1432.2030max3321421321210 xxxxxxxxxxtsxxzL ；松弛問(wèn)題:0L155, 00, 5 . 25 . 304321zxxxx，x13x14:1L:2LL0的最優(yōu)單純型表：x1x2x3x4常數(shù)項(xiàng)檢00-5-5Z-155x2012/5-1/55/2x110-1/103/107/20,35.1645.1432.2030max33211421321211xxxxxxxxxxxtsxxzL ；隨堂練習(xí):0L155, 00, 5 . 25 . 304321zxxxx，x13x14:1L3440, 0,350,6173154321zxxxxx，:2L