1、4 4 運輸問題運輸問題數(shù)學模型及其解法數(shù)學模型及其解法 4.1運輸問題數(shù)學運輸問題數(shù)學模型模型 4.2 運輸問題運輸問題的求解方法的求解方法 4.3 對對解解進進行行檢驗檢驗及改及改進進 4.4 運輸問題運輸問題的的進進一步一步討論討論 4.5 應應用用問題舉問題舉例例 P&T P&T 公司的配送問題案例公司的配送問題案例CANNERY 1 BellinghamCANNERY 2 EugeneWAREHOUSE 1 SacramentoWAREHOUSE 2 Salt Lake CityWAREHOUSE 3 Rapid CityWAREHOUSE 4 Albuquerque

2、CANNERY 3 Albert LeaFigure 1 Location of the canneries and warehouses for the P&T Company problem.運輸數(shù)據(jù)運輸數(shù)據(jù)CanneryOutputWarehouseAllocationBellingham75 truckloadsSacramento80 truckloadsEugene125 truckloadsSalt Lake City65 truckloadsAlbert Lea100 truckloadsRapid City70 truckloadsTotal300 truckload

3、sAlbuquerque85 truckloadsTotal300 truckloads目前的運輸計劃目前的運輸計劃WarehouseFrom ToSacramentoSalt Lake CityRapid CityAlbuquerqueCanneryBellingham75000Eugene565550Albert Lea001585卡車的運輸成本卡車的運輸成本W(wǎng)arehouseFrom ToSacramentoSalt Lake CityRapid CityAlbuquerqueCanneryBellingham$464$513$654$867Eugene352416690791Alber

4、t Lea995682388685總的運輸成本總的運輸成本= 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595運輸問題的特點運輸問題的特點n需求假設需求假設q每一個出發(fā)地都有一個固定的供應量，所有的供應量都每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地。必須配送到目的地。q每一個目的地都有一個固定得需求量，整個需求量都必每一個目的地都有一個固定得需求量，整個需求量都必須由出發(fā)地滿足。須由出發(fā)地滿足。n可行解的特性可行解的特性q當且僅當供應量的總和等于需求量的總和時，運輸問題當且僅

5、當供應量的總和等于需求量的總和時，運輸問題才有可行解。才有可行解。n成本假設成本假設q從任何一個出發(fā)地到任何一個目的地的貨物配送成本和從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系。所配送的數(shù)量成線性比例關(guān)系。q這個成本就等于配送的單位成本乘以所配送的數(shù)量。這個成本就等于配送的單位成本乘以所配送的數(shù)量。 S1S2S3D4D2D1D37512510080657085SuppliesDemandsSourcesDestinations(Bellingham)(Eugene)(Albert Lea)(Sacramento)(Salt Lake City)(Rapid Ci

6、ty)(Albuquerque)464513654867352416690791995682685388網(wǎng)絡表示網(wǎng)絡表示4.1 4.1 運輸問題的一般數(shù)學模型運輸問題的一般數(shù)學模型n有有m個產(chǎn)地生產(chǎn)個產(chǎn)地生產(chǎn)某某種物資，有種物資，有n個地區(qū)需要該類個地區(qū)需要該類物資物資n令令a1, a2, , am表示各產(chǎn)地產(chǎn)量，表示各產(chǎn)地產(chǎn)量， b1, b2, , bn表表示各銷地的銷量，示各銷地的銷量， ai= bj 稱為產(chǎn)銷平衡稱為產(chǎn)銷平衡n設設xij表示產(chǎn)地表示產(chǎn)地 i 運往銷地運往銷地 j 的物資量，的物資量，wij表示對表示對應的單位運費，則我們有運輸問題的數(shù)學模型如應的單位運費，則我們有運輸問題

7、的數(shù)學模型如下：下：0 , 2 , 1 , 2 , 1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxcxf銷量約束產(chǎn)地約束運輸問題有運輸問題有m n個決策變量，個決策變量，m+n 個約束條件。個約束條件。由于產(chǎn)銷平衡條件，只有由于產(chǎn)銷平衡條件，只有m+n1個相互獨立，個相互獨立，因此，運輸問題的基變量只有因此，運輸問題的基變量只有m+n1 個個例例1某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地將物品運往三個銷地B1、B2、B3，各產(chǎn)地的各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物

