運籌學（第2版）課件 第二章 運輸問題

南京航空航天大學經(jīng)濟與管理學院運籌學第二章運輸問題

前面討論了一般線性規(guī)劃問題的數(shù)學模型的建立和求解方法，但在實際工作中，往往碰到有些線性規(guī)劃問題，它們的約束條件系數(shù)矩陣具有特殊結構，這就使我們有可能找到比單純形法更為簡單的求解方法，從而節(jié)約大量的計算時間和費用。本章所討論的運輸問題就是屬于這樣一類特殊的線性規(guī)劃問題。

在日常生產(chǎn)和經(jīng)營管理過程中，常常遇到這樣一類問題：公司有若干個生產(chǎn)單位與銷售單位，根據(jù)各生產(chǎn)單位的產(chǎn)量及銷售單位的銷售量，并且知道各生產(chǎn)單位到各銷售單位之間的運輸單價，該公司應如何將產(chǎn)品運到各銷售單位而使總的運輸費用最小？運輸問題是特殊的線性規(guī)劃問題，它是早期的線性網(wǎng)絡最優(yōu)化的一個例子。運輸問題不僅代表了物資合理調運、車輛合理調度等問題，有些其他類型的問題經(jīng)過適當變換后也可以歸結為運輸問題。運輸問題是極具實際意義的研究。運輸問題中最有名的一個實例是羅馬尼亞薪柴配送問題。當時的研究條件相當艱苦，整個羅馬尼亞只有一臺計算機和兩位程序員。在沒有計算機的幫助下，巴拉斯硬是和八名學生一起通過手算的方式，利用線性規(guī)劃技術成功解決了當時羅馬尼亞交通領域的大難題——薪柴配送問題，為整個羅馬尼亞節(jié)約了8%的運輸成本，這在當時引起了極大轟動。小有成就后，巴拉斯進入了木材工業(yè)設計院工作，領導院里的線性規(guī)劃小組。發(fā)展簡史

發(fā)展簡史

2.1運輸問題的數(shù)學模型例2.1某公司有3個生產(chǎn)同類產(chǎn)品的生產(chǎn)地點（以后稱為產(chǎn)地），運往4個銷售地（以后稱為銷地）銷售，各產(chǎn)地的生產(chǎn)量、各銷地的銷售量以及各產(chǎn)地到各銷地的單位產(chǎn)品運價如表2.1所示。問該公司應如何調運產(chǎn)品，在滿足各銷地的需要量的前提下，使總的運費為最小。假設xij

表示從Ai到Bj

的運量,Z表示的運輸費用，從而得到其數(shù)學模型:

在該模型中，目標函數(shù)要求其極小化；前4個約束條件的意義是由各產(chǎn)地運往某一銷地的物品數(shù)量之和等于該銷地的銷量；第(5),(6),(7)這3個約束條件表示由某一產(chǎn)地運往各銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量;最后一個約束條件表示決策變量的非負條件。

可見運輸問題是一種線性規(guī)劃問題。對于一般情況，假設有m個生產(chǎn)地點，可以供應某種物資(以后稱為產(chǎn)地)，用Ai表示，i=1,2,…,m；有n個銷售地(以后稱為銷地)，用Bj表示，j=1,2,…,n；產(chǎn)地的產(chǎn)量和銷地的銷售量分別為ai,i=1,2,…,m和bj，j=1,2,…,n，從Ai到Bj運輸單位物資的運價為cij，這些數(shù)據(jù)可匯總于如表2.2。如果運輸問題的總產(chǎn)量等于其總銷量，即則稱該運輸問題為產(chǎn)銷平衡運輸問題；反之，稱為產(chǎn)銷不平衡運輸問題。下面建立在產(chǎn)銷平衡情況下的運輸問題的數(shù)學模型。假設xij表示從Ai到Bj的運量,則所求的數(shù)學模型為:下面建立在產(chǎn)銷不平衡情況下的運輸問題的數(shù)學模型。當產(chǎn)大于銷時，即時，運輸問題的數(shù)學模型可以寫成：當銷大于產(chǎn)時即時，運輸問題的數(shù)學模型可以寫成：2.2運輸問題的基本可行解

針對運輸問題的數(shù)學模型結構的特殊性，它的約束方程組的系數(shù)矩陣具有如下特點：（1）在該矩陣中，它的元素均等于0或1；（2）每列只有兩個元素為1，其余元素都是0；（3）對應于每一個變量，在前m個約束方程中只出現(xiàn)一次，在后n個約束方程中也只出現(xiàn)一次。（2.1）

根據(jù)運輸問題的數(shù)學模型求出的運輸問題的解，它代表著一個運輸方案，其中每一個變量xij的值表示由Ai調運到Bj的物品數(shù)量。由于運輸問題也是一個線性規(guī)劃問題，因此在求解時，我們與使用單純形方法類似，首先應當確定該問題的基變量個數(shù)；其次，要知道這樣一組基變量應當是由哪些變量來組成（也就是要求出初始基本可行解）。運輸問題的解X必須要滿足模型中的所有約束條件；基變量對應的約束方程組的系數(shù)列向量必須是線性無關的；可以證明系數(shù)矩陣（2.1）的秩是m+n-1。一方面矩陣的前m行相加之和減去后n行之和結果是0向量，因此該矩陣的秩小于m+n；另一方面有矩陣（2.1）的第2行至第m+n行和前n列及

