物流運(yùn)籌學(xué)課件 第3章 整數(shù)規(guī)劃

第三章整數(shù)規(guī)劃目錄3.1整數(shù)規(guī)劃問題的提出3.2整數(shù)規(guī)劃概述3.3分枝定界法3.4隱枚舉法與0-1規(guī)劃問題3.5匈牙利法與指派問題3.6整數(shù)規(guī)劃問題的應(yīng)用3.1整數(shù)規(guī)劃問題的提出在前面討論的線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問題，常有要求解答必須是整數(shù)的情形(稱為整數(shù)解)。例如，所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)或裝貨的車數(shù)等，分?jǐn)?shù)或小數(shù)的解答就不合要求。為了滿足整數(shù)解的要求，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”就可以了。但這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪?；或雖是可行解，但不一定是最優(yōu)解。因此，對(duì)求最優(yōu)整數(shù)解的問題，有必要另行研究。我們稱這樣的問題為整數(shù)線性規(guī)劃(integerlinearprogramming)，簡(jiǎn)稱ILP，整數(shù)線性規(guī)劃是最近幾十年來發(fā)展起來的規(guī)劃論中的一個(gè)分支。問題舉例某集裝箱運(yùn)輸公司，箱型標(biāo)準(zhǔn)體積24m3，重量13T,現(xiàn)有兩種貨物可以裝運(yùn)，甲貨物體積5m3、重量2T、每件利潤(rùn)2000元；乙貨物體積4m3、重量5T、每件利潤(rùn)1000元，如何裝運(yùn)獲利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且為整數(shù)解此LP問題，得：X1=4.8，X2=0顯然不是可行解和一般線性規(guī)劃問題的區(qū)別x1=4.8，x2=0，maxz=96若考慮用“四舍五入”的方法化整，能得到整數(shù)最優(yōu)解嗎？取x1=5，x2=0，不滿足約束條件5x1+4x2≤24取x1=4，x2=0，滿足約束條件，maxz=80取x1=4，x2=1，也滿足約束條件，maxz=90可見，僅用四舍五入的取整法，不一定能求到最優(yōu)解。因此，需要采用其他方法來求解。圖解法：x1x243210124.8①2.6②(4,1)

∴

x1*=4x2*=1zI*=903.2整數(shù)規(guī)劃概述整數(shù)規(guī)劃是線性規(guī)劃的延伸，指全部或者一部分決策變量要求取整數(shù)值的線性問題。分類：純整數(shù)規(guī)劃：全部決策變量都要求取整數(shù)混合整數(shù)規(guī)劃：僅部分決策變量取整數(shù)0-1整數(shù)規(guī)劃：全部決策變量只能取值0或1的整數(shù)規(guī)劃（指派問題）求解方法：分枝定界法、割平面法、隱枚舉法、匈牙利法3.3分枝定界法在求解整數(shù)線性規(guī)劃時(shí)，如果可行域是有界的，首先容易想到的方法就是窮舉變量的所有可行的整數(shù)組合，就如圖解法中畫出所有“×”號(hào)的點(diǎn)那樣，然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解。對(duì)于小型的問題，變量數(shù)很少，可行的整數(shù)組合數(shù)也是很小時(shí)，這個(gè)方法是可行的，也是有效的。對(duì)于大型的問題，可行的整數(shù)組合數(shù)是很大的。例如指派問題(這也是整數(shù)線性規(guī)劃)中，將n項(xiàng)任務(wù)指派n個(gè)人去完成，不同的指派方案共有n!種，當(dāng)n=10，這個(gè)數(shù)就超過300萬；當(dāng)n=20，這個(gè)數(shù)就超過2×1018，如果一一計(jì)算，就是用每秒百萬次的計(jì)算機(jī)，也要幾萬年的功夫，很明顯，解這樣的題，窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。分枝定界法(branchandboundmethod)就是其中的一個(gè).分枝定界法可用于解純整數(shù)或混合的整數(shù)線性規(guī)劃問題。在20世紀(jì)60年代初由LandDoig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)線性規(guī)劃的重要方法。3.3.1基本思路根據(jù)某種策略將原問題對(duì)應(yīng)的、不考慮整數(shù)要求的線性規(guī)劃問題（松弛問題）的可行域分解為越來越小的子域，并檢查每個(gè)子域內(nèi)整數(shù)解的情況，直到找到最優(yōu)的整數(shù)解或證明整數(shù)解不存在。分枝：分解可行域在松弛問題的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以［bj］表示小于bj的最大整數(shù)。并構(gòu)造兩個(gè)約束條件xj≤［bj］和xj≥［bj］+1定界：不斷尋找更好的整數(shù)解來修正問題的上下界3.3.2求解步驟設(shè)整數(shù)規(guī)劃問題對(duì)應(yīng)的松弛問題為A，用單純形法求出其最優(yōu)解?？赡苡腥缦虑闆r：?jiǎn)栴}A沒有可行解，則整數(shù)規(guī)劃問題無解，停止計(jì)算問題A有最優(yōu)整數(shù)解，且同為整數(shù)規(guī)劃問題的解，停止計(jì)算問題A有最優(yōu)解，但非整數(shù)解。則分枝，不考慮整數(shù)條件求解這兩個(gè)后繼問題A1和A2。以每個(gè)后繼問題為一分枝標(biāo)明求解結(jié)果，若無整數(shù)解，則繼續(xù)分枝，直到至少得到一個(gè)最優(yōu)目標(biāo)函數(shù)整數(shù)值。以此最優(yōu)目標(biāo)函數(shù)整數(shù)值為界（定界）若各分枝的值劣于界，則剪掉不再計(jì)算，否則繼續(xù)分枝，定界。例：分枝定界法求解思路：切割可行域，去掉非整數(shù)點(diǎn)。一次分枝變成兩個(gè)可行域，分別求最優(yōu)解例

maxZ=20x1+10x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且為整數(shù)解：先不考慮整數(shù)要求，解相應(yīng)的LP問題，得：x1=4.8x2=0Z=96不是可行解

Z=96是IP問題的上界，記為：Z=96分枝定界法（續(xù)）X1=4.8不符合要求，切掉4—5之間的可行域，可行域變成兩塊，即原有約束條件再分別附加約束條件x1

≤4和x1≥5原問題分解為兩個(gè)maxZ=20x1+10x2

maxZ=20x1+10x25x1+4x2≤245x1+4x2≤242x1+5x2

≤13(IP1)2x1+5x2

≤13(IP2)x1

≤4x1≥5x1.x2

≥0且為整數(shù)x1.x2

≥0且為整數(shù)分枝定界法（續(xù)）不考慮整數(shù)要求，解相應(yīng)LP問題。解IP1得：x1=4,x2=1z=90

解IP2得：無可行解此時(shí)可以斷定IP問題的下界為90，記為Z=90

由于目前的分枝末梢最大值是90，故IP問題的上界便是90。由于Z=Z，此時(shí)已得IP問題的最優(yōu)解，即x1=4,x2=1,Z=90分枝定界法的解題步驟1、不考慮整數(shù)約束，解相應(yīng)LP問題2、檢查是否符合整數(shù)要求，是，則得最優(yōu)解，完畢。否則，轉(zhuǎn)下步3、任取一個(gè)非整數(shù)變量xi=bi，構(gòu)造兩個(gè)新的約束條件：xi

≤[bi],xi

≥[bi]+1,分別加入到上一個(gè)LP問題，形成兩個(gè)新的分枝問題。4、不考慮整數(shù)要求，解分枝問題。若整數(shù)解的Z值>所有分枝末梢的Z值，則得最優(yōu)解。否則，取Z值最大的非整數(shù)解，繼續(xù)分解，Goto3思考題：求下面的整數(shù)規(guī)劃問題maxz=3x1+2x22x1+3x2≤142x1+x2

≤9x1.x2

≥0且為整數(shù)分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥43.4隱枚舉法與0-1規(guī)劃問題3.4.10-1規(guī)劃問題及模型1、0-1規(guī)劃問題的概念在整數(shù)規(guī)劃問題中，若變量取值為0或者1，則為0-1規(guī)劃問題。

0-1變量通常用來表示邏輯性選擇的決策。2、0-1變量的應(yīng)用例1：某油田在10個(gè)有油氣構(gòu)造處要選擇若干個(gè)鉆探采油，設(shè)第j個(gè)構(gòu)造開采時(shí)需投資aj元，投產(chǎn)后預(yù)計(jì)年收益為cj元，若該油田投資的總限額為b元，問：應(yīng)選擇哪幾個(gè)構(gòu)造開采最為有利？設(shè)xj=10---選擇開采第j個(gè)構(gòu)造---不選擇開采第j個(gè)構(gòu)造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年總收益----投資額限制（1）表示選擇性決策（投資場(chǎng)所的選定——相互排斥的計(jì)劃）例2