8、品的運費如下表所示，問：應如何調(diào)運可使總運輸費用最小問：應如何調(diào)運可使總運輸費用最小？解：解： 產(chǎn)銷平衡問題：產(chǎn)銷平衡問題： 總產(chǎn)量總產(chǎn)量 = 總銷量總銷量 設設 xij 為從產(chǎn)地為從產(chǎn)地Ai運往銷地運往銷地Bj的運輸量，得到下列運輸量表：的運輸量，得到下列運輸量表： B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200 Min f = 6Min f = 6x x1111+ 4+ 4x x1212+ 6+ 6x x1313+ 6+ 6x x2121+ 5+ 5x x2222+ 5+ 5x x23 23 s.t. s.t. x x1111+ + x x1

9、2 12 + + x x13 13 = 200= 200 x x21 21 + + x x2222+ + x x2323 = 300 = 300 x x11 11 + + x x21 21 = 150= 150 x x12 12 + + x x2222 = 150 = 150 x x13 13 + + x x2323 = 200 = 200 x xijij 0 ( i = 1 0 ( i = 1、2 2；j = 1j = 1、2 2、3 3）運輸問題有有限最優(yōu)解運輸問題有有限最優(yōu)解約束條件非常有規(guī)律，技術(shù)系數(shù)非約束條件非常有規(guī)律，技術(shù)系數(shù)非 0 即即 1平衡運輸問題數(shù)學模型特點平衡運輸問題數(shù)學

10、模型特點111111111111111111m行行n行行每個變量每個變量Xij對應的矩陣對應的矩陣列列中中,除第除第i個元素和第個元素和第m+j個個元素為元素為1外外,其余元素為零其余元素為零.每行有每行有n個個1，其余為，其余為0。所有結(jié)構(gòu)的約束條件是所有結(jié)構(gòu)的約束條件是等式約束等式約束各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和運輸問題的解運輸問題的解解滿足所有的約束條件解滿足所有的約束條件;基變量基變量對應的約束方程組的系數(shù)列向量線性無關(guān)對應的約束方程組的系數(shù)列向量線性無關(guān);解中非零變量解中非零變量Xij的個數(shù)不能大于的個數(shù)不能大于(m+n-1)個個;為使迭代求解順利

11、進行為使迭代求解順利進行,基變量的個數(shù)在迭代過基變量的個數(shù)在迭代過程中保持為程中保持為(m+n-1)個個;基變量的個數(shù)遠小于決策變量的個數(shù)基變量的個數(shù)遠小于決策變量的個數(shù).4.2 4.2 運輸問題的求解方法運輸問題的求解方法n采用表上作業(yè)法，稱為位勢法采用表上作業(yè)法，稱為位勢法n運算中涉及兩個表：運費表和產(chǎn)銷平衡表運算中涉及兩個表：運費表和產(chǎn)銷平衡表(分配表分配表)銷銷地地產(chǎn)產(chǎn)量量運運量量12nai產(chǎn)產(chǎn)地地1x11x12x1na12x21x22x2na2 mxm1xm2xmnam銷銷量量bjb1b2bn運費表運費表分配表分配表尋找初始可行解的方法尋找初始可行解的方法 1、西北角法、西北角法q從

12、從 x11開始分配，從西北向東南方向逐個分配開始分配，從西北向東南方向逐個分配qxij 的分配公式的分配公式列待分物資量列已分配的總量行尚余物資量行已分配的總量 ) ( ) (minjjbiiaxjiij例例2銷銷地地產(chǎn)產(chǎn)量量運運費費1234ai產(chǎn)產(chǎn)地地120113652591021031874115銷銷量量bj331212銷地產(chǎn)量運量1234ai產(chǎn)地15210315銷量 bj331212 例例4.2.1 4.2.1 西北角法西北角法銷地產(chǎn)量運量1234ai產(chǎn)地13x125210315銷量 bj331212銷地產(chǎn)量運量1234ai產(chǎn)地13252x2210315銷量 bj331212銷地產(chǎn)量運量

13、1234ai產(chǎn)地132521x2310315銷量 bj331212銷地產(chǎn)量運量1234ai產(chǎn)地1325219103x3315銷量 bj331212銷地產(chǎn)量運量1234ai產(chǎn)3315銷量 bj331212銷地產(chǎn)量運量1234ai產(chǎn)地132521910331215銷量 bj3312123141205)(67ijijijxcxfnm個基變量有 2 2、最低費用法、最低費用法 采用最小采用最小費用優(yōu)先費用優(yōu)先分配的原分配的原則則編編號號運運費費表表wij分分配配表表xij2011(3)6x135I5910210187411215331212編編號號運運費費表表wij分分配配表

14、表xij20113655II5910210187(4)1x331215331212編編號號運運費費表表wij分分配配表表xij20 113655III59 (10) 23341018741312 153312 12f(x)=121，費用比費用比西北角法西北角法低低84 3 3、運費差額法（沃格爾法、運費差額法（沃格爾法- -VolgeVolge）n最小元素法初看十分合理。但是，有時按某一最小元素法初看十分合理。但是，有時按某一最小單位運價優(yōu)先安排物品調(diào)運時，卻可能導最小單位運價優(yōu)先安排物品調(diào)運時，卻可能導致對其它代銷點配送時費用更高，從而使總費致對其它代銷點配送時費用更高，從而使總費用增加。用

15、增加。n對每一個供銷地或銷售地，均可由它到各銷售對每一個供銷地或銷售地，均可由它到各銷售地到各供應地的單位運價中找出最小單位運價地到各供應地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為和次小單位運價，并稱這兩個單位運價之差為該供應地或銷售地的該供應地或銷售地的罰數(shù)罰數(shù)。若罰數(shù)的值不大，。若罰數(shù)的值不大，當不能按最小單位運價安排運輸時造成的運費當不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數(shù)的值很大，不按最損失不大；反之，如果罰數(shù)的值很大，不按最小運價組織運輸就會造成很大的損失，故應盡小運價組織運輸就會造成很大的損失，故應盡量按最小單位運價安排運輸。量按最

16、小單位運價安排運輸。n采用最大差額費用采用最大差額費用(即利用每行或列中最小費用與次即利用每行或列中最小費用與次最小之間的差額中選最大最小之間的差額中選最大)優(yōu)先分配的原則。優(yōu)先分配的原則。f(x)=98，比比最低費用法最低費用法又低了又低了23編編號號運運費費表表wij分分配配表表xij20113635I5910233101874131513211331212編編 號號運運 費費 表表 wij分分 配配 表表 xij20113635II59102737101874131513211331212編編 號號運運 費費 表表 wij分分 配配 表表 xij20113635III5910273710

17、18741351513415331212編編 號號運運 費費 表表 wij分分 配配 表表 xij201136855IV59102737101874133751513-5331212 種某種物品先放在種某種物品先放在A A1 1、A A2 2和和A A3 3三個倉庫中，再運往使用地三個倉庫中，再運往使用地B B1 1、B B2 2、B B3 3和和B B4 4，其間的距離（或單位運價）如下表所示，各倉庫的存量和使用地的需要其間的距離（或單位運價）如下表所示，各倉庫的存量和使用地的需要量也都表示于下表中，試建立使總運輸費用最小的運輸問題數(shù)學模型。量也都表示于下表中，試建立使總運輸費用最小的運輸問

18、題數(shù)學模型。用前面講的三種方法分別求可行解用前面講的三種方法分別求可行解用上面的三種求下列運輸問題的解用上面的三種求下列運輸問題的解 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A116A210A322銷量銷量81412144124112103985116表表1用上面的三種求下列運輸問題的解用上面的三種求下列運輸問題的解 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A18816A26410A381422銷量銷量81412144124112103985116用西北角法求的可行解用西北角法求的可行解表表2412用上面的三種求下列運輸問題的解用上面的三種求下列運輸問題的解 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A110616A2

19、8210A314822銷量銷量81412144124112103985116用最小元素法求的可行解用最小元素法求的可行解表表3用上面的三種求下列運輸問題的解用上面的三種求下列運輸問題的解 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A112416A28210A314822銷量銷量81412144124112103985116用沃爾格法求的可行解用沃爾格法求的可行解表表44.3 對解的可行性進行檢對解的可行性進行檢驗驗 運輸表中的格子是空的運輸表中的格子是空的, ,則代表是非基變量則代表是非基變量. .若若存在非基變量的檢驗數(shù)小于零存在非基變量的檢驗數(shù)小于零, ,說明得到的解不說明得到的解不是最優(yōu)解！是最優(yōu)

20、解！運輸問題常用的解檢驗方法有運輸問題常用的解檢驗方法有2種：種：閉回路法；位勢法閉回路法；位勢法 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A110616A28210A314822銷量銷量81412144124112103985116檢驗用最小元素法求的可行解（下表）是否最優(yōu)檢驗用最小元素法求的可行解（下表）是否最優(yōu)表表34.3.1利用閉回路法檢驗分配方案是否最優(yōu)利用閉回路法檢驗分配方案是否最優(yōu)表表3中的可行解用閉回路法計算的檢驗數(shù)中的可行解用閉回路法計算的檢驗數(shù) 銷地產(chǎn)地B1B2B3B3產(chǎn)量產(chǎn)量A112A21-1A31012銷量銷量因因X23的檢驗數(shù)小于的檢驗數(shù)小于0，表，表3的調(diào)運方案不是最優(yōu)解的

21、調(diào)運方案不是最優(yōu)解 4.3.2利用位勢法檢驗分配方案是否最優(yōu)利用位勢法檢驗分配方案是否最優(yōu)l思路：思路：不采用單純型法，如何獲得不采用單純型法，如何獲得xij的檢驗數(shù)的檢驗數(shù)找到原問題的基礎可行解，保持互補松弛條件，找到原問題的基礎可行解，保持互補松弛條件，求出對應對偶問題的解，若該對偶問題的解非可求出對應對偶問題的解，若該對偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達到最優(yōu)行，則原問題的解不是最優(yōu)解；否則，達到最優(yōu)解解0, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnjbxmiaxxcxfnjmivucvuvbuavugjiijjinjjj

22、miii, 2, 1 , 2 , 1,),(max11不限利用位勢法檢驗分配方案是否最優(yōu)利用位勢法檢驗分配方案是否最優(yōu) 平衡運輸問題平衡運輸問題數(shù)學模型數(shù)學模型 平衡運輸問題平衡運輸問題的對偶問題的對偶問題3323132222121121112223222111131211232322222121131312121111vbxx vb xxvbxxuaxxxuaxxxxxxxxxc minccccc無限制321212332222221121331122111113322112211v,v,v,u,uv u vu vu v uvuvuvbvbvbuauamax cccccc動輸問題變量動輸問題變

23、量 的檢驗數(shù)表示為的檢驗數(shù)表示為: ijx)(,2121jiijijnmijijijijijijvucPvvvuuucYPczc設已得到運輸問題的基可行解設已得到運輸問題的基可行解,其基變量是其基變量是:1,2211nmsxxxssjijiji 由于基變量的檢驗數(shù)等于由于基變量的檢驗數(shù)等于0,0,故對于這組基變量故對于這組基變量可寫出議程組可寫出議程組: :ssssjijijijijijicvucvucvu22221111 可以證明上面的方程有解可以證明上面的方程有解,且由于對偶變量且由于對偶變量數(shù)比方程數(shù)多一個數(shù)比方程數(shù)多一個,故解不唯一故解不唯一.稱上面方程稱上面方程的解為位勢的解為位勢.

24、 對上面的方程組求解對上面的方程組求解, ,然后計算運輸問題的然后計算運輸問題的檢驗數(shù)檢驗數(shù), ,若有檢驗數(shù)小于零若有檢驗數(shù)小于零, ,則原運輸問題則原運輸問題的解不是最優(yōu)解的解不是最優(yōu)解. .4.3.3 4.3.3 解的改進解的改進 運輸問題中運輸問題中,若某一非基變量的檢驗數(shù)小于零若某一非基變量的檢驗數(shù)小于零,說明這說明這個非基變量作為基變量時個非基變量作為基變量時,運輸費用將更小運輸費用將更小.因而當前解因而當前解不是最優(yōu)解不是最優(yōu)解.用閉回路法進行調(diào)整用閉回路法進行調(diào)整. 將檢驗數(shù)最小的非基變量作為換入變量將檢驗數(shù)最小的非基變量作為換入變量,找出它在運輸找出它在運輸表中的閉回去路表中的

25、閉回去路,取閉回路中所有偶數(shù)點中最小運量取閉回路中所有偶數(shù)點中最小運量,在在所有奇數(shù)點上都增加這一最小運量所有奇數(shù)點上都增加這一最小運量,在所有偶數(shù)點上增在所有偶數(shù)點上增加這一最小運量加這一最小運量. 然后然后,再對調(diào)整后的解進行最優(yōu)性檢驗再對調(diào)整后的解進行最優(yōu)性檢驗,如不是最優(yōu)解如不是最優(yōu)解,就重復以上步驟繼續(xù)進行調(diào)整就重復以上步驟繼續(xù)進行調(diào)整,一直到得出最優(yōu)解為一直到得出最優(yōu)解為止止.4.3.4 4.3.4 需要說明的幾個問題需要說明的幾個問題1)1)若運輸問題的某一可行解有幾個非基變量的檢驗數(shù)均為若運輸問題的某一可行解有幾個非基變量的檢驗數(shù)均為負負, ,在繼續(xù)進行迭代時在繼續(xù)進行迭代時,

