運(yùn)籌學(xué) 第四 第四 運(yùn)輸問題PPT學(xué)習(xí)教案

1、會計學(xué)1例1：某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點(diǎn)（銷地）出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位均為t）以及各工廠到各銷售點(diǎn)的單位運(yùn)價（元/t）示于下表中要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小 4.1 運(yùn)輸問題及其數(shù)學(xué)模型單位 銷地 運(yùn)價產(chǎn)地產(chǎn)量2910291342584257銷量38464321 BBBB321AAA第1頁/共116頁A2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供應(yīng)量供應(yīng)地運(yùn)價需求量需求地2910213428425運(yùn)輸問題網(wǎng)絡(luò)圖運(yùn)輸問題網(wǎng)絡(luò)圖第2頁/共116頁 )4 . 3 . 2 . 1, 3 . 2

2、 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約約束束條條件件：目目標(biāo)標(biāo)函函數(shù)數(shù)：為為運(yùn)運(yùn)量量設(shè)設(shè)產(chǎn)量約束銷量約束第3頁/共116頁運(yùn)輸問題的一般提法是：設(shè)某種物資有 個產(chǎn)地m,1A,2A,mA各產(chǎn)地的產(chǎn)量是;,21maaa有 個銷地,1B,2B,nBn各銷地的銷量是.,21nbbb假定從產(chǎn)地 ), 2 , 1(miAi到銷地),2, 1(njBj運(yùn)輸

3、單位物品的運(yùn)價是 ，問ijc怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最?。康?頁/共116頁 銷地產(chǎn)地產(chǎn)量銷 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama運(yùn)價表第5頁/共116頁 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)銷平衡時，其模型如下：0,0,0ijijabc假設(shè)：第6頁/共116頁當(dāng)產(chǎn)大于銷時，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ第7頁/共116頁當(dāng)產(chǎn)小于銷時，其模型是：min ()0ijiji

4、jiijjijijZc xxaxbabx第8頁/共116頁 1 1、平衡運(yùn)輸問題必有可行解，、平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解；也必有最優(yōu)解；運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)證明 記.11dbaminjji則令dbaxjiij), 2 , 1;, 2 , 1(njmi第9頁/共116頁則 為運(yùn)輸問題的一個可行解。事實(shí)上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一組可行解。ijx又因為總費(fèi)用不會為負(fù)值（存在下界）。這說明，運(yùn)輸問題

5、既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。第10頁/共116頁 2 2、運(yùn)輸問題約束條件的系數(shù)矩、運(yùn)輸問題約束條件的系數(shù)矩陣陣運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)對運(yùn)輸問題數(shù)學(xué)模型的結(jié)構(gòu)約束加以整理，可知其系數(shù)矩陣具有下述形式：第11頁/共116頁m行n行1運(yùn)輸問題是一個具有mn個變量和n+m個等型約束的線性規(guī)劃問題。 （41）mnmmnnxxxxxxxxx,;,212222111211第12頁/共116頁jmiijeep), 2 , 1;, 2 , 1(njmi() 1() 1() 1000110000101000ijimjmnmnmnpee第13頁/共116頁2運(yùn)輸問題約

6、束方程組的系數(shù)矩陣是一個只有0和1兩個數(shù)值的稀疏矩陣,其中1的總數(shù)為 2mn 個。3、約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次第14頁/共116頁4、約束條件系數(shù)矩陣的秩是m+n-1。即運(yùn)輸問題的基變量總數(shù)是m+n-1證明：因A的前m行對應(yīng)元素的和與后n行對應(yīng)元素的和相等，恰好都是：nmE) 1 , 1 , 1 (1所以A的行向量是線性相關(guān)的。從而 r(A)m+n.第15頁/共116頁去掉A的第一行，并取如下m+n-1列，得到m+n-1階子式1112121311|00010000001000000110100111010

7、000001000nmDp pp ppp 所以 r(A)=m+n-1.第16頁/共116頁對于產(chǎn)銷平衡運(yùn)輸問題，除了上述特點(diǎn)外，還有以下特點(diǎn)： 1 所有結(jié)構(gòu)約束條件都是等式約束 2 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和第17頁/共116頁 3 3、運(yùn)輸問題的解、運(yùn)輸問題的解運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題是一種線性規(guī)劃問題。前面講述的單純形法是求解線性規(guī)劃問題十分有效的一般方法，因而可用單純形法求解運(yùn)輸問題。但是當(dāng)用單純形法求解運(yùn)輸問題時，先得在每個約束條件中引入一個人工變量，這樣一來，即使對于m=3、n=4這樣簡單的運(yùn)輸問題，變量數(shù)目也會達(dá)到19個之多。第18頁/共116頁因

8、此，我們利用運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)，引入了表上作業(yè)法來求解運(yùn)輸問題第19頁/共116頁 4.2 用表上作業(yè)法求解運(yùn)輸問題表上作業(yè)法的基本思想：先設(shè)法給出一個初始方案,然后根據(jù)確定的判別準(zhǔn)則對初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如下圖所示。第20頁/共116頁初始化最優(yōu)性檢驗迭代（Iteration）最優(yōu)？yesSTOPno這和單純形法的求解思想完全一致，但是具體的作法則更加簡捷。第21頁/共116頁例1 某部門有3個同類型的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點(diǎn)出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位為t）以及各工廠到銷售點(diǎn)的單位運(yùn)價（元/t）示于表4-2中，問如何調(diào)運(yùn)才能使

