山東大學(xué) 運(yùn)籌學(xué)課件及課后解答第三章 運(yùn)輸問題新a

作業(yè)：P99~1003.1表3-353.23.3

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

第一節(jié)運(yùn)輸問題的數(shù)學(xué)模型

有某種物資需要調(diào)運(yùn)，已知有m個(gè)產(chǎn)地（產(chǎn)地用Ai表示，i=1，2，…，m)供應(yīng)該種物資，產(chǎn)地Ai的產(chǎn)量為ai；有n個(gè)銷地（銷地用Bj表示，j=1，2，…，n)需要該種物資，銷地Bj的銷量為bj，從第i個(gè)產(chǎn)地到第j個(gè)銷地的單位物資運(yùn)價(jià)為cij，要求：制定一個(gè)調(diào)運(yùn)方案，在滿足供需關(guān)系的條件下，使總運(yùn)費(fèi)最少。

（上述資料見下面的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，也可將兩表合并起來，見后）

解：設(shè)為xij表示從產(chǎn)地為Ai給銷地為Bj的運(yùn)輸量。

則有運(yùn)輸問題的系數(shù)矩陣

下面先討論產(chǎn)銷平衡的運(yùn)輸問題的解法，對(duì)產(chǎn)銷不平衡的運(yùn)輸問題，只需化為產(chǎn)銷平衡問題，即可求解。產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型的特征：

1.產(chǎn)地：m個(gè)；

2.銷地：n個(gè)；

3.變量：m×n個(gè)；

4.約束條件：m+n個(gè)；

5.約束矩陣具有：分布稀疏性，排列規(guī)律性，數(shù)據(jù)單一性（0或1）；

6.約束矩陣的秩：r=m+n–1;

7.基變量個(gè)數(shù)：m+n–1；

8.非基變量個(gè)數(shù)：m×n–(m+n–1)。定理1.運(yùn)輸問題的數(shù)學(xué)模型必有最優(yōu)解。

定理2.若運(yùn)輸問題中產(chǎn)量和銷量皆為整數(shù)，則必有整數(shù)最優(yōu)解。第二節(jié)求解運(yùn)輸問題的表上作業(yè)法表上作業(yè)法的步驟：

1.將運(yùn)輸問題化為產(chǎn)銷平衡的問題（供過于求：增加假設(shè)銷地；供不應(yīng)求，增加假設(shè)產(chǎn)地）；

2.確定初始調(diào)運(yùn)方案（最小元素法，西北角法，vogel法）；

3.最優(yōu)性檢驗(yàn)（閉回路法，位勢(shì)法）；若所有非基變量的檢驗(yàn)數(shù)都有σij≥0，則得最優(yōu)方案，結(jié)束計(jì)算。否則，轉(zhuǎn)4；

4.調(diào)整方案（閉回路法），轉(zhuǎn)3。例1.已知運(yùn)輸問題見表

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

311310192874105

749銷量

3656

202-1初始方案的確定

1.最小元素法（就近供應(yīng)的思想）

在單位運(yùn)價(jià)表中的最小運(yùn)價(jià)處確定供銷關(guān)系，劃去滿足的行或列，以此類推，直至給出一個(gè)完整的調(diào)運(yùn)方案。

初始調(diào)運(yùn)運(yùn)方案見見下，總總運(yùn)費(fèi)為為z=86

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

433163

749銷量

3656

20特殊情況況：若運(yùn)運(yùn)價(jià)表為為:

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

31131791812105

749銷量

3656

20

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3016433

749銷量

3656

20在未被劃劃掉的運(yùn)運(yùn)價(jià)對(duì)應(yīng)應(yīng)的空格格處補(bǔ)0，然后后劃掉該該行和該該列。2.西西北角法法在在單位運(yùn)運(yùn)價(jià)表中中的左上上角（西西北角））處確定定供銷關(guān)關(guān)系，劃劃去滿足足的行或或列，以以此類推推，直至至給出一一個(gè)完整整的調(diào)運(yùn)運(yùn)方案。。

對(duì)例例1，已已知單位位運(yùn)價(jià)表表為

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

311310192874105

749銷量

3656

20初始調(diào)運(yùn)運(yùn)方案見見下，總總運(yùn)費(fèi)為為z=111

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A33

42236

749銷量

