運籌學——.整數規(guī)劃與分配問題（行業(yè)知識）

1、第四章 整數規(guī)劃與分配問題對于線性規(guī)劃問題，最優(yōu)解可能是分數或小數。但是對于某些問題，會要求解答必須是整數（稱為整數解）。對于所求解是機器的臺數、完成工作的人數、裝貨的車數、集裝箱數量等；對于一些決策變量必須取Boolean值時，如要不要在某地建工廠，可選用一個邏輯變量x，令x=0表示不在該地建廠，x=1表示在該地建廠。 這時，分數或小數的解就不合要求，我們稱這樣的問題為整數規(guī)劃。例：某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如下表：貨物體積米3/箱重量百斤/箱 利潤百元/箱 甲 乙54 252010托運限制2413問兩種貨物各托運多少箱，可使獲得的利潤為最大？

2、能否先不考慮對變量的整數約束，作為一般線性規(guī)劃來求解，當解為非整數的時候可以用“四舍五入”或“湊整”方法尋找最優(yōu)解？對于變量取值很大時，用上述方法得到的解與最優(yōu)解差別不大；但當變量取值較小時，得到的解就可能與實際整數最優(yōu)解差別很大。當問題規(guī)模較大（決策變量較多）時，用“湊整”方法來算工作量很大。 例：某線性規(guī)劃問題最優(yōu)解為(x1, x2) = (4.6, 5.5)，用湊整法需要比較與上述數據最接近的幾種組合：(4, 5), (4, 6), (5, 5), (5, 6)，共四種組合。若問題中有10個整數變量，則解組合達到210 = 1024個整數組合。且最優(yōu)解未必在這些組合中。例：求整數規(guī)劃問題

3、的最優(yōu)解解：用圖解法得最優(yōu)解為（3.25 , 2.5）如果不考慮整數約束（稱為整數規(guī)劃問題的松弛問題）最優(yōu)解為（4 , 1）， z*= 14。湊整法求解：比較四個點（4 , 3）,（4 , 2）,（3 , 3）,（3 , 2），前三個都不是可行解，第四個雖然是可行解，但 z=13 不是最優(yōu)解。(4,1)主要內容一、整數規(guī)劃的特點及作用二、分配問題與匈牙利法三、分枝定界法四、應用舉例第一節(jié) 整數規(guī)劃的特點及作用第四章 整數規(guī)劃及分配問題一、整數規(guī)劃的特點及作用1.1 整數規(guī)劃的概念整數規(guī)劃(Integer Programming) ：決策變量要求取整數的線性規(guī)劃。如果所有的決策變量、技術系數和右

4、端項都是非負整數，就稱為純整數規(guī)劃。如果所有的決策變量都是非負整數，技術系數和右端項為有理數，稱為全整數規(guī)劃。如果僅一部分決策變量為整數，則稱為混合整數規(guī)劃。如果變量取值僅限于0或1，稱為0-1整數規(guī)劃。一、整數規(guī)劃的特點及作用1.2 0-1整數規(guī)劃某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點）Ai供選擇。規(guī)定在東區(qū)，由A1，A2，A3三個點中至多選兩個；在西區(qū)，由A4，A5兩個點中至少選一個；在南區(qū)，由A6，A7兩個點中至少選一個。如選用Ai點，設備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問：應如何選址，可使年利潤為最大？一、整數規(guī)劃的特點及作用1.

5、2 0-1整數規(guī)劃0-1整數規(guī)劃的一般形式:0-1整數規(guī)劃一般都是純整數規(guī)劃。一、整數規(guī)劃的特點及作用1.3 整數規(guī)劃的作用0-1整數規(guī)劃在管理領域具有重要作用m個約束條件中只有k個起作用；約束條件的右端項可能是r個值(b1, b2, br)中的某一個；兩組條件中滿足一組；用以表示含固定費用的函數。第二節(jié) 分配問題與匈牙利法第四章 整數規(guī)劃及分配問題二、分配問題與匈牙利法2.1 分配問題(1)指派n個人去完成n項任務，使完成 n項任務的總效率最高(或所需總時間最少)，這類問題稱為指派問題或分配問題。安排工作（派工）：有n項加工任務，怎樣指派到n臺機床上完成；有n條航線，怎樣指定n艘船去航行的；

6、 二、分配問題與匈牙利法2.1 分配問題(2)如果完成任務的效率表現為資源消耗，考慮的是如何分配任務使得目標函數極小化；如果完成任務的效率表現為生產效率的高低，則考慮的是如何分配使得目標函數最大化。在分配問題中，利用不同資源完成不同計劃活動的效率，通常用表格形式表示為效率表，表格中數字組成效率矩陣。二、分配問題與匈牙利法2.2 分配問題實例(1)例：有一份中文說明書，需要譯成英、日、德、俄四種文字?，F有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下，問應指派何人去完成工作，使所需總時間最少? 人員任務甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914

