2.4運(yùn)輸問(wèn)題(修改)解析

第2.4節(jié)運(yùn)輸問(wèn)題一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型二、表上作業(yè)法三、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法1

例1

某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個(gè)加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。單位運(yùn)價(jià)表產(chǎn)銷平衡表2一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型已知有m個(gè)生產(chǎn)地點(diǎn)Ai,i=1,2,…，m。可供應(yīng)某種物資，其供應(yīng)量(產(chǎn)量)分別為：ai，i=1，2，…，m有n個(gè)銷地Bj，j=1,2,…,n，其需要量分別為：bj，j=1,2,…,n從

Ai到

Bj

運(yùn)輸單位物資的運(yùn)價(jià)(單價(jià))為：cij這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運(yùn)價(jià)表中，見(jiàn)下表。有時(shí)可把這兩表合二為一。銷地產(chǎn)地12┉n產(chǎn)量12┆m

a1a2┆am銷量b1b2┈bn

3若用

xij

表示從Ai到Bj

的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案的數(shù)學(xué)模型為：4一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型這就是運(yùn)輸問(wèn)題的數(shù)學(xué)模型。它包含m×n個(gè)變量，(m+n)個(gè)約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。5一，運(yùn)輸問(wèn)題的數(shù)學(xué)模型該系數(shù)矩陣中對(duì)應(yīng)于變量xij

的系數(shù)向量Pij，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零。即

Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j

對(duì)產(chǎn)銷平衡的運(yùn)輸問(wèn)題，由于有以下關(guān)系式存在：運(yùn)輸問(wèn)題是否一定有解？(見(jiàn)后面)運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)，A的秩為m+n-1？

最后一行可由前m+n-1行線性表示。其中任何一行都是一樣。6二，表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問(wèn)題時(shí)的一種簡(jiǎn)化方法，其實(shí)質(zhì)是單純形法。但具體計(jì)算和術(shù)語(yǔ)有所不同。可歸納為：

(1)

找出初始基可行解。即在(m×n)產(chǎn)銷平衡表上用西北角法或最小元素法，Vogel法給出m+n-1個(gè)數(shù)字，稱為數(shù)字格。它們就是初始基變量的取值。

(2)

求各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。

(3)

確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。

(4)

重復(fù)(2)，(3)直到得到最優(yōu)解為止。72.1確定初始基可行解與一般線性規(guī)劃問(wèn)題不同，產(chǎn)銷平衡的運(yùn)輸問(wèn)題總是存在可行解。因有：必存在xij≥0，i=1，…，m，j=1，…，n，如：Xij

=aibj

/d就是可行解。又因0≤xij≤min(aj，bj)，故運(yùn)輸問(wèn)題必存在最優(yōu)解。

82.1確定初始基可行解確定初始基可行解的方法很多，有西北角法，最小元素法和伏格爾(Vogel)法。一般希望的方法是既簡(jiǎn)便，又盡可能接近最優(yōu)解。下面介紹最小元素法：9

1.最小元素法最小元素法的基本思路是以運(yùn)價(jià)最低者優(yōu)先為原則安排初始的調(diào)運(yùn)方案，即從單位運(yùn)價(jià)表中最小運(yùn)價(jià)處開(kāi)始確定供銷關(guān)系。若產(chǎn)量大于銷量，則用加工廠的產(chǎn)量滿足對(duì)應(yīng)銷地的全部日銷量，在對(duì)應(yīng)的空格內(nèi)填入相應(yīng)的調(diào)運(yùn)量。并用垂直直線劃去銷售地所在列，表明該銷地的日銷量已經(jīng)全部滿足，同時(shí)從對(duì)應(yīng)加工廠的日產(chǎn)量中減去調(diào)運(yùn)量。反之，若產(chǎn)量小于銷售量。則把加工廠的日產(chǎn)量全部分配給對(duì)應(yīng)的銷售地。在對(duì)應(yīng)空格填入調(diào)運(yùn)量。用水平直線劃去加工廠所在行，并從對(duì)應(yīng)銷地的日銷量中減去調(diào)運(yùn)量。依次類推，逐步推出初始方案。由于最小元素法已經(jīng)考慮到了運(yùn)價(jià)最低者優(yōu)先為原則，因此所求的初始基本可行解通常比較接近最優(yōu)解。經(jīng)過(guò)若干次調(diào)整即可求得最有解。

