運籌學第四章整數規(guī)劃與分配問題ppt課件

1、作業(yè)：作業(yè)：P126 4.1 4.2 4.3(a) 4.4第四章第四章 整數規(guī)劃與分配問題整數規(guī)劃與分配問題第一節(jié)第一節(jié) 整數規(guī)劃的特點及運用整數規(guī)劃的特點及運用一、整數規(guī)劃的普通方式一、整數規(guī)劃的普通方式定義：一部分或全部決策變量必需取整數定義：一部分或全部決策變量必需取整數值的規(guī)劃問題稱為整數規(guī)劃。不思索整數值的規(guī)劃問題稱為整數規(guī)劃。不思索整數條件，由余下的目的函數和約束條件構成條件，由余下的目的函數和約束條件構成的規(guī)劃問題稱為該整數規(guī)劃的松弛問題。的規(guī)劃問題稱為該整數規(guī)劃的松弛問題。假設松弛問題是線性規(guī)劃，那么該整數規(guī)假設松弛問題是線性規(guī)劃，那么該整數規(guī)劃稱為整數線性規(guī)劃。劃稱為整數線性

2、規(guī)劃。且部分或全部取整數）或或),.2 , 1(0),.2 , 1(min)max(11njxmibxaxczjijnjijjnjj且均取整數值最優(yōu)解求下述整數規(guī)劃問題的例, 0,5 . 45 . 0143223max. 121212121xxxxxxxxz整數線性規(guī)劃的普通方式:不思索整數要求時，不思索整數要求時，最優(yōu)解為：最優(yōu)解為： X=(3.25 ,2.5)T X=(3.25 ,2.5)T Z=13 Z=13 見下頁圖解法見下頁圖解法思索整數要求時，最優(yōu)解為：思索整數要求時，最優(yōu)解為：X=(4 ,1)T Z=14X=(4 ,1)T Z=14湊整湊整 3 3，2 2可行，非最優(yōu)，可行，非最

3、優(yōu)，Z=13Z=13。 4 4，3 3，4 4，2 2，3 3，3 3 不可行不可行二、整數規(guī)劃的分類二、整數規(guī)劃的分類1. 1. 全整數線性規(guī)劃全整數線性規(guī)劃 決策變量全部取整數，約束系數和約束常數項決策變量全部取整數，約束系數和約束常數項也取整數的整數線性規(guī)劃。也取整數的整數線性規(guī)劃。2. 2. 純整數線性規(guī)劃純整數線性規(guī)劃 決策變量全部取整數，約束系數和約束常數項決策變量全部取整數，約束系數和約束常數項可取非整數的整數線性規(guī)劃?？扇》钦麛档恼麛稻€性規(guī)劃。 純整數線性規(guī)劃可化為全整數線性規(guī)劃。純整數線性規(guī)劃可化為全整數線性規(guī)劃。3. 3. 混合整數線性規(guī)劃混合整數線性規(guī)劃 決策變量中有一部

4、分取整數值，另一部分可取決策變量中有一部分取整數值，另一部分可取非整數值的整數線性規(guī)劃。非整數值的整數線性規(guī)劃。4. 0-14. 0-1整數線性規(guī)劃整數線性規(guī)劃 決策變量只能取決策變量只能取0 0或或1 1的整數線性規(guī)劃。的整數線性規(guī)劃。三、三、0-1變量或稱邏輯變量在模型中變量或稱邏輯變量在模型中的運用的運用 整數規(guī)劃模型對研討管理問題有重整數規(guī)劃模型對研討管理問題有重要意義。很多不能歸結為線性規(guī)劃數學要意義。很多不能歸結為線性規(guī)劃數學模型的管理問題，卻可以經過設置邏輯模型的管理問題，卻可以經過設置邏輯變量建立起整數規(guī)劃數學模型。變量建立起整數規(guī)劃數學模型。第二節(jié)第二節(jié) 分配問題分配問題(

5、(指派問題與匈牙利法指派問題與匈牙利法 2-1 2-1 問題的提出及數學模型問題的提出及數學模型 假設有假設有m m項義務分配給項義務分配給m m個人去完成，并個人去完成，并指定每個人完成其中一項，每項義務也只由指定每個人完成其中一項，每項義務也只由一個人完成，問應如何分配義務，才干使總一個人完成，問應如何分配義務，才干使總效率最高？或總費用最少，破費的總時間效率最高？或總費用最少，破費的總時間最少等等。最少等等。 設每個人完成不同義務的耗費見下面的設每個人完成不同義務的耗費見下面的效率矩陣，通常要求效率矩陣，通常要求aij0aij0。 mmmmmmmmijaaaaaaaaaaA.212222

6、111211),.,2 , 1,(j0, 1mjiijixij項任務。人去完成第不分配第，項任務；人去完成第分配第又設那么分配問題的數學模型為那么分配問題的數學模型為),.,2 , 1,(10),.,2 , 1( 1),.,2 , 1( 1min1111mjixmjxmixxazijmiijmjijmimjijij，或2-2 2-2 匈牙利法匈牙利法定理定理1.1.假設從分配問題效率矩陣假設從分配問題效率矩陣(aij)(aij)的每一的每一行元素中分別減去或加上一個常數行元素中分別減去或加上一個常數ui ui 稱為該行的位勢；從每一列中分別減去稱為該行的位勢；從每一列中分別減去或加上一個常數或

7、加上一個常數 vj vj 稱為該列的位稱為該列的位勢；得到一個新的效率矩陣勢；得到一個新的效率矩陣bijbij，其中，其中bij= bij= aij - ui - vj aij - ui - vj ，那么，那么aijaij的最優(yōu)解等價于的最優(yōu)解等價于bijbij的最優(yōu)解。的最優(yōu)解。定理定理2. 2. 假設效率矩陣假設效率矩陣A A的元素可分成的元素可分成0 0與非與非0 0兩部分，那么覆蓋一切兩部分，那么覆蓋一切0 0元素的最少直線數等元素的最少直線數等于位于不同行不同列的于位于不同行不同列的0 0元素的最大個數。元素的最大個數。匈牙利法的步驟：匈牙利法的步驟：第一步第一步 效率矩陣每行都減去

8、該行的最小元素；效率矩陣每行都減去該行的最小元素；第二步第二步 效率矩陣每列都減去該列的最小元素；效率矩陣每列都減去該列的最小元素； 此時，效率矩陣的每行每列都有此時，效率矩陣的每行每列都有0 0元素。元素。第三步第三步 尋覓位于不同行不同列的尋覓位于不同行不同列的0 0元素，也就是元素，也就是尋覓能覆蓋一切尋覓能覆蓋一切0 0元素的最少直線數。元素的最少直線數。 方法：方法：1. 1. 從只需一個從只需一個0 0元素的行開場，對元素的行開場，對0 0元素打上元素打上 號，然后對打號，然后對打 的的0 0元素所在列畫一條直線，元素所在列畫一條直線，依次進展到最后一行；依次進展到最后一行；2.

9、2. 從只需一個從只需一個0 0元素的列開場，對元素的列開場，對0 0元素打上元素打上 號，號， 然后對打然后對打 的的0 0元素所在行畫一條直線，元素所在行畫一條直線，依次進展到最后一列；依次進展到最后一列；3. 3. 反復反復1.1.、2.2.兩個步驟，能夠出現(xiàn)三種情況：兩個步驟，能夠出現(xiàn)三種情況： 1 1假設能找到假設能找到m m個位于不同行不同列的個位于不同行不同列的0 0元素元素即帶即帶 的的0 0元素，那么令元素，那么令0 0處的處的xij=1,xij=1,求解終了；求解終了；2 2假設有構成閉回路的假設有構成閉回路的0 0元素，那么任選一個元素，那么任選一個打打 ，然后對每個間隔

10、的，然后對每個間隔的0 0元素打元素打 ，同，同時對打時對打 的的0 0元素所在行或列畫一條直線。元素所在行或列畫一條直線。 3 3假設位于不同行不同列的假設位于不同行不同列的0 0元素元素 即帶即帶 的的0 0元素元素 少于少于m m，轉第四步。，轉第四步。 第四步第四步 為產生為產生m m個位于不同行不同列的個位于不同行不同列的0 0元素，元素，用定理一對效率矩陣進展調整，使之生成新的用定理一對效率矩陣進展調整，使之生成新的0 0元素。方法：元素。方法：1. 1. 在效率矩陣未被直線覆蓋的元素中找出最小在效率矩陣未被直線覆蓋的元素中找出最小元素元素k k；2. 2. 效率矩陣未被直線覆蓋的

11、行都減效率矩陣未被直線覆蓋的行都減k;k;3. 3. 效率矩陣被直線覆蓋的列都加效率矩陣被直線覆蓋的列都加k;k;4. 4. 轉回第三步。轉回第三步。2-3 特殊情況的處置特殊情況的處置1. 人數多于義務數，加虛擬義務。人數多于義務數，加虛擬義務。設有設有n人，人，m項義務，項義務，nm,那么添加那么添加n-m項義務。項義務。2. 人數少于義務數，加虛擬人員。人數少于義務數，加虛擬人員。設有設有n人，人，m項義務，項義務，nm,那么添加那么添加m-n項義務。項義務。此時，效率矩陣的元素全成為負值，不符合要此時，效率矩陣的元素全成為負值，不符合要求，根據定理求，根據定理1 1，令，令變換后的效率

12、矩陣每行都加變換后的效率矩陣每行都加M M即可。即可。mimjijijxaz11)(min ijaMmax3. 對求最大值問題的處置對求最大值問題的處置設目的函數為設目的函數為可將其變換為可將其變換為mimjijijxaz11max作業(yè)：作業(yè)：P127 4.8(a)P127 4.8(a)第三節(jié)第三節(jié) 分枝定界法分枝定界法一、分枝定界法的根本思想一、分枝定界法的根本思想 先不思索整數解的限制，用單純形法求先不思索整數解的限制，用單純形法求解其松弛問題，假設求得的解恰好是整數解，解其松弛問題，假設求得的解恰好是整數解，那么得整數規(guī)劃最優(yōu)解，停頓計算。否那么，那么得整數規(guī)劃最優(yōu)解，停頓計算。否那么，

13、將松弛問題分解為兩個子問題也稱后繼問將松弛問題分解為兩個子問題也稱后繼問題，每個子問題都是在原松弛問題的根底題，每個子問題都是在原松弛問題的根底上添加一個變量取整數的約束條件，這樣就上添加一個變量取整數的約束條件，這樣就減少了原來的可行域，然后用單純形法求解，減少了原來的可行域，然后用單純形法求解，直至得到最終結果。直至得到最終結果。二、分枝定界法的步驟最大值問題二、分枝定界法的步驟最大值問題第一步第一步 尋覓替代問題并求解尋覓替代問題并求解 設原整數規(guī)劃問題為設原整數規(guī)劃問題為IPIP，其松弛問題為，其松弛問題為L0L0。用單純形法求用單純形法求L0L0，假設，假設L0L0無可行解，那么無可

14、行解，那么IPIP也也無可行解，計算停頓。假設求得無可行解，計算停頓。假設求得L0L0為整數解，為整數解，那么得那么得IPIP的最優(yōu)解，停頓。否那么，轉下一步；的最優(yōu)解，停頓。否那么，轉下一步；第二步第二步 分枝與定界分枝與定界 在在L0L0的解中，任選一個不滿足整數條件的的解中，任選一個不滿足整數條件的變量變量xixi，設，設xi = bi xi = bi ，那么做兩個子問題，那么做兩個子問題 iibxL,1 1,2iibxL 不思索整數條件，用單純形法求解兩個不思索整數條件，用單純形法求解兩個子問題，假設得整數解或子問題的最優(yōu)值小子問題，假設得整數解或子問題的最優(yōu)值小于前面分支中已計算得到

15、的一切整數解的目于前面分支中已計算得到的一切整數解的目的函數最大值，那么停頓分枝；否那么，選的函數最大值，那么停頓分枝；否那么，選取一切子問題中目的函數值最大的問題作為取一切子問題中目的函數值最大的問題作為L0L0繼續(xù)分枝，直至得到整數規(guī)劃的最優(yōu)解。繼續(xù)分枝，直至得到整數規(guī)劃的最優(yōu)解。 第三步第三步 剪枝剪枝 在一切整數解中選取獲得最大值的解為在一切整數解中選取獲得最大值的解為最優(yōu)解。最優(yōu)解。且均取整數值數規(guī)劃問題的最優(yōu)解用分枝定界法求下述整例, 0,5 . 45 . 0143223max.21212121xxxxxxxxz第四節(jié)第四節(jié) 割平面法割平面法一、割平面法的根本思想一、割平面法的根本

16、思想 先不思索整數條件，用單純形法求解其先不思索整數條件，用單純形法求解其松弛問題，假設得整數解，即得整數規(guī)劃最松弛問題，假設得整數解，即得整數規(guī)劃最優(yōu)解。否那么，添加線性約束條件稱為割優(yōu)解。否那么，添加線性約束條件稱為割平面方程，將原問題的可行域切割掉一部平面方程，將原問題的可行域切割掉一部分，被切割掉的都是非整數解，再用單純形分，被切割掉的都是非整數解，再用單純形法求解新的線性規(guī)劃問題，依次進展下去，法求解新的線性規(guī)劃問題，依次進展下去，直到使問題的最優(yōu)解恰好在可行域的某個具直到使問題的最優(yōu)解恰好在可行域的某個具有整數坐標的頂點上得到。有整數坐標的頂點上得到。二、割平面法的步驟二、割平面法

17、的步驟第一步第一步 將問題化為全整數規(guī)劃問題；將問題化為全整數規(guī)劃問題； 第二步第二步 加非負松弛變量，將約束條件化為等加非負松弛變量，將約束條件化為等式約束；式約束； 第三步第三步 解相應的線性規(guī)劃問題解相應的線性規(guī)劃問題1. 1. 假設線性規(guī)劃的最優(yōu)解是整數解，那么得假設線性規(guī)劃的最優(yōu)解是整數解，那么得整數規(guī)劃的最優(yōu)解，停頓計算，否那么轉整數規(guī)劃的最優(yōu)解，停頓計算，否那么轉2;2;2. 2. 求解割平面方程作為附加約束條件，構成求解割平面方程作為附加約束條件，構成新的線性規(guī)劃問題，繼續(xù)第三步。新的線性規(guī)劃問題，繼續(xù)第三步。三、割平面方程的求法三、割平面方程的求法 1.1.求解線性方程組法求

18、解線性方程組法 設設xi=bi xi=bi 是整數規(guī)劃的松弛問題是整數規(guī)劃的松弛問題LPLP問題問題最優(yōu)解中取分數值分數部分最大的基變量，最優(yōu)解中取分數值分數部分最大的基變量，將將xi=bixi=bi用非基變量表示用非基變量表示 將將bibi，aikaik分解成整數部分和非負真分數部分分解成整數部分和非負真分數部分之和：之和：kkikiixabxkkikikkikiikkikikkikikkikikiiiikikikikiiiixffxNNxxffxNNxfNfNxffNaffNb)() 10() 10(得kkikiixabx 要使一切變量都取非負整數值，上式左要使一切變量都取非負整數值，上式

19、左端必為整數，從而右端也必為整數，由于端必為整數，從而右端也必為整數，由于fi fi 0 0 ， fik 0 fik 0 ，故應有，故應有 這就是所求的割平面方程這就是所求的割平面方程GomoryGomory方程方程 。1kkikixff例例 設某整數規(guī)劃的松弛問題最優(yōu)解中有設某整數規(guī)劃的松弛問題最優(yōu)解中有x1 = x1 = 3.5 3.5 ， x1 x1的非基變量表達式為的非基變量表達式為x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 =3+0.5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 =3+0.

20、5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 x6x6或或: : x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 由此可得割平面方程為由此可得割平面方程為 0.5 + 0.4 x4 + 0.4 x5 1 0.5 + 0.4 x4 + 0.4 x5 1 2. 2. 借助單純形表法借助單純形表法 對求解整數規(guī)劃問題的松弛問題對求解整數規(guī)劃問題的松弛問題LPLP問題得到問題得到最優(yōu)單純形表，設最優(yōu)單純形表，設xi=bi xi=bi 是最優(yōu)解中取分數值分數是最優(yōu)解中取分數值分數部分最

21、大的基變量，那么有部分最大的基變量，那么有kkikiikkikiikikikikiikikikikiiiiikiikkikixffNxNxfNxfNxffNaffNbabbxax即得令真分數部分之和，分解成整數部分和非負將)() 10() 10(, 上式中，要使等式左端為整數，那么右上式中，要使等式左端為整數，那么右端也必為整數，由端也必為整數，由0 0fifi1,1,故應有故應有 這就是所求的割平面方程這就是所求的割平面方程GomoryGomory方程。方程。0kkikixff例例 設某整數規(guī)劃的松弛問題最優(yōu)解中有設某整數規(guī)劃的松弛問題最優(yōu)解中有x1=3.5 x1=3.5 ， x1x1在單純

22、形表中的約束條件為：在單純形表中的約束條件為： x1-2.4x4 +3.6x5 -4x6=3.5 x1-2.4x4 +3.6x5 -4x6=3.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 或或: x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 : x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 由此可得割平面方程為由此可得割平面方程為 0.5 -0.6x4 -0.6x50 0.5 -0.6x4 -0.6x50 且均取整數值規(guī)劃問題的最優(yōu)解用割平面法求下述整數例,

23、0,5 . 45 . 0143223max.21212121xxxxxxxxz解：解：1.1.將問題化為全整數規(guī)劃問題；去掉變量的將問題化為全整數規(guī)劃問題；去掉變量的整數要求，可得其松弛問題整數要求，可得其松弛問題G0G02. 2. 加松弛變量，將約束化為等式約束；并加松弛變量，將約束化為等式約束；并用單純形法求解得到最優(yōu)表；表用單純形法求解得到最優(yōu)表；表4-44-40,92143223max21212121xxxxxxxxz0,92143223max432142132121xxxxxxxxxxxxz3. 找出非整數解變量中非整數部分最大的找出非整數解變量中非整數部分最大的一個基變量這里是一個

24、基變量這里是x2，并寫出這一行，并寫出這一行的約束；的約束；:02121212121212)212()211()210(2122121434342432432加松弛變量化為等式所以，割平面方程為或即xxxxxxxxxxxx。形表，見表的單純法繼續(xù)求解得到中，然后用對偶單純形的單純形表解，可將該式直接加入求問題的約束中，得一新的將上式加入松弛問題54LP2121211010543GGGGxxx 4.由于表中還有非整數解，找出非整數解變量由于表中還有非整數解，找出非整數解變量中非整數部分最大的一個基變量這里是中非整數部分最大的一個基變量這里是x1，并寫出這一行的約束；并寫出這一行的約束；:0212

25、1212132132121321555415541541加松弛變量化為等式得割平面方程為或即xxxxxxxxxxxx。單純形表，見表的續(xù)求解得到然后用對偶單純形法繼的單純形表中，可將該式直接加入求解，問題中得一新的將上式加入到64LP2121212165GGGGxx該表已得到整數解，故原整數規(guī)劃問題的最優(yōu)解該表已得到整數解，故原整數規(guī)劃問題的最優(yōu)解為為: x1 = 4: x1 = 4， x2 = 1x2 = 1， 最優(yōu)值為最優(yōu)值為max z=14max z=14作業(yè)：作業(yè)：P128130 4.13 4.14 4.16 4.18 P128130 4.13 4.14 4.16 4.18 第五節(jié)第五

26、節(jié) 解解0-10-1規(guī)劃問題的隱枚舉法規(guī)劃問題的隱枚舉法一、隱枚舉法的根本思想一、隱枚舉法的根本思想 首先令一切整數變量都取首先令一切整數變量都取0 0值，然后使某值，然后使某些變量取值為些變量取值為1 1，直到獲得一個可行解，將第，直到獲得一個可行解，將第一個可行解作為暫時最優(yōu)解稱為過濾條一個可行解作為暫時最優(yōu)解稱為過濾條件，再繼續(xù)試探某些變量的取值，假設可件，再繼續(xù)試探某些變量的取值，假設可找到另一個可行解優(yōu)于暫時最優(yōu)解，那么將找到另一個可行解優(yōu)于暫時最優(yōu)解，那么將新的可行解作為暫時最優(yōu)解新的過濾條新的可行解作為暫時最優(yōu)解新的過濾條件，依此類推，檢查整數變量等于件，依此類推，檢查整數變量等于0 0或或1 1的的各種組合，不斷尋求新的暫時