3.2整數(shù)規(guī)劃的建模ppt課件

1、第八章 整數(shù)規(guī)劃在線性規(guī)劃問題中，有一類特殊的情形，稱為整數(shù)規(guī)劃，這類問題的最優(yōu)解必須是整數(shù)。如求解完成工作所需的最少人數(shù)，或加工一批零件所需機(jī)器的臺(tái)數(shù)。由于這類問題并不是由簡(jiǎn)單的“四舍五入法或“去零化整法就能求得最優(yōu)解，因此有必要對(duì)它作專門的討論。 本章包含四部分的內(nèi)容：第一部分：整數(shù)規(guī)劃的建摸第二部分：整數(shù)規(guī)劃的應(yīng)用0-1型整數(shù)規(guī)劃）第三部分：分支定界法第四部分：指派問題1、整數(shù)規(guī)劃的建摸整數(shù)規(guī)劃問題的數(shù)學(xué)模型和線性規(guī)劃基本相同，只是約束條件有所不同，下面我們以例題說明整數(shù)規(guī)劃的建模。1、問題的提出例1 某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表，問兩

2、種貨物各托運(yùn)多少箱可獲利潤(rùn)最大？ 貨物體積每箱（m3)重量每箱（m3)利潤(rùn)每箱（百元）甲 5220乙4510托運(yùn)限制2413解：設(shè)x1,x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)應(yīng)為大于或等于零的整數(shù)），這是一個(gè)整數(shù)規(guī)劃問題，數(shù)學(xué)模型如下211020 xxMaxz取整數(shù)21212121,0,13522445xxxxxxxx從上式可見，它和線性規(guī)劃問題的區(qū)別僅在于 x1,x2為整數(shù)這一條件。如果我們暫不考慮 這一條件，很容易求得相應(yīng)線性規(guī)劃問題的最優(yōu)解為 ，但不滿足整數(shù)要求，如按四舍五入取 ，又破壞了 這一條件，如舍去尾數(shù)取x1=4,x2=0 雖然滿足了約束條件，但此時(shí)z=80，不是最優(yōu)解，因?yàn)楫?dāng)時(shí)x1

3、=4,x2=1，既滿足約束條件，且z=9080。由此可見整數(shù)規(guī)劃問題并非通過“化整求其最優(yōu)解。21,xx21,xx96, 0, 8 . 421Maxzxx96, 0, 8 . 421Maxzxx0, 521xx244521xx從以上的例題可以看出：由于相應(yīng)的線性規(guī)劃的可行域包含了其整數(shù)規(guī)劃的可行解，就可有如下的性質(zhì)：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值。 2、定義 規(guī)劃中的變量部分或全部限制為整數(shù)時(shí)，稱為整數(shù)規(guī) 劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù) 線性規(guī)劃。 3、整數(shù)規(guī)劃分類 如不加特殊說明，一般指整數(shù)線性規(guī)劃。

4、對(duì)于整數(shù)線性規(guī) 劃模型大致可分為兩類： （1） 變量全限制為整數(shù)的，稱純完全整數(shù)規(guī)劃。 （2變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。 4、整數(shù)規(guī)劃特點(diǎn) 整數(shù)規(guī)劃標(biāo)準(zhǔn)形式實(shí)際為整數(shù)線性規(guī)劃） AX=b，X0，CTX=min，xj為整數(shù)j=1，n） (1) （1原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后， 其整數(shù)規(guī)劃解出現(xiàn)下述情況； 原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 整數(shù)規(guī)劃無(wú)可行解。 有可行解當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。 原線性規(guī)劃為： 2x1+4x2=6，X0，CTX=x1+x2=min 其最優(yōu)實(shí)數(shù)解為：x1=0，x2=3/2，min CTX =3/2。 若

5、限制整數(shù)則得：x1=1，x2=1，min CTX =2。 5、求解方法分類： （1 割平面法主要求解純整數(shù)線性規(guī)劃 （ 2 分枝定界法可求純或混合整數(shù)線性規(guī)劃 （3 隱枚舉法求解“01整數(shù)規(guī)劃： 過濾隱枚舉法； 分枝隱枚舉法 （4 匈牙利法解決指派問題（“01規(guī)劃特殊情形）。 （ 5蒙特卡洛法求解各種類型規(guī)劃。2、整數(shù)規(guī)劃的應(yīng)用0-1型整數(shù)規(guī)劃）在整數(shù)規(guī)劃中有一類特殊的情形，它的變量xi僅能取0或1，這時(shí)的xi稱為0-1變量，這類問題也就稱為0-1型整數(shù)規(guī)劃。2、1 0-1型數(shù)規(guī)劃的建模0-1變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài)或者決策時(shí)是否采取某個(gè)特定方案。當(dāng)問題含有多項(xiàng)要

