深化能力自學(xué)部分位勢(shì)法檢驗(yàn)最優(yōu)方案（以課內(nèi)練習(xí)題為例求解）

表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問(wèn)題時(shí)的一種簡(jiǎn)化方法。它包括以下步驟：確定初始可行方案。方法比較多，一般希望方法既簡(jiǎn)單，又盡可能接近最優(yōu)解，常用最小元素法和伏格爾法。最優(yōu)方案的判別。判別的方法是計(jì)算空格的檢驗(yàn)數(shù)，常用閉回路法和位勢(shì)法。改進(jìn)方案。常使用閉回路調(diào)整法進(jìn)行調(diào)整以得到最優(yōu)的方案。最小元素法【例7】有某公司經(jīng)銷一產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為A1＝7噸、A2＝4噸，A3＝9噸，該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各個(gè)銷售點(diǎn)每日銷量為B1＝3噸，B2＝6噸，B3＝5噸，B4＝6噸，已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如表所示，問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少。B1B2B3B4A1311310A21928A374105銷地加工廠B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656銷地加工廠314633B1B2B3B4A143A231A363銷地加工廠2、最優(yōu)方案的判別——位勢(shì)法使用位勢(shì)法求出檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)都不為負(fù)數(shù)，則原方案為最優(yōu)解，若有負(fù)檢驗(yàn)數(shù)存在，則負(fù)檢驗(yàn)數(shù)所在空格需進(jìn)行調(diào)整。只有沒(méi)有運(yùn)量的空格處需要計(jì)算檢驗(yàn)數(shù)。2、最優(yōu)方案的判別——位勢(shì)法檢驗(yàn)數(shù)的計(jì)算方法如下：設(shè)有運(yùn)量的格子數(shù)最多的行或列的位勢(shì)＝0有運(yùn)量格子的運(yùn)價(jià)＝行位勢(shì)+列位勢(shì)空格的檢驗(yàn)數(shù)＝運(yùn)價(jià)-（行位勢(shì)+列位勢(shì)）

【例10】下面是用最小元素法的得出的運(yùn)輸方案，試用位勢(shì)法判斷是否最優(yōu)。B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656銷地加工廠314633【例10】下面是用最小元素法的得出的運(yùn)輸方案，試用位勢(shì)法判斷是否最優(yōu)。B1B2B3B4行位勢(shì)A13113?10?A21?92?8A374?105?列位勢(shì)銷地加工廠0310-1-529121-110123、改進(jìn)方案——閉合回路調(diào)整法從負(fù)檢驗(yàn)數(shù)所在格子出發(fā)找一條閉合回路，用水平或垂直線向前劃，每碰到數(shù)字格轉(zhuǎn)90度，然后繼續(xù)前進(jìn)，直到回到起始空格為止。并從出發(fā)格開(kāi)始依次標(biāo)上正負(fù)號(hào)。將所有標(biāo)有負(fù)號(hào)的轉(zhuǎn)角格中的最小運(yùn)量作為調(diào)整數(shù)。各正號(hào)加上調(diào)整數(shù)，負(fù)號(hào)減去調(diào)整數(shù)?！纠?1】使用閉合回路法對(duì)例10進(jìn)行調(diào)整。B1B2B3B4行位勢(shì)A13113?10?A21?92?8A374?105?列位勢(shì)銷地加工廠0310-1-529121-11012B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656銷地加工廠314633++--152最優(yōu)方案：B1B2B3B4產(chǎn)量A13113107A219284A3741059