對應的列交叉處的元素構成m+n-1階方陣D，D的行列式。

因此矩陣A的秩恰好等于m+n-1，可以證明m+n個方程中的任意m+n-1個方程的系數(shù)向量都是線性無關的。

因此在運輸問題中解的基變量個數(shù)應由m+n-1個變量組成(即基變量的個數(shù)=產(chǎn)地個數(shù)+銷售地個數(shù)–1)。進一步我們想知道，怎樣的m+n-1個變量會構成一組基變量？為此我們需要引入一些基本概念，通過對這些基本概念的分析和討論，結合單純形算法的基本結果，便可得出我們所需要的結論。定義2.1凡是能排成：或互不相同，且互不相同，且形成的變量的集合稱之為一個閉回路。而把出現(xiàn)在閉回路中的變量稱為這個閉回路的頂點。例2.2設m=3，n=4，決策變量表示由產(chǎn)地Ai調運到銷地Bj的數(shù)量，如表2.3中，x11、x12、x32、x34、x24、x21構成一個閉回路。這里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4。

銷地產(chǎn)地B1B2B3B4A1x11x12

A2x21

x24A3

x32

x34若把閉回路的頂點都在表中畫出，并且把相鄰的頂點都用一條直線連接起來，就可以得到一條封閉的折線，并且折線的每一條邊或者是水平的，或者是垂直的。另外表中每一行和每一列由折線相連的閉回路的頂點只有兩個。如表2.4，即頂點為{x12、x32、x34、x14}和表2.5，即頂點為{x11、x12、x22、x24、x34、x31}也分別構成兩個閉回路。

表2.4

表2.5定理2.1

m+n-1個變量

構成基變量的充分必要條件是它不包含有任何閉回路。

該定理給出了運輸問題基的一個重要特征，這個結論是非常重要的，因為利用它可以判斷m+n-1個變量是否構成基變量，它比直接判斷這些變量所對應的系數(shù)列向量組是否線性無關要簡單和直觀。

如果定理2.1中的m+n-1個基變量全部大于等于0，這時是基本可行解。開始結束按某種規(guī)則找出一個初始解（初始調運方案）在運輸表上對其進行調整，得出一個新解現(xiàn)行解為最優(yōu)性YesNo2.3運輸問題表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質是單純形算法。只是具體計算和術語有所不同，可歸納為：（1）找出初始基可行解，即在(mn)產(chǎn)銷平衡表上給出m+n-1個有數(shù)字的格，這些有數(shù)字的格不能構成閉回路，且行和等于產(chǎn)量，列和等于銷售量；（2）求各非基變量的檢驗數(shù)，即在表上求出空格的檢驗數(shù)，判斷是否達到最優(yōu)解。如果達到最優(yōu)解，則停止計算，否則轉入下一步；（3）確定換入變量和換出變量，找出新的基可行解，在表上用閉回路法進行調整。（4）重復（2）、（3）步，直到求得最優(yōu)解為止。以下具體給出求解運輸問題表上作業(yè)法的計算步驟。2.3.1確定初始基可行解確定初始基可行解即首先給出初始的調運方案，方法很多，我們只介紹其中的兩種方法：（1）最小元素法最小元素法的基本思想就是就近供應。即從單位運價表中最小的運價開始確定產(chǎn)銷關系，依次類推，直到給出初始方案為止。下面通過例2.3來說明最小元素法確定初始基可行解的具體步驟。例2.3用最小元素法求例2.1的初始運輸方案。解：第一步：從單位運價表2.1中找出最小的單位運價為1，這表示先將A2的產(chǎn)品供應給B1。由于A2每天生產(chǎn)4噸，B1每天只需要3噸，即A2除每日能滿足B1的需要外還剩余1噸。因此在產(chǎn)銷平衡表(A2,B1)交叉處填上3(即x21=3=min(a2,b1)=min(4,3))，表示A2調運3噸給B1，再在單位運價表中將B1這一列單位運價劃去，表示B1的需求已滿足，不需要繼續(xù)調運。第二步:從上述未劃去的單位運價表的元素中再找出最小的單位運價2，即A2把剩余的產(chǎn)品供應給B3；B3每天需要5噸，A2只剩余1噸，因此在上述產(chǎn)銷平衡表的(A2,B3)交叉處填上1，劃去上述單位運價表中A2這一行單位運價，表示A2的產(chǎn)品已分配完畢，如表2.6所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A21③92①84A3741059銷量3656

表2.6第三步:在表2.6中，未劃去的元素中找出最小單位運價為3。這表示將A1的產(chǎn)品供應B3，A1每天生產(chǎn)7噸，B3尚缺4噸，因此在產(chǎn)銷平衡表的(A1,B3)交叉處填上4，由于B3的需求已滿足，將單位運價表中的B3這一列單位運價劃去。如此，一步步進行下去，直到單位運價表中所有元素都劃去為止，最終在產(chǎn)銷平衡表上就可以得到一個初始調運方案。這個方案的總運費為86元，如表2.7所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1

437A23

1

4A3

6

39銷量3656

表2.7檢查全表，產(chǎn)銷已平衡，得到初始調運方案為：,

其余。

