[管理學(xué)]表上作業(yè)法(編輯修改稿)
2024-11-15 02:10 本頁面
【文章內(nèi)容簡介】 干個基變量的取值受其影響 。 這樣 ， 利用單位產(chǎn)品變化 （ 運輸?shù)膯挝毁M用 ） 可計算出它們對目標(biāo)函數(shù)的綜合影響 ， 其作用與線性規(guī)劃單純形方法中的檢驗數(shù)完全相同 。 故也稱這個綜合影響為該非基變量對應(yīng)的檢驗數(shù) 。 上面計算的兩個非基變量的檢驗數(shù)為 ?24 = 1，?22 = 1。 閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗數(shù) 。 如果規(guī)定作為起始頂點的非基變量為第 1 個頂點 ， 閉回路的其他頂點依次為第 2 個頂點 、 第 3 個頂點 …… ， 那么就有 ?ij = (閉回路上的奇數(shù)次頂點單位運費之和 ) (閉回路上的偶數(shù)次頂點單位運費之和 ) 其中 ij 為非基變量的下角指標(biāo) 。 按上述作法 ， 可計算出表中的所有非基變量的檢驗數(shù) ， 把它們填入相應(yīng)位置的方括號內(nèi) ， 如下圖所示 。 銷地 產(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)銷平衡 ) 初始基本可行解及檢驗數(shù) 顯然 ， 當(dāng)所有非基變量的檢驗數(shù)均大于或等于零時 ， 現(xiàn)行的調(diào)運方案就是最優(yōu)方案 ， 因為此時對現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運輸費用增加 。 閉回路法的主要缺點是：當(dāng)變量個數(shù)較多時 ， 尋找閉回路以及計算兩方面都會產(chǎn)生困難 。 當(dāng)非基變量的檢驗數(shù)出現(xiàn)負(fù)值時 ， 則表明當(dāng)前的基本可行解不是最優(yōu)解 。 在這種情況下 ， 應(yīng)該對基本可行解進(jìn)行調(diào)整 ， 即找到一個新的基本可行解使目標(biāo)函數(shù)值下降 ，這一過程通常稱為換基 (或主元變換 )過程 。 三 、 求新的基本可行解 （ 1）選負(fù)檢驗數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量（上圖中 x24 ） 。 （ 2）以 xrk 為起點找一條閉回路，除 xrk 外其余 頂點必須為基變量格（上頁圖中的回路） 。 在運輸問題的表上作業(yè)法中，換基的過程是如下進(jìn)行： （ 3）為閉回路的每一個頂點標(biāo)號， xrk 為 1，沿一個方向（順時針或逆時針）依次給各頂點標(biāo)號； （ 4）求 ? =min{xij?xij對應(yīng)閉回路上的偶數(shù)標(biāo)號格 }= xpq 那么確定 xpq為出基變量， ?為調(diào)整量； （ 5）對閉回路的各奇標(biāo)號頂點調(diào)整為： xij + ?，對各偶標(biāo)號頂點 調(diào)整為： xij ?，特別 xpq ? = 0， xpq變?yōu)榉?基變量。 重復(fù) (2)、 (3)步，直到所有檢驗數(shù)均非負(fù)，得到最優(yōu)解。 ?ij ≥ 0，得到最優(yōu)解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1