運(yùn)籌學(xué)運(yùn)輸問(wèn)題（課堂PPT）

1、第六章 運(yùn)輸問(wèn)題 前面幾章中，我們討論了線(xiàn)性規(guī)劃的一般形式及求解方法，對(duì)偶線(xiàn)性規(guī)劃問(wèn)題與靈敏度分析等問(wèn)題。但在實(shí)際工作中，常常遇到很多線(xiàn)性規(guī)劃問(wèn)題，由于它們約束條件變量的系數(shù)矩陣具有特殊的結(jié)構(gòu)，有可能找到比單純形法更為簡(jiǎn)便的方法求解，從而可以大量節(jié)約計(jì)算的時(shí)間和費(fèi)用。本章討論的運(yùn)輸問(wèn)題就是這一類(lèi)特殊的線(xiàn)性規(guī)劃問(wèn)題。1結(jié)構(gòu)安排2第一節(jié) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 在社會(huì)經(jīng)濟(jì)生活中，經(jīng)常會(huì)碰到大宗物資的調(diào)運(yùn)問(wèn)題。如煤、鋼鐵、木材、糧食等物資，在全國(guó)有若干生產(chǎn)基地，根據(jù)已有的交通網(wǎng)絡(luò)，制定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，這樣調(diào)運(yùn)的目的，不僅是要把這些物資供給各地消費(fèi)，而且我們也希望調(diào)運(yùn)的費(fèi)用最省，這類(lèi)問(wèn)

2、題就是所謂的運(yùn)輸問(wèn)題。3一、運(yùn)輸問(wèn)題案例一、運(yùn)輸問(wèn)題案例 例例 ：某公司從兩個(gè)產(chǎn)地A1，A2將物品運(yùn)往三個(gè)銷(xiāo)地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地的每件物品的運(yùn)費(fèi)如表所示，問(wèn)應(yīng)如何調(diào)運(yùn)，使得總運(yùn)輸費(fèi)最小？銷(xiāo)地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3產(chǎn)量（件）A1646200A2655300銷(xiāo) 量1501502004 解：因?yàn)榇藛?wèn)題中產(chǎn)量和銷(xiāo)量都是500，所以這是一個(gè)產(chǎn)銷(xiāo)平衡問(wèn)題。 設(shè)xij表示從產(chǎn)地Ai調(diào)運(yùn)到銷(xiāo)地Bj的運(yùn)輸量 （i=1，2；j=1，2，3），例如，x12表示由A1調(diào)運(yùn)到B2的物品數(shù)量，現(xiàn)將安排的運(yùn)輸量列表如下：銷(xiāo)地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3產(chǎn)量（件）A1x11x12x1

