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