有數(shù)字的格的總數(shù)應為6個（m+n–1=6），而這6個變量包含有任何回路，滿足定理2.1，所以是一個基本解。又滿足模型的所有約束條件，所以是可行解。該方案對應的解是一個基本可行解。該調運方案的運費為86。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1

437A23

1

4A3

6

39銷量3656

表2.7

應當注意的是，在用最小元素法確定初始基可行解的時候，有可能出現(xiàn)以下的兩種特殊情況：

一是當在中間步驟的未劃去的單位運價表中尋找最小元素時，有多個元素同時達到最小，這時從這些最小元素中任意選擇一個作為基變量；

二是當在中間步驟的未劃去的單位運價表中尋找最小元素時，發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于該元素所在列的剩余銷售量。這時在產(chǎn)銷平衡表相應的位置填上該剩余產(chǎn)量數(shù)，而在單位運價表中就要同時劃去一行和一列。為了使調運方案中有數(shù)字的格仍為（m+n–1）個，需要在同時劃去的行或列的任一空格位置添上一個“0”，這個“0”表示該變量是基變量，只不過它取值為0，即此時的調運方案是一個退化的基可行解。最小元素法代碼展示（2）伏格爾法

最小元素法的缺點是，為了節(jié)省一處的費用，有時造成在其它地方要花多幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品，假如不能按最小運費就近供應，就考慮次小運費。這就有一個差額，差額越大，說明不能按最小運費調運時，運費增加就越多。因此，對于差額最大處，就優(yōu)先采用最小運費調運。例2.4用最伏格爾法求例2.1的初始運輸方案。步驟如下：第一步：在單位運價表中增加一行和一列，列的格位置相應填入該行的次小運費與最小運費之差，我們稱之為行差額。行的格位置相應填入該列的次小運費與最小運費之差，我們稱之為列差額。如此可得表2.8：

銷地產(chǎn)地B1B2B3B4行差額A13113100A219281A3741051列差額2513

表2.8第二步：從行差額和列差額中選出最大者，選擇它所在的行或列中的最小元素。比較該元素所在的行和列的產(chǎn)量與銷量，取它們最小者填入產(chǎn)銷平衡表相應的位置。同時在單位運價表中劃去一行或一列。由于B2

的列差額最大。B2

列中最小元素為4（即A3

行），可確定A3

產(chǎn)品優(yōu)先供應B2

。比較它們的產(chǎn)量和銷量，可知產(chǎn)地A3的產(chǎn)量為9，銷地B2的銷量為6，因此在產(chǎn)銷平衡表的(A3,B2)空格處填入6，由于銷地B2已經(jīng)滿足，因此在單位運價表中劃去B2

列。第三步：對上述未劃去的元素中計算出各行、各列的差額。重復第一、二步的工作，直到給出初始解為止。本問題利用伏格爾方法給出的初始調運方案如表2.9所示。由以上可見：伏格爾方法同最小元素法除在確定供求關系的原則上不同外，其余步驟相同，因而給出的初始調運方案也是基可行解。一般來說，用伏格爾方法所求出的初始解比用最小元素法求出的初始解更接近于最優(yōu)解。本例用伏格爾方法給出的初始解的總運費為85元。表2.9

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1

527A23

14A3

6

39銷量3656

伏格爾法代碼展示2.3.2最優(yōu)解的判別

得到運輸問題的初始基可行解后就要判別這個解是否為最優(yōu)解，判別的方法是計算非基變量即空格的檢驗數(shù)。因運輸問題的目標函數(shù)是要求實現(xiàn)最小化，所以當所有的非基變量檢驗數(shù)全都大于等于0時為最優(yōu)解。下面介紹兩種求空格檢驗數(shù)的方法。

（1）閉回路法

在給出調運方案的計算表上，如表2.7，從每一空格出發(fā)，找一條閉回路。它是以空格為起點，用水平線或垂直線向前劃，每碰到一數(shù)字格就轉90度后繼續(xù)前進。直到回到起始空格處為止。該閉回路除了起始頂點是非基變量外，其它頂點均為基變量（對應著數(shù)字格）?？梢宰C明，如果對閉回路的方向不加區(qū)別，對于任一非基變量而言，以每個空格為起點的閉回路都存在且唯一。如(A1,B1)空格與(A1,B3)、(A2,B3)和(A2,B1)三個有數(shù)字的格構成一閉回路，如此等等。

閉回路計算檢驗數(shù)的經(jīng)濟解釋為：在已給出初始解的表2.7中，可以從任一空格出發(fā)，如從(A1,B1)出發(fā)，若讓A1

的產(chǎn)品調1噸給B1，為了保持產(chǎn)銷平衡，就要依次作調整：在(A1,B3)處減少1噸，(A2,B3)處增加1噸，(A2,B1)處減少1噸，即構成了以(A1,B1)空格為起點，其它為有數(shù)字的格的閉回路。如表2.10中的直線所示。各頂點所在格的右上角的數(shù)字是單位運價。表2.10

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13（＋1）

34（－1）

37A213（－1）

21（＋1）

4A3

6

39銷量3656

可見這一調整方案使運費增加了：(+1)

3+(-1)

3+(+1)

2+(-1)

