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