運(yùn)籌學(xué)3運(yùn)輸問題

1、 運(yùn)輸問題及其數(shù)學(xué)模型 表上作業(yè)法3.3 產(chǎn)銷不平衡的運(yùn)輸問題 應(yīng)用舉例本章主要內(nèi)容: 1掌握運(yùn)輸問題的數(shù)學(xué)模型、系數(shù)矩陣特殊形式 2掌握用西北角法、最小元素法求初始基可行解 3掌握回路、位勢(shì)法求解過程和表上作業(yè)法求解運(yùn)輸問題過程教學(xué)要求： 運(yùn)輸問題及其數(shù)學(xué)模型 在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到物資調(diào)撥中的運(yùn)輸問題。 例如 煤、鋼材、糧食、木材等物資，在全國都有若干生產(chǎn)基地，分別將這些物資調(diào)到各消費(fèi)基地去，應(yīng)如何制定調(diào)運(yùn)方案，使總的運(yùn)輸費(fèi)用最少？問題的提出: 運(yùn)輸問題的一般提法是：設(shè)某種物資有m m個(gè)產(chǎn)地和n n個(gè)銷地。產(chǎn)地A Ai i的產(chǎn)量為 ；銷地B Bj j的銷量 。從第i i個(gè)產(chǎn)地向第j j個(gè)銷

2、地運(yùn)輸每單位物資的運(yùn)價(jià)為C Cijij。 這就是由多個(gè)產(chǎn)地供應(yīng)多個(gè)銷地的單品種物資運(yùn)輸問題。問如何調(diào)運(yùn)這些物資才能使總運(yùn)費(fèi)達(dá)到最小。), 2 , 1( miai ), 2 , 1( njbj 1、運(yùn)輸問題的一般提法單位運(yùn)價(jià)表 （1） 。即運(yùn)輸問題的總產(chǎn)量等于其總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷平衡的運(yùn)輸問題。 （2） 。即運(yùn)輸問題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷不平衡的運(yùn)輸問題。 njjmiiba11 njjmiiba11分兩種情況來討論： 若用x xijij表示從A Ai i到B Bj j的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為： 0, 2 , 1)13

3、(, 2 , 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz2、運(yùn)輸問題的數(shù)學(xué)模型其中，ai和bj滿足： 稱為產(chǎn)銷平衡條件。 njjmiiba11將約束方程式展開可得11112122111211112222 nnmmnmmmxxaxxaxxaxxxbxxx212 nnmnnbxxxb約束方程式中共mn個(gè)變量，m+n個(gè)約束。行行行行nmAxxxxxxxxxmnmmnn 111111111111111111212222111211 上述模型是一個(gè)線性規(guī)劃問題。但是其結(jié)構(gòu)很特殊，特點(diǎn)如下：1.變量多（mn個(gè)），但結(jié)構(gòu)簡(jiǎn)單。 技術(shù)系數(shù)矩陣 該系數(shù)矩陣中每列只有兩

4、個(gè)元素為1，其余的都為零。ijab2.m+n個(gè)約束中有一個(gè)是多余的（因?yàn)槠溟g含有一個(gè)平衡關(guān)系式 ）所以R(A)=m+n-1，即解的mn個(gè)變量中基變量為m+n-1個(gè)。 表上作業(yè)法 運(yùn)輸問題仍然是線性規(guī)劃問題，可以用線性規(guī)劃法中的單純形法來解決。但是： 1.運(yùn)輸問題所涉及的變量多，造成單純形表太大； 2.若把技術(shù)系數(shù)矩陣A中的0迭代成非0，會(huì)使問題更加復(fù)雜。 以上兩個(gè)原因使得我們不得不利用運(yùn)輸問題的特點(diǎn)設(shè)計(jì)出它的特殊解法表上作業(yè)法。表上作業(yè)法，實(shí)質(zhì)上還是單純形法。其步驟如下：1.確定一個(gè)初始可行調(diào)運(yùn)方案?？梢酝ㄟ^最小元素法、西北角法、Vogel 法來完成；2.檢驗(yàn)當(dāng)前可行方案是否最優(yōu)，常用的方法有

