管理運籌學講義第3章運輸問題

第3章運輸問題Subtitle學習要點1．掌握運輸問題的數(shù)學模型、系數(shù)矩陣特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握位勢法求解、牢固掌握三合一表格求解運輸問題過程1石家莊經(jīng)濟學院管理科學與工程學院§3.1運輸問題及其數(shù)學模型§3.2表上作業(yè)法§3.3產銷不平衡的運輸問題§3.4應用舉例本章主要內容第3章運輸問題2石家莊經(jīng)濟學院管理科學與工程學院§3.1運輸問題及其數(shù)學模型

問題的提出一般的運輸問題就是要解決把某種產品從若干個產地調運到若干個銷地，在每個產地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。回本章目錄3石家莊經(jīng)濟學院管理科學與工程學院

例3.1

某公司從三個產地A1、A2、A3將物品運往四個銷地B1、B2、B3、B4，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示

問應如何調運，可使得總運輸費最小?4石家莊經(jīng)濟學院管理科學與工程學院解：這是一個產銷平衡的運輸問題，設xij為從產地Ai運往銷地Bj的運輸量（i=1，2，3；j=1，2，3，4）該運輸問題的線性規(guī)劃模型如下：Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x345石家莊經(jīng)濟學院管理科學與工程學院s.t.x11+x12+x13+x14=7

x21+x22+x23+x24=4

x31+x32+x33+x34=9

x11+x21+x31=3

x12+x22+x32=6

x13+x23+x33=5