26、 ,取它們中的任一變量為換入變量取它們中的任一變量為換入變量均可使目標函數(shù)值得到改善均可使目標函數(shù)值得到改善, ,但通常取檢驗數(shù)小于零中最但通常取檢驗數(shù)小于零中最小者對應的變量為換入變量小者對應的變量為換入變量. .2)2)當?shù)竭\輸問題有最優(yōu)解時當?shù)竭\輸問題有最優(yōu)解時, ,如果有某非基變量的檢驗如果有某非基變量的檢驗數(shù)等于零數(shù)等于零, ,則說明該運輸問題有無窮多最優(yōu)解則說明該運輸問題有無窮多最優(yōu)解. .3)3)當運輸問題某部分產(chǎn)地的產(chǎn)量和當運輸問題某部分產(chǎn)地的產(chǎn)量和, ,與某一部分銷地的銷量與某一部分銷地的銷量和相等時和相等時, ,在迭代過程中有可能在某個格填入一個運量時在迭代過程中有

27、可能在某個格填入一個運量時需要同時劃去運輸表的一行和一列需要同時劃去運輸表的一行和一列, ,這時就出現(xiàn)了退化這時就出現(xiàn)了退化. .在運輸問題中在運輸問題中, ,退化解是時常發(fā)生的退化解是時常發(fā)生的, ,為了使一表上作業(yè)為了使一表上作業(yè)法的迭代工作進行下去法的迭代工作進行下去, ,退化時在同時劃去一行或一列的退化時在同時劃去一行或一列的某個格中填入數(shù)字某個格中填入數(shù)字0,0,表示這個格中的變量是取值為表示這個格中的變量是取值為0 0的基的基變量變量, ,使迭代過程中可行解的分量恰好為使迭代過程中可行解的分量恰好為(m+n-1)(m+n-1)個個. .4.4 4.4 運輸問題的進一步討論運輸問題的

