第三講運(yùn)輸及指派問(wèn)題

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

2、以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)量，以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)( (或運(yùn)輸距離或運(yùn)輸距離) )，問(wèn)應(yīng)，問(wèn)應(yīng)如何組織調(diào)運(yùn)才能使總運(yùn)費(fèi)如何組織調(diào)運(yùn)才能使總運(yùn)費(fèi)( (或總運(yùn)輸量或總運(yùn)輸量) )最??？最??？【例【例1】現(xiàn)有】現(xiàn)有A1，A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng)三個(gè)產(chǎn)糧區(qū)，可供應(yīng) 糧食分別為糧食分別為10，8，5(萬(wàn)噸萬(wàn)噸)，現(xiàn)將糧食運(yùn)往，現(xiàn)將糧食運(yùn)往B1，B2，B3，B4四個(gè)地區(qū)，其需要量分四個(gè)地區(qū)，其需要量分別為別為5，7，8，3(萬(wàn)噸萬(wàn)噸)。產(chǎn)糧地到需求地的運(yùn)價(jià)。產(chǎn)糧地到需求地的運(yùn)價(jià)(元元/噸噸)如表如表1所所示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)

3、用最少。地區(qū)地區(qū)產(chǎn)糧區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量產(chǎn)量A1326310A253828A341295需要量需要量578323運(yùn)價(jià)表運(yùn)價(jià)表(元元/噸噸)表表1運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems34333231242322211413121192428353623minxxxxxxxxxxxxZ4 , 3 , 2 , 13 , 2 , 1, 038755810342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij； 設(shè)設(shè)xij(i=1,2,3；j=1,2,

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

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

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

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

8、：模型特征模型特征:1. 運(yùn)輸問(wèn)題存在可行解，也一定存在最優(yōu)解運(yùn)輸問(wèn)題存在可行解，也一定存在最優(yōu)解; 2. 當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解;3. 有有m+n個(gè)約束個(gè)約束，mn個(gè)變量個(gè)變量;4. 有有m+n1個(gè)基變量個(gè)基變量;運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems為一個(gè)閉回路為一個(gè)閉回路 ，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。的連線為閉回路的邊。 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個(gè)頂點(diǎn)，個(gè)頂點(diǎn)， 這這8個(gè)頂點(diǎn)間用水平或垂直個(gè)頂點(diǎn)間用水平或垂直線段連接起來(lái)，組成一條線段連接起來(lái)，組成一條封閉的回路。封閉的回路。 1 11 22 22 311212, ,s ssi ji ji ji ji ji jssxxxxxxi iij jj稱集合；互不相同閉回路閉回路:運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problemsx11x12x32x33x41 B1B2B3A1 A2 A3 A

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

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

12、常用的方法 有有最小元素法、元素差額法最小元素法、元素差額法( (Vogel近似法近似法)、左上角法等。、左上角法等。 Step2：求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。常用于求檢驗(yàn)求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。常用于求檢驗(yàn)數(shù)的方法有數(shù)的方法有閉回路法閉回路法和和位勢(shì)法位勢(shì)法，當(dāng)非基變量的檢驗(yàn)數(shù)，當(dāng)非基變量的檢驗(yàn)數(shù)ij全都非全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)lk0，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。轉(zhuǎn)第三步。 Step3：調(diào)整運(yùn)量，即換基。選一個(gè)變量出基，對(duì)原運(yùn)量調(diào)整運(yùn)量，即換基。選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。進(jìn)行調(diào)整得到新的

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

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

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

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

17、路法和位勢(shì)法。閉回路法和位勢(shì)法。1 1閉回路法閉回路法 求某一非基變量的檢驗(yàn)數(shù)的方法是：在基本可行解求某一非基變量的檢驗(yàn)數(shù)的方法是：在基本可行解矩陣中，以該非基變量為起點(diǎn)，以基變量為其它頂點(diǎn)，找一條閉矩陣中，以該非基變量為起點(diǎn)，以基變量為其它頂點(diǎn)，找一條閉回路，由起點(diǎn)開(kāi)始，分別在頂點(diǎn)上回路，由起點(diǎn)開(kāi)始，分別在頂點(diǎn)上交替標(biāo)上代數(shù)符號(hào)交替標(biāo)上代數(shù)符號(hào)+、-、+、-、，以這些符號(hào)分別乘以相應(yīng)的運(yùn)價(jià)，其代數(shù)和就是這個(gè)非基，以這些符號(hào)分別乘以相應(yīng)的運(yùn)價(jià)，其代數(shù)和就是這個(gè)非基變量的檢驗(yàn)數(shù)。變量的檢驗(yàn)數(shù)。求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method【解

18、】用最小元素法得到下列一組基本可行解【解】用最小元素法得到下列一組基本可行解6010702030 501010201060 4030X【例【例5】求下列運(yùn)輸問(wèn)題的一個(gè)初始基本可行解及其檢驗(yàn)數(shù)?！壳笙铝羞\(yùn)輸問(wèn)題的一個(gè)初始基本可行解及其檢驗(yàn)數(shù)。 矩陣中的元素為運(yùn)價(jià)矩陣中的元素為運(yùn)價(jià)Cij ，矩陣右邊的元素為產(chǎn)量，矩陣右邊的元素為產(chǎn)量ai ，下方的，下方的元素為銷量元素為銷量bj 。938470765150210922010 6040 30運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method只求非基變量的檢驗(yàn)數(shù)：只求非基變量的檢驗(yàn)數(shù)：求求11，先找出，先找出x11的閉

19、回路的閉回路 ，對(duì)應(yīng)的運(yùn)價(jià)為，對(duì)應(yīng)的運(yùn)價(jià)為再用正負(fù)號(hào)分別交替乘以運(yùn)價(jià)有再用正負(fù)號(hào)分別交替乘以運(yùn)價(jià)有直接求代數(shù)和得直接求代數(shù)和得31331311,xxxx31331311,CCCC31331311,CCCC829893133131111CCCC6010702030 501010201060 4030X運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method BjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj10604030831331311,xxxx31331311,CCCC829893133131111CCCC

20、0966-33951269831063856929570851433232434343313123232121323222231332321211323244114CCCCCCCCCCCCCCCCCCCC2 2位勢(shì)法求檢驗(yàn)數(shù)位勢(shì)法求檢驗(yàn)數(shù): : 位勢(shì)法求檢驗(yàn)數(shù)是根據(jù)對(duì)偶理論推導(dǎo)出來(lái)的位勢(shì)法求檢驗(yàn)數(shù)是根據(jù)對(duì)偶理論推導(dǎo)出來(lái)的一種方法。一種方法。設(shè)平衡運(yùn)輸問(wèn)題為設(shè)平衡運(yùn)輸問(wèn)題為minjjiijxcZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 111；， 設(shè)前設(shè)前m個(gè)約束對(duì)應(yīng)的對(duì)偶變量為個(gè)約束對(duì)應(yīng)的對(duì)偶變量為ui(i=1,2,

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

22、弛變量ij ，當(dāng)（當(dāng)（i，j）I 時(shí)時(shí)ij=0，因而有，因而有( , )( . )ijiji jijijuvci jIcuvi jI（解上面第一個(gè)方程，將解上面第一個(gè)方程，將ui、vj 代入第二個(gè)方程求出代入第二個(gè)方程求出ij運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method【例【例6】用位勢(shì)法求例】用位勢(shì)法求例7給出的初始基本可行解的檢驗(yàn)數(shù)。給出的初始基本可行解的檢驗(yàn)數(shù)?！窘狻康谝徊角笪粍?shì)【解】第一步求位勢(shì)u1、u2、u3及及v1、v2、v3、v4。 101030201060X20507010 60 40 30121213132323242431313333

23、uvcuvcuvcuvcuvcuvc921583331342323121vuvuvuvuvuvu令令u1=0得到位勢(shì)的解為得到位勢(shì)的解為130321uuu48314321vvvv運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method再由公式再由公式 求出檢驗(yàn)數(shù)，其中求出檢驗(yàn)數(shù)，其中cij是非是非基變量對(duì)應(yīng)的運(yùn)價(jià)?；兞繉?duì)應(yīng)的運(yùn)價(jià)。()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 計(jì)算結(jié)果與例計(jì)算結(jié)果與例7結(jié)果相同。結(jié)果相同。運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method用位勢(shì)法求檢驗(yàn)數(shù)通?？芍苯釉诒砩线M(jìn)行計(jì)算：例如用位勢(shì)法求檢驗(yàn)數(shù)通常可直接在表上進(jìn)行計(jì)算：例如 BjAiB1B2B3B4uiA193846010A276512030A3210921010vj308-341189660-3運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method調(diào)整運(yùn)量調(diào)整運(yùn)量當(dāng)某個(gè)檢驗(yàn)數(shù)小于零時(shí)，基可行解不是最優(yōu)解，總運(yùn)費(fèi)還可以當(dāng)某個(gè)檢驗(yàn)數(shù)小于零時(shí)，基可行解不是最優(yōu)解，總運(yùn)費(fèi)還可以下降，這時(shí)需調(diào)整運(yùn)輸量，改進(jìn)原運(yùn)輸方案，