5、閉回路法和位勢(shì)法，用這兩種方法計(jì)算出檢驗(yàn)數(shù)，從而判別方案是否最優(yōu)；3.方案調(diào)整，從當(dāng)前方案出發(fā)尋找更好方案，常采用閉回路法。表上作業(yè)法（續(xù)） 某公司從三個(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)如下表3-4所示 問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 即初始基本可行解的確定，與一般線性規(guī)劃問題不同，產(chǎn)銷平衡運(yùn)輸問題總是存在可行解。1、確定初始方案 確定初始基本可行解的方法很多，一般希望方法是既簡(jiǎn)便，又盡可能接近最優(yōu)解。下面介紹兩種方法：最小元素法，西北角法、 Vogel 法（1）最小元素法 最小元素法的基本思想是優(yōu)先

6、滿足單位運(yùn)價(jià)最小的供銷業(yè)務(wù)。 首先找出運(yùn)價(jià)最小的，并以最大限度滿足其供銷量為原則確定供銷業(yè)務(wù)。同樣的方法反復(fù)進(jìn)行直到確定了所有的供銷業(yè)務(wù)，得到一個(gè)完整的調(diào)運(yùn)方案即初始基本可行解為止。 銷產(chǎn)A17311310A241928A3974105需求3656201321344653103方案表運(yùn)價(jià)表以此，得到一初始方案：X21=3，X32=6，X13=4，X23=1，X14=3，X34=3（有數(shù)格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（）有數(shù)格是基變量，共m+n-1=3+4-1=6個(gè)。空格是非基變量，共劃去m+n=7條線；（）如果填上一個(gè)

7、運(yùn)量之后能同時(shí)劃去兩條線（一行與一列），就須在所劃去的該行或該列填一個(gè)0，此0格當(dāng)有數(shù)格對(duì)待。初始方案運(yùn)費(fèi) Z0=31+64+43+12+310+35=86(元)（2）西北角法 西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運(yùn)價(jià)的供銷業(yè)務(wù)，而是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求365620342236方案表運(yùn)價(jià)表應(yīng)用西北角法和最小元素法，每次填完數(shù)，都應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一只劃去一行或一列。行或一列。 當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，

8、也應(yīng)任意劃去一行(列列)。在保留的列（行）沒被劃去的格內(nèi)標(biāo)一個(gè)。在保留的列（行）沒被劃去的格內(nèi)標(biāo)一個(gè) 0 , 然后劃去然后劃去該列（行）。該列（行）。 某公司下屬有生產(chǎn)一種化工產(chǎn)品的三個(gè)產(chǎn)地某公司下屬有生產(chǎn)一種化工產(chǎn)品的三個(gè)產(chǎn)地A1、A2、A3 ，有四個(gè)銷售點(diǎn)，有四個(gè)銷售點(diǎn)B1、B2、B3、B4 銷售這種化工產(chǎn)品。各銷售這種化工產(chǎn)品。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)（百元）如下表所示。運(yùn)費(fèi)（百元）如下表所示。 銷產(chǎn)A1753859A2402948A3806375需求35405565195 問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)

9、最小問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 解：用西北角法求初始基本可行解解：用西北角法求初始基本可行解 銷產(chǎn)A1753859A2402948A3806375需求35405565195方案表運(yùn)價(jià)表35400401565(3)伏格爾法（次小運(yùn)價(jià)與最小運(yùn)價(jià)之差大者先安排） 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求365620方案表運(yùn)價(jià)表 2 5 1 3 01160123 2 1 2 3765122、判斷當(dāng)前方案是否為最優(yōu) 用單純形法解線性規(guī)劃問題時(shí)，在迭代過程中每次求得一個(gè)基本可行解以后，都要檢驗(yàn)它是不是最優(yōu)解，如果不是最優(yōu)解，就要繼續(xù)進(jìn)行迭代，直到求得最優(yōu)解或者判定無最優(yōu)解。

10、 表上作業(yè)法是用以下兩種方法來處理這個(gè)問題的：閉回路法和位勢(shì)法。（1）閉回路法 在單純形法中，為了檢驗(yàn)一個(gè)基本可行解是不是最優(yōu)解，需要求出所有非基變量的檢驗(yàn)數(shù)。在運(yùn)輸問題中，每個(gè)空格對(duì)應(yīng)一個(gè)非基變量。因此，我們需要求出每個(gè)空格的檢驗(yàn)數(shù)。 由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案。 B1B2B3B4A143A231A363 對(duì)方案表中每一空格，確定一條由空格出發(fā)的閉回路。 閉回路是由水平或垂直線組成的閉合圖形。閉回路上的頂點(diǎn)除了這個(gè)空格外，其余均為有數(shù)格。B1B2B3B4A143A231A363 可以證明，對(duì)每一個(gè)空格都存在而且惟一存在這樣一條封閉回路。B1B

