[管理學(xué)]運輸問題-文庫吧資料
2024-10-25 02:13本頁面
【正文】 3 9 銷量 bj 3 6 5 6 20 ?ij ≥ 0，得到 最優(yōu)解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 。 即求新的基本可行解 — 閉回路調(diào)整法 在運輸問題的表上作業(yè)法中，換基的過程是如下進行： 30 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 銷量 bj 3 6 5 6 20 31 （ 3） 為閉回路的每一個頂點標(biāo)號， xrk 為 1，沿一個方向（順時針或逆時針）依次給各頂點標(biāo)號； （ 4） 求 ? =Min{xij?xij對應(yīng)閉回路上的偶數(shù)標(biāo)號格 }= xpq 那么確定 xpq為出基變量， ?為調(diào)整量； 32 （ 5） 對閉回路的各奇標(biāo)號頂點調(diào)整為： xij + ?，對各偶標(biāo)號頂點 調(diào)整為： xij ?，特別 xpq ? = 0， xpq變?yōu)榉腔兞俊? 閉回路的概念 29 （ 1） 選負(fù)檢驗數(shù)中最小者 ?rk，那么 xrk 為主元，作為進基變量（下頁圖中 x24 ） 。 這時 ， 應(yīng)該對基本可行解進行調(diào)整 ， 即找到一個新的基本可行解使目標(biāo)函數(shù)值下降 ， 這一過程通常稱為 換基 (或主元變換 )過程 改進運輸方案的辦法（即求新的基本可行解） —— 閉回路調(diào)整法 25 例如 ， x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路 。 j = 1, … , n 最優(yōu)解的判別 —位勢法 22 前例，位勢法求檢驗數(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) 最優(yōu)解的判別 —位勢法 23 當(dāng)非基變量的檢驗數(shù) 均為正 ，則當(dāng)前解就是最優(yōu)解； 當(dāng)非基變量的檢驗數(shù) 出現(xiàn)負(fù)值時 ， 則表明當(dāng)前的基本可行解不是最優(yōu)解 。 二、 最優(yōu)解的判別 — 位勢法 21 由于有 m + n 個變量（ ui , vj ）， m + n 1 個方程（基變量個數(shù)）， 故有一個自由變量，位勢不唯一。 16 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 c11 x11 c12 x12 … c1n x1n a1 A2 c21 x21 c22 x22 … c2n x2n a2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1