【正文】 為了把初始基本可行解與運價區(qū)分開，我們把 運價 放在每一欄的 右上角 ，每一欄的 中間 寫上 初始基本可行解 （調(diào)運量）。在表上找到單位運價最小的 x21，并使 x21取盡可能大的值，即 x21=min(4,3)=3,把 A2的產(chǎn)量改為 1， B1的銷量改為 0，并把 B1列劃去。這樣可以保證填過數(shù)或零的格為 m+n1個，即保證基變量的個數(shù)為 m+n1個。 ? 檢驗數(shù)都大于等于零，則已求得最優(yōu)解。 4 運輸問題的表上作業(yè)法 三、改進(jìn)運輸方案的辦法 — 閉回路調(diào)整法 ?調(diào)整判別準(zhǔn)則：存在檢驗數(shù)小于零 ?調(diào)整方法：選取 所有負(fù)檢驗數(shù)最小的非基變量 作為入基變量 ?在以 x24為出發(fā)點的閉回路中，找出所有偶數(shù)的頂點的調(diào)運量： x14=3， x23=1， x24=min(3,1)=1。 167。 4 運輸問題的表上作業(yè)法 最優(yōu)方案 最小費用為 85百元。 4 運輸問題的表上作業(yè)法 銷地 產(chǎn)地 B1 B2 B3 B4 ui A1 3 11 5 3 2 10 A2 3 1 9 2 1 8 A3 7 6 4 10 3 5 vj 12 0 ② 2 5 3 9 3 10 令 u1=0 v3=c13? u1=30=3 令 λ13=0 令 λ14=0 v4=c14? u1=100=10 令 λ24=0 u2=c24? v4 =810=2 令 λ34=0 u3=c34? v4 =510=5 令 λ21=0 v1=c21 ? u2 =1(2)=3 令 λ32=0 v2=c32 ? u3 =4 (?5)=9 ① ⑨ λ11=c11? u1 ? v1 =3? 0? 3=0 λ12=c12 ? u1? v2= 11? 0?9=2 λ22=c22 ? u2 ? v2 =9 ?(?2) ?9=2 λ23= c23? u2? v3=2?(?2) ?3= 1 λ31= c31 ? u3? v1= 7?(?5) ?3=9 λ33 = c33 ? u3? v3 = 10?3 ?(?5)=12 ② 0 所有非基變量檢驗數(shù)都大于等于零，基變量的檢驗數(shù)等于零，此解釋最優(yōu)解。 167。 ? 非基變量檢驗數(shù)：調(diào)整運輸方案引起費用的變化。 4 運輸問題的表上作業(yè)法 在求初始基本可行解時要注意的兩個問題： ? xij的值之后，會出現(xiàn) Ai的產(chǎn)量與 Bj的銷量都改為零的情況，這時只能劃去 Ai行或 Bj列，但不能同時劃去 Ai行與 Bj列。 4 運輸問題的表上作業(yè)法 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 3 4 2 2 3 6 x11 =min (7,3) =3 x12 =min (4,6) =4 0 4 0 2 0 6 0 2 0 3 0 x22 =min (4,2) =2 x23 =min (2,5) =2 x33 =min (3,9) =3 x34 =min (6,6) =6 0 167。問該公司應(yīng)如何調(diào)運產(chǎn)品在滿足各銷點的需求量的前提下總運費最少？ 167。 3 運輸問題的應(yīng)用 應(yīng)用軟件計算，最優(yōu)解： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 銷量 20 20 3 17 20 20 20 20 20 20 20 6 3 14 23 6 20 26 5 20 25 6 20 26 27 24 29 20 20 20 20 20 20 20 20 240 20 20 7 13 20 167。 167。 3 運輸問題的應(yīng)用 騰飛公司運輸網(wǎng)絡(luò)圖 1 廣州 2 大連 3 上海 4 天津 5 南京 6 濟(jì)南 7 南昌 8 青島 2 3 3 1 4 2 6 3 6 4 4 6 5 600 400 200 150 350 300 供應(yīng)量 需求量 167。 銷地 運輸量 產(chǎn)地 I II III IV D 產(chǎn)量 I 10 15 0 25 II 0 5 30 35 III 25 5 30 IV 10 10 銷量 10 15 25 20 30 167。如果生產(chǎn)出來的柴油機當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費用 萬元。339。 3 運輸問題的應(yīng)用 例 7. 造船廠根據(jù)合同從當(dāng)年起連續(xù)三年末各提供五條規(guī)格型號相同的大型客貨輪。 銷地 運輸量 產(chǎn)地 I′ I″ II III IV′ IV″ 產(chǎn)量 A 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 銷量 30 20 70 30 10 50 210 210 167。 3 運輸問題的應(yīng)用 例 5. 設(shè)有 A、 B、 C 三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。供應(yīng)能力分別為 1 500 t、 4 000 t，運價如表所示。 2 運輸問題的計算機求解 解： 銷地 運費單價 /元 產(chǎn)地 B1 B2 B3 產(chǎn)量 /件 A1 6 4 6 300 A2 6 5 5 300 銷量 /件 150 150 200 600 0 0 100 B4 600 500 產(chǎn)銷平衡 運輸費用？ 增加一個虛設(shè)的銷地 B4，即增加一個倉庫進(jìn)行貨物存儲 增加一個虛設(shè)的銷地 B4 167。 1 , 2 , ,mni j i jijni j ijmi j jiijf c xx s i mx d j nx i m j n???????????????,≥ 0? ?1111m i ns . t . 1 , 2 ,1 , 2 ,1 , 2 , , 。 管理運籌學(xué) 第七章 運輸問題 運輸問題的計算機求解 運輸問題的應(yīng)用 運輸問題的表上作業(yè)法 本章內(nèi)容 1 2 3 4 167。 1 , 2 , ,mni j i jijni j ijmi j jiijf c xx s i mx d j nx i m j n???????????????,≥ 0? ?1111m i ns . t . 1 , 2 ,1 , 2 ,1 , 2 , , 。 2 運輸問題的計算機求解 例 2. 某公司從兩個產(chǎn)地 A A2 將物品運往三個銷地 BB B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各