運(yùn)輸問題數(shù)學(xué)建模(2015春)

運(yùn)輸問題與表上作業(yè)許華臨沂大學(xué)物流學(xué)院§3.1運(yùn)輸問題及其數(shù)學(xué)建?！?.2表上作業(yè)法§3.3產(chǎn)銷不平衡的運(yùn)輸問題§3.4應(yīng)用舉例本章主要內(nèi)容:1．掌握運(yùn)輸問題的數(shù)學(xué)模型、系數(shù)矩陣特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握回路、位勢法求解過程和表上作業(yè)法求解運(yùn)輸問題過程教學(xué)要求：一、運(yùn)輸問題及其數(shù)學(xué)模型

在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到物資調(diào)撥中的運(yùn)輸問題。例如煤、鋼材、糧食、木材等物資，在全國都有若干生產(chǎn)基地，分別將這些物資調(diào)到各消費(fèi)基地去，應(yīng)如何制定調(diào)運(yùn)方案，使總的運(yùn)輸費(fèi)用最少？問題的提出:

運(yùn)輸問題的一般提法是：設(shè)某種物資有m個產(chǎn)地和n個銷地。產(chǎn)地Ai的產(chǎn)量為；銷地Bj的銷量。從第i個產(chǎn)地向第j個銷地運(yùn)輸每單位物資的運(yùn)價為Cij。

這就是由多個產(chǎn)地供應(yīng)多個銷地的單品種物資運(yùn)輸問題。問如何調(diào)運(yùn)這些物資才能使總運(yùn)費(fèi)達(dá)到最小。1、運(yùn)輸問題的一般提法單位運(yùn)價表

（1）。即運(yùn)輸問題的總產(chǎn)量等于其總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷平衡的運(yùn)輸問題。（2）。即運(yùn)輸問題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷不平衡的運(yùn)輸問題。分兩種情況來討論：

若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為：

2、運(yùn)輸問題的數(shù)學(xué)模型其中，ai和bj滿足：稱為產(chǎn)銷平衡條件。將約束方程式展開可得約束方程式中共mn個變量，m+n個約束。

上述模型是一個線性規(guī)劃問題。但是其結(jié)構(gòu)很特殊，特點如下：1.變量多（mn個），但結(jié)構(gòu)簡單。

技術(shù)系數(shù)矩陣

該系數(shù)矩陣中每列只有兩個元素為1，其余的都為零。2.m+n個約束中有一個是多余的（因為其間含有一個平衡關(guān)系式）所以R(A)=m+n-1，即解的mn個變量中基變量為m+n-1個。二、表上作業(yè)法

運(yùn)輸問題仍然是線性規(guī)劃問題，可以用線性規(guī)劃法中的單純形法來解決。但是：

1.運(yùn)輸問題所涉及的變量多，造成單純形表太大；2.若把技術(shù)系數(shù)矩陣A中的0迭代成非0，會使問題更加復(fù)雜。以上兩個原因使得我們不得不利用運(yùn)輸問題的特點設(shè)計出它的特殊解法——表上作業(yè)法。表上作業(yè)法，實質(zhì)上還是單純形法。其步驟如下：1.確定一個初始可行調(diào)運(yùn)方案?？梢酝ㄟ^最小元素法、西北角法、Vogel法來完成；2.檢驗當(dāng)前可行方案是否最優(yōu)，常用的方法有閉回路法和位勢法，用這兩種方法計算出檢驗數(shù)，從而判別方案是否最優(yōu)；3.方案調(diào)整，從當(dāng)前方案出發(fā)尋找更好方案，常采用閉回路法。二、表上作業(yè)法（續(xù)）

例3.1

某公司從三個產(chǎn)地A1、A2、A3將物品運(yùn)往四個銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表3-4所示

問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小?

即初始基本可行解的確定，與一般線性規(guī)劃問題不同，產(chǎn)銷平衡運(yùn)輸問題總是存在可行解。1、確定初始方案

