第3章運輸問題第1節運輸問題的數學模型第2節表上作業法第3節產銷不平衡的運輸問題及其求解方法第4節應用舉例第1節運輸問題的數學模型已知有m個生產地點Ai,i=1,2,…，m。可供應某種物資，其供應量(產量)分別為ai，i=1，2，…，m，有n個銷地Bj，j=1,2,…,n，其需要量分別為bj，j=1,2,…,n，從Ai到Bj運輸單位物資的運價(單價)為cij。運輸問題的數學模型bn

…b2b1需求量Bn…B2B1

需方供方AmA2A1ama2a1供應量供需平衡運價運輸問題的數學模型bn…b2b1需求量BnB2B1

需方供方AmA2A1ama2a1供應量cmncm2cm1c2nc22c21c1nc12c11…………如何建立供需搭配，使總的運輸費用最小？供需平衡表數學模型設從Ai到Bj的物資運量為xij

，產銷平衡運輸問題的數學模型。Ai的產品全部供應出去Bj的需求全部得到滿足平衡表、運價表合二為一：約束條件或解可用產銷平衡表表示:

ui?vj無約束（i=1,2,…,m;j=1,2,…,n)uivj設ui,vj為對偶變量，對偶問題模型為m個

n個這就是運輸問題的數學模型。它包含m×n個變量，(m+n)個約束方程。其系數矩陣的結構比較松散，且特殊。

第2節表上作業法

表上作業法是單純形法在求解運輸問題時的一種簡化方法，其實質是單純形法。(1)找出初始基可行解。即在(m×n)產銷平衡表上給出m+n-1個數字格，它們就是初始基變量的取值。(2)求各非基變量的檢驗數，即在表上計算空格的檢驗數，判別是否達到最優解。如已是最優解，則停止計算，否則轉到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調整。(4)重復(2)，(3)直到得到最優解為止。

例1某公司經銷甲產品。它下設三個加工廠。每日的產量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產品分別運往四個銷售點。各銷售點每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點的單位產品的運價為表3-3所示。問該公司應如何調運產品，在滿足各銷點的需要量的前提下，使總運費為最少。

例運輸問題供需平衡表和運價表如下，求最優調運方案。

6563需求量（T）951047A348291A27103113A1供應量（T）B4B3B2B1

需供表3-31.

最小元素法這方法的基本思想是就近供應，即從單位運價表中最小的運價開始確定供銷關系，然后次小。一直到給出初始基可行解為止。⑴最小元素法314

633Z=4×3+3×10+3×1+1×2+6×4+3×5=86該方案總運費：用最小元素法給出的初始解是運輸問題的基可行解，其理由為：(1)用最小元素法給出的初始解，是從單位運價表中逐次地挑選最小元素，并比較產量和銷量。當產大于銷，劃去該元素所在列。當產小于銷，劃去該元素所在行。然后在未劃去的元素中再找最小元素，再確定供應關系。這樣在產銷平衡表上每填入一個數字，在運價表上就劃去一行或一列。表中共有m行n列，總共可劃(n+m)條直線。但當表中只剩一個元素時，這時當在產銷平衡表上填這個數字時，而在運價表上同時劃去一行和一列。此時把單價表上所有元素都劃去了，相應地在產銷平衡表上填了(m+n-1)個數字，即給出了(m+n-1)個基變量的值。(2)這(m+n-1)個基變量對應的系數列向量是線性獨立的。

證若表中確定的第一個基變量為它對應的系數列向量為:

因當給定的值后，將劃去第i1行或第j1列，即其后的系數列向量中再不出現ei1或em+j1，因而不可能用解中的其他向量的線性組合表示。類似地給出第二個，…，第(m+n-1)個。這(m+n-1)個向量都不可能用解中的其他向量的線性組合表示。故這(m+n-1)個向量是線性獨立的。

用最小元素法給出初始解時，有可能在產銷平衡表上填入一個數字后，在單位運價表上同時劃去一行和一列。這時就出現退化，關于退化時的處理將在2.4節中講述。

2.伏格爾法