7、161378119二、分配問題與匈牙利法2.2 分配問題實例(2)效率矩陣用aij表示。aij 0 ( i,j = 1,2,n )表示指派第j人去完成第i項任務時的效率(時間、成本等)。 人員任務甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119二、分配問題與匈牙利法2.2 分配問題實例(3)某項任務只能由1人完成；某人只能完成1項任務。 建立整數規(guī)劃模型 分配問題是0-1整數規(guī)劃的特例，也是運輸問題的特例； n = m, aj = bj = 1。二、分配問題與匈牙利法2.3 匈牙利法分配問題可以用單純形法或運輸表求解。庫恩(W.W.Kuhn)于1955

8、年提出了指派問題的解法，他引用了匈牙利數學家康尼格(D.Knig)一個關于矩陣中零元素的定理：系數矩陣中獨立0元素的最多個數等于能覆蓋所有0元素的最少直線數。這個解法稱為匈牙利法。二、分配問題與匈牙利法2.3 匈牙利法的基本思想如果效率矩陣的所有元素aij0, 而其中存在一組位于不同行不同列的零元素，則只要令對應于這些零元素位置的xij = 1，其余的xij= 0，則所得到的可行解就是問題的最優(yōu)解。顯然令 x11=1, x23=1, x32=1, x44=1，即將第一項工作分配給甲，第二項給丙，第三項給乙，第四項給丁。這時完成總工作的時間為最少。如何尋找這組位于不同行不同列的零元素？二、分配問

9、題與匈牙利法2.3 匈牙利法的基本定理定理1 如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個常數ui(被稱為該行的位勢)，從每一列分別減去(或加上)一個常數vj(被稱為該列的位勢)，得到一個新的效率矩陣bij，若其中bij = aij uivj，則bij的最優(yōu)解等價于aij的最優(yōu)解。定理2 若矩陣A的元素可分為“0”和非“0”兩部分，則覆蓋“0”元素的最少直線數等于位于不同行不同列的“0”元素的最大個數。二、分配問題與匈牙利法2.4 匈牙利法實例(1) 人員任務甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119第一步：找出每行的最小元素

10、，每行對應減去這個元素。二、分配問題與匈牙利法2.4 匈牙利法實例(2)第二步：找出矩陣每列的最小元素，再分別從各列中減去。必定滿足：bij = aijuivj二、分配問題與匈牙利法2.4 匈牙利法實例(3)第三步：從第一行開始，若該行只有一個零元素，對零元素打上()括號，表示行所代表的任務已指派。用直線劃去其所在列；若該行沒有零元素或有兩個以上零元素(已劃去的不計在內)，則轉下一行，依次進行到最后一行為止。二、分配問題與匈牙利法2.4 匈牙利法實例(4)第三步：從第一列開始，若該列只有一個零元素，對零元素打上()括號(同樣不考慮已劃去的零元素)，再用直線劃去其所在行；若該列沒有零元素或有兩個

11、零元素，則轉下一列，依次進行到最后一列為止。二、分配問題與匈牙利法2.4 匈牙利法實例(5)效率矩陣每行都有一個打() 的零元素，這些零元素都位于不同行不同列，令對應打() 零元素的 xij=1 就得到最優(yōu)解；矩陣中所有零元素或被劃去，或被打上() ，但打() 的零元素少于m個，這時轉第四步。打()的零元素小于m，但未被劃去的零元素之間存在閉回路。二、分配問題與匈牙利法2.4 匈牙利法實例(6)順著閉回路的走向，對每個間隔的零元素打 ()，然后對所有打()的零元素或所在行或所在列畫一條直線，同樣得到最優(yōu)解。二、分配問題與匈牙利法2.4 匈牙利法實例(7)第四步：繼續(xù)按照定理1，對矩陣進行變換。

12、從矩陣未被直線覆蓋的數字中找出一個最小的數k；對矩陣的每行，當該行有直線覆蓋時，令ui=0，無直線覆蓋的，令ui=k；對矩陣中有直線覆蓋的列，令vj= -k，對無直線覆蓋的列，令vj=0。只有一條直線覆蓋的元素保持不變二、分配問題與匈牙利法2.4 匈牙利法實例(8)第五步：回到第三步，迭代運算，直到矩陣的每一行都有一個打() 的零元素為止。最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。所需時間為：4 + 4 + 9 + 11 = 28h二、分配問題與匈牙利法2.5 人數和任務數不相等的分配問題有四項工作分配給六個人去完成，每個人分別完成各項工作的時間如下，依然規(guī)定每個人完成一項工作。

