理學(xué)整數(shù)規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1理學(xué)整數(shù)規(guī)劃理學(xué)整數(shù)規(guī)劃2第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃第1頁(yè)/共64頁(yè)引例：某廠利用集裝箱托運(yùn)甲、乙兩種貨物，引例：某廠利用集裝箱托運(yùn)甲、乙兩種貨物，每箱體積重量每箱體積重量 、可獲利潤(rùn)及托運(yùn)限制如下：、可獲利潤(rùn)及托運(yùn)限制如下：體積體積重量重量利潤(rùn)利潤(rùn)甲甲5220乙乙4510托運(yùn)限制托運(yùn)限制2413兩種貨物各托運(yùn)多少箱使利潤(rùn)最大？?jī)煞N貨物各托運(yùn)多少箱使利潤(rùn)最大？第2頁(yè)/共64頁(yè)Max Z= 20 x1 +10 x25x1 +4x2242x1 +5x213x1 , x20 x2x1244521 xx135221 xx0Ax1 , x2 為整數(shù)為整數(shù)ZA=96A(4.8, 0 )第3頁(yè)/

2、共64頁(yè)Max Z= 20 x1 +10 x25x1 +4x2242x1 +5x213x1 , x20 x2x1(4.8, 0 ) AZA=96x1 , x2 為整數(shù)為整數(shù)(4,0) Z=80(5,0)(4,1) max Z=90第4頁(yè)/共64頁(yè)第一節(jié)第一節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃問(wèn)題一、整數(shù)規(guī)劃問(wèn)題 整數(shù)規(guī)劃問(wèn)題（整數(shù)規(guī)劃問(wèn)題（IP）:是指要求部分是指要求部分或全部決策變量的取值為整數(shù)的規(guī)劃問(wèn)或全部決策變量的取值為整數(shù)的規(guī)劃問(wèn)題。題。 松弛問(wèn)題：松弛問(wèn)題：不考慮整數(shù)條件，由余不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題。

3、題。 重點(diǎn)研究：重點(diǎn)研究：整數(shù)線性規(guī)劃問(wèn)題整數(shù)線性規(guī)劃問(wèn)題第5頁(yè)/共64頁(yè)二、整數(shù)線性規(guī)劃問(wèn)題的模型二、整數(shù)線性規(guī)劃問(wèn)題的模型j=1,2,njnjjxcZ1max(min)0),(1jinjjijxbxai=1,2,mxj 中取部分或全部為整數(shù)中取部分或全部為整數(shù)第6頁(yè)/共64頁(yè)三、整數(shù)規(guī)劃問(wèn)題的類(lèi)型：三、整數(shù)規(guī)劃問(wèn)題的類(lèi)型：1. 純整數(shù)規(guī)劃問(wèn)題純整數(shù)規(guī)劃問(wèn)題第7頁(yè)/共64頁(yè)minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8x1 8x1 + x2 8x1 + x2+ x3 7x1+x2+ x3 + x4 1x2+ x3 + x4 + x5 2x3+ x4 + x5 +x6 1x

4、4 + x5 +x6 + x7 5x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6x8 6 xi 0 (i =1,8)且為整數(shù)且為整數(shù)第8頁(yè)/共64頁(yè)2. 0-1型整數(shù)線性規(guī)劃型整數(shù)線性規(guī)劃例例2：現(xiàn)有資金總額為：現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)可供選擇的投資項(xiàng)目有目有n個(gè)，項(xiàng)目個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別所需投資額和預(yù)期收益分別為為aj和和cj,此外，因種種原因，有此外，因種種原因，有3個(gè)附加條件：個(gè)附加條件：若選擇項(xiàng)目若選擇項(xiàng)目1必須同時(shí)選擇項(xiàng)目必須同時(shí)選擇項(xiàng)目2，反之，不，反之，不一定；項(xiàng)目一定；項(xiàng)目3和項(xiàng)目和項(xiàng)目4中至少選擇一個(gè)；第三，中至少