1=1(元)這表明若這樣調整運輸方式將增加運費。將“1”這個數(shù)填入(A1,B1)格，這就是該空格的檢驗數(shù)。按以上所述，就可以找出所有空格的檢驗數(shù)，見如下表2.11表2.11空格閉

回

路檢驗數(shù)(A1,B1)(1,1)→(1,3)→(2,3)→(2,1)→(1,1)1(A1,B2)(1,2)→(1,4)→(3,4)→(3,2)→(1,2)2(A2,B2)(2,2)→(2,3)→(1,3)→(1,4)→(3,4)→(3,2)→(2,2)1(A2,B4)(2,4)→(2,3)→(1,3)→(1,4)→(2,4)-1(A3,B1)(3,1)→(3,4)→(1,4)→(1,3)→(2,3)→(2,1)→(3,1)10(A3,B3)(3,3)→(3,4)→(1,4)→(1,3)→(3,3)12這時檢驗數(shù)還存在負數(shù)，因為(A2,B4)空格的檢驗數(shù)為–1，這說明表2.7給出的調運方案還不是最優(yōu)解，還需要進一步改進，改進方法見本節(jié)后面的基可行解的改進方法。（2）位勢法

用閉回路法求檢驗數(shù)時，需要給每一空格找一條閉回路。當產(chǎn)銷點很多時，空格的數(shù)量很大，計算檢驗數(shù)將十分費時。下面介紹一種較為簡便的方法——位勢法。

是一組基可行解，現(xiàn)在引進m+n

個未知量u1,···,um,v1,···,vn，由上述基本可行解可構造如下一個方程組：其中

為變量對應的單位運價。方程組（2.1）共有m+n個未知數(shù)和m+n-1個方程。(2.1)的解存在且恰有一個自由變量。稱u1,···,um

，v1,···,vn為列位勢。定理2.2

設已給了一組基本可行解，則對每一個非基變量xij

來說，它所對應的檢驗數(shù)為：

ij=cij–(ui+vj

)(2.2)

下面,我們就以例子來說明這種方法的具體實施過程。

仍以例2.3所給出的初始基可行解表2.7為例：第一步：在對應表2.7的數(shù)字格處填入單位運價如表2.12所示：銷地產(chǎn)地B1B2B3B4A1

331010A211

22

A3

44

55表2.12第二步：在表2.12上增加一行和一列，列中填入行位勢ui

，行中填入列位勢vj

得表2.13。表2.13銷地產(chǎn)地B1B2B3B4行位勢uiA1

3310100A211

22

－1A3

44

55－5列位勢vj29310

先令u1=0（一般令行和列中數(shù)字格（基變量）多的行位勢或列位勢令為0），然后按ui+vj=cij

(i,j)

基變量指標集

，相繼確定ui、vj

。由表3—15可見，當u1=0時，由u1+v3=c13=3可得v3

=3，由u1+v4=c14=10，可得v4

=10；在v4

=10時，由u3+v4=c34=5可得u3=-5。以此類推可確定所有的ui、vj的值。第三步：按

ij=cij–(ui+vj

),(i,j)

非基變量指標集，計算所有的空格檢驗數(shù)。如：

11

=c11–(u1+v1

)=3–(0+2)=1

12

=c12–(u1+v2

)=11-(0+9)=2這些計算可直接在表2.13上進行。為了方便，特設計計算表，如表2.14。右上角框內(nèi)的數(shù)為單位運價。在表2.14中檢驗數(shù)還有小于0的，說明還未達到最優(yōu)解，還得進一步進行改進。表2.14銷地產(chǎn)地B1B2B3B4行位勢uiA131112301000A21091208-1－1A371040101250－5列位勢vj29310

2.3.3基可行解改進的方法——閉回路調整法

當計算完所有的空格檢驗數(shù)時，如果檢驗數(shù)還有小于0的，這表明還未達到最優(yōu)解。若有兩個或兩個以上的檢驗數(shù)小于0時，一般選擇其中最小的小于0的檢驗數(shù)，以它對應的空格為調入格。即以它對應的非基變量為換入變量。由表2.14可知(A2,B4)為調入格（即以它對應的變量x24

為換入變量）。以x24為出發(fā)點，作一閉回路為x24→x14→x13→x23，如表2.15所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1

4(+1)3(-1)7A23

1(-1)(+1)4A3

6

39銷量3656

表2.15

在閉回路上作運量調整，稱空格點x24為第1頂點，x14，x13，x23，分別稱為第2，3，4頂點，(A2,B4)格的調入量

是選擇閉回路上偶數(shù)格中運量的最小者，即

=min{1,3}=1(其原理與單純形法中按

規(guī)則來確定的換出變量是相同)，然后在閉回路上的奇頂點加入該調整量，偶頂點減入該調整量，，得到調整方案如表2.16所示。對表2.16給出的解，再用閉回路法或位勢法求各空格的檢驗數(shù)，這時表中的所有檢驗數(shù)全都大于等于0，所以表2.16所給出的解為最優(yōu)解。這時得到的總運費的最小值是85元。表2.16

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1

527A23

14A3

6

39銷量3656