9、總運(yùn)費(fèi)最?。康?2頁/共116頁 銷地產(chǎn)地產(chǎn)量4124111621039108511622銷 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x第23頁/共116頁34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxx

10、xxxxij該運(yùn)輸問題的數(shù)學(xué)模型為：第24頁/共116頁可以證明：約束矩陣的秩 r (A) = m +n -1.基變量的個數(shù)為 m+n-1.第25頁/共116頁第26頁/共116頁第27頁/共116頁下面介紹三種常用的方法。一、給出運(yùn)輸問題的初始可行解（初始調(diào)運(yùn)方案）l最小元素法l西北角法l沃格爾(Vogel)法第28頁/共116頁1。最小元素法思想：優(yōu)先滿足運(yùn)價（或運(yùn)距）最小的供銷業(yè)務(wù)。第29頁/共116頁 銷地產(chǎn)地產(chǎn)量 4124111610398511622銷 量141214481A2A1B2B3B4B3A表 3-2228810第30頁/共116頁 銷地產(chǎn)地產(chǎn)量 4124111621091

11、08511622銷 量 81414481A2A1B2B3B4B3A表 3-23210128第31頁/共116頁 銷地產(chǎn)地產(chǎn)量 412112109108511622銷 量 8141214481A2A1B2B3B4B3A表 3-232104161068第32頁/共116頁 銷地產(chǎn)地產(chǎn)量 4121182109108116銷 量 81214481A2A1B2B3B4B3A表 3-2321041610651422148第33頁/共116頁 銷地產(chǎn)地產(chǎn)量 412118210910811銷 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146第34頁/共116頁

12、銷地產(chǎn)地產(chǎn)量 4128210910811銷 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611第35頁/共116頁此時得到一個初始調(diào)運(yùn)方案（初始可行解）：,1013x, 614x, 821x, 223x,1432x, 834x其余變量全等于零。總運(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz246685143228116410此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為6（等于m+n-1=3+4-1=6).第36頁/共116頁 西北角法西北角法是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。第37頁/共116頁 銷地產(chǎn)地產(chǎn)量41241

13、121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281611x第38頁/共116頁 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281688第39頁/共116頁 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量1214481A2A1B2B3B4B3A表 3-28168812x14第40頁/共116頁 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-2816886第41頁/共116頁 銷地產(chǎn)地產(chǎn)量 41241121

14、0398511622銷 量141214481A2A1B2B3B4B3A表 3-281688622x10第42頁/共116頁 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-28168861064第43頁/共116頁 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量1414481A2A1B2B3B4B3A表 3-2816886106423x12第44頁/共116頁 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-281688610648第45頁/共116頁 銷地產(chǎn)地產(chǎn)量

15、 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-2816886106432x822第46頁/共116頁 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064822814第47頁/共116頁 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量1412481A2A1B2B3B4B3A表 3-2816886106482281434x14第48頁/共116頁 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064

16、822814第49頁/共116頁此時得到一個初始調(diào)運(yùn)方案（初始可行解）：, 811x, 812x, 622x, 423x, 833x,1434x其余變量全等于零。總運(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz3726141183410612848此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為6（等于m+n-1=3+4-1=6).第50頁/共116頁 沃格爾（Vogel)法初看起來，最小元素法十分合理。但是，有時按某一最小單位運(yùn)價安排物品調(diào)運(yùn)時，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷點(diǎn)，從而使整個運(yùn)輸費(fèi)用增加。沃格爾法的思想： 對每一個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)