25、使總運(yùn)費(fèi)減少，下降，這時(shí)需調(diào)整運(yùn)輸量，改進(jìn)原運(yùn)輸方案，使總運(yùn)費(fèi)減少，改進(jìn)運(yùn)輸方案的改進(jìn)運(yùn)輸方案的步驟步驟是：是：第一步：確定進(jìn)基變量第一步：確定進(jìn)基變量:()min0iki ji jikijx，進(jìn)基第二步：確定出基變量第二步：確定出基變量: 在進(jìn)基變量在進(jìn)基變量xik的閉回路中，標(biāo)有負(fù)號(hào)的的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量最小運(yùn)量作為調(diào)整量，對(duì)應(yīng)的基變量為出基變量，并打上對(duì)應(yīng)的基變量為出基變量，并打上“”以示作為非基變量。以示作為非基變量。第三步：調(diào)整運(yùn)量第三步：調(diào)整運(yùn)量: 在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量

26、，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，其余變量不變，得到一，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。組新的基可行解，然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method BjAiB1B2B3B4ai23647804535A31012145402515bj45655030190 【例【例7】求下列運(yùn)輸問(wèn)題的最優(yōu)解】求下列運(yùn)輸問(wèn)題的最優(yōu)解表表95.2 運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method 【解】【解】 用最小元素法求得初始基本可行解如表

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

