【正文】 4 運(yùn)輸問題的表上作業(yè)法 最優(yōu)方案 最小費(fèi)用為 85百元。 167。 如在本題中給出的最優(yōu)運(yùn)輸方案中 x11的檢驗(yàn)數(shù)為 0，可知此運(yùn)輸問題有多個(gè)最優(yōu)解。 167。 4 運(yùn)輸問題的表上作業(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 所有非基變量檢驗(yàn)數(shù)都大于等于零，基變量的檢驗(yàn)數(shù)等于零，此解釋最優(yōu)解。 4 運(yùn)輸問題的表上作業(yè)法 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 3 7 A2 3 1 4 A3 6 3 9 銷量 3 6 5 6 x24=min(3,1)=1 (+1) (1) (1) (+1) 167。 167。 4 運(yùn)輸問題的表上作業(yè)法 三、改進(jìn)運(yùn)輸方案的辦法 — 閉回路調(diào)整法 ?調(diào)整判別準(zhǔn)則：存在檢驗(yàn)數(shù)小于零 ?調(diào)整方法：選取 所有負(fù)檢驗(yàn)數(shù)最小的非基變量 作為入基變量 ?在以 x24為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)的頂點(diǎn)的調(diào)運(yùn)量： x14=3， x23=1， x24=min(3,1)=1。 167。 ?數(shù)值由 基變量 xij 的檢驗(yàn)數(shù) λij = cij?ui?vj = 0 決定。 4 運(yùn)輸問題的表上作業(yè)法 尋找非基變量 x11的檢驗(yàn)數(shù)： 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 4 3 7 A2 3 1 1 2 4 A3 9 銷量 3 6 5 6 非基變量 x11 ① x11調(diào)運(yùn)量增加 1t，運(yùn)費(fèi)增加 3百元 保持 A1產(chǎn)量平衡， x13減少 1t，運(yùn)費(fèi)減少 3百元 保持 B3銷量平衡， x23增加 1t，運(yùn)費(fèi)增加 2百元 保持 A2與 B1平衡， x21減少 1t，運(yùn)費(fèi)減少 1百元 調(diào)整后運(yùn)費(fèi)增加33+21=1百元 167。 ? 檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解。 ? 非基變量檢驗(yàn)數(shù)：調(diào)整運(yùn)輸方案引起費(fèi)用的變化。 一個(gè)空格存在唯一的閉回路 167。 167。這樣可以保證填過數(shù)或零的格為 m+n1個(gè)，即保證基變量的個(gè)數(shù)為 m+n1個(gè)。 4 運(yùn)輸問題的表上作業(yè)法 在求初始基本可行解時(shí)要注意的兩個(gè)問題： ? xij的值之后，會(huì)出現(xiàn) Ai的產(chǎn)量與 Bj的銷量都改為零的情況，這時(shí)只能劃去 Ai行或 Bj列，但不能同時(shí)劃去 Ai行與 Bj列。 ?對(duì)單位運(yùn)價(jià)最小的變量分配運(yùn)輸量 ?使運(yùn)輸量最大 ?至少使一產(chǎn)地或銷地的剩余量為 0 167。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運(yùn)價(jià)要少。在表上找到單位運(yùn)價(jià)最小的 x21，并使 x21取盡可能大的值，即 x21=min(4,3)=3,把 A2的產(chǎn)量改為 1， B1的銷量改為 0，并把 B1列劃去。 4 運(yùn)輸問題的表上作業(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。同理可得余下的初始基本可行解。 4 運(yùn)輸問題的表上作業(yè)法 1. 西北角法 先 從表的左上角（即西北角）的變量 x11開始分配運(yùn)輸量， 并使 x11取盡可能大的值，即 x11=min(7,3)=3,則 x21與 x31必為零。 4 運(yùn)輸問題的表上作業(yè)法 一、確定初始基本可行解 為了把初始基本可行解與運(yùn)價(jià)區(qū)分開，我們把 運(yùn)價(jià) 放在每一欄的 右上角 ，每一欄的 中間 寫上 初始基本可行解 （調(diào)運(yùn)量）。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？ 167。 4 運(yùn)輸問題的表上作業(yè)法 基本可行解 （ m+n1個(gè)基變量 ） 非基變量檢驗(yàn)數(shù) 檢驗(yàn)數(shù)大于等于 0 唯一最優(yōu)解 閉回路法調(diào)整方案 是 否 計(jì)算過程（假設(shè)產(chǎn)銷平衡） 非基變量檢驗(yàn)數(shù)等于 0 多個(gè)最優(yōu)解 否 167。 運(yùn)輸問題都存在最優(yōu)解 。 3 運(yùn)輸問題的應(yīng)用 產(chǎn)地直接運(yùn)輸至銷地的最小費(fèi)用： 85百元 運(yùn)輸問題的計(jì)算機(jī)求解 運(yùn)輸問題的應(yīng)用 運(yùn)輸問題的表上作業(yè)法 本章內(nèi)容 4 1 2 3 167。 3 運(yùn)輸問題的應(yīng)用 應(yīng)用軟件計(jì)算，最優(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） Ai： 產(chǎn)量為 20+原產(chǎn)量，銷量為 20； Ti：產(chǎn)量、銷量均為 20； Bi：產(chǎn)量為 20，銷量為 20 +原銷量，其中 20 為各點(diǎn)可能變化的最大流量。 3 運(yùn)輸問題的應(yīng)用 解：轉(zhuǎn)化為一般運(yùn)輸問題 （ 1）把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站同時(shí)看作產(chǎn)地和銷地。 167。 銷地 運(yùn)費(fèi)單價(jià) /百元 產(chǎn)地 B1