17、價中找出最小單位運(yùn)價和次小單位運(yùn)價，并稱這兩個單位運(yùn)價之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小運(yùn)價安排運(yùn)輸時造成的運(yùn)費(fèi)損失不大；反之，如果罰數(shù)的值很大，不按最小運(yùn)價組織運(yùn)輸就會造成很大的損失，故應(yīng)盡量按最大罰數(shù)安排運(yùn)輸。第51頁/共116頁銷 地產(chǎn)地產(chǎn)量行罰數(shù)1234124111602103910181161銷 量8121448列罰數(shù)12513231A2A1B2B3B4B3A51422148第52頁/共116頁銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 412411160021039101185112212銷 量8141248列罰數(shù)12513221331A2A1B2B3B4B3A814614

18、6第53頁/共116頁銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 41241116000103911185112212銷 量141248列罰數(shù)125132213321 21A2A1B2B3B4B3A8146146281082第54頁/共116頁銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 41211710396851122銷 量1448列罰數(shù)412561A2A1B2B3B4B3A814614628108241216124第55頁/共116頁銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 412117010360851122銷 量1448列罰數(shù)4125 261A2A1B2B3B4B3A81461462810824121612494第56頁/共116

19、頁此時得到一個初始調(diào)運(yùn)方案（初始可行解）：,1213x, 414x, 821x, 224x3214,x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz244685149228114412此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為6（等于m+n-1=3+4-1=6).第57頁/共116頁比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法解的目標(biāo)函數(shù)值最大。 一般說來，沃格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似值。第58頁/共116頁 銷地產(chǎn)地產(chǎn)量 414681250837514銷 量65632

20、01A2A1B2B3B4B3A課堂練習(xí)課堂練習(xí)第59頁/共116頁第60頁/共116頁二、解的最優(yōu)性檢驗前面得到了初始基可行解，一般來說此解并非最優(yōu)。下面介紹最優(yōu)性檢驗的兩種方法。1 閉回路法(Cycle method)2 對偶變量法（dual variable method）也稱為位勢法第61頁/共116頁補(bǔ)充：閉回路的數(shù)學(xué)定義補(bǔ)充：閉回路的數(shù)學(xué)定義定義：定義：凡是能排成凡是能排成1 112222311 12 122321,.,.,ssssssi ji ji ji ji ji ji ji ji ji ji ji jxxxxxxxxxxxx或形式的變量的集合稱為一個閉回路，并將這些變量稱為這個

21、閉回路的頂點(diǎn)。形式的變量的集合稱為一個閉回路，并將這些變量稱為這個閉回路的頂點(diǎn)。第62頁/共116頁由此可以看出閉回路的幾何特點(diǎn)：由此可以看出閉回路的幾何特點(diǎn)：1. 閉回路都是一條封閉折線，每個頂點(diǎn)格子都是轉(zhuǎn)角閉回路都是一條封閉折線，每個頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn)點(diǎn)2. 每一行或每一列只有且僅有兩個頂點(diǎn)格子每一行或每一列只有且僅有兩個頂點(diǎn)格子3. 每兩個頂點(diǎn)格子的連線都是水平的或垂直的。每兩個頂點(diǎn)格子的連線都是水平的或垂直的?？梢宰C明的一個重要結(jié)論：可以證明的一個重要結(jié)論：m+n-1個變量構(gòu)成基變量的充要條件是它不含閉回路，即不存在以這些變量為頂點(diǎn)的閉回路個變量構(gòu)成基變量的充要條件是它不含閉回路，即不

22、存在以這些變量為頂點(diǎn)的閉回路第63頁/共116頁 閉回路法（閉回路法（cycle method)下面用最小元素法所確定的初始基本可行解來說明。下面用最小元素法所確定的初始基本可行解來說明。與單純性原理相同，現(xiàn)目標(biāo)是運(yùn)費(fèi)最少，故檢驗每一個非與單純性原理相同，現(xiàn)目標(biāo)是運(yùn)費(fèi)最少，故檢驗每一個非基變量（對應(yīng)于運(yùn)輸表中的空格）的檢驗數(shù)是否基變量（對應(yīng)于運(yùn)輸表中的空格）的檢驗數(shù)是否. 0ij?ij若所有空格的檢驗數(shù)全非負(fù)，則不管怎樣均不能使運(yùn)輸費(fèi)用降低，即目標(biāo)函數(shù)值已無法改進(jìn)，這個解就是最優(yōu)解若所有空格的檢驗數(shù)全非負(fù)，則不管怎樣均不能使運(yùn)輸費(fèi)用降低，即目標(biāo)函數(shù)值已無法改進(jìn)，這個解就是最優(yōu)解第64頁/共11

