3-2運(yùn)輸問題表上作業(yè)法課件

運(yùn)輸問題的表上作業(yè)法1、單純形法（為什麼？）2、表上作業(yè)法

由于問題的特殊形式而采用的更簡潔、更方便的方法運(yùn)輸問題的表上作業(yè)法1、單純形法（為什麼？）一、表上作業(yè)法的基本思想

先設(shè)法給出一個(gè)初始方案,然后根據(jù)確定的判別準(zhǔn)則對初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如圖3-1所示。表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡捷。一、表上作業(yè)法的基本思想

確定初始方案(初始基本可行解)

改進(jìn)調(diào)整（換基迭代）否

判定是否最優(yōu)？是結(jié)束最優(yōu)方案圖1運(yùn)輸問題求解思路圖確定初始方案改進(jìn)調(diào)整否判定是否是結(jié)束最優(yōu)方

二、初始方案的確定

1、作業(yè)表（產(chǎn)銷平衡表）

初始方案就是初始基本可行解。將運(yùn)輸問題的有關(guān)信息表和決策變量——調(diào)運(yùn)量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。

表2是兩個(gè)產(chǎn)地、三個(gè)銷地的運(yùn)輸問題作業(yè)表。二、初始方案的確定調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A1c11

X11c12

X12

c13

X13a1

A2c21

X21c22

X22c23

X23a2

銷量

b1b2b3表2運(yùn)輸問題作業(yè)表（產(chǎn)銷平衡表）

調(diào)銷地c11其中xij是決策變量，表示待確定的從第i個(gè)產(chǎn)地到第j個(gè)銷地的調(diào)運(yùn)量，cij為從第i個(gè)產(chǎn)地到第j個(gè)銷地的單位運(yùn)價(jià)。2、確定初始方案的步驟：（1）選擇一個(gè)xij，令xij=min{ai，bj}=將具體數(shù)值填入xij在表中的位置；其中xij是決策變量，表示待確定的從第i個(gè)產(chǎn)地到第j個(gè)銷地的（2）調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別減去xij的值，若ai-xij=0，則劃去產(chǎn)地Ai所在的行，即該產(chǎn)地產(chǎn)量已全部運(yùn)出無剩余，而銷地Bj尚有需求缺口bj-ai；若bj-xij=0，則劃去銷地Bj所在的列，說明該銷地需求已得到滿足，而產(chǎn)地Ai尚有存余量ai-bj；（3）當(dāng)作業(yè)表中所有的行或列均被劃去，說明所有的產(chǎn)量均已運(yùn)到各個(gè)銷地，需求全部滿足，xij的取值構(gòu)成初始方案。否則，在作業(yè)表剩余的格子中選擇下一個(gè)決策變量，返回步驟（2）。（2）調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別減去xij的值，若

按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取值非負(fù)，且總數(shù)是m+n-1個(gè)，因此構(gòu)成運(yùn)輸問題的基本可行解。

對xij的選擇采用不同的規(guī)則就形成各種不同的方法，比如每次總是在作業(yè)表剩余的格子中選擇運(yùn)價(jià)（或運(yùn)距）最小者對應(yīng)的xij，則構(gòu)成最小元素法，若每次都選擇左上角格子對應(yīng)的xij就形成西北角法（也稱左上角法）。按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取

3、舉例

例3-2甲、乙兩個(gè)煤礦供應(yīng)A、B、C三個(gè)城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運(yùn)輸距離見表3-4，求使總運(yùn)輸量最少的調(diào)運(yùn)方案。

3、舉例例3-2甲、乙兩個(gè)煤礦供應(yīng)A、B、C三個(gè)表3-4例3-2有關(guān)信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應(yīng)量）CBA運(yùn)距城市煤礦表3-4例3-2有關(guān)信息表日銷量例3-2的數(shù)學(xué)模型例3-2的數(shù)學(xué)模型

分別使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供應(yīng)”；&西北角法則不考慮運(yùn)距（或運(yùn)價(jià)），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程與最小元素法相同；分別使用最小元素法和西北角法求出初始方案。調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

用最小元素法確定例3-2初始調(diào)運(yùn)方案

150100100100100100100調(diào)銷地90

得到初始調(diào)運(yùn)方案為：

