1、運籌學運籌學Operations Research第三講第三講 運輸與指派問題運輸與指派問題 實際工作中常碰到很多線性規劃問題，由于他們約束實際工作中常碰到很多線性規劃問題，由于他們約束條件變量的系數矩陣具有特殊的結構，很可能找到比單純條件變量的系數矩陣具有特殊的結構，很可能找到比單純形法更為簡便的方法進行求解，從而可節約時間和費用形法更為簡便的方法進行求解，從而可節約時間和費用, , 運輸問題就是其中之一。運輸問題的一般提法是運輸問題就是其中之一。運輸問題的一般提法是: :某種物資某種物資有若干個產地和銷地，若已知各產地地產量、各銷地的銷有若干個產地和銷地，若已知各產地地產量、各銷地的銷量，

2、以及各產地到各銷地的單位運價量，以及各產地到各銷地的單位運價( (或運輸距離或運輸距離) )，問應，問應如何組織調運才能使總運費如何組織調運才能使總運費( (或總運輸量或總運輸量) )最省？最省？【例【例1】現有】現有A1，A2，A3三個產糧區，可供應三個產糧區，可供應 糧食分別為糧食分別為10，8，5(萬噸萬噸)，現將糧食運往，現將糧食運往B1，B2，B3，B4四個地區，其需要量分四個地區，其需要量分別為別為5，7，8，3(萬噸萬噸)。產糧地到需求地的運價。產糧地到需求地的運價(元元/噸噸)如表如表1所所示，問如何安排一個運輸計劃，使總的運輸費用最少。示，問如何安排一個運輸計劃，使總的運輸費

3、用最少。地區地區產糧區產糧區B1B2B3B4產量產量A1326310A253828A341295需要量需要量578323運價表運價表(元元/噸噸)表表1運輸模型運輸模型 Model of Transportation Problems34333231242322211413121192428353623minxxxxxxxxxxxxZ4 , 3 , 2 , 13 , 2 , 1, 038755810342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij； 設設xij(i=1,2,3；j=1,2,

4、3,4)為為i個產糧地運往第個產糧地運往第j個需求地的運個需求地的運量，這樣得到下列運輸問題的數學模型：量，這樣得到下列運輸問題的數學模型： 【解】【解】 運輸模型運輸模型 Model of Transportation Problems【例【例2】有三臺機床加工三種零件，計劃第】有三臺機床加工三種零件，計劃第i臺的生產任務為臺的生產任務為a i (i=1,2,3)個零件，第個零件，第j種零件的需要量為種零件的需要量為bj (j=1,2,3)，第，第 i 臺機床臺機床加工第加工第 j 種零件需要的時間為種零件需要的時間為cij ，如表，如表2所示。問如何安排生產所示。問如何安排生產任務使總的加

5、工時間最少？任務使總的加工時間最少？ 零件零件機床機床B1B2B3生產任務生產任務A152350A264160A373440需要量需要量703050150表表 2運輸模型運輸模型 Model of Transportation Problems【解】【解】 設設 xi j (i=1,2,3；j=1,2,3,)為第為第i臺機床加工第臺機床加工第j種零件的數種零件的數 量，則此問題的數學模型為量，則此問題的數學模型為111213212223313233111213212223313233112131122232132333min523647345060407030500,1,2,31,2,3ijZ

6、xxxxxxxxxxxxxxxxxxxxxxxxxxxxij；運輸模型運輸模型 Model of Transportation Problems運輸問題的一般數學模型運輸問題的一般數學模型設有設有m個產地生產某種物資個產地生產某種物資, 記作記作A1, A2, A3 , , Am，其產量分別，其產量分別為為a1, a2, , am；有；有n個銷地個銷地, 記作記作B1，B2，Bn，其需要量分，其需要量分別為別為b1, b2 , , bn；且；且產銷平衡產銷平衡，即，即 。從第。從第 i個產地個產地到第到第 j 個銷地的單位運價為個銷地的單位運價為cij ，在滿足各地需要的前提下，求總，在滿足各