23、6頁 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A3A1B2B3B4B考慮空格考慮空格(A1,B1),設(shè)想由產(chǎn)地設(shè)想由產(chǎn)地A1供應(yīng)一個單位的物品給銷地供應(yīng)一個單位的物品給銷地B1，為使運(yùn)入銷地，為使運(yùn)入銷地B1的物品總量不大于它的銷量，應(yīng)將的物品總量不大于它的銷量，應(yīng)將A2運(yùn)到運(yùn)到B1的物品數(shù)量減的物品數(shù)量減1，即將格子（，即將格子（A2,B1）中填入的數(shù)字）中填入的數(shù)字8改為改為7；另一方面，為使產(chǎn)地另一方面，為使產(chǎn)地A2運(yùn)出的物品數(shù)量正好等于它的產(chǎn)量運(yùn)出的物品數(shù)量正好等于它的產(chǎn)量(保證新得到的解仍為基可行解保證新得到的解仍為基可行

24、解)，應(yīng)將，應(yīng)將A2運(yùn)到運(yùn)到B3的物品數(shù)量增的物品數(shù)量增1。同理同理A1運(yùn)往運(yùn)往B3的物品數(shù)量減的物品數(shù)量減1，A1運(yùn)出的物品數(shù)量正好等于其產(chǎn)量運(yùn)出的物品數(shù)量正好等于其產(chǎn)量第65頁/共116頁按照上述設(shè)想，由產(chǎn)地按照上述設(shè)想，由產(chǎn)地A1供給供給1個單位物品給銷地個單位物品給銷地B1,由此引起的總運(yùn)費(fèi)變化是：由此引起的總運(yùn)費(fèi)變化是：11212313c -c +c -c= 4-2+3-4 =1根據(jù)檢驗數(shù)的定義，它正是非基變量根據(jù)檢驗數(shù)的定義，它正是非基變量x11(或者說空格或者說空格(A1,B1)的檢驗數(shù)的檢驗數(shù)第66頁/共116頁定義定義1：基變量（有數(shù)字的）對應(yīng)的格為基格；非基變量（空格）對應(yīng)

25、的頂點(diǎn)為非基格?；兞浚ㄓ袛?shù)字的）對應(yīng)的格為基格；非基變量（空格）對應(yīng)的頂點(diǎn)為非基格。定義定義2：從每一空格（非基格）出發(fā)，沿水平或垂直方向前進(jìn)，每碰到數(shù)字格轉(zhuǎn)從每一空格（非基格）出發(fā)，沿水平或垂直方向前進(jìn)，每碰到數(shù)字格轉(zhuǎn)90o（有些情況也可以不改變方向）繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱為閉回路。（有些情況也可以不改變方向）繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱為閉回路。規(guī)定：起始頂點(diǎn)的空格為第一頂點(diǎn)，則規(guī)定：起始頂點(diǎn)的空格為第一頂點(diǎn)，則 =閉回路上奇數(shù)次頂點(diǎn)運(yùn)價之和閉回路上奇數(shù)次頂點(diǎn)運(yùn)價之和 閉回路上偶數(shù)次頂點(diǎn)運(yùn)價之和閉回路上偶數(shù)次頂點(diǎn)運(yùn)價之和 ij

26、第67頁/共116頁 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2143241323211111cccc1第68頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-221165121434321212cccc21第69頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2134116510231314343222

27、22cccccc121第70頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-21341192313142424cccc1121第71頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-210611432834141323213131cccccc102111第72頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B

28、3A表 3-2124116111314343333cccc12101121第73頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-212111012檢驗數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。第74頁/共116頁 對偶變量法（位勢法）(dual variable method) 用閉回路法判定一個運(yùn)輸方案是否最優(yōu)，需要找出所有空格的閉回路，并計算其檢驗數(shù)。當(dāng)運(yùn)輸問題的產(chǎn)地和銷地很多時，空格的數(shù)目很大，計算檢驗數(shù)的工作量很大，而用對偶變量法就簡便得多。nmvvvuuuY.2121 對產(chǎn)銷平衡運(yùn)輸問題，若