x11=100，x13=100，x22=150，x23=100

得到初始調(diào)運(yùn)方案為：最小元素法實(shí)施步驟口訣《運(yùn)價(jià)表》上找最小，《平衡表》上定產(chǎn)銷；滿足銷量劃去“列”，修改“行產(chǎn)”要記牢；（滿足產(chǎn)量劃去“行”，修改“列銷”要記牢）劃去列(行)對《運(yùn)價(jià)》，修改“行產(chǎn)(列銷)”在《產(chǎn)銷》；余表再來找最小，方案很快就找到。最小元素法實(shí)施步驟口訣《運(yùn)價(jià)表》上找最小，《平衡表》上定產(chǎn)銷調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250

銷量

100

150

200

450

用西北角法確定例3-2初始調(diào)運(yùn)方案

100100100

5050200200調(diào)銷地90

得到初始調(diào)運(yùn)方案為：

x11=100，x12=100，x22=50，x23=200

三、最優(yōu)性檢驗(yàn)

檢查當(dāng)前調(diào)運(yùn)方案是不是最優(yōu)方案的過程就是最優(yōu)性檢驗(yàn)。檢查的方法：計(jì)算非基變量（未填上數(shù)值的格，即空格）的檢驗(yàn)數(shù)（也稱為空格的檢驗(yàn)數(shù)），若全部大于等于零，則該方案就是最優(yōu)調(diào)運(yùn)方案，否則就應(yīng)進(jìn)行調(diào)整。得到初始調(diào)運(yùn)方案為：三、最1、閉回路法

以確定了初始調(diào)運(yùn)方案的作業(yè)表為基礎(chǔ)，以一個(gè)非基變量作為起始頂點(diǎn)，尋求閉回路。

該閉回路的特點(diǎn)是：除了起始頂點(diǎn)是非基變量外，其他頂點(diǎn)均為基變量（對應(yīng)著填上數(shù)值的格）?？梢宰C明，如果對閉回路的方向不加區(qū)別，對于每一個(gè)非基變量而言，以其為起點(diǎn)的閉回路存在且唯一。1、閉回路法

約定作為起始頂點(diǎn)的非基變量為偶數(shù)次頂點(diǎn)，其它頂點(diǎn)從1開始順次排列，那麼，該非基變量xij的檢驗(yàn)數(shù)：現(xiàn)在，在用最小元素法確定例3-2初始調(diào)運(yùn)方案的基礎(chǔ)上，計(jì)算非基變量X12的檢驗(yàn)數(shù)：=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）（3-6）約定作為起始頂點(diǎn)的非基變量為偶數(shù)次頂點(diǎn)，其它頂點(diǎn)從1開始調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150例3-2初始調(diào)運(yùn)方案中以X12(X21)為起點(diǎn)的閉回路調(diào)銷地90非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：

=（c12+c23）-（c13+c22）

=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。經(jīng)濟(jì)含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個(gè)單位運(yùn)量而成為基變量時(shí)目標(biāo)函數(shù)值的變化量。非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：2、位勢法

以例3-2初始調(diào)運(yùn)方案為例，設(shè)置位勢變量和，在初始調(diào)運(yùn)方案表的基礎(chǔ)上增加一行和一列（見下頁表格）。然后構(gòu)造下面的方程組：（3-7）2、位勢法以例3-2初始調(diào)運(yùn)方案為例，設(shè)置位勢變量例3-2初始調(diào)運(yùn)方案位勢變量對應(yīng)表

調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450位勢變量vjv1v2v3100100100150位勢變量

uiu1u2例3-2初始調(diào)運(yùn)方案位勢變量對應(yīng)表調(diào)銷地方程組的特點(diǎn)：方程個(gè)數(shù)是m+n-1=2+3-1=4個(gè)，位勢變量共有m+n=2+3=5個(gè)，通常稱ui為第i行的位勢，稱vj為第j列的位勢；初始方案的每一個(gè)基變量xij對應(yīng)一個(gè)方程——-—所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運(yùn)距（或運(yùn)價(jià)）：ui+vj=cij；

方程組恰有一個(gè)自由變量，可以證明方程組中任意一個(gè)變量均可取作自由變量。

方程組的特點(diǎn)：