7、地需要的前提下，求總運輸費用最小的調運方案。運輸費用最小的調運方案。 設設xij(i=1,2,m；j=1,2,n)為第為第 i 個產地到第個產地到第 j個銷地的運量，則數學模型為：個銷地的運量，則數學模型為： njjmiiba11njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij, 1;, 1, 0, 1, 111運輸模型運輸模型 Model of Transportation Problemsniijijmixcz11minnjmixnjbxmiaxijjmiijnjiij, 1;, 1,0, 1, 111設平衡運輸問題設平衡運輸問題的數學模型為：的數學模型為

8、：模型特征模型特征:1. 運輸問題存在可行解，也一定存在最優解運輸問題存在可行解，也一定存在最優解; 2. 當供應量和需求量都是整數時，則一定存在整數最優解當供應量和需求量都是整數時，則一定存在整數最優解;3. 有有m+n個約束個約束，mn個變量個變量;4. 有有m+n1個基變量個基變量;運輸模型運輸模型 Model of Transportation Problems為一個閉回路為一個閉回路 ，集合中的變量稱為回路的頂點，相鄰兩個變量，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。的連線為閉回路的邊。 x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x

9、11 x12x31 x42表表3表表3中閉回路的變量集合是中閉回路的變量集合是x11, x12, x42, x 43, x 23, x 25, x 35, x 31共有共有8個頂點，個頂點， 這這8個頂點間用水平或垂直個頂點間用水平或垂直線段連接起來，組成一條線段連接起來，組成一條封閉的回路。封閉的回路。 1 11 22 22 311212, ,s ssi ji ji ji ji ji jssxxxxxxi iij jj稱集合；互不相同閉回路閉回路:運輸模型運輸模型 Model of Transportation Problemsx11x12x32x33x41 B1B2B3A1 A2 A3 A

10、4 x43表表4表表4中閉回路是中閉回路是123233434111,xxxxxx注：注： (1)(1)一條回路中的頂點數一定是偶數，回路遇到頂點必須一條回路中的頂點數一定是偶數，回路遇到頂點必須轉轉9090度與另一頂點連接。度與另一頂點連接。 有些變量組本身不構成回路，但其可能包含回路，例如：有些變量組本身不構成回路，但其可能包含回路，例如：表表3中變量組中變量組 不能組成一條不能組成一條閉回路，但閉回路，但A中包含有中包含有(2)(2) 閉回路閉回路 ;,121131352521xxxxxxA ;,31352521xxxx運輸模型運輸模型 Model of Transportation Pr

11、oblems1111min1,1,0,1,;1,mnijijijnijijmijjiijzc xxaimxbjnxim jn 設平衡運輸問題的數學模型為：設平衡運輸問題的數學模型為：運輸單純形法運輸單純形法 Transportation Simplex Method運輸單純形法基本思路：運輸單純形法基本思路：是是基可行解基可行解最優否最優否否否停停 運輸單純形法也稱為運輸單純形法也稱為表上作業法表上作業法，是直接在運價表上求最，是直接在運價表上求最優解的一種方法，它的步驟是：優解的一種方法，它的步驟是： Step1：求初始基可行解求初始基可行解( (初始調運方案初始調運方案) )。常用的方法。

