運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題課件

1、運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,第四章 整數(shù)規(guī)劃與分配問題,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,對(duì)于線性規(guī)劃問題，最優(yōu)解可能是分?jǐn)?shù)或小數(shù)。但是對(duì)于某些問題，會(huì)要求解答必須是整數(shù)（稱為整數(shù)解）。 對(duì)于所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)、裝貨的車數(shù)、集裝箱數(shù)量等； 對(duì)于一些決策變量必須取Boolean值時(shí)，如要不要在某地建工廠，可選用一個(gè)邏輯變量x，令x=0表示不在該地建廠，x=1表示在該地建廠。 這時(shí)，分?jǐn)?shù)或小數(shù)的解就不合要求，我們稱這樣的問題為整數(shù)規(guī)劃。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,例：某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如下表：,問兩種貨物各托運(yùn)多少箱，可使獲得的利

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

3、且最優(yōu)解未必在這些組合中。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,例：求整數(shù)規(guī)劃問題的最優(yōu)解,解：用圖解法得最優(yōu)解為（3.25 , 2.5） 如果不考慮整數(shù)約束（稱為整數(shù)規(guī)劃問題的松弛問題）,最優(yōu)解為（4 , 1）， z*= 14。,湊整法求解：比較四個(gè)點(diǎn)（4 , 3）,（4 , 2）,（3 , 3）,（3 , 2），前三個(gè)都不是可行解，第四個(gè)雖然是可行解，但 z=13 不是最優(yōu)解。,(4,1),運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,主要內(nèi)容,一、整數(shù)規(guī)劃的特點(diǎn)及作用 二、分配問題與匈牙利法 三、分枝定界法 四、應(yīng)用舉例,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,第一節(jié) 整數(shù)規(guī)劃的特點(diǎn)及作用,第四章 整數(shù)規(guī)劃及分配問題,運(yùn)籌學(xué)

4、.整數(shù)規(guī)劃與分配問題,一、整數(shù)規(guī)劃的特點(diǎn)及作用1.1 整數(shù)規(guī)劃的概念,整數(shù)規(guī)劃(Integer Programming) ：決策變量要求取整數(shù)的線性規(guī)劃。 如果所有的決策變量、技術(shù)系數(shù)和右端項(xiàng)都是非負(fù)整數(shù)，就稱為純整數(shù)規(guī)劃。 如果所有的決策變量都是非負(fù)整數(shù)，技術(shù)系數(shù)和右端項(xiàng)為有理數(shù)，稱為全整數(shù)規(guī)劃。 如果僅一部分決策變量為整數(shù)，則稱為混合整數(shù)規(guī)劃。 如果變量取值僅限于0或1，稱為0-1整數(shù)規(guī)劃。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,一、整數(shù)規(guī)劃的特點(diǎn)及作用1.2 0-1整數(shù)規(guī)劃,某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（點(diǎn)）Ai供選擇。規(guī)定 在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；

5、 在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。 如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。 問：應(yīng)如何選址，可使年利潤為最大？,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,一、整數(shù)規(guī)劃的特點(diǎn)及作用1.2 0-1整數(shù)規(guī)劃,0-1整數(shù)規(guī)劃的一般形式:,0-1整數(shù)規(guī)劃一般都是純整數(shù)規(guī)劃。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,一、整數(shù)規(guī)劃的特點(diǎn)及作用1.3 整數(shù)規(guī)劃的作用,0-1整數(shù)規(guī)劃在管理領(lǐng)域具有重要作用 m個(gè)約束條件中只有k個(gè)起作用； 約束條件的右端項(xiàng)可能是r個(gè)值(b1, b2, br)中的某一個(gè)； 兩組條件中滿足一組； 用以表示含固定費(fèi)

6、用的函數(shù)。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,第二節(jié) 分配問題與匈牙利法,第四章 整數(shù)規(guī)劃及分配問題,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.1 分配問題(1),指派n個(gè)人去完成n項(xiàng)任務(wù)，使完成 n項(xiàng)任務(wù)的總效率最高(或所需總時(shí)間最少)，這類問題稱為指派問題或分配問題。 安排工作（派工）：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上完成； 有n條航線，怎樣指定n艘船去航行的； ,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.1 分配問題(2),如果完成任務(wù)的效率表現(xiàn)為資源消耗，考慮的是如何分配任務(wù)使得目標(biāo)函數(shù)極小化； 如果完成任務(wù)的效率表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目標(biāo)函