13、每項工作只交給一個人去完成。即六個人中挑選哪四個人去完成，花費時間最少。 工作人IIIIIIIV123456373655616427245346648732 工作人IIIIIIIVVVI123456373655616427245346648732000000000000二、分配問題與匈牙利法2.6 目標函數最大化的分配問題令 bij = M - aij標準化 M為充分大的常數，可以得到bij0。根據定理1，這種轉換是等價的。 bij = aij uivj = aij + M若aij0，轉換后的效率矩陣不符合匈牙利法的條件。第四章 整數規(guī)劃及分配問題作 業(yè) 一求下面指派問題的最優(yōu)解第三節(jié) 分枝定

14、界法第四章 整數規(guī)劃及分配問題三、分枝定界法3.1 分枝定界法的基本思想分枝定界法可用于全部類型的整數規(guī)劃問題。設有最大化的整數規(guī)劃問題A，對應的線性規(guī)劃為問題B，從解問題B開始，若其最優(yōu)解不符合A的整數條件，那么B的最優(yōu)目標函數必是A的最優(yōu)目標函數z*的上界，記作 ；而A的任意可行解的目標函數值將是z*的下界 。分支定界法就是將B的可行域分成子區(qū)域(稱為分枝)的方法，逐步減小和增大上、下界，最終得到整數規(guī)劃問題A的z*。三、分枝定界法3.2 分枝定界法實例(1)求解B：其最優(yōu)解為x1 = 3.25，x2 = 2.5，最優(yōu)目標函數值為z* = 14.75松弛問題定界：令x1 = 0，x2 =

15、0 作為初始整數解，其 z = 0，因此 。分枝：在B的最優(yōu)解中，任取一個非整數變量，如 x2 = 2.5；因 x2 的最近鄰整數解為 x2 = 2或 x2 = 3，其最優(yōu)整數解區(qū)間只能是 x2 3或 x2 2。對B分別加上約束條件 x2 3和 x2 2，可得到兩個子問題B1和B2。三、分枝定界法3.2 分枝定界法實例(2)定界： 用圖解法可得B1的最優(yōu)解為(3.5, 2), z1 = 14.5； B2的最優(yōu)解為(2.5, 3), z2 =13.5。沒有整數最優(yōu)解，上界其下界沒有整數解， z1 z2，對B1再次分枝。 三、分枝定界法3.2 分枝定界法實例(3)三、分枝定界法3.2 分枝定界法實

16、例(4)再次分枝定界： B11的最優(yōu)解為(3, 2), z11 = 13;B12的最優(yōu)解為(4, 1), z12 = 14。這兩個最優(yōu)解都是A的可行解，此時A的上界和下界分別為14.5和 14。得最優(yōu)解： (4, 1)，Z* = 14。三、分枝定界法3.2 分枝定界法 剪枝Bx1=3.25 x2=2.5Z =14.75B1x1=3.5 x2=2Z = 14.5B2x1=2.5 x2=3Z =13.5B11x1=3 x2=2Z =13B12x1=4 x2=1Z =14x2 2x2 3x1 3x1 4將各子問題邊界值與保留的可行解的值進行比較。把邊界值劣于可行解的分支減去。若除保留的可行解外，其他

17、的分支均被減去，則得到最優(yōu)解。三、分枝定界法3.3 分枝定界法的解題思路分枝定界法實際上是一種利用替代問題的解來逐漸逼近原問題最優(yōu)解的方法；對替代問題的要求是：容易求解，且原問題的解集應無例外地包含在替代問題的解集中；如果替代問題(松弛)的最優(yōu)解是原問題的可行解，這個解就是原問題的最優(yōu)解；否則這個解的值是原問題最優(yōu)解的上界(求極大時)或下界值(求極小時)。三、分枝定界法3.4 分枝定界法的解題步驟(1)解松馳問題B：B沒有可行解，這時A也沒有可行解，停止。B有最優(yōu)解，并符合問題A的整數條件，B的最優(yōu)解即為A的最優(yōu)解，停止。B有最優(yōu)解，但不符合問題A的整數條件，將B的目標函數值為問題A的上界。用觀察法找問題A的一個整數可行解，一般可取 xj = 0，j=1,n，求得其目標函數值，作為A的下界，開始迭代運算。三、分枝定界法3.4 分枝定界法的解題步驟(2)分枝與定界：分枝：在B的最優(yōu)解中任選一個不符合整數條件的變量xj。其值為bj，以bj表示小于bj的最大整數。構造兩個約束條件xj bj和xj bj + 1，將這兩個約束條件，分別加入問題B，求兩個后繼規(guī)劃問題B1和B2。求解這兩個后繼松弛問題。定界：比較所有后繼問