最小元素法的缺點是：為了節省一處的費用，有時造成在其他處要多花幾倍的運費。伏格爾法考慮到，一產地的產品假如不能按最小運費就近供應，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調運時，運費增加越多。因而對差額最大處，就應當采用最小運費調運。

.②伏格爾法

分別計算各行、各列次小、最小運價的差額，優先在最大差額處進行供需搭配。銷地產地B1B2B3B4行差額A1A2A3317119432101085011列差額2513步驟：1計算未劃去行、列的差額；2找出最大差額對應的最小元素cij進行供需分配；3在未被劃去的行、列重新計算差額。6563銷量

9A34A27A1供量B4B3B2B1

銷產

63152列差額151047A318291A20103113A1行差額B4B3B2B16563銷量

9

A34A27A1供量B4B3B2B1

銷產

6312列差額251047A318291A20103113A1行差額B4B3B2B1

36563銷量

9

A34A27A1供量B4B3B2B1

銷產

6212列差額51047A318291A20103113A1行差額B4B3B2B1

3

36563銷量

9A34A27A1供量B4B3B2B1

銷產

621差額51047A368291A27103113A1差額B4B3B2B1

3

5

1

2

3最優解的判別（檢驗數的求法）①閉回路法閉回路：從空格出發順時針(或逆時針)畫水平(或垂直)直線，遇到填有運量的方格可轉90°，然后繼續前進，直到到達出發的空格所形成的閉合回路。調運方案的任意空格存在唯一閉回路。6563銷量

93

6A34

13A27

2

5A1供量B4B3B2B1

銷產差額法方案最優解的判別（檢驗數的求法）①閉回路法閉回路：從空格出發順時針(或逆時針)畫水平(或垂直)直線，遇到填有運量的方格可轉90°，然后繼續前進，直到到達出發的空格所形成的閉合回路。調運方案的任意空格存在唯一閉回路。6563銷量

93

6A34

13A27

2

5A1供量B4B3B2B1

銷產從每一空格出發一定存在和可以找到唯一的閉回路。因(m+n-1)個數字格(基變量)對應的系數向量是一個基。任一空格(非基變量)對應的系數向量是這個基的線性組合。如Pij,i,j∈N可表示為

其中Pik,Plk,Pls,Pus,Puj∈B。而這些向量構成了閉回路(見圖3-2)。

閉回路法計算檢驗數的經濟解釋為：在已給出初始解的表3-9中，可從任一空格出發，如(A1，B1)，

若讓A1的產品調運1噸給B1。為了保持產銷平衡，就要依次作調整：

在(A1，B3)處減少1噸，(A2，B3)處增加1噸，(A2，B1)處減少1噸，即構成了以(A1，B1)空格為起點，其他為數字格的閉回路。

314

633最小元素法+-+-

x11為換入變量，x11增加1，運費的變化為3-1+2-3=1。這個變化就是x11的檢驗數，故

11=1將“1”這個數填入(A1，B1)格，這就是檢驗數。按以上所述，可找出所有空格的檢驗數，

見表3-15。

當檢驗數還存在負數時，說明原方案不是最優解，要繼續改進，改進方法見2.3小節。

而每個決策變量xij的系數向量Pij=ei+em+j，所以CBB-1Pij=ui+vj。于是檢驗數

②.位勢法

用閉回路法求檢驗數時，需給每一空格找一條閉回路。設u1，u2，…，um;v1，v2，…，vn是對應運輸問題的m+n個約束條件的對偶變量。

標準型運輸問題的對偶問題是：

基變量的檢驗數為零(

基變量xij)，

ij=cij-(ui+vj),ui

,vj

自由變量-Y-YS2-YS1-CBB-1CN-CBB-1N0XSXNXB得m+n-1個方程，令某個ui

(或vj)=0，可解出m+n個ui

和vj；由此得非基變量的檢驗數。314

633位勢法

令v1=0,

由c21=1=u2+v1，得u2=1調運方案表調運量

0

1

1

2

0

1

1

28-3

7位勢表2989-3-2下一步：檢驗數位勢

0

1

1

28-3

7檢驗數表121-11012