7、數(shù)最大化。 在分配問題中，利用不同資源完成不同計(jì)劃活動(dòng)的效率，通常用表格形式表示為效率表，表格中數(shù)字組成效率矩陣。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.2 分配問題實(shí)例(1),例：有一份中文說明書，需要譯成英、日、德、俄四種文字。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下，問應(yīng)指派何人去完成工作，使所需總時(shí)間最少?,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.2 分配問題實(shí)例(2),效率矩陣用aij表示。aij 0 ( i,j = 1,2,n )表示指派第j人去完成第i項(xiàng)任務(wù)時(shí)的效率(時(shí)間、成本等)。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分

8、配問題與匈牙利法2.2 分配問題實(shí)例(3),某項(xiàng)任務(wù)只能由1人完成； 某人只能完成1項(xiàng)任務(wù)。 建立整數(shù)規(guī)劃模型,分配問題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問題的特例； n = m, aj = bj = 1。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.3 匈牙利法,分配問題可以用單純形法或運(yùn)輸表求解。 庫恩(W.W.Kuhn)于1955年提出了指派問題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.Knig)一個(gè)關(guān)于矩陣中零元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。這個(gè)解法稱為匈牙利法。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.3 匈牙利法的基本

9、思想,如果效率矩陣的所有元素aij0, 而其中存在一組位于不同行不同列的零元素，則只要令對(duì)應(yīng)于這些零元素位置的xij = 1，其余的xij= 0，則所得到的可行解就是問題的最優(yōu)解。,顯然令 x11=1, x23=1, x32=1, x44=1，即將第一項(xiàng)工作分配給甲，第二項(xiàng)給丙，第三項(xiàng)給乙，第四項(xiàng)給丁。這時(shí)完成總工作的時(shí)間為最少。,如何尋找這組位于不同行不同列的零元素？,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.3 匈牙利法的基本定理,定理1 如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui(被稱為該行的位勢(shì))，從每一列分別減去(或加上)一個(gè)常數(shù)vj(被稱為

10、該列的位勢(shì))，得到一個(gè)新的效率矩陣bij，若其中bij = aij uivj，則bij的最優(yōu)解等價(jià)于aij的最優(yōu)解。 定理2 若矩陣A的元素可分為“0”和非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素的最大個(gè)數(shù)。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(1),第一步：找出每行的最小元素，每行對(duì)應(yīng)減去這個(gè)元素。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(2),第二步：找出矩陣每列的最小元素，再分別從各列中減去。 必定滿足：bij = aijuivj,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4

11、 匈牙利法實(shí)例(3),第三步：從第一行開始，若該行只有一個(gè)零元素，對(duì)零元素打上()括號(hào)，表示行所代表的任務(wù)已指派。用直線劃去其所在列；若該行沒有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi))，則轉(zhuǎn)下一行，依次進(jìn)行到最后一行為止。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(4),第三步：從第一列開始，若該列只有一個(gè)零元素，對(duì)零元素打上()括號(hào)(同樣不考慮已劃去的零元素)，再用直線劃去其所在行；若該列沒有零元素或有兩個(gè)零元素，則轉(zhuǎn)下一列，依次進(jìn)行到最后一列為止。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(5),效率矩陣每行都有一個(gè)打() 的

12、零元素，這些零元素都位于不同行不同列，令對(duì)應(yīng)打() 零元素的 xij=1 就得到最優(yōu)解； 矩陣中所有零元素或被劃去，或被打上() ，但打() 的零元素少于m個(gè)，這時(shí)轉(zhuǎn)第四步。 打()的零元素小于m，但未被劃去的零元素之間存在閉回路。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(6),順著閉回路的走向，對(duì)每個(gè)間隔的零元素打 ()，然后對(duì)所有打()的零元素或所在行或所在列畫一條直線，同樣得到最優(yōu)解。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(7),第四步：繼續(xù)按照定理1，對(duì)矩陣進(jìn)行變換。 從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)k；對(duì)矩陣