某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置(點(diǎn))Ai(i=1，2，…，7)可供選擇。規(guī)定：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大?解題時(shí)先引入0-1變量xi

(=1,2，…，7)

于是問題可列成：

例3.在本章開始的集裝箱運(yùn)輸中，關(guān)于運(yùn)貨的體積限制為5x1+4x2≤24(3-1)今設(shè)運(yùn)貨有車運(yùn)和船運(yùn)兩種方式，上面的條件系用車運(yùn)時(shí)的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為7x1+3x2≤45(3-2)這兩條件是互相排斥的。為統(tǒng)一在一個(gè)問題中，引入0-1變量y，令（2）表示選擇性約束

于是(3-1)式和(3-2)式可由下述的條件

(3-3)式和(3-4)式來代替：

5x1+4x2≤24+yM(3-3)

7x1+3x2≤45+(1-y)M(3-4)

其中M是充分大的數(shù)?？沈?yàn)證，當(dāng)y=0時(shí)，(3-3)式就是(3-1)式，而(3-14)式自然成立，因而是多余的。當(dāng)y=1時(shí)(3-4)式就是(3-2)式，而(3-3)式是多余的。引入的變量y不必出現(xiàn)在目標(biāo)函數(shù)內(nèi)，即認(rèn)為在目標(biāo)函數(shù)式內(nèi)y的系數(shù)為0。如果有m個(gè)互相排斥的約束條件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m為了保證這m個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量yi(i=1,2,…，m)和一個(gè)充分大的常數(shù)M，而下面這一組m+1個(gè)約束條件αi1x１+αi2x2+…+αinxn≤bi+yiM，i=1,2,…，m(3-5)y1+y2+…+ym=m-1(3-6)

就合于上述要求。這是因?yàn)?，由?3-6)式，m個(gè)yi中只有一個(gè)能取0值，設(shè)yi*=0，代入(3-5)式，就只有i=i*的約束條件起作用，而別的式子都是多余的。例4：例1中，如果在開采中需用電力，解決的方案或由電網(wǎng)供電或由自備的柴油機(jī)發(fā)電。已知第j個(gè)構(gòu)造開采時(shí)每天耗電量為dj度，電網(wǎng)每天供電量限制為f度。當(dāng)使用自備柴油機(jī)發(fā)電時(shí)，每度電平均耗油0.3公斤，而柴油供應(yīng)量限額為每天p公斤。試在模型中表示出該限制條件。采用電網(wǎng)供電：∑djxjf采用自備柴油機(jī)發(fā)電：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正數(shù)(3)關(guān)于固定費(fèi)用的問題

在討論線性規(guī)劃時(shí)，有些問題是要求使成本為最小。那時(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用(固定成本)的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)線性規(guī)劃來解決，見下例。

例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定投資高的生產(chǎn)方式(選購自動(dòng)化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就降低；反之，如選定投資低的生產(chǎn)方式，將來分配到每件產(chǎn)品的變動(dòng)成本可能增加，所以必須全面考慮。今設(shè)有三種方式可供選擇，令xj表示采用第j種方式時(shí)的產(chǎn)量；cj表示采用第j種方式時(shí)每件產(chǎn)品的變動(dòng)成本；kj表示采用第j種方式時(shí)的固定成本。為了說明成本的特點(diǎn)，暫不考慮其他約束條件。采用各種生產(chǎn)方式的總成本分別為在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問題中討論，現(xiàn)引入0-1變量yj，令于是目標(biāo)函數(shù)minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)(3-7)式這個(gè)規(guī)定可由以下3個(gè)線性約束條件表示：xj≤yjM，j=1,2,3(3-8)

其中M是個(gè)充分大的常數(shù)。(3-8)式說明，當(dāng)xj＞0時(shí)yj必須為1；當(dāng)xj=0時(shí)只有yj為0時(shí)才有意義，所以(3-8)式完全可以代替(3-7)式

因此，該整數(shù)規(guī)劃的數(shù)學(xué)模型為：minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)

xj≤yjM，

st.xj≥0且為整數(shù)，j=1,2,3

yj=0或1，j=1,2,3

