【文章內(nèi)容簡(jiǎn)介】 與單純形方法中的原理相同 ， 即計(jì)算檢驗(yàn)數(shù) 。 由于目標(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) —表上作業(yè)法 41 閉回路法 為了方便 ， 我們以表 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è)單位 。 —表上作業(yè)法 42 這個(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)整以得到更好的方案 。 —表上作業(yè)法 43 可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此， 對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。 表 410中用虛線畫(huà)出以非基變量 x22 為起始頂點(diǎn)的閉回路 。 —表上作業(yè)法 44 表 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 45 可以計(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è)基變量的取值受其影響 。 —表上作業(yè)法 46 這樣 ， 利用單位產(chǎn)品變化 （ 運(yùn)輸?shù)膯挝毁M(fèi)用 ） 可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響 ， 其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同 。 故也稱這個(gè)綜合影響為該非基變量對(duì)應(yīng)的 檢驗(yàn)數(shù) 。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 ?24 = 1， ?22 = 1。 閉回路方法原理就是通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)數(shù) 。 —表上作業(yè)法 47 如果規(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) 。 —表上作業(yè)法 48 按上述作法 ， 可計(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ù) 49 顯然 ， 當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí) ， 現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案 ， 因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加 。 閉回路法的 主要缺點(diǎn) 是：當(dāng)變量個(gè)數(shù)較多時(shí) ， 尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難 。 —表上作業(yè)法 位勢(shì)：設(shè)對(duì)應(yīng) 基變量 xij 的 m +n 1 個(gè) ij ，存在 ui ,vj 滿足 ui+vj=cij ， i=1,2 … ,m 。 j=1,2 … ,n . 稱這些 ui , vj 為該基本可行解對(duì)應(yīng)的位勢(shì) 。 —表上作業(yè)法 51 由于有 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 —表上作業(yè)法 52 前例，位勢(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) —表上作業(yè)法 53 vj 3 4 2 5 ui B1 B2 B3 B4 產(chǎn)量 ai 5 A1 3 1 11 2 3 4 10 3 7 4 A2 1 3 9 1 2 *1 8 1 4 0 A3 7 10 4 6 10 12 5 3 9 銷(xiāo)量 bj 3 6 5 6 20 — 表上作業(yè)法 54 當(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ò)程通常稱為 換基 (或主元變換 )過(guò)程 。 —表上作業(yè)法 三 、 求新的基本可行解 55 （ 1） 選負(fù)檢驗(yàn)數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量（上頁(yè)圖中 x24 ） 。 （ 2） 以 xrk 為起點(diǎn)找一條閉回路，除 xrk 外其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回路） 。 —表上作業(yè)法 在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程是如下進(jìn)行： 56 （ 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)整量； —表上作業(yè)法 57 （ 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)榉腔兞俊? 重復(fù) (2)、 (3)步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。 —表上作業(yè)法 58 —表上作業(yè)法 vj 2 4 2 5 ui B1 B2 B3 B4 產(chǎn)量 ai 5 A1 3 0 11 2 3 ( 4+1 ) 5 10 ( 3 1 ) 2 7 3 A2 1