1、運輸問題第三章 運輸問題前言n前兩章討論了一般線性規劃問題的求解方法。但在實際工作中，往往碰到一些特殊的線性規劃問題，它們的約束方程的系數具有特殊的結構，這樣就有可能找到比單純形法更為簡單的求解方法。本章所討論的運輸問題就屬于這樣一類問題。第一節 運輸問題 及其數學模型 運輸問題是一類特殊的線性規劃問題，本節介紹運輸問題的數學模型及其約束方程組的系數矩陣結構的特殊性。運輸問題n典型背景物資運輸調度問題 一般提法為：設某種物品有: m個產地： 產量： n個銷地： 銷量： 從產地 到銷地 的單位運價是 。 求總運費最小的調度方案。mAAA,21nBBB,21maaa,21nbbb,21iAjBij

2、c運輸問題n決策變量 表示由 到 的物品數量。iAjBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121銷地產地銷量產量運輸問題n產銷平衡問題總產量=總銷量 即n產銷不平衡問題總產量=總銷量nijmiiba11運輸問題 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111產銷平衡問題的數學模型運輸問題約束條件（不包括非負約束）均為等式；產量之和=銷量之和；約束條件的獨立方程最多有m+n-1個。（約束條件中，前m行

3、相加之和減去后n行相加之和結果是零向量，說明mn個行向量線性相關。可以證明，mn個約束方程中的任意mn1個方程都是線型無關的。非零變量的個數不大于獨立的約束方程的個數，從而在運輸表上填有數字的格子數不大于m+n-1個。）第二節 運輸問題的 表上作業法 由上節介紹運輸問題的數學模型及其約束方程組的系數矩陣結構的特殊性，本節將由此給出運輸問題的比單純形法更為簡便的求解方法表上作業法。運輸問題表上作業法n表上作業法是單純形法在求解運輸問題的一種簡便方法。n單純形法與表上作業法的關系：（1）找出初始基可行解 （2）求各非基變量的檢驗數（3）判斷是否最優解計算表中空格檢驗數表上給出m+n-1個數字格判斷

4、方法相同運輸問題表上作業法換基：（4）確定換入變量和換出變量找出新的基可行解。（5）重復（2）、（3）直至求出最優解。表上調整（閉回路調整）（運輸問題必有最優解）停止最優解？是否運輸問題表上作業法舉例說明表上作業法例1、某部門三個工廠生產同一產品的產量、 四個銷售點的銷量及單位運價如下表：41228543961111104814121482210163214321AAABBBB銷量產量銷地產地運輸問題表上作業法 按單位運價的大小決定供應的先后，優先滿足單位運價最小者的供銷要求。 即從單價中最小運價確定供應量，逐步次小，直至得到m+n-1個數字格。 運輸問題表上作業法最小元素法舉例4122854

5、3961111104814121482210163214321AAABBBB銷量產量銷地產地822010100614868000060運輸問題表上作業法最小元素法舉例41228543961111104814121482210163214321AAABBBB銷量產量銷地產地821014682466811632410514280z運輸問題表上作業法 罰數（即差額）=次小運價-最小運價罰數（或差額）的解釋：;差額大，則不按最小運費調運，運費增加大。差額大，則不按最小運費調運，運費增加大。;差額小，則不按最小運費調運，運費增加不大。差額小，則不按最小運費調運，運費增加不大。對差額最大處，采用最小運費調

6、運。伏格爾法思路：運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數04-4=0第一次第一次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數013-2=1第一次第一次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地

7、產地產地行罰數011第一次第一次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數011 列 罰 數4-2=22153第一次第一次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數011 列 罰 數21531480優先安排銷地優先安排銷地 ，否則運，否則運價會更高價會更高2B下次不考慮該列第一次第一次運輸問題表上作業法第二次第二次n結

8、合例結合例1說明這種方法。說明這種方法。行罰數012 列 罰 數213優先安排銷地 ，否則運價會更高4B81234123161022814121448BBBBAAA4122854396111110銷量產量銷地銷地產地產地148006下次不考慮該行運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。行罰數01 列 罰 數21284814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地148006下次不考慮該列802第三次第三次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。行罰數76 列 罰 數1284814121

9、482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地1480068024120下次不考慮該列第四次第四次運輸問題表上作業法n結合例結合例1說明這種方法。說明這種方法。行罰數00 列 罰 數24284814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地1480068024120000第五次第五次運輸問題表上作業法n例1用伏格爾法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地4814812224468514

10、9228114412 z目標函數值目標函數值用最小元素法求出的目標函數z=246運輸問題表上作業法第二步：解的最優性檢驗n閉回路法 思路：計算空格（非基變量）的檢驗數 24242121121211110 xxxxzz0112412110, 1zzxxx若令則如何求檢驗數？分析：運費的增量即 增加1個單位 的檢驗數=相應的運費增量11x11x運輸問題表上作業法41228543961111104814121482210163214321AAABBBB銷量產量銷地產地821014682460z從初始表分析：要保證產銷平衡，則1, 12344110zz111121231311xxxx 稱為閉回路 21

11、231311xxxx+1-1+1-1運輸問題表上作業法41228543961111104814121482210163214321AAABBBB銷量產量銷地產地821014682561112121561143102221運輸問題表上作業法檢驗數表41228543961111104814121482210163214321AAABBBB銷量產量銷地產地82101468211-11012,0124表中的解不是最優解。運輸問題表上作業法第三步：解的調整 調整位置（2，4）非空，回路角上的格至少一個為空，且保證數字的非負性。41228543961111104814121482210163214321AAABBBB銷量產量銷地產地82101468-1（-2）（-2）（+2）（+2）運輸問題表上作業法n調整后的解為：41228543961111104814121482210163214321AAABBBB銷量產量銷地產地82121448220911222462446892114412514