第四章 運(yùn)輸問題

第三章運(yùn)輸問題4.1運(yùn)輸問題模型及有關(guān)概念4.2運(yùn)輸問題求解4.3運(yùn)輸問題的應(yīng)用4.1運(yùn)輸問題的數(shù)學(xué)模型

例某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？產(chǎn)量銷量產(chǎn)地銷地解設(shè)為從產(chǎn)地到銷地的運(yùn)輸量產(chǎn)量銷量產(chǎn)地銷地運(yùn)價(jià)系數(shù)矩陣約束方程系數(shù)矩陣111000000111100100010010001001特點(diǎn)：1、共有2+3=5行，表示2個(gè)產(chǎn)地和3個(gè)銷地；有2×3=6列，恰好對(duì)應(yīng)6個(gè)變量；2、每列只有兩個(gè)1，其余為0，表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用；

一般運(yùn)輸問題的數(shù)學(xué)模型（產(chǎn)銷平衡的運(yùn)輸問題）A1,

A2,…,Am

表示某物資的m個(gè)產(chǎn)地；B1,B2,…,Bn

表示該物資的n個(gè)銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj的銷量；

cij

表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)為從產(chǎn)地運(yùn)往銷地的運(yùn)輸量，產(chǎn)量銷量產(chǎn)地銷地運(yùn)價(jià)得到下列一般運(yùn)輸問題的模型：

其系數(shù)矩陣為變化：

1）有時(shí)目標(biāo)函數(shù)求最大，如求利潤(rùn)最大或營(yíng)業(yè)額最大等；2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入（等式或不等式）約束；3）產(chǎn)銷不平衡時(shí)，可加入虛設(shè)的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。求解思路是

基本可行解最優(yōu)否結(jié)束

否

換基運(yùn)輸問題基變量的特點(diǎn)*運(yùn)輸問題的基變量共有m+n-1個(gè)，A的秩為m+n-1。*運(yùn)輸問題的可行解一定存在。

*運(yùn)輸問題的最優(yōu)解一定存在。⑷.重復(fù)⑵.⑶，直到找到最優(yōu)解為止。步驟：⑴.找出初始基本可行解（初始調(diào)運(yùn)方案，一般m+n-1個(gè)數(shù)字格），用西北角法、最小元素法,元素差額法；⑵.求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用閉回路法或位勢(shì)法計(jì)算；⑶.改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；4.2運(yùn)輸問題的求解——表上作業(yè)法例一、某運(yùn)輸資料如下表所示：?jiǎn)挝讳N地運(yùn)價(jià)產(chǎn)地產(chǎn)量311310719284741059銷量36561、求初始方案：⑴.西北角法（或左上角法）：此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實(shí)際背景，但它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。方法如下：365674934490656404902562029005620090036360000000340002200036總的運(yùn)費(fèi)＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元（1）最小元素法總的運(yùn)輸費(fèi)用為基本思想是就近供應(yīng)，即從最小運(yùn)價(jià)開始分配運(yùn)輸量，然后次小，直到最后供完為止。產(chǎn)量銷量產(chǎn)地銷地運(yùn)價(jià)（2）元素差額法（Vogel法）產(chǎn)量銷量產(chǎn)地銷地運(yùn)價(jià)差額列差額行總的運(yùn)輸費(fèi)用為注：只剩下最后一行或一列時(shí)，就不再求差額了，從最小運(yùn)價(jià)開始逐一進(jìn)行即可。1、初始基本可行解的確定：（1）西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。（3）元素差額法：在運(yùn)價(jià)表中分別計(jì)算出各行各列最小元素與次小元素的差額，并分別列于差額行的第一行與差額列的第一列，在差額最大的行或列找出最小元素，先安排該位置，劃去一行或一列。計(jì)算剩余行與列的最小元素與次小元素的差額，并分別列于差額行的第二行與差額列的第二列，在差額最大的行或列找出最小元素，先安排該位置，劃去一行或一列，如此反復(fù)，直到劃去所有的行與列。注：應(yīng)用西北角法，最小元素法和元素差額法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列）在保留的列（行）任意沒被劃去的格內(nèi)標(biāo)一個(gè)0。注：除最后一個(gè)元素（相當(dāng)于同時(shí)刪去一行一列）外，每填一個(gè)數(shù)都只刪去一行或一列。若當(dāng)前的行、列同時(shí)滿足，可在當(dāng)前的行（或列）的一個(gè)格子標(biāo)0，同時(shí)刪去當(dāng)前的列（或行）。2、最優(yōu)性檢驗(yàn)：

判別方法：計(jì)算ij=cij-CBB–1Pij,i=1,…,m;j=1,…,n。

因?yàn)槟繕?biāo)函數(shù)求最小，當(dāng)所有檢驗(yàn)數(shù)均大于等于0時(shí)為最優(yōu)解。（1）閉回路法從每一空格出發(fā)，用水平或垂直向前劃，每碰到一合適的數(shù)字格轉(zhuǎn)90度，直到回到初始空格，得一閉回路，而且是唯一的閉回路。

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

其中Pik,Plk,Pls,Pus,Puj∈B。而這些向量構(gòu)成了閉回路。

用下述方法找檢驗(yàn)數(shù)Step1：寫出初始基解的運(yùn)價(jià)；Step2：利用“對(duì)角和相等”填空格，得新表；Step3：老運(yùn)價(jià)表-新運(yùn)價(jià)表=檢驗(yàn)數(shù)表如上例的最小元素法所得初始解的檢驗(yàn)數(shù)__==（2）位勢(shì)法：