3、3200A2x21x22x23300銷(xiāo) 量1501502005005此運(yùn)輸問(wèn)題的線(xiàn)性規(guī)劃模型如下：)3 , 2 , 1; 2 , 1(0,200,150,150,300,200.556646min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxfij6二、運(yùn)輸問(wèn)題的一般情形二、運(yùn)輸問(wèn)題的一般情形 假設(shè)某物資有m個(gè)產(chǎn)地 A1，A2，.，Am ， n個(gè)銷(xiāo)地 B1，B2，.，Bn，已知這m個(gè)產(chǎn)地的產(chǎn)量為 a1，a2，.，am；n個(gè)銷(xiāo)地的銷(xiāo)量分別為 b1，b2，.，bn，從第i個(gè)產(chǎn)地到第j個(gè)銷(xiāo)地的單位物資運(yùn)價(jià)為cij,這些數(shù)據(jù)可用產(chǎn)

4、銷(xiāo)平衡表和單位運(yùn)價(jià)表表示如下。7產(chǎn)銷(xiāo)平衡表銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地B1B2.Bn 產(chǎn)量產(chǎn)量A1A2.Ama1a2.am銷(xiāo)銷(xiāo) 量量b1b2.bn8單位運(yùn)價(jià)表銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地B1B2.BnA1A2.Amc11c21.cm1c12c22.cm2.c1nc2n.cmn9v 若總產(chǎn)量等于總銷(xiāo)量（產(chǎn)銷(xiāo)平衡），試確定總運(yùn)費(fèi)最省若總產(chǎn)量等于總銷(xiāo)量（產(chǎn)銷(xiāo)平衡），試確定總運(yùn)費(fèi)最省的調(diào)運(yùn)方案。的調(diào)運(yùn)方案。v建 模 ： 設(shè)建 模 ： 設(shè) xi j為 從 產(chǎn) 地為 從 產(chǎn) 地 Ai運(yùn) 往 銷(xiāo) 地運(yùn) 往 銷(xiāo) 地 Bj的 物 資 數(shù) 量的 物 資 數(shù) 量（i=1，m；j=1，n。銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地B1B2.Bn 產(chǎn)量產(chǎn)量A1A2.A

5、mX11X21.Xm1X12X22 .Xm2.X1nX2n.Xmna1a2.am銷(xiāo)銷(xiāo) 量量b1b2.bn10則運(yùn)輸問(wèn)題的數(shù)學(xué)模型如下：mmnmmnnaxxxaxxxaxxx21222221111211), 2 , 1;, 2 , 1( 021222212112111njmixbxxxbxxxbxxxijnmnnnmmijminjijxcZ11min11), 2 , 1;, 2 , 1(02122221211211121222221111211njmixbxxxbxxxbxxxaxxxaxxxaxxxijnmnnnmmmmnmmnnijminjijxcZ11min顯然，模型是具有mn個(gè)變量， m

6、+n個(gè)約束的線(xiàn)性規(guī)劃，可以用一般的單純形法求解，但是當(dāng)m與n較大時(shí)，模型的規(guī)模比較大，計(jì)算比較困難。為了進(jìn)一步研究針對(duì)運(yùn)輸問(wèn)題的特殊解法，下面考察它的約束系數(shù)矩陣。12mnmmnnxxxxxxxxx,;,;,;,212222111211111111111111111111m行行n行行1314 容易證明，秩A=m+n-1。事實(shí)上，由于A的前m行之和等于后n行之和，因此，秩Am+n-1;又，取A的前m+n-1行，變量 對(duì)應(yīng)的列所構(gòu)成的A的子式為 由此易知，這個(gè)m+n-1階子式的值為1或-1，所以，A的秩恰為m+n-1?？梢?jiàn)運(yùn)輸問(wèn)題的基可行解中，基變量的個(gè)數(shù)應(yīng)為m+n-1個(gè)。 mnnnnxxxxx,

7、3211115 根據(jù)運(yùn)輸問(wèn)題數(shù)學(xué)模型結(jié)構(gòu)上具有的上述特征，在前面所講的單純形方法的基礎(chǔ)上，逐漸創(chuàng)造出一種專(zhuān)門(mén)用來(lái)求解運(yùn)輸問(wèn)題線(xiàn)性規(guī)劃模型的運(yùn)輸單純形方法，一般稱(chēng)其為表上作業(yè)法。16第二節(jié) 表上作業(yè)法 表上作業(yè)法是一類(lèi)比較特殊的單純形法。它必須首先確定一個(gè)初始方案，也就是找出一個(gè)基可行解，然后根據(jù)判別準(zhǔn)則來(lái)檢查這個(gè)初始方案是不是最優(yōu)的，如果不是最優(yōu)的，那么對(duì)初始方案加以改進(jìn)，直到找出最優(yōu)方案。17 確定初始確定初始方案方案( ( 初初 始始 基本可行解基本可行解) ) 改進(jìn)調(diào)整改進(jìn)調(diào)整（換基迭代）（換基迭代）否否 判定是否判定是否 最最 優(yōu)？?jī)?yōu)？是是結(jié)結(jié) 束束最優(yōu)方案最優(yōu)方案v下面通過(guò)例子介紹它