6、素，而每項(xiàng)要素皆有兩種選擇時(shí)，也可用0-1變量來(lái)描述 設(shè)某問題有有限要素E1,E2, ,E n，其中每項(xiàng)Ej有兩種選擇Aj和 (j=1.2.-,n)那么：)(01PPPx即采取時(shí)不采取方案時(shí)采取方案jAjAjA)2 , 1(01njAEAExjjjjj時(shí)選擇時(shí)選擇2、1、2下面討論0-1整數(shù)規(guī)劃的幾種應(yīng)用實(shí)例。 1相互排斥的計(jì)劃問題例3 某超市連鎖店的布點(diǎn)問題。某超市連鎖店在分析某城市的特征后，將該城市劃分成四個(gè)區(qū)域：東片、西片、南片、北片。在四個(gè)區(qū)域中共確定了10個(gè)連鎖店的備選點(diǎn)，記作 在連鎖店選擇時(shí)需考慮以下限制： 1021,sss1021,sss東片的三個(gè)點(diǎn) 中,至少應(yīng)選擇一個(gè);西片的兩

7、個(gè)點(diǎn) 中，應(yīng)恰好選擇一個(gè)；南片的四個(gè)點(diǎn) 中，最多只能選三個(gè)；北片只有一個(gè)備選點(diǎn) ，可選可不選。321,sss54,ss9876,ssss10s如果選中 點(diǎn)，其投資為 元，每年的預(yù)期收益為 元?，F(xiàn)要求總投資不超過Z元，問應(yīng)選擇哪些備選點(diǎn)，既可滿足限制，又可使每年的總收益最大。試建立這個(gè)問題的0-1型整數(shù)規(guī)劃數(shù)學(xué)模型。解：設(shè) 則可建立如下0-1型整數(shù)規(guī)則數(shù)學(xué)模型： jsjzjp點(diǎn)未被選中點(diǎn)被選中jjjssx,0, 1101jjjxpMaxz10,2,1,10311101987654321jxzxzssxxxxxxxjjjj或例4 某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油，使總的鉆探費(fèi)

8、用為最小。若10個(gè)井位的代號(hào)為 ，相應(yīng)的鉆探費(fèi)用為 ，并且井位選擇上要滿足下列限制條件：或選擇S1和S7，或選擇S8；選擇了S3或S4就不能選S5，反之，選了S5，則不能選S3或S4；在S5S8中最多選兩個(gè)。建立這個(gè)問題的0-1型整數(shù)規(guī)劃模型1021,SSS1021,ccc解：101jjjxcMinz井位不選井位選擇jjjjjSSxxxxxxxxxxxxxx01211115876554538781101例5指派問題 有 n 項(xiàng)不同的任務(wù)，恰好 n 個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把 n 項(xiàng)任務(wù)指派給 n 個(gè)人，

9、使得完成 n 項(xiàng)任務(wù)的總的效率最高，這就是指派問題例有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。 工 作工 人ABCD甲15182124乙19232218丙26171619丁19212317解：引入解：引入01變量變量 xij，并令，并令 xij = 1(當(dāng)指派第當(dāng)指派第 i人去完成第人去完成第j項(xiàng)工作時(shí)項(xiàng)工作時(shí))或或0當(dāng)不指派第當(dāng)不指派第 i人去完成第人去完成第j項(xiàng)工作時(shí)項(xiàng)工作時(shí))這可以表示為一個(gè)這可以表示為一個(gè)0-1整數(shù)規(guī)劃問題：整數(shù)規(guī)劃問題： Minz=15x11+18x12+21x13+24x14+19

10、x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作丁只能干一項(xiàng)工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42=

11、1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 為為0-1變量，變量，i,j = 1,2,3,42相互排斥約束條件問題例6 在例1中，關(guān)于貨運(yùn)的體積限制為。5X1+4X224如設(shè)貨運(yùn)有車運(yùn)和船運(yùn)兩種方式，上面的體積限制條件是針對(duì)車運(yùn)的 ， 如 用 船 運(yùn) 時(shí) 體 積 限 制 條 件 為7X1+3X245，為把這兩個(gè)限制條件統(tǒng)一在一個(gè)問題中，我們引入0-1變量，令這樣數(shù)學(xué)模型的約束條件就應(yīng)寫為：其中M為一充分大數(shù)，當(dāng) y=0時(shí)，上面