其中M是個(gè)充分大的常數(shù)。3.4.2隱枚舉法隱枚舉法是求解0-1規(guī)劃問題的一種簡(jiǎn)便方法本質(zhì)也是分枝定界法隱枚舉法類似于窮舉法，區(qū)別在于：隱枚舉法不需要把全部可行解一一列舉，而是通過分析判斷，排除一些變量組合，從而得出最優(yōu)方案。計(jì)算步驟①化標(biāo)準(zhǔn)形(隱枚舉法)：1)目標(biāo)函數(shù)極小化

2)約束條件化成

3)使目標(biāo)函數(shù)系數(shù)皆為非負(fù),若xj系數(shù)為負(fù)值,則令xj=1-xj 4)使目標(biāo)函數(shù)按變量系數(shù)由小→大順序排列，約束條件變 量排列的順序要與之對(duì)應(yīng)。（能減少運(yùn)算量，讓最優(yōu)解較早出現(xiàn)）②令所有變量xj=0，計(jì)算邊界目標(biāo)函數(shù)值z(mì)，檢查是否滿足所有約束條件，若滿足，即為最優(yōu)解；否則，分枝計(jì)算。③分枝：按變量次序依次令各變量取“1”和“0”值，計(jì)算邊界值，然后檢查是否滿足所有約束，若滿足，轉(zhuǎn)下步；否則繼續(xù)分枝。④剪枝：在得到一個(gè)可行解后，分枝過程中要進(jìn)行剪枝工作。 (a)對(duì)可行解，保留邊界值最小的一枝zmin，其余全剪掉； (b)>zmin分枝，剪掉； (c)能判斷出為無可行解的分枝，剪掉； (d)非上述情況，繼續(xù)分枝。 例：求解下述0-1規(guī)劃問題：Maxz=8x1+2x2-4x3-7x4-5x5 st.3x1+3x2+x3+2x4+3x5

4 5x1+3x2-2x3-x4+x54 xj=0或1(j=1,2,3,4,5)1)目標(biāo)函數(shù)極小化:minz=-8x1-2x2+4x3+7x4+5x5①化標(biāo)準(zhǔn)形：2)約束條件：-3x1-3x2-x3-2x4-3x5

-4 -5x1-3x2+2x3+x4-x5-4 xj=0或1(j=1,2,3,4,5)3)使目標(biāo)函數(shù)系數(shù)皆為正：令x1=1-x1，x2=1-x2

minz=-8+8x1-2+2x2+4x3+7x4+5x5st.-3+3x1-3+3x2-x3-2x4-3x5

-4-5+5x1-3+3x2+2x3+x4-x5-4x1,x2,xj=0或1(j=3,4,5)4)變量按順序排列：minz=2x2+4x3+5x5+7x4+8x1-10st.3x2-x3-3x5-2x4+3x1

23x2+2x3-x5+x4+5x14x1,x2,xj=0或1(j=3,4,5)xj=0或1求解圖示：1234567891011z=-10z

=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z=-3√×××××例6：某公司欲對(duì)三個(gè)項(xiàng)目投資，投資金額與收益如下表所示，問應(yīng)對(duì)哪幾個(gè)項(xiàng)目投資，獲利最大？投資年度項(xiàng)目投資金額IIIIII10425251273403745136純利潤(rùn)20816例6解：

0當(dāng)項(xiàng)目未被選中投資

1當(dāng)項(xiàng)目被選中投資

maxZ=20x1+8x2+16x3

4x2+2x3≤

5

st.5x1+x2+2x3

≤

7

4x1+3x3≤

7

5x1+x2+3x3≤

6

xj=0或1j=1，2,…,3建模：設(shè)xj=第一步：將決策變量按系數(shù)從小到大的順序排列（若求最小化，則從大到小排列）

maxZ=8x2+16x3+20x1

4x1+2x2+0x1≤

5

st.x2+2x3+5x1

≤

7

0x2+3x3+

4x1≤

7

x2+3x3+5x1≤

6

xj=0或1

j=1，2,…,3求解第二步：求解過程如下表所示（x2,x3,x1）Z值（1，1，1）X

XX44（0，1，1）X36（1，0，1）28（1，1，0）X24（1，0，0）

8（0，1，0）

16（0，0，1）

20（0，0，0）