給定自由變量一個(gè)值，解方程組式（3-7），即可求得位勢變量的一組值，根據(jù)式（3-6）結(jié)合方程組（3-7），推出計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）（3-8）在式（3-7）中，令u1=0，則可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15與前面用閉回路法求得的結(jié)果相同。給定自由變量一個(gè)值，解方程組式（3-7），即可求得位位勢法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）（3-8）=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）（3-6）閉回路法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式：復(fù)習(xí)比較檢驗(yàn)數(shù)計(jì)算的兩種方法思考：試解釋位勢變量的含義（提示：寫出運(yùn)輸問題的對偶問題）位勢法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σi

四、方案調(diào)整

當(dāng)至少有一個(gè)非基變量的檢驗(yàn)數(shù)是負(fù)值時(shí)，說明作業(yè)表上當(dāng)前的調(diào)運(yùn)方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。若檢驗(yàn)數(shù)σij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路，并求出調(diào)整量ε：ijε=min{該閉回路中奇數(shù)次頂點(diǎn)調(diào)運(yùn)量xij}四、方案調(diào)整ijε=min{該閉回路中奇數(shù)次頂點(diǎn)調(diào)調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--繼續(xù)上例，因σ12=-20，畫出以x12為起始變量的閉回路調(diào)銷地90

計(jì)算調(diào)整量：ε=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運(yùn)量：閉回路上，奇數(shù)次頂點(diǎn)的調(diào)運(yùn)量減去ε，偶數(shù)次頂點(diǎn)（包括起始頂點(diǎn)）的調(diào)運(yùn)量加上ε；閉回路之外的變量調(diào)運(yùn)量不變。得到新的調(diào)運(yùn)方案：計(jì)算調(diào)整量：ε=Min（100，150）=100。得到調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運(yùn)方案：調(diào)銷地90調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450150

50200

50調(diào)銷地90

結(jié)果

最優(yōu)調(diào)運(yùn)方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運(yùn)輸量為：

Zmin=90×50+70×150+80×50+75×200=34000（噸公里）結(jié)運(yùn)輸問題的計(jì)算機(jī)求解

——表上作業(yè)法1、適用軟件Transportation/TransshipmentProblem（TRP）2、輸入數(shù)據(jù)：Maximize1minimize2<2>Numberofsources?<2>Numberofdestinations?<3>Numberoftransshipmentpoint?<0>Usethedefaultnames(S1…Sn,D1…Dn,T1…Tn)<Y>運(yùn)輸問題的計(jì)算機(jī)求解

——表上作業(yè)法1、適用軟件PresstheSpaceBartocontinueifyourentriesarecorrect

CapacitiesofSourcesS1:200S2:250DemandsofdestinationsD1:100D2:150D3:200PresstheSpaceBartocontinuENTERTHECost/ProfitCoefficientsoftheTRPModel

MinimizationFromToS1D1:90D2:70D3:100S2D1:80D2:65D3:80(注意：該例的輸入數(shù)據(jù)與前例不同)ENTERTHECost/ProfitCoeffici3、計(jì)算過程中的初始表

Initialsolutionby

000V(j)+200

+150

+100Demands0+250

+80

+200

+65

+80

+50S20

+200

+100

+70+150

90

+50S1U(I)SuppliesD3D2D1SN\DN3、計(jì)算過程中的初始表

Initials4、求解結(jié)果報(bào)告SummaryofResultsforTR2Page:1FromToShipment@costOpp.ct.FromToShipment@costOpp.ct.S1S1S1D1D2D3+50.000+150.000+90.00+70.00+100.000

+10.00S2S2S2D1D2D3+50.0000+200.00+80+65+80050MinimizedOBJ=35000Iteration=0ElapsedCPUsecond=53.3906

4、求解結(jié)果報(bào)告SummaryofR3.3運(yùn)輸問題的推廣一、產(chǎn)銷不平衡的運(yùn)輸問題供大于求供不應(yīng)求增加虛擬銷地

增加虛擬產(chǎn)地

產(chǎn)銷平衡的運(yùn)輸問題對應(yīng)的運(yùn)距（或運(yùn)價(jià)）

？轉(zhuǎn)化3.3運(yùn)輸問題的推廣一、產(chǎn)銷不平衡的運(yùn)輸問題供大于求供不應(yīng)求二、轉(zhuǎn)運(yùn)問題特點(diǎn)是所調(diào)運(yùn)的物資不是由產(chǎn)地直接運(yùn)送到銷地，而是經(jīng)過若干中轉(zhuǎn)站送達(dá)。求解思路：轉(zhuǎn)化成一個(gè)等價(jià)的產(chǎn)銷平衡運(yùn)輸問題，再用表上作業(yè)法求出最優(yōu)調(diào)運(yùn)方案。

如何轉(zhuǎn)化？二、轉(zhuǎn)運(yùn)問題如何轉(zhuǎn)化？第一步，將產(chǎn)地、轉(zhuǎn)運(yùn)點(diǎn)、銷地重新編排，轉(zhuǎn)運(yùn)點(diǎn)既作為產(chǎn)地又作為銷地；第二步，各地之間的運(yùn)距（或運(yùn)價(jià)）在原問題運(yùn)距（運(yùn)價(jià)）表基礎(chǔ)上進(jìn)行擴(kuò)展：從一地運(yùn)往自身的單位運(yùn)距（運(yùn)價(jià)）記為零，不存在運(yùn)輸線路的則記為M（一個(gè)足夠大的正數(shù)）；第一步，將產(chǎn)地、轉(zhuǎn)運(yùn)點(diǎn)、銷地重新編排，轉(zhuǎn)運(yùn)點(diǎn)既作為產(chǎn)地又作為第三步，由于經(jīng)過轉(zhuǎn)運(yùn)點(diǎn)的物資量既是該點(diǎn)作為銷地的需求量，又是該點(diǎn)作為產(chǎn)地時(shí)的供應(yīng)量，但事先又無法獲取該數(shù)量的確切值，因此通常將調(diào)運(yùn)總量作為該數(shù)值的上界。對于產(chǎn)地和銷地也作類似的處理。第三步，由于經(jīng)過轉(zhuǎn)運(yùn)點(diǎn)的物資量既是該點(diǎn)作為銷地的需求量，又是作業(yè)

作業(yè)運(yùn)輸問題的表上作業(yè)法1、單純形法（為什麼？）2、表上作業(yè)法

由于問題的特殊形式而采用的更簡潔、更方便的方法運(yùn)輸問題的表上作業(yè)法1、單純形法（為什麼？）一、表上作業(yè)法的基本思想

先設(shè)法給出一個(gè)初始方案,然后根據(jù)確定的判別準(zhǔn)則對初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如圖3-1所示。表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡捷。一、表上作業(yè)法的基本思想

確定初始方案(初始基本可行解)

改進(jìn)調(diào)整（換基迭代）否

判定是否最優(yōu)？是結(jié)束最優(yōu)方案圖1運(yùn)輸問題求解思路圖確定初始方案改進(jìn)調(diào)整否判定是否是結(jié)束最優(yōu)方

二、初始方案的確定

1、作業(yè)表（產(chǎn)銷平衡表）

初始方案就是初始基本可行解。將運(yùn)輸問題的有關(guān)信息表和決策變量——調(diào)運(yùn)量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。

表2是兩個(gè)產(chǎn)地、三個(gè)銷地的運(yùn)輸問題作業(yè)表。二、初始方案的確定調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A1c11

X11c12

X12

c13

X13a1

A2c21

X21c22

X22c23

X23a2

銷量

b1b2b3表2運(yùn)輸問題作業(yè)表（產(chǎn)銷平衡表）

調(diào)銷地c11其中xij是決策變量，表示待確定的從第i個(gè)產(chǎn)地到第j個(gè)銷地的調(diào)運(yùn)量，cij為從第i個(gè)產(chǎn)地到第j個(gè)銷地的單位運(yùn)價(jià)。2、確定初始方案的步驟：（1）選擇一個(gè)xij，令xij=min{ai，bj}=將具體數(shù)值填入xij在表中的位置；其中xij是決策變量，表示待確定的從第i個(gè)產(chǎn)地到第j個(gè)銷地的（2）調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別減去xij的值，若ai-xij=0，則劃去產(chǎn)地Ai所在的行，即該產(chǎn)地產(chǎn)量已全部運(yùn)出無剩余，而銷地Bj尚有需求缺口bj-ai；若bj-xij=0，則劃去銷地Bj所在的列，說明該銷地需求已得到滿足，而產(chǎn)地Ai尚有存余量ai-bj；（3）當(dāng)作業(yè)表中所有的行或列均被劃去，說明所有的產(chǎn)量均已運(yùn)到各個(gè)銷地，需求全部滿足，xij的取值構(gòu)成初始方案。否則，在作業(yè)表剩余的格子中選擇下一個(gè)決策變量，返回步驟（2）。（2）調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別減去xij的值，若

按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取值非負(fù)，且總數(shù)是m+n-1個(gè)，因此構(gòu)成運(yùn)輸問題的基本可行解。

對xij的選擇采用不同的規(guī)則就形成各種不同的方法，比如每次總是在作業(yè)表剩余的格子中選擇運(yùn)價(jià)（或運(yùn)距）最小者對應(yīng)的xij，則構(gòu)成最小元素法，若每次都選擇左上角格子對應(yīng)的xij就形成西北角法（也稱左上角法）。按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取

3、舉例

例3-2甲、乙兩個(gè)煤礦供應(yīng)A、B、C三個(gè)城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運(yùn)輸距離見表3-4，求使總運(yùn)輸量最少的調(diào)運(yùn)方案。

3、舉例例3-2甲、乙兩個(gè)煤礦供應(yīng)A、B、C三個(gè)表3-4例3-2有關(guān)信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應(yīng)量）CBA運(yùn)距城市煤礦表3-4例3-2有關(guān)信息表日銷量例3-2的數(shù)學(xué)模型例3-2的數(shù)學(xué)模型

分別使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供應(yīng)”；&西北角法則不考慮運(yùn)距（或運(yùn)價(jià)），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程與最小元素法相同；分別使用最小元素法和西北角法求出初始方案。調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

用最小元素法確定例3-2初始調(diào)運(yùn)方案

150100100100100100100調(diào)銷地90

得到初始調(diào)運(yùn)方案為：

x11=100，x13=100，x22=150，x23=100

得到初始調(diào)運(yùn)方案為：最小元素法實(shí)施步驟口訣《運(yùn)價(jià)表》上找最小，《平衡表》上定產(chǎn)銷；滿足銷量劃去“列”，修改“行產(chǎn)”要記牢；（滿足產(chǎn)量劃去“行”，修改“列銷”要記牢）劃去列(行)對《運(yùn)價(jià)》，修改“行產(chǎn)(列銷)”在《產(chǎn)銷》；余表再來找最小，方案很快就找到。最小元素法實(shí)施步驟口訣《運(yùn)價(jià)表》上找最小，《平衡表》上定產(chǎn)銷調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250

銷量

100

150

200

450

用西北角法確定例3-2初始調(diào)運(yùn)方案

100100100

5050200200調(diào)銷地90

得到初始調(diào)運(yùn)方案為：

x11=100，x12=100，x22=50，x23=200

三、最優(yōu)性檢驗(yàn)

檢查當(dāng)前調(diào)運(yùn)方案是不是最優(yōu)方案的過程就是最優(yōu)性檢驗(yàn)。檢查的方法：計(jì)算非基變量（未填上數(shù)值的格，即空格）的檢驗(yàn)數(shù)（也稱為空格的檢驗(yàn)數(shù)），若全部大于等于零，則該方案就是最優(yōu)調(diào)運(yùn)方案，否則就應(yīng)進(jìn)行調(diào)整。得到初始調(diào)運(yùn)方案為：三、最1、閉回路法

以確定了初始調(diào)運(yùn)方案的作業(yè)表為基礎(chǔ)，以一個(gè)非基變量作為起始頂點(diǎn)，尋求閉回路。

該閉回路的特點(diǎn)是：除了起始頂點(diǎn)是非基變量外，其他頂點(diǎn)均為基變量（對應(yīng)著填上數(shù)值的格）?？梢宰C明，如果對閉回路的方向不加區(qū)別，對于每一個(gè)非基變量而言，以其為起點(diǎn)的閉回路存在且唯一。1、閉回路法

約定作為起始頂點(diǎn)的非基變量為偶數(shù)次頂點(diǎn)，其它頂點(diǎn)從1開始順次排列，那麼，該非基變量xij的檢驗(yàn)數(shù)：現(xiàn)在，在用最小元素法確定例3-2初始調(diào)運(yùn)方案的基礎(chǔ)上，計(jì)算非基變量X12的檢驗(yàn)數(shù)：=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）（3-6）約定作為起始頂點(diǎn)的非基變量為偶數(shù)次頂點(diǎn)，其它頂點(diǎn)從1開始調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150例3-2初始調(diào)運(yùn)方案中以X12(X21)為起點(diǎn)的閉回路調(diào)銷地90非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：

=（c12+c23）-（c13+c22）

=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。經(jīng)濟(jì)含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個(gè)單位運(yùn)量而成為基變量時(shí)目標(biāo)函數(shù)值的變化量。非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：2、位勢法

以例3-2初始調(diào)運(yùn)方案為例，設(shè)置位勢變量和，在初始調(diào)運(yùn)方案表的基礎(chǔ)上增加一行和一列（見下頁表格）。然后構(gòu)造下面的方程組：（3-7）2、位勢法以例3-2初始調(diào)運(yùn)方案為例，設(shè)置位勢變量例3-2初始調(diào)運(yùn)方案位勢變量對應(yīng)表

調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450位勢變量vjv1v2v3100100100150位勢變量

uiu1u2例3-2初始調(diào)運(yùn)方案位勢變量對應(yīng)表調(diào)銷地方程組的特點(diǎn)：方程個(gè)數(shù)是m+n-1=2+3-1=4個(gè)，位勢變量共有m+n=2+3=5個(gè)，通常稱ui為第i行的位勢，稱vj為第j列的位勢；初始方案的每一個(gè)基變量xij對應(yīng)一個(gè)方程——-—所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運(yùn)距（或運(yùn)價(jià)）：ui+vj=cij；

方程組恰有一個(gè)自由變量，可以證明方程組中任意一個(gè)變量均可取作自由變量。

方程組的特點(diǎn)：

給定自由變量一個(gè)值，解方程組式（3-7），即可求得位勢變量的一組值，根據(jù)式（3-6）結(jié)合方程組（3-7），推出計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）（3-8）在式（3-7）中，令u1=0，則可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15與前面用閉回路法求得的結(jié)果相同。給定自由變量一個(gè)值，解方程組式（3-7），即可求得位位勢法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）（3-8）=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）（3-6）閉回路法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式：復(fù)習(xí)比較檢驗(yàn)數(shù)計(jì)算的兩種方法思考：試解釋位勢變量的含義（提示：寫出運(yùn)輸問題的對偶問題）位勢法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σi

四、方案調(diào)整

當(dāng)至少有一個(gè)非基變量的檢驗(yàn)數(shù)是負(fù)值時(shí)，說明作業(yè)表上當(dāng)前的調(diào)運(yùn)方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。若檢驗(yàn)數(shù)σij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路，并求出調(diào)整量ε：ijε=min{該閉回路中奇數(shù)次頂點(diǎn)調(diào)運(yùn)量xij}四、方案調(diào)整ijε=min{該閉回路中奇數(shù)次頂點(diǎn)調(diào)調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--繼續(xù)上例，因σ12=-20，畫出以x12為起始變量的閉回路調(diào)銷地90

計(jì)算調(diào)整量：ε=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運(yùn)量：閉回路上，奇數(shù)次頂點(diǎn)的調(diào)運(yùn)量減去ε，偶數(shù)次頂點(diǎn)（包括起始頂點(diǎn)）的調(diào)運(yùn)量加上ε；閉回路之外的變量調(diào)運(yùn)量不變。得到新的調(diào)運(yùn)方案：計(jì)算調(diào)整量：ε=Min（100，150）=100。得到調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運(yùn)方案：調(diào)銷地90調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450150

50200

50調(diào)銷地90

結(jié)果

最優(yōu)調(diào)運(yùn)方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運(yùn)輸量為：

Zmin=90×50+70×150+80×50+75×200=34000（噸公里）結(jié)運(yùn)輸問題的計(jì)算機(jī)求解

——表上作業(yè)法1、適用軟件Transportation/TransshipmentProblem（TRP）2、輸入數(shù)據(jù)：Maximize1minimize2<2>Numberof