x14+x24+x34=6xij≥0(i=1、2、3；j=1、2、36石家莊經(jīng)濟學院管理科學與工程學院其系數(shù)矩陣為：共有m+n行，分別表示產地和銷地；有mn列分別表示各變量；每列只有兩個1，其余為0。7石家莊經(jīng)濟學院管理科學與工程學院

運輸問題的一般提法是：設某種物資有m個產地和n個銷地。產地Ai的產量為；銷地Bj的銷量為。從第i個產地向第j個銷地運輸每單位物資的運價為Cij，這就是由多個產地供應多個銷地的單品種物資運輸問題。問如何調運這些物資才能使總運費達到最小。8石家莊經(jīng)濟學院管理科學與工程學院表3-1產銷平衡表9石家莊經(jīng)濟學院管理科學與工程學院表3-2單位運價表10石家莊經(jīng)濟學院管理科學與工程學院

表中的表示由產地Ai向銷地Bj運輸物資的數(shù)量（即運量）。在產銷平衡表3-1中，去掉最后一行和最后一列余下的部分，稱為一個調運方案，或簡稱為一個方案?；蛘邔⑸鲜鰞蓚€表格合在一起，稱為運輸表（表3-3）。11石家莊經(jīng)濟學院管理科學與工程學院

銷地產地B1B2…Bn產量A1x11x12…x1na1A2x21x22…x2na2Amxm1xm2…xmnam銷量b1b2…bn

表3-3運輸表12石家莊經(jīng)濟學院管理科學與工程學院下面分兩種情況來討論：

（1）。即運輸問題的總產量等于其總銷量，這樣的運輸問題稱為產銷平衡的運輸問題。（2）。即運輸問題的總產量不等于總銷量，這樣的運輸問題稱為產銷不平衡的運輸問題。

我們重點討論產銷平衡的運輸問題及其求解方法。然后在此基礎上討論產銷不平衡的運輸問題應該如何轉化為產銷平衡的運輸問題。13石家莊經(jīng)濟學院管理科學與工程學院若用xij表示從Ai到Bj的運量，那么在產銷平衡的條件下，要求得總運費最小的調運方案，數(shù)學模型為：

14石家莊經(jīng)濟學院管理科學與工程學院其中，ai和bj滿足：(3-2)稱為產銷平衡條件。15石家莊經(jīng)濟學院管理科學與工程學院將（3-1）的結構約束加以整理，可知其系數(shù)矩陣的結構比較松散，且特殊16石家莊經(jīng)濟學院管理科學與工程學院該系數(shù)矩陣中對應于變量xij的系數(shù)向量Pij，其分量中除第i個和第m+j個為1以外，其余的都為零。即17石家莊經(jīng)濟學院管理科學與工程學院

根據(jù)運輸問題的數(shù)學模型求出的運輸問題的解，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調運數(shù)量為xij的物品給Bj。前已指出運輸問題是一種線性規(guī)劃問題，可設想用迭代法進行求解，即先找出它的某一個基可行解，再進行解的最優(yōu)性檢驗，若它不是最優(yōu)解，就進行迭代調整，以得到一個新的更好的解，繼續(xù)檢驗和調整改進，直至得到最優(yōu)解為止。18石家莊經(jīng)濟學院管理科學與工程學院

為了能按上述思路求解運輸問題，要求每步得到的解X=(xij)都必須是基可行解，這意味著:（1）解X必須滿足模型中的所有約束條件；（2）解中基變量xij的個數(shù)不能大于(m+n-1)個；原因是運輸問題中雖有(m+n)個約束條件，但由于總產量等于總銷量，故只有(m+n-1)個約束條件是線性獨立的。19石家莊經(jīng)濟學院管理科學與工程學院§3.2表上作業(yè)法表上作業(yè)法是求解產銷平衡運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行。其實質是單純形法。但具體計算和術語有所有同?？蓺w納為以下步驟：

回本章目錄20石家莊經(jīng)濟學院管理科學與工程學院（1）找出初始基本可行解（初始運輸方案）（2）求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉到下一步。（3）確定換入變量和換出變量，找出新的基本可行解。（4）重復（2），（3）直到得到最優(yōu)解為止。以上運算都可以在運輸表上完成。21石家莊經(jīng)濟學院管理科學與工程學院§3.2.1初始基本可行解的確定

與一般線性規(guī)劃問題不同，產銷平衡運輸問題總是存在可行解。不難驗證

≥

就是模型（3-1）的可行解。又因，目標函數(shù)值有下界，故產銷平衡的運輸問題必有最優(yōu)解。22石家莊經(jīng)濟學院管理科學與工程學院

確定初始基本可行解的方法很多，一般希望方法是既簡便，又盡可能接近最優(yōu)解。下面介紹三種方法：最小元素法，西北角法和伏格爾（Vogel）法。23石家莊經(jīng)濟學院管理科學與工程學院（1）最小元素法

最小元素法的基本思想是優(yōu)先滿足單位運價最小的供銷業(yè)務。首先找出運價最小的，并以最大限度滿足其供銷量為原則確定供銷業(yè)務。然后，在余下的未確定的供銷業(yè)務中找運價最小的，同樣以最大限度滿足其供銷量為原則確定供銷業(yè)務，同樣的方法反復進行直到確定了所有的供銷業(yè)務，得到一個完整的調運方案即初始基本可行解為止。由于該方法基于優(yōu)先滿足單位運價最小的供銷業(yè)務，故稱為最小元素法。

24石家莊經(jīng)濟學院管理科學與工程學院表3-5運輸表（運價小者先安排）銷產B1B2B3B4產量B1B2B3B4A17311310A241928A3974105需求3656201321344653103產銷平衡表運價表25石家莊經(jīng)濟學院管理科學與工程學院（2）西北角法

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

26石家莊經(jīng)濟學院管理科學與工程學院考慮例3.1某公司從三個產地A1、A2、A3將物品運往四個銷地B1、B2、B3、B4，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如表所示。27石家莊經(jīng)濟學院管理科學與工程學院問應如何調運，可使得總運輸費最小?28石家莊經(jīng)濟學院管理科學與工程學院銷產B1B2B3B4產量B1B2B3B4A17311310A241928A3974105需求365620342236產銷平衡表運價表29石家莊經(jīng)濟學院管理科學與工程學院注：應用西北角法和最小元素法，每次填完數(shù)，都應只劃去一行或一列。當填上一個數(shù)后行、列同時飽和時，也應任意劃去一行(列)，然后在保留的列（行）沒被劃去的格內標一個0。

例3.2

某公司下屬有生產一種化工產品的三個產地A1、A2、A3，有四個銷售點B1、B2、B3、B4銷售這種化工產品。各產地的產量、各銷地的銷量和各產地運往各銷地每噸產品的運費（百元）如下表所示。30石家莊經(jīng)濟學院管理科學與工程學院銷產B1B2B3B4產量B1B2B3B4A1753859A2402948A3806375需求35405565195產銷平衡表運價表

問應如何調運，可使得總運輸費最小?31石家莊經(jīng)濟學院管理科學與工程學院解：用西北角法求初始基本可行解銷產B1B2B3B4產量B1B2B3B4A1753859A2402948A3806375需求35405565195產銷平衡表運價表3540040156532石家莊經(jīng)濟學院管理科學與工程學院（3）伏格爾法(沃格爾法Vogel)

最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其它處要多花幾倍的運價。伏格爾法考慮到，某產地的產品假如不能按最小運價就近供應，就考慮次小運價，這就有一個差額。差額越大，說明不能按最小運價調運時，運費增加越多。因而對差額最大的行或列，就應當采用最小運價調運。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。

33石家莊經(jīng)濟學院管理科學與工程學院銷產B1B2B3B4產量B1B2B3B4A17311310A241928A3974105需求365620產銷平衡表運價表2513

01160123212

37651234石家莊經(jīng)濟學院管理科學與工程學院§3.2.2解的最優(yōu)性檢驗

用單純形法解線性規(guī)劃問題時，在迭代過程中每次求得一個基本可行解以后，都要檢驗它是不是最優(yōu)解，如果不是最優(yōu)解，就要繼續(xù)進行迭代，直到求得最優(yōu)解或者判定無最優(yōu)解。對于運輸問題來說，按單純形法來求檢驗數(shù)并進行迭代是非常困難的。表上作業(yè)法是用以下兩種方法來處理這個問題的：閉回路法和位勢法。35石家莊經(jīng)濟學院管理科學與工程學院一、閉回路法

在單純形法中，為了檢驗一個基本可行解是不是最優(yōu)解，需要求出所有非基變量的檢驗數(shù)。在運輸問題中，每個空格對應一個非基變量。因此，我們需要求出每個空格的檢驗數(shù)。由于目標要求極小，因此，當所有的檢驗數(shù)都大于或等于零時該調運方案就是最優(yōu)方案。

36石家莊經(jīng)濟學院管理科學與工程學院

定義3.1

閉回路是在已給出的調運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。37石家莊經(jīng)濟學院管理科學與工程學院

①閉回路均為一封閉折線，它的每一條邊，或為水平的，或為垂直的；②閉回路的每一條邊（水平的或垂直的）均有且僅有兩個頂點（基變量格）。

根據(jù)定義可以看出閉回路的一些明顯特點:：可以證明，如果對閉回路的方向不加區(qū)別，對每一個非基變量可以找到而且只能找到唯一的一個閉回路。38石家莊經(jīng)濟學院管理科學與工程學院所謂閉回路法，就是對于代表非基變量的空格（其調運量為零），把它的調運量調整為1，由于產銷平衡的要求,我們必須對這個空格的閉回路的頂點的調運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。39石家莊經(jīng)濟學院管理科學與工程學院方法：對每個非基變量xij

其檢驗數(shù)為

ij=(閉回路上的奇數(shù)次頂點單位運費之和)-(閉回路上的偶數(shù)次頂點單位運費之和)銷產B1B2B3B4產量B1B2B3B4A1437311310A23141928A363974105需求365620所以22=9-2+3–10+5–4=140石家莊經(jīng)濟學院管理科學與工程學院11=3-3+2-1=112=11-10+5-4=222=9-2+3–0+5–4=124=8–10+3–2=-131=7-5+10–3+2–1=1033=10-5+10-3=12閉回路法的主要缺點是：當變量個數(shù)較多時，尋找閉回路以及計算都會產生困難。

41石家莊經(jīng)濟學院管理科學與工程學院二、位勢法（對偶變量法）

對于一個調運方案的每列賦予一個值，稱為列位勢。記為：，對于每行賦予一個值，稱為行位勢，記為。它們的值由下列方程組決定：

其中，cij是所有基變量xij的系數(shù)?？梢宰C明，“任意確定一個u或v的值，其它u、v的值可以唯一決定”。對于任何非基變量xij，其檢驗數(shù)為：

ij=cij–(ui+vj)i=1,…,m;j=1,…,n42石家莊經(jīng)濟學院管理科學與工程學院

我們先給u1賦個任意數(shù)值，不妨設u1=0，則從基變量x13的檢驗數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等見上表。銷地產地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

123-5vj29310202031131085102947143石家莊經(jīng)濟學院管理科學與工程學院

應該說明，盡管各個u、v的值依賴于第一個取定的u或v的值，但ui+vi的值不變，故檢驗數(shù)的值是唯一確定的（不難看出，若某ui增加2，所有u均加2，所有v均減2，而u+v不變）。44石家莊經(jīng)濟學院管理科學與工程學院

如果某一個調運方案的所有空格的檢驗數(shù)都大于或等于零，則該調運方案是最優(yōu)方案。因為在這種情況下，方案的任何變動都不會使總的運費減少。當檢驗數(shù)表中有負的檢驗數(shù)時，說明該調運方案不是最優(yōu)方案，進一步調整，還可以使總的運費減少。

§3.2.3解的改進45石家莊經(jīng)濟學院管理科學與工程學院調整方法：

(1)找閉回路：以最小的負檢驗數(shù)對應的非基變量為起始頂點尋找一個閉回路。(2)求調整量：閉回路上偶數(shù)次頂點運量的最小值為調整量，記作：θ(3)調整：閉回路上的偶數(shù)次頂點的調運量減去θ；閉回路上的奇數(shù)次頂點的調運量加上θ；非閉回路頂點的其他變量調運量不變，這樣就得到一個新的運輸方案。46石家莊經(jīng)濟學院管理科學與工程學院

下表中紅色數(shù)字是用最小元素法確定的初始可行解的基變量，方格中的右上角數(shù)字是運價，帶圈的數(shù)字是用位勢法法求得的非基變量的檢驗數(shù)。銷地產地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

123-5vj29310202031131085102947147石家莊經(jīng)濟學院管理科學與工程學院銷產B1B2B3B4產量A1527A2314A3639需求36562024=-1，作x24的閉回路，調整數(shù)=1，調整得48石家莊經(jīng)濟學院管理科學與工程學院重新求新方案的檢驗數(shù)：可知所有的檢驗數(shù)均為非負，因此得到最優(yōu)解：

x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的xij=0總運費為：f=5×3+2×10+3×1+1×8+6×4+3×5=85。

如果非基變量的檢驗數(shù)有等于零的時候，將出現(xiàn)多解的情況。上面的例題是多解情況。49石家莊經(jīng)濟學院管理科學與工程學院§3.2.4表上作業(yè)法中需要說明的問題

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

當?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重（無窮多）最優(yōu)解。50石家莊經(jīng)濟學院管理科學與工程學院（2）退化當運輸問題某部分產地的產量和，與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運量時需同時劃去運輸表的一行和一列，這時就出現(xiàn)了退化。在運輸問題中，退化解是時常發(fā)生的。為了使表上作業(yè)法的迭代工作進行下去，退化時應在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為個。51石家莊經(jīng)濟學院管理科學與工程學院§3.3產銷不平衡的運輸問題

前面我們討論的運輸問題，都是產銷平衡的問題，即滿足在實際問題中，產銷往往是不平衡的，遇到這種情況，我們可以經(jīng)過簡單的處理，使其轉化為產銷平衡問題，然后再按前面的方法來求解。故本節(jié)著重于講清產銷不平衡轉化為產銷平衡的方法。下面分兩種情況來討論：產量大于銷量的情況以及銷量大于產量的情況?；乇菊履夸?2石家莊經(jīng)濟學院管理科學與工程學院§3.3.1產量大于銷量對于產大于銷問題，可得到下列運輸問題的模型：53石家莊經(jīng)濟學院管理科學與工程學院54石家莊經(jīng)濟學院管理科學與工程學院

可增加一個假想的銷地，其銷量為：由于假想的銷地實際上并不存在，因而由某個產地Ai運到這個假想銷地Bn+1的物資量xi,n+1，實際上就意味著將這些物資在原產地貯存，其相應的運價，上述不平衡問題就可以轉化為產銷平衡的問題，其數(shù)學模型為：55石家莊經(jīng)濟學院管理科學與工程學院56石家莊經(jīng)濟學院管理科學與工程學院例3-3某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？銷產B1B2B3產量B1B2B3A178131512A245112922需求533625

12311457石家莊經(jīng)濟學院管理科學與工程學院解：

這里，總產量為78+45=123；總銷量為53+36+25=114。產銷不平衡，增加一個虛設的銷地，得到下表銷產B1B2B3B4產量B1B2B3B4A1781315120A2451129220需求5236259123計算過程從略。58石家莊經(jīng)濟學院管理科學與工程學院§3.3.2產量小于銷量59石家莊經(jīng)濟學院管理科學與工程學院

可增加一個假想的產地，其產量為：由于假想的產地實際上并不存在，其產量當然也不存在。因此由假想產地運往某個銷地的物資數(shù)量，實際上就意味著銷地缺少這些物資供應的量，其相應的運費為。

上述不平衡問題就轉化為平衡的問題，

60石家莊經(jīng)濟學院管理科學與工程學院61石家莊經(jīng)濟學院管理科學與工程學院

例3-4某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表，問：應如何調運可使總運輸費用最小？銷產B1B2B3產量B1B2B3A178131512A245112922需求533665

12315462石家莊經(jīng)濟學院管理科學與工程學院解:這里，總產量小于總銷量，產銷不平衡，增加一個虛設的產地，得到下表銷產B1B2B3產量B1B2B3A178131512A245112922A331000需求533665154計算過程從略。63石家莊經(jīng)濟學院管理科學與工程學院

例3-5有A1、A2、A3三個生產某種物資的產地，五個地區(qū)B1、B2、B3、B4、B5對這種物資有需求?，F(xiàn)要將這種物資從三個產地運往五個需求地區(qū)，各產地的產量、各需求地區(qū)的需要量和各產地運往各地區(qū)每單位物資的運費如下表所示，其中B2地區(qū)的115個單位必須滿足。問：應如何調運可使總運輸費用最小？64石家莊經(jīng)濟學院管理科學與工程學院運輸費用及產量、需求量表銷地產地B1B2B3B4B5產量A1101520204050A22040153030100A33035405525130需求2511560307028030065石家莊經(jīng)濟學院管理科學與工程學院解：由于產量小于需求量，因此設一虛設產地A4,它的產量為需求量與產量的差20，與這一項有關的運輸費用一般為零。因為B2地區(qū)的115個單位必須滿足，即不能有物資從A4運往B2地區(qū)，于是取相應的費用為M（M是一個充分大的正數(shù)），以保證在求最小運輸費用的前提下，該變量的值為零。66石家莊經(jīng)濟學院管理科學與工程學院可以建立如下產銷平衡的運輸費用表銷地產地B1B2B3B4B5產量A1101520204050A22040153030100A33035405525130A40M00020需求2511560307067石家莊經(jīng)濟學院管理科學與工程學院

例3-6某研究院有B1、B2、B3三個區(qū)。每年取暖分別需要用煤3500噸、1100噸、2400噸，這些煤都要由A1、A2兩處煤礦負責供應，價格、質量均相同。A1、A2煤礦的供應能力分別為1500噸、4000噸，運價（元/噸）如下表。由于需求大于供給，經(jīng)院研究決定B1區(qū)供應量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應量不少于1600噸，試求總費用為最低的調運方案。68石家莊經(jīng)濟學院管理科學與工程學院銷地產地B1B2B3產量A11751952081500A21601822154000需求量350011002400解：這是需求量大于生產量的運輸問題，由于B1區(qū)供應量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應量不少于16005500700069石家莊經(jīng)濟學院管理科學與工程學院噸，可以把B1區(qū)和B3區(qū)分別設為兩個區(qū)：一個為必須滿足需求量的區(qū)域，另一個為可以調整供應量的區(qū)域。這樣，原問題化為五個需求區(qū)域B1、B1’、B2、B3、B3’的問題，同時增加一個虛設的產地A3。在運輸費方面,必須滿足需求量的相應變量，運費的取值為M，可調整需求量的相應變量，運費的取值為0，作出產銷平衡的運價表。70石家莊經(jīng)濟學院管理科學與工程學院銷地產地B1B1*B2B3B3*產量A11751751952082081500A21601601822152154000A3M0MM01500需求量260090011001600800計算過程從略71石家莊經(jīng)濟學院管理科學與工程學院§3.4應用舉例

在變量個數(shù)相等的情況下，表上作業(yè)法的計算遠比單純形法簡單。解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運輸問題的數(shù)學模型。下面為幾個典型的例子。回本章目錄72石家莊經(jīng)濟學院管理科學與工程學院

例3-7某公司生產某種規(guī)格的設備，由于生產與季節(jié)有關系，生產能力與成本有差異，如下表所示。某種規(guī)格設備各季節(jié)的生產能力與成本

第一季度第二季度第三季度第四季度生產能力(臺)500700600200成本(萬元/臺）9.810.510.310.673石家莊經(jīng)濟學院管理科學與工程學院該廠年初簽訂的合同規(guī)定：當年一、二、三、四每個季度末分別需要提供200、300、500、400臺這種規(guī)格的設備。如果生產出來的設備當季不交貨，每臺每積壓一個季度需儲存、維護等費用為0.15萬元。試求在完成合同的前提下，使該廠全年生產總費用為最小的決策方案。74石家莊經(jīng)濟學院管理科學與工程學院解：

設xij為第i季度生產的第j季度交貨的設備數(shù)目，則問題的線性規(guī)劃模型為：

cij=第i季度每臺的生產成本+0.15(j-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。75石家莊經(jīng)濟學院管理科學與工程學院于是得到目標函數(shù)：

Minf=9.8x11+9.95x12+10.1x13+10.25x14++10.5x22+10.65x23+10.8x24+10.3x33++10.45x34+10.6x44我們把第i季度生產的設備數(shù)目看作第i個生產廠的產量；把第j季度交貨的設備數(shù)目看作第j個銷售點的銷量；成本加儲存、維護等費用看作運費。由于產大于銷，虛構一個銷地，可構造下列產銷平衡問題:76石家莊經(jīng)濟學院管理科學與工程學院

各季節(jié)的生產、交貨費用表

交貨生產第一季度第二季度第三季度第四季度虛設交貨生產能力第一季度9.89.9510.110.250500第二季度M10.510.6510.80700第三季度MM10.310.450600第四季度MMM10.60200交貨量200300500400600200077石家莊經(jīng)濟學院管理科學與工程學院

例3-8

某航運公司承擔六個港口城市A，B，C，D，E，F(xiàn)的四條固定航線的物資運輸任務。已知各條航線的起點、終點城市及每天航班數(shù)見表3-8。假定各條航線使用相同型號的船只，各城市間的航班天數(shù)見表3-9。每條船只每次裝卸貨的時間各需1天。問該航運公司至少應配備多少條船，才能滿足所有航線的運貨需求？78石家莊經(jīng)濟學院管理科學與工程學院表3-8航線起點城市終點城市每天班數(shù)1234EBADDCFB321179石家莊經(jīng)濟學院管理科學與工程學院表3-9到從ABCDEFABCDEF012147710313882301555141315017207851703785203O80石家莊經(jīng)濟學院管理科學與工程學院

解

該公司所需配備船只可分兩部分：（1）載貨航程需要的周轉船只數(shù)。例如航線1，在港口E裝貨1d，E至

D航程17d，在D卸貨1d,總計19d。每天3航班，故該航線周轉船只需57條，各條航線周轉所需船只數(shù)見表3-10。以上累計共需周轉船只數(shù)91條。81石家莊經(jīng)濟學院管理科學與工程學院

（2）各港口間調度所需船只數(shù)。有些港口每天到達船只數(shù)多于需要發(fā)出船只數(shù)，例如港口D，每天到達3條，需求1條；而有些港口到達數(shù)少于需求數(shù)，例如港口B。各港口每天余缺船只數(shù)的計算如表3-11所示。航線裝貨天數(shù)航程天數(shù)卸貨天數(shù)小計航班數(shù)需周轉船只數(shù)12341111173713111119591532115710915表3-10

82石家莊經(jīng)濟學院管理科學與工程學院表3-11港口城市每天到達每天需求余缺數(shù)ABCDEF012301120130-1-122-31

為使配備船只數(shù)最小，應做到周轉的空船數(shù)最少。因此建立以下運輸問題，其產銷平衡表如表3-12所示。83石家莊經(jīng)濟學院管理科學與工程學院表3-12ABE每天多余船只CDF221每天缺少船只113

84石家莊經(jīng)濟學院管理科學與工程學院單位運價表應為相應各港口之間的船只航程天數(shù)如表3-13所示。

表3-13ABECDF21473138517385石家莊經(jīng)濟學院管理科學與工程學院用表上作業(yè)法求出空船的最優(yōu)解調度方案如表3-14所示。

表3-14ABE每天多余船只CDF1121221每天缺少船只113

由表3-14知算出最少需周轉的空船數(shù)為40條，這樣在不考慮維修、儲備等情況下，該公司至少應配備131條船。MinZ=1X14+1X13+2X5+1X3=4086石家莊經(jīng)濟學院管理科學與工程學院課堂練習一、產銷不平衡的運輸問題1.石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供應能力分別為1500、4000噸，運價為：由于需大于供，經(jīng)院研究決定一區(qū)供應量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應量不少于1500噸，試求總費用為最低的調運方案。解：根據(jù)題意，作出產銷平衡與運價表：這里M代表一個很大的正數(shù)，其作用是強迫相應的x31、x33、x34取值為0。87石家莊經(jīng)濟學院