28、法運(yùn)輸單純形法 Transportation Simplex Method因?yàn)橛幸驗(yàn)橛?個(gè)檢個(gè)檢驗(yàn)數(shù)小于零，驗(yàn)數(shù)小于零，所 以 這 組 基所 以 這 組 基本 可 行 解 不本 可 行 解 不是 最 優(yōu) 解 。是 最 優(yōu) 解 。對(duì) 應(yīng) 的 非 基對(duì) 應(yīng) 的 非 基變量變量x11進(jìn)基進(jìn)基.4,min343113,1111對(duì)應(yīng)的非基變量對(duì)應(yīng)的非基變量x11進(jìn)基進(jìn)基.x11的閉回路是的閉回路是212333321211,xxxxxxx33最小，最小，x33是出基量，調(diào)整量是出基量，調(diào)整量=151545,15,40min,min2133,12xxx BjAiB1B2B3B4ai

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

30、ortation Simplex Method BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190重新求所有非基變量的檢驗(yàn)數(shù)得重新求所有非基變量的檢驗(yàn)數(shù)得13=3，22=0，24=7，31=1，33=4，34=134=10,說(shuō)明還沒(méi)有得到最優(yōu)解，說(shuō)明還沒(méi)有得到最優(yōu)解，x34進(jìn)基，在進(jìn)基，在x34的閉回路中，的閉回路中，標(biāo)負(fù)號(hào)的變量標(biāo)負(fù)號(hào)的變量x14和和x32，調(diào)整量為，調(diào)整量為3040,30min,min3214xx運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method BjAiB1

31、B2B3B4ai23647803050A31012145401030bj45655030190 x14出基，調(diào)整運(yùn)量得到：出基，調(diào)整運(yùn)量得到：再求非基變量的檢驗(yàn)數(shù)：再求非基變量的檢驗(yàn)數(shù)：13=3，14=1，22=0，24=8，31=1，33=4運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method再求非基變量的檢驗(yàn)數(shù)：再求非基變量的檢驗(yàn)數(shù)：13=3，14=1，22=0，24=8，31=1，33=4所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)ij 0因而得到最優(yōu)解因而得到最優(yōu)解300100050030005515X最小運(yùn)費(fèi)最小運(yùn)費(fèi)31411075305101250

32、4303558155ijijijxCZ運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method設(shè)數(shù)學(xué)模型為設(shè)數(shù)學(xué)模型為 minjijijxCZ11maxnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，最大值問(wèn)題最大值問(wèn)題運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method方法一：方法一：將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題。設(shè)極大化問(wèn)題的運(yùn)將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題。設(shè)極大化問(wèn)題的運(yùn)價(jià)表為價(jià)表為C=（Cij）mn，用一個(gè)較大的數(shù)，用一個(gè)較大的數(shù)M（MmaxCij）去減）去減

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

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

35、部非正, 得到最優(yōu)解得到最優(yōu)解運(yùn)輸方案運(yùn)輸方案,結(jié)果與第一種方法相同結(jié)果與第一種方法相同.運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method 當(dāng)總產(chǎn)量與總銷量不相等時(shí)當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問(wèn)題稱為不平衡運(yùn)輸問(wèn)題.這類運(yùn)輸問(wèn)這類運(yùn)輸問(wèn)題在實(shí)際中常常碰到題在實(shí)際中常常碰到,它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再按平衡問(wèn)題求解。按平衡問(wèn)題求解。1.1.當(dāng)產(chǎn)大于銷時(shí)當(dāng)產(chǎn)大于銷時(shí), ,即即 minjjiba11數(shù)學(xué)模型為數(shù)學(xué)模型為 minjijijxCZ11minnjmixnjbxmiaxijmijijnjii

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

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

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

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

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

41、3243132333441424344xxxxxxxxXxxxxxxxx4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ111144434241343332312423222114131211xxxxxxxxxxxxxxxx111144342414433323134232221241312111xxxxxxxxxxxxxxxx4 , 3 , 2 , 110jixij、，或數(shù)學(xué)模型為：數(shù)學(xué)模型為：甲乙丙丁ABCD圖圖5. 3指派問(wèn)題指派問(wèn)題assignment problem

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

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

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