【文章內(nèi)容簡(jiǎn)介】 1 3 8 5 9 75 A2 2 9 4 8 60 A3 6 3 7 5 60 銷(xiāo)量 35 40 55 65 195（平衡） 西北角法： 35 [ ] [ ] 40 [ ] [ ] 0 [ ] 55 [ ] 5 60 Page 49 of 9 B1 B2 B3 B4 產(chǎn)量 A1 3 35 8 40 5 [ ] 9 [ ] 75 A2 2 [ ] 9 0 4 55 8 5 60 A3 6 [ ] 3 [ ] 7 [ ] 5 60 60 銷(xiāo)量 35 40 55 65 195（平衡） 西北角法 Page 50 of 9 例，用最小元素法 B1 B2 B3 B4 產(chǎn)量 A1 3 8 5 9 75 A2 2 6 4 8 90 A3 6 5 7 5 30 銷(xiāo)量 35 40 55 65 195（平衡） Page 51 of 9 B1 B2 B3 B4 產(chǎn)量 A1 3 8 5 9 75 A2 2 6 4 8 90 A3 6 5 7 5 30 銷(xiāo)量 35 40 55 65 195（平衡） 35 [ ] [ ] 55 [ ] [ ] 0 30 45 Page 52 of 9 B1 B2 B3 B4 產(chǎn)量 A1 3 [ ] 8 10 5 [ ] 9 65 75 A2 2 35 6 0 4 55 8 [ ] 90 A3 6 [ ] 5 30 7 [ ] 5 [ ] 30 銷(xiāo)量 35 40 55 65 195（平衡） Page 53 of 9 53 由于目標(biāo)要求極小 ， 因此 ， 當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu) ， 需要進(jìn)行調(diào)整 。 下面介紹兩種求檢驗(yàn)數(shù)的方法 : 閉回路法 和 位勢(shì)法 二、基本可行解的最優(yōu)性檢驗(yàn) Page 54 of 9 54 為了方便 ， 我們以表 1給出的初始基本可行解方案為例 ， 考察初始方案的任意一個(gè)非基變量 ， 比如 x24。 根據(jù)初始方案 ，產(chǎn)地 A2 的產(chǎn)品是不運(yùn)往銷(xiāo)地 B4 的 。 如果現(xiàn)在改變初始方案 ， 把 A2 的產(chǎn)品運(yùn)送 1 個(gè)單位給 B4 ， 那么為了保持產(chǎn)銷(xiāo)平衡 ，就必須使 x14 或 x34 減少 1 個(gè)單位；而如果 x14 減少 1 個(gè)單位 ， 第 1 行的運(yùn)輸量就必須增加 1 個(gè)單位 ， 例如 x13 增加 1 個(gè)單位 ， 那么為了保持產(chǎn)銷(xiāo)平衡 ， 就必須使 x23 減少 1 個(gè)單位 。 閉回路法 Page 55 of 9 55 這個(gè)過(guò)程就是尋找一個(gè)以非基變量 x24 為起始頂點(diǎn)的閉回路 —— {x24 ， x14 ，x13 ， x23 }， 這個(gè)閉回路的其他頂點(diǎn)均為基變量 (對(duì)應(yīng)著填上數(shù)字的格 )。 容易計(jì)算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 – 10 + 3 – 2 ＝ 1 ， 即總的運(yùn)費(fèi)減少 1 個(gè)單位 ， 這就說(shuō)明原始方案不是最優(yōu)方案 ， 可以進(jìn)行調(diào)整以得到更好的方案 。 Page 56 of 9 56 可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此， 對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。 表 410中用虛線(xiàn)畫(huà)出以非基變量 x22 為起始頂點(diǎn)的閉回路 。 Page 57 of 9 57 表 410 以非基變量 x22 為起始頂點(diǎn)的閉回路 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 3 [ ] 11 [ ] 3 4 10 3 7 1 3 9 [ ] 2 1 8 [ ] 4 7 [ ] 4 6 10 [ ] 5 3 9 銷(xiāo)量 3 6 5 6 20(產(chǎn)銷(xiāo)平衡 ) A1 A2 A3 1 2 1 Page 58 of 9 58 可以計(jì)算出以非基變量 x22 為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 9 – 2 + 3 – 10 + 5 – 4 ＝ 1 即總的運(yùn)費(fèi)增加 1 個(gè)單位 ， 這就說(shuō)明這個(gè)調(diào)整不能改善目標(biāo)值 。 從上面的討論可以看出 ， 當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí) ， 有若干個(gè)基變量的取值受其影響 。 Page 59 of 9 59 這樣 ， 利用單位產(chǎn)品變化 （ 運(yùn)輸?shù)膯挝毁M(fèi)用 ） 可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響 ， 其作用與線(xiàn)性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同 。 故也稱(chēng)這個(gè)綜合影響為該非基變量對(duì)應(yīng)的 檢驗(yàn)數(shù) 。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 ?24 = 1， ?22 = 1。 閉回路方法原理就是通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)數(shù) 。 Page 60 of 9 60 如果規(guī)定作為起始頂點(diǎn)的非基變量為第 1 個(gè)頂點(diǎn) ， 閉回路的其他頂點(diǎn)依次為第 2 個(gè)頂點(diǎn) 、 第 3 個(gè)頂點(diǎn) …… 那么就有 ?ij = (閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和 ) (閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和 ) 其中 ij 為非基變量的下角指標(biāo) 。 Page 61 of 9 61 按上述作法 ， 可計(jì)算出表 1的所有非基變量的檢驗(yàn)數(shù) ， 把它們填入相應(yīng)位置的方括號(hào)內(nèi) ，如圖 411所示 。 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 [1] 11 [2] 3 4 10 3 7 A2 1 3 9 [1] 2 1 8 [1] 4 A3 7 [10] 4 6 10 [12] 5 3 9 銷(xiāo)量 3 6 5 6 20(產(chǎn)銷(xiāo)平衡 ) 表 411 初始基本可行解及檢驗(yàn)數(shù) Page 62 of 9 62 閉回路法的 主要缺點(diǎn) 是：當(dāng)變量個(gè)數(shù)較多時(shí) ， 尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難 。 位勢(shì)：設(shè)對(duì)應(yīng) 基變量 xij 的 m +n 1 個(gè) cij ，存在 ui ,vj 滿(mǎn)足 ui+vj=cij ， i=1,2 … ,m 。 j=1,2 … ,n . 稱(chēng)這些 ui , vj 為該基本可行解對(duì)應(yīng)的位勢(shì) 。 Page 64 of 9 64 由于有 m + n 個(gè)變量 （ ui , vj ）， m + n 1 個(gè)方程（基變量個(gè)數(shù)）， 故有一個(gè)自由變量，位勢(shì)不唯一 。 利用位勢(shì)求檢驗(yàn)數(shù)： ?ij = cij ui vj i = 1, … , m 。 j = 1, … , n Page 65 of 9 65 前例，位勢(shì)法求檢驗(yàn)數(shù)： step 1 從任意基變量對(duì)應(yīng)的 cij 開(kāi)始 ,任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 個(gè) ui , vj 從 c14 = 10 開(kāi)始 step 2 計(jì)算非基變量的檢驗(yàn)數(shù) ?ij = cij ui vj ；填入圓圈內(nèi) Page 66 of 9 66 vj ui B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷(xiāo)量 3 6 5 6 [ ] [ ] [ ] [ ] [ ] [ ] 4 3 1 3 6 3 5 5 2 4 3 0 4 1 2 1 1 10 12 令 u1=5 Page 67 of 9 67 vj ui B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷(xiāo)量 3 6 5 6 [ ] [ ] [ ] [ ] [ ] [ ] 4 3 1 3 6 3 10 0 3 1 2 5 9 1 2 1 1 10 12 令 u1=0時(shí)，所以任選 u1對(duì)檢驗(yàn)數(shù)沒(méi)影響 Page 68 of 9 68 當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí) ，則表明當(dāng)前的基本可行解不是最優(yōu)解 。在這種情況下 ， 應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整 ， 即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降 ， 這一過(guò)程通常稱(chēng)為 換基(或主元變換 )過(guò)程 。 三 、 求新的基本可行解 Page 69 of 9 69 （ 1） 選負(fù)檢驗(yàn)數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量（上頁(yè)圖中 x24 ） 。 （ 2） 以 xrk 為起點(diǎn)找一條閉回路，除 xrk 外其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回路） 。 在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程是如下進(jìn)行： Page 70 of 9 70 （ 3） 為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)， xrk 為 1，沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號(hào)； （ 4） 求 ? =Min{xij?xij對(duì)應(yīng)閉回路上的偶數(shù)標(biāo)號(hào)格 }= xpq 那么 確定 xpq為出基變量，?為調(diào)整量； Page 71 of 9 71 （ 5） 對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào)整為： xij + ?，對(duì)各偶標(biāo)號(hào)頂點(diǎn) 調(diào)整為： xij ?，特別 xpq ? = 0， xpq變?yōu)榉腔兞俊?