2.4運輸問題的Excel求解方法2.4.1產(chǎn)銷平衡運輸問題例2.5使用Excel規(guī)劃求解工具求解例2.1。方法如下：Step(1)根據(jù)題目條件，建立電子表格如圖2.1，其中第2-5行是運費表，第7-15行是規(guī)劃求解需要的表格。其中的C8:F10是規(guī)劃求解的可變單元格區(qū)域，用于存放從3個產(chǎn)地發(fā)往4個銷地的產(chǎn)品數(shù)量，為便于識別進行了顏色填充。圖2.1電子表格Step(2)對電子表格的單元格編輯公式。

第11行用于對3個產(chǎn)地的供貨數(shù)量進行求和，以便于與存量目標進行對比。單擊C11單元格后如圖2.2輸入公式C11=SUM(C8:C10)點擊對號符號“√”，則完成對C11單元格的公式輸入。并向右復制填充至F11單元格。圖2.2單元格公式輸入G列用于對4個銷地的實際到貨數(shù)量進行求和，以便于與產(chǎn)地的產(chǎn)量進行對比。在G8單元格內(nèi)輸入公式G8=SUM(C8:F8)并向下復制填充至G10單元格。

第13行用于計算實際到貨量與需求量之間的差額，即缺貨量。在C13單元格內(nèi)輸入公式C13=C12-C11并向右復制填充至F13單元格。I列用于計算3個產(chǎn)地的產(chǎn)量與實際供貨量之間的差額，在I8單元格內(nèi)輸入公式I8=H8-G8并向下復制填充至I10單元格。C15是目標單元格用于計算實際產(chǎn)生的運輸費用：C15=SUMPRODUCT(C3:F5,C8:F10)所有公式輸入結束之后，當點擊公式下的顯示公式，會看到編輯的所有公式見圖2.4。Step(3)選中C15單元格，打開“規(guī)劃求解參數(shù)”對話框，在“設置目標單元格”文本框中選擇C15單元格，選中“最小值”按鈕，在“可變單元格”文本框中選擇C8:F10單元格區(qū)域。圖2.4Step(4)單擊“添加”按鈕，打開“添加約束”對話框進行約束條件的添加，本例所包含的約束條件如下：

條件1：C11:F11=C12:F12

條件2：G8:G10=H8:H10添加完成，單擊“添加約束”對話框中的“確定”按鈕，返回“規(guī)劃求解參數(shù)”對話框，結果如圖2.5所示。圖2.5設置規(guī)劃求解參數(shù)因為是供需平衡，所以條件1表示需求全部滿足，有實際到貨總量=需求量；條件2表示產(chǎn)量全部用完，即有實際供貨量=產(chǎn)量。Step(5)因為所有變量的運算均是線性運算并且要求變量是正數(shù)，所以選擇“使無約束變量為非負數(shù)”選項。為了提高規(guī)劃求解的運算效率，可以單擊“單純線性規(guī)劃”復選框旁的“選項”按鈕，打開“所有方法”對話框，如圖2.6所示。圖2.6采用線性模型和假定非負Step(6)單擊“確定”按鈕返回“規(guī)劃求解參數(shù)”對話框，然后單擊“求解”按鈕開始求解運算過程，顯示找到一個結果。單擊“規(guī)劃求解結果”對話框中的“確定”按鈕保存此結果，如圖2.7所示?？芍Y果顯示總運費為85。圖2.7運輸問題求解結果2.4.2產(chǎn)銷不平衡運輸問題（1）當產(chǎn)量大于銷量例2.6

若例2.1中A2產(chǎn)量增加到6,該運輸問題如何用Excel求解呢?

解：此時，總產(chǎn)量>總銷量。使用Excel規(guī)劃工具求解時按照例2.5的步驟操作，注意以下幾個步驟：Step(1)圖2.3中H9數(shù)據(jù)單元格的值由4改為6。Step(4)添加2個約束如下：條件1：C11:F11=C12:F12條件2：G8:G10<=H8:H10。因為是產(chǎn)量大于銷量，條件1：實際到貨總量=需求量，表示需求全部滿足；條件2：實際供貨總量<=產(chǎn)量，表示產(chǎn)量有剩余。最后求解的結果如圖2.8所示。圖2.8生產(chǎn)量大于銷售量的求解結果（2）當產(chǎn)量小于銷量例2.7

若將例2.1中B3的需求調整為7,該運輸問題如何用Excel求解呢?解：此時，總產(chǎn)量<總銷量。使用Excel規(guī)劃工具求解時按照例2.5的步驟操作，注意以下幾個步驟：Step(1)將圖2.3中B3的需求對應的數(shù)據(jù)單元格E12由5改為7。Step(4)如果仍用例2.6的2個約束Step(6)求解結果顯示無解，如圖2.9所示。圖2.9生產(chǎn)量小于銷售量的求解結果可以判斷是供不應求，而事實確實如此。那么該怎么做呢？Step(4)選中要修改的約束單擊【更改】按鈕，改變一下條件1和條件2。條件1：C11:F11<=C12:F12條件2：G8:G10=H8:H10Step(6)最后求解的結果如圖2.10所示。圖2.10改變條件后生產(chǎn)量小于銷售量的求解結果