29、用u1,u2,um分別表示前m個約束等式相對應(yīng)的對偶變量，用v1,v2vn 分別表示后n個等式相對應(yīng)的對偶變量，即有對偶向量第75頁/共116頁這時可將運(yùn)輸問題的對偶規(guī)劃寫成：的符號不限jiijjinjjjmiiivunjmicvustvbuaZ,.1,.1.max11前面學(xué)習(xí)知道，線性規(guī)劃問題變量xj的檢驗數(shù)可表示為：1jjjBjjjjczcc B PcYP第76頁/共116頁由此可寫出運(yùn)輸問題某變量xij(對應(yīng)于運(yùn)輸表中(Ai,Bj)的檢驗數(shù)如下：1212(,., ,.)()ijijijijijmijijjjniiczcYPcu uuv vvPcuv其中 分別稱為行位勢、列位勢。jivu

30、,有基變量所對應(yīng)的檢驗數(shù)為零，可從m+n-1個等式0)(jiijvuc（2.2）解出所有的行位勢、列位勢。（2.1）第77頁/共116頁可以證明，不論令 為何值， 始終不變。avi)(jivu 即 將不會隨 的取值而改變。 ijiv為此，在求解方程組（2.2）時，為計算簡便，可指定一個位勢等于一個較小的整數(shù)或零。第78頁/共116頁 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv10410392jiijvuc行位勢列位勢設(shè)u1=1第79頁/共116頁當(dāng)然，也可用采用解方程組的辦法來求位勢：13142

31、12332344112356uvuvuvuvuvuv兩種方法任選一種第80頁/共116頁 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv1041039212111012)(jiijijvuc第81頁/共116頁三。解的改進(jìn)（用閉回路法調(diào)整）選擇進(jìn)基變量的原則：,min|0Nklijiji j J即選擇非基變量中檢驗數(shù)最小的一個進(jìn)基。在進(jìn)基格點(diǎn)所對應(yīng)的閉回路上，定義頂點(diǎn)的序號：自進(jìn)基格點(diǎn)起選定一個方向（比如順時針方向），依次為第一格、第二格、在奇數(shù)格點(diǎn)上增加調(diào)整量 ，在偶數(shù)格點(diǎn)上減少調(diào)整量 。第82

32、頁/共116頁其中調(diào)整量為),( |minjixij為閉回路中偶數(shù)格點(diǎn)第83頁/共116頁 銷地產(chǎn)地產(chǎn)量 41241116821039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv104103921211012210602222第84頁/共116頁 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309jiijvuc)(jiijijvuc第85頁/共116頁四。表上作業(yè)法計算中的兩個問題 無窮多個最優(yōu)解若在最優(yōu)解中，某個非基變量

33、的檢驗數(shù)為零，則該問題有無窮多個最優(yōu)解此時得到一個最優(yōu)解：,1213x, 414x, 821x, 224x,1432x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz244685149228114412第86頁/共116頁 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309第87頁/共116頁 銷地產(chǎn)地產(chǎn)量 412124111621039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039

34、134284444第88頁/共116頁 銷地產(chǎn)地產(chǎn)量 441212411164210369108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121390第89頁/共116頁此時得另一個最優(yōu)解：, 411x,1213x, 421x, 624x,1432x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz24468514962441244 退化情況與一般LP問題類似，運(yùn)輸問題也可能出現(xiàn)退化了的基本可行解。有以下兩種情況：第90頁/共116頁（1）在確定初始基本可行解時，若已確定在空格）在確定初始基本可行解時，

35、若已確定在空格 處處),(ji要添上調(diào)運(yùn)量要添上調(diào)運(yùn)量 ，而此時發(fā)點(diǎn)的當(dāng)前可發(fā)送量與收點(diǎn)的當(dāng)，而此時發(fā)點(diǎn)的當(dāng)前可發(fā)送量與收點(diǎn)的當(dāng)前需求量恰好相等。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收前需求量恰好相等。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收點(diǎn)的需求量已全部滿足。因此應(yīng)同時劃掉發(fā)送的行及接受的點(diǎn)的需求量已全部滿足。因此應(yīng)同時劃掉發(fā)送的行及接受的列。為了使調(diào)運(yùn)表上確保有列。為了使調(diào)運(yùn)表上確保有(m+n-1)個基變量的值，就需要在個基變量的值，就需要在所劃掉的行（或列）的任一空格添上調(diào)運(yùn)量所劃掉的行（或列）的任一空格添上調(diào)運(yùn)量0。這樣就得到有。這樣就得到有一個基變量取值為一個基變量取值為0的基本可行解的基本

36、可行解退化解。退化解。ijx例如：下表給出一個例如：下表給出一個34運(yùn)輸?shù)倪\(yùn)價及發(fā)送量與需求量。運(yùn)輸?shù)倪\(yùn)價及發(fā)送量與需求量。試用最小元素法求該問題的一個初始基本可行解。試用最小元素法求該問題的一個初始基本可行解。第91頁/共116頁 銷地產(chǎn)地產(chǎn)量3114577738121069銷 量3656481A2A1B2B3B4B3A表 4-26011634第92頁/共116頁此時得到一個退化了的初始基本可行解：, 012x, 113x, 614x, 423x, 331x, 632x其余變量全等于零。 在用閉回路調(diào)整當(dāng)前基本可行解時，有多個偶數(shù)格值相等且都是極小值點(diǎn) 。此時只能取一個離基，其余的仍作為基格

