[高等教育]Ch4 運輸問題ppt課件

1、第四章第四章 運輸問題運輸問題一、運輸問題的數(shù)學(xué)模型一、運輸問題的數(shù)學(xué)模型 問題的提出問題的提出 在許多大型連鎖超市的商品供應(yīng)在許多大型連鎖超市的商品供應(yīng), 物流公司的物資供物流公司的物資供應(yīng)都牽涉到眾多貨物的運輸問題應(yīng)都牽涉到眾多貨物的運輸問題. 這些問題最終都面臨這些問題最終都面臨一個如何降低貨物運輸本錢的問題一個如何降低貨物運輸本錢的問題. 該問題可用下面的該問題可用下面的方式加以描畫方式加以描畫: 問題問題 設(shè)有某種物資設(shè)有某種物資, 該物資共有該物資共有 個產(chǎn)地個產(chǎn)地, 產(chǎn)地產(chǎn)地 的產(chǎn)量的產(chǎn)量miA的需求量為的需求量為 且產(chǎn)量和需求量為相等且產(chǎn)量和需求量為相等. ,1,2,jbjn

2、分析分析 一個適宜的運輸方案即是要確定從第一個適宜的運輸方案即是要確定從第 個產(chǎn)地個產(chǎn)地i,1,2,iaimjBn為為 該物資另有該物資另有 個銷售點個銷售點, 銷售點銷售點iAjB,ijc從產(chǎn)地從產(chǎn)地 到銷售點到銷售點 的單位運輸本錢為的單位運輸本錢為 求一個運輸求一個運輸方案方案, 使總運輸費用為最小使總運輸費用為最小.jjB,ijx到第到第 個需求點個需求點 的物資供應(yīng)量的物資供應(yīng)量. 假設(shè)供應(yīng)量為假設(shè)供應(yīng)量為 那那么么問題的約束條件為問題的約束條件為0.1,2,;1,2,ijxim jn1, 1,2,.nijijxaim1, 1,2, .mijjixbjns.t.而相應(yīng)的總運輸本錢為而

3、相應(yīng)的總運輸本錢為.ijijzc x從而得到問題的數(shù)學(xué)模型從而得到問題的數(shù)學(xué)模型0.1,2,;1,2,ijxim jn1, 1,2,.nijijxaim1, 1,2, .mijjixbjns.t.min .ijijzc x例例1 試對下面的運輸問題建立相應(yīng)的數(shù)學(xué)模型試對下面的運輸問題建立相應(yīng)的數(shù)學(xué)模型.20055655030需求量需求量60158610408104121002012614產(chǎn)量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地1B2B3B4B1A2A3A解解 由前面的討論容易得到相應(yīng)的數(shù)學(xué)模型由前面的討論容易得到相應(yīng)的數(shù)學(xué)模型:1112131421min 146122012zxxxxx222324313233

4、344108106815,xxxxxxx111213142122232431323334100,40,60,xxxxxxxxxxxx11213112223230,50,xxxxxxs.t.13233314243465,55,xxxxxx0,1,2,3;1,2,3,4.ijxij注注: 前面所討論的是產(chǎn)銷平衡的運輸問題前面所討論的是產(chǎn)銷平衡的運輸問題. 假設(shè)產(chǎn)銷不假設(shè)產(chǎn)銷不平平0.1,2,;1,2,ijxim jn1, 1,2,.nijijxaim1, 1,2, .mijjixbjns.t.min .ijijzc x衡時衡時, 相應(yīng)的模型將分為產(chǎn)大于銷或銷大于產(chǎn)的運輸問相應(yīng)的模型將分為產(chǎn)大于銷或

5、銷大于產(chǎn)的運輸問題題. 當產(chǎn)大于銷時當產(chǎn)大于銷時, 那么問題的模型為那么問題的模型為:而當需求量大于供應(yīng)量時而當需求量大于供應(yīng)量時, 相應(yīng)的模型為相應(yīng)的模型為0.1,2,;1,2,ijxim jn1, 1,2,.nijijxaim1, 1,2, .mijjixbjns.t.min .ijijzc x二、表上作業(yè)法二、表上作業(yè)法 在上面的例中可以看到在上面的例中可以看到: 運輸問題的數(shù)學(xué)模型最終歸運輸問題的數(shù)學(xué)模型最終歸結(jié)為一個線性規(guī)劃的模型結(jié)為一個線性規(guī)劃的模型, 并可用相應(yīng)的解法加以求解并可用相應(yīng)的解法加以求解,但即使是一個簡單的運輸問題但即使是一個簡單的運輸問題, 涉及到的變量也是比較涉及

6、到的變量也是比較多的多的, 因此求解也較為困難因此求解也較為困難. 這里將引見一種新的解法這里將引見一種新的解法:表上作業(yè)法表上作業(yè)法. 表上作業(yè)法的求解步驟表上作業(yè)法的求解步驟: 求出一個初始可行解求出一個初始可行解; 斷定當前解能否為最優(yōu)解斷定當前解能否為最優(yōu)解; 解的調(diào)整解的調(diào)整. 求初始基可行解求初始基可行解 1.西北角法西北角法 用西北角法求運輸問題的初始解的要點是用西北角法求運輸問題的初始解的要點是: 從西北角從西北角開場按最大能夠進展分配開場按最大能夠進展分配, 直到完成一切分配直到完成一切分配.例例2 用西北角法求下面運輸問題的初始解用西北角法求下面運輸問題的初始解.銷地銷地產(chǎn)

7、地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200解解 由西北角法由西北角法, 首先分配首先分配 得得1121500,100,xx500100再對第二列及第三列進展分配再對第二列及第三列進展分配, 即有下表即有下表銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400100銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546

8、300需求量需求量600400200200500100400100100200最后對第三行進展分配最后對第三行進展分配, 得下表得下表,由此得初始解為由此得初始解為112122500,100,400,xxx233334100,100,200.xxx此時對應(yīng)的運輸本錢為此時對應(yīng)的運輸本錢為 6000.z 注注 1.用西北角法所得到問題的解與表中的單位運輸成用西北角法所得到問題的解與表中的單位運輸成2.在表格中在表格中, 凡填入數(shù)據(jù)的單元凡填入數(shù)據(jù)的單元 稱為基變量稱為基變量, 否那么否那么稱稱ijx3.基變量的個數(shù)應(yīng)基變量的個數(shù)應(yīng) 當?shù)仁讲怀闪r當?shù)仁讲怀闪r, 那么稱那么稱該該1,mn本無關(guān)本

9、無關(guān), 因此該解普通與最優(yōu)解的間隔較因此該解普通與最優(yōu)解的間隔較“遠遠;為非基變量為非基變量.解是退化的解是退化的. 對退化問題對退化問題, 需求虛擬基變量來補充基變量需求虛擬基變量來補充基變量的個數(shù)的個數(shù), 其取值為其取值為0.例例3 用西北角法求下面問題的初始解用西北角法求下面問題的初始解銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量385420解解 由西北角法由西北角法, 容易得到問題的初始解容易得到問題的初始解銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量3854203445411122233343,4,4

10、,5,4.xxxxx即即: 問題的初始解為問題的初始解為并留意到該解是退化的并留意到該解是退化的. 此時可令此時可令230 x來添加基變來添加基變 量的個數(shù)量的個數(shù). 2.最小元素法最小元素法 最小元素法的根本想法是最小元素法的根本想法是: 按最小本錢進展分配按最小本錢進展分配.例例4 用最小元素法求下面運輸問題的初始解用最小元素法求下面運輸問題的初始解.銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1327 765002752360031546300需求量需求量600400200200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200300

11、解解 由最小元素法由最小元素法, 最小本錢為最小本錢為 故故31300,x311,c剩下的最小本錢分別為剩下的最小本錢分別為12232,2,cc1223400,200,xx銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200300400200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200300400200最后有最后有112124100,200,200.xxx100200200由此得到問題的初始解由此得到問題的初始解111221100,400,200,xxx232

12、431200,200,300.xxx此時對應(yīng)的運輸本錢為此時對應(yīng)的運輸本錢為3800.z 例例5 用最小元素法求下面運輸問題的初始解用最小元素法求下面運輸問題的初始解.銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量385420解解 由最小元素法得由最小元素法得:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量385420314831即即: 初始解為初始解為1314212332344,3,3,1,8,1.xxxxxx 最優(yōu)解的斷定最優(yōu)解的斷定 為判別當前解能否為最優(yōu)解為判別當前解能否為最優(yōu)解, 需求建立相應(yīng)的位勢需求建

13、立相應(yīng)的位勢. ,.1,2,1,2,iju vim jn.ijijcuvijx 假設(shè)假設(shè) 為基變量為基變量, 那么有那么有因基變量的個數(shù)為因基變量的個數(shù)為 故令故令 由此得到一切由此得到一切1,mn10.u 為此定義位勢為此定義位勢 的位勢的位勢.例例6 求下面運輸問題的初始解所對應(yīng)的位勢求下面運輸問題的初始解所對應(yīng)的位勢.銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765001004002752360020020020031546300300需求量需求量600400200200解解 由位勢的定義由位勢的定義, 及及 是基變量是基變量, 11x10,u 1111,cuv由此得到由此得到 同樣有同樣有

14、13.v 1212,cuv得得 再由再由 及及 得得 同理同理22.v 2121cuv13,v 24.u 3432,1,2.vvu 即有下表即有下表:又又可得其它位勢可得其它位勢:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765001004002752360020020020031546300300需求量需求量60040020020010u 13v 22v 24u 32u 32v 41v 例例7 求下面運輸問題的初始解所對應(yīng)的位勢求下面運輸問題的初始解所對應(yīng)的位勢銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131074321928431374105981需求量需求量385420解解 由位勢的定義可分別得

15、到由位勢的定義可分別得到銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量38542031483110u 33v 410v 21u 12v 35u 29v 下面的例子闡明對退化問題的處置方式下面的例子闡明對退化問題的處置方式例例8 求下面運輸問題的初始解所對應(yīng)的位勢求下面運輸問題的初始解所對應(yīng)的位勢銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13113107342192844374105954需求量需求量385420解解 由位勢的定義可分別得到由位勢的定義可分別得到銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13113107342192844374105954需求量需求量38542

16、010u 211v 13v 22u 此時此時, 因基變量的個數(shù)因基變量的個數(shù)1.mn230,x計算下去計算下去. 為此為此, 虛擬基變量虛擬基變量勢勢:故位勢無法再繼續(xù)故位勢無法再繼續(xù)再進一步計算位再進一步計算位銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量131131072192843741059需求量需求量3854203445410u 211v 13v 22u 034v 36u 41v 由位勢由位勢, 再定義影響系數(shù)再定義影響系數(shù) 其定義關(guān)系為其定義關(guān)系為: 假設(shè)假設(shè) 為為,ijijx.ijijijcuv非基變量非基變量, 那么那么例例9 對下面問題求相應(yīng)的影響系數(shù)對下面問題求相應(yīng)的影響系數(shù).64513

17、2576723200200400600需求量需求量300360025001產(chǎn)量產(chǎn)量4321銷地銷地產(chǎn)地產(chǎn)地30040020010020020010u 13v 22v 24u 32u 32u 31u 解解 因因 為非基變量為非基變量, 由影響系數(shù)的定義由影響系數(shù)的定義, 有有13x13149,7,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量60040020020030040020010020020010u 13v 22v 24u 32u 32v 31v 971589 最優(yōu)解斷定方法最優(yōu)解斷定方法 當前解是最優(yōu)解當前解是最優(yōu)解0.ij 解的調(diào)整解的調(diào)

18、整 假設(shè)當前解不是最優(yōu)解假設(shè)當前解不是最優(yōu)解, 那么要進展適當?shù)慕獾恼{(diào)整那么要進展適當?shù)慕獾恼{(diào)整, 以以 1.確定進基變量確定進基變量 :stxmin0 .stijijij 2.對當前進基變量對當前進基變量 構(gòu)造一條閉回路構(gòu)造一條閉回路:,stx降低運輸費用降低運輸費用. 其詳細步驟為其詳細步驟為 閉回路閉回路: 從當前非基變量出發(fā)從當前非基變量出發(fā), 以直線方式向前后以直線方式向前后, 留意到在閉回路上留意到在閉回路上, 除出發(fā)頂點外除出發(fā)頂點外, 其他頂點均為基其他頂點均為基左左, 右前進右前進, 遇到某一個基變量變向遇到某一個基變量變向, 直到回到起點直到回到起點.變量頂點變量頂點.常見

19、的幾種閉回路方式常見的幾種閉回路方式 3.在閉回路上確定最大調(diào)整量在閉回路上確定最大調(diào)整量M. 首先在閉回路上給各頂點以編號首先在閉回路上給各頂點以編號: 出發(fā)頂點標號為出發(fā)頂點標號為0, 012345依次類推依次類推. 例如在下面的回路中例如在下面的回路中, 各個頂點的編號為各個頂點的編號為: 最大調(diào)整量最大調(diào)整量 閉回路上編號為奇數(shù)頂點的最小運輸閉回路上編號為奇數(shù)頂點的最小運輸M=012345150280200 例如在下面問題中例如在下面問題中, 那么最大調(diào)整量那么最大調(diào)整量M=150.量量. 4.求出新解求出新解 在閉回路上進展解的調(diào)整在閉回路上進展解的調(diào)整: 偶數(shù)頂點偶數(shù)頂點+ 奇數(shù)頂

20、點奇數(shù)頂點M,M. 由此得到求解運輸問題的詳細方法由此得到求解運輸問題的詳細方法: 1.求出問題的初始解普通用最小元素法求出問題的初始解普通用最小元素法; 2.求出位勢及影響系數(shù)求出位勢及影響系數(shù), 從而斷定能否為最優(yōu)解從而斷定能否為最優(yōu)解; 3.假設(shè)不是最優(yōu)解假設(shè)不是最優(yōu)解, 那么進展解的調(diào)整那么進展解的調(diào)整; 4.重新進展斷定重新進展斷定.例例10 求下面運輸問題的最小本錢解求下面運輸問題的最小本錢解銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200解解 由西北角法得到問題的初始解由西北角法得到問題的初始解:銷地銷地產(chǎn)地產(chǎn)地

21、1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400100100200再求出相應(yīng)的位勢及影響系數(shù)再求出相應(yīng)的位勢及影響系數(shù).銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量60040020020050010040010010020010u 13v 24u 21v 32v 36u 40v 1213141,9,6,2431321,8,2, 即有下表即有下表銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002005001004001

22、0010020010u 13v 24u 21v 32v 36u 40v 196182由于由于 是最小的負數(shù)是最小的負數(shù), 故以故以 為進基變量為進基變量, 構(gòu)構(gòu)318 31x3133232131,xxxxx即即造閉回路造閉回路: 銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量60040020020050010040010010020010u 13v 24u 21v 32v 36u 40v 196182由此得最大調(diào)整量由此得最大調(diào)整量 從而得到新解從而得到新解. 留意到該解留意到該解M100,210,x是退化的是退化的, 因此需求虛擬基變量因此需求虛

23、擬基變量: 令并進一步計令并進一步計算位勢和影響系數(shù)算位勢和影響系數(shù): 銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400100100200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002005001004002002000銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 24u 32u 32v 48v 21v 192968最小影響系數(shù)

24、為最小影響系數(shù)為249, 閉回路為閉回路為:2434312124,xxxxx最大調(diào)整量最大調(diào)整量 即有即有M0,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002005001004002002000銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002005001004002002000銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 25u 32u 37v 48

25、v 210v 802319最小影響系數(shù)為最小影響系數(shù)為128, 12222434311112,xxxxxxx構(gòu)造閉回路構(gòu)造閉回路:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 25u 32u 37v 48v 210v 802319最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解:M200,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002005001004002002000200200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1

26、32765003002002752360020020020031546300300需求量需求量600400200200再一次計算位勢和影響系數(shù)再一次計算位勢和影響系數(shù), 得得銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量60040020020030030020020020020010u 13v 23u 32u 31v 40v 22v 865718由于由于 故當前解為最優(yōu)解故當前解為最優(yōu)解, 最優(yōu)解值最優(yōu)解值0,ij3600.ijijzc x注注 由于在上題的解題中的初始解是經(jīng)過西北角法得到由于在上題的解題中的初始解是經(jīng)過西北角法得到的的, 因此求解

27、過程比較煩瑣因此求解過程比較煩瑣. 下面我們用最小元素法求下面我們用最小元素法求解該問題解該問題.例例11 求下面問題的最小本錢解求下面問題的最小本錢解銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200解解 由最小元素法得問題的初始解由最小元素法得問題的初始解銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200300400200100200200進一步求出位勢及影響系數(shù)進一步求出位勢及影響系數(shù):銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13276500275236003154

28、6300需求量需求量60040020020030040020010020020010u 13v 22v 24u 32u 32v 41v 971589最小影響系數(shù)為最小影響系數(shù)為 閉回路為閉回路為221, 2221111222,xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解:M200,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量600400200200300400200100200200200銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量132765002752360031546300需求量需求量6004002002003003002002002002

29、00留意到該解即為用西北角法求解過程中所得到的最優(yōu)解留意到該解即為用西北角法求解過程中所得到的最優(yōu)解. 此例闡明用最小元素法所得到的初始解普通情況下比此例闡明用最小元素法所得到的初始解普通情況下比用西北角法得到的初始解更為優(yōu)越用西北角法得到的初始解更為優(yōu)越.例例12 求下面運輸問題的最小本錢解求下面運輸問題的最小本錢解.銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量137641522432123438513需求量需求量111010940銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量137641522432123438513需求量需求量111010940解解 由最小元素法得到問題的初始解由最小元素法得到問題的初始解:111

30、78103對此初始解對此初始解, 再求相應(yīng)的位勢和影響系數(shù)再求相應(yīng)的位勢和影響系數(shù):銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764157822432121113438513103需求量需求量11101094010u 36v 44v 22u 32u 14v 21v 165121最小影響系數(shù)最小影響系數(shù)312, 31331314242131,xxxxxxx即有下表即有下表:閉回路為閉回路為銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764157822432121113438513103需求量需求量11101094010u 36v 44v 22u 32u 14v 21v 165121最大調(diào)整量為最大調(diào)整量為 由

31、此得到新解由此得到新解M3,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764157822432121113438513103需求量需求量1110109403310358344234825410673409101011需求量需求量133122151產(chǎn)量產(chǎn)量4321銷地銷地產(chǎn)地產(chǎn)地計算相應(yīng)的位勢及影響系數(shù)計算相應(yīng)的位勢及影響系數(shù):銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764151052243212843438513310需求量需求量11101094010u 36v 44v 22u 30u 14v 23v 143112最小影響系數(shù)最小影響系數(shù) 取取 為進基變量為進基變量, 那么閉那么閉回回11231, 23

32、x2324141323,xxxxxM4,最大調(diào)整量為最大調(diào)整量為 由此得到新解由此得到新解:路為路為銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764151052243212843438513310需求量需求量1110109404銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1376415692243212843438513310需求量需求量111010940再計算位勢及影響系數(shù)再計算位勢及影響系數(shù):銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1376415692243212843438513310需求量需求量11101094010u 36v 44v 23u 31u 15v 24v 232313最小影響系數(shù)最小影響系數(shù) 取取

33、為進基變量為進基變量, 那么閉回路那么閉回路為為112, 11x1113232111,xxxxxM6,最大調(diào)整量為最大調(diào)整量為銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1376415692243212843438513310需求量需求量1110109406銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764156922432122103438513310需求量需求量111010940進一步計算位勢和影響系數(shù)進一步計算位勢和影響系數(shù)銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764156922432122103438513310需求量需求量11101094010u 34v 44v 21u 31u 13v 22v 30315

34、2最小影響系數(shù)最小影響系數(shù) 回路回路241, 2414112124,xxxxx最大調(diào)整量為最大調(diào)整量為 從而得到新解從而得到新解:M2,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764156922432122103438513310需求量需求量1110109402銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764158722432121023438513310需求量需求量111010940計算位勢和影響系數(shù)計算位勢和影響系數(shù), 得得銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量13764158722432121023438513310需求量需求量11101094010u 13v 44v 22u 35v 22v 31u 5

35、11420因因 故當前解為最優(yōu)解故當前解為最優(yōu)解, 且最小本錢為且最小本錢為 0,ij128.z 例例13 求解下面的運輸問題求解下面的運輸問題:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128251357395285需求量需求量549220解解 由最小元素法得初始解由最小元素法得初始解:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128251357395285需求量需求量549220453512計算位勢計算位勢, 得得銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128512251357433952855需求量需求量54922010u 13v 37v 412v 24u 35u 25v 1631151此時

36、最小影響系數(shù)此時最小影響系數(shù) 回路為回路為243, 2423131424,xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解M2,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128512251357433952855需求量需求量549220銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128512251357433952855需求量需求量5492202銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513574123952855需求量需求量549220再計算位勢和影響系數(shù)再計算位勢和影響系數(shù), 得得銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513574123952855需求量需求量5

37、4922010u 13v 37v 49v 24u 35u 25v 1631154此時最小影響系數(shù)此時最小影響系數(shù) 回路為回路為121, 1213232212,xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解M3,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513574123952855需求量需求量549220銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513574123952855需求量需求量5492203銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513571423952855需求量需求量549220再計算位勢和影響系數(shù)再計算位勢和影響系數(shù), 得得銷地銷地產(chǎn)地

38、產(chǎn)地1234產(chǎn)量產(chǎn)量1347128532513571423952855需求量需求量54922010u 13v 36v 48v 23u 34u 24v 5410541因因 故當前解為最優(yōu)解故當前解為最優(yōu)解, 且最小本錢為且最小本錢為 0,ij60z 三、幾類特殊的運輸問題三、幾類特殊的運輸問題 在前面所討論的是產(chǎn)銷平衡的運輸問題在前面所討論的是產(chǎn)銷平衡的運輸問題, 實踐任務(wù)中實踐任務(wù)中遇到的更多的是產(chǎn)銷不平衡的運輸問題遇到的更多的是產(chǎn)銷不平衡的運輸問題. 由于在處置中由于在處置中是把產(chǎn)銷不平衡的運輸問題化為產(chǎn)銷平衡的運輸問題加是把產(chǎn)銷不平衡的運輸問題化為產(chǎn)銷平衡的運輸問題加以處理以處理, 故本段

39、中我們將其歸為特殊的運輸問題來處理故本段中我們將其歸為特殊的運輸問題來處理. 1.產(chǎn)銷不平衡的運輸問題產(chǎn)銷不平衡的運輸問題 產(chǎn)大于銷的運輸問題產(chǎn)大于銷的運輸問題 設(shè)運輸問題中設(shè)運輸問題中, 產(chǎn)量總和大于需求量的總和產(chǎn)量總和大于需求量的總和, 即有即有11.mnijijab為此為此, 虛擬需求點虛擬需求點 需求量為需求量為1,nB111.mnnijijbab運輸本錢均為運輸本錢均為 從而將問題轉(zhuǎn)化為產(chǎn)銷平衡從而將問題轉(zhuǎn)化為產(chǎn)銷平衡,10.i nc的問題的問題.銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1295352461015需求量需求量1510155040例例14 求解運輸問題求解運輸問題解解 虛擬第四個

40、需求點虛擬第四個需求點, 由此得下表由此得下表銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量129503524610015需求量需求量1510151050由最小元素法由最小元素法, 容易得到問題的初始解容易得到問題的初始解:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量129503524610015需求量需求量1510151050計算位勢和影響系數(shù)得計算位勢和影響系數(shù)得:101015105銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量129503515101024610015105需求量需求量151015105010u 25u 12v 21v 35v 40v 835最小影響系數(shù)最小影響系數(shù) 回路回路245, 2414132324,xx

41、xxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解M5,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量129503515101024610015105需求量需求地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量12950351515524610015105需求量需求量1510151050相應(yīng)的位勢和影響系數(shù)為相應(yīng)的位勢和影響系數(shù)為銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量12950351515524610015105需求量需求量151015105010u 12v 26v 35v 40v 20u 325因因 故當前解為最優(yōu)解故當前解為最優(yōu)解, 且最小本錢為且最小本錢為 0,ij165.z 銷大于產(chǎn)的運輸問題銷大

42、于產(chǎn)的運輸問題11.nmjijiba為此為此, 虛擬產(chǎn)地虛擬產(chǎn)地 產(chǎn)量為產(chǎn)量為1,mA111.nmmjijiaba 設(shè)運輸問題中設(shè)運輸問題中, 需求量總和大于產(chǎn)量的總和需求量總和大于產(chǎn)量的總和, 即有即有運輸本錢均為運輸本錢均為1,M.mjc的問題的問題.從而將問題轉(zhuǎn)化為產(chǎn)銷平衡從而將問題轉(zhuǎn)化為產(chǎn)銷平衡例例15 求下面運輸問題的最小費用解求下面運輸問題的最小費用解.銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量18561202151012803391080需求量需求量1407090 280300解解 由前面討論由前面討論, 虛擬產(chǎn)地虛擬產(chǎn)地 產(chǎn)量為產(chǎn)量為4,A3341120.jijiaba那么有下表那么有下表

43、:銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300由最小元素法得問題的初始解由最小元素法得問題的初始解, 并計算位勢和影響系數(shù)并計算位勢和影響系數(shù)銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 208070504040銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 2080705010u 19v 25v 36v 26u 36u 114040101049uM43最小影響系數(shù)最小影

44、響系數(shù) 回路回路111, 1113232111,xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解M40,銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1856120407010215101280803391080804MMM2020需求量需求量1407090300銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1856120407010215101280803391080804MMM2020需求量需求量140709030010u 18v 26u 35u 25v 36v 119948uM32最小影響系數(shù)最小影響系數(shù) 回路回路221, 2223131222.xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解:M70,

45、銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1856120408021510128070103391080804MMM2020需求量需求量1407090300銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1856120408021510128070103391080804MMM2020需求量需求量140709030010u 18v 26u 35u 24v 36v 1109148uM42因因 故當前解為最優(yōu)解故當前解為最優(yōu)解, 且最小本錢為且最小本錢為 0,ij1860.z 注注: 在上題中在上題中, 假設(shè)先分配假設(shè)先分配4220,x由此得到初始解由此得到初始解:銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量1856120507021510

46、128060203391080804MMM2020需求量需求量1407090300再計算相應(yīng)的位勢再計算相應(yīng)的位勢, 有有銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v 36v 26u 36u 112060101045uM41最小影響系數(shù)為最小影響系數(shù)為414, 閉回路為閉回路為41421213232141,xxxxxxx銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v

47、36v 26u 36u 112060101045uM41此時最大調(diào)整量為此時最大調(diào)整量為20, 繼續(xù)迭代繼續(xù)迭代, 所得到的解即為前面所得到的解即為前面解法中的初始解解法中的初始解.銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v 36v 26u 36u 112060101045uM41銷地銷地產(chǎn)地產(chǎn)地123產(chǎn)量產(chǎn)量185612021510128033910804MMM20需求量需求量1407090300 208070504040 2.存在無通行路的運輸問題存在無通行路的運輸問題 所

48、謂存在無通行路的運輸問題是指在一個運輸問題中所謂存在無通行路的運輸問題是指在一個運輸問題中, 分析分析: 對所給條件對所給條件, 為使為使 不能成為基變量不能成為基變量, 可使相可使相ijxiAjB產(chǎn)地產(chǎn)地 與需求點與需求點 之間不存在相應(yīng)的運輸線路之間不存在相應(yīng)的運輸線路. 在此種在此種情況下情況下, 求運輸方案求運輸方案.,ijcM應(yīng)的運輸本錢為最大的應(yīng)的運輸本錢為最大的. 為此可設(shè)為此可設(shè) 再由前面所再由前面所提供的方法求出最優(yōu)解提供的方法求出最優(yōu)解.例例16 求解下面的運輸問題求解下面的運輸問題:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量17654502973650387350需求量需求量204

49、03060150銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1765450297365038M7350需求量需求量20403060150解解 由最小元素法得初始解由最小元素法得初始解5010304020留意到該解是退化的留意到該解是退化的, 故需虛擬基變量故需虛擬基變量. 但基變量需在但基變量需在求位勢的過程中加以處理求位勢的過程中加以處理. 先求位勢先求位勢:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量176545040102973650203038M735050需求量需求量2040306015010u 26v 44v 31u 此時此時, 位勢計算中斷位勢計算中斷, 問題在于初始解退化問題在于初始解退化. 為此為此

50、, 虛擬虛擬220,x基變量基變量, 令令 那么有那么有銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量1765450401029736502003038M735050需求量需求量2040306015010u 26v 44v 31u 21u 18v 32v 13116此時最小影響系數(shù)此時最小影響系數(shù) 回路為回路為111, 1112222111,xxxxx最大調(diào)整量最大調(diào)整量 由此得到新解由此得到新解M20,銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量產(chǎn)量17654502020102973650203038M735050需求量需求量20403060150計算位勢和影響系數(shù)后得計算位勢和影響系數(shù)后得:銷地銷地產(chǎn)地產(chǎn)地1234產(chǎn)量

51、產(chǎn)量17654502020102973650203038M735050需求量需求量2040306015010u 26v 44v 31u 21u 17v 32v 31261因因 故當前解為最優(yōu)解故當前解為最優(yōu)解, 且最小本錢為且最小本錢為 0,ij680.z 例例17 有三個化肥廠供應(yīng)四個地域農(nóng)用化肥有三個化肥廠供應(yīng)四個地域農(nóng)用化肥. 假設(shè)等量假設(shè)等量的化肥在這些地域運用效果一樣的化肥在這些地域運用效果一樣. 各化肥廠的年產(chǎn)量各化肥廠的年產(chǎn)量, 各各地域的需求量和各廠到各地的單位運價如下表所示地域的需求量和各廠到各地的單位運價如下表所示, 求求總運費最省的調(diào)運方案總運費最省的調(diào)運方案.不限不限3

52、07050最高需求最高需求1007030最低需求最低需求50_23201936015191314250172213161產(chǎn)量產(chǎn)量4321 地域地域化肥廠化肥廠解解 此為產(chǎn)銷不平衡的運輸問題此為產(chǎn)銷不平衡的運輸問題. 總產(chǎn)量為總產(chǎn)量為160, 四個地域的最低需求量為四個地域的最低需求量為110, 最高需最高需求量可以設(shè)為求量可以設(shè)為210. 因此是需求量大于產(chǎn)量的問題因此是需求量大于產(chǎn)量的問題. 為此為此虛設(shè)工廠虛設(shè)工廠. 再留意到各地域的需求量分為兩部分再留意到各地域的需求量分為兩部分, 一部分一部分是必需滿足的是必需滿足的, 另一部分是可以不滿足的另一部分是可以不滿足的. 由此產(chǎn)生表由此產(chǎn)生

53、表格格.0M0M0MMM23201919151519171722131613141416210501030702030504503602501443211 留意對表中第四行中單位本錢的了解留意對表中第四行中單位本錢的了解. 由最小元素法得到問題的初始解由最小元素法得到問題的初始解:11234411616132217175050214141319151560301020319192023MM501010304M0M0M050302030207030105021011234411616132217175050214141319151560301020319192023MM501010304M0M0

54、M050302030207030105021010u 213v 114v 35vM20u 114v 35u 45vM45vM45uM再計算相應(yīng)的影響系數(shù)再計算相應(yīng)的影響系數(shù):111113142,2,27,22,MM1423242422,24,20,MMM3132330,5,13,M 414142219,19,225,MMM430.此時此時 為進基變量為進基變量, 由此得新解由此得新解33x11234411616132217175050214141319151560301020319192023MM501030104M0M0M3005020302070301050210再一次計算位勢和影響系數(shù)有

55、再一次計算位勢和影響系數(shù)有11234411616132217175050214141319151560301020319192023MM501010304M0M0M050302030207030105021010u 213v 114v 35vM20u 114v 35u 45vM45vM45uM再計算相應(yīng)的影響系數(shù)再計算相應(yīng)的影響系數(shù)111113142,2,17,12,MM1423242412,14,10,MMM3132331,2,23,M 414142219,19,225,MMM40.j以以 為進基變量為進基變量, 那么有新解那么有新解24x11234411616132217175050214

56、141319151560302010319192023MM5020304M0M0M0503020302070301050210經(jīng)過數(shù)次換基后得到問題的最優(yōu)解經(jīng)過數(shù)次換基后得到問題的最優(yōu)解:122224315,20,40,50.xxxx 4.具有中轉(zhuǎn)站的運輸問題具有中轉(zhuǎn)站的運輸問題 某類物資有某類物資有 個產(chǎn)地個產(chǎn)地, 產(chǎn)地產(chǎn)地 的產(chǎn)地為的產(chǎn)地為m,iaiA對該類物對該類物資有資有 個需求點個需求點, 第第 個需求點的需求量為個需求點的需求量為nj.jb 從產(chǎn)地到達需求點都需經(jīng)過從產(chǎn)地到達需求點都需經(jīng)過 個中轉(zhuǎn)站中的某個中轉(zhuǎn)個中轉(zhuǎn)站中的某個中轉(zhuǎn)p站站. 啟動第啟動第 個中轉(zhuǎn)站將發(fā)生固定費用個中轉(zhuǎn)

57、站將發(fā)生固定費用k,kf相應(yīng)的單位相應(yīng)的單位費用分別為費用分別為,.ikkjcd 求運輸方案求運輸方案, 使總運費為最小使總運費為最小.中轉(zhuǎn)站的最大轉(zhuǎn)運量為中轉(zhuǎn)站的最大轉(zhuǎn)運量為.kc 引入引入 變量變量 0 1,1kkxx ,ikkjxy表示啟用第表示啟用第 個中轉(zhuǎn)站個中轉(zhuǎn)站,k表示經(jīng)過從表示經(jīng)過從 個產(chǎn)地到第個產(chǎn)地到第 個中轉(zhuǎn)站及從第個中轉(zhuǎn)站及從第 個中轉(zhuǎn)站到個中轉(zhuǎn)站到ikk第第 個需求點的運輸量個需求點的運輸量, 那么問題的目的函數(shù)為那么問題的目的函數(shù)為j11111,pppmnkkikikkjkjkikkjzf xc xd y產(chǎn)量限制產(chǎn)量限制:1,1,2,pikikxaim1,1,2,mi

58、kkkixc xkp 中轉(zhuǎn)站才干限制中轉(zhuǎn)站才干限制:需求量限制：需求量限制：1,1,2,pkjjkybjn 供需平衡限制供需平衡限制:11.1,2,mnikkjijxykp 由此得到該問題的數(shù)學(xué)模型由此得到該問題的數(shù)學(xué)模型:11111min,pppmnkkikikkjkjkikkjzf xc xd y11111,1,2,1,2,1,2,.1,2,pikikmikkkipkjjkmnikkjijxaimxc xkpybjnxykp01,1,2,0,0.kikkjxkpxy四、指派問題四、指派問題 1.指派問題的數(shù)學(xué)模型指派問題的數(shù)學(xué)模型 問題問題 設(shè)有設(shè)有 項任務(wù)項任務(wù), 交給交給 個人去完成個

59、人去完成. 每個人只能每個人只能nn 如此的問題即稱為指派問題如此的問題即稱為指派問題.完成其中的一項完成其中的一項. 又每人完成其中任何一項任務(wù)的代價又每人完成其中任何一項任務(wù)的代價為知為知, 求這樣的義務(wù)分配方案求這樣的義務(wù)分配方案, 使完成這些任務(wù)的總使完成這些任務(wù)的總代價為最小代價為最小. 以以 表示第表示第 人完成第人完成第 項任務(wù)所需的代價項任務(wù)所需的代價, 由此得由此得ijcij111212122212.nnnnnnccccccCccc 如此的矩陣稱為指派問題中的代價矩陣如此的矩陣稱為指派問題中的代價矩陣.到矩陣到矩陣: 引入決策變量引入決策變量 :ijx10ijx第第 人完成第

60、人完成第 項任務(wù)項任務(wù);ij第第 項任務(wù)由其他人完成項任務(wù)由其他人完成.j由此得到矩陣由此得到矩陣 留意到留意到: 由于每項任務(wù)只能由由于每項任務(wù)只能由.ijXx一人完成及每人只能完成一項任務(wù)一人完成及每人只能完成一項任務(wù), 故在矩陣中每行和故在矩陣中每行和每列只能有一個每列只能有一個1, 其他均為其他均為0. 如此的矩陣稱為指派問題中的指派矩陣如此的矩陣稱為指派問題中的指派矩陣.例例17 設(shè)指派問題中的代價矩陣為設(shè)指派問題中的代價矩陣為151812111316109,131710811 1889C那么以下矩陣那么以下矩陣 121000010001001000,0010000100010010