確定初始基本可行解的方法很多，一般希望方法是既簡便，又盡可能接近最優(yōu)解。下面介紹兩種方法：最小元素法，西北角法、Vogel法（1）最小元素法

最小元素法的基本思想是優(yōu)先滿足單位運(yùn)價最小的供銷業(yè)務(wù)。

首先找出運(yùn)價最小的，并以最大限度滿足其供銷量為原則確定供銷業(yè)務(wù)。同樣的方法反復(fù)進(jìn)行直到確定了所有的供銷業(yè)務(wù)，得到一個完整的調(diào)運(yùn)方案即初始基本可行解為止。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表運(yùn)價表以此，得到一初始方案：X13=4,X14=3，

X21=3，X23=1，X32=6，

X34=3（有數(shù)格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（?。┯袛?shù)格是基變量，共m+n-1=3+4-1=6個?？崭袷欠腔兞?，共劃去m+n=7條線；（ⅱ）如果填上一個變量之后能同時劃去兩條線（一行與一列），就須在所劃去的該行或該列填一個0，此0格當(dāng)有數(shù)格對待。初始方案運(yùn)費(fèi)Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)（2）西北角法

西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運(yùn)價的供銷業(yè)務(wù)，而是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。

銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求365620342236方案表運(yùn)價表注：應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列。

當(dāng)填上一個數(shù)后行、列同時飽和時，也應(yīng)任意劃去一行(列)。在飽和的列（行）沒被劃去的格內(nèi)標(biāo)一個0,然后劃去該列（行）。

例3.2

某公司下屬有生產(chǎn)一種化工產(chǎn)品的三個產(chǎn)地A1、A2、A3，有四個銷售點B1、B2、B3、B4

銷售這種化工產(chǎn)品。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)（百元）如下表所示。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1753859A2402948A3806375需求35405565195

問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小?

解：用西北角法求初始基本可行解銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1753859A2402948A3806375需求35405565195方案表運(yùn)價表35400401565(3)伏格爾法（次小運(yùn)價與最小運(yùn)價之差大者先安排）銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求365620方案表運(yùn)價表2513

01160123212

3765122、判斷當(dāng)前方案是否為最優(yōu)

用單純形法解線性規(guī)劃問題時，在迭代過程中每次求得一個基本可行解以后，都要檢驗它是不是最優(yōu)解，如果不是最優(yōu)解，就要繼續(xù)進(jìn)行迭代，直到求得最優(yōu)解或者判定無最優(yōu)解。

表上作業(yè)法是用以下兩種方法來處理這個問題的：閉回路法和位勢法。（1）閉回路法

在單純形法中，為了檢驗一個基本可行解是不是最優(yōu)解，需要求出所有非基變量的檢驗數(shù)。在運(yùn)輸問題中，每個空格對應(yīng)一個非基變量。因此，我們需要求出每個空格的檢驗數(shù)。

由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗數(shù)都大于或等于零時該調(diào)運(yùn)方案就是最優(yōu)方案。

B1B2B3B4A143A231A363

①對方案表中每一空格，確定一條由空格出發(fā)的閉回路。閉回路是由水平或垂直線組成的閉合圖形。閉回路上的頂點除了這個空格外，其余均為有數(shù)格。B1B2B3B4A143A231A363

可以證明，對每一個空格都存在而且惟一存在這樣一條封閉回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363②計算出空格的檢驗數(shù)—等于閉回路上由此空格起奇數(shù)頂點運(yùn)價與偶數(shù)頂點運(yùn)價負(fù)值的代數(shù)和。B1B2B3B4A143A231A36311=3-3+2-1=122=9-2+3–0+5–4=131=7-5+10–3+2–1=1012=11-10+5-4=224=8–10+3–2=-133=10-5+10-3=12③當(dāng)所有空格檢驗數(shù)

σij≥0則當(dāng)前方案是最優(yōu)的，若尚有空格檢驗數(shù)小于零，表明當(dāng)前方案尚有待調(diào)整。

