1、運籌學01規劃指派問題1運籌學01規劃指派問題2純整數規劃、混整數規劃純整數規劃、混整數規劃分枝定界法分三步：分枝定界法分三步：運籌學01規劃指派問題3首先，刪去首先，刪去，把原，把原整數規劃整數規劃。其次，。其次，。最后，如果相應線性規劃的最優解。最后，如果相應線性規劃的最優解也是原整數規劃的最優解，那么整個計算過程也是原整數規劃的最優解，那么整個計算過程即告結束；否則，便轉入第二步。即告結束；否則，便轉入第二步。運籌學01規劃指派問題4從相應線性規劃的最優解從相應線性規劃的最優解中，任意選擇一個不滿足原整數規劃整數條中，任意選擇一個不滿足原整數規劃整數條件的決策變量件的決策變量xj=bj。

2、以使相應線性規劃增加以使相應線性規劃增加一個約束條件；一個約束條件；（或（或），因而得到兩枝新的線），因而得到兩枝新的線性規劃，然后計算每枝的最優解和最優值。性規劃，然后計算每枝的最優解和最優值。運籌學01規劃指派問題5 ：進行定界（由各枝的最：進行定界（由各枝的最優值中選最大值），找出界枝。若界枝的優值中選最大值），找出界枝。若界枝的最優解就是原整數規劃的最優解，則計算最優解就是原整數規劃的最優解，則計算過程便告結束；否則，回到第二步。過程便告結束；否則，回到第二步。返回返回運籌學01規劃指派問題6一、一、0- -1 規劃的概念規劃的概念二、隱枚舉法二、隱枚舉法運籌學01規劃指派問題7 在暑

3、假期間，某同學準備徒步回家探在暑假期間，某同學準備徒步回家探親。他把要帶的物品裝進包后，覺得還能多親。他把要帶的物品裝進包后，覺得還能多放放5個單位重量的東西。為此，他列出了擬放個單位重量的東西。為此，他列出了擬放物品的清單，見表物品的清單，見表2-11。他認為：應使所增加。他認為：應使所增加的物品總價值為最大。基于以上的考慮，他的物品總價值為最大。基于以上的考慮，他到底還要帶哪些東西呢？到底還要帶哪些東西呢？一、一、0- -1 規劃的概念規劃的概念運籌學01規劃指派問題8y為增加的物品總價值為增加的物品總價值;, 1,0號物品帶號物品不帶jjxj4,3,2, 11,0532553643214

4、321jxxxxxxxxxymaxj 編號編號 名稱名稱 重量重量 價值價值 1 書籍書籍 5 6 2 誘餌誘餌 2 3 3 電筒電筒 1 1 4 食物食物 3 5表表2-112-11解：解：設設例例9的數模為：的數模為：運籌學01規劃指派問題9 只取只取0或或1的變量的變量,稱為稱為0- -1變量變量。若純整。若純整數規劃的決策變量都是數規劃的決策變量都是0- -1變量，則稱為變量，則稱為0- -1規劃規劃。 在討論線性規劃時，如果研究對象可以在討論線性規劃時，如果研究對象可以歸結為互相對立的兩種可能情況，那么依靠歸結為互相對立的兩種可能情況，那么依靠引入引入0- -1變量，就能夠將它進一步

5、化成變量，就能夠將它進一步化成0- -1規規劃。劃。運籌學01規劃指派問題10如果如果0-1規劃模型不是標準型，總可以通過適規劃模型不是標準型，總可以通過適當的變換，使其化為標準型當的變換，使其化為標準型. 稱下面形式的數學模型為稱下面形式的數學模型為0-10-1規劃的標準型：規劃的標準型：11max(1, 2,)s.t.0,1.(1, 2, )njjjnijjijjyc xa xbimxjn返回返回運籌學01規劃指派問題11n從理論上講，求解從理論上講，求解01規劃，可用枚舉法。規劃，可用枚舉法。 這時，一旦有這時，一旦有n個決策變量個決策變量x1，x2，xn，就必須逐一地檢查（就必須逐一地