結果顯示，產(chǎn)地的生產(chǎn)量沒有剩余的同時B4銷地還缺貨2噸，總運費為71元。2.5案例分析案例分析1（生產(chǎn)玩具銷售）某玩具公司分別生產(chǎn)三種新型玩具，每月可供應量分別為1000件、2000件、2000件，它們分被送到甲、乙、丙三個百貨商店銷售。已知每月各百貨商店各類玩具總和的預期銷售量均為1500件，由于經(jīng)營方面原因，各商店銷售不同玩具的盈利額不同（見表2.18）。又知道丙百貨商店要求至少供應C玩具1000件，而拒絕A玩具。求滿足上述條件下使總盈利額為最大的供銷分配方案。

甲乙丙可供應量A54—1000B16892000C1210112000表2.18三種新型玩具有關數(shù)據(jù)解：由于總供應量為1000+2000+2000=5000,總需求量（預期銷售量）為1500+1500+1500=4500，總供應大于總需求，因此是產(chǎn)大于銷的運輸問題。用Excel求解時其電子表格模型見圖2.11。圖2.11生產(chǎn)玩具銷售案例數(shù)學模型單元格公式參照圖2.12進行編輯。圖2.12生產(chǎn)玩具銷售案例數(shù)學模型的公式編輯模型的“規(guī)劃求解參數(shù)”對話框如圖2.13所示。在“設置目標”文本框中選擇B13單元格，選中“最大值”按鈕，在“通過更改可變單元格”文本框中選擇B6:D8單元格區(qū)域。添加4個約束：

條件1：B9:D9=B10:D10

條件2：D6=0

條件3：D8>=1000

條件4：E6:E8<=F6:F8圖2.13生產(chǎn)玩具銷售案例“規(guī)劃求解參數(shù)”設置

各條件的含義如下：條件1：到貨總量=需求量，表示需求全部滿足；條件2：表示丙拒絕A玩具，所以A運到丙的玩具數(shù)量是0；條件3：表示丙百貨商店要求至少供應C玩具1000件條件4：供貨總量<=產(chǎn)量，表示產(chǎn)量有剩余；

最后求解結果見圖2.14。圖2.14生產(chǎn)玩具銷售案例求解結果案例分析2（化肥調撥問題）

設有三個化肥廠供應四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用的效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價表如表2.19所示。試求出總的運費最省的化肥調撥方案。表2.19單位運價：萬元/萬噸）

需求產(chǎn)地B1B2B3B4產(chǎn)量(萬噸)A11613221750A21413191560A3192023—50最低需求3070010

最高需求507030不限解:顯然這是一個產(chǎn)銷不平衡問題。總產(chǎn)量為160萬噸，按照題意分析最多運往B4地區(qū)60萬噸。所以設定B4地區(qū)的最高需求是60萬噸。用Excel求解時其電子表格模型見圖2.15。圖2.15解:顯然這是一個產(chǎn)銷不平衡問題?？偖a(chǎn)量為160萬噸，按照題意分析最多運往B4地區(qū)60萬噸。所以設定B4地區(qū)的最高需求是60萬噸。圖2.16所示對單元格進行公式編輯。圖2.16選中B16單元格，打開“規(guī)劃求解參數(shù)”對話框，在“設置目標”文本框中選擇B12單元格，選中“最小值”按鈕，在“通過更改可變單元格”文本框中選擇B6:E8單元格區(qū)域，如圖2.17所示。圖2.17添加4個約束：條件1：B10:E10<=B11:E11條件2：B10:E10>=B9:E9條件3：E8=0條件4：F6:F8=G6:G8圖2.18含義如下：條件1：實際收到<=最高需求；條件2：實際收到>=最低需求條件3：表示A3不能運送化肥到B4地區(qū)，所以該單元格運量是0；條件4：因為最高需求量總和大于產(chǎn)量，所以有實際運送=產(chǎn)量。

結果顯示B1、B2地區(qū)的最高需求得到滿足，B3地區(qū)的到貨量是0，B4地區(qū)的到貨量是40萬噸，均滿足了最低需求。案例分析3（生產(chǎn)安排問題）

某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表2.20所示。又如果生產(chǎn)出來的柴油機當季不交貨，每臺每季度需存儲費、維護費等共0.15萬元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護等）費用最小的決策。表2.20季

度生產(chǎn)能力(臺)單位成本(萬元)I2510.8II3511.1III3011.0IV1011.3人們常常盡可能把某些線性規(guī)劃問題化為運輸問題的數(shù)學模型。下面介紹如何把線性規(guī)劃問題轉化為運輸問題。解：4個季度作為4個產(chǎn)地，每季度的生產(chǎn)能力為對應的產(chǎn)量；4個季度作為4個銷地，按合同規(guī)定須于每個季度末分別提供同一規(guī)格的柴油機的數(shù)量作為對應的需求量。第i季度生產(chǎn)的用于第j季度交貨的每臺柴油機的實際成本cij應該是該季度單位成本加上儲存、維護等費用。得到一個運輸問題,數(shù)據(jù)見表2.21。表2.21產(chǎn)銷表與單位運價表

銷售生產(chǎn)I銷地II銷地III銷地IV銷地產(chǎn)量I產(chǎn)地10.810.9511.1011.2525II產(chǎn)地

11.1011.2511.4035II產(chǎn)地

11.0011.1530IV產(chǎn)地

11.3010銷量10152520

由于每個季度生產(chǎn)出來的柴油機不一定當季交貨，所以設xij

表示為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù)。根據(jù)合同要求，必須滿足：

