2.4運輸問題(修改)解析

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

例1

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

Ai到

Bj

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

a1a2┆am銷量b1b2┈bn

3若用

xij

表示從Ai到Bj

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

=aibj

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

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

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

10例1

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

銷地產(chǎn)地B1

B2

B3

B4

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

3113107A2

19284A3

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

482913A2

7103113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

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

4821913A2

7103113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

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

-1136563銷量（噸）95310467A3

4821913A2

710334113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

-3-1

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

-6③-4⑤

②

-3146563銷量（噸）95310467A3

4821913A2

710334113A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠①

-3-1③

-6④

-4⑤

②

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

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

2.伏格爾法（略）

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

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

B1

B2

B3

B4

B5

B6

B7

B8

B9

產(chǎn)量

A1

a1A2

a2A3

a3A4

a4銷量

b1

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

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

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

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

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

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

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

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

4821913A2

710334113１A1

產(chǎn)量（噸）

B4

B3

B2

B1

銷售地加工廠例2

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

48-１219１13A2

71033411２3１A1

產(chǎn)量（噸）

B4

B3

B2

B1

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

302.3

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

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

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

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

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

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