運(yùn)籌學(xué)（第2版）課件 第二章 運(yùn)輸問題

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

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

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

發(fā)展簡史

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

表示從Ai到Bj

的運(yùn)量,Z表示的運(yùn)輸費(fèi)用，從而得到其數(shù)學(xué)模型:

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

可見運(yùn)輸問題是一種線性規(guī)劃問題。對于一般情況，假設(shè)有m個生產(chǎn)地點(diǎn)，可以供應(yīng)某種物資(以后稱為產(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運(yùn)輸單位物資的運(yùn)價為cij，這些數(shù)據(jù)可匯總于如表2.2。如果運(yùn)輸問題的總產(chǎn)量等于其總銷量，即則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題；反之，稱為產(chǎn)銷不平衡運(yùn)輸問題。下面建立在產(chǎn)銷平衡情況下的運(yùn)輸問題的數(shù)學(xué)模型。假設(shè)xij表示從Ai到Bj的運(yùn)量,則所求的數(shù)學(xué)模型為:下面建立在產(chǎn)銷不平衡情況下的運(yùn)輸問題的數(shù)學(xué)模型。當(dāng)產(chǎn)大于銷時，即時，運(yùn)輸問題的數(shù)學(xué)模型可以寫成：當(dāng)銷大于產(chǎn)時即時，運(yùn)輸問題的數(shù)學(xué)模型可以寫成：2.2運(yùn)輸問題的基本可行解

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

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

對應(yīng)的列交叉處的元素構(gòu)成m+n-1階方陣D，D的行列式。

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

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

銷地產(chǎn)地B1B2B3B4A1x11x12

A2x21

x24A3

x32

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

表2.4

表2.5定理2.1

m+n-1個變量

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

該定理給出了運(yùn)輸問題基的一個重要特征，這個結(jié)論是非常重要的，因?yàn)槔盟梢耘袛鄊+n-1個變量是否構(gòu)成基變量，它比直接判斷這些變量所對應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡單和直觀。

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

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

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

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

437A23

1

4A3

6

39銷量3656

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

其余。

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

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

437A23

1

4A3

6

39銷量3656

表2.7

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

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

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

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

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

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

的列差額最大。B2

列中最小元素為4（即A3

行），可確定A3

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

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

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

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

527A23

14A3

6

39銷量3656

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

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

（1）閉回路法

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

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

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

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

34（－1）

37A213（－1）

21（＋1）

4A3

6

39銷量3656

可見這一調(diào)整方案使運(yùn)費(fèi)增加了：(+1)

3+(-1)

3+(+1)

2+(-1)

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

回

路檢驗(yàn)數(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這時檢驗(yàn)數(shù)還存在負(fù)數(shù)，因?yàn)?A2,B4)空格的檢驗(yàn)數(shù)為–1，這說明表2.7給出的調(diào)運(yùn)方案還不是最優(yōu)解，還需要進(jìn)一步改進(jìn)，改進(jìn)方法見本節(jié)后面的基可行解的改進(jìn)方法。（2）位勢法

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

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

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

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

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

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

來說，它所對應(yīng)的檢驗(yàn)數(shù)為：

ij=cij–(ui+vj

)(2.2)

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

仍以例2.3所給出的初始基可行解表2.7為例：第一步：在對應(yīng)表2.7的數(shù)字格處填入單位運(yùn)價如表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)

基變量指標(biāo)集

，相繼確定ui、vj

。由表3—15可見，當(dāng)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)

非基變量指標(biāo)集，計(jì)算所有的空格檢驗(yàn)數(shù)。如：

11

=c11–(u1+v1

)=3–(0+2)=1

12

=c12–(u1+v2

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

2.3.3基可行解改進(jìn)的方法——閉回路調(diào)整法

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

為換入變量）。以x24為出發(fā)點(diǎn)，作一閉回路為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

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

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

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

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

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

527A23

14A3

6

39銷量3656

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

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

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

條件1：C11:F11=C12:F12

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

若例2.1中A2產(chǎn)量增加到6,該運(yùn)輸問題如何用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。因?yàn)槭钱a(chǎn)量大于銷量，條件1：實(shí)際到貨總量=需求量，表示需求全部滿足；條件2：實(shí)際供貨總量<=產(chǎn)量，表示產(chǎn)量有剩余。最后求解的結(jié)果如圖2.8所示。圖2.8生產(chǎn)量大于銷售量的求解結(jié)果（2）當(dāng)產(chǎn)量小于銷量例2.7

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

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

甲乙丙可供應(yīng)量A54—1000B16892000C1210112000表2.18三種新型玩具有關(guān)數(shù)據(jù)解：由于總供應(yīng)量為1000+2000+2000=5000,總需求量（預(yù)期銷售量）為1500+1500+1500=4500，總供應(yīng)大于總需求，因此是產(chǎn)大于銷的運(yùn)輸問題。用Excel求解時其電子表格模型見圖2.11。圖2.11生產(chǎn)玩具銷售案例數(shù)學(xué)模型單元格公式參照圖2.12進(jìn)行編輯。圖2.12生產(chǎn)玩具銷售案例數(shù)學(xué)模型的公式編輯模型的“規(guī)劃求解參數(shù)”對話框如圖2.13所示。在“設(shè)置目標(biāo)”文本框中選擇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ù)”設(shè)置

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

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

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

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