6、檢查（x1，x2，xn）的）的2n種種取值（不僅僅指可行解）。但是，當取值（不僅僅指可行解）。但是，當 n10時，即使經歷漫長的計算過程找到了最優解，時，即使經歷漫長的計算過程找到了最優解，也會由于時過境遷而失去實用價值。也會由于時過境遷而失去實用價值。n隱枚舉法是隱枚舉法是0- -1規劃的常用解法，它只須檢查規劃的常用解法，它只須檢查（x1，x2，xn）取值的一部分，即可找到）取值的一部分，即可找到最優解。最優解。運籌學01規劃指派問題12 利用隱枚舉法求解例利用隱枚舉法求解例9。試探的方法試探的方法這是一個求這是一個求y 的的最大值問題，當最大值問題，當然可以認為然可以認為ymax6這個新

7、的約束條件具有濾這個新的約束條件具有濾掉非最優解的功能，稱為掉非最優解的功能，稱為過濾條件過濾條件。找出一個可行解并計算出相應的目標函數值：找出一個可行解并計算出相應的目標函數值： （x1，x2，x3，x4）=（1，0，0，0），），y = 6；（2 2）將不等式）將不等式6x1+3x2+x3+5x46加到約束條件中；加到約束條件中；（3 3）把）把 6x1+3x2+x3+5x46 和和 5x1+2x2+x3+3x45 依次記作（依次記作（0）和（）和（1），把它們的左邊分別），把它們的左邊分別 寫成（寫成（0） 和（和（1） 。運籌學01規劃指派問題13 本本0-10-1規劃包含規劃包含4

8、4 個決策變量。所以（個決策變量。所以（x1，x2，x3，x4）共有）共有24種不同的取值。見表種不同的取值。見表2-12。其中：（其中：（x1，x2，x3，x4）是）是24種取值；（種取值；（0） 和（和（1） 是將（是將（x1，x2，x3，x4）取值代入后的）取值代入后的計算結果。考查它們是否滿足（計算結果。考查它們是否滿足（0）和（）和（1）：）：當不滿足某個約束條件時，同行以下的各項就當不滿足某個約束條件時，同行以下的各項就不再考慮，這表明（不再考慮，這表明（x1，x2，x3，x4）不是可行）不是可行解；當滿足全部約束條件時，這表明（解；當滿足全部約束條件時，這表明（x1，x2，x3，

9、x4）是可行解。）是可行解。運籌學01規劃指派問題14（x1，x2 ， x3 ， x4 ） ( 0 ) ( 1 ) 是是( ) 否否( ) y （0, 0, 0, 0 ） 0 ( 0, 0, 0, 1 ) 5 ( 0, 0 ,1, 0 ) 1 ( 0, 0, 1, 1 ) 6 4 6 ( 0, 1, 0, 0 ) 3 ( 0, 1, 0, 1 ) 8 5 8 ( 0, 1, 1, 0 ) 4 ( 0, 1, 1, 1 ) 9 6 ( 1, 0, 0, 0 ) 6 ( 5) 6 ( 1, 0, 0, 1 ) 11 8 ( 1, 0, 1, 0 ) 7 6 ( 1, 0, 1, 1 ) 12 9

10、( 1, 1, 0, 0 ) 9 7 ( 1, 1, 0, 1 ) 14 10 ( 1, 1, 1, 0 ) 10 8 ( 1, 1, 1, 1 ) 15 11 小于上面的目小于上面的目標值標值8，所以所以此解此解非最優。非最優。最最優優解解運籌學01規劃指派問題15求出這些可行解對應的目標函數的最大值：求出這些可行解對應的目標函數的最大值：max 6 , 8 = 8。于是，本于是，本0-10-1規劃的規劃的 最優值最優值y ymaxmax= 8= 8 最優解（最優解（x1，x2，x3，x4）=（0，1，0，1）。這表明，該同學還要帶誘餌和食物。這表明，該同學還要帶誘餌和食物。運籌學01規劃指