37、。例如：下表給出一個34運(yùn)輸問題的基本可行解及發(fā)送量與需求量、基本可行解的檢驗數(shù)。試用閉回路法對其做出調(diào)整。第93頁/共116頁 銷地產(chǎn)地產(chǎn)量 317339銷 量3646481A2A1B2B3B4B3A表 4-514112311633333333第94頁/共116頁 銷地產(chǎn)地產(chǎn)量 347369銷 量3646481A2A1B2B3B4B3A表 4-51411211033第95頁/共116頁3 運(yùn)輸問題的進(jìn)一步討論運(yùn)輸問題的進(jìn)一步討論一、產(chǎn)銷不平衡運(yùn)輸問題一、產(chǎn)銷不平衡運(yùn)輸問題對產(chǎn)銷不平衡問題，可轉(zhuǎn)化為平衡問題，然后按表上作業(yè)對產(chǎn)銷不平衡問題，可轉(zhuǎn)化為平衡問題，然后按表上作業(yè)法求解。轉(zhuǎn)換辦法：法求

38、解。轉(zhuǎn)換辦法： 若產(chǎn)大于銷，增加一個假想的銷地（可視為庫存地）其銷若產(chǎn)大于銷，增加一個假想的銷地（可視為庫存地）其銷量設(shè)定為余量，相應(yīng)的運(yùn)價設(shè)為量設(shè)定為余量，相應(yīng)的運(yùn)價設(shè)為0 0。 若銷大于產(chǎn)，增加一個虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為不足若銷大于產(chǎn)，增加一個虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為不足量，相應(yīng)的運(yùn)價也設(shè)為量，相應(yīng)的運(yùn)價也設(shè)為0 0。第96頁/共116頁例例4 某市有某市有3個造紙廠個造紙廠 ， 和和 ，有，有4個集中用戶個集中用戶 和和 ，各工廠的生產(chǎn)量、各用戶的需用量以及各，各工廠的生產(chǎn)量、各用戶的需用量以及各工廠到用戶的單位運(yùn)價（元工廠到用戶的單位運(yùn)價（元/t）示于表）示于表3-14中，問如何調(diào)運(yùn)

39、中，問如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最?。坎拍苁箍傔\(yùn)費(fèi)最?。?A2A3A1B,2B,3B4B第97頁/共116頁 銷地產(chǎn)地產(chǎn)量31234811259567159銷 量43561A2A1B2B3B4B3A表 3-142218可增加一個假想的銷地可增加一個假想的銷地5B第98頁/共116頁 銷地產(chǎn)地產(chǎn)量 31234081125905671509銷 量435641A2A1B2B3B4B3A表 3-145B第99頁/共116頁運(yùn)價運(yùn)價 地區(qū)地區(qū)煤礦煤礦甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量 A A B B C C161614141919131313132020222219192323171715152525505060605050最低需求最低需求最高需求最高需求30305050707070700 030301010不限不限第100頁/共116頁第101頁/共116頁運(yùn)價 地區(qū)煤礦甲1甲2乙丙丁1丁2產(chǎn)量 A B C D161419M1614190131320M2219230171225M1712250 50 60 50 50需求量302070301050 210210第102頁/共116頁運(yùn)價 地區(qū)煤礦甲1甲2