5、選擇一個(gè)；第三，項(xiàng)目項(xiàng)目5、6、7中恰好選擇兩個(gè)。應(yīng)當(dāng)怎樣選擇中恰好選擇兩個(gè)。應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？投資項(xiàng)目，才能使總預(yù)期收益最大？第9頁(yè)/共64頁(yè)1 對(duì)項(xiàng)目對(duì)項(xiàng)目 j 投資投資0 對(duì)項(xiàng)目對(duì)項(xiàng)目 j 不投資不投資 xj=Max Z=cjxjajxjBx2 x1x3+ x4 1x5+ x6 +x7=2xj=0或或1（j=1,2,n）第10頁(yè)/共64頁(yè)3. 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃 例例3 工廠工廠A1和和A2生產(chǎn)某種物資，由于生產(chǎn)某種物資，由于該種物資供不應(yīng)求，還需要建一家工廠。由該種物資供不應(yīng)求，還需要建一家工廠。由兩個(gè)待選方案兩個(gè)待選方案A3和和A4。物資需求地為物資需

6、求地為Bj(j=1,2,3,4)。工廠工廠A3和和A4的生產(chǎn)費(fèi)用估計(jì)的生產(chǎn)費(fèi)用估計(jì)為為1200萬(wàn)元或萬(wàn)元或1500萬(wàn)元。選擇哪一個(gè)方案才萬(wàn)元。選擇哪一個(gè)方案才能使總費(fèi)用（包括物資運(yùn)費(fèi)和新工廠的生產(chǎn)能使總費(fèi)用（包括物資運(yùn)費(fèi)和新工廠的生產(chǎn)費(fèi)用）最小。費(fèi)用）最小。第11頁(yè)/共64頁(yè)B1B2B3B4生產(chǎn)能力生產(chǎn)能力A12934400A28357600A37612200A44525200需求量需求量350400300150第12頁(yè)/共64頁(yè)y 0-1變量變量y=1 若建工廠若建工廠A30 若建工廠若建工廠A4設(shè)設(shè)xij為由為由Ai送往送往Bj 的物資數(shù)量。的物資數(shù)量。則總費(fèi)用為則總費(fèi)用為:min Z=c

7、ijxij +1200y+1500(1-y)第13頁(yè)/共64頁(yè)x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200yx41+ x42+ x43+ x44=200(1-y)xij0, y=0或或1第14頁(yè)/共64頁(yè)第二節(jié)第二節(jié) 解純整數(shù)規(guī)劃的割平面解純整數(shù)規(guī)劃的割平面法法一、基本思想一、基本思想 找到純整數(shù)線性規(guī)劃的松弛問(wèn)題，不考找

8、到純整數(shù)線性規(guī)劃的松弛問(wèn)題，不考慮整數(shù)約束條件，但增加線性約束條件，將慮整數(shù)約束條件，但增加線性約束條件，將松弛問(wèn)題的可行域切割一部分，但不切割掉松弛問(wèn)題的可行域切割一部分，但不切割掉任何整數(shù)解，只切割掉包括松弛問(wèn)題的最優(yōu)任何整數(shù)解，只切割掉包括松弛問(wèn)題的最優(yōu)解在內(nèi)的非整數(shù)解。解在內(nèi)的非整數(shù)解。第15頁(yè)/共64頁(yè)二、割平面求解舉例二、割平面求解舉例Max Z=x1+x2-x1+x213x1+x2 4x1 , x20且為整數(shù)且為整數(shù)松弛問(wèn)題松弛問(wèn)題Max Z=x1+x2-x1+x213x1+x2 4x1 , x20-x1+x2+x3 =13x1+x2 +x4=4x1 , x20第16頁(yè)/共64頁(yè)

9、不考慮整數(shù)解約束，解松弛問(wèn)題的最優(yōu)單純形表為：不考慮整數(shù)解約束，解松弛問(wèn)題的最優(yōu)單純形表為：CBXBb1100 x1x2x3x40 x31-11100 x443101-1-1001x13/410-1/41/41x27/4013/41/4Z=5/2001/21/2x2+3/4x3+1/4x4=7/4x2-1=3/4-3/4x3-1/4x4第17頁(yè)/共64頁(yè)將將 -3x3-x4+x5= -3（切割方程切割方程） 代入最優(yōu)表代入最優(yōu)表CBXBb11000 x1x2x3x4x51x13/410-1/41/401x27/4013/41/400 x5-300-3-11Z=5/200-1/2-1/201x1

10、11001/31/121x2101001/40 x310011-1/3Z=2000-1/3-1/3x2-1=3/4-3/4x3-1/4x43/4-3/4x3-1/4x403-3x3-x403-3x3-x4+x5=0第18頁(yè)/共64頁(yè)MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20 且為整數(shù)且為整數(shù)MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20第19頁(yè)/共64頁(yè)CBXBb11000 x1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/7Z=5/200-5/7