若所有的空格檢驗數(shù)都大于等于零，表明任何一個空格處調(diào)運(yùn)1單位都會引起總成本的上升，這表明當(dāng)前方案不能再改進(jìn)，即定為最優(yōu)方案。σ

ij

具有確切的經(jīng)濟(jì)意義，它表示由Ai往Bj增運(yùn)1單位時，引起的總運(yùn)輸成本的變化數(shù)。B1B2B3B4A143A231A363

閉回路法的主要缺點是：當(dāng)變量個數(shù)較多時，尋找閉回路以及計算都會產(chǎn)生困難。（2）位勢法（對偶變量法）

對于一個調(diào)運(yùn)方案的每列賦予一個值，稱為列位勢，記，對于每行賦予一個值，稱為行位勢，記為

則檢驗數(shù)為：

ij=cij-ui

-vji=1,…,m;j=1,…,n它們的值由下列方程組決定：其中，cij

是所有基變量（數(shù)字格）xij

的運(yùn)價系數(shù)。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表運(yùn)價表u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1u2u3v1v3v2v4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5令u1=5則有v4=5

v3=-2u2=4

u3=0v2=4v1=-311=c11–u1-v1=3–5–(-3)=1

12=c12–u1–v2=11–5–4=222=c22–u2–v2=9–4–4=1

24=c24–u2–v4=8–4–5=-1

31=c31–u3-v1=7–0–(-3)=1033=c33–u3–v3=10–0–(-2)=12再求非基變量（空格）檢驗數(shù)：

u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5（1）在有數(shù)格上填上相應(yīng)的運(yùn)價銷產(chǎn)B1B2B3B4A143A231A363方案表運(yùn)價表銷產(chǎn)B1B2B3B4A1310A212A345u1u2u3v1v3v2v4位勢法在表上進(jìn)行：(2)設(shè)u1=0，然后根據(jù)cij=ui+vj

（有數(shù)格），依次求得ui和vj的值，并填在相應(yīng)的位置銷產(chǎn)B1B2B3B4A1310A212A345u1u2u3v1v3v2v4239100-1-5計算(ui+vj)表，把(ui+vj)位勢和值填在表中相應(yīng)位置上，并將有數(shù)格位置上的值ui+vj

加上括號以示區(qū)別。（）（）（）（）（）（）2989-3-2(ui+vj)表銷產(chǎn)B1B2B3B4A1311310A21928A374105運(yùn)價表銷產(chǎn)B1B2B3B4A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5檢驗數(shù)表銷產(chǎn)B1B2B3B4A1A2A3（3）計算檢驗數(shù)表ij=cij–(ui

+vj)(ui+vj)表121-110123、調(diào)整方案

若在檢驗數(shù)上有某空格的檢驗數(shù)為負(fù)，則可改進(jìn)方案，降低成本。調(diào)整的方法是從具有負(fù)檢驗數(shù)的空格出發(fā)(有多個負(fù)檢驗數(shù)時，選擇絕對值大的一個)，沿它的閉回路進(jìn)行調(diào)整，即在保持方案可行的條件下，盡量增加空格上的運(yùn)量。從σij為最小負(fù)值的空格出發(fā).對其閉回路上的奇數(shù)頂點運(yùn)量增加θ,偶數(shù)頂點的運(yùn)量減少θ(這才能保證新的平衡)，其中調(diào)整量θ為該空格閉回路中偶數(shù)頂點的最小值。B1B2B3B4A143A231A363注：若閉回路的偶數(shù)頂點中同時有兩個格以上運(yùn)量為θ，則調(diào)整后其中一個變空格，其余填0。（保證基變量個數(shù)不變）（p48）B1B2B3B4A152A231A36324=-1，作x24

的閉回路，調(diào)整數(shù)=1，調(diào)整得再用閉回路法或位勢法求各空格的檢驗數(shù)，B1B2B3B4A152A231A363銷產(chǎn)B1B2B3B4A102A221A3912x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的