10例1

某公司經(jīng)銷甲產(chǎn)品。下設(shè)三個(gè)加工廠Ａ1，Ａ2，Ａ3，每天把產(chǎn)品分別運(yùn)往四個(gè)銷地Ｂ1，Ｂ2，Ｂ3，Ｂ4。各加工廠的日產(chǎn)量，各銷地的日銷量以及從各加工廠運(yùn)送單位產(chǎn)品至各銷售地的運(yùn)價(jià)如下表：

銷地產(chǎn)地B1

B2

B3

B4

日產(chǎn)量（噸）A1

3113107A2

19284A3

741059日銷量（噸）3656單位：千元/噸問(wèn)該公司應(yīng)如何確定調(diào)運(yùn)方案，在滿足各銷地需求量的前提下可使得總運(yùn)費(fèi)最??？116563銷量（噸）951047A3

482913A2

7103113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

為了用最小元素法確定初始基本可行解，可先畫出綜合運(yùn)輸表。然后按以下步驟確定初始調(diào)運(yùn)方案。①?gòu)娜繂挝贿\(yùn)價(jià)中找出最低單位運(yùn)價(jià)（若有兩個(gè)以上最低單位運(yùn)價(jià)，則可在其中任選其一）。然后比較最低運(yùn)價(jià)所對(duì)應(yīng)的加工廠的日產(chǎn)量和銷地的日銷量，并且確定第一筆供銷關(guān)系。-3126563銷量（噸）951047A3

4821913A2

7103113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

-3②在未被劃去的單位運(yùn)價(jià)中再找尋最低運(yùn)價(jià)，比較最低運(yùn)價(jià)對(duì)應(yīng)的加工廠的日產(chǎn)量（或剩余量）和銷地的日銷量（或尚缺量）來(lái)確定供銷關(guān)系?；驹瓌t與①中描述過(guò)程相同。

-1136563銷量（噸）95310467A3

4821913A2

710334113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

-3-1

重復(fù)步驟②可逐個(gè)確定從加工廠到銷地的供銷關(guān)系?；驹瓌t是在空格內(nèi)內(nèi)每填入一個(gè)調(diào)運(yùn)量必須劃去一行或一列。填入最后一個(gè)調(diào)運(yùn)量后則同時(shí)劃去一行和一列．這樣在運(yùn)輸表中共計(jì)填入了m＋n－1個(gè)數(shù)字。這些數(shù)字對(duì)應(yīng)了一個(gè)初始基本可行解。④

-6③-4⑤

②

-3146563銷量（噸）95310467A3

4821913A2

710334113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

-3-1③

-6④

-4⑤

②

-3所填入的m＋n－1＝3＋4－1＝6個(gè)數(shù)字為對(duì)應(yīng)初始基本可行解的

6個(gè)初始基變量的值。即對(duì)應(yīng)的總運(yùn)費(fèi)為Z＝4×3＋3×10＋3×1＋1×2＋6×4＋3×5＝86（千元）15必須補(bǔ)充說(shuō)明的是：利用最小元素法確定初始調(diào)運(yùn)方案過(guò)程中，可能出現(xiàn)最低單位運(yùn)價(jià)對(duì)應(yīng)的產(chǎn)地的產(chǎn)量和銷地的銷量恰好相等的情形。此時(shí)在運(yùn)輸表中填入一個(gè)數(shù)字后，必須同時(shí)劃去產(chǎn)地所在行和銷地所在列，這和每填入一個(gè)數(shù)字只劃一條直線的基本原則相違背（最后一個(gè)數(shù)字除外）。這時(shí)我們稱運(yùn)輸問(wèn)題出現(xiàn)了退化。為了使運(yùn)輸表中有m＋n－1個(gè)數(shù)字格。需要添加一個(gè)“0”調(diào)運(yùn)量，它的位置可在同時(shí)劃去的那行或那列的任一空格處。這個(gè)“0”調(diào)運(yùn)量是不可缺少的。因?yàn)檫\(yùn)輸問(wèn)題的基本解中基變量的個(gè)數(shù)必須是m＋n－1個(gè)。不能多，也不能少。出現(xiàn)了數(shù)字為0的數(shù)字格只是說(shuō)明在初始基本可行解中有一個(gè)基變量為零。即該初始基本可行解是退化解。162.1確定初始基可行解用最小元素法給出初始解時(shí)，有可能在產(chǎn)銷平衡表上填入一個(gè)數(shù)字后，在單位運(yùn)價(jià)表上同時(shí)劃去一行和一列，這時(shí)就出現(xiàn)退化。關(guān)于退化時(shí)的處理詳見(jiàn)教材。172.1確定初始基可行解