11、0-3/7x1+1/7x3 + 2/7x5=13/7x1+1/7x3 + 2/7x5=1+6/7x1- 1 = 6/7 -（1/7x3 + 2/7x5）6/7 -（1/7x3 + 2/7x5）0-1/7x3 - 2/7x5- 6/7 第20頁(yè)/共64頁(yè)-1/7x3 - 2/7x5- 6/7-1/7x3 - 2/7x5+x6=- 6/7CBXBb110000 x1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/71Z=5/200-5/70-3/70第21頁(yè)/共64頁(yè)CBXBb11

12、0000 x1x2x3x4x5x63x11100001-1x24/5010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4Z=5/200000-17/4-1/4x4 + 1/4x6-3/4余下略余下略第22頁(yè)/共64頁(yè)第三節(jié)第三節(jié) 分支定界法分支定界法一、基本思想一、基本思想 定界：為求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)定界：為求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題劃問(wèn)題(A)，先求出其松弛問(wèn)題（先求出其松弛問(wèn)題（B）的最優(yōu)的最優(yōu)解，作為問(wèn)題解，作為問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值的上界，的最優(yōu)目標(biāo)函數(shù)值的上界，同時(shí)選擇任意整數(shù)可行解作為同時(shí)選擇任意整數(shù)可行解作為A的最優(yōu)目

13、標(biāo)的最優(yōu)目標(biāo)函數(shù)值的下界。函數(shù)值的下界。 分支：將應(yīng)為整數(shù)解，但尚是非整數(shù)解分支：將應(yīng)為整數(shù)解，但尚是非整數(shù)解之一的決策變量取值分區(qū)，并入松弛問(wèn)題中，之一的決策變量取值分區(qū)，并入松弛問(wèn)題中，形成兩個(gè)分支松弛問(wèn)題，分別求解。依結(jié)果形成兩個(gè)分支松弛問(wèn)題，分別求解。依結(jié)果來(lái)調(diào)整上下界。來(lái)調(diào)整上下界。 第23頁(yè)/共64頁(yè)二、舉例二、舉例例例1：A問(wèn)題為問(wèn)題為 B問(wèn)題為問(wèn)題為MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 x1,x2 都為整數(shù)都為整數(shù)MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 第24頁(yè)/共64頁(yè) 問(wèn)題

14、問(wèn)題B x1=4.81 ,x2=1.82 Z=356Z=356 Z=0 問(wèn)題問(wèn)題B1 x1=4,x2=2.1 Z=349 問(wèn)題問(wèn)題B 2 x1=5 ,x2=1.57 Z=341x14x15Z=349 Z=0 x22x23問(wèn)題問(wèn)題B3 x1=4, x2=2 Z=340問(wèn)題問(wèn)題B4 x1=1.42 x2=3 Z=327Z=349 Z=340 x21x22問(wèn)題問(wèn)題B5 x1=5.44 x2=1 Z=308Z*=340問(wèn)題問(wèn)題B6 無(wú)可無(wú)可行解行解第25頁(yè)/共64頁(yè)第四節(jié)第四節(jié) 0-1型整數(shù)規(guī)劃型整數(shù)規(guī)劃一、一、0-1變量的概念變量的概念 0-1變量變量：一種邏輯變量，常用來(lái)表：一種邏輯變量，常用來(lái)表

15、示系統(tǒng)處于某個(gè)特定狀態(tài)，或者決策時(shí)示系統(tǒng)處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。是否取某個(gè)特定方案。 x=1 當(dāng)決策取方案當(dāng)決策取方案P時(shí)時(shí) 0 當(dāng)決策不取方案當(dāng)決策不取方案P時(shí)時(shí)第26頁(yè)/共64頁(yè)二、二、0-1變量的實(shí)際應(yīng)用變量的實(shí)際應(yīng)用1. 制定相互排斥的計(jì)劃制定相互排斥的計(jì)劃例例1：投資場(chǎng)所的選定：投資場(chǎng)所的選定 某公司擬在市東、西、南三區(qū)建立門(mén)市部，擬某公司擬在市東、西、南三區(qū)建立門(mén)市部，擬議中有議中有7個(gè)位置個(gè)位置Ai 可供選擇，規(guī)定：可供選擇，規(guī)定： 在東區(qū)，由在東區(qū)，由A1， A2 ，A3三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由在西區(qū)，由A4， A5 兩點(diǎn)中至

