運籌學(xué)-整數(shù)規(guī)劃與分配問題

第四章整數(shù)規(guī)劃與分配問題運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第1頁!對于線性規(guī)劃問題，最優(yōu)解可能是分數(shù)或小數(shù)。但是對于某些問題，會要求解答必須是整數(shù)（稱為整數(shù)解）。對于所求解是機器的臺數(shù)、完成工作的人數(shù)、裝貨的車數(shù)、集裝箱數(shù)量等；對于一些決策變量必須取Boolean值時，如要不要在某地建工廠，可選用一個邏輯變量x，令x=0表示不在該地建廠，x=1表示在該地建廠。

這時，分數(shù)或小數(shù)的解就不合要求，我們稱這樣的問題為整數(shù)規(guī)劃。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第2頁!例：某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如下表：貨物體積米3/箱重量百斤/箱利潤百元/箱

甲乙54252010托運限制2413問兩種貨物各托運多少箱，可使獲得的利潤為最大？能否先不考慮對變量的整數(shù)約束，作為一般線性規(guī)劃來求解，當解為非整數(shù)的時候可以用“四舍五入”或“湊整”方法尋找最優(yōu)解？運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第3頁!對于變量取值很大時，用上述方法得到的解與最優(yōu)解差別不大；但當變量取值較小時，得到的解就可能與實際整數(shù)最優(yōu)解差別很大。當問題規(guī)模較大（決策變量較多）時，用“湊整”方法來算工作量很大。例：某線性規(guī)劃問題最優(yōu)解為(x1,x2)=(4.6,5.5)，用湊整法需要比較與上述數(shù)據(jù)最接近的幾種組合：(4,5),(4,6),(5,5),(5,6)，共四種組合。若問題中有10個整數(shù)變量，則解組合達到210=1024個整數(shù)組合。且最優(yōu)解未必在這些組合中。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第4頁!主要內(nèi)容一、整數(shù)規(guī)劃的特點及作用二、分配問題與匈牙利法三、分枝定界法四、應(yīng)用舉例運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第5頁!一、整數(shù)規(guī)劃的特點及作用

1.1整數(shù)規(guī)劃的概念整數(shù)規(guī)劃(IntegerProgramming)：決策變量要求取整數(shù)的線性規(guī)劃。如果所有的決策變量、技術(shù)系數(shù)和右端項都是非負整數(shù)，就稱為純整數(shù)規(guī)劃。如果所有的決策變量都是非負整數(shù)，技術(shù)系數(shù)和右端項為有理數(shù)，稱為全整數(shù)規(guī)劃。如果僅一部分決策變量為整數(shù)，則稱為混合整數(shù)規(guī)劃。如果變量取值僅限于0或1，稱為0-1整數(shù)規(guī)劃。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第6頁!一、整數(shù)規(guī)劃的特點及作用

1.2

0-1整數(shù)規(guī)劃0-1整數(shù)規(guī)劃的一般形式:0-1整數(shù)規(guī)劃一般都是純整數(shù)規(guī)劃。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第7頁!第二節(jié)分配問題與匈牙利法第四章整數(shù)規(guī)劃及分配問題運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第8頁!二、分配問題與匈牙利法

2.1分配問題(2)如果完成任務(wù)的效率表現(xiàn)為資源消耗，考慮的是如何分配任務(wù)使得目標函數(shù)極小化；如果完成任務(wù)的效率表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目標函數(shù)最大化。在分配問題中，利用不同資源完成不同計劃活動的效率，通常用表格形式表示為效率表，表格中數(shù)字組成效率矩陣。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第9頁!二、分配問題與匈牙利法

2.2分配問題實例(2)效率矩陣用[aij]表示。aij>0(i,j=1,2,…,n)表示指派第j人去完成第i項任務(wù)時的效率(時間、成本等)。

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第10頁!二、分配問題與匈牙利法

2.3匈牙利法分配問題可以用單純形法或運輸表求解。庫恩(W.W.Kuhn)于1955年提出了指派問題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.K?nig)一個關(guān)于矩陣中零元素的定理：系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。這個解法稱為匈牙利法。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第11頁!二、分配問題與匈牙利法

2.3匈牙利法的基本定理定理1如果從分配問題效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數(shù)ui(被稱為該行的位勢)，從每一列分別減去(或加上)一個常數(shù)vj(被稱為該列的位勢)，得到一個新的效率矩陣[bij]，若其中bij=aij

–ui–vj，則[bij]的最優(yōu)解等價于[aij]的最優(yōu)解。定理2若矩陣A的元素可分為“0”和非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素的最大個數(shù)。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第12頁!二、分配問題與匈牙利法

2.4匈牙利法實例(2)第二步：找出矩陣每列的最小元素，再分別從各列中減去。必定滿足：bij=aij–ui–vj運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第13頁!二、分配問題與匈牙利法