8、的計(jì)算步驟。運(yùn)輸問(wèn)題求解思路圖運(yùn)輸問(wèn)題求解思路圖18一、初始方案的給定1、最小元素法2、Vogel法191、最小元素法 基本思路是：就近供應(yīng)，即從運(yùn)價(jià)表中最小運(yùn)價(jià)開(kāi)始確定調(diào)運(yùn)量，然后次小，一直到給出初始調(diào)運(yùn)方案為止。20 （1）找出運(yùn)價(jià)表中最小元素 ，確定 ，若 ，則令 ，劃掉運(yùn)價(jià)表的第L行；反之，若 ，則令 ，劃掉運(yùn)價(jià)表的第k列。 （2）在運(yùn)價(jià)表剩余元素中重復(fù)（1），直至運(yùn)價(jià)表元素全部被劃掉。LKCKLLKbax,minLLKaxLKKabbKLKbxKLLbaa21 例：某糖果公司下設(shè)三個(gè)工廠，每日產(chǎn)量分別為：A1 7噸、A2 4噸、A3 9噸。該公司將這些產(chǎn)品運(yùn)往四個(gè)門(mén)市部，各門(mén)市部每日

9、銷(xiāo)量為：B1 3噸、B2 6噸、B3 5噸、B4 6噸。各工廠到各門(mén)市部的單位運(yùn)價(jià)如下表，試確定最優(yōu)的運(yùn)輸方案。返回中間轉(zhuǎn)運(yùn)問(wèn)題22產(chǎn)銷(xiāo)平衡表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3 749銷(xiāo)銷(xiāo) 量量 3 6 5 6銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5單位運(yùn)價(jià)表 31463323注意： 有時(shí)選定最小元素后，發(fā)現(xiàn)該行的產(chǎn)地剩余產(chǎn)量恰好等于銷(xiāo)地剩余銷(xiāo)量。此時(shí)在產(chǎn)銷(xiāo)平衡表上就必須劃去一行和一列。此時(shí)為了保持?jǐn)?shù)字個(gè)數(shù)仍然為m+n-1個(gè)。則必須在產(chǎn)銷(xiāo)平衡表上劃去的該行和該列的任意空格處填上數(shù)字“0”，如下表所示

10、：24Table1 產(chǎn)銷(xiāo)平衡表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3749銷(xiāo)銷(xiāo) 量量 3 6 5 6銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 3 11 4 5 7 7 3 8 1 2 10 6Table2 單位運(yùn)價(jià)表 36252、Vogel法v基本思路是：從全局考慮。其方法是從運(yùn)價(jià)表上分別找出每行與每列最小的兩個(gè)元素之差，再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。 當(dāng)產(chǎn)地或銷(xiāo)地中有一方數(shù)量上供應(yīng)完畢或得到滿(mǎn)足時(shí)，劃去運(yùn)價(jià)表中的行或列，再重復(fù)上述步驟。直到找出最佳調(diào)運(yùn)方案。26Table3 產(chǎn)銷(xiāo)平衡表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4

11、產(chǎn)產(chǎn) 量量A1A2A3749銷(xiāo)銷(xiāo) 量量 3 6 5 6Table4 單位運(yùn)價(jià)表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地B1 B2 B3 B4 兩最小元素之差兩最小元素之差 A1A2A33 11 3 101 9 2 87 4 10 50 0 0 7 01 1 1 6 0 1 2兩最小兩最小元素元素之差之差2 5 1 32 1 32 1 2 1 2 236521327二、最優(yōu)性檢驗(yàn)與方案的調(diào)整v最小元素法和Vogel法給出的是一個(gè)基可行解，要確定該基可行解是否是最優(yōu)解，還必須進(jìn)行最優(yōu)性檢驗(yàn)。并進(jìn)一步對(duì)方案進(jìn)行調(diào)整。v進(jìn)行最優(yōu)性檢驗(yàn)的方法主要有閉回路法和位勢(shì)法。281、閉回路法v閉回路是指調(diào)運(yùn)方案中由一個(gè)空格和若干個(gè)數(shù)字

12、格的水平或垂直連線(xiàn)包圍成的封閉回路。v所謂的閉回路，就是從一個(gè)空格出發(fā)，沿水平方向或垂直方向前進(jìn)，遇到合適的數(shù)字格后轉(zhuǎn)90度，繼續(xù)前進(jìn)，如果能夠回到出發(fā)點(diǎn)，則稱(chēng)這個(gè)封閉折線(xiàn)為閉回路。29Table5 產(chǎn)銷(xiāo)平衡表 3 6 5 6銷(xiāo)銷(xiāo) 量量749A1A2A3產(chǎn)產(chǎn) 量量 B1 B2 B3 B4銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地36521330（a） （b） （c） （d） （e）表中的折線(xiàn)構(gòu)成一條封閉曲線(xiàn)，且所有的表中的折線(xiàn)構(gòu)成一條封閉曲線(xiàn)，且所有的邊都是邊都是或或的；的； 表中的表中的和和；31ij32Table6 運(yùn)輸方案閉回路表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3 4 3 3 1 6

13、 3749銷(xiāo)銷(xiāo) 量量 3 6 5 6 -1 +1 -1 +1 3 11 3 10 1 9 2 8 7 4 10 5A1A2A3 B1 B2 B3 B4銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地Table2 單位運(yùn)價(jià)表 33 1 2 1 -1 10 12A1A2A3 B1 B2 B3 B4銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地Table7 檢驗(yàn)數(shù)表 34方案的調(diào)整 若最優(yōu)性檢驗(yàn)時(shí)某非基（空格Ai，Bj）xij的檢驗(yàn)數(shù)為負(fù)，說(shuō)明這個(gè)非基變量變?yōu)榛兞繒r(shí)運(yùn)費(fèi)會(huì)更小，因而這個(gè)解不是最優(yōu)解，還可以進(jìn)一步調(diào)整改進(jìn)。改進(jìn)的具體步驟：（1）以xij為換入變量，找出它在運(yùn)輸表中的閉回路。（2）以空格（ Ai，Bj ）為第一個(gè)奇數(shù)，沿閉回路的順（或逆）時(shí)針?lè)较?/p>

14、前進(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)。（3）在閉回路上的所有偶數(shù)頂點(diǎn)中，找出運(yùn)輸量最小的頂點(diǎn)，以該變量為換出變量。（4）以該變量為調(diào)整量，將該閉回路上所有奇數(shù)頂點(diǎn)處的運(yùn)輸量都增加這一數(shù)值，所有偶數(shù)頂點(diǎn)處的運(yùn)輸量都減去這一數(shù)值，從而得出以新的運(yùn)輸方案。 然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，如不是最優(yōu)解，就重復(fù)以上的步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。35Table8 運(yùn)輸方案調(diào)整表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3 4 3 3 1 6 3749銷(xiāo)銷(xiāo) 量量 3 6 5 6 -1 +1 -1 +1Table9 運(yùn)輸方案調(diào)整表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn)

15、量量A1A2A3 5 2 3 1 6 3749銷(xiāo)銷(xiāo) 量量 3 6 5 636Table10 新檢驗(yàn)數(shù)表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 0 2 2 1 9 12 注意:有時(shí)在閉回路調(diào)整中，在需要減少運(yùn)量的地方有兩個(gè)以上相等的最小數(shù)。這樣調(diào)整時(shí)在原先空格處填上這個(gè)最小數(shù)，而有兩個(gè)最小數(shù)的地方成了空格。此時(shí)只需把其中之一變?yōu)榭崭?，其余均補(bǔ)添“0”，使方案中由數(shù)字格仍為m+n-1。（將為“0”的格當(dāng)數(shù)字格看待）372、位勢(shì)法v閉回路法需要求每一個(gè)空格的檢驗(yàn)數(shù)，這對(duì)于大型的運(yùn)輸問(wèn)題來(lái)說(shuō)顯得非常復(fù)雜。v位勢(shì)法求檢驗(yàn)數(shù)時(shí)，第一步需要將運(yùn)輸方案表（初始可行解）中的運(yùn)輸量（數(shù)字格）換上單

