【文章內(nèi)容簡介】 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 1 2 3 4 12 4 11 16 0 0 2 10 3 9 10 1 1 8 5 11 22 1 2 銷 量 8 14 12 48 列 罰 數(shù) 1 2 5 1 3 2 2 1 3 3 1A2A1B 2B 3B 4B3A814614 6銷 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 1 2 3 4 12 4 11 16 0 0 0 10 3 9 1 1 1 8 5 11 22 1 2 銷 量 14 12 48 列 罰 數(shù) 1 2 5 1 3 2 2 1 3 3 2 1 1A2A1B 2B 3B 4B3A814614 6281082銷 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 4 5 6 4 12 11 7 10 3 9 6 8 5 11 22 銷 量 14 48 列 罰 數(shù) 4 1 2 5 6 1A2A1B 2B 3B 4B3A814614 628108241216124銷 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 4 5 6 4 12 11 7 0 10 3 6 0 8 5 11 22 銷 量 14 48 列 罰 數(shù) 4 1 2 5 2 6 1A2A1B 2B 3B 4B3A814614 62810824121612494此時得到一個初始調(diào)運方案（初始可行解）： ,1213 ?x,414 ?x ,821 ?x ,224 ?x 32 14,x ? ,834 ?x其余變量全等于零。 總運費為（目標函數(shù)值） ? ?? ??3141i jijij xcz2 4 4685149228114412 ?????????????此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為 6 （等于 m+n1=3+41=6). 比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標函數(shù)值最小，最小元素法次之，西北角法解的目標函數(shù)值最大。 一般說來，沃格爾法得出的初始解的質(zhì)量最好，常用來作為運輸問題最優(yōu)解的近似值。 銷地 產(chǎn)地 產(chǎn) 量 4 1 4 6 8 1 2 5 0 8 3 7 5 1 4 銷 量 6 5 6 3 20 1A2A1B 2B 3B 4B3A課堂練習 表上作業(yè)法 ?計算步驟： 給出初始方案 檢驗是否最優(yōu) 調(diào)整調(diào)運方案 , Go to 2 二、解的最優(yōu)性檢驗 前面得到了初始基可行解，一般來說此解并非最優(yōu)。下面介紹 最優(yōu)性檢驗的兩種方法。 1 閉回路法 (Cycle method) 2 對偶變量法（ dual variable method）也稱為位勢法 ⒈ 閉回路法（ cycle method) 下面用最小元素法所確定的初始基本可行解來說明。 與單純性原理相同，現(xiàn)目標是運費最少，故檢驗每一個非 基變量（對應于運輸表中的空格）的檢驗數(shù)是否 .0?ij???ij?若所有空格的檢驗數(shù)全非負，則不管怎樣均不能使運輸費用降低，即目標函數(shù)值已無法改進，這個解就是最優(yōu)解 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A3A1B 2B 3B 4B考慮空格 (A1,B1),設想由產(chǎn)地 A1供應一個單位的物品給銷地 B1，為使運入銷地 B1的物品總量不大于它的銷量，應將 A2運到 B1的物品數(shù)量減 1，即將格子（ A2,B1）中填入的數(shù)字 8改為 7； 另一方面，為使產(chǎn)地 A2運出的物品數(shù)量正好等于它的產(chǎn)量 (保證新得到的解仍為基可行解 )，應將 A2運到 B3的物品數(shù)量增 1。 同理 A1運往 B3的物品數(shù)量減 1， A1運出的物品數(shù)量正好等于其產(chǎn)量 按照上述設想，由產(chǎn)地 A1供給 1個單位物品給銷地 B1,由此引起的總運費變化是： 11 21 23 13c c +c c = 42 +3 4 = 1根據(jù)檢驗數(shù)的定義，它正是非基變量 x11(或者說空格(A1,B1))的檢驗數(shù) 定義 1： 基變量（有數(shù)字的）對應的格為基格；非基變量（空格）對應的頂點為非基格。 定義 2： 從每一空格（非基格）出發(fā)，沿水平或垂直方向前進，每碰到數(shù)字格轉(zhuǎn) 90o（有些情況也可以不改變方向）繼續(xù)前進，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱為閉回路。 規(guī)定：起始頂點的空格為第一頂點，則 =閉回路上奇數(shù)次頂點運價之和 — 閉回路上偶數(shù)次頂點運價之和 ij? 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 143241323211111 ????????? cccc?1 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 21165121434321212 ????????? cccc?21 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 13411651023131434322222 ????????????? cccccc?121 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 1341192313142424 ?????????? cccc?1?121 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 10611432834141323213131 ????????????? cccccc?102111? 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 124116111314343333 ????????? cccc?12101?121 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 1 21 1?10 12檢驗數(shù)中有負數(shù)，說明原方案不是最優(yōu)解。 ⒉ 對偶變量法（位勢法） (dual variable method) 用閉回路法判定一個運輸方案是否最優(yōu)，需要找出所有空格的閉回路，并計算其檢驗數(shù)。當運輸問題的產(chǎn)地和銷地很多時，空格的數(shù)目很大，計算檢驗數(shù)的工作量很大，而用對偶變量法就簡便得多。 ? ?nm vvvuuuY ...... 2121? 對產(chǎn)銷平衡運輸問題，若用 u1,u2,…,u m分別表示前 m個約束等式相對應的對偶變量，用 v1,v2…v n 分別表示后 n個等式相對應的對偶變量，即有對偶向量 這時可將運輸問題的對偶規(guī)劃寫成： ?????????????? ????的符號不限jiijjinjjjmiiivunjmicvustvbuaZ, . . .1, . .1.m a x11前面學習知道，線性規(guī)劃問題變量 xj的檢驗數(shù)可表示為： 1j j j B j j jj c z c c