運輸問題-初始基可行解的確定

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

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

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

4、量全等于零。,總運費為（目標函數值）,此解滿足所有約束條件，且基變量（非零變量）的個數為6（等于m+n-1=3+4-1=6).,⒉ 西北角法,西北角法是優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷需求。,表 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,,①,,,,,③,,,②,④,,,⑤,,,,⑥,⑥,此時得到一個初始調運方案（初始可行解）：,其余變量全等于零。,總運費為（目標函數值）,此解滿足所有約束條件，且基變量（非零變量）的個數為6（等于m+n-1=3+4-1=6).,⒊ 沃格爾（Vogel)法,初看起來，最小元素法十分

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

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