x11=10

x12+x22=15

x13+x23+x33=25

x14+x24+x34+x44=20又每季度生產(chǎn)的用于當季和以后各季交貨的柴油機數(shù)不可能超過該季度的生產(chǎn)能力，故又有：

x11+x12+x13+x14

25x22+x23+x24

35x33+x34

30x44

10第i

季度生產(chǎn)的用于第j

季度交貨的每臺柴油機的實際成本cij

應該是該季度單位成本加上儲存、維護等費用。

cij

的具體數(shù)值見表2.22。

設用ai

表示該廠第i季度生產(chǎn)能力，bj表示第j季度的合同供應量，則問題可寫成：表2.22顯然這是一個產(chǎn)大于銷的運輸問題模型。用Excel求解時建立的規(guī)劃求解的電子模型如圖2.19。圖2.19單元格公式按照圖2.20進行編輯。圖2.20求解時添加的約束條件有：條件1：B8=0條件2：B9:C9=0條件3：B10:D10=0條件4：B11:E11=B12:E12條件5：F7:F10<=G7:G10

條件1表示產(chǎn)地II不能向銷地I供貨,條件2表示產(chǎn)地III不能向銷地I,銷地II供貨條件3表示產(chǎn)地V不能向銷地I,銷地II和銷地III供貨最后求解的結果如圖2.21所示。

結果顯示，第Ⅰ季度生產(chǎn)25臺，其中10臺當季交貨，10臺第Ⅱ季度交貨；第Ⅱ季度生產(chǎn)5臺用于第Ⅱ季度交貨；第Ⅲ季度生產(chǎn)30臺，其中25臺當季交貨，5臺用于第Ⅳ季度交貨；第Ⅳ季度生產(chǎn)10臺用于當季度交貨。按此方案安排生產(chǎn)，可使該廠總的生產(chǎn)(包括儲存費、維護費等)費用最省，即為773萬元。案例分析4（生產(chǎn)成本問題）某造船廠根據(jù)合同要求從當年起連續(xù)三年末各提供三條規(guī)格型號相同的大型客貨輪。已知該廠這三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪成本如表2.23所示。表2.23造船廠三年內(nèi)生產(chǎn)大型客貨輪的有關數(shù)據(jù)

已知加班生產(chǎn)時，每艘客貨輪成本比正常生產(chǎn)時高出70萬元。又知造出來的客貨輪如當年不交貨，每艘每積壓一年造成的積壓損失為40萬元。在簽訂合同時，該廠已儲存了兩艘客貨輪，而該廠希望在第三年末完成合同后還能儲存一艘備用。問該廠該如何安排每年客貨輪的生產(chǎn)量，使在滿足上述各項要求的情況下，總的生產(chǎn)費用加積壓損失為最少。解：這是一個生產(chǎn)與儲存問題，可以轉化為運輸問題來做。根據(jù)已知條件可以列出生產(chǎn)能力（正常生產(chǎn)能力和加班生產(chǎn)能力）和合同要求以及費用表2.24。表2.24費用表年度1至年度3，總的生產(chǎn)能力(包括上年年末儲存)為17艘，合同要求總量為10艘(包括第三年年末儲存)，為生產(chǎn)量大于銷售量。上年年末庫存2艘客貨輪，只考慮每艘積壓一年造成的積壓損失40萬元。當年生產(chǎn)當年交貨，則只計算生產(chǎn)成本；如果當年生產(chǎn)出來的客貨輪當年不交貨，則將生產(chǎn)成本以及每艘每積壓一年40萬元所造成的積壓損失一起計算。4.對于第三年年末的留出庫存考慮生產(chǎn)成本以及每年的積壓損失。

生產(chǎn)分成正常生產(chǎn)和加班生產(chǎn)。運用Excel求解時建立的電子表格模型如圖2.22所示。圖2.22單元格公式見圖2.23。圖2.23求解時添加的約束有：

條件1：B14:B17=0條件2：C16:C17=0條件3：B18:E18=B20:E20條件4：F11:F17<=H11:H17最后結果見圖2.24。下面討論運輸問題中的轉運問題。所謂的轉運問題是運輸問題的一個擴充，即在原來運輸問題中的產(chǎn)地與銷地之間再增加中轉點。在運輸問題中只允許物品從產(chǎn)地運往銷地，而在轉運問題中還允許把物品從一個產(chǎn)地運往另一個產(chǎn)地(中轉點或銷地)，允許把物品從一個中轉點運往另一個中轉點(產(chǎn)地或銷地)，也允許把物品從一個銷地運往另一個中轉點或產(chǎn)地。每個產(chǎn)地的生產(chǎn)量都有限制，而每個銷地的需求量也都有一個限制，在任意兩點間單位物品運價已知的情況下，如何使總的運輸費最小圖2.24案例分析5（物質調運問題）宏達電子儀器公司，其生產(chǎn)線分別在大連、廣州，大連分廠每月生產(chǎn)400臺某種儀器，廣州分廠每月生產(chǎn)600臺某種儀器。在任意分廠的生產(chǎn)線生產(chǎn)的產(chǎn)品可能被運往公司設在長沙或天津的地區(qū)倉庫中的任意一個。從這些倉庫，公司向南京、西安、濟南和上海的零售商發(fā)貨。這些城市間的每臺儀器的運費我們標在兩個城市間上的弧上，單位為萬元；工廠和零售商的供給與需求在圖的左側和右側標明如圖2.25所示。問應該如何調運儀器，使總的運費最低？圖2.25宏達電子儀器公司轉運網(wǎng)絡圖解：該轉運問題可以轉化為兩個運輸問題。可做如下處理：(1)由于問題中的所有產(chǎn)地、中轉點都可以看成產(chǎn)地，而中轉點與銷地都可以看成銷地，因此整個問題可以看成是一個由四個產(chǎn)地和六個銷地組成的運輸問題；(2)對于擴大的運輸問題建立運價表，表中的不可能運輸方案的運價用M代替；(3)所有中轉點的生產(chǎn)量等于銷售量，即流入量等于流出量。由于運費最小時不可能出現(xiàn)物資來回倒運的現(xiàn)象，因此每個中轉點的運量不會超過1000臺，所以可以規(guī)定中轉點的生產(chǎn)量和銷售量均為1000臺，這樣就可以得到擴大的產(chǎn)銷平衡運輸問題及其運價表，如表2.25所示。表2.25