2.伏格爾法（略）

182.2最優(yōu)解的判別回顧利用單純形法求解線性規(guī)劃的步驟：在求出基本可行解以后，就必須檢驗(yàn)該基本可行解是否為最優(yōu)解，為此給出一個(gè)檢驗(yàn)標(biāo)準(zhǔn)。在求極大化的線性規(guī)劃時(shí)，若初始基本可行解所有非基變量檢驗(yàn)數(shù)（j為非基變量下標(biāo)）則初始可行解為最優(yōu)解，停止計(jì)算。否則將進(jìn)行基變換，對(duì)初始基本可行解進(jìn)行改進(jìn)。運(yùn)輸問(wèn)題初始基本可行解的最優(yōu)性檢驗(yàn)也必須設(shè)定一個(gè)標(biāo)準(zhǔn)。由于運(yùn)輸問(wèn)題目標(biāo)函數(shù)是求極小化問(wèn)題，因此檢驗(yàn)標(biāo)準(zhǔn)是計(jì)算所有非基變量（空格）的檢驗(yàn)數(shù)

(i,j為非基變量下標(biāo))．如果所有非基變量檢驗(yàn)數(shù)則初始基本可行解為最優(yōu)解。下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法。191.閉回路法。利用閉回路的概念計(jì)算非基變量的檢驗(yàn)數(shù)，以判別基本可行解是否為最優(yōu)解。定義：若運(yùn)輸表中的一組變量經(jīng)過(guò)適當(dāng)排列以后，可寫成如下形式：其中互不相同，互不相同。那么這些變量集合就構(gòu)成了一個(gè)閉回路。其中的每一個(gè)變量稱為這個(gè)閉回路的頂點(diǎn)。由閉回路定義可知，若用水平和垂直的線段將這個(gè)變量集合中處于同行同列的相鄰頂點(diǎn)相連接。就能構(gòu)成一個(gè)封閉的回路。而且該閉回路的每一條邊（水平或垂直）上只包含兩個(gè)頂點(diǎn)。且都處于每條邊的兩個(gè)端點(diǎn)上。如20表中變量集合,變量集合,變量集合等均構(gòu)成閉回路．

B1

B2

B3

B4

B5

B6

B7

B8

B9

產(chǎn)量

A1

a1A2

a2A3

a3A4

a4銷量

b1

b2b3b4b5b6b7b8b9常見(jiàn)的幾種閉回路見(jiàn)表：21性質(zhì)定理1

運(yùn)輸問(wèn)題模型中，系數(shù)矩陣A的一組系數(shù)列向量線性無(wú)關(guān)的充分必要條件是這組向量所對(duì)應(yīng)的變量不包含閉回路。本定理證明從略。

變量組不包含閉回路的含義是該變量組中任何一個(gè)變量子集合均不構(gòu)成閉回路。由定理１可得如下推論：推論1.若一組變量包含閉回路，那么這組變量所對(duì)應(yīng)得系數(shù)列向量線性相關(guān)。推論2.m＋n－1個(gè)變量構(gòu)成基本可行解的基變量的充分必要條件是它們不包含閉回路。22定理2

若變量組(s=m+n-1)是運(yùn)輸問(wèn)題基本可行解的基變量，是一個(gè)非基變量，則變量組中存在包含的唯一閉回路。由定理2可知，從任何一個(gè)非基變量對(duì)應(yīng)的空格出發(fā)，用水平或垂直線向前劃，遇到某個(gè)基變量對(duì)應(yīng)的數(shù)字格，試轉(zhuǎn)90o后繼續(xù)前進(jìn)，最后總能找到一條閉回路，回到起始空格。23