03.5匈牙利法與指派問題3.5.1指派問題在物流活動(dòng)中經(jīng)常遇到這樣的問題：需完成n項(xiàng)運(yùn)輸任務(wù)，恰好有n輛車可承擔(dān)這些任務(wù)。由于車型、載重以及司機(jī)對(duì)道路熟悉程度等方面的不同，效率也不同。于是產(chǎn)生應(yīng)指派哪輛車去完成哪項(xiàng)運(yùn)輸任務(wù)，使完成總效率最高(或所需費(fèi)用最小)。這類問題稱為指派問題或分派問題(assignmentproblem)。例7：某物流公司現(xiàn)有四項(xiàng)運(yùn)輸任務(wù)A、B、C、D，現(xiàn)有甲、乙、丙、丁四輛車，他們完成任務(wù)所需時(shí)間如表所示。問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？完成任務(wù)所需時(shí)間表任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119類似有：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上分別完成的問題；有n條航線，怎樣指定n艘船去航行問題……。對(duì)應(yīng)每個(gè)指派問題，需有類似表1那樣的數(shù)表，稱為效率矩陣或系數(shù)矩陣，其元素cij＞0(i,j=1,2，…，n)表示指派第i人去完成第j項(xiàng)任務(wù)時(shí)的效率(或時(shí)間、成本等)。解題時(shí)需引入變量xij；其取值只能是1或0。并令

給例7建立模型：設(shè)xij=10A：x11+x12+x13+x14=1

B：x21+x22+x23+x24=1C：x31+x32+x33+x34=1D：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1?。簒14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)minz=cijxij

(cij---效率)i=1j=144若第i項(xiàng)工作交與第j個(gè)人完成若第i項(xiàng)工作不交與第j個(gè)人完成指派問題一般數(shù)學(xué)模型結(jié)構(gòu)：設(shè)有m項(xiàng)工作要交與m個(gè)人完成，其中第i項(xiàng)工作交與第j個(gè)人完成時(shí)所需花費(fèi)的時(shí)間為

cij。規(guī)定每項(xiàng)工作只能交與其中的一個(gè)人完成，而每個(gè)人只能完成其中的一項(xiàng)工作。問：如何分配，可使所需的總時(shí)間最少？①②③④顯然，解矩陣(xij)中各行各列的元素之和都是1。但這不是最優(yōu)。約束條件②說明第j項(xiàng)任務(wù)只能由1人去完成；約束條件③說明第i人只能完成1項(xiàng)任務(wù)。滿足約束條件②～④的可行解xij也可寫成表格或矩陣形式，稱為解矩陣。如例7的一個(gè)可行解矩

指派問題解的特點(diǎn)指派問題的最優(yōu)解有這樣性質(zhì)，若從系數(shù)矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)，那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。3.5.2匈牙利法以下用例7來說明指派問題的解法——匈牙利法。

第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。

(1)從系數(shù)矩陣的每行元素減去該行的最小元素；

(2)再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。

若某行(列)已有0元素，那就不必再減了。

例7的計(jì)算為

行列都有零元素第二步：進(jìn)行試指派，以尋求最優(yōu)解。為此，按以下步驟進(jìn)行。經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個(gè)獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。當(dāng)n較小時(shí)，可用觀察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，常用的步驟為：

