運籌學 第3章運輸問題

Chapter3運輸問題

(TransportationProblem)運輸問題的數(shù)學模型表上作業(yè)法運輸問題的應用本章主要內容：1

從m個發(fā)點向n個收點發(fā)送某種貨物.發(fā)點的發(fā)量為，收點的收量為。由運往單位貨物的運費為，問如何調配，才能使運費最??？問題的提出2表1產銷平衡表

上述數(shù)據(jù)可以匯總于表格中,如下:表2單位運價表

3運輸問題的數(shù)學模型

設xij代表為從第i個產地調運給第j個銷地的物資的數(shù)量.在產銷平衡的條件下，即使總的運費支出最小，可以表為以下數(shù)學形式：4運輸問題的約束方程組系數(shù)矩陣及特征矩陣A是一個m+n行mn列的矩陣，它的秩為m+n-1。運輸問題應該有m+n-1個基變量。3.xij的系數(shù)列向量為：m行n行5表上作業(yè)法6表上作業(yè)法的基本思路：確定初始調運方案最優(yōu)性檢驗改進方案

71確定初始基可行解運輸問題確定初始基可行解，就是求出運輸問題的初始調運方案.確定初始基可行解的方法有最小元素法伏格爾法8

【例2-1】某公司經銷甲產品,下設3個加工廠A1、A2、A3，產品分別運往銷售點B1、B2、B3、B4，各工廠的日產量和各銷售點的日需求量及各工廠到各銷售點的運價如下表所示：（運輸問題供需平衡表和運價表如下），求總運費最少的調運方案。銷地產地B1B2B3B4發(fā)量（T）A13113107A219284A3741059收量（T）3656表3-39

思路：為了減少運費，應優(yōu)先考慮單位運價最小(或運距最短)的供銷業(yè)務，最大限度地滿足其供銷量。在可供物品已用完的產地或需求已全部滿足的銷地，以后將不再考慮。然后，在余下的供、銷點的供銷關系中，繼續(xù)按上述方法安排調運，直至安排完所有供銷任務，得到一個完整的調運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調運方案)。由于該方法基于優(yōu)先滿足單位運價(或運距)最小的供銷業(yè)務，故稱為最小元素法。1、最小元素法101.最小元素法314

633Z=4×3+3×10+3×1+1×2+6×4+3×5=86該方案總運費：（思想：就近供應）不能同時劃去行和列保證填有運量的格子為m+n-1表3-411最小元素法，有時按某一最小單位運價優(yōu)先安排物品調運時，卻可能在其他供銷點多花幾倍的運費，從而使整個運輸費用增加。55552.沃格爾法沃格爾法考慮到：一個產地的產品假如不能按照最小運費就近供應，就考慮次小運費，這就有個差額。如果差額不大，當不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果差額很大，不按最小運價組織運輸就會造成很大損失，故應盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。12沃格爾法計算步驟：1)分別算出各行、各列的最小運費與次小運費的差額。2)從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進行運量調整。3)對剩余行、列再分別計算各行、列的差額。返回1)、2)。132.伏格爾法①2513①

011表3-6[]6②213②

0123③212③

01

[][]3④12④

76

[]521表3-5Z=85141若有兩個以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填數(shù)字，不能劃掉。3計算行差，列差時，已經劃去的列或者行不再考慮。15銷產B1B2B3產量A151

812A224114A33

674銷量91011例用伏格爾法求初始調運方案16銷產B1B2B3產量A1210

12A231114A34

4銷量91011初始調運方案172.2最優(yōu)解的判別判別辦法是計算空格(非基變量)的檢驗數(shù),因為運輸問題的目標函數(shù)是實現(xiàn)最小化,所以當所有空格處的檢驗數(shù)大于等于零時,為最優(yōu)解.下面分別介紹兩種計算檢驗數(shù)的方法:閉回路法(2)位勢法18①閉回路法閉回路：從空格出發(fā)畫水平(或垂直)直線，遇到填有運量的方格（數(shù)字格）可轉90°，然后繼續(xù)前進，直到到達出發(fā)的空格所形成的閉合回路。調運方案的任意空格一定存在唯一閉回路。

銷產B1B2B3B4供量A1

5

27A23

14A3

6

39銷量

3656表3-719

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1銷地產地

6

3

3

4

3

1計算最小元素法得到的初始基可行解的檢驗數(shù)

(+1)

(-1)

(+1)

