【正文】 （規(guī)模效益） ?由上表可知： C、 D、 F港口有多余船只可供調出，而 A、 B、 E港口則需要調入空船。又知各城市之間的航行天數(shù)，假定船只型號相同，裝卸貨時間各一天，問該公司至少要配備多少條船才能滿足需要？ 航線 起點 終點 每天航班數(shù) 1 2 3 4 E B A D D C F B 3 2 1 1 城市之間航行天數(shù)表 Cij A B C D E F A B C D E F 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 問題分析 問題要求的是在保證需要的前提下，至少需多少船只。 ? 處理辦法：設想一個虛擬煤礦 D，生產 50萬噸，但這個產量只能供應可有可無的最高需求部分，于是各地的需求也應分為兩個部分：基本需求、機動需求 ? 虛擬產量的運輸費用為零，但它對于基本需求來講，運費為無窮大。 由此可以看出閉回路的幾何特點： 1. 閉回路都是一條封閉折線，每個頂點格子都是轉角點 2. 每一行或每一列只有且僅有兩個頂點格子 3. 每兩個頂點格子的連線都是水平的或垂直的。 3 運輸問題的進一步討論 一、產銷不平衡運輸問題 對產銷不平衡問題，可轉化為平衡問題，然后按表上作業(yè) 法求解。此時只能取一個離基，其余的仍作為 基格。 ijx例如：下表給出一個 3 4運輸?shù)倪\價及發(fā)送量與需求量。即發(fā)點的當前發(fā)送量已全部用完，而收 點的需求量已全部滿足。表上作業(yè)法計算中的兩個問題 ⒈ 無窮多個最優(yōu)解 若在最優(yōu)解中，某個非基變量的檢驗數(shù)為零，則該問題有 無窮多個最優(yōu)解 此時得到一個最優(yōu)解： ,1213 ?x ,414 ?x ,821 ?x ,224 ?x,1432 ?x ,834 ?x 其余變量全等于零。 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 iujv104?10392jiij vuc ??行位勢 列位勢 設 u1=1 當然，也可用采用解方程組的辦法來求位勢： 1314212332344112356uvuvuvuvuvuv???????? ???????? ???????兩種方法任選一種 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 iujv104?103921 21 1?10 12)( jiijij vuc ????三。 ji vu ,有基變量所對應的檢驗數(shù)為零，可從 m+n1個等式 0)( ??? jiij vuc （ ） 解出所有的行位勢、列位勢。 規(guī)定：起始頂點的空格為第一頂點，則 =閉回路上奇數(shù)次頂點運價之和 — 閉回路上偶數(shù)次頂點運價之和 ij? 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 143241323211111 ????????? cccc?1 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 21165121434321212 ????????? cccc?21 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 13411651023131434322222 ????????????? cccccc?121 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 1341192313142424 ?????????? cccc?1?121 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 10611432834141323213131 ????????????? cccccc?102111? 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 124116111314343333 ????????? cccc?12101?121 銷地 產地 產 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 1 21 1?10 12檢驗數(shù)中有負數(shù)，說明原方案不是最優(yōu)解。 1 閉回路法 (Cycle method) 2 對偶變量法（ dual variable method）也稱為位勢法 ⒈ 閉回路法（ cycle method) 下面用最小元素法所確定的初始基本可行解來說明。 總運費為（目標函數(shù)值） ? ?? ??3141i jijij xcz2 4 4685149228114412 ?????????????此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為 6 （等于 m+n1=3+41=6). 比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標函數(shù)值最小，最小元素法次之，西北角法解的目標函數(shù)值最大。但是，有時按某一最小單位運價安排物品調運時，卻可能導致不得不采用運費很高的其他供銷點，從而使整個運輸費用增加。 銷地 產地 產 量 4 12 4 11 16 10 3 9 8 5 11 6 22 銷 量 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 ① 228810 銷地 產地 產 量 4 12 4 11 16 2 10 9 10 8 5 11 6 22 銷 量 8 14 14 48 1A2A1B 2B 3B 4B3A表 32 ① 3 ② 210128 銷地 產地 產 量 4 12 11 2 10 9 10 8 5 11 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 ① 3 ② 210416106③ 8 銷地 產地 產 量 4 12 11 8 2 10 9 10 8 11 6 銷 量 8 12 14 48 1A2A1B 2B 3B 4B3A表 32 ① 3 ② 210416106③ 5142214④ 8