16、位運(yùn)價(jià)表中對(duì)應(yīng)格的運(yùn)價(jià)：38銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3 4 3 3 1 6 3749銷(xiāo)銷(xiāo) 量量 3 6 5 6銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 3 10 1 2 4 5Table11 運(yùn)輸方案表Table12 調(diào)運(yùn)價(jià)格表39 第二步在上表的右面和下面增加一行和一列，并新添上一些數(shù)字，使得表中的各個(gè)數(shù)恰好等于他所在行和列的這些新添寫(xiě)的數(shù)字之和。通常用ui(i=1,2,.,m)和vj(j=1,2,.,n)來(lái)代表這些新添數(shù)字。 ui和vj分別稱(chēng)為第i行和第j列的位勢(shì)。 由于這些數(shù)字是相互關(guān)聯(lián)的，填寫(xiě)時(shí)先決定其中的任意一個(gè)，再推導(dǎo)出其余位勢(shì)的數(shù)值

17、，如令v1=1，則有如下的位勢(shì)表：40再用閉回路法計(jì)算各空格的檢驗(yàn)數(shù)，如（再用閉回路法計(jì)算各空格的檢驗(yàn)數(shù)，如（A3，B1）格的）格的檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：C31是空格（是空格（A3，B1）對(duì)應(yīng)的運(yùn)價(jià)表中的運(yùn)價(jià)，）對(duì)應(yīng)的運(yùn)價(jià)表中的運(yùn)價(jià)，u3+v1恰恰好是該空格所在行和列的位勢(shì)，類(lèi)似的，任意空格的檢驗(yàn)好是該空格所在行和列的位勢(shì)，類(lèi)似的，任意空格的檢驗(yàn)數(shù)為：數(shù)為：銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4uiA1A2A3 3 10 1 2 4 510-4vj 1 8 2 9+1)()()()()()(133121231314343131vucuvuvuvuvuvc)(jiijijvucTable13 位勢(shì)表

18、41得到各空格處的檢驗(yàn)數(shù)，經(jīng)過(guò)對(duì)比可以發(fā)現(xiàn)，這與閉回路法計(jì)算結(jié)果相一致。銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 1 2 1 -1 10 12Table14 檢驗(yàn)數(shù)表42ij43表上作業(yè)法計(jì)算步驟框圖表上作業(yè)法計(jì)算步驟框圖分析實(shí)際問(wèn)題分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo)平衡表列出產(chǎn)銷(xiāo)平衡表和單位運(yùn)價(jià)表和單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案確定初始調(diào)運(yùn)方案（最小元素法或（最小元素法或Vogel法）法）求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)（閉回路法或位勢(shì)法）（閉回路法或位勢(shì)法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)00找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)用閉回路調(diào)整，得出新方案用閉回路調(diào)整，得出新方案得到最優(yōu)方案得到最優(yōu)方案算出總的運(yùn)價(jià)

19、算出總的運(yùn)價(jià)是否44三、表上作業(yè)法與單純形法的比較（課后請(qǐng)大家進(jìn)一步思考）1.初始基可行解的確定；2.最優(yōu)性檢驗(yàn)；3.確定入基變量；4.確定出基變量；5.迭代運(yùn)算。v表上作業(yè)法計(jì)算步驟、過(guò)程與單純形法相同，但在具體計(jì)算時(shí)卻不必畫(huà)出單純形表，而只需在產(chǎn)銷(xiāo)平衡表上進(jìn)行。45四、多個(gè)最優(yōu)方案的情形v識(shí)別運(yùn)輸問(wèn)題是否有多個(gè)最優(yōu)解的方法與單純形法一樣，只需要看最優(yōu)方案中是否有非基變量的檢驗(yàn)數(shù)為零。如某個(gè)非基變量的檢驗(yàn)數(shù)為零，可知此運(yùn)輸問(wèn)題有多個(gè)最優(yōu)解。此時(shí)只需要把檢驗(yàn)數(shù)為零的非基變量作為入基變量，調(diào)整運(yùn)輸方案，就可得到另一個(gè)最優(yōu)方案。46銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4產(chǎn)產(chǎn) 量量A1A2A3 5