閉回路法。設(shè)是一個(gè)非基變量，根據(jù)定理2，在運(yùn)輸表中可以找到以為第一個(gè)頂點(diǎn)，其他頂點(diǎn)均為基變量的唯一閉回路。然后沿一個(gè)方向?qū)㈤]回路中奇數(shù)頂點(diǎn)對(duì)應(yīng)的值取為正，偶數(shù)頂點(diǎn)對(duì)應(yīng)的值為負(fù)。求它們的代數(shù)和，即為非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。填入相應(yīng)的空格。做上記號(hào)以便與數(shù)字格的基變量值（調(diào)運(yùn)量）相區(qū)別。242.2最優(yōu)解的判別閉回路法計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表中，可從任一空格出發(fā)，如(A1，B1)。若讓A1的產(chǎn)品調(diào)運(yùn)1噸給B1。為了保持產(chǎn)銷平衡，就要依次作調(diào)整：

在(A1，B3)處減少1噸，(A2，B3)處增加1噸，(A2，B1)處減少1噸，即構(gòu)成了以(A1，B1)空格為起點(diǎn)，其他為數(shù)字格的閉回路。如表中的虛線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價(jià)。252.2最優(yōu)解的判別可見(jiàn)這調(diào)整的方案使運(yùn)費(fèi)增加

(+1)×3+(?1)×3+(+1)×2+(?1)×１=1(元)

這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。將“1”這個(gè)數(shù)填入(A1，B1)格，這就是檢驗(yàn)數(shù)。266563銷量（噸）95310467A3

4821913A2

710334113１A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠例2

在例1中用最小元素法求出初始基本可行解為下表所示。試用閉回路法求各非基變量（空格）的檢驗(yàn)數(shù)．解：非基變量為起點(diǎn)的閉回路為，如表所示。因此所對(duì)應(yīng)的檢驗(yàn)數(shù)276563銷量（噸）953101246710A3

48-１219１13A2

71033411２3１A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠而非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)：其他非基變量的檢驗(yàn)數(shù)用同樣方法求解，結(jié)果下表。本例中，則必存在對(duì)現(xiàn)行調(diào)運(yùn)方案的改進(jìn)辦法?？墒沟每傎M(fèi)用進(jìn)一步降低。282.2最優(yōu)解的判別當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說(shuō)明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)，改進(jìn)方法見(jiàn)2.3小節(jié)。292.2最優(yōu)解的判別2.位勢(shì)法（略）

302.3

改進(jìn)的方法——閉回路調(diào)整法當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得最優(yōu)解。若有兩個(gè)和兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格。即以它對(duì)應(yīng)的非基變量為換入變量。以(2，4)為調(diào)入格。以此格為出發(fā)點(diǎn)，作一閉回路，如下表所示。312.3

改進(jìn)的方法——閉回路調(diào)整法(2，4)格的調(diào)入量θ是選擇閉回路上具有(-1)的數(shù)字格中的最小者。即θ=min(1,3)=1(其原理與單純形法中按θ規(guī)劃來(lái)確定換出變量相同)。然后按閉回路上的正、負(fù)號(hào)，加入和減去此值，得到調(diào)整方案，如下表所示。322.3

改進(jìn)的方法——閉回路調(diào)整法對(duì)上表給出的解，再用閉回路法或位勢(shì)法求各空格的檢驗(yàn)數(shù)，見(jiàn)下表。表中的所有檢驗(yàn)數(shù)都非負(fù)，故此表中的解為最優(yōu)解。這時(shí)得到的總運(yùn)費(fèi)最小是85元。B1B2B3B4A1A2A30922112332.4

表上作業(yè)法計(jì)算中的問(wèn)題1.無(wú)窮多最優(yōu)解2.退化34三產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法前面所講表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的；但是實(shí)際問(wèn)題中產(chǎn)銷往往是不平衡的。就需要把產(chǎn)銷不平衡的問(wèn)題化成產(chǎn)銷平衡的問(wèn)題。當(dāng)產(chǎn)大于銷時(shí)

35三、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法運(yùn)輸問(wèn)題的數(shù)學(xué)模型可寫成=36三、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法1.由于總的產(chǎn)量大于銷量，就要考慮多余的物資在哪一個(gè)產(chǎn)地就地儲(chǔ)存的問(wèn)題。設(shè)xi,n+1是產(chǎn)地Ai的儲(chǔ)存量，于是有：37三，產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法令當(dāng)i=1,…，m，j=1,…，n時(shí)

當(dāng)i=1,…，m，j=n+1時(shí)將其分別代入，得到38三、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法39三、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法由于該模型中有所以這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題。當(dāng)產(chǎn)大于銷時(shí)，只要增加一個(gè)假想的銷地j=n+1(實(shí)際上是儲(chǔ)存)，該銷地總需要量為