12、兩個(gè)約束條件實(shí)際上就是第一個(gè)在起作用，當(dāng)y=1時(shí)第一式自然滿足，起作用的僅是第二式。當(dāng)采用船運(yùn)方式當(dāng)采用車運(yùn)方式10yMyxxyMxx)1 (4537244521212、2 0-1型整數(shù)規(guī)劃的解法 例 求解0-1整數(shù)規(guī)劃 32173xxxMaxz10,03506202232121321321或xxxxxxxxxxx (3.5) 解：先考慮可能的解的組合，共23=8個(gè)，列于表3.3中。先分析第一個(gè)解0，0，0），經(jīng)檢查為可行解，而其目標(biāo)函數(shù)值為0，則考察其它的解，只有其目標(biāo)函數(shù)值滿足 （3、6）時(shí)，才檢查其是否可行，否則不予檢查。我們把條件3.6稱為過濾條件。再分析解0，0，1），由于其目標(biāo)函數(shù)

13、值為-1，不滿足過濾條件3.6），故不予檢查。073321xxx分析解0，1，0），其目標(biāo)函數(shù)值為7，故要檢查，經(jīng)檢查不滿足約束條件，故過濾條件不予修改。類似于上述分析，直到將所有的解均檢查完畢，最后得到結(jié)論，最優(yōu)解為1，1，1），最優(yōu)目標(biāo)函數(shù)值為9。我們將上述求解方法稱為隱枚舉法。(二二)、簡(jiǎn)單隱枚舉法、簡(jiǎn)單隱枚舉法(max)原則：原則：(1)、用試探法，求出一個(gè)可行解，以它的目、用試探法，求出一個(gè)可行解，以它的目標(biāo)值作為當(dāng)前最好值標(biāo)值作為當(dāng)前最好值Z0(2)、增加過濾條件、增加過濾條件Z Z0(3)、將、將xi 按按ci由小由小大排列大排列例：例：maxZ = 3x1 -2x2+5x3x1

14、 +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 ) 解解(x2 x1 x3 ) 目標(biāo)值目標(biāo)值 Z0 當(dāng)前最好當(dāng)前最好值值 (0 ,0 ,0) 0 5 (0 ,1 ,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1 ,0) 1 (1 ,1 ,1) 6 10/3 ，所以優(yōu)先選擇B2再進(jìn)行分枝。分別加上約束條件X

15、223/9和X223/9+1，將分枝為和兩個(gè)子問題，繼續(xù)求解。按照這一方法不斷分枝和定界，可行域不斷縮小，上界不斷減少，下界逐漸增大，當(dāng)上界和下界相等時(shí)，便得到最優(yōu)整數(shù)解。本題有兩個(gè)最優(yōu)解，分別為X1=3,X2=1和 X1=2,X2=2 上述分枝定界法的求解過程還可用圖來(lái)表示 4、指數(shù)問題在整數(shù)規(guī)劃中還有一類特殊的情形就是指派問題。指派問題在現(xiàn)實(shí)生活中經(jīng)常遇到，例如：有若干項(xiàng)工作需要分配給若干人來(lái)完成，由于每個(gè)人的專長(zhǎng)不同，所以完成工作所需的時(shí)間也不同，那么就產(chǎn)生了如何合理安排哪個(gè)人去完成哪項(xiàng)工作，才能使總效率最高，這是一類典型的指派問題。由此引伸到學(xué)校如何安排班級(jí)在各教室上課，以及工程選擇投

16、標(biāo)者承包等。這類問題的共同要求就是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。4、1指派問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型指派問題標(biāo)準(zhǔn)形式是：有n個(gè)人和n件事，已知第I個(gè)人做第j件事的費(fèi)用為cij,I,j=1,2, ncij還可表示成本、時(shí)間等含義），要求確定人與事之間的一一對(duì)應(yīng)的指派方案，使完成n件事的總費(fèi)用最少。為了建立上述指派問題的數(shù)學(xué)模型，引入個(gè)0-1變量：這樣它的數(shù)學(xué)模型為：模型中，約束條件3.7表示每件事必有且只有一個(gè)人去做，約束條件3.8表示每個(gè)人必做且只做一件事。件事個(gè)人做第若不指派第件事個(gè)人做第若指派第jijixij01 ninjijijxcMinz11njixnixnjxi