長沙/萬元天津/萬元南京/萬元西安/萬元濟南/萬元上海/萬元生產(chǎn)量/臺廣州23MMMM600大連31MMMM400長沙0M26361000天津M044651000銷售量/臺10001000200150350300

運用Excel求解：建立的電子表格模型見圖2.26，在模型中運價是M處均用10000替換（這個值要遠遠大于其它的單位運價，當求運費最小時，此處運量就是0）。這樣，求解時約束條件如同例2.5只有2個，即供貨總量=產(chǎn)量；到貨總量=需求量。圖2.26單元格公式見圖2.27。圖2.27最后結果如圖2.28。圖2.28如圖2.28所示最優(yōu)運輸方案為從廣州運往長沙550臺，從長沙再運往南京200臺、濟南350臺；從廣州運往天津50臺、從大連運往天津400臺，從天津再運往西安150臺；直接從天津運往上海300臺。總運費為5200萬元。如果公司認為從大連到上海的距離較近，可以直接從大連分廠向上海供貨，且每臺運費為5萬元，如圖2.29所示，這時的運輸問題及其運價表，如表2.26所示當采用excel求解時只需將電子模型（圖2.26）的單元格G4的值改為5，參照上一問的步驟，最后求解結果見圖2.30。圖2.29宏達電子儀器公司轉運網(wǎng)絡圖圖2.30這時的最優(yōu)運輸方案為從廣州運往長沙550臺，從長沙再運往南京200臺、濟南350臺；從廣州運往天津50臺、從大連運往天津100臺，從天津再運往西安150臺；直接從大連運往上海300臺?？傔\費為4900萬元。如果公司認為從大連到上海的距離較近，可以直接從大連分廠向上海供貨，每臺運費為4萬元，也可以從濟南向上海供貨，每臺運費為1萬元，如圖2.31所示。這時要把問題中的產(chǎn)地、銷地、中轉點都看成產(chǎn)地，中轉點與銷地看成銷地，因此整個問題可以看成是一個由五個產(chǎn)地和六個銷地組成的運輸問題圖2.31宏達電子儀器公司轉運網(wǎng)絡圖

這時的運輸問題及其運價表，如表2.27所示。此時濟南作為產(chǎn)地承擔了中轉的作用，最多運出1000，所以規(guī)定產(chǎn)量是1000；而濟南作為銷地需求是1000+350=1350。此時excel求解建立的電子模型和求解結果見圖2.32。表2.27

這時的最優(yōu)運輸方案為：從廣州運往長沙600臺，從長沙再運往南京200臺、濟南400臺，從濟南運50臺到上海；從大連運往天津150臺，運往上海250臺，再從天津運往西安150臺?？傔\費為4850萬元。圖2.32案例分析6（蔬菜供應問題）某市是一個人口不到15萬人的小城市，根據(jù)該市的蔬菜種植情況，分別在A、B和C設立三個收購點，再由收購點分別送到全市的8個菜市場。按照往年情況，A、B、C三個收購點每天的收購量分別是200、170和160（單位：kg）,各菜市場每天的需求量及發(fā)生供應短缺時帶來的損失見表2.28。各收購點至各菜市場的距離見表2.29。各收購點至各菜市場的單位運價為1元/100kg.100m。表2.28表2.29各收購點至菜場的距離為該市設計一個從各收購點至菜市場的定點供應方案，使總費用(包括蔬菜運費、缺貨損失)最小。若規(guī)定各菜市場短缺量一律不超過需求量的20%，重新設計定點供應方案。為滿足城市居民的蔬菜供應，該市規(guī)劃增加蔬菜的種植面積，試問增產(chǎn)的蔬菜每天應分別向A、B、C三個收購點各供應多少最為經(jīng)濟合理。解：（1）三個收購點每天總收購量為200+170+160=530，而菜市場每天總需求量為75+60+80+70+100+55+90+80=610，這是一個“銷大于產(chǎn)”的運輸問題①設假設xij

表示從收購點i（i=A,B,C）向菜市場j(j=1,2,…,8)調運的蔬菜量（單位：100kg）,yj表示菜場j(j=1,2,…,8)的供應短缺量