運(yùn)籌學(xué)運(yùn)輸問題演示文稿

運(yùn)籌學(xué)運(yùn)輸問題演示文稿1第一頁，共四十六頁。運(yùn)籌學(xué)第章運(yùn)輸問題2第二頁，共四十六頁。

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

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

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

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

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

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

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

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

12A231114A34

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

銷產(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)整后總運(yùn)費(fèi)增加：空格處檢驗數(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)整后總運(yùn)費(fèi)增加：空格處檢驗數(shù)為10

(-1)

(+1)表3-9第二十二頁，共四十六頁。檢驗數(shù)表110121-12因為存在小于零的檢驗數(shù),所以最小元素法給出的方案不是最優(yōu)方案.表3-10第二十三頁，共四十六頁。2.位勢法位勢：運(yùn)輸問題的對偶變量稱為位勢。因為m個供應(yīng)點n個需求點的運(yùn)輸問題有m+n個約束，因此運(yù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。第二十四頁，共四十六頁。定理：運(yù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，當(dāng)前方案不是最優(yōu)方案。最優(yōu)方案判別準(zhǔn)則表3-12第二十七頁，共四十六頁。2.3閉回路調(diào)整法改進(jìn)方案xpq為換入變量從(p,q)空格開始畫閉回路，其它轉(zhuǎn)角點都是填有運(yùn)量的方格，并從(p,q)空格開始給閉回路上的點按+1，-1，+1，-1編號，-1格的最小運(yùn)量為調(diào)整量。表3-13第二十八頁，共四十六頁。找到最小調(diào)整量以后,按照閉回路上的正、負(fù)號，分別加上和減去此值，得到新的運(yùn)輸方案。

銷產(chǎn)B1B2B3B4供量A1

5

27A23

14A3

6

39銷量

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

銷產(chǎn)B1B2B3B4供量A102

7A22

14A39

129銷量

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

銷產(chǎn)B1B2B3B4供量A137

6

45A224

322A34

38

53銷量

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

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

※利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的最小運(yùn)量（超過2個最小值）作為調(diào)整量θ，選擇任意一個最小運(yùn)量對應(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ùn)輸問題及其求解方法表上作業(yè)法是以產(chǎn)銷平衡為前提的：實際中，往往遇到產(chǎn)銷不平衡的運(yùn)輸問題1.產(chǎn)大于銷（供過于求）

2.銷大于產(chǎn)（供不應(yīng)求）第三十七頁，共四十六頁。產(chǎn)銷不平衡運(yùn)輸問題向產(chǎn)銷平衡運(yùn)輸問題的轉(zhuǎn)化產(chǎn)大于銷的運(yùn)輸問題：數(shù)學(xué)模型第三十八頁，共四十六頁。設(shè)xin+1是產(chǎn)地Ai的儲存量，化成標(biāo)準(zhǔn)形其中引入虛擬的銷地(儲存地)（需求量為），并令各個產(chǎn)地到虛擬銷地的單位運(yùn)費(fèi)為0。第三十九頁，共四十六頁。產(chǎn)小于銷的運(yùn)輸問題：引入一個虛擬的產(chǎn)地（產(chǎn)量等于），并令該虛擬產(chǎn)地到各銷地的單位運(yùn)費(fèi)為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)地平均運(yùn)輸1千噸蔬菜到各個城市的單位費(fèi)用(萬元)見下表，你能否替他們編制一個總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？

單位運(yùn)費(fèi)B1B2B3B4供應(yīng)量A1211347A2103595A378127需求量2346

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

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

單位運(yùn)費(fèi)B1B2B3B4供應(yīng)量A1211343A2103594A378125需求量2346

單位運(yùn)費(fèi)B1B2B3B4供應(yīng)量A1211344A2103593A378125A