運(yùn)輸問題-初始基可行解的確定

1、4.2 用表上作業(yè)法求解運(yùn)輸問題,表上作業(yè)法的基本思想：先設(shè)法給出一個(gè)初始方案,然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如下圖所示。,初始化,最優(yōu)性檢驗(yàn),迭代（Iteration）,最優(yōu)？,,,,yes,,STOP,no,這和單純形法的求解思想完全一致，但是具體的作法則更加簡(jiǎn)捷。,例1 某部門有3個(gè)同類型的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位為t）

2、以及各工廠到銷售點(diǎn)的單位運(yùn)價(jià)（元/t）示于表4-2中，問如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？,表 4-2,該運(yùn)輸問題的數(shù)學(xué)模型為：,可以證明：約束矩陣的秩 r (A) = m +n -1.,基變量的個(gè)數(shù)為 m+n-1.,表上作業(yè)法,計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案 , Go to 2,表上作業(yè)法,計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案 , Go to 2,下面介紹三種常用的方法。,一、給

3、出運(yùn)輸問題的初始可行解（初始調(diào)運(yùn)方案）,最小元素法西北角法沃格爾(Vogel)法,1。最小元素法,思想：優(yōu)先滿足運(yùn)價(jià)（或運(yùn)距）最小的供銷業(yè)務(wù)。,表 3-2,,①,,表 3-2,,①,②,,,,表 3-2,,①,②,,,,,,③,表 3-2,,①,②,,,,,,③,,④,,表 3-2,,①,,,,,,③,,④,,,⑤,,②,表 3-2,,①,,,,,,③,,④,,,⑤,,,,⑥,⑥,②,此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：,其余變

4、量全等于零。,總運(yùn)費(fèi)為（目標(biāo)函數(shù)值）,此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6).,⒉ 西北角法,西北角法是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。,表 3-2,表 3-2,,①,,表 3-2,,①,,表 3-2,,①,,,②,,表 3-2,,①,,,②,,表 3-2,,①,,,②,,,③,,表 3-2,,①,,,②,,,③,,表 3-2,,①,,,②,,,③,,,④,,表 3

5、-2,,①,,,,,③,,,②,④,,表 3-2,,①,,,,,③,,,②,④,,,⑤,,表 3-2,,①,,,,,③,,,②,④,,,⑤,,表 3-2,,①,,,,,③,,,②,④,,,⑤,,,,⑥,⑥,此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：,其余變量全等于零。,總運(yùn)費(fèi)為（目標(biāo)函數(shù)值）,此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6).,⒊ 沃格爾（Vogel)法,初看起來，最小元素法十分

6、合理。但是，有時(shí)按某一最小單位運(yùn)價(jià)安排物品調(diào)運(yùn)時(shí)，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷點(diǎn)，從而使整個(gè)運(yùn)輸費(fèi)用增加。,沃格爾法的思想： 對(duì)每一個(gè)供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià)，并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大；反之，如果罰數(shù)的值很大，不按最小運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大的損失，故應(yīng)盡量按最大罰

7、數(shù)安排運(yùn)輸。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：,其余變量全等于零。,總運(yùn)費(fèi)為（目標(biāo)函數(shù)值）,此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6).,比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法解的目標(biāo)函數(shù)值最大。 一般說來，沃格爾法得出的初始解