28、進一步討論4.4.1 產(chǎn)銷不平衡產(chǎn)銷不平衡 1)供過于求，即供過于求，即 a i bj .數(shù)學模型為數(shù)學模型為:0, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnjbxmiaxxcxf 為借助于產(chǎn)銷平衡時的表上作業(yè)法求解為借助于產(chǎn)銷平衡時的表上作業(yè)法求解,可增加一個可增加一個假想的銷地假想的銷地Bn+1,由于實際上它不存在由于實際上它不存在,因而由產(chǎn)地因而由產(chǎn)地Ai(i=1,2,m)調(diào)運到這個假想銷地的物品數(shù)量調(diào)運到這個假想銷地的物品數(shù)量xi,n+1(相當于松馳變量相當于松馳變量),實際上是就地存貯在實際上是就地存貯在Ai的物品的物品數(shù)量數(shù)量.就地

29、存貯的物品不經(jīng)運輸就地存貯的物品不經(jīng)運輸,故其單位運費故其單位運費ci,n+1=0(i=1,2,m)令假想銷地的銷量為令假想銷地的銷量為bn+1,且且minjjinbab11101, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnnjbxmiaxxcxf 注意相對應的注意相對應的運輸表運輸表!4.4.1 產(chǎn)銷不平衡產(chǎn)銷不平衡 1)供過于求，即供過于求，即 ai bj .假想產(chǎn)地假想產(chǎn)地Am+1,它的它的產(chǎn)量等于產(chǎn)量等于:miinjjmaba111 由于這個假想的產(chǎn)地不存在由于這個假想的產(chǎn)地不存在, ,求出的由它發(fā)往各個銷地求出的由它發(fā)往各個銷地的物品