xij=0總運(yùn)費(fèi)為：

f=5×3+2×10+3×1+1×8+6×4+3×5=85

。

表中的所有檢驗數(shù)都非負(fù)，故上表中的解為最優(yōu)解。檢驗數(shù)表方案表表上作業(yè)法中需要說明的問題

（1）無窮多最優(yōu)解

當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運(yùn)輸問題有多重（無窮多）最優(yōu)解。上面的例題是多解情況銷產(chǎn)B1B2B3B4A102A221A3912B1B2B3B4A1250A213A363B1B2B3B4A152A231A363檢驗數(shù)表方案表調(diào)整方案表

（2）退化

當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運(yùn)量時需同時劃去運(yùn)輸表的一行和一列，這時就出現(xiàn)了退化。在運(yùn)輸問題中，退化解是時常發(fā)生的。為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化時應(yīng)在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為（m+n-1）個。表上作業(yè)法中需要說明的問題三、產(chǎn)銷不平衡的運(yùn)輸問題

前面我們討論的運(yùn)輸問題，都是產(chǎn)銷平衡的問題，即滿足

在實際問題中，產(chǎn)銷往往是不平衡的，遇到這種情況，我們可以經(jīng)過簡單的處理，使其轉(zhuǎn)化為產(chǎn)銷平衡問題，然后再按前面的方法來求解。1、產(chǎn)量大于銷量

對于產(chǎn)大于銷問題，可得到下列運(yùn)輸問題的模型：

可增加一個假想的銷地，其銷量為：

某個產(chǎn)地Ai運(yùn)到這個假想銷地Bn+1的物資量xi,n+1，實際上就意味著將這些物資在原產(chǎn)地貯存，其相應(yīng)的運(yùn)價，轉(zhuǎn)化為產(chǎn)銷平衡的問題，其數(shù)學(xué)模型為：

例3-3某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地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)用最?。夸N產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533625123114單位運(yùn)價表解：這里，總產(chǎn)量為78+45=123；總銷量為53+36+25=114。產(chǎn)銷不平衡，增加一個虛設(shè)的銷地，得到下表銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1781315120A2451129220需求5236259123銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求5336251231142、產(chǎn)量小于銷量

對于產(chǎn)小于銷問題

可增加一個假想的產(chǎn)地，其產(chǎn)量為：

其相應(yīng)的運(yùn)費(fèi)為

上述不平衡問題就轉(zhuǎn)化為平衡的問題，

例3-4某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地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)B1B2B3產(chǎn)量A113151278A211292245需求533665123154單位運(yùn)價表解:這里，總產(chǎn)量小于總銷量，產(chǎn)銷不平衡，增加一個虛設(shè)的產(chǎn)地，得到下表銷產(chǎn)B1B2B3產(chǎn)量B1B2B3A178131512A245112922A331000需求533665154銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533665123154四、應(yīng)用舉例

在變量個數(shù)相等的情況下，表上作業(yè)法的計算遠(yuǎn)比單純形法簡單。解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。下面為幾個典型的例子。

例3-5

有A1、A2、A3三個生產(chǎn)某種物資的產(chǎn)地，五個地區(qū)B1、B2、B3、B4、B5對這種物資有需求?，F(xiàn)要將這種物資從三個產(chǎn)地運(yùn)往五個需求地區(qū)，各產(chǎn)地的產(chǎn)量、各需求地區(qū)的需要量和各產(chǎn)地運(yùn)往各地區(qū)每單位物資的運(yùn)費(fèi)如下表所示，其中B2地區(qū)的115個單位必須滿足。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。夸N地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300運(yùn)輸費(fèi)用及產(chǎn)量、需求量表解：由于產(chǎn)量小于需求量，因此設(shè)一虛設(shè)產(chǎn)地A4,它的產(chǎn)量為需求量與產(chǎn)量的差20，與這一項有關(guān)的運(yùn)輸費(fèi)用一般為零。因為B2地區(qū)的115個單位必須滿足，即不能有物資從A4運(yùn)往B2地區(qū)，于是取相應(yīng)的費(fèi)用為M（M是一個充分大的正數(shù)），以保證在求最小運(yùn)輸費(fèi)用的前提下，該變量的值為零。銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300