11、2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363計(jì)算出空格的檢驗(yàn)數(shù)等于閉回路上由此空格起奇數(shù)頂點(diǎn)運(yùn)價(jià)與偶數(shù)頂點(diǎn)運(yùn)價(jià)負(fù)值的代數(shù)和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 22= 9-2+30+54 =1 31= 7-5+103+21=10 12=11 - 10+5 - 4=2 24= 810 +3 2 =-1 33=10 - 5+10 -3=12當(dāng)所有空格檢驗(yàn)數(shù) ij 0則當(dāng)前方案是最優(yōu)的，若尚有空格檢驗(yàn)數(shù)小于零，表明當(dāng)前方案尚有待調(diào)整。 若所有的空格檢驗(yàn)

12、數(shù)都大于等于零，表明任何一個(gè)空格處調(diào)運(yùn)1單位都會(huì)引起總成本的上升，這表明當(dāng)前方案不能再改進(jìn)，即定為最優(yōu)方案。 ij 具有確切的經(jīng)濟(jì)意義，它表示由Ai往Bj增運(yùn)1單位時(shí)，引起的總運(yùn)輸成本的變化數(shù)。B1B2B3B4A143A231A363 閉回路法的主要缺點(diǎn)是：閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算都會(huì)產(chǎn)生困難。路以及計(jì)算都會(huì)產(chǎn)生困難。（2）位勢(shì)法（對(duì)偶變量法） 對(duì)于一個(gè)調(diào)運(yùn)方案的每列賦予一個(gè)值，稱為列位勢(shì)，記 ，對(duì)于每行賦予一個(gè)值，稱為行位勢(shì)，記為 nvvv,21muuu,21ijjicvu 則檢驗(yàn)數(shù)為： ij = cij - ui - vj i =

13、 1, , m ; j = 1, , n它們的值由下列方程組決定：其中， cij 是所有基變量（數(shù)字格）xij 的運(yùn)價(jià)系數(shù) 。 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求3656201321344653103方案表運(yùn)價(jià)表u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1u2u3v1v3v2v4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 令u1 = 5 則有 v4 = 5 v3 = -2u2 = 4 u3=0v2=4v1= -311 = c11 u1 -

14、 v1 = 3 5 (-3) = 1 12 = c12 u1 v2 = 11 5 4 = 222 = c22 u2 v2 = 9 4 4 = 1 24 = c24 u2 v4 = 8 4 5 = -1 31 = c31 u3 - v1 = 7 0 (-3) = 10 33 = c33 u3 v3 = 10 0 (-2) = 12 再求非基變量（空格）檢驗(yàn)數(shù)： u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 （1）在有數(shù)格上填上相應(yīng)的

15、運(yùn)價(jià) 銷銷產(chǎn)產(chǎn)A143A231A363方案表運(yùn)價(jià)表 銷銷產(chǎn)產(chǎn)A1310A212A345u1u2u3v1v3v2v4位勢(shì)法在表上進(jìn)行： (2) 設(shè)u1=0，然后根據(jù)cij=ui+vj （有數(shù)格），依次求得ui和vj的值，并填在相應(yīng)的位置 銷銷產(chǎn)產(chǎn)A1310A212A345u1u2u3v1v3v2v4239100-1-5計(jì)算(ui+vj )表，把(ui+vj )位勢(shì)和值填在表中相應(yīng)位置上，并將有數(shù)格位置上的值ui+vj 加上括號(hào)以示區(qū)別。（ ） （ ）（ ）（ ）（ ）（ ）2989-3-2(ui+vj )表 銷銷產(chǎn)產(chǎn)A1311310A21928A374105運(yùn)價(jià)表 銷銷產(chǎn)產(chǎn)A129(3)(10)

16、A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5檢驗(yàn)數(shù)表 銷銷產(chǎn)產(chǎn)A1A2A3（3）計(jì)算檢驗(yàn)數(shù)表ij = cij ( ui + vj)(ui+vj )表121-110123、調(diào)整方案 若在檢驗(yàn)數(shù)上有某空格的檢驗(yàn)數(shù)為負(fù)，則可改進(jìn)方案，降低成本。調(diào)整的方法是從具有負(fù)檢驗(yàn)數(shù)的空格出發(fā)(有多個(gè)負(fù)檢驗(yàn)數(shù)時(shí)，選擇絕對(duì)值大的一個(gè))，沿它的閉回路進(jìn)行調(diào)整，即在保持方案可行的條件下，盡量增加空格上的運(yùn)量。 從ij 為最小負(fù)值的空格出發(fā).對(duì)其閉回路上的奇數(shù)頂點(diǎn)運(yùn)量增加,偶數(shù)頂點(diǎn)的運(yùn)量減少(這才能保證新的平衡)，其中調(diào)整量為該空格閉回路中偶數(shù)頂點(diǎn)的最小值。B1B2B3B4