最高需求507030不限解:顯然這是一個產(chǎn)銷不平衡問題?？偖a(chǎn)量為160萬噸，按照題意分析最多運(yùn)往B4地區(qū)60萬噸。所以設(shè)定B4地區(qū)的最高需求是60萬噸。用Excel求解時其電子表格模型見圖2.15。圖2.15解:顯然這是一個產(chǎn)銷不平衡問題?？偖a(chǎn)量為160萬噸，按照題意分析最多運(yùn)往B4地區(qū)60萬噸。所以設(shè)定B4地區(qū)的最高需求是60萬噸。圖2.16所示對單元格進(jìn)行公式編輯。圖2.16選中B16單元格，打開“規(guī)劃求解參數(shù)”對話框，在“設(shè)置目標(biāo)”文本框中選擇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：實(shí)際收到<=最高需求；條件2：實(shí)際收到>=最低需求條件3：表示A3不能運(yùn)送化肥到B4地區(qū)，所以該單元格運(yùn)量是0；條件4：因?yàn)樽罡咝枨罅靠偤痛笥诋a(chǎn)量，所以有實(shí)際運(yùn)送=產(chǎn)量。

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

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

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

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

x11=10

x12+x22=15

x13+x23+x33=25

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

x11+x12+x13+x14

25x22+x23+x24

35x33+x34

30x44

10第i

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

季度交貨的每臺柴油機(jī)的實(shí)際成本cij

應(yīng)該是該季度單位成本加上儲存、維護(hù)等費(fèi)用。

cij

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

設(shè)用ai

表示該廠第i季度生產(chǎn)能力，bj表示第j季度的合同供應(yīng)量，則問題可寫成：表2.22顯然這是一個產(chǎn)大于銷的運(yùn)輸問題模型。用Excel求解時建立的規(guī)劃求解的電子模型如圖2.19。圖2.19單元格公式按照圖2.20進(jìn)行編輯。圖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供貨最后求解的結(jié)果如圖2.21所示。

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

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

生產(chǎn)分成正常生產(chǎn)和加班生產(chǎn)。運(yù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最后結(jié)果見圖2.24。下面討論運(yùn)輸問題中的轉(zhuǎn)運(yùn)問題。所謂的轉(zhuǎn)運(yùn)問題是運(yùn)輸問題的一個擴(kuò)充，即在原來運(yùn)輸問題中的產(chǎn)地與銷地之間再增加中轉(zhuǎn)點(diǎn)。在運(yùn)輸問題中只允許物品從產(chǎn)地運(yùn)往銷地，而在轉(zhuǎn)運(yùn)問題中還允許把物品從一個產(chǎn)地運(yùn)往另一個產(chǎn)地(中轉(zhuǎn)點(diǎn)或銷地)，允許把物品從一個中轉(zhuǎn)點(diǎn)運(yùn)往另一個中轉(zhuǎn)點(diǎn)(產(chǎn)地或銷地)，也允許把物品從一個銷地運(yùn)往另一個中轉(zhuǎn)點(diǎn)或產(chǎn)地。每個產(chǎn)地的生產(chǎn)量都有限制，而每個銷地的需求量也都有一個限制，在任意兩點(diǎn)間單位物品運(yùn)價已知的情況下，如何使總的運(yùn)輸費(fèi)最小圖2.24案例分析5（物質(zhì)調(diào)運(yùn)問題）宏達(dá)電子儀器公司，其生產(chǎn)線分別在大連、廣州，大連分廠每月生產(chǎn)400臺某種儀器，廣州分廠每月生產(chǎn)600臺某種儀器。在任意分廠的生產(chǎn)線生產(chǎn)的產(chǎn)品可能被運(yùn)往公司設(shè)在長沙或天津的地區(qū)倉庫中的任意一個。從這些倉庫，公司向南京、西安、濟(jì)南和上海的零售商發(fā)貨。這些城市間的每臺儀器的運(yùn)費(fèi)我們標(biāo)在兩個城市間上的弧上，單位為萬元；工廠和零售商的供給與需求在圖的左側(cè)和右側(cè)標(biāo)明如圖2.25所示。問應(yīng)該如何調(diào)運(yùn)儀器，使總的運(yùn)費(fèi)最低？圖2.25宏達(dá)電子儀器公司轉(zhuǎn)運(yùn)網(wǎng)絡(luò)圖解：該轉(zhuǎn)運(yùn)問題可以轉(zhuǎn)化為兩個運(yùn)輸問題?？勺鋈缦绿幚恚?1)由于問題中的所有產(chǎn)地、中轉(zhuǎn)點(diǎn)都可以看成產(chǎn)地，而中轉(zhuǎn)點(diǎn)與銷地都可以看成銷地，因此整個問題可以看成是一個由四個產(chǎn)地和六個銷地組成的運(yùn)輸問題；(2)對于擴(kuò)大的運(yùn)輸問題建立運(yùn)價表，表中的不可能運(yùn)輸方案的運(yùn)價用M代替；(3)所有中轉(zhuǎn)點(diǎn)的生產(chǎn)量等于銷售量，即流入量等于流出量。由于運(yùn)費(fèi)最小時不可能出現(xiàn)物資來回倒運(yùn)的現(xiàn)象，因此每個中轉(zhuǎn)點(diǎn)的運(yùn)量不會超過1000臺，所以可以規(guī)定中轉(zhuǎn)點(diǎn)的生產(chǎn)量和銷售量均為1000臺，這樣就可以得到擴(kuò)大的產(chǎn)銷平衡運(yùn)輸問題及其運(yùn)價表，如表2.25所示。表2.25

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

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

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

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

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