運籌學運輸問題演示文稿

運籌學運輸問題演示文稿1第一頁，共四十六頁。運籌學第章運輸問題2第二頁，共四十六頁。

從m個發(fā)點向n個收點發(fā)送某種貨物.發(fā)點的發(fā)量為，收點的收量為。由運往單位貨物的運費為，問如何調(diào)配，才能使運費最??？問題的提出第三頁，共四十六頁。表1產(chǎn)銷平衡表

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

第四頁，共四十六頁。運輸問題的數(shù)學模型

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

第八頁，共四十六頁。1確定初始基可行解運輸問題確定初始基可行解，就是求出運輸問題的初始調(diào)運方案.確定初始基可行解的方法有最小元素法伏格爾法第九頁，共四十六頁。

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

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

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

011表3-6[]6②213②

0123③212③

01

[][]3④12④

76

[]521表3-5Z=8515第十五頁，共四十六頁。1若有兩個以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填數(shù)字，不能劃掉。3計算行差，列差時，已經(jīng)劃去的列或者行不再考慮。第十六頁，共四十六頁。銷產(chǎn)B1B2B3產(chǎn)量A151

812A224114A33

674銷量91011例用伏格爾法求初始調(diào)運方案第十七頁，共四十六頁。銷產(chǎn)B1B2B3產(chǎn)量A1210

12A231114A34

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

銷產(chǎn)B1B2B3B4供量A1

5

27A23

14A3

6

39銷量

3656表3-7第二十頁，共四十六頁。

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1銷地產(chǎn)地

6

3

3

4

3

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

(+1)

(-1)

(+1)

(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1調(diào)整后總運費增加：空格處檢驗數(shù)為1表3-8第二十一頁，共四十六頁。

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1銷地產(chǎn)地

6

3

3

4

3

1

(+1)

(-1)

(+1)

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

(-1)

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

行位勢:關(guān)于供應(yīng)點Ai的約束對應(yīng)的對偶變量，記為ui,i=1,2,…m。列位勢:關(guān)于需求點Bj的約束對應(yīng)的對偶變量，記為vj,j=1,2,…,n。第二十四頁，共四十六頁。定理：運輸問題變量xij的檢驗數(shù)證明：第二十五頁，共四十六頁。位勢法

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

;

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

第二十六頁，共四十六頁。

2

-1

3010-5

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

銷產(chǎn)B1B2B3B4供量A1

5

27A23

14A3

6

39銷量

3656再用閉回路法或者位勢法求檢驗數(shù)，得到下表:表3-14第二十九頁，共四十六頁。

銷產(chǎn)B1B2B3B4供量A102

7A22

14A39

129銷量

3656這時所有的檢驗數(shù)都非負，表中的解就是最優(yōu)解.表3-15第三十頁，共四十六頁。

銷產(chǎn)B1B2B3B4供量A137

6

45A224

322A34

38

53銷量

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

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

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

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

2.銷大于產(chǎn)（供不應(yīng)求）第三十七頁，共四十六頁。產(chǎn)銷不平衡運輸問題向產(chǎn)銷平衡運輸問題的轉(zhuǎn)化產(chǎn)大于銷的運輸問題：數(shù)學模型第三十八頁，共四十六頁。設(shè)xin+1是產(chǎn)地Ai的儲存量，化成標準形其中引入虛擬的銷地(儲存地)（需求量為），并令各個產(chǎn)地到虛擬銷地的單位運費為0。第三十九頁，共四十六頁。產(chǎn)小于銷的運輸問題：引入一個虛擬的產(chǎn)地（產(chǎn)量等于），并令該虛擬產(chǎn)地到各銷地的單位運費為0。第四十頁，共四十六頁?？偣?yīng)量為19千噸，而總需求量為15千噸例2：

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

單位運費B1B2B3B4供應(yīng)量A1211347A2103595A378127需求量2346

第四十一頁，共四十六頁。

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

單位運費B1B2B3B4供應(yīng)量A1211343A2103594A378125需求量2346

單位運費B1B2B3B4供應(yīng)量A1211344A2103593A378125A