30、數(shù)量的物品數(shù)量x xm+1,jm+1,j(j=1,2,n),(j=1,2,n),實際上是各銷地所需物實際上是各銷地所需物品的欠缺額品的欠缺額, ,顯然有顯然有: :njcjm, 2 , 1, 0, 1例例 某市有三個造紙廠某市有三個造紙廠A1、A2、A3，其紙的產(chǎn)量，其紙的產(chǎn)量分別為分別為8、5和和9個單位。有個單位。有4個集中用戶，其需個集中用戶，其需要量分別是要量分別是4、3、5和和6個單位。由各造紙廠到個單位。由各造紙廠到各用戶的單位運輸價格如下表所示，請確定總運各用戶的單位運輸價格如下表所示，請確定總運費最小的調(diào)運方案。費最小的調(diào)運方案。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1312348A

31、2112595A367159銷量4356 假定假定m個產(chǎn)地個產(chǎn)地A1,A2,Am 和和n 個銷地個銷地B1,B2, Bn 都可以都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點和接收物品的作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點和接收物品的地點都有地點都有m+n個，這就是轉(zhuǎn)運問題。為建立數(shù)學模型，令：個，這就是轉(zhuǎn)運問題。為建立數(shù)學模型，令：4.4.2 4.4.2 有轉(zhuǎn)運的運輸問題有轉(zhuǎn)運的運輸問題ai: 第第i個產(chǎn)地的產(chǎn)量（凈供應量）；個產(chǎn)地的產(chǎn)量（凈供應量）；bj:第第j個銷地的銷量（凈需要量）；個銷地的銷量（凈需要量）；Xij: 由第由第i個發(fā)送地運到第個發(fā)送地運到第j個接收地的物品數(shù)量；個接收地