(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1調整后總運費增加：空格處檢驗數(shù)為1表3-820

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1銷地產地

6

3

3

4

3

1

(+1)

(-1)

(+1)

(-1)7-5+10-3+2-1=10調整后總運費增加：空格處檢驗數(shù)為10

(-1)

(+1)表3-921檢驗數(shù)表110121-12因為存在小于零的檢驗數(shù),所以最小元素法給出的方案不是最優(yōu)方案.表3-10222.位勢法位勢：運輸問題的對偶變量稱為位勢。因為m個供應點n個需求點的運輸問題有m+n個約束，因此運輸問題就有m+n個位勢。

行位勢:關于供應點Ai的約束對應的對偶變量，記為ui,i=1,2,…m。列位勢:關于需求點Bj的約束對應的對偶變量，記為vj,j=1,2,…,n。23定理：運輸問題變量xij的檢驗數(shù)證明：24位勢法

求檢驗數(shù)的步驟:1.在表中下面和右面增加一行和一列,列中添入ui,行中添入vj,令u1=0,按照,根據(jù)表中已有的數(shù)字確定所有的ui及vj

;

2.計算所有空格處的檢驗數(shù).

25

2

-1

3010-5

9檢驗數(shù)表121-1101224=-1＜0，當前方案不是最優(yōu)方案。最優(yōu)方案判別準則表3-12262.3閉回路調整法改進方案xpq為換入變量從(p,q)空格開始畫閉回路，其它轉角點都是填有運量的方格，并從(p,q)空格開始給閉回路上的點按+1，-1，+1，-1編號，-1格的最小運量為調整量。表3-1327找到最小調整量以后,按照閉回路上的正、負號，分別加上和減去此值，得到新的運輸方案。

銷產B1B2B3B4供量A1

5

27A23

14A3

6

39銷量

3656再用閉回路法或者位勢法求檢驗數(shù)，得到下表:表3-1428

銷產B1B2B3B4供量A102

7A22

14A39

129銷量

3656這時所有的檢驗數(shù)都非負，表中的解就是最優(yōu)解.表3-1529

銷產B1B2B3B4供量A137

6

45A224

322A34

38

53銷量

3322例求該運輸問題的最優(yōu)解30表上作業(yè)法的計算步驟：分析實際問題列出產銷平衡表及單位運價表確定初始調運方案（最小元素法或伏格爾法）求檢驗數(shù)閉回路或位勢法所有檢驗數(shù)≥0找出絕對值最大的負檢驗數(shù)，用閉合回路調整，得到新的調運方案得到最優(yōu)方案，算出總運價31表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取σij<0中最小者對應的變量為換入變量。（2）無窮多最優(yōu)解 產銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。32⑵退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進基變量的閉回路對解進行調整時，標有負號的最小運量（超過2個最小值）作為調整量θ，選擇任意一個最小運量對應的基變量作為換出變量，而經調整后，得到退化解。這時另一個數(shù)字格必須填入一個“0”以示它為基變量。33銷地產地B1B2B3B4產量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經過調整，可得到另一個最優(yōu)解。

其中綠色是非基變量檢驗數(shù)，紅色為分配量。34銷地產地B1B2B3B4產量A17A24A39銷量36562011443137782106341606在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解35第三節(jié)產銷不平衡的運輸問題及其求解方法表上作業(yè)法是以產銷平衡為前提的：實際中，往往遇到產銷不平衡的運輸問題1.產大于銷（供過于求）

2.銷大于產（供不應求）36產銷不平衡運輸問題向產銷平衡運輸問題的轉化產大于銷的運輸問題：數(shù)學模型37設xin+1是產地Ai的儲存量，化成標準形其中引入虛擬的銷地(儲存地)（需求量為），并令各個產地到虛擬銷地的單位運費為0。38產小于銷的運輸問題：引入一個虛擬的產地（產量等于），并令該虛擬產地到各銷地的單位運費為0。39總供應量為19千噸，而總需求量為15千噸例2：

A1、A2、A3三個蔬菜生產地生產的蔬菜主要供應B1、B2、B3、B4四個城市。已知三個產地今年的蔬菜產量預計分別為7千噸、5千噸和7千噸；四個城市今年的蔬菜需求量分別為2千噸、3千噸、4千噸和6千噸；從每個蔬菜產地平均運輸1千噸蔬菜到各個城市的單位費用(萬元)見下表，你能否替他們編制一個總運費最省的蔬菜調運方案？

單位運費B1B2B3B4供應量A1211347A2103595A378127需求量2346

40

需求地生產地B1B2B3B4B5供應量A12113407A21035905A3781207需求量2346400-220430825723343222387最優(yōu)解中x15=2,x25=2，表示兩個產地沒有運出去的蔬菜量。41假如例2中各產地的蔬菜總產量不是19千噸，而是12千噸，就成了一個供不應求的運輸問題。

單位運費B1B2B3B4供應量A1211343A2103594A378125需求量2346

單位運費B1B2B3B4供應量A1211344A2103593A378125A400003需求量2346

引入一個虛擬產地42例3設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產量，各地區(qū)年需要量及從各個化肥廠到各地區(qū)單位化肥的運價如下表所示，試決定使總運費最省的化肥調撥方案。

需求地區(qū)化肥廠IIIIIIIV產量（萬噸）A161322