[管理學(xué)]運(yùn)輸問(wèn)題(編輯修改稿)
2024-11-15 02:13 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ， 存在 ui ,vj 滿足 ui+vj=cij ， i=1,2 … ,m 。 j=1,2 … ,n . 稱這些 ui , vj 為該基本可行解對(duì)應(yīng)的位勢(shì) 。 二、 最優(yōu)解的判別 — 位勢(shì)法 21 由于有 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ōu)解的判別 —位勢(shì)法 22 前例，位勢(shì)法求檢驗(yàn)數(shù)： step 1 從任意 基變量 對(duì)應(yīng)的 cij 開始 ,任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 個(gè) ui , vj , 從 c14 = 10 開始 step 2 計(jì)算 非基變量 的檢驗(yàn)數(shù) ?ij = cij ui vj ；填入括號(hào)內(nèi) 最優(yōu)解的判別 —位勢(shì)法 23 當(dāng)非基變量的檢驗(yàn)數(shù) 均為正 ，則當(dāng)前解就是最優(yōu)解； 當(dāng)非基變量的檢驗(yàn)數(shù) 出現(xiàn)負(fù)值時(shí) ， 則表明當(dāng)前的基本可行解不是最優(yōu)解 。 最優(yōu)解的判別 —位勢(shì)法 24 當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí) ，則表明當(dāng)前的基本可行解不是最優(yōu)解 。 這時(shí) ， 應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整 ， 即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降 ， 這一過(guò)程通常稱為 換基 (或主元變換 )過(guò)程 改進(jìn)運(yùn)輸方案的辦法（即求新的基本可行解） —— 閉回路調(diào)整法 25 例如 ， x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路 。 若把閉回路的各變量格看作節(jié)點(diǎn) ， 在表中可以畫出如下形式的閉回路： 閉回路的概念 閉回路示意圖 26 根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)： (1)閉回路均為一封閉折線 ， 它的每一條邊 ， 或?yàn)樗降?， 或?yàn)榇怪钡模? (2)閉回路的每一條邊 （ 水平的或垂直的 ） 均有且僅有兩個(gè)閉回路的頂點(diǎn)（ 變量格 ） 。 閉回路的概念 29 （ 1） 選負(fù)檢驗(yàn)數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量（下頁(yè)圖中 x24 ） 。 （ 2） 以 xrk 為起點(diǎn)找一條閉回路，除 xrk 外其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回路） 。 即求新的基本可行解 — 閉回路調(diào)整法 在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程是如下進(jìn)行： 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） 為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)， xrk 為 1，沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號(hào)； （ 4） 求 ? =Min{xij?x
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1