管理運(yùn)籌學(xué)講義第3章運(yùn)輸問(wèn)題

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

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

例3.1

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

問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小?4石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院解：這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題，設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量（i=1，2，3；j=1，2，3，4）該運(yùn)輸問(wèn)題的線性規(guī)劃模型如下：Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x345石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院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)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院其系數(shù)矩陣為：共有m+n行，分別表示產(chǎn)地和銷地；有mn列分別表示各變量；每列只有兩個(gè)1，其余為0。7石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院

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

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

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1x11x12…x1na1A2x21x22…x2na2Amxm1xm2…xmnam銷量b1b2…bn

表3-3運(yùn)輸表12石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院下面分兩種情況來(lái)討論：

（1）。即運(yùn)輸問(wèn)題的總產(chǎn)量等于其總銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷平衡的運(yùn)輸問(wèn)題。（2）。即運(yùn)輸問(wèn)題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷不平衡的運(yùn)輸問(wèn)題。

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

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

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

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

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

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

≥

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

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

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

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

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

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

例3.2

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

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

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

33石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求365620產(chǎn)銷平衡表運(yùn)價(jià)表2513

01160123212

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

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

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

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

定義3.1

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

①閉回路均為一封閉折線，它的每一條邊，或?yàn)樗降?，或?yàn)榇怪钡模虎陂]回路的每一條邊（水平的或垂直的）均有且僅有兩個(gè)頂點(diǎn)（基變量格）。

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

其檢驗(yàn)數(shù)為

ij=(閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)-(閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1437311310A23141928A363974105需求365620所以22=9-2+3–10+5–4=140石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院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閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算都會(huì)產(chǎn)生困難。

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

對(duì)于一個(gè)調(diào)運(yùn)方案的每列賦予一個(gè)值，稱為列位勢(shì)。記為：，對(duì)于每行賦予一個(gè)值，稱為行位勢(shì)，記為。它們的值由下列方程組決定：

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

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

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

1

2430A23

11

-1-1A3

106

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

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

如果某一個(gè)調(diào)運(yùn)方案的所有空格的檢驗(yàn)數(shù)都大于或等于零，則該調(diào)運(yùn)方案是最優(yōu)方案。因?yàn)樵谶@種情況下，方案的任何變動(dòng)都不會(huì)使總的運(yùn)費(fèi)減少。當(dāng)檢驗(yàn)數(shù)表中有負(fù)的檢驗(yàn)數(shù)時(shí)，說(shuō)明該調(diào)運(yùn)方案不是最優(yōu)方案，進(jìn)一步調(diào)整，還可以使總的運(yùn)費(fèi)減少。

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

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

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

1

2430A23

11

-1-1A3

106

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

x13=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。

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

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

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

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

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

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

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

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

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

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

例3-4某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。夸N產(chǎn)B1B2B3產(chǎn)量B1B2B3A178131512A245112922需求533665

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

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

例3-6某研究院有B1、B2、B3三個(gè)區(qū)。每年取暖分別需要用煤3500噸、1100噸、2400噸，這些煤都要由A1、A2兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量均相同。A1、A2煤礦的供應(yīng)能力分別為1500噸、4000噸，運(yùn)價(jià)（元/噸）如下表。由于需求大于供給，經(jīng)院研究決定B1區(qū)供應(yīng)量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應(yīng)量不少于1600噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。68石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院銷地產(chǎn)地B1B2B3產(chǎn)量A11751952081500A21601822154000需求量350011002400解：這是需求量大于生產(chǎn)量的運(yùn)輸問(wèn)題，由于B1區(qū)供應(yīng)量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應(yīng)量不少于16005500700069石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院噸，可以把B1區(qū)和B3區(qū)分別設(shè)為兩個(gè)區(qū)：一個(gè)為必須滿足需求量的區(qū)域，另一個(gè)為可以調(diào)整供應(yīng)量的區(qū)域。這樣，原問(wèn)題化為五個(gè)需求區(qū)域B1、B1’、B2、B3、B3’的問(wèn)題，同時(shí)增加一個(gè)虛設(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)價(jià)表。70石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院銷地產(chǎn)地B1B1*B2B3B3*產(chǎn)量A11751751952082081500A21601601822152154000A3M0MM01500需求量260090011001600800計(jì)算過(guò)程從略71石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院§3.4應(yīng)用舉例

在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單。解決實(shí)際問(wèn)題時(shí)，人們常常盡可能把某些線性規(guī)劃的問(wèn)題化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型。下面為幾個(gè)典型的例子?；乇菊履夸?2石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院

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

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

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

cij=第i季度每臺(tái)的生產(chǎn)成本+0.15(j-i)（儲(chǔ)存、維護(hù)等費(fèi)用）。計(jì)算可得：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)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院于是得到目標(biāo)函數(shù)：

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

各季節(jié)的生產(chǎn)、交貨費(fèi)用表

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

例3-8

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

解

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

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

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

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

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

84石家莊經(jīng)濟(jì)學(xué)院管理科學(xué)與工程學(xué)院?jiǎn)挝贿\(yùn)價(jià)表應(yīng)為相應(yīng)各港口之間的船只航程天數(shù)如表3-13所示。

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

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

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