17、A143A231A363注：若閉回路的偶數(shù)頂點(diǎn)中同時(shí)有兩個(gè)格以上運(yùn)量為，則調(diào)整后其中一個(gè)變空格，其余填0。（保證基變量個(gè)數(shù)不變）（p48）B1B2B3B4A152A231A36324= -1，作 x24 的閉回路，調(diào)整數(shù)=1，調(diào)整得再用閉回路法或位勢(shì)法求各空格的檢驗(yàn)數(shù)，B1B2B3B4A152A231A363 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余的 xij = 0 總運(yùn)費(fèi)為： f = 53 + 210 + 31 + 18 + 64 + 35 = 85 。 銷銷產(chǎn)產(chǎn)A102A221A3912表中的所有檢驗(yàn)數(shù)都非負(fù)，故上表

18、中的解為最優(yōu)解。檢驗(yàn)數(shù)表方案表表上作業(yè)法中需要說明的問題 （1）無窮多最優(yōu)解 當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí)，如果有某非基變量的檢驗(yàn)數(shù)等于零，則說明該運(yùn)輸問題有多重（無窮多）最優(yōu)解。上面的例題是多解情況 銷銷產(chǎn)產(chǎn)A102A221A3912B1B2B3B4A152A231A363檢驗(yàn)數(shù)表方案表B1B2B3B4A1250A213A363調(diào)整方案表 （2）退化 當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時(shí)，在迭代過程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列，這時(shí)就出現(xiàn)了退化。在運(yùn)輸問題中，退化解是時(shí)常發(fā)生的。為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化時(shí)應(yīng)在同時(shí)劃去的一行或一

19、列中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為（m+n-1）個(gè)。表上作業(yè)法中需要說明的問題 三、 產(chǎn)銷不平衡的運(yùn)輸問題 前面我們討論的運(yùn)輸問題，都是產(chǎn)銷平衡的問題，即滿足 在實(shí)際問題中，產(chǎn)銷往往是不平衡的，遇到這種情況，我們可以經(jīng)過簡(jiǎn)單的處理，使其轉(zhuǎn)化為產(chǎn)銷平衡問題，然后再按前面的方法來求解。 njjmiiba111、產(chǎn)量大于銷量 對(duì)于產(chǎn)大于銷問題 ，可得到下列運(yùn)輸問題的模型： njjmiiba11ijminjijxcz 11minmiaxtsinjij, 2 , 1.1 njbxjmiij, 2 , 11 njmixij, 2 , 1, 2

20、, 10 可增加一個(gè)假想的銷地 ，其銷量為： 某個(gè)產(chǎn)地Ai運(yùn)到這個(gè)假想銷地Bn+1的物資量xi,n+1，實(shí)際上就意味著將這些物資在原產(chǎn)地貯存，其相應(yīng)的運(yùn)價(jià) ，轉(zhuǎn)化為產(chǎn)銷平衡的問題，其數(shù)學(xué)模型為：1 nB njjmiinbab111), 2 , 1( 01,micni minjijijxcz111min)1, 2 , 1 ;, 2 , 1( 0 )1, 2 , 1( ), 2 , 1( 111 njmixnjbxmiaxijjmiijinjij 例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)如下表所示，問：應(yīng)如何

21、調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？ 銷產(chǎn)A113151278A211292245需求533625 123114單位運(yùn)價(jià)表解： 這里，總產(chǎn)量為 78 + 45 = 123 ；總銷量為 53 +36 + 25 = 114 。產(chǎn)銷不平衡，增加一個(gè)虛設(shè)的銷地，得到下表 銷產(chǎn)A1781315120A2451129220需求5236259123 銷產(chǎn)A113151278A211292245需求533625 1231142、產(chǎn)量小于銷量 對(duì)于產(chǎn)小于銷問題 njjmiiba11 可增加一個(gè)假想的產(chǎn)地 ，其產(chǎn)量為： 其相應(yīng)的運(yùn)費(fèi)為 上述不平衡問題就轉(zhuǎn)化為平衡的問題， 1mA miinjjmaba111), 2 , 1(

22、0, 1njcjm 111minminjijijxcz), 2 , 1; 1, 2 , 1( 0 ), 2 , 1( ) 1, 2 , 1( 111njmmixnjbxmmiaxijjmiijinjij 例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)如下表，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？ 銷產(chǎn)A113151278A211292245需求533665 123154單位運(yùn)價(jià)表解: 這里，總產(chǎn)量小于總銷量，產(chǎn)銷不平衡，增加一個(gè)虛設(shè)的產(chǎn)地，得到下表 銷產(chǎn)A178131512A245112922A331000需求53