16、少選擇兩點(diǎn)中至少選擇1個(gè)；個(gè)； 在南區(qū)，由在南區(qū)，由 A6， A7 兩點(diǎn)中至少選擇兩點(diǎn)中至少選擇1個(gè)。個(gè)。若選擇若選擇Ai 點(diǎn)，估計(jì)設(shè)備投資為點(diǎn)，估計(jì)設(shè)備投資為bi 元，獲利元，獲利ci ,但投資但投資不能超過(guò)不能超過(guò)B元，如何投資獲利最大？元，如何投資獲利最大？第27頁(yè)/共64頁(yè)x=1 當(dāng)當(dāng)Ai 點(diǎn)被選用時(shí)點(diǎn)被選用時(shí) 0 當(dāng)當(dāng)Ai 點(diǎn)未被選用時(shí)點(diǎn)未被選用時(shí)解：解：Max Z=cixibixiBx1+ x2 +x32 x4+ x5 1 x6+ x7 1 xj=0或或1（i=1,2,n）第28頁(yè)/共64頁(yè)2. 相互排斥的約束條件問(wèn)題相互排斥的約束條件問(wèn)題例：集裝箱運(yùn)貨（用車(chē)運(yùn)或用船運(yùn)）例：集裝箱

17、運(yùn)貨（用車(chē)運(yùn)或用船運(yùn)）車(chē)運(yùn)體積車(chē)運(yùn)體積船運(yùn)體積船運(yùn)體積重量重量利潤(rùn)利潤(rùn)甲甲57220乙乙43510托運(yùn)托運(yùn)限制限制244513兩種貨物各托運(yùn)多少箱可以使利潤(rùn)最大？?jī)煞N貨物各托運(yùn)多少箱可以使利潤(rùn)最大？第29頁(yè)/共64頁(yè)y=1 船運(yùn)船運(yùn) 0 車(chē)運(yùn)車(chē)運(yùn)解：解：5x1+4x224+yM7x1+3x245+(1-y)M第30頁(yè)/共64頁(yè)Max Z=20 x1+10 x25x1+4x224+yM7x1+3x245 +(1-y)M2x1+5x213x1, x20 ，y=0或或1x1, x2為整數(shù)為整數(shù)y=1 船運(yùn)船運(yùn) 0 車(chē)運(yùn)車(chē)運(yùn)解：解：x1 ，x2 分別為甲分別為甲乙兩種貨物的托乙兩種貨物的托運(yùn)數(shù)量運(yùn)數(shù)量

18、第31頁(yè)/共64頁(yè)3. 固定費(fèi)用問(wèn)題固定費(fèi)用問(wèn)題 例：例：有三種資源被用于生產(chǎn)三種產(chǎn)品，有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用售價(jià)、資源單耗資源量、產(chǎn)品單件可變費(fèi)用售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見(jiàn)下表。量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見(jiàn)下表。要求制定一個(gè)生產(chǎn)計(jì)劃使總收益為最大。要求制定一個(gè)生產(chǎn)計(jì)劃使總收益為最大。第32頁(yè)/共64頁(yè) 產(chǎn)品產(chǎn)品資源資源資源量資源量A248500B234300C123100單件可變費(fèi)用單件可變費(fèi)用456固定費(fèi)用固定費(fèi)用100150200單價(jià)單價(jià)81012第33頁(yè)/共64頁(yè)設(shè)設(shè)xj 為生產(chǎn)第為生產(chǎn)第 j 種產(chǎn)品的產(chǎn)量。種產(chǎn)品的產(chǎn)量。y為為0

19、-1變量變量Max Z=4x1+5x2+6x3-100y1-150y2-200y32x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1x2 M2y2x3 M3y3xj 0且為整數(shù)，且為整數(shù)，j=1,2,3yj=0或或1，j=1,2,3第34頁(yè)/共64頁(yè)三、三、0-1型整數(shù)規(guī)劃的解法型整數(shù)規(guī)劃的解法 隱枚舉法隱枚舉法 隱枚舉法隱枚舉法：不同于窮舉法，只檢查變：不同于窮舉法，只檢查變量取值組合的一部分就能找到問(wèn)題的最優(yōu)量取值組合的一部分就能找到問(wèn)題的最優(yōu)解。解題關(guān)鍵是尋找可行解，產(chǎn)生過(guò)濾條解。解題關(guān)鍵是尋找可行解，產(chǎn)生過(guò)濾條件。件。 過(guò)濾條件：過(guò)濾條