20、 2 3 1 6 3749銷(xiāo)銷(xiāo) 量量 3 6 5 6銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 2 2 1 9 120+2-2-2+2檢驗(yàn)數(shù)表最優(yōu)方案調(diào)整表473 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及應(yīng)用舉例v當(dāng)產(chǎn)大于銷(xiāo) 時(shí)，運(yùn)輸問(wèn)題的數(shù)學(xué)模型可以寫(xiě)成：)(11minjjiba 0),1(),1(.min1111ijmijijnjiijminjijijxnjbxmiaxtsxcz48 由于總的產(chǎn)量大于銷(xiāo)量，就要考慮多余的物資在哪一個(gè)產(chǎn)地就地庫(kù)存的問(wèn)題。設(shè) 是產(chǎn)地 的庫(kù)存量，于是有1,nixiAminjnjmiinimijijnjnjiijniijbbaxnjbxmiaxxx11111,11111,

21、), 1(), 1(49學(xué)模型，可得將上面的式子代入原數(shù)令) 1, 1(0), 1, 1(njmicnjmiccijijij0),1(),1(.min1111111,11111 ijmijijinjijmiminjijijijniminjminjijijijijxnjbxmiaxtsxcxcxcxcz50題。轉(zhuǎn)化成一個(gè)產(chǎn)銷(xiāo)平衡問(wèn)，最終也價(jià)為假想產(chǎn)地到各銷(xiāo)地的運(yùn)在單位運(yùn)價(jià)表上令從該，該地產(chǎn)量為產(chǎn)地產(chǎn)銷(xiāo)表中增加一個(gè)假想產(chǎn)時(shí)，只需在題。類(lèi)似的，當(dāng)銷(xiāo)大于轉(zhuǎn)化為一個(gè)產(chǎn)銷(xiāo)平衡問(wèn)價(jià)均為零，就產(chǎn)地到該銷(xiāo)地的單位運(yùn)而在單位運(yùn)價(jià)表中從個(gè)銷(xiāo)地的總需要量為（實(shí)際上是庫(kù)存），該假想的銷(xiāo)地于銷(xiāo)時(shí)，只要增加一個(gè)運(yùn)輸問(wèn)題。所

22、以當(dāng)產(chǎn)大是一個(gè)產(chǎn)銷(xiāo)平衡的在上面的模型中0)(1)(1,111111111miinjjnjjmiinjjnjnjmiiabmibanjbbba51 例例2 設(shè)有A1、A2、A3三個(gè)產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為7t、5t、7t，B1、B2、B3、B4四個(gè)銷(xiāo)地需要該種物資，銷(xiāo)量分別為2t、3t、4t、6t，又知各產(chǎn)銷(xiāo)地之間的單位運(yùn)價(jià)表如下所示，試決定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4A1A2A3 2 11 3 4 10 3 5 9 7 8 1 2Table 單位運(yùn)價(jià)表52Table5 產(chǎn)銷(xiāo)平衡表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 庫(kù)庫(kù)存存產(chǎn)產(chǎn) 量量A1A2A37

23、57銷(xiāo)銷(xiāo) 量量 2 3 4 6 4銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 庫(kù)存庫(kù)存A1A2A3 2 11 3 4 0 10 3 5 9 0 7 8 1 2 0Table6 單位運(yùn)價(jià)表 總產(chǎn)量19，總銷(xiāo)量15，產(chǎn)大于銷(xiāo)53銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 庫(kù)存庫(kù)存產(chǎn)產(chǎn) 量量A1A2A3 2 3 2 3 2 4 3757銷(xiāo)銷(xiāo) 量量 2 3 4 6 4Table18 運(yùn)輸方案表54 例例3 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)的需要量及從各化肥廠到各地區(qū)的單位運(yùn)價(jià)表如下所示，試決定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。Table 單位運(yùn)價(jià)和

24、產(chǎn)銷(xiāo)量表需求地區(qū)需求地區(qū)化肥廠化肥廠 產(chǎn)量產(chǎn)量（萬(wàn)（萬(wàn)t）ABC 16 13 22 17 14 13 19 15 19 20 23 506050最低需求（萬(wàn)最低需求（萬(wàn)t）最高需求（萬(wàn)最高需求（萬(wàn)t） 30 70 0 10 50 70 30 不限不限55Table 產(chǎn)銷(xiāo)平衡表 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 產(chǎn)產(chǎn) 量量ABCD50605050銷(xiāo)銷(xiāo) 量量 30 20 70 30 10 50Table 單位運(yùn)價(jià)表 最高需求為210萬(wàn)t，大于產(chǎn)量，增加一假想產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 ABCD 16 16 13 22 17 17 14 14 13 19 15 15 19 19 20 23 M M M 0 M 0 M 0