17、jnjijniij2, 1,10)8 .3(2, 11)7 .3(2, 1111或指派問題的可行解可用矩陣表示：解矩陣的每行每列元素中都有且只有一個(gè)1，以滿足約束條件。指派問題有n！個(gè)可行解。下面以例題說明指派問題的建模。nnnnnnnnijxxxxxxxxxxx212222111211)(下面以例題說明指派問題的建模。例 某商業(yè)公司計(jì)劃開辦五家新商店。為了盡早建成營(yíng)業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai對(duì)新商店Bj的建造費(fèi)用的報(bào)價(jià)萬(wàn)元為Cij，見表所示。商業(yè)公司應(yīng)當(dāng)對(duì)5家建筑公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？B1B2B3B4B5A14871512A2791714

18、10A3691287A46714610A56912106這是一個(gè)標(biāo)準(zhǔn)的指派問題。若設(shè)0-1變量則問題的數(shù)學(xué)模型為 )5 , 2 , 1,(01jiBABAxjijiij時(shí)不承建當(dāng)時(shí)承建當(dāng)55541211515161084xxxxxcMinzijijij52,1,1052,1152,115151jixixjxijjijiij或4、2指派問題的匈牙利解法 從指派問題的數(shù)學(xué)模型可以看出，指派問題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問題的特例，即 ，當(dāng)然更是一個(gè)整數(shù)規(guī)劃問題，所以指派問題可用隱枚舉法、表上作業(yè)法和分枝定界法求解。但是我們可以利用指派問題數(shù)學(xué)模型的特點(diǎn)，找到更加簡(jiǎn)便的方法，這就是由匈牙利數(shù)學(xué)

19、家康尼格D.knig提出的匈牙利解法。1,jibamn4、2、1匈牙利解法的思想基礎(chǔ) 從指派問題的系數(shù)矩陣 的某行某列各元素中分別減去一個(gè)常數(shù)k，得到的新矩陣 所代表的新指派問題與原指派問題有相同最優(yōu)解。nnijc)(nnijc )(例9 有一份中文說明書，要將其翻譯成三種不同的文字，三位不同人翻譯三種不同的文字所花的時(shí)間見表。試確定翻譯的最佳指派方案。英文中文德文甲425乙463丙447解：1.先對(duì)時(shí)間矩陣的各行減去最小值。 2確定獨(dú)立0元素，即在每行和每列中各圈出一個(gè)“0”。當(dāng)n較小時(shí)，可用觀察法、試探法找出n個(gè)獨(dú)立0元素，當(dāng)n較大時(shí)，可按以下步驟進(jìn)行：300031302432744364

20、524（1從只有一個(gè)0素的行列開場(chǎng)，給這個(gè)0元素加圈，稱為獨(dú)立0元素，記作，這表示對(duì)這行所代表的“人只翻譯該列所對(duì)應(yīng)的語(yǔ)種，然后劃去所在列或行的其他0元素，記作 ，這表明該行的“人得到任務(wù)后，該人則不能再翻譯其他語(yǔ)種。（2再在剩下的元素中，從只有一個(gè)0元素的行列），給這個(gè)0元素加圈。重復(fù)上述過程，直到所有0元素都被圈出或劃掉。如果獨(dú)立元素有n個(gè)，則表明已可確定最優(yōu)指派方案。此時(shí)令矩陣中和獨(dú)立0元素相對(duì)應(yīng)位置上的元素為1，其余元素為0，即可得最優(yōu)矩陣。按此步驟，本例可得獨(dú)立0元素如下： 從而得指派方案：即：甲翻譯日文乙翻譯德文丙翻譯英文所花總時(shí)間為：2+3+4=9。001100010是不是所有的

21、問題都能像例9那樣，方便地獲得獨(dú)立的0元素呢？現(xiàn)在我們?cè)賮?lái)看一則例子，以進(jìn)一步說明匈牙利算法的詳細(xì)解題步驟。用匈牙利算法求解上上例所對(duì)應(yīng)的問題的最優(yōu)解。解：已知例指派問題的系數(shù)矩陣為：610129610614767812961014179712157841先對(duì)各行元素分別減去本行的最小元素，然后對(duì)各列也如此，即此時(shí)，中各行和各列都已出現(xiàn)0元素，且沒有負(fù)數(shù)。 CC043204050012320377108110300463040810126303710208113402確定中的獨(dú)立0元素，即： 3由于本例中只有4個(gè)獨(dú)立0元素，少于系數(shù)矩陣階數(shù)n=5，表示還不能確定最優(yōu)指派方案。此時(shí)，需要確定能覆蓋所有0元素的最少直線數(shù)目的直線集合?？砂聪旅娌襟E進(jìn)行：1對(duì)沒有的行打“”；（2在已打“”的行中，對(duì)0所在列打“”；（3在已打“”的列中，對(duì)所在行打“”；（4反復(fù)2和3），直到再也不能找到可以打“”的行或列為止；（5對(duì)沒有打“”的行畫一橫線，對(duì)打“”的列畫一垂線，這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合。本例可得下面矩陣： 4在未被直線覆蓋的元素中找出一個(gè)最小元素，對(duì)未被覆蓋元素所在行中各元素都減去這一最小元素，這樣勢(shì)