3656

203.vogel法從從運(yùn)價(jià)價(jià)表上分分別找出出每行與與每列的的最小的的兩個(gè)元元素之差差，再從從差值最最大的行行或列中中找出最最小運(yùn)價(jià)價(jià)確定供供需關(guān)系系和供需需數(shù)量，，劃去運(yùn)運(yùn)價(jià)表中中對(duì)應(yīng)的的行或列列，然后后重復(fù)上上述步驟驟。

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

523163

749銷量

3656

20初始調(diào)運(yùn)方方案為見下下，總運(yùn)費(fèi)費(fèi)為z=852-2最最優(yōu)性檢驗(yàn)驗(yàn)1.進(jìn)進(jìn)行最優(yōu)性性檢驗(yàn)的閉閉回路法閉閉回路：：在調(diào)運(yùn)方方案中，從從一個(gè)空格格處出發(fā)，，以有數(shù)字字格為頂點(diǎn)點(diǎn)（或拐點(diǎn)點(diǎn)），沿水水平或垂直直連線又回回到空格處處所形成的的封閉回路路。定理3.對(duì)對(duì)調(diào)運(yùn)方方案中的任任一個(gè)空格格，有且僅僅有一個(gè)以以有數(shù)字格格為頂點(diǎn)的的閉回路。。推論：運(yùn)輸輸問題中n+m-1個(gè)變量能能構(gòu)成基變變量的充要要條件是他他們不構(gòu)成成閉回路。。通過閉回路路計(jì)算空格格處的檢驗(yàn)驗(yàn)數(shù)σij，若σij≥0（因?yàn)闉槭乔髆inz)，則得最最優(yōu)調(diào)運(yùn)方方案，否則則，轉(zhuǎn)2-3。這里定義：：閉回路上上空格頂點(diǎn)點(diǎn)的編號(hào)為為0，其余余按1，2，3...類推。。

閉回回路的可能能形狀：σ11=c11-c13+c23-c21=3-3+2-1=1σσ31=7-1+2-3+10-5=10......2-3調(diào)調(diào)整方案，，然后轉(zhuǎn)2-2令令調(diào)整整量θ=閉閉回路上奇奇數(shù)頂點(diǎn)的的最小運(yùn)量量。

調(diào)整整方法：閉閉回路上偶偶數(shù)頂點(diǎn)運(yùn)運(yùn)量+θθ閉閉回路路上奇數(shù)頂頂點(diǎn)運(yùn)量-θ因所有檢驗(yàn)驗(yàn)數(shù)σij≥0，故得得最優(yōu)方案案。

Minz=85作業(yè)P993.1表3-36（（位勢(shì)法））P1013.43.52.進(jìn)進(jìn)行最優(yōu)性性檢驗(yàn)的位位勢(shì)法運(yùn)運(yùn)輸輸問題的對(duì)對(duì)偶問題數(shù)數(shù)學(xué)模型為為對(duì)約束條件件加松弛變變量，得已知運(yùn)輸問問題的基變變量有m+n-1個(gè)個(gè)，因此，，上式是一一個(gè)具有m+n個(gè)變變量，m+n-1個(gè)個(gè)等式的方方程組，由由于變量數(shù)數(shù)多于方程程數(shù)，故有有無窮多解解。對(duì)以上問題題，可先選選定任意一一個(gè)變量的的取值，然然后就可計(jì)計(jì)算出其它它變量的值值。(變量量ui也稱為行位位勢(shì)，vj稱為列位勢(shì)勢(shì)。)有了了ui和vj，就可計(jì)算算非基變量量的檢驗(yàn)數(shù)數(shù)σij=cij–(ui+vj)。對(duì)對(duì)例例1，可先先令v1=1，根據(jù)據(jù)cij就可求出其其它的ui，vj，從而可計(jì)計(jì)算出檢驗(yàn)驗(yàn)數(shù)。

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

311310192874105

749銷量

3656

20例：求解解下列運(yùn)輸輸問題

銷地產(chǎn)地

B1B2B3B4B5

產(chǎn)量A1A2A310

1520204020401530303035405525

506090銷量

2535601070

200

銷地產(chǎn)地

B1B2B3B4B5

產(chǎn)量A1A2A32525600101070

506090銷量2535601070

200解:初始始方案