25、不能由某地提供由假想產(chǎn)地提供，滿(mǎn)足不滿(mǎn)足均可56Table 運(yùn)輸方案表銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 產(chǎn)產(chǎn) 量量ABCD 50 20 10 30 30 20 0 30 2050605050銷(xiāo)銷(xiāo) 量量 30 20 70 30 10 5057vMin 16x11+13x12+22x13+17x14+14x21+13x22+19x23+15x24+19x31+20 x32+23x33+1000 x34vStvX11+x12+x13+x14=50vX21+x22+x23+x24=60vX31+x32+x33+x34=50vX11+x21+x31=30vX11+x21+x31=50vX12+x22+x32=70vX1

26、3+x23+x33=10vend58 例例4 （中間轉(zhuǎn)運(yùn)問(wèn)題）在典例典例中，如果假定：每個(gè)工廠生產(chǎn)的糖果不一定直接發(fā)送到銷(xiāo)售點(diǎn)，可以將其中幾個(gè)產(chǎn)地的糖果集中一起運(yùn)；運(yùn)往各銷(xiāo)地的糖果可以先運(yùn)給其中幾個(gè)銷(xiāo)地，再轉(zhuǎn)運(yùn)給其他銷(xiāo)地；除產(chǎn)、銷(xiāo)地之外，中間還有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷(xiāo)地之間或產(chǎn)銷(xiāo)地之間轉(zhuǎn)運(yùn)。已知各產(chǎn)地、銷(xiāo)地、中間轉(zhuǎn)運(yùn)站及相互之間每噸糖果的運(yùn)價(jià)如下表，問(wèn)在考慮到產(chǎn)銷(xiāo)地之間直接運(yùn)輸和非直接運(yùn)輸?shù)母鞣N可能方案的情況下，如何將三個(gè)廠每天生產(chǎn)的糖果運(yùn)往銷(xiāo)售地，使總的運(yùn)費(fèi)最少？59產(chǎn)地產(chǎn)地中間裝運(yùn)站中間裝運(yùn)站銷(xiāo)地銷(xiāo)地A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4產(chǎn)地產(chǎn)地A1A2A3 1

27、3 1 3 2 1 4 3 3 5 2 1 2 3 3 11 3 10 1 9 2 8 7 4 10 5中間轉(zhuǎn)運(yùn)站中間轉(zhuǎn)運(yùn)站T1T2T3T4 2 3 1 1 5 4 2 3 2 3 1 3 2 1 1 1 3 1 2 2 1 2 2 8 4 6 4 5 2 7 1 8 2 4 1 2 6銷(xiāo)地銷(xiāo)地B1B2B3B4 3 1 7 11 9 4 3 2 10 10 8 5 2 4 1 1 8 5 8 4 2 2 2 6 7 4 6 1 4 2 1 2 1 4 2 3 2 1 3601.由于問(wèn)題中所有產(chǎn)地、中間轉(zhuǎn)運(yùn)站、銷(xiāo)地都可以看作產(chǎn)地，又可以看作銷(xiāo)地。因此把整個(gè)問(wèn)題當(dāng)作有11個(gè)產(chǎn)地和11個(gè)銷(xiāo)地的擴(kuò)大的運(yùn)輸問(wèn)題。2.對(duì)擴(kuò)大的運(yùn)輸問(wèn)題建立單位運(yùn)價(jià)表，方法是將不可能的運(yùn)輸方案運(yùn)價(jià)用任意大的正數(shù)M代替。3.所有中間轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷(xiāo)量，由于運(yùn)費(fèi)最少時(shí)不可能出現(xiàn)一批物資來(lái)回倒運(yùn)的現(xiàn)象，所以每個(gè)轉(zhuǎn)運(yùn)站的運(yùn)數(shù)不超過(guò)20