第五章運(yùn)輸問題

1、第五章第五章 運(yùn)輸問題運(yùn)輸問題 運(yùn)輸問題及其數(shù)學(xué)建模 表上作業(yè)法5.3 產(chǎn)銷不平衡的運(yùn)輸問題 應(yīng)用舉例本章主要內(nèi)容： 運(yùn)輸問題及其數(shù)學(xué)模型 在日常生活中，經(jīng)常碰到物資調(diào)撥中的運(yùn)輸問題。 例如 電子商務(wù)中的物流問題，無論電商還是快遞公司都建立自己的物流倉庫； 經(jīng)濟(jì)生活中，煤碳、鋼材、糧食、木材等物資，在全國都有若干生產(chǎn)基地； 分別將這些物資調(diào)到各消費(fèi)基地去，應(yīng)如何制定調(diào)運(yùn)方案，使總的運(yùn)輸費(fèi)用最少？問題的提出: 運(yùn)輸問題及其數(shù)學(xué)模型（續(xù)）例1 某公司從兩個(gè)產(chǎn)地兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：

2、應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200解：產(chǎn)銷平衡問題：總產(chǎn)量解：產(chǎn)銷平衡問題：總產(chǎn)量 = = 總銷量總銷量500500 設(shè)設(shè) x xijij 為從產(chǎn)地為從產(chǎn)地A Ai i運(yùn)往銷地運(yùn)往銷地B Bj j的運(yùn)輸量，得到下列運(yùn)輸量表：的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11

3、+ x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）物資調(diào)運(yùn)是一個(gè)典型的線性規(guī)劃問題物資調(diào)運(yùn)是一個(gè)典型的線性規(guī)劃問題.1939前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一問題問題,1941年美國數(shù)學(xué)家年美國數(shù)學(xué)家F.L.Hitchcock提提出運(yùn)輸問題數(shù)學(xué)模型出運(yùn)輸問題數(shù)學(xué)模型,1951年年Dantzig將此將此類問題的解法系統(tǒng)化類問題的解法系統(tǒng)化,完善化完善化,改為用表上作改為用表上作業(yè)法求解業(yè)法求解. 運(yùn)輸問題的一般提法是：設(shè)某種物資有m m個(gè)產(chǎn)地和n n個(gè)銷地。產(chǎn)地A Ai i的產(chǎn)

4、量為 ；銷地B Bj j的銷量 。從第i i個(gè)產(chǎn)地向第j j個(gè)銷地運(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)銷平衡的條件下，

5、要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為：0, 2 , 1) 13(, 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.

6、變量多（mn個(gè)），但結(jié)構(gòu)簡單。 技術(shù)系數(shù)矩陣 該系數(shù)矩陣中每列只有兩個(gè)元素為1，其余的都為零。ijab2.m+n個(gè)約束中有一個(gè)是多余的（因?yàn)槠溟g含有一個(gè)平衡關(guān)系式 ）所以R(A)=m+n-1，即解的mn個(gè)變量中基變量為m+n-1個(gè)。定理1 在產(chǎn)銷平衡的運(yùn)輸問題中,其約束方程組的系數(shù)矩陣和增廣矩陣的秩相等,且等于m+n-1.證明:3、運(yùn)輸問題的基本性質(zhì). 1)(1)(1A11nmAranknmAranknmAnmbanjjmii及行之和，必有行之和等于后中前因此行，行，另一個(gè)屬于后必有一個(gè)屬于前中每列的兩個(gè)非零元素及由 .,11111011010njjmiinjnjmiijjminjijmiii

7、jbaxbxax所以及則是方程組的一個(gè)可行解設(shè)定理定理2 2 方程組方程組 有解的充要條件是有解的充要條件是0 xbAx證明:必要性.11minjjiba充分性充分性., 2 , 1, 2 , 1,111011101110011njjminjijmiiminjijiinjjinjjinjijjiijnjjmiibxaxaMMabMaMbaxnjmiMbaxMba同理故取設(shè)定理定理3 平衡的運(yùn)輸問題一定有最優(yōu)解平衡的運(yùn)輸問題一定有最優(yōu)解.minjijijijijSxcScx110.min, 0, 0, 0存在故證明證明: 表上作業(yè)法 運(yùn)輸問題仍然是線性規(guī)劃問題，可以用線性規(guī)劃法中的單純形法來解決

8、。但是： 1.運(yùn)輸問題所涉及的變量多，造成單純形表太大； 2.若把技術(shù)系數(shù)矩陣A中的0迭代成非0，會使問題更加復(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)，常用的方法有閉回路法和位勢法，用這兩種方法計(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)量、各銷地的

9、銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表2所示 問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 即初始基本可行解的確定，與一般線性規(guī)劃問題不同，產(chǎn)銷平衡運(yùn)輸問題總是存在可行解。1、確定初始方案 確定初始基本可行解的方法很多，一般希望方法是既簡便，又盡可能接近最優(yōu)解。下面介紹三種方法：最小元素法，西北角法、 Vogel 法（1）最小元素法 最小元素法的基本思想是優(yōu)先滿足單位運(yùn)價(jià)最小的供銷業(yè)務(wù)。 首先找出運(yùn)價(jià)最小的，并以最大限度滿足其供銷量為原則確定供銷業(yè)務(wù)。同樣的方法反復(fù)進(jìn)行直到確定了所有的供銷業(yè)務(wù)，得到一個(gè)完整的調(diào)運(yùn)方案即初始基本可行解為止。 發(fā)發(fā)量7 3113104 19289 74105收量 365

10、6 20例2 見下表:收321AAA4321BBBB4321BBBB36413343331方案表運(yùn)價(jià)表以此，得到一初始方案：X13=4 , X14=3， X21=3，X23=1， X32=6， X34=3（有數(shù)格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：）有數(shù)格是基變量,共m+n-1=3+4-1=6個(gè)?？崭袷欠腔兞浚矂澣+n=7條線；）表格中一般要有表格中一般要有(m+n-1)(m+n-1)個(gè)數(shù)字格。個(gè)數(shù)字格。如果填上一個(gè)變量之后能同時(shí)劃去兩條線（一行與一列），就須在所劃去的該行或該列填一個(gè)0，此0格當(dāng)有數(shù)格對待。以保證有以保

11、證有(m+n-1)(m+n-1)個(gè)數(shù)字格作個(gè)數(shù)字格作為基變量。為基變量。 初始方案運(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à)表42236應(yīng)用西北角法和最小元素法，每次填完數(shù)，都應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一只劃去一行或一列。行或一列。 當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃

12、去一行(列列)。在飽和的列（行）沒被劃去的格內(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)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)（百元）如下表所示。（百元）如下表所示。 銷產(chǎn)A1753859A2402948A3806375需求35405565195 問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小問應(yīng)如何

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

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

15、路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363計(jì)算出空格的檢驗(yàn)數(shù)等于閉回路上由此空格起奇數(shù)頂點(diǎn)奇數(shù)頂點(diǎn)運(yùn)價(jià)與偶數(shù)頂點(diǎn)運(yùn)價(jià)負(fù)值的代數(shù)和。運(yùn)價(jià)與偶數(shù)頂點(diǎn)運(yùn)價(jià)負(fù)值的代數(shù)和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 22= 9-2+310+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)

16、數(shù)小于零，表明當(dāng)前方案尚有待調(diào)整。 若所有的空格檢驗(yàn)數(shù)都大于等于零，表明任何一個(gè)空格處調(diào)運(yùn)1單位都會引起總成本的上升，這表明當(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ì)算都會產(chǎn)生困難。路以及計(jì)算都會產(chǎn)生困難。（2）位勢法（對偶變量法） 對于一個(gè)調(diào)運(yùn)方案的每列賦予一個(gè)值，稱為列位勢，記 ，對于每行賦予一個(gè)值，稱為行位勢，記為 nvvv,21muuu,21ijjicvu 則檢驗(yàn)

17、數(shù)為： 它們的值由下列方程組決定：其中， cij 是所有基變量（數(shù)字格）xij 的運(yùn)價(jià)系數(shù) 。jiijijvuCi i = 1, , = 1, , m m ; ; j j = 1, , = 1, , n n產(chǎn)產(chǎn)量437 311 310314 1928639 7410 5需求3656 20321AAA4321BBBB4321BBBB銷4321vvvv321uuuu1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 5421103344332

