【正文】 由此得到新解 M 3,?銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 4 7 12 8 5 3 2 5 1 3 5 7 4 1 2 3 9 5 2 8 5 5 需求量 5 4 9 2 20 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 4 7 12 8 5 3 2 5 1 3 5 7 4 1 2 3 9 5 2 8 5 5 需求量 5 4 9 2 20 3 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 4 7 12 8 5 3 2 5 1 3 5 7 1 4 2 3 9 5 2 8 5 5 需求量 5 4 9 2 20 再計算位勢和影響系數(shù) , 得 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 4 7 12 8 5 3 2 5 1 3 5 7 1 4 2 3 9 5 2 8 5 5 需求量 5 4 9 2 20 1 0u ?1 3v ? 3 6v ? 4 8v ?2 3u ??3 4u ??2 4v ?5410 5 41因 故當(dāng)前解為最優(yōu)解 , 且最小成本為 0,ij? ?60z ?三、幾類特殊的運輸問題 在前面所討論的是產(chǎn)銷平衡的運輸問題 , 實際工作中 遇到的更多的是產(chǎn)銷不平衡的運輸問題 . 由于在處理中 是把產(chǎn)銷不平衡的運輸問題化為產(chǎn)銷平衡的運輸問題加 以解決 , 故本段中我們將其歸為特殊的運輸問題來解決 . ⑴ 產(chǎn)大于銷的運輸問題 設(shè)運輸問題中 , 產(chǎn)量總和大于需求量的總和 , 即有 11.mnijijab?????為此 , 虛擬需求點 需求量為 1,nB ?111.mnn i jijb a b???????運輸成本均為 從而將問題轉(zhuǎn)化為產(chǎn)銷平衡 ,1 ? ?的問題 . 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 2 9 5 35 2 4 6 10 15 需求量 15 10 15 50 40 例 14 求解運輸問題 解 虛擬第四個需求點 , 由此得下表 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 2 4 6 10 0 15 需求量 15 10 15 10 50 由最小元素法 , 容易得到問題的初始解 : 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 2 4 6 10 0 15 需求量 15 10 15 10 50 計算位勢和影響系數(shù)得 : 10 10 15 10 5 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 15 10 10 2 4 6 10 0 15 10 5 需求量 15 10 15 10 50 1 0u ?2 5u ?1 2v ? 2 1v ? 3 5v ? 4 0v ?83? 5?最小影響系數(shù) 回路 24 5,? ??2 4 1 4 1 3 2 3 2 4 ,x x x x x? ? ? ?最大調(diào)整量 由此得到新解 M 5,?銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 15 10 10 2 4 6 10 0 15 10 5 需求量 15 10 15 10 50 5 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 15 15 5 2 4 6 10 0 15 10 5 需求量 15 10 15 10 50 相應(yīng)的位勢和影響系數(shù)為 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 2 9 5 0 35 15 15 5 2 4 6 10 0 15 10 5 需求量 15 10 15 10 50 1 0u ?1 2v ? 2 6v ? 3 5v ? 4 0v ?2 0u ?32 5因 故當(dāng)前解為最優(yōu)解 , 且最小成本為 0,ij? ? ? ⑵ 銷大于產(chǎn)的運輸問題 11.nmjijiba?????為此 , 虛擬產(chǎn)地 產(chǎn)量為 1,mA ?111.nmm j ijia b a??????? 設(shè)運輸問題中 , 需求量總和大于產(chǎn)量的總和 , 即有 運輸成本均為 1, ? ?的問題 . 從而將問題轉(zhuǎn)化為產(chǎn)銷平衡 例 15 求下面運輸問題的最小費用解 . 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 需求量 140 70 90 280 300 解 由前面討論 , 虛擬產(chǎn)地 產(chǎn)量為 4,A334112 0 .jijia b a??? ? ???則有下表 : 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 由最小元素法得問題的初始解 , 并計算位勢和影響系數(shù) 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 70 50 40 40 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 70 50 1 0u ?1 9v ? 2 5v ? 3 6v ?2 6u ?3 6u ??1?1? 40 40 10 104 9uM?? 4 3最小影響系數(shù) 回路 11 1,? ??1 1 1 3 2 3 2 1 1 1 ,x x x x x? ? ? ?最大調(diào)整量 由此得到新解 M 40,?銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 40 70 10 2 15 10 12 80 80 3 3 9 10 80 80 4 M M M 20 20 需求量 140 70 90 300 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 40 70 10 2 15 10 12 80 80 3 3 9 10 80 80 4 M M M 20 20 需求量 140 70 90 300 1 0u ?1 8v ?2 6u ?3 5u ??2 5v ? 3 6v ?1?19 94 8uM?? 3 2最小影響系數(shù) 回路 22 1,? ??2 2 2 3 1 3 1 2 2 2 .x x x x x? ? ? ?最大調(diào)整量 由此得到新解 : M 70,?銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 40 80 2 15 10 12 80 70 10 3 3 9 10 80 80 4 M M M 20 20 需求量 140 70 90 300 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 40 80 2 15 10 12 80 70 10 3 3 9 10 80 80 4 M M M 20 20 需求量 140 70 90 300 1 0u ?1 8v ?2 6u ?3 5u ??2 4v ? 3 6v ?110 914 8uM?? 4 2因 故當(dāng)前解為最優(yōu)解 , 且最小成本為 0,ij? ? ? 注 : 在上題中 , 若先分配 42 2 0 ,x ?由此得到初始解 : 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 50 70 2 15 10 12 80 60 20 3 3 9 10 80 80 4 M M M 20 20 需求量 140 70 90 300 再計算相應(yīng)的位勢 , 有 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 50 70 1 0u ?1 9v ? 2 5v ? 3 6v ?2 6u ?3 6u ??1?1? 20 60 10 104 5uM?? 4? 1?最小影響系數(shù)為 41 4,? ??閉回路為 4 1 4 2 1 2 1 3 2 3 2 1 4 1 ,x x x x x x x? ? ? ? ? ?銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 50 70 1 0u ?1 9v ? 2 5v ? 3 6v ?2 6u ?3 6u ??1?1? 20 60 10 104 5uM?? 4? 1?此時最大調(diào)整量為 20, 繼續(xù)迭代 , 所得到的解即為前面 解法中的初始解 . 銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 50 70 1 0u ?1 9v ? 2 5v ? 3 6v ?2 6u ?3 6u ??1?1? 20 60 10 104 5uM?? 4? 1?銷地 產(chǎn)地 1 2 3 產(chǎn)量 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 4 M M M 20 需求量 140 70 90 300 20 80 70 50 40 40 所謂存在無通行路的運輸問題是指在一個運輸問題中 , 分析 : 對所給條件 , 為使 不能成為基變量 , 可使相 ijxiA jB產(chǎn)地 與需求點 之間不存在相應(yīng)的運輸線路 . 在此種 情況下 , 求運輸方案 . ,ijcM?應(yīng)的運輸成本為最大的 . 為此可設(shè) 再由前面所 提供的方法求出最優(yōu)解 . 例 16 求解下面的運輸問題 : 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 7 6 5 4 50 2 9 7 3 6 50 3 8 — 7 3 50 需求量 20 40 30 60 150 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 7 6 5 4 50 2 9 7 3 6 50 3 8 M 7 3 50 需求量 20 40 30 60 150 解 由最小元素法得初始解 50 10 30 40 20 注意到該解是退化的 , 故需虛擬基變量 . 但基變量需在 求位勢的過程中加以解決 . 先求位勢 : 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 7 6 5 4 50 40 10 2 9 7 3 6 50 20 30 3 8 M 7 3 50 50 需求量 20 40 30 60 150 1 0u ?2 6v ? 4 4v ?3 1u ??此時 , 位勢計算中斷 , 問題在于初始解退化 . 為此 , 虛擬 22 0,x ?基變量 , 令 則有 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 7 6 5 4 50 40 10 2 9 7 3 6 50 20 0 30 3 8 M 7 3 50 50 需求量 20 40 30 60 150 1 0u ?2 6v ? 4 4v ?3 1u ??2 1u ?1 8v ? 3 2v ?1? 311 6此時最小影響系數(shù) 回路為 11 1,? ??1 1 1 2 2 2 2 1 1 1 ,x x x x x? ? ? ?最大調(diào)整量 由此得到新解 M 20,?銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 7 6 5 4 50 20 20 10 2 9 7 3 6 50 20 30 3 8 M 7 3 50 50 需求量 20 40 30 60 150 計算位勢和影響