運籌學(xué)課件第3章運輸問題-第1，2節(jié)-資料下載頁
2025-10-07 13:00本頁面
【正文】 0 =4 ( 5+9) 10 12=10 ( 5+3) 5 0=5 ( 5+10) 5 v j 2 9 3 10 表 318 中還有負(fù)檢驗數(shù)。說明未得最優(yōu)解，還可以改進(jìn)。 改進(jìn)的方法 —— 閉回路調(diào)整法 ? 當(dāng)在表中空格處出現(xiàn)負(fù)檢驗數(shù)時 ， 表明未得最優(yōu)解 。 若有兩個和兩個以上的負(fù)檢驗數(shù)時 ，一般選其中最小的負(fù)檢驗數(shù) ， 以它對應(yīng)的空格為調(diào)入格 。 即以它對應(yīng)的非基變量為換入變量 。 由表 318得 (2， 4)為調(diào)入格 。 以此格為出發(fā)點 ， 作一閉回路 ， 如表 319所示 。 表 319 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 4(+1) 1( 1) 3( 1) (+1) 3 7 4 9 銷量 3 6 5 6 (2， 4)格的調(diào)入量 θ 是選擇閉回路上具有 (1)的數(shù)字格中的最小者。即 θ =min(1,3)=1(其原理與單純形法中按θ 規(guī)劃來確定換出變量相同 )。然后按閉回路上的正、負(fù)號，加入和減去此值，得到調(diào)整方案，如表 320所示。 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 對表 320給出的解，再用閉回路法或位勢法求各空格的檢驗數(shù)，見表 321。表中的所有檢驗數(shù)都非負(fù)，故表 320中的解為最優(yōu)解。這時得到的總運費最小是 85元。 銷地 加工廠 B 1 B 2 B 3 B 4 A 1 A 2 A 3 0 9 2 2 1 12 表上作業(yè)法計算中的問題 ? 1. 無窮多最優(yōu)解 ? 2. 退化 1. 無窮多最優(yōu)解 ? 在本章 ， 產(chǎn)銷平衡的運輸問題必定存在最優(yōu)解 。 那么有唯一最優(yōu)解還是無窮多最優(yōu)解 ? 判別依據(jù)與第 1章 。 即某個非基變量 (空格 )的檢驗數(shù)為 0時 ， 該問題有無窮多最優(yōu)解 。 表 321空格 (1， 1)的檢驗數(shù)是 0，表明例 1有無窮多最優(yōu)解 。 可在表 320中以 (1，1)為調(diào)入格 ， 作閉回路 (1， 1)+(1， 4)(2， 4)+(2， 1)(1， 1)+。 確定 θ =min(2,3)=2。 經(jīng)調(diào)整后得到另一最優(yōu)解 ，見表 322。 表 322 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 2 1 6 5 3 3 7 4 9 銷量 3 6 5 6 2. 退化 用表上作業(yè)法求解運輸問題當(dāng)出現(xiàn)退化時，在相應(yīng)的格中一定要填一個 0，以表示此格為數(shù)字格。有以下兩種情況： ? (1) 當(dāng)確定初始解的各供需關(guān)系時，若在 (i,j)格填入某數(shù)字后，出現(xiàn) Ai處的余量等于 Bj處的需量。這時在產(chǎn)銷平衡表上填一個數(shù)，而在單位運價表上相應(yīng)地要劃去一行和一列。為了使在產(chǎn)銷平衡表上有(m+n1)個數(shù)字格。這時需要添一個 “ 0”。它的位置可在對應(yīng)同時劃去的那行或那列的任一空格處。如表 323，表 324所示。因第一次劃去第一列，剩下最小元素為 2，其對應(yīng)的銷地 B2，需要量為 6，而對應(yīng)的產(chǎn)地 A3未分配量也是 6。這時在產(chǎn)銷表 (3， 2)交叉格中填入 6，這時在單位運價表 324中需同時劃去B2列和 A3行。在表 323的空格 (1， 2)， (2， 2)， (3，3)， (3， 4)中任選一格添加一個 0。 表 323 ，表 324 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 7 4 9 銷量 3 6 5 6 銷地 加工廠 B 1 B 2 B 3 B 4 A 1 A 2 A 3 3 1 7 11 9 4 3 2 10 10 8 5 ? (2) 在用閉回路法調(diào)整時 ， 在閉回路上出現(xiàn)兩個和兩個以上的具有 (1)標(biāo)記的相等的最小值 。 這時只能選擇其中一個作為調(diào)入格 。而經(jīng)調(diào)整后 ， 得到退化解 。 這時另一個數(shù)字格必須填入一個 0， 表明它是基變量 。 當(dāng)出現(xiàn)退化解后 ， 并作改進(jìn)調(diào)整時 ， 可能在某閉回路上有標(biāo)記為 (1)的取值為 0的數(shù)字格 ， 這時應(yīng)取調(diào)整量 θ =0。 第 1， 2節(jié)結(jié)束
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1