32、的物品數(shù)量；cij :由第由第i個發(fā)送地到第個發(fā)送地到第j個接收地的單位運價；個接收地的單位運價；ti:第第i個地點轉(zhuǎn)運物品的數(shù)量；個地點轉(zhuǎn)運物品的數(shù)量；ci:第第i個地點轉(zhuǎn)運物品的費用。個地點轉(zhuǎn)運物品的費用。 現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有：銷地排在后面，則有：am+1=am+2=am+n=0b1=b2=bm=0假定為平衡運輸問題，即有假定為平衡運輸問題，即有minjjiQba11有轉(zhuǎn)運的運輸問題有轉(zhuǎn)運的運輸問題有轉(zhuǎn)運的運輸問題的數(shù)學模型有轉(zhuǎn)運的運輸問題的數(shù)學模型)(, 2 , 1, 0, 1, 2 , 1, 1, 2

33、, 1min, 1, 121, 1, 121,1,1,21,1,1,21111jinmjixnmmjtbxxxxxmjtxxxxxnmmitxxxxxmitaxxxxxtcxczijjjjnmjjjjjjjjnmjjjjjjinmiiiiiiiiinmiiiiiiinmjiinmijjnmiiiijijjjjiiitQxtQx或 nmjixnmmjtbQxxmjQxxnmmiQxxmiaQxxQcxczijjjjnmjjnmjnmiiinmiinminmjnmiiijij,2, 1,0, 1,2, 1, 1,2, 1min,1,1,1,1111 將上式中各約束條件中的將上式中各約束條件中的ti

34、或或tj移到等式左側(cè)，然后兩側(cè)加移到等式左側(cè)，然后兩側(cè)加上上Q并令：并令： 有下面的運輸表達式：有下面的運輸表達式：jjjiiitQxtQx或有轉(zhuǎn)運的運輸問題的運量表有轉(zhuǎn)運的運輸問題的運量表 接收發(fā)送產(chǎn)地銷地發(fā)送量1mm+1m+n產(chǎn)地1X11X1mX1m+1X1m+nQ+a1 mXm1XmmXm,m+1Xm,m+nQ+am+1銷地m+1Xm+1,1Xm+1,mXm+1,m+1Xm+1,m+nQm+nXm+n,1Xm+n,mXm+n,m+1Xm+n,n+nQ接收量Q QQ+bm+1Q+bm+n有轉(zhuǎn)運的運輸問題運價表有轉(zhuǎn)運的運輸問題運價表 接收發(fā)送產(chǎn)地銷地發(fā)送量1mm+1m+n產(chǎn)地1-c1c1mc

35、1m+1c1m+nQ+a1 mcm1-cmcm,m+1cm,m+nQ+am+1銷地m+1cm+1,1cm+1,m-cm+1cm+1,m+nQm+ncm+n,1cm+n,mcm+n,m+1-cm+nQ接收地Q QQ+bm+1Q+bm+n例例 一個運輸系統(tǒng)包括了二個產(chǎn)地一個運輸系統(tǒng)包括了二個產(chǎn)地和、二和、二個銷地個銷地和及一個中間轉(zhuǎn)運站，各產(chǎn)和及一個中間轉(zhuǎn)運站，各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應節(jié)點處箭地的產(chǎn)量和各銷地的銷量用相應節(jié)點處箭線旁的數(shù)字表示，節(jié)點數(shù)字表示期間的運線旁的數(shù)字表示，節(jié)點數(shù)字表示期間的運輸單價，節(jié)點聯(lián)線上的數(shù)字表示期間的運輸單價，節(jié)點聯(lián)線上的數(shù)字表示期間的運輸單價，節(jié)點旁的數(shù)字

36、為該地的轉(zhuǎn)運單價，輸單價，節(jié)點旁的數(shù)字為該地的轉(zhuǎn)運單價，試確定最優(yōu)運輸方案。試確定最優(yōu)運輸方案。4.5 4.5 應用問題舉例應用問題舉例 由于運輸問題的表上作業(yè)法由于運輸問題的表上作業(yè)法,遠比一般單純形法遠比一般單純形法計算簡單計算簡單,因而人們在解決有些實際問題時因而人們在解決有些實際問題時,常常設法將其轉(zhuǎn)化為運輸問題的數(shù)學模型求解設法將其轉(zhuǎn)化為運輸問題的數(shù)學模型求解,下面下面通過幾個例子加以說明通過幾個例子加以說明.例例4.5.1 某企業(yè)和用戶簽訂了設備交貨合同某企業(yè)和用戶簽訂了設備交貨合同,已知已知該企業(yè)各季度的生產(chǎn)能力，每臺設備的生產(chǎn)該企業(yè)各季度的生產(chǎn)能力，每臺設備的生產(chǎn)成本和每季度末的交貨量（見下表），若生成本和每季度末的交貨量（見下表），若生產(chǎn)出來的設備當季不交貨，每臺設備每季度產(chǎn)出來的設備當季不交貨，每臺