根據(jù)單純形法中檢驗(yàn)數(shù)的定義，從約束條件中解出基變量，代入目標(biāo)函數(shù)中，消去目標(biāo)函數(shù)中的基變量，得到的非基變量的系數(shù)就是檢驗(yàn)數(shù)。位勢(shì)：設(shè)對(duì)應(yīng)基變量xij

的m+n-1個(gè)i、j，存在ui,vj

滿足ui+vj=cij，i=1,…,m;j=1,…,n.稱這些ui,vj

為該基本可行解對(duì)應(yīng)的位勢(shì)。由于有m+n個(gè)變量（ui,vj），m+n-1個(gè)方程（基變量個(gè)數(shù)），故有一個(gè)自由變量，位勢(shì)不唯一。利用位勢(shì)求檢驗(yàn)數(shù)：

ij=cij-ui-vji=1,…,m;j=1,…,n前例，位勢(shì)法求檢驗(yàn)數(shù)：

step1從任意基變量對(duì)應(yīng)的cij

開始，任取ui

或vj，然后利用公式cij=ui+vj

依次找出m+n個(gè)ui,vj；從

c14=10開始

step2計(jì)算非基變量的檢驗(yàn)數(shù)ij=cij-ui-vj；填入圓圈內(nèi)3、解的改進(jìn)——閉回路調(diào)整法：（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk為主元，作為進(jìn)基變量；（上頁圖中x24）（2）以為xrk起點(diǎn)找一條閉回路，除xrk

外其余頂點(diǎn)必須為基變量格；（上頁圖中藍(lán)色回路）（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，xrk

為1，沿一個(gè)方向依次給各頂點(diǎn)標(biāo)號(hào)；（4）求=min{xijxij對(duì)應(yīng)閉回路上的偶數(shù)標(biāo)號(hào)格}=xpq那么確定xpq為出基變量，為調(diào)整量；（5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)xij+，對(duì)各偶標(biāo)號(hào)頂點(diǎn)xij-，特別xpq-=0，變?yōu)榉腔兞?；主元變換：由前面得到=1，于是

ij≥0，得到最優(yōu)解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余xij=0;

最優(yōu)費(fèi)用：f*=3*5+10*2+1*3+8*1+4*6+5*3=85

1、產(chǎn)大于銷：模型方法是先將原問題變成平衡問題，需假設(shè)一個(gè)銷地(Bn+1)(實(shí)際上考慮產(chǎn)地的存量)，4.產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法模型為：

2、銷大于產(chǎn)：同樣假設(shè)一個(gè)產(chǎn)地即可，變化同上。單位運(yùn)價(jià)表中的單位運(yùn)價(jià)為1、產(chǎn)量大于銷量例、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往個(gè)銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。拷猓涸黾右粋€(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為0例、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往個(gè)銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。拷猓涸黾右粋€(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A3702030406040403030203020用最小元素法求初始方案例題：20已知某運(yùn)輸問題的資料如下表所示B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125

1、表中的發(fā)量、收量單位為：噸，運(yùn)價(jià)單位為：元/噸試求出最優(yōu)運(yùn)輸方案.練習(xí)：

2、如將A2的發(fā)量改為17，其它資料不變，試求最優(yōu)調(diào)運(yùn)方案。B1B2B3B4發(fā)量A112315A210212A313013收量1013125B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125解：1、用最小元素法求初始方案B1B2B3B4發(fā)量A112315A210212A313013收量1013125B1B2B3B4A153A211A324運(yùn)費(fèi)為108元/噸2、用位勢(shì)法判斷：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4

u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4

令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝3B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中還有負(fù)數(shù)，說明沒有得到最優(yōu)解，調(diào)整運(yùn)輸方案。σij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的運(yùn)送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

總的運(yùn)費(fèi)105元/噸B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中還有負(fù)數(shù)，說明沒有得到最優(yōu)解，繼續(xù)調(diào)整運(yùn)輸方案。cij(ui+vj)1

(σij)1

013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的運(yùn)送方案總的運(yùn)費(fèi)85元/噸B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中沒有負(fù)數(shù)，說明已經(jīng)得到最優(yōu)解。但有無窮多最優(yōu)解。0013A312A25010A1B4B3B2B1最終的運(yùn)送方案總的運(yùn)費(fèi)85元/噸B1B2B3B4發(fā)量A131215A27512A313013收量1013125B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125B1B2B3B4A125A211A327B1B2B3B4ui

A125u1A211u2A327u3vj

v1v2v3v4成本表

u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7

令：u1＝0u1＝0v1＝2u2＝－1v2＝0u3＝2v3＝5v4＝2B1B2B3B4ui

A120520A21-141-1A342742vj

2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui

A10601A204-20A3-1000vj

σijB1B2B3B4發(fā)量A131215A27512A313013收量1013125B1B2B3B4發(fā)量A110515A27512A313013收量1013125B1B2B3B4B5發(fā)量A110515A2102517A313013收量10131255B1B2B3B4B5發(fā)量A12653015A21321017A33274013收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表

u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij505B45121310收量1313A317210A215510A1發(fā)量B5B3B2B1B1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表

u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1040-10A224004A310200σijB1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5發(fā)量A110515A212517A31313收量10131255C=75已知資料如下表所示，問如何供電能使總的輸電費(fèi)用為最??？發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A110523A24312A35634單位輸電費(fèi)用作業(yè)：B1B2B3B4A1A2A3初始方案10010050250400100B1B2B3B4A110523A24312A35634單位輸電費(fèi)用發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A11053A212A35B1B2B3B4ui

A1105230A29412-