(1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作◎。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列(行)的其他0元素，記作Φ。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。(2)給只有一個(gè)0元素列(行)的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作Φ。(3)反復(fù)進(jìn)行(1)，(2)兩步，直到所有0元素都被圈出和劃掉為止。

(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)(表示對(duì)這個(gè)可以從兩項(xiàng)任務(wù)中指派其一)。這可用不同的方案去試探。從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其他0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。(5)若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m＜n，則轉(zhuǎn)入下一步?，F(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運(yùn)算。按步驟(1)，先給b22加圈，然后給b31加圈，劃掉b11，b41；按步驟(2)，給b43加圈，劃掉b44，最后給b14加圈，得到

01370606905320100這表明：指定甲完成任務(wù)D，乙完成任務(wù)B，丙完成任務(wù)A，丁完成任務(wù)C。所需總時(shí)間最少minz=28ABCD甲乙丙丁3.6整數(shù)規(guī)劃模型的應(yīng)用例1：在未來四個(gè)月中，某制鞋廠必須按時(shí)完成下述合同要求，第一個(gè)月300雙，第二個(gè)月500雙，第三個(gè)月100雙，第四個(gè)月100雙。在一月初，工廠已有50雙鞋（以前的存貨）和3名工人，每名工人的月薪為1500元，每月可工作160小時(shí)（正常工作時(shí)間）。一名工人最多還可有20小時(shí)的加班工作時(shí)間（規(guī)定），在加班工作時(shí)，每小時(shí)需付25元的加班費(fèi)用。制作一雙鞋需耗費(fèi)4個(gè)工時(shí)和5元的原料費(fèi)。在每月的開始，可以租用和解雇工人。每雇用一名工人需支付1600元的費(fèi)用，每解雇一名工人需支付2000元的解雇費(fèi)用。在每月末，要為留在倉庫里未交貨的每雙鞋支付30元的保管維護(hù)費(fèi)用。一個(gè)月生產(chǎn)的產(chǎn)品可用于滿足多個(gè)月的需求。試用ILP方法確定最佳的生產(chǎn)計(jì)劃和用工政策。問題分析：需要解決的問題：每月租進(jìn)、解雇、使用的工人數(shù)每月所需的加班時(shí)間每月在正常時(shí)間、加班時(shí)間生產(chǎn)的鞋子的數(shù)量每月開始和結(jié)束時(shí)庫存鞋子的數(shù)量費(fèi)用明細(xì)：雇工費(fèi)、解雇費(fèi)、用工費(fèi)、加班費(fèi)、原料費(fèi)月初人數(shù)本月雇用本月解雇本月使用用工過程圖示：生產(chǎn)過程圖示：正常生產(chǎn)加班生產(chǎn)月初庫存月末庫存交貨數(shù)量工人數(shù)鞋子數(shù)建模思路：每月可用工人≥0每月庫存鞋子≥0可用工人數(shù)=月初數(shù)+租進(jìn)數(shù)-解雇數(shù)=月末數(shù)月末庫存量=月初庫存+正常生產(chǎn)+加班生產(chǎn)-交貨量目標(biāo)函數(shù)=總費(fèi)用 =月薪+雇用費(fèi)+解雇費(fèi)+加班費(fèi)+原料費(fèi)+庫存費(fèi)例2：某海軍部隊(duì)在三個(gè)征兵中心征招新兵。新兵必須送到三個(gè)海軍訓(xùn)練基地中的一個(gè)進(jìn)行訓(xùn)練，從每個(gè)征兵中心運(yùn)送一個(gè)新兵至某一個(gè)訓(xùn)練基地的費(fèi)用如表1所示（單位：元）。

每年在中心1征招1000名士兵，中心2征召600名，中心3征召700名?；?可訓(xùn)練1000名，基地2可訓(xùn)練800名，基地3可訓(xùn)練700名。fromtoBase1Base2Base3Center1Center2Center3240200300300400220300400250新兵受訓(xùn)后，要送到海軍部隊(duì)。運(yùn)送時(shí)可采用小船或大船兩種工具，共有7條小船和3條大船可供使用。若使用小船，則每條船要花費(fèi)5000元加上每海里2元的費(fèi)用；使用大船要花費(fèi)10000元加上每海里3元的費(fèi)用。一條小船可運(yùn)送200人，沿途最多可經(jīng)過2個(gè)訓(xùn)練基地；一條大船可運(yùn)送500人，最多可經(jīng)過3個(gè)訓(xùn)練基地?？赡艿暮骄€如表2中所示。現(xiàn)問，應(yīng)怎樣決策，能使發(fā)生的總費(fèi)用最少？表1途徑訓(xùn)練基地航程（海里）航線1234567

B—1—B370B—1—2—B515B—2—3—B665B—2—B460B—3—B600B—1—3—B640B—1—2—3—B720表2需要解決的問題：(1)Centeri→Basej運(yùn)送的人數(shù)(2)Basej實(shí)際訓(xùn)練人數(shù)(3)第i航線運(yùn)送第j基地人數(shù)(4)第i航線使用小船數(shù)量(5)第i航線使用大船數(shù)量(6)征兵中心至訓(xùn)練基地運(yùn)送費(fèi)用(7)訓(xùn)練基地至海軍部隊(duì)運(yùn)送費(fèi)用(8)總費(fèi)用例3：倉庫位置問題韓德公司有五個(gè)生產(chǎn)番茄醬的工廠，每個(gè)工廠的生產(chǎn)能力如表1所示。生產(chǎn)出來的番茄醬可儲(chǔ)存在三個(gè)成品庫中，從各工廠運(yùn)送一噸產(chǎn)品到各成品庫的費(fèi)用如表2所示。由于某些因素，公司銷售看淡，現(xiàn)只有四家客戶，其需求量如