13、的每行，當(dāng)該行有直線覆蓋時(shí)，令ui=0，無直線覆蓋的，令ui=k；對(duì)矩陣中有直線覆蓋的列，令vj= -k，對(duì)無直線覆蓋的列，令vj=0。,只有一條直線覆蓋的元素保持不變,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.4 匈牙利法實(shí)例(8),第五步：回到第三步，迭代運(yùn)算，直到矩陣的每一行都有一個(gè)打() 的零元素為止。,最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。所需時(shí)間為：4 + 4 + 9 + 11 = 28h,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.5 人數(shù)和任務(wù)數(shù)不相等的分配問題,有四項(xiàng)工作分配給六個(gè)人去完成，每個(gè)人分別完成各項(xiàng)工作的時(shí)間如下，依然規(guī)定每個(gè)

14、人完成一項(xiàng)工作。每項(xiàng)工作只交給一個(gè)人去完成。即六個(gè)人中挑選哪四個(gè)人去完成，花費(fèi)時(shí)間最少。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,二、分配問題與匈牙利法2.6 目標(biāo)函數(shù)最大化的分配問題,M為充分大的常數(shù)，可以得到bij0。根據(jù)定理1，這種轉(zhuǎn)換是等價(jià)的。 bij = aij uivj = aij + M,若aij0，轉(zhuǎn)換后的效率矩陣不符合匈牙利法的條件。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,第四章 整數(shù)規(guī)劃及分配問題作 業(yè) 一,求下面指派問題的最優(yōu)解,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,第三節(jié) 分枝定界法,第四章 整數(shù)規(guī)劃及分配問題,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,三、分枝定界法3.1 分枝定界法的基本思想,分枝定界法可用于全

15、部類型的整數(shù)規(guī)劃問題。 設(shè)有最大化的整數(shù)規(guī)劃問題A，對(duì)應(yīng)的線性規(guī)劃為問題B，從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)z*的上界，記作 ；而A的任意可行解的目標(biāo)函數(shù)值將是z*的下界 。分支定界法就是將B的可行域分成子區(qū)域(稱為分枝)的方法，逐步減小和增大上、下界，最終得到整數(shù)規(guī)劃問題A的z*。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,三、分枝定界法3.2 分枝定界法實(shí)例(1),求解B：其最優(yōu)解為x1 = 3.25，x2 = 2.5，最優(yōu)目標(biāo)函數(shù)值為z* = 14.75,定界：令x1 = 0，x2 = 0 作為初始整數(shù)解，其 z = 0，因此 。,運(yùn)籌學(xué).整數(shù)規(guī)劃

16、與分配問題,分枝：在B的最優(yōu)解中，任取一個(gè)非整數(shù)變量，如 x2 = 2.5；因 x2 的最近鄰整數(shù)解為 x2 = 2或 x2 = 3，其最優(yōu)整數(shù)解區(qū)間只能是 x2 3或 x2 2。對(duì)B分別加上約束條件 x2 3和 x2 2，可得到兩個(gè)子問題B1和B2。,三、分枝定界法3.2 分枝定界法實(shí)例(2),運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,定界： 用圖解法可得B1的最優(yōu)解為(3.5, 2), z1 = 14.5； B2的最優(yōu)解為(2.5, 3), z2 =13.5。沒有整數(shù)最優(yōu)解，上界 其下界沒有整數(shù)解， z1 z2，對(duì)B1再次分枝。,三、分枝定界法3.2 分枝定界法實(shí)例(3),運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,三

17、、分枝定界法3.2 分枝定界法實(shí)例(4),再次分枝定界： B11的最優(yōu)解為(3, 2), z11 = 13; B12的最優(yōu)解為(4, 1), z12 = 14。 這兩個(gè)最優(yōu)解都是A的可行解，此時(shí)A的上界和下界分別為14.5和 14。 得最優(yōu)解： (4, 1)，Z* = 14。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,三、分枝定界法3.2 分枝定界法 剪枝,x2 2,x2 3,x1 3,x1 4,將各子問題邊界值與保留 的可行解的值進(jìn)行比較。 把邊界值劣于可行解的分 支減去。若除保留的可行 解外，其他的分支均被減 去，則得到最優(yōu)解。,運(yùn)籌學(xué).整數(shù)規(guī)劃與分配問題,三、分枝定界法3.3 分枝定界法的解題思路,分

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