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

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

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

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

4、對于整數(shù)線性規(guī) 劃模型大致可分為兩類： （1） 變量全限制為整數(shù)的，稱純完全整數(shù)規(guī)劃。 （2變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。 4、整數(shù)規(guī)劃特點 整數(shù)規(guī)劃標準形式實際為整數(shù)線性規(guī)劃） AX=b，X0，CTX=min，xj為整數(shù)j=1，n） (1) （1原線性規(guī)劃有最優(yōu)解，當自變量限制為整數(shù)后， 其整數(shù)規(guī)劃解出現(xiàn)下述情況； 原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 整數(shù)規(guī)劃無可行解。 有可行解當然就存在最優(yōu)解），但最優(yōu)解值變差。 原線性規(guī)劃為： 2x1+4x2=6，X0，CTX=x1+x2=min 其最優(yōu)實數(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ī)劃的應用0-1型整數(shù)規(guī)劃）在整數(shù)規(guī)劃中有一類特殊的情形，它的變量xi僅能取0或1，這時的xi稱為0-1變量，這類問題也就稱為0-1型整數(shù)規(guī)劃。2、1 0-1型數(shù)規(guī)劃的建模0-1變量作為邏輯變量，常被用來表示系統(tǒng)是否處于某個特定狀態(tài)或者決策時是否采取某個特定方案。當問題含有多項要

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

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

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

9、使得完成 n 項任務的總的效率最高，這就是指派問題例有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應如何指派工作，才能使總的消耗時間為最少。 工 作工 人ABCD甲15182124乙19232218丙26171619丁19212317解：引入解：引入01變量變量 xij，并令，并令 xij = 1(當指派第當指派第 i人去完成第人去完成第j項工作時項工作時)或或0當不指派第當不指派第 i人去完成第人去完成第j項工作時項工作時)這可以表示為一個這可以表示為一個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 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) 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中，關于貨運的體積限制為。5X1+4X224如設貨運有車運和船運兩種方式，上面的體積限制條件是針對車運的 ， 如 用 船 運 時 體 積 限 制 條 件 為7X1+3X245，為把這兩個限制條件統(tǒng)一在一個問題中，我們引入0-1變量，令這樣數(shù)學模型的約束條件就應寫為：其中M為一充分大數(shù)，當 y=0時，上面

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

13、值為-1，不滿足過濾條件3.6），故不予檢查。073321xxx分析解0，1，0），其目標函數(shù)值為7，故要檢查，經(jīng)檢查不滿足約束條件，故過濾條件不予修改。類似于上述分析，直到將所有的解均檢查完畢，最后得到結論，最優(yōu)解為1，1，1），最優(yōu)目標函數(shù)值為9。我們將上述求解方法稱為隱枚舉法。(二二)、簡單隱枚舉法、簡單隱枚舉法(max)原則：原則：(1)、用試探法，求出一個可行解，以它的目、用試探法，求出一個可行解，以它的目標值作為當前最好值標值作為當前最好值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 ) 目標值目標值 Z0 當前最好當前最好值值 (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再進行分枝。分別加上約束條件X

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

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

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

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

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

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

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