銷地產(chǎn)地

B1B2B3B4B5

uiA1A2A31015(0)(-15)(35)(15)(30)1530(30)(0)35(0)5525

0-520vj

101520355

檢驗(yàn)驗(yàn)表表

銷地產(chǎn)地

B1B2B3B4B5

產(chǎn)量A1A2A32525600101070

506090銷量

2535601070

200一次次調(diào)調(diào)整整后后方方案案

銷地產(chǎn)地

B1B2B3B4B5

產(chǎn)量A1A2A32515106002070

506090銷量

2535601070

200檢驗(yàn)驗(yàn)表表

銷地產(chǎn)地

B1B2B3B4B5

uiA1A2A31015(15)20(35)(0)(15)1530(15)(0)35(15)(15)25

01020vj

10155205

因所所有有檢檢驗(yàn)驗(yàn)數(shù)數(shù)都都大大于于等等于于零零,故故得得最最優(yōu)優(yōu)方方案案。。minz=4025。。2-4表表上上作作業(yè)業(yè)法法總總結(jié)結(jié)1.總總結(jié)結(jié)2.求求最最大大值值問問題題例：：求求解解下下列列運(yùn)運(yùn)輸輸問問題題

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3

376424324385

523銷量

3232

10第三三節(jié)節(jié)產(chǎn)產(chǎn)銷銷不不平平衡衡的的運(yùn)運(yùn)輸輸問問題題及及應(yīng)應(yīng)用用此時(shí)時(shí)，，可可增增加加一一個(gè)個(gè)銷銷量量為為供供求求差差額額的的假假設(shè)設(shè)銷銷地地，，從從而而化化為為產(chǎn)產(chǎn)銷銷平平衡衡問問題題。?？煽捎糜帽肀肀肀硎臼救缛缦孪?。。1.當(dāng)當(dāng)供供過過于于求求時(shí)時(shí)，，運(yùn)運(yùn)輸輸問問題題的的數(shù)數(shù)學(xué)學(xué)模模型型可可寫寫成成下下式式，，加加松松弛弛變變量量化化為為標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形式式

銷地產(chǎn)地

B1B2…BnBn+1產(chǎn)量A1A2...Am

c11c12…c1nc1,n+1

c21c22…c2nc2,n+1

..…....…....…..cm1cm2…cmncm,n+1

a1a2...am銷量

b1b2…bnbn+1

2.當(dāng)當(dāng)供供不不應(yīng)應(yīng)求求時(shí)時(shí)，，運(yùn)運(yùn)輸輸問問題題的的數(shù)數(shù)學(xué)學(xué)模模型型可可寫寫成成下下式式，，加加松松弛弛變變量量化化為為標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形式式此時(shí)時(shí)，，可可增增加加一一個(gè)個(gè)產(chǎn)產(chǎn)量量為為供供求求差差額額的的假假設(shè)設(shè)產(chǎn)產(chǎn)地地，，從從而而化化為為產(chǎn)產(chǎn)銷銷平平衡衡問問題題。?？煽捎糜帽肀肀肀硎臼救缛缦孪?。。

銷地產(chǎn)地

B1B2…Bn產(chǎn)量A1A2...AmAm+1

c11c12…c1n

c21c22…c2n

..…...…...….cm1cm2…cmn

cm+1,1cm+1,2…cm+1,n

a1a2...am

am+1銷量

b1b2…bn

作業(yè)業(yè)P1033.73.8(a)例例2.已已知知見見表表：：試試決決定定總總運(yùn)運(yùn)費(fèi)費(fèi)最最少少的的調(diào)調(diào)運(yùn)運(yùn)方方案案。。

銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A32

1134103597812

757銷量

2346

1915解：這這是一一個(gè)產(chǎn)產(chǎn)大于于銷的的運(yùn)輸輸問題題，先先將其其化為為產(chǎn)銷銷平衡衡問題題，然然后求求解。。最優(yōu)方方案見見下表表，最最小運(yùn)運(yùn)費(fèi)為為minz=35

銷地產(chǎn)地

B1B2B3B4庫存

產(chǎn)量A1A2A32

323243

757銷量23464

19

銷地產(chǎn)地

B1B2B3B4庫存

產(chǎn)量A1A2A32

1134010359078120

757銷量

234