2.4匈牙利法實例(4)第三步：從列開始，若該列只有一個零元素，對零元素打上()括號(同樣不考慮已劃去的零元素)，再用直線劃去其所在行；若該列沒有零元素或有兩個零元素，則轉(zhuǎn)下一列，依次進行到最后一列為止。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第14頁!二、分配問題與匈牙利法

2.4匈牙利法實例(6)順著閉回路的走向，對每個間隔的零元素打()，然后對所有打()的零元素或所在行或所在列畫一條直線，同樣得到最優(yōu)解。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第15頁!二、分配問題與匈牙利法

2.4匈牙利法實例(8)第五步：回到第三步，迭代運算，直到矩陣的每一行都有一個打()的零元素為止。最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。所需時間為：4

+

4

+

9

+

11=28h運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第16頁!二、分配問題與匈牙利法

2.6目標函數(shù)最大化的分配問題令

bij

=

M

-

aij標準化

M為充分大的常數(shù)，可以得到bij≥0。根據(jù)定理1，這種轉(zhuǎn)換是等價的。bij

=?aij

–ui–vj

=?aij

+

M若aij≥0，轉(zhuǎn)換后的效率矩陣不符合匈牙利法的條件。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第17頁!第三節(jié)分枝定界法第四章整數(shù)規(guī)劃及分配問題運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第18頁!三、分枝定界法

3.2分枝定界法實例(1)求解B：其最優(yōu)解為x1=3.25，x2=2.5，最優(yōu)目標函數(shù)值為z*

=14.75松弛問題定界：令x1=0，x2=0作為初始整數(shù)解，其z=0，因此。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第19頁!定界：

用圖解法可得B1的最優(yōu)解為(3.5,2),z1=14.5；B2的最優(yōu)解為(2.5,3),z2=13.5。沒有整數(shù)最優(yōu)解，上界其下界沒有整數(shù)解，

z1>z2，對B1再次分枝。

三、分枝定界法

3.2分枝定界法實例(3)運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第20頁!三、分枝定界法

3.2分枝定界法—剪枝Bx1=3.25

x2=2.5Z

=14.75B1x1=3.5x2=2Z

=

14.5B2x1=2.5

x2=3Z

=13.5B11x1=3

x2=2Z

=13B12x1=4x2=1Z

=14××x2≤2x2≥3x1≤3x1≥4將各子問題邊界值與保留的可行解的值進行比較。把邊界值劣于可行解的分支減去。若除保留的可行解外，其他的分支均被減去，則得到最優(yōu)解。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第21頁!三、分枝定界法

3.4分枝定界法的解題步驟(1)解松馳問題B：B沒有可行解，這時A也沒有可行解，停止。B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，停止。B有最優(yōu)解，但不符合問題A的整數(shù)條件，將B的目標函數(shù)值為問題A的上界。用觀察法找問題A的一個整數(shù)可行解，一般可取xj=0，j=1,…,n，求得其目標函數(shù)值，作為A的下界，開始迭代運算。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第22頁!三、分枝定界法

3.4分枝定界法的解題步驟(3)比較與剪枝：各分支的最優(yōu)目標函數(shù)若小于第三步得到的下界，則剪掉此分枝(用打×表示)，以后不再考慮。若大于下界，且不符合整數(shù)條件，則重復(fù)第三步，選取所有邊界值最優(yōu)的分枝進行分枝與定界，一直到最后得到z*=

A的下界為止，此時得到最優(yōu)解。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第23頁!例：求整數(shù)規(guī)劃問題的最優(yōu)解解：用圖解法得最優(yōu)解為（3.25,2.5）如果不考慮整數(shù)約束（稱為整數(shù)規(guī)劃問題的松弛問題）最優(yōu)解為（4,1），z*=14。湊整法求解：比較四個點（4,3）,（4,2）,（3,3）,（3,2），前三個都不是可行解，第四個雖然是可行解，但z=13不是最優(yōu)解。(4,1)運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第24頁!節(jié)整數(shù)規(guī)劃的特點及作用第四章整數(shù)規(guī)劃及分配問題運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第25頁!一、整數(shù)規(guī)劃的特點及作用

1.2

0-1整數(shù)規(guī)劃某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點）Ai供選擇。規(guī)定在東區(qū)，由A1，A2，A3三個點中至多選兩個；在西區(qū)，由A4，A5兩個點中至少選一個；在南區(qū)，由A6，A7兩個點中至少選一個。如選用Ai點，設(shè)備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問：應(yīng)如何選址，可使年利潤為最大？運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第26頁!一、整數(shù)規(guī)劃的特點及作用

1.3整數(shù)規(guī)劃的作用0-1整數(shù)規(guī)劃在管理領(lǐng)域具有重要作用m個約束條件中只有k個起作用；約束條件的右端項可能是r個值(b1,b2,…br)中的某一個；兩組條件中滿足一組；用以表示含固定費用的函數(shù)。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第27頁!二、分配問題與匈牙利法

