【正文】 運輸問題 ?運輸問題及其數(shù)學模型 ?運輸問題的表上作業(yè)法 ?運輸問題的進一步討論 例 1：某部門有 3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由 4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為 t）以及各工廠到各銷售點的單位運價（元 /t）示于下表中 要求研究產(chǎn)品如何調(diào)運才能使總運費最小 運輸問題及其數(shù)學模型 單位 銷地 運價 產(chǎn)地 產(chǎn)量 2 9 10 2 9 1 3 4 2 5 8 4 2 5 7 銷量 3 8 4 6 4321 BBBB321AAAA2 A3 B2 A1 B3 B4 B1 s2=5 s3=7 d1=3 d2=8 d3=4 d4=6 s1=9 供應量 供應地 運價 需求量 需求地 2 9 10 2 1 3 4 2 8 4 2 5 運輸問題網(wǎng)絡圖 ????????????????????????????????????????????????????),(06483759524824371092m i n342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約束條件：目標函數(shù)：為運量設產(chǎn)量約束 銷量約束 運輸問題的一般提法是：設某種物資有 個產(chǎn)地 m ,1A ,2A ,?,mA各產(chǎn)地的產(chǎn)量是 。,21 maaa ?有 個銷地 ,1B ,2B ,? ,nBn各銷地的銷量是 .,21 nbbb ?假定從產(chǎn)地 ),2,1( miAi ??到銷地 ),2,1( njB j ??運輸單位物品的運價是 ，問 ijc怎樣調(diào)運這些物品才能使總運費最小？ 銷地 產(chǎn)地 產(chǎn) 量 銷 量 1A2AmA1B 2B nB??11c 12c nc111x 12xnx121c 22c nc221x 22x nx21mc 2mc mnc1mx2mx mnx??1b 2b nb1a2ama運價表 ) ( ??????????? ? ??? ?? ?0m i n1 1ijjijijiijminjijijxbabxaxxcZ當產(chǎn)銷平衡時，其模型如下： 0 , 0 , 0i j ija b c? ? ?假 設 ：當產(chǎn)大于銷時，其模型是： ) ( ??????????? ? ??? ?? ?0m i n1 1ijjijijiijminjijijxbabxaxxcZ當產(chǎn)小于銷時，其模型是： m i n ( )0i j i ji j ii j j i jijZ c xxax b a bx?? ?????????????? ? ? 平衡運輸問題必有可行解，也必有最優(yōu)解； 運輸問題數(shù)學模型的特點 證明 記 .1 1dbaminjji ??? ?? ?則令 dbax jiij ?),2,1。,2,1( njmi ?? ??則 為運輸問題的一個可行解。事實上： ijx?? ??? ????njijinjnjjiij abdadbax11 1),2,1( mi ???? ??? ????mijijmimijiij badbdbax11 1),2,1( nj ??又因 .0,0 ??ji ba所以 .0?ijx故 是一組可行解。 []ijx又因為總費用不會為負值（存在下界）。這說明，運輸問題既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。 運輸問題約束條件的系數(shù)矩陣 運輸問題數(shù)學模型的特點 對運輸問題數(shù)學模型的結構約束加以整理，可知其系數(shù)矩陣具有下述形式： ????????????????????????????????111111111111111111???????????? m行 n行 1．運輸問題是一個具有 m n個變量和 n+m個等型約束的線性規(guī)劃問題。 （ 4－ 1） mnmmnn xxxxxxxxx ??????? ,,,。, 212222111211jmiij eep ??? ),2,1。,2,1( njmi ?? ??( ) 1 ( ) 1 ( ) 10 0 01 1 00 0 01 0 10 0 0ij i m jm n m n m np e e?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?2． 運輸問題約束方程組的系數(shù)矩陣是一個只有 0和 1兩個數(shù)值的稀疏矩陣 ,其中 1的總數(shù)為 2 m n 個 。 約束條件系數(shù)矩陣的 每一列有兩個非零元素， 這對應于每一個變量在前 m個約束方程中出現(xiàn)一次，在后 n個約束方程中也出現(xiàn)一次 約束條件系數(shù)矩陣的秩是 m+n1。即運輸問題的基變量總數(shù)是 m+n1 證明：因 A的前 m行對應元素的和與后 n行對應元素的和相等， 恰好都是： nmE ?? )1,1,1(1 ?所以 A的行向量是線性相關 的。從而 r(A)≤m+n. 去掉 A的第一行，并取如下 m+n1列，得到 m+n1階子式 11 12 1 21 31 1||0 0 0 1 0 00 0 0 0 1 00 0 0 0 0 1101 0 0 1 1 10 1 0 0 0 00 0 1 0 0 0nmD p p p p p p? ? ? ? ? ??? ? ? ?所以 r(A)=m+n1. 對于產(chǎn)銷平衡運輸問題，除了上述特點外，還有以下特點： 1 所有結構約束條件都是等式約束 2 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和 運輸問題的解 運輸問題數(shù)學模型的特點 運輸問題是一種線性規(guī)劃問題。前面講述的單純形法是求解線性規(guī)劃問題十分有效的一般方法，因而可用單純形法求解運輸問題。 但是當用單純形法求解運輸問題時，先得在每個約束條件中引入一個人工變量，這樣一來，即使對于 m= n=4這樣簡單的運輸問題，變量數(shù)目也會達到 19個之多。 因此，我們利用運輸問題數(shù)學模型的特點，引入了 表上作業(yè)法 來求解運輸問題 用表上作業(yè)法求解運輸問題 表上作業(yè)法的基本思想： 先設法給出一個初始方案 ,然后根據(jù)確定的判別準則對初始方案進行檢查、調(diào)整、改進，直至求出最優(yōu)方案，如下圖所示。 初始化 最優(yōu)性檢驗 迭代 （ Iteration） 最優(yōu)？ yes STOP no 這和單純形法的求解思想完全一致，但是具體的作法則更加簡捷。 例 1 某部門有 3個同類型的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由 4個 銷售點出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單 位為 t）以及各工廠到銷售點的單位運價（元 /t）示于表 42 中，問如何調(diào)運才能使總運費最小？ 銷地 產(chǎn)地 產(chǎn) 量 4 12 4 11 16 2 10 3 9 10 8 5 11 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 42 11x 12x13x 14x21x 22x 23x 24x31x 32x 33x 34x34333231242322213141141312116115893102114124m i nxxxxxxxxxxxxxczi jijij????????????? ? ?? ?????????????????????????????????????????4,3,2,1。3,2,1,01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxx