【正文】 產(chǎn) 量 4 12 12 4 4 11 16 8 2 10 3 2 9 10 8 14 5 11 8 6 22 銷(xiāo) 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 iujv14?1039221121?309jiij vuc ?? )( jiijij vuc ????四。 ij? iv為此，在求解方程組（ ）時(shí)，為計(jì)算簡(jiǎn)便，可指定一個(gè)位 勢(shì)等于一個(gè)較小的整數(shù)或零。 ? ?nm vvvuuuY ...... 2121? 對(duì)產(chǎn)銷(xiāo)平衡運(yùn)輸問(wè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)輸問(wèn)題的對(duì)偶規(guī)劃寫(xiě)成： ?????????????? ????的符號(hào)不限jiijjinjjjmiiivunjmicvustvbuaZ, . . .1, . .1.m a x11前面學(xué)習(xí)知道，線性規(guī)劃問(wèn)題變量 xj的檢驗(yàn)數(shù)可表示為： 1j j j B j j jj c z c c B P c Y P??? ? ? ? ? ?由此可寫(xiě)出運(yùn)輸問(wèn)題某變量 xij(對(duì)應(yīng)于運(yùn)輸表中 (Ai,Bj))的檢驗(yàn)數(shù)如下： 1 2 1 2( , , .. . , , .. . )()ij ij ij ijij mijijjjniic z c Y Pc u u u v v v Pc u v? ?????????其中 分別稱(chēng)為行位勢(shì)、列位勢(shì)。 定義 2： 從每一空格（非基格）出發(fā)，沿水平或垂直方向前進(jìn)，每碰到數(shù)字格轉(zhuǎn) 90o（有些情況也可以不改變方向）繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱(chēng)為閉回路。下面介紹 最優(yōu)性檢驗(yàn)的兩種方法。 銷(xiāo) 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 1 2 3 4 12 4 11 16 0 2 10 3 9 10 1 8 11 6 1 銷(xiāo) 量 8 12 14 48 列 罰 數(shù) 1 2 5 1 3 2 3 1A2A1B 2B 3B 4B3A51422148銷(xiāo) 地 產(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 銷(xiāo) 量 8 14 12 48 列 罰 數(shù) 1 2 5 1 3 2 2 1 3 3 1A2A1B 2B 3B 4B3A814614 6銷(xiāo) 地 產(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 銷(xiāo) 量 14 12 48 列 罰 數(shù) 1 2 5 1 3 2 2 1 3 3 2 1 1A2A1B 2B 3B 4B3A814614 6281082銷(xiāo) 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 4 5 6 4 12 11 7 10 3 9 6 8 5 11 22 銷(xiāo) 量 14 48 列 罰 數(shù) 4 1 2 5 6 1A2A1B 2B 3B 4B3A814614 628108241216124銷(xiāo) 地 產(chǎn)地 產(chǎn) 量 行罰數(shù) 4 5 6 4 12 11 7 0 10 3 6 0 8 5 11 22 銷(xiāo) 量 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 xcz3 7 26141183410612848 ?????????????此解滿(mǎn)足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為 6 （等于 m+n1=3+41=6). ⒊ 沃格爾（ Vogel)法 初看起來(lái)，最小元素法十分合理。最小元素法 思想：優(yōu)先滿(mǎn)足運(yùn)價(jià)（或運(yùn)距）最小的供銷(xiāo)業(yè)務(wù)。 初始化 最優(yōu)性檢驗(yàn) 迭代 （ Iteration） 最優(yōu)？ yes STOP no 這和單純形法的求解思想完全一致，但是具體的作法則更加簡(jiǎn)捷。從而 r(A)≤m+n. 去掉 A的第一行，并取如下 m+n1列，得到 m+n1階子式 11 12 1 21 31 1||0 0 0 1 0 00 0 0 0 1 00 0 0 0 0 1101 0 0 1 1 10 1 0 0 0 00 0 1 0 0 0nmD p p p p p p? ? ? ? ? ??? ? ? ?所以 r(A)=m+n1. 對(duì)于產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題，除了上述特點(diǎn)外，還有以下特點(diǎn)： 1 所有結(jié)構(gòu)約束條件都是等式約束 2 各產(chǎn)地產(chǎn)量之和等于各銷(xiāo)地銷(xiāo)量之和 運(yùn)輸問(wèn)題的解 運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn) 運(yùn)輸問(wèn)題是一種線性規(guī)劃問(wèn)題。, 212222111211jmiij eep ??? ),2,1。 []ijx又因?yàn)榭傎M(fèi)用不會(huì)為負(fù)值（存在下界）。運(yùn)輸問(wèn)題 ?運(yùn)輸問(wèn)題及其數(shù)學(xué)模型 ?運(yùn)輸問(wèn)題的表上作業(yè)法 ?運(yùn)輸問(wèn)題的進(jìn)一步討論 例 1：某部門(mén)有 3個(gè)生產(chǎn)同類(lèi)產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由 4個(gè)銷(xiāo)售點(diǎn)（銷(xiāo)地）出售，各工廠的生產(chǎn)量、各銷(xiāo)售點(diǎn)的銷(xiāo)售量（假定單位均為 t）以及各工廠到各銷(xiāo)售點(diǎn)的單位運(yùn)價(jià)（元 /t）示于下表中 要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型 單位 銷(xiāo)地 運(yùn)價(jià) 產(chǎn)地 產(chǎn)量 2 9 10 2 9 1 3 4 2 5 8 4 2 5 7 銷(xiāo)量 3 8 4 6 4321 BBBB321AAAA2 A3 B2 A1 B3 B4 B1 s2=5 s3=7 d1=3 d2=8 d3=4 d4=6 s1=9 供應(yīng)量 供應(yīng)地 運(yùn)價(jià) 需求量 需求地 2 9 10 2 1 3 4 2 8 4 2 5 運(yùn)輸問(wèn)題網(wǎng)絡(luò)圖 ????????????????????????????????????????????????????),(06483759524824371092m i n342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約束條件：目標(biāo)函數(shù)：為運(yùn)量設(shè)產(chǎn)量約束 銷(xiāo)量約束 運(yùn)輸問(wèn)題的一般提法是：設(shè)某種物資有 個(gè)產(chǎn)地 m ,1A ,2A ,?,mA各產(chǎn)地的產(chǎn)量是 。事實(shí)上： ijx?? ??? ????njijinjnjjiij abdadbax11 1),2,1( mi ???? ??? ????mijijmimijiij badbdbax11 1),2,1( nj ??又因 .0,0 ??ji ba所以 .0?ijx故 是一組可行解。 （ 4－ 1） mnmmnn xxxxxxxxx ??????? ,。即運(yùn)輸問(wèn)題的基變量總數(shù)是 m+n1 證明：因 A的前 m行對(duì)應(yīng)元素的和與后 n行對(duì)應(yīng)元素的和相等， 恰好都是： nmE ?? )1,1,1(1 ?所以 A的行向量是線性相關(guān) 的。 因此，我們利用運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn)，引入了 表上作業(yè)法 來(lái)求解運(yùn)輸問(wèn)題 用表上作業(yè)法求解運(yùn)輸問(wèn)題 表上作業(yè)法的基本思想： 先設(shè)法給出一個(gè)初始方案 ,然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如下圖所示。 一、給出運(yùn)輸問(wèn)題的初始可行解（初始調(diào)運(yùn)方案） ?最小元素法 ?西北角法 ?沃格爾 (Vogel)法 1。 銷(xiāo)地 產(chǎn)地 產(chǎn) 量 4 12 4 11 2 10 3 9 10 8 5 11 6 22 銷(xiāo) 量 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 81611x