18、232332211214411331cvucvucvucvucvucvu該乘數(shù)方程有六個(gè)方程,七個(gè)未知數(shù),一定有解,且有無窮多解.可令 得出一組解., 01u103925104321321vvvvuuu由這組解按下面的公式求空格(非基變量的檢驗(yàn)數(shù):jiijijvuC產(chǎn)產(chǎn)量437 311 310314 1928639 7410 5需求3656 20321AAA4321BBBB4321BBBB銷4321vvvv321uuu123) 5(10102) 5(7110) 1(819) 1(9290111203333333133131422424222222211212111111vucvucvucvuc

19、vucvuc51010392121-110120000003、調(diào)整方案調(diào)運(yùn)方案的判優(yōu)準(zhǔn)則:對調(diào)運(yùn)方案表中的每一空格作一條閉回路,并求出檢驗(yàn)數(shù),如果檢驗(yàn)數(shù)全部大于等于零,則該調(diào)運(yùn)方案最優(yōu).否則要調(diào)整調(diào)運(yùn)方案.方案的調(diào)整 選取入基變量:絕對值最大的負(fù)檢驗(yàn)數(shù)的空格對應(yīng)的非基變量為入基變量.本例中 為入基變量.24 入基變量的取值為,=min偶轉(zhuǎn)角點(diǎn)運(yùn)量.即該非基變量的運(yùn)量為,同時(shí)變?yōu)榛兞? 出基變量的選擇:在此閉回路上和偶轉(zhuǎn)角點(diǎn)上最小運(yùn)量對應(yīng)的基變量變?yōu)榱?該變量是出基變量,在新方案中它的位置是空格. 在該閉回路中按奇,偶點(diǎn)進(jìn)行運(yùn)量的平衡調(diào)整,得一新的調(diào)運(yùn)方案. 對新方案判優(yōu),調(diào)整,直到求出最優(yōu)方

20、案.3、調(diào)整方案（續(xù)）方案的調(diào)整產(chǎn)產(chǎn)量437 311 310314 1928639 7410 5需求3656 20321AAA4321BBBB4321BBBB銷121-11012000000124作 x24 的閉回路，調(diào)整數(shù)=1，調(diào)整得B1B2B3B4A152A231A363注：若閉回路的偶數(shù)頂點(diǎn)中同時(shí)有兩個(gè)格以上運(yùn)量為，則調(diào)整后其中一個(gè)變空格，其余填0。（保證基變量個(gè)數(shù)不變）再用閉回路法或位勢法求各空格的檢驗(yàn)數(shù)，B1B2B3B4A152A231A363 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余的 xij = 0 總運(yùn)費(fèi)為

21、： f = 53 + 210 + 31 + 18 + 64 + 35 = 85 。 銷銷產(chǎn)產(chǎn)A102A221A3912表中的所有檢驗(yàn)數(shù)都非負(fù)，故上表中的解為最優(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)量

22、某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列，時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列，這時(shí)就出現(xiàn)了退化。 在運(yùn)輸問題中，退化解是時(shí)常發(fā)生的。為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化時(shí)應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為（迭代過程中基可行解的分量恰好為（m+n-1）個(gè)。個(gè)。表上作業(yè)法中需要說明的問題 三、 產(chǎn)銷不平衡的運(yùn)輸問題 前面我們討論的運(yùn)輸問題，都是產(chǎn)銷平衡的問題，即滿足 在實(shí)際問題中，產(chǎn)銷往往是不平衡的，遇到這種情況，我們可以經(jīng)過簡單的處理，使其轉(zhuǎn)化為產(chǎn)銷平衡問題，然后再按前面的方法來求解。 njjmiiba1

23、11、產(chǎn)量大于銷量 對于產(chǎn)大于銷問題 ，可得到下列運(yùn)輸問題的模型： njjmiiba11ijminjijxcz 11minmiaxtsinjij, 2 , 1. .1njbxjmiij, 2 , 11 njmixij, 2 , 1, 2 , 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 nBnjjmiinbab111), 2 , 1( 01,micni minjijijxcz111min)1, 2 , 1 ;, 2 , 1( 0 )1, 2 , 1