2.1分配問題(1)指派n個人去完成n項任務(wù)，使完成n項任務(wù)的總效率最高(或所需總時間最少)，這類問題稱為指派問題或分配問題。安排工作（派工）：有n項加工任務(wù)，怎樣指派到n臺機床上完成；有n條航線，怎樣指定n艘船去航行的；……運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第28頁!二、分配問題與匈牙利法

2.2分配問題實例(1)例：有一份中文說明書，需要譯成英、日、德、俄四種文字。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下，問應(yīng)指派何人去完成工作，使所需總時間最少?

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第29頁!二、分配問題與匈牙利法

2.2分配問題實例(3)某項任務(wù)只能由1人完成；某人只能完成1項任務(wù)。

建立整數(shù)規(guī)劃模型分配問題是0-1整數(shù)規(guī)劃的特例，也是運輸問題的特例；n=m,aj=bj=1。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第30頁!二、分配問題與匈牙利法

2.3匈牙利法的基本思想如果效率矩陣的所有元素aij≥0,而其中存在一組位于不同行不同列的零元素，則只要令對應(yīng)于這些零元素位置的xij=1，其余的xij=0，則所得到的可行解就是問題的最優(yōu)解。顯然令x11=1,x23=1,x32=1,x44=1，即將項工作分配給甲，第二項給丙，第三項給乙，第四項給丁。這時完成總工作的時間為最少。如何尋找這組位于不同行不同列的零元素？運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第31頁!二、分配問題與匈牙利法

2.4匈牙利法實例(1)

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119步：找出每行的最小元素，每行對應(yīng)減去這個元素。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第32頁!二、分配問題與匈牙利法

2.4匈牙利法實例(3)第三步：從行開始，若該行只有一個零元素，對零元素打上()括號，表示行所代表的任務(wù)已指派。用直線劃去其所在列；若該行沒有零元素或有兩個以上零元素(已劃去的不計在內(nèi))，則轉(zhuǎn)下一行，依次進行到最后一行為止。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第33頁!二、分配問題與匈牙利法

2.4匈牙利法實例(5)效率矩陣每行都有一個打()的零元素，這些零元素都位于不同行不同列，令對應(yīng)打()零元素的xij=1

就得到最優(yōu)解；矩陣中所有零元素或被劃去，或被打上()，但打()的零元素少于m個，這時轉(zhuǎn)第四步。打()的零元素小于m，但未被劃去的零元素之間存在閉回路。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第34頁!二、分配問題與匈牙利法

2.4匈牙利法實例(7)第四步：繼續(xù)按照定理1，對矩陣進行變換。從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù)k；對矩陣的每行，當該行有直線覆蓋時，令ui=0，無直線覆蓋的，令ui=k；對矩陣中有直線覆蓋的列，令vj=

-k，對無直線覆蓋的列，令vj=0。只有一條直線覆蓋的元素保持不變運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第35頁!二、分配問題與匈牙利法

2.5人數(shù)和任務(wù)數(shù)不相等的分配問題有四項工作分配給六個人去完成，每個人分別完成各項工作的時間如下，依然規(guī)定每個人完成一項工作。每項工作只交給一個人去完成。即六個人中挑選哪四個人去完成，花費時間最少。

工作人IIIIIIIV123456373655616427245346648732

工作人IIIIIIIVVVI123456373655616427245346648732000000000000運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第36頁!第四章整數(shù)規(guī)劃及分配問題

作業(yè)一求下面指派問題的最優(yōu)解運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第37頁!三、分枝定界法

3.1分枝定界法的基本思想分枝定界法可用于全部類型的整數(shù)規(guī)劃問題。設(shè)有最大化的整數(shù)規(guī)劃問題A，對應(yīng)的線性規(guī)劃為問題B，從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標函數(shù)必是A的最優(yōu)目標函數(shù)z*的上界，記作；而A的任意可行解的目標函數(shù)值將是z*的下界。分支定界法就是將B的可行域分成子區(qū)域(稱為分枝)的方法，逐步減小和增大上、下界，最終得到整數(shù)規(guī)劃問題A的z*。運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第38頁!分枝：在B的最優(yōu)解中，任取一個非整數(shù)變量，如x2=2.5；因x2的最近鄰整數(shù)解為x2=2或x2=3，其最優(yōu)整數(shù)解區(qū)間只能是x2≥3或x2≤2。對B分別加上約束條件x2≥3和x2≤2，可得到兩個子問題B1和B2。三、分枝定界法

3.2分枝定界法實例(2)運籌學(xué)——整數(shù)規(guī)劃與分配問題共43頁，您現(xiàn)在瀏覽的是第39頁!三、分枝定界法

3.2分枝定