20、件：目標(biāo)函數(shù)值優(yōu)于計(jì)算過(guò)的目標(biāo)函數(shù)值優(yōu)于計(jì)算過(guò)的可行解目標(biāo)函數(shù)值?？尚薪饽繕?biāo)函數(shù)值。第35頁(yè)/共64頁(yè)maxZ=3X1 -2X2+5X3X1+ 2X2 - X3 2 X1 + 4X2 +X3 4 X1 + X2 3 4X2 +X3 6 X1 , X2 , X3 = 0 或或 1 第36頁(yè)/共64頁(yè)(x1 , x2 , x3)Z值值約束條件約束條件 過(guò)濾條件過(guò)濾條件（0，0，0）0 Z0（0，0，1）5 Z5（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）8 Z8（1，1，0）1（1，1，1）6第37頁(yè)/共64頁(yè)第五節(jié)第五節(jié) 指派問(wèn)題指派問(wèn)題 一、典型的指派問(wèn)題一、典型的指派問(wèn)題

21、 某單位需完成某單位需完成n項(xiàng)任務(wù)，恰有項(xiàng)任務(wù)，恰有n個(gè)人個(gè)人可以承擔(dān)，由于每個(gè)人的專(zhuān)長(zhǎng)不同，各人可以承擔(dān)，由于每個(gè)人的專(zhuān)長(zhǎng)不同，各人完成任務(wù)的效率不同，各人完成一項(xiàng)任務(wù)完成任務(wù)的效率不同，各人完成一項(xiàng)任務(wù)的同時(shí)，不能同時(shí)去做其它任務(wù)，如何分的同時(shí)，不能同時(shí)去做其它任務(wù)，如何分配任務(wù)會(huì)使所需的時(shí)間最小或成本最低。配任務(wù)會(huì)使所需的時(shí)間最小或成本最低。第38頁(yè)/共64頁(yè) 例：有一份中文說(shuō)明書(shū)，需譯成英、例：有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記做日、德、俄四種文字，分別記做E、J、G、R?，F(xiàn)有甲、乙、丙、丁現(xiàn)有甲、乙、丙、丁4人，他們將中文人，他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)

22、所需的時(shí)間說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)所需的時(shí)間如下，問(wèn)應(yīng)指派何人去完成何種工作，使所如下，問(wèn)應(yīng)指派何人去完成何種工作，使所需總時(shí)間最少？需總時(shí)間最少？第39頁(yè)/共64頁(yè) 任務(wù)任務(wù)人員人員EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119第40頁(yè)/共64頁(yè)指派問(wèn)題的標(biāo)準(zhǔn)形式指派問(wèn)題的標(biāo)準(zhǔn)形式 n個(gè)人，個(gè)人，n件事，第件事，第i個(gè)人做第個(gè)人做第j件事的件事的費(fèi)用為費(fèi)用為cij,確定人和事之間一一對(duì)應(yīng)的指派確定人和事之間一一對(duì)應(yīng)的指派方案，使完成方案，使完成n件事的總費(fèi)用最小。件事的總費(fèi)用最小。效率效率矩陣矩陣或或系數(shù)系數(shù)矩陣矩陣C=(cij)nn=c11 c12 c1n

23、c21 c22 c2n cn1 cn1 cnn 第41頁(yè)/共64頁(yè)C=(cij )nn=2151341041415914161378119第42頁(yè)/共64頁(yè)二、標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型二、標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型xij=1 指派第指派第 i 個(gè)人做第個(gè)人做第 j 件事件事0 不指派第不指派第 i 個(gè)人做第個(gè)人做第 j 件事件事ninjijijxcZ11minniijx11njijx11j=1,2,ni=1,2,nxij=1或或0第43頁(yè)/共64頁(yè) 解矩陣：解矩陣：滿(mǎn)足約束條件的可行解也滿(mǎn)足約束條件的可行解也可以寫(xiě)成表格或矩陣的形式，稱(chēng)為解矩可以寫(xiě)成表格或矩陣的形式，稱(chēng)為解矩陣。陣。例：例：X=(x

24、ij )44=010 000011 0 0 00 0 1 0第44頁(yè)/共64頁(yè)三、匈牙利解法三、匈牙利解法（1）關(guān)鍵性質(zhì)關(guān)鍵性質(zhì)： 若從指派問(wèn)題的系數(shù)矩陣若從指派問(wèn)題的系數(shù)矩陣(cij)nn的某的某行或某列各元素中分別減一個(gè)常數(shù)行或某列各元素中分別減一個(gè)常數(shù)k, 得到得到的新矩陣與原矩陣有相同的最優(yōu)解。的新矩陣與原矩陣有相同的最優(yōu)解。C=(cij )nn=2151341041415914161378119第45頁(yè)/共64頁(yè)C=(cij )nn=2151341041415914161378119ninjijijxcZ11min00102350960607130241047501110062111