24、( ), 2 , 1( 111 njmixnjbxmiaxijjmiijinjij 例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需求533625 123114單位運(yùn)價(jià)表解： 這里，總產(chǎn)量為 78 + 45 = 123 ；總銷量為 53 +36 + 25 = 114 。產(chǎn)銷不平衡，增加一個(gè)虛設(shè)的銷地，得到下表 銷產(chǎn)A1781315120A2451129220需求5236259123 銷產(chǎn)A113151278A21129224

25、5需求533625 1231142、產(chǎn)量小于銷量 對于產(chǎn)小于銷問題 njjmiiba11 可增加一個(gè)假想的產(chǎn)地 ，其產(chǎn)量為： 其相應(yīng)的運(yùn)費(fèi)為 上述不平衡問題就轉(zhuǎn)化為平衡的問題， 1mA miinjjmaba111), 2 , 1( 0, 1njcjm 111minminjijijxcz), 2 , 1; 1, 2 , 1( 0 ), 2 , 1( ) 1, 2 , 1( 111njmmixnjbxmmiaxijjmiijinjij 例5 某公司從兩個(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)用最

26、小？ 銷產(chǎn)A113151278A211292245需求533665 123154單位運(yùn)價(jià)表解: 這里，總產(chǎn)量小于總銷量，產(chǎn)銷不平衡，增加一個(gè)虛設(shè)的產(chǎn)地，得到下表 銷產(chǎn)A178131512A245112922A331000需求533665 154 銷產(chǎn)A113151278A211292245需求533665 123154四、應(yīng)用舉例 在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡單。解決實(shí)際問題時(shí)，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。下面為幾個(gè)典型的例子。 例6 有 A1、A2、A3 三個(gè)生產(chǎn)某種物資的產(chǎn)地，五個(gè)地區(qū) B1、B2、B3、B4、B5 對這種物資有需求。

27、現(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)量A1101520204050A22040153030100A33035405525130需求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ù)），以保

28、證在求最小運(yùn)輸費(fèi)用的前提下，該變量的值為零。銷地產(chǎn)地產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300 可以建立如下產(chǎn)銷平衡的運(yùn)輸費(fèi)用表銷地產(chǎn)地產(chǎn)量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070 例7 某研究院有 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à)

29、（元/噸）如下表。 由于需求大于供給，經(jīng)院研究決定 B1 區(qū)供應(yīng)量可減少 0900 噸，B2 區(qū)必須滿足需求量，B3 區(qū)供應(yīng)量不少于 1600 噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。 銷地產(chǎn)地A11751952081500A21601822154000需求量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)

30、的取值為 M ，可調(diào)整需求量的相應(yīng)變量 ，運(yùn)費(fèi)的取值為 0，作出產(chǎn)銷平衡的運(yùn)價(jià)表解： 這是需求量大于生產(chǎn)量的運(yùn)輸問題 銷地產(chǎn)地A11751751952082081500A21601601822152154000A2M0MM01500需求量260090011001600800 例8 某公司生產(chǎn)某種規(guī)格的設(shè)備，由于生產(chǎn)與季節(jié)有關(guān)系，生產(chǎn)能力與成本有差異，如下表所示。某種規(guī)格設(shè)備各季節(jié)的生產(chǎn)能力與成本 第一季度第二季度第三季度第四季度生產(chǎn)能力 (臺) 500700600200成本(萬元/臺）9.810.510.310.6 該廠年初簽訂的合同規(guī)定：當(dāng)年一、二、三、四每個(gè)季度末分別需要提供 200、30

31、0、500、400 臺這種規(guī)格的設(shè)備。如果生產(chǎn)出來的設(shè)備當(dāng)季不交貨，每臺每積壓一個(gè)季度需儲存、維護(hù)等費(fèi)用為 0.15萬元。試求在完成合同的前提下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解： 設(shè) x 為第 i 季度生產(chǎn)的第 j 季度交貨的設(shè)備數(shù)目，則問題的線性規(guī)劃模型為： c = 第 i 季度每臺的生產(chǎn)成本 + 0.15(j-i)（儲存、維護(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 ,

32、 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.45x34+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)的銷量；成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。例9例2 某公司從三個(gè)產(chǎn)