可以建立如下產(chǎn)銷平衡的運(yùn)輸費(fèi)用表銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070

例3-6

某研究院有B1、B2、B3三個區(qū)。每年取暖分別需要用煤3500噸、1100噸、2400噸，這些煤都要由A1、A2兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量均相同。A1、A2煤礦的供應(yīng)能力分別為1500噸、4000噸，運(yùn)價（元/噸）如下表。

由于需求大于供給，經(jīng)院研究決定B1區(qū)供應(yīng)量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應(yīng)量不少于1600噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。銷地產(chǎn)地B1B2B3產(chǎn)量A11751952081500A21601822154000需求量350011002400

由于B1區(qū)供應(yīng)量可減少0—900噸，B3區(qū)供應(yīng)量不少于1600噸，可以把B1區(qū)和B3區(qū)分別設(shè)為兩個區(qū)：一個為必須滿足需求量的區(qū)域，另一個為可以調(diào)整供應(yīng)量的區(qū)域。

原問題化為五個需求區(qū)域B1、B1’、B2、B3、B3’的問題，同時增加一個虛設(shè)的產(chǎn)地A3。

在運(yùn)輸費(fèi)方面,必須滿足需求量的相應(yīng)變量，運(yùn)費(fèi)的取值為M，可調(diào)整需求量的相應(yīng)變量，運(yùn)費(fèi)的取值為0，作出產(chǎn)銷平衡的運(yùn)價表解：這是需求量大于生產(chǎn)量的運(yùn)輸問題銷地產(chǎn)地B1B1*B2B3B3*產(chǎn)量A11751751952082081500A21601601822152154000A2M0MM01500需求量260090011001600800

例3-7

某公司生產(chǎn)某種規(guī)格的設(shè)備，由于生產(chǎn)與季節(jié)有關(guān)系，生產(chǎn)能力與成本有差異，如下表所示。某種規(guī)格設(shè)備各季節(jié)的生產(chǎn)能力與成本

第一季度第二季度第三季度第四季度生產(chǎn)能力(臺)500700600200成本(萬元/臺）9.810.510.310.6

該廠年初簽訂的合同規(guī)定：當(dāng)年一、二、三、四每個季度末分別需要提供200、300、500、400臺這種規(guī)格的設(shè)備。如果生產(chǎn)出來的設(shè)備當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用為0.15萬元。試求在完成合同的前提下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的設(shè)備數(shù)目，則問題的線性規(guī)劃模型為：

cij=第i季度每臺的生產(chǎn)成本+0.15(j-i)（儲存、維護(hù)等費(fèi)用）。計算可得：

c11=9.8,c12=9.95,c13=10.1,c14=10.25,c22=10.5,c23=10.65,c24=10.8,c33=10.3,c34=10.45,c44=10.6。于是得到目標(biāo)函數(shù)：Minf=9.8x11+9.95x12+10.1x13+10.25x14++10.5x22+10.65x23+10.8x24+10.3x33++10.45x34+10.6x44x11=200x12+x22=300x13+x23+x33=500x14+x24+x34+x44=400

交貨：生產(chǎn)：x11+x12+x13+x14≤500x22+x23+x24≤700x33+x34≤600x44≤200xij

0i=1,2,3,4ji由于產(chǎn)大于銷，虛構(gòu)一個銷地，可構(gòu)造下列產(chǎn)銷平衡問題:各季節(jié)的生產(chǎn)、交貨費(fèi)用表交貨生產(chǎn)第一季度第二季度第三季度第四季度虛設(shè)交貨生產(chǎn)能力第一季度