23、3665 154 銷產(chǎn)A113151278A211292245需求533665 123154四、應(yīng)用舉例 在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單。解決實(shí)際問題時(shí)，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。下面為幾個(gè)典型的例子。 例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è)單位必須滿足。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？銷地產(chǎn)地產(chǎn)量A11015202

24、04050A22040153030100A33035405525130需求25115603070280300運(yùn)輸費(fèi)用及產(chǎn)量、需求量表解：由于產(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)用的前提下，該變量的值為零。銷地產(chǎn)地產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300 可以建立如下產(chǎn)銷平衡的運(yùn)輸費(fèi)用表銷地產(chǎn)地

25、產(chǎn)量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070 例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)量可減少 0900 噸，B2 區(qū)必須滿足需求量，B3 區(qū)供應(yīng)量不少于 1600 噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。 銷地產(chǎn)地A11751952081500A2

26、1601822154000需求量350011002400 由于 B1 區(qū)供應(yīng)量可減少 0900 噸，B3 區(qū)供應(yīng)量不少于 1600噸，可以把 B1 區(qū)和 B3 區(qū)分別設(shè)為兩個(gè)區(qū)：一個(gè)為必須滿足需求量的區(qū)域，另一個(gè)為可以調(diào)整供應(yīng)量的區(qū)域。 原問題化為五個(gè)需求區(qū)域 B1、B1、B2、B3、B3 的問題，同時(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à)表解： 這是需求量大于生產(chǎn)量的運(yùn)輸問題 銷地產(chǎn)地A11751751952082081500A21601601822152154000A2M0M

27、M01500需求量260090011001600800 例3-7 某公司生產(chǎn)某種規(guī)格的設(shè)備，由于生產(chǎn)與季節(jié)有關(guān)系，生產(chǎn)能力與成本有差異，如下表所示。某種規(guī)格設(shè)備各季節(jié)的生產(chǎn)能力與成本 第一季度第二季度第三季度第四季度生產(chǎn)能力 (臺(tái)) 500700600200成本(萬元/臺(tái)）9.810.510.310.6 該廠年初簽訂的合同規(guī)定：當(dāng)年一、二、三、四每個(gè)季度末分別需要提供 200、300、500、400 臺(tái)這種規(guī)格的設(shè)備。如果生產(chǎn)出來的設(shè)備當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用為 0.15萬元。試求在完成合同的前提下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解： 設(shè) x 為第 i 季度生產(chǎn)

28、的第 j 季度交貨的設(shè)備數(shù)目，則問題的線性規(guī)劃模型為： c = 第 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 。于是得到目標(biāo)函數(shù)： Min f = 9.8x11+9.95x12+10.1x13+ 10.25x14 + +10.5x22+10.65x23+10.8x24+10.3x33+ +10.45x

29、34+10.6x44x11 = 200 x12 + x22 = 300 x13 + x23 + x33 = 500 x14 + x24 + x34 + x44 = 400 交貨：交貨：生產(chǎn)：生產(chǎn)：x11 + x12 + x13 + x14 500 x22 + x23 + x24 700 x33 + x34 600 x44 200 xij 0 i=1,2,3,4 j i由于產(chǎn)大于銷，虛構(gòu)一個(gè)銷地，可構(gòu)造下列產(chǎn)銷平衡問題:各季節(jié)的生產(chǎn)、交貨費(fèi)用表 交貨生產(chǎn)第一季度第二季度第三季度第四季度虛設(shè)交貨生產(chǎn)能力第一季度9.89.9510.110.250500第二季度M10.510.6510.80700第三季度MM10.310.450600第四季度MMM10.60200交貨量2003005004006002000 把第 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)。例8例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)如表所示銷地銷地 產(chǎn)地產(chǎn)地 B B1 1 B B2 2 B B3 3 B B4 4