25、30第46頁(yè)/共64頁(yè)C=(cij )nn=01370606905320100匈牙利法的步驟匈牙利法的步驟1.變換系數(shù)矩陣變換系數(shù)矩陣00102350960607130每行減最小數(shù)，每行減最小數(shù)，沒(méi)沒(méi)0的列，減最小數(shù)的列，減最小數(shù)第47頁(yè)/共64頁(yè)C=(cij )nn=01370606905320100匈牙利法的步驟匈牙利法的步驟2.尋找獨(dú)立尋找獨(dú)立“0”元素元素若有若有n個(gè)，計(jì)算結(jié)個(gè)，計(jì)算結(jié)束束若少于若少于n個(gè)，轉(zhuǎn)個(gè)，轉(zhuǎn)3第48頁(yè)/共64頁(yè)C=(cij )nn= 137669 532 1匈牙利法的步驟匈牙利法的步驟2.尋找獨(dú)立尋找獨(dú)立“0”元素元素若有若有n個(gè)，計(jì)算結(jié)個(gè)，計(jì)算結(jié)束束若少于若少

26、于n個(gè)，轉(zhuǎn)個(gè)，轉(zhuǎn)3第49頁(yè)/共64頁(yè)C=(cij )nn=2151341041415914161378119Min Z=c31+c22+c43+c14=4+4+9+11=28第50頁(yè)/共64頁(yè)2.尋找獨(dú)立尋找獨(dú)立“0”元素元素C=(cij )nn=4 8 7 15 127 9 17 14 106 9 12 8 76 7 14 6 106 9 12 10 6行減最小數(shù)行減最小數(shù)匈牙利法的步驟匈牙利法的步驟第51頁(yè)/共64頁(yè)2.尋找獨(dú)立尋找獨(dú)立“0”元素元素C=(cij )nn=0 4 3 11 80 2 10 7 30 3 6 2 10 1 8 0 40 3 6 4 0匈牙利法的步驟匈牙利法的步

27、驟沒(méi)有零的列減最小數(shù)第52頁(yè)/共64頁(yè)2.尋找獨(dú)立尋找獨(dú)立“0”元素元素若有若有n個(gè)，計(jì)算結(jié)個(gè)，計(jì)算結(jié)束束若少于若少于n個(gè)，轉(zhuǎn)個(gè)，轉(zhuǎn)3C=(cij )nn=0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 40 2 3 4 0匈牙利法的步驟匈牙利法的步驟是否找到最優(yōu)指派 610129610614767812961014179712157843534第53頁(yè)/共64頁(yè)3.尋找最少覆蓋尋找最少覆蓋“0”的直線的直線0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 41 2 3 4 0（1）行或列中只）行或列中只有一個(gè)有一個(gè)“0”的元，的元，作標(biāo)記，如果其

28、所作標(biāo)記，如果其所在列或行有其它在列或行有其它“0”的，則劃去的，則劃去。（2）如此反復(fù)直）如此反復(fù)直到所有行的到所有行的“0”被被直線覆蓋直線覆蓋匈牙利法的步驟匈牙利法的步驟第54頁(yè)/共64頁(yè)（1）對(duì)所有不含）對(duì)所有不含0元素的行打元素的行打匈牙利法的步驟匈牙利法的步驟（2）對(duì)已打）對(duì)已打的行的行中所有含中所有含0元素的元素的列打列打（3）在對(duì)已打）在對(duì)已打的列中含的列中含0元素元素的行打的行打直到無(wú)法打直到無(wú)法打?yàn)橹篂橹?3.尋找最少覆蓋尋找最少覆蓋“0”的直線的直線0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 第55頁(yè)/共64頁(yè)匈牙利法的步驟匈牙利法的步驟（4）沒(méi)打）沒(méi)打的行畫(huà)的行畫(huà)直線，直線，對(duì)打?qū)Υ虻牧挟?huà)直線的列畫(huà)直線,3.尋找最少覆蓋尋找最少覆蓋“0”的直線的直線0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 第56頁(yè)/共64頁(yè)0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 4.繼續(xù)變換