24=-1＜0，當前方案不是最優方案。檢驗數運價2.3閉回路調整法改進方案pqijj,i)(min

=<0xpq為換入變量q

=min{1，3}=1從(p,q)空格開始畫閉回路，其它轉角點都是填有運量的方格，并從(p,q)空格開始給閉回路上的點按+1，-1，+1，-1編號，-1格的最小運量為調整量。換出變量銷地

產地

B1

B2

B3

B4

產量

A1

A2

A3

3

6

4(+1)…

┇

1(-1)…

…3(-1)

┇

…(+1)

3

7

4

9

銷量

3

6

5

6

851186zz2401=×-=ql+=新的調運方案為：銷地

產地

B1

B2

B3

B4

產量

A1

A2

A3

3

6

5

2

1

3

7

4

9

銷量

3

6

5

6

0-7-1-7Vj

5129A3812A21020A1uiB4B3B2B1

需供713491110231085表3-21檢驗數表最優解中有非基變量檢驗數為零時，以此非基變量為換入變量，可求得另一基最優解。即某個非基變量(空格)的檢驗數為0時，該問題有無窮多最優解。2.4表上作業法計算中的問題1無窮多最優解表3-22表3-21空格(1，1)的檢驗數是0，表明例1有無窮多最優解。可在表3-20中以(1，1)為調入格，作閉回路(1，1)+-(1，4)--(2，4)+-(2，1)--(1，1)+。確定θ=min(2,3)=2。經調整后得到另一最優解，見用表上作業法求解運輸問題當出現退化時，在相應的格中一定要填一個0，以表示此格為數字格。有以下兩種情況：(1)在確定初始解的各供需關系時，若在(i,j)格填入某數字后，出現Ai處的余量等于Bj處的需量。這時在產銷平衡表上填一個數，而在單位運價表上相應地要劃去一行和一列。為了使在產銷平衡表上有(m+n-1)個數字格。這時需要添一個“0”，它的位置可在對應同時劃去的那行或那列的任一空格處。2退化如表3-23，表3-24所示。因第一次劃去第一列，剩下最小元素為2，其對應的銷地B2，需要量為6，而對應的產地A3未分配量也是6。這時在產銷表(3，2)交叉格中填入6，這時在單位運價表3-24中需同時劃去B2列和A3行。在表3-23的空格(1，2)，(2，2)，(3，3)，(3，4)中任選一格添加一個0。

表3-23，表3-24(2)在用閉回路法調整時，當閉回路上出現兩個和兩個以上的具有(-1)標記的相等的最小值。這時只能選擇其中一個作為調入格。而經調整后，得到退化解。這時另一個數字格必須填入一個0，表明它是基變量。當出現退化解后，并作改進調整時，可能在某閉回路上有標記為(-1)的取值為0的數字格，這時應取調整量θ=0。第3節產銷不平衡的運輸問題及其求解方法

前面所講表上作業法，都是以產銷平衡為前提條件的。但是實際問題中產銷往往是不平衡的，就需要把產銷不平衡的問題化成產銷平衡的問題。當產大于銷運輸問題的數學模型可寫成

目標函數：滿足：由于總的產量大于銷量，就要考慮多余的物資在哪一個產地就地儲存的問題。設xi,n+1是產地Ai的儲存量，于是有：

令：當i=1,…，m，j=1,…，n時

當i=1,…，m，j=n+1時將其分別代入，得到滿足：由于這個模型中所以這是一個產銷平衡的運輸問題。

因此，當產大于銷時，只要增加一個假想的銷地j=n+1(實際上是儲存)，該銷地總需要量為

而在單位運價表中從各產地到假想銷地的單位運價為，就轉化成一個產銷平衡的運輸問題

當銷大于產時，可以在產銷平衡表中增加一個假想的產地i=m+1，該地產量為

在單位運價表上令從該假想產地到各銷地的運價，同樣可以轉化為一個產銷平衡的運輸問題.。

例2設有三個化肥廠(A，B，C)供應四個地區(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農用化肥。假定等量的化肥在這些地區使用效果相同。各化肥廠年產量，各地區年需要量及從各化肥廠到各地區運送單位化肥的運價如表3-25所示。試求出總的運費最節省的化肥調撥方案。

表3-25

解這是一個產銷不平衡的運輸問題，總產量為160萬噸，四個地區的最低需求為110萬噸，最高需求為無限。根據現有產量，第Ⅳ個地區每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于產量。為了求得平衡，在產銷平衡表中增加一個假想的化肥廠D，其年產量為50萬噸。由于各地區的需要量包含兩部分，如地區Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應運價為M(任意大正數)，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應運價為0。對凡是需求分兩種情況的地區，實際上可按照兩個地區看待。這樣可以寫出這個問題的產銷平衡表(表3-26)和單位運價表(表3-27)。

產銷平衡表(表3-26),單位運價表(表3-27)

根據表上作業法計算，可以求得這個問題的最優方案如表3-28所示

第4節應用舉例由于在變量個數相等的情況下，表上作業法的計算遠比單純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規劃的問題化為運輸問題的數學模型。下面介紹幾個典型的例子。例3某廠按合同規定須于當年每個季度末分別提供10，15，25，20臺同一規格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如表3-29所示。又如果生產出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用0.15萬元。要求在完成合同的情況下，作出使該廠全年生產(包括儲存、維護)費用最小的決策。表3-29解由于每個季度生產出來的柴油機不一定當季交貨，所以設xij為第i季度生產的用于第j季度交貨的柴油機數。根據合同要求，必須滿足

又每季度生產的用于當季和以后各季交貨的柴油機數不可能超過該季度的生產能力，故又有：

第i季度生產的用于j季度交貨的每臺柴油機的實際成本cij應該是該季度單位成本加上儲存、維護等費用。cij的具體數值見表3-30

表3-30設用ai表示該廠第i季度的生產能力，bj表示第j季度的合同供應量，則問題可寫成：

目標函數：滿足顯然，這是一個產大于銷的運輸問題模型。注意到這個問題中當i＞j時，xij=0，所以應令對應的cij=M，再加上一個假想的需求D，就可以把這個問題變成產銷平衡的運輸模型，并寫出產銷平衡表和單位運價表(合在一起，見表3-31)。經用表上作業法求解，可得多個最優方案，表3-32中列出最優方案之一。即第Ⅰ季度生產25臺，10臺當季交貨，15臺Ⅱ季度交貨；Ⅱ季度生產5臺，用于Ⅲ季度交貨；Ⅲ季度生產30臺，其中20臺于當季交貨，10臺于Ⅳ季度交貨。Ⅳ季度生產10臺，于當季交貨。按此方案生產，該廠總的生產(包括儲存、維護)的費用為773萬元。表3-32例4某航運公司承擔六個港口城市A、B、C、D、E、F的四條固定航線的物資運輸任務。已知各條航線的起點、終點城市及每天航班數

見表3-33。

假定各條航線使用相同型號的船只，又各城市間的航程天數見表3-34。

又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應配備多少條船，才能滿足所有航線的運貨需求?

解該公司所需配備船只分兩部分。(1)載貨航程需要的周轉船只數。例如航線1，在港口E裝貨1天，E→D航程17天，在D卸貨1天，總計19天。每天3航班，故該航線周轉船只需57條。各條航線周轉所需船只數見表3-35。表3-35以上累計共需周轉船只數91條

.(2)各港口間調度所需船只數。有些港口每天到達船數多于需要船數，例如港口D，每天到達3條，需求1條；而有些港口到達數少于需求數，

例如港口B。各港口每天余缺船只數的計算見表3-36。

為使配備船只數最少，應做到周轉的空船數為最少。即將由多余船只的港口調往需用船只的港口為空船航駛,應采用合理的調度方案,以使“調運量”最小。因此建立以下運輸問題，其產銷平衡表見表3-37。

單位運價表應為相應各港口之間的船只航程天數，見表3-38。

用表上作業法求出空船的最優調度方案見表3-39。

由表3-39知最少需周轉的空船數為

2×1+13×1+5×1+17×1+3×1=40條。這樣在不考慮維修、儲備等情況下，該公司至少應配備40+91=131條船。例5在本章的例1中，如果假定①每個