11、派問題16 從提高隱枚舉法的效率著想，當求解最從提高隱枚舉法的效率著想，當求解最大（小）化大（小）化0- -1規劃時，若遇到規劃時，若遇到y 值大（小）值大（小）于（于（0）的右邊，應隨即讓（）的右邊，應隨即讓（0）的右邊改取）的右邊改取這個這個y 值。求解值。求解0- -1規劃，不要墨守成規，應規劃，不要墨守成規，應視具體情況選擇適當的解法，以期收到事半視具體情況選擇適當的解法，以期收到事半功倍的效果。功倍的效果。運籌學01規劃指派問題17 求下面求下面0-10-1規劃的解規劃的解. . 1231231231223max32522 (1)44 (2)s.t.3 (3)46 (4)01.(1,

12、 2,3, )jyxxxxxxxxxxxxxxj或它滿足約束條件（它滿足約束條件（1）到（）到（4），且對應的目標函數值），且對應的目標函數值y = 3于是過濾條件為：于是過濾條件為：)001 (),(321xxx 首先用試探的方法找一個可行解首先用試探的方法找一個可行解:)0(3523321xxx運籌學01規劃指派問題18表表3-13 隱枚舉法計算表隱枚舉法計算表),(321xxx(0)（1）（2）（3）（4）滿足滿足否則否則y(0, 0, 0)0 (0, 0, 1)5-11015(0, 1, 0)-2 (0, 1, 1)3 (1, 0, 0)3 (1, 0, 1)802118(1, 1,

13、0)1 (1, 1, 1)6 運籌學01規劃指派問題19 用全部枚舉法，用全部枚舉法，3個變量共有個變量共有23=8個解，原來個解，原來4個約束條件共需個約束條件共需32次運算，現在用隱枚舉法，將次運算，現在用隱枚舉法，將5個約束條件按（個約束條件按（0）（4）順序排好（見表）順序排好（見表3-13），），對每個解依次代入約束條件左側，求出數值，看對每個解依次代入約束條件左側，求出數值，看是否適合不等式條件，如某一條件不適合，同行是否適合不等式條件，如某一條件不適合，同行以下各條件可不必再檢查，因而就減少了運算次以下各條件可不必再檢查，因而就減少了運算次數數. 本例實際只作本例實際只作18次運

14、算最優解次運算最優解:8max),101 (),(321yxxx返回返回運籌學01規劃指派問題20運籌學01規劃指派問題21 指派問題就是人員和設備的任務安排問題。指派問題就是人員和設備的任務安排問題。但是，運籌學當前所涉及的指派問題，并不是泛但是，運籌學當前所涉及的指派問題，并不是泛指一切指派問題，而是把它局限于某種特殊情況。指一切指派問題，而是把它局限于某種特殊情況。這種特殊情況的一個典型事例是：這種特殊情況的一個典型事例是：有有n個人分別個人分別完成完成n項任務中的項任務中的其中一項其中一項。因工作性質和個人。因工作性質和個人專長的差異，每個人完成各項工作的時間也就有專長的差異，每個人完

15、成各項工作的時間也就有所不同。于是便提出這樣的問題：所不同。于是便提出這樣的問題：指派哪個人完指派哪個人完成哪項工作，可使他們總的工作時間最短成哪項工作，可使他們總的工作時間最短？ 指派問題有指派問題有和和之分，二者的解之分，二者的解法大同小異。法大同小異。返回返回運籌學01規劃指派問題22 某醫院的四名化驗員（甲、乙、丙、某醫院的四名化驗員（甲、乙、丙、丁）完成四項化驗工作（丁）完成四項化驗工作（a、b、c、d）所消耗的時間見表所消耗的時間見表2- -13。哪個化驗員擔當。哪個化驗員擔當哪項化驗工作，可使他們總的消耗時間最哪項化驗工作，可使他們總的消耗時間最短？短？運籌學01規劃指派問題23

16、;, 1, 0jijixji擔當表示不擔當表示 a b c d 消耗時間（分） 甲 37.7 43.4 33.3 29.2 乙 32.9 33.1 28.5 26.4 丙 33.8 42.2 38.9 29.6 丁 37.0 34.7 30.4 28.5建立其數學模型。設：建立其數學模型。設： i = 1, ,2, ,3, ,4 分別表示甲，乙，丙，丁；分別表示甲，乙，丙，丁； j = 1, 2, 3, 4 分別表示分別表示a，b，c，d； bij 表示表示 i 完成完成 j 的消耗時間；的消耗時間；運籌學01規劃指派問題24 y 表示四名化驗員總的消耗時間，于是表示四名化驗員總的消耗時間，于

17、是數學模型數學模型為：為：41i41jjijixbymin 28.5 30.4 34.7 37.029.6 38.9 42.2 33.826.4 28.5 33.1 32.9 29.2 33.3 43.4 3 .37j ib4 3, 2, 1, 1 , 04 , 3 , 2 , 114 , 3 , 2 , 114141, jixixjxjijjiiji例例1111稱為稱為最小化指派問題最小化指派問題。運籌學01規劃指派問題25一般地，最小化指派問題的一般地，最小化指派問題的數學模型數學模型是：是：mimjjijijib xbymin110, m, , i, j , x, m, , i x, m

18、, , j xjimjjimiji211021121111其中其中 bij 稱為稱為效率矩陣效率矩陣。運籌學01規劃指派問題26 若效率矩陣若效率矩陣bij第第i 行元素的最小值為行元素的最小值為bi ,則效則效率矩陣分別為率矩陣分別為bij和和bij-bi的最小化指派問題具有相的最小化指派問題具有相同的最優解。把同的最優解。把“第第i行行”換成換成“第第j列列”，“bi”換換成成 “ “bj”后，依然成立。后，依然成立。在效率矩陣在效率矩陣bij中，讓每行（列）元素減去該中，讓每行（列）元素減去該行（列）元素的行（列）元素的，從而得到矩陣，從而得到矩陣。運籌學01規劃指派問題27 28.5

19、30.4 34.7 37.029.6 38.9 42.2 33.826.4 28.5 33.1 32.9 29.2 33.3 43.4 3 .37j ib 0 1.9 6.2 8.50 9.3 12.6 4.20 2.1 6.7 6.5 0 4.1 14.2 1 . 8jib 0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.3 0 2.2 8.0 9 . 3jic每行減去該行每行減去該行的最小元素的最小元素28.5-29.6-26.4-29.2-09 . 12 . 62 . 4每列減去該列每列減去該列的最小元素的最小元素每行每每行每列都有列都有零零運籌學01規劃指派問題28在

20、矩陣在矩陣cij中，首先找出含中，首先找出含0最少的行，并且最少的行，并且把其中的一個把其中的一個0括起來，即括起來，即（0）；然后劃掉與；然后劃掉與前提下，相繼完成其它各行。前提下，相繼完成其它各行。 （0）同行或同列的）同行或同列的0，即，即 。在不得再括。在不得再括 的的 0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.3 0 2.2 8.0 9 . 3jic( )( )( )運籌學01規劃指派問題29在矩陣在矩陣cij中，若不能得到中，若不能得到m個（個（0），），則進行第四步；若能得到則進行第四步；若能得到m個（個（0），則令），則令cij中中與（與（0）相對應的）

21、相對應的xij=1，其余的決策，其余的決策變量等于變量等于0。這時，。這時，xij便是最優解。將最便是最優解。將最優解代入目標函數優解代入目標函數 y 的表達式，即得最優的表達式，即得最優值。值。 0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.3 0 2.2 8.0 9 . 3jic( )( )( )沒有得到沒有得到4個個(0)轉入第四步轉入第四步運籌學01規劃指派問題30遵循下列程序，在遵循下列程序，在cij中畫出直線：中畫出直線：（一）在沒有（一）在沒有（0）的行，標上）的行，標上“”；（三）在標上（三）在標上“”的列中（的列中（0）所在的行，標上）所在的行，標上“”；

22、（四）在沒有標上（四）在沒有標上 “ “”的行或已經標上的行或已經標上“”的的列，列， 都畫上一條直線；都畫上一條直線；（二）在標上（二）在標上“”的行中的行中 所在的列，標上所在的列，標上“”；（五）去掉（五）去掉“”，而且將（，而且將（0）和）和 重新寫成重新寫成 0 0。0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.30 2.2 8.0 9 . 3 ( )( )( )( )( )( )0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.30 2.2 8.0 9 . 3運籌學01規劃指派問題31從從cij未畫上直線的元素中未畫上直線的元素中。讓畫上直線的列

23、中元素都。讓畫上直線的列中元素都，未畫上直線的行中元素都，未畫上直線的行中元素都，隨即去掉各行各列上的直線，并轉，隨即去掉各行各列上的直線，并轉 入第二步。入第二步。運籌學01規劃指派問題32 0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.3 0 2.2 8.0 9 . 3jic 0 0 0 4.30 7.4 6.4 0 0 0.2 0.5 2.30 2.2 8.0 9 . 3jic最小元素最小元素0.22 . 02 . 02 . 0 2 . 0 0 0 4.32 . 0 7.4 6.4 0 0 0 0.3 2.1 0 2.0 7.8 7 . 3j ic新產生新產生的的0元

24、素元素運籌學01規劃指派問題33 2 . 0 0 0 4.32 . 0 7.4 6.4 0 0 0 0.3 2.1 0 2.0 7.8 7 . 3jic0 0 1 00 0 0 1 0 1 0 0 1 0 0 0jix( )( )( )( ) 已得到已得到4個個（0），則令，則令cij中中與與（0）相對應的相對應的xij=1，其余的決策變量等于其余的決策變量等于0。這時，。這時，xij便是最優解。將最優解代便是最優解。將最優解代入目標函數入目標函數 y 的表達式，即得最優值的表達式，即得最優值 ymin = 126.2 (分分) 。轉入第二步轉入第二步, ,重新括重新括0 0元素元素: :返回

25、返回 這表明，讓化驗員甲、乙、丙、丁分別擔當化驗工作這表明，讓化驗員甲、乙、丙、丁分別擔當化驗工作d、c、a、b，可使他們總的消耗時間最短，只消，可使他們總的消耗時間最短，只消126.2分，就能完成四項化驗工作。分，就能完成四項化驗工作。運籌學01規劃指派問題34 某衛生防疫站準備選拔防疫科、食品科、總某衛生防疫站準備選拔防疫科、食品科、總務科的三名科長。幾經篩選，僅剩下趙、錢、孫三務科的三名科長。幾經篩選，僅剩下趙、錢、孫三名候選人。根據民主評議的統計結果名候選人。根據民主評議的統計結果, ,他們主持各個他們主持各個 科的工作能力（以科的工作能力（以 得分多少來衡量）得分多少來衡量） 如表如

26、表2-14 所示。試所示。試 從工作能力出發，從工作能力出發， 確定最優選擇科長確定最優選擇科長 方案。方案。 防疫防疫 食品食品 總務總務 工作能力（分）工作能力（分） 趙趙 35 30 27 錢錢 37 35 29 孫孫 38 28 32表表 2 21414運籌學01規劃指派問題35 設：設： i = 1, 2, 3分別表示趙，錢，孫；分別表示趙，錢，孫； j =1, 2, 3分別表示防疫科，食品科，總務科；分別表示防疫科，食品科，總務科； aij 表示表示 i 擔任擔任 j 科長的工作能力；科長的工作能力； ; , 1, , 0科長擔任表示科長不擔任表示jijixji y 表示三名科長總

27、的工作能力。表示三名科長總的工作能力。于是所求于是所求數學模型數學模型是：是：運籌學01規劃指派問題36例例12稱為最大化指派問題。稱為最大化指派問題。 3131ijjiji xaymax322838293537273035jia3,2, 1,1,03, 2, 113, 2, 113131jixixjxjijjiiji運籌學01規劃指派問題37 一般地，最大化指派問題的數學模型是：一般地，最大化指派問題的數學模型是：011jimimjjijia xaymaxmjixmixmjxjimjjimiji,2, 1,1,0,2, 11, 2, 1111其中其中aij稱為稱為效率矩陣效率矩陣。運籌學01規劃指派問題38：將最大化指派問題的效率矩陣將最大化指派問題的效率矩陣aij化成化成 aaij ，a = max aij i, j = 1, 2, , m 求出效率矩陣為求出效率矩陣為aaij的最小化指派問題的最小化指派問題的最優解，以其作為最大化指派問題的最優解。的最優解，以其作為最大化指派問題的最優解。把最優解代入最大化指派問題的目標函數把最優解代入最大化指派問題的目標函數的表達式，求出最優解。的表達式，求出最優解。 若效率矩陣若效率矩陣aij各元素的最大值是各元素的最大值是 a ,則效率矩陣為則效率矩陣為指派問題與效率