12、常用的方法 有有最小元素法、元素差額法最小元素法、元素差額法( (Vogel近似法近似法)、左上角法等。、左上角法等。 Step2：求檢驗數并判斷是否得到最優解。常用于求檢驗求檢驗數并判斷是否得到最優解。常用于求檢驗數的方法有數的方法有閉回路法閉回路法和和位勢法位勢法，當非基變量的檢驗數，當非基變量的檢驗數ij全都非全都非負時得到最優解，若存在檢驗數負時得到最優解，若存在檢驗數lk0，說明還沒有達到最優，說明還沒有達到最優，轉第三步。轉第三步。 Step3：調整運量，即換基。選一個變量出基，對原運量調整運量，即換基。選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步。進行調整得到新的

13、基可行解，轉入第二步。注注: : 表上作業法的條件是表上作業法的條件是產銷平衡和運價非負。產銷平衡和運價非負。運輸單純形法運輸單純形法 Transportation Simplex Method初始基可行解的確定初始基可行解的確定最小元素法：最小元素法： 最小元素法的思想是就近優先運送，即最小運價最小元素法的思想是就近優先運送，即最小運價cij 對應的變量對應的變量 xij 優先賦值優先賦值然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，依次下去，直到最后得到一個初始基可行解。依次下去，直到最后得到一個初始基可行解。jiijbax

14、,min【例【例3】求表】求表5所示的運輸問題的初始基可行解。所示的運輸問題的初始基可行解。表表 5 銷銷 地地產地產地B1B2B3產產 量量A1A2A3847634758304525銷銷 量量603010100運輸單純形法運輸單純形法 Transportation Simplex Method BjAiB1B2B3產產 量量A186730A243545A374825銷銷 量量603010100表表6【解】【解】3015102520運輸單純形法運輸單純形法 Transportation Simplex Method【例【例4】求表】求表7給出的運輸問題的初始基本可行解給出的運輸問題的初始基本可

15、行解 B1B2B3B4aiA14104420A2773815A31210615bj510251050表表7運輸單純形法運輸單純形法 Transportation Simplex Method表表8 BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】【解】510 0151010運輸單純形法運輸單純形法 Transportation Simplex Method初始基本可行解可用下列矩陣表示初始基本可行解可用下列矩陣表示0101015510表表8中，基變量恰好是中，基變量恰好是3+41=6個且不包含閉回路，個且不包含閉回路，是一組基變量，其

16、余標有符號是一組基變量，其余標有符號的變量是非基變量的變量是非基變量 323123141312,xxxxxx運輸單純形法運輸單純形法 Transportation Simplex Method求出一組基可行解后，判斷其是否最優，仍然是用檢驗數來判斷，求出一組基可行解后，判斷其是否最優，仍然是用檢驗數來判斷，記記xij的檢驗數為的檢驗數為ij ，由第一章知，求最小值的運輸問題的最優判由第一章知，求最小值的運輸問題的最優判別準則是：別準則是：所有非基變量的檢驗數都非負，則運輸方案最優所有非基變量的檢驗數都非負，則運輸方案最優(即為最優解即為最優解)。求檢驗數的方法有兩種，求檢驗數的方法有兩種，閉回

17、路法和位勢法。閉回路法和位勢法。1 1閉回路法閉回路法 求某一非基變量的檢驗數的方法是：在基本可行解求某一非基變量的檢驗數的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上回路，由起點開始，分別在頂點上交替標上代數符號交替標上代數符號+、-、+、-、，以這些符號分別乘以相應的運價，其代數和就是這個非基，以這些符號分別乘以相應的運價，其代數和就是這個非基變量的檢驗數。變量的檢驗數。求檢驗數求檢驗數運輸單純形法運輸單純形法 Transportation Simplex Method【解

18、】用最小元素法得到下列一組基本可行解【解】用最小元素法得到下列一組基本可行解6010702030 501010201060 4030X【例【例5】求下列運輸問題的一個初始基本可行解及其檢驗數。】求下列運輸問題的一個初始基本可行解及其檢驗數。 矩陣中的元素為運價矩陣中的元素為運價Cij ，矩陣右邊的元素為產量，矩陣右邊的元素為產量ai ，下方的，下方的元素為銷量元素為銷量bj 。938470765150210922010 6040 30運輸單純形法運輸單純形法 Transportation Simplex Method只求非基變量的檢驗數：只求非基變量的檢驗數：求求11，先找出，先找出x11的閉

19、回路的閉回路 ，對應的運價為，對應的運價為再用正負號分別交替乘以運價有再用正負號分別交替乘以運價有直接求代數和得直接求代數和得31331311,xxxx31331311,CCCC31331311,CCCC829893133131111CCCC6010702030 501010201060 4030X運輸單純形法運輸單純形法 Transportation Simplex Method BjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj10604030831331311,xxxx31331311,CCCC829893133131111CCCC

20、0966-33951269831063856929570851433232434343313123232121323222231332321211323244114CCCCCCCCCCCCCCCCCCCC2 2位勢法求檢驗數位勢法求檢驗數: : 位勢法求檢驗數是根據對偶理論推導出來的位勢法求檢驗數是根據對偶理論推導出來的一種方法。一種方法。設平衡運輸問題為設平衡運輸問題為minjjiijxcZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 111；， 設前設前m個約束對應的對偶變量為個約束對應的對偶變量為ui(i=1,2,

21、m)，后，后n個約束對個約束對應的對偶變量為應的對偶變量為vj(j=1,2,n), 則運輸問題的對偶問題是則運輸問題的對偶問題是運輸單純形法運輸單純形法 Transportation Simplex Methodminjjjiivbuaw11max,1,2,;1,2,1,2,;1,2,ijijijuvcim jnu vim jn無約束加入松馳變量加入松馳變量ij將約束化為等式將約束化為等式:ui+vj+ij=cij記原問題基變量記原問題基變量XB的下標集為的下標集為I，由第二章對偶性質知，原問題，由第二章對偶性質知，原問題xij的檢驗數的相反數是對偶問題的松弛變量的檢驗數的相反數是對偶問題的松

22、弛變量ij ，當（當（i，j）I 時時ij=0，因而有，因而有( , )( . )ijiji jijijuvci jIcuvi jI（解上面第一個方程，將解上面第一個方程，將ui、vj 代入第二個方程求出代入第二個方程求出ij運輸單純形法運輸單純形法 Transportation Simplex Method【例【例6】用位勢法求例】用位勢法求例7給出的初始基本可行解的檢驗數。給出的初始基本可行解的檢驗數。【解】第一步求位勢【解】第一步求位勢u1、u2、u3及及v1、v2、v3、v4。 101030201060X20507010 60 40 30121213132323242431313333

23、uvcuvcuvcuvcuvcuvc921583331342323121vuvuvuvuvuvu令令u1=0得到位勢的解為得到位勢的解為130321uuu48314321vvvv運輸單純形法運輸單純形法 Transportation Simplex Method再由公式再由公式 求出檢驗數，其中求出檢驗數，其中cij是非是非基變量對應的運價。基變量對應的運價。()i jijijcuv111111141414212121222222323232343434()9(0 1)8()4(04)0()7( 3 1)9()6( 33)6()10(1 3)6()2(14)3cuvcuvcuvcuvcuvcu

24、v 計算結果與例計算結果與例7結果相同。結果相同。運輸單純形法運輸單純形法 Transportation Simplex Method用位勢法求檢驗數通常可直接在表上進行計算：例如用位勢法求檢驗數通常可直接在表上進行計算：例如 BjAiB1B2B3B4uiA193846010A276512030A3210921010vj308-341189660-3運輸單純形法運輸單純形法 Transportation Simplex Method調整運量調整運量當某個檢驗數小于零時，基可行解不是最優解，總運費還可以當某個檢驗數小于零時，基可行解不是最優解，總運費還可以下降，這時需調整運輸量，改進原運輸方案，

25、使總運費減少，下降，這時需調整運輸量，改進原運輸方案，使總運費減少，改進運輸方案的改進運輸方案的步驟步驟是：是：第一步：確定進基變量第一步：確定進基變量:()min0iki ji jikijx，進基第二步：確定出基變量第二步：確定出基變量: 在進基變量在進基變量xik的閉回路中，標有負號的的閉回路中，標有負號的最小運量作為調整量最小運量作為調整量，對應的基變量為出基變量，并打上對應的基變量為出基變量，并打上“”以示作為非基變量。以示作為非基變量。第三步：調整運量第三步：調整運量: 在進基變量的閉回路中標有正號的變量加上在進基變量的閉回路中標有正號的變量加上調整量調整量，標有負號的變量減去調整量

26、，標有負號的變量減去調整量，其余變量不變，得到一，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數重新檢驗。組新的基可行解，然后求所有非基變量的檢驗數重新檢驗。運輸單純形法運輸單純形法 Transportation Simplex Method BjAiB1B2B3B4ai23647804535A31012145402515bj45655030190 【例【例7】求下列運輸問題的最優解】求下列運輸問題的最優解表表95.2 運輸單純形法運輸單純形法 Transportation Simplex Method 【解】【解】 用最小元素法求得初始基本可行解如表

27、用最小元素法求得初始基本可行解如表9用 閉 回 路用 閉 回 路法 求 非 基法 求 非 基變 量 的 檢變 量 的 檢驗數驗數 得：得：111121233332121313123233222232332324242333321214313133232134341412534 14 12898 12 1416 12 144474 14 12821110 144334CCCCCCCCCCCCCCCCCCCCCCCCCCCC 32528 121 BjAiB1B2B3B4ai23647804535A31012145402515bj45655030190+_+_+_運輸單純形

28、法運輸單純形法 Transportation Simplex Method因為有因為有4個檢個檢驗數小于零，驗數小于零，所 以 這 組 基所 以 這 組 基本 可 行 解 不本 可 行 解 不是 最 優 解 。是 最 優 解 。對 應 的 非 基對 應 的 非 基變量變量x11進基進基.4,min343113,1111對應的非基變量對應的非基變量x11進基進基.x11的閉回路是的閉回路是212333321211,xxxxxxx33最小，最小，x33是出基量，調整量是出基量，調整量=151545,15,40min,min2133,12xxx BjAiB1B2B3B4ai

29、23647804535A31012145402515bj4565503019011112123333212534 14 1284CCCCCC +_+_+_ BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190在在x11的閉回路上的閉回路上x11、x32、x23分別加上分別加上15，x12、x33、x21分別減分別減去去15，并且在，并且在x33處打上記號處打上記號“”作為非基變量，其余變量不作為非基變量，其余變量不變，調整后得到一組新的基可行解：變，調整后得到一組新的基可行解：運輸單純形法運輸單純形法 Transp

30、ortation Simplex Method BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190重新求所有非基變量的檢驗數得重新求所有非基變量的檢驗數得13=3，22=0，24=7，31=1，33=4，34=134=10,說明還沒有得到最優解，說明還沒有得到最優解，x34進基，在進基，在x34的閉回路中，的閉回路中，標負號的變量標負號的變量x14和和x32，調整量為，調整量為3040,30min,min3214xx運輸單純形法運輸單純形法 Transportation Simplex Method BjAiB1

31、B2B3B4ai23647803050A31012145401030bj45655030190 x14出基，調整運量得到：出基，調整運量得到：再求非基變量的檢驗數：再求非基變量的檢驗數：13=3，14=1，22=0，24=8，31=1，33=4運輸單純形法運輸單純形法 Transportation Simplex Method再求非基變量的檢驗數：再求非基變量的檢驗數：13=3，14=1，22=0，24=8，31=1，33=4所有檢驗數所有檢驗數ij 0因而得到最優解因而得到最優解300100050030005515X最小運費最小運費31411075305101250

32、4303558155ijijijxCZ運輸單純形法運輸單純形法 Transportation Simplex Method設數學模型為設數學模型為 minjijijxCZ11maxnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，最大值問題最大值問題運輸單純形法運輸單純形法 Transportation Simplex Method方法一：方法一：將極大化問題轉化為極小化問題。設極大化問題的運將極大化問題轉化為極小化問題。設極大化問題的運價表為價表為C=（Cij）mn，用一個較大的數，用一個較大的數M（MmaxCij）去減）去減

33、每一個每一個Cij得到矩陣得到矩陣C=（Cij）mn ，其中，其中Cij=MCij0,將將C作作為極小化問題的運價表，用表上用業法求出最優解，目標函數為極小化問題的運價表，用表上用業法求出最優解，目標函數值為值為 11mnijijijZC x例如，下列矩陣例如，下列矩陣C是是Ai（i=1，2，3）到）到Bj的噸公里利潤的噸公里利潤,運輸部運輸部門如何安排運輸方案使總利潤最大門如何安排運輸方案使總利潤最大.2589107654C121098 14 922Mmax10,10ijijijCCCC取則852103456C 運輸單純形法運輸單純形法 Transportation Simplex Meth

34、od用最小元素法求初始方案得用最小元素法求初始方案得048109X11=8, 12=4, 21=2, 23=2全部非負全部非負,得到得到最 優 運 輸 方 案最 優 運 輸 方 案 X , 最 大 利 潤最 大 利 潤Z=89+1010+68+54=240方法二方法二: :所有非基變量的檢驗數所有非基變量的檢驗數ij0時最優時最優. 求求初始運輸方案可采初始運輸方案可采用最大元素法用最大元素法. 如上例如上例,用最大元素得到用最大元素得到 的初始運輸方案的初始運輸方案:048109X4567109852C121098 14 9求檢驗數求檢驗數:11=8,12=4,21=2,23=2,全部非正全

35、部非正, 得到最優解得到最優解運輸方案運輸方案,結果與第一種方法相同結果與第一種方法相同.運輸單純形法運輸單純形法 Transportation Simplex Method 當總產量與總銷量不相等時當總產量與總銷量不相等時,稱為不平衡運輸問題稱為不平衡運輸問題.這類運輸問這類運輸問題在實際中常常碰到題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。按平衡問題求解。1.1.當產大于銷時當產大于銷時, ,即即 minjjiba11數學模型為數學模型為 minjijijxCZ11minnjmixnjbxmiaxijmijijnjii

36、j, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，不平衡運輸問題不平衡運輸問題運輸單純形法運輸單純形法 Transportation Simplex Method 由于總產量大于總銷量，必有部分產地的產量不能全部運送由于總產量大于總銷量，必有部分產地的產量不能全部運送完，必須就地庫存，即每個產地設一個倉庫，庫存量為完，必須就地庫存，即每個產地設一個倉庫，庫存量為 xi，n+1（i=1，2，m），總的庫存量為），總的庫存量為 njjmiimininmnnnbaxxxxb1111,1,1,21, 11運輸單純形法運輸單純形法 Transportation Simplex Meth

37、odbn+1作為一個虛設的銷地作為一個虛設的銷地Bn+1的銷量。各產地的銷量。各產地Ai到到Bn+1的運價為零，的運價為零，即即Ci，n+1=0,（i=1，m）。則平衡問題的數學模型為：）。則平衡問題的數學模型為： minjijijxCZ11min, 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時具體求解時,只在只在運價表右端增加一列運價表右端增加一列Bn+1，運價為零，運價為零,銷量為銷量為bn+1即可即可運輸單純形法運輸單純形法 Transportation Simplex Method2.2.當銷大于產時當銷

38、大于產時, ,即即minjjiba11數學模型為數學模型為 minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111運輸單純形法運輸單純形法 Transportation Simplex Method由于總銷量大于總產量由于總銷量大于總產量,故一定有些需求地不完全滿足故一定有些需求地不完全滿足,這時虛設這時虛設一個產地一個產地Am+1，產量為，產量為 nmmmmxxxa,121111，njmiijnjjmabx1111,xm+1,j 是是Am+1運到運到Bj的運量，也是的運量，也是Bj不能滿足需要的數

39、量。不能滿足需要的數量。Am+1到到Bj的運價為零的運價為零,即即Cm+1,j=0(j=1,2, ,n) 運輸單純形法運輸單純形法 Transportation Simplex Method銷大于產平衡問題的數學模型為銷大于產平衡問題的數學模型為 ： minjijijxCZ11minnjmixnjbxmiaxijmijijnjiji, 2 , 11, 2 , 1, 0, 2 , 11, 2 , 1111；具體計算時，在運價表的下方增加一行具體計算時，在運價表的下方增加一行Am+1，運價為零。，運價為零。產量為產量為am+1即可。即可。 運輸單純形法運輸單純形法 Transportation S

40、implex Method指派問題指派問題assignment problem 【例【例8】人事部門欲安排四人到四個不同的崗位工作，每個崗位】人事部門欲安排四人到四個不同的崗位工作，每個崗位一個人經考核四人在不同崗位的成績（百分制）如下表所示，一個人經考核四人在不同崗位的成績（百分制）如下表所示，如何安排他們的工作使總成績最好。如何安排他們的工作使總成績最好。 工作工作人員人員ABCD甲甲85927390乙乙95877895丙丙82837990 丁丁86908088工作時人做不分配第工作時人做分配第jijixij01【解】設【解】設指派問題的數學模型指派問題的數學模型1112131421222

41、3243132333441424344xxxxxxxxXxxxxxxxx4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ111144434241343332312423222114131211xxxxxxxxxxxxxxxx111144342414433323134232221241312111xxxxxxxxxxxxxxxx4 , 3 , 2 , 110jixij、，或數學模型為：數學模型為：甲乙丙丁ABCD圖圖5. 3指派問題指派問題assignment problem

42、mjixmjxmixxcZijmiijmjijmimjijij, 1,10, 11, 11min(max)1111或假設假設m個人恰好做個人恰好做m項工作，第項工作，第i個人做第個人做第j項工作的效率為項工作的效率為cij0，效率矩陣為效率矩陣為cij，如何分配工作使效率最佳，如何分配工作使效率最佳(min或或max)的數學模的數學模型為型為 指派問題指派問題assignment problem 解指派問題的匈牙利算法解指派問題的匈牙利算法匈牙利法的條件匈牙利法的條件：問題求：問題求最小值、人數與工作數相等及效率非負最小值、人數與工作數相等及效率非負 【定理【定理5.4】如果從分配問題效率矩陣

43、如果從分配問題效率矩陣cij的每一行元素中分別減的每一行元素中分別減去去(或加上或加上)一個常數一個常數ui(被稱為該行的位勢被稱為該行的位勢)，從每一列分別減去，從每一列分別減去(或加上或加上)一個常數一個常數vj(稱為該列的位勢稱為該列的位勢)，得到一個新的效率矩陣，得到一個新的效率矩陣bij，其中，其中bij=cij ui vj,則則bij的最優解等價于的最優解等價于cij的最優解，這的最優解，這里里cij、bij均非負均非負【定理【定理5.5】若矩陣若矩陣A的元素可分成的元素可分成“0”與非與非“0”兩部分，則覆蓋兩部分，則覆蓋“0”元素的元素的最少直線數等于位于不同行不同列的最少直線

44、數等于位于不同行不同列的“0”元素元素(稱為獨稱為獨立元素立元素)的最大個數的最大個數如果最少直線數等于如果最少直線數等于m，則存在，則存在m個獨立的個獨立的“0”元素，令這些零元素，令這些零元素對應的元素對應的xij等于等于1，其余變量等于，其余變量等于0，這時目標函數值等于零，這時目標函數值等于零，得到最優解得到最優解指派問題指派問題assignment problem 【例【例9】某汽車公司擬將四種新產品配置到四個工廠生產，四個】某汽車公司擬將四種新產品配置到四個工廠生產，四個工廠的單位產品成本工廠的單位產品成本(元元/件件)如下表所示求最優生產配置方案如下表所示求最優生產配置方案 產品產品1產品產品2產品產品3產品產品4工廠工廠工廠27550150230工廠工廠36570170250工廠工廠48255200280【解】問題求最小值。【解】問題求最小值。第一步：第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最找出