運籌學_運輸問題.ppt

《運籌學_運輸問題.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第五章運輸問題運輸問題模型表上作業(yè)法運輸問題擴展例1.某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往個銷地每件物品的運費如下表所示，問：應如何調(diào)運可使總運輸費用最小？引例B1B2B3產(chǎn)量A1646200A2655300銷量150150200銷地產(chǎn)地解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：Minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+

2、x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3)構建數(shù)學模型：線性規(guī)劃模型B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200500銷地產(chǎn)地運輸問題的一般形式假設某種物品有m個產(chǎn)地，用Ai來表示(i=1,…,m)，各地的產(chǎn)量分別為ai(i=1,…,m)，有n個銷地，用Bj來表示(j=1,…,n)，各地的銷量分別為bj(j=1,…,n)，從產(chǎn)地Ai到銷地Bj運輸一個單位物資的運價為Cij，問該如何調(diào)運物品使總運費最?。窟\輸問題的一般模型ai——產(chǎn)地i的產(chǎn)量，bj——銷地j的銷量。(4)s.t

3、.產(chǎn)銷平衡運輸問題的模型(5)s.t.產(chǎn)銷平衡運輸問題數(shù)學模型的特點：產(chǎn)量總和等于銷量總和。約束條件系數(shù)矩陣的元素等于0或1。約束條件系數(shù)矩陣的每一列有兩個1其余都等于0，即每一個變量xij在前m個約束方程中出現(xiàn)1次，在后n個約束方程中出現(xiàn)1次。所有的約束都是等式約束。11‥‥‥111‥‥‥111‥‥‥1‥‥‥11‥‥‥1111111111111‥‥‥‥‥‥1111x11x12‥‥x1nx21x22‥‥x2nx31x32‥‥x3n‥‥‥xm1xm2‥‥xmnm行n行(m+n)×mn系數(shù)矩陣AA的m+n-1階方陣是非奇異的將A的第m行去掉，然后選取下列變量對應

4、的列向量，構成一個m+n-1階子方陣可以證明：(1)運輸問題一定有有限的最優(yōu)解；為什么？？？(2)運輸問題任意m+n-1個約束都是線性獨立的，即基可行解應有m+n-1個基變量(a)運輸問題目標函數(shù)有下界，目標函數(shù)值不會趨于負無窮大；(b)令可以驗證上述解為運輸問題的一個可行解，因此運輸問題存在上界。因而，運輸問題一定存在有限個最優(yōu)解。運輸問題可行解的表示：m個產(chǎn)地、n個銷地的運輸問題，除了滿足可行的條件外，任何一個基要滿足以下條件：基變量的個數(shù)為m+n-1即m+n-1個格的運輸量不為0(實格)，(m-1)(n-1)個格的運輸量為0(空格)?；兞坎荒苄纬砷]回

5、路運輸表：運輸問題表上作業(yè)法就是基于運輸表來展開。銷地產(chǎn)地基可行解在運輸表中的表示B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4123B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4123B1B2B3B4A1A2A3B1B2B3B4A1A2A3運輸表中同行同列組成回路的變量表上作業(yè)法運輸問題的求解方法：(1)單純形法：把運輸問題作為標準的線性規(guī)劃問題來處理，用一般單純形法來求解。缺點：變量較多，計算時間較長。(2)表上作業(yè)法：根據(jù)運輸問題約束系數(shù)

6、矩陣和目標函數(shù)構成的特殊性來求解問題。表上作業(yè)法運輸問題的求解方法：表上作業(yè)法基于運輸表來求解運輸問題銷地產(chǎn)地表上作業(yè)法表上作業(yè)法(其實質(zhì)是單純形法)該法分以下幾步進行：第一步：找初始基可行解求出初始基可行解。即在m×n產(chǎn)銷平衡運輸表上給出m+n-1個數(shù)字格(基變量)，其它為空格(非基變量)且使基變量對應的系數(shù)列向量線性無關；第二步：解的最優(yōu)性檢驗求出各非基變量的檢驗數(shù)，判斷是否最優(yōu)，如果是則停止計算，如果不是轉下一步；第三步：解的改進確定換入換出變量，找出新的基可行解(即調(diào)整運輸方案)；重復第二步和第三步直到找到最優(yōu)解為止。第一步：初始基可

7、行解的確定方法1：最小元素法方法2：西北角法方法3：沃格爾法方法1：最小元素法1.相應的在運輸表上對應位置標記出運輸量。相應的在運輸表上劃去不需要再考慮的產(chǎn)地。相應的在運輸表上劃去不需要再考慮的銷地。2.在余下的供銷關系(尚未劃去的表格)中，繼續(xù)按照上面的方法安排調(diào)運，直至安排完所有的供銷任務，得到一個完整的調(diào)運方案為止。按照費用矩陣元素cij增加順序逐個選擇引入基本解的變量xij，非退化情況下，每選擇1個，就必然排除1個產(chǎn)地或銷地，最后一步可一次排除1個產(chǎn)地和1個銷地，這樣便可得到一個初始基礎可行解(m+n-1個基變量)。填有數(shù)字的表格對應的為基變量。對于

8、非基變量對應的表格(空格)，不填入數(shù)字。例1：某部門