《運(yùn)輸問題》ppt課件

1、運(yùn)輸問題v運(yùn)輸問題及其數(shù)學(xué)模型v運(yùn)輸問題的表上作業(yè)法v運(yùn)輸問題的進(jìn)一步討論例1：某部門有3個(gè)消費(fèi)同類產(chǎn)品的工廠產(chǎn)地，消費(fèi)的產(chǎn)品由4個(gè)銷售點(diǎn)銷地出賣，各工廠的消費(fèi)量、各銷售點(diǎn)的銷售量假定單位均為t以及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)元/t示于下表中要求研討產(chǎn)品如何調(diào)運(yùn)才干使總運(yùn)費(fèi)最小 4.1 運(yùn)輸問題及其數(shù)學(xué)模型單位 銷地 運(yùn)價(jià)產(chǎn)地產(chǎn)量2910291342584257銷量38464321 BBBB321AAAA2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地2910213428425運(yùn)輸問題網(wǎng)絡(luò)圖運(yùn)輸問題網(wǎng)絡(luò)圖 )4 . 3 . 2 . 1

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

3、位物品的運(yùn)價(jià)是 ，問ijc怎樣調(diào)運(yùn)這些物品才干使總運(yùn)費(fèi)最?。?銷地產(chǎn)地產(chǎn)量銷 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama運(yùn)價(jià)表 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：0,0,0ijijabc假設(shè)：當(dāng)產(chǎn)大于銷時(shí)，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)小于銷時(shí)，其模型是：min ()0ijijijiijjijijZc xxaxbabx 1 1、平衡運(yùn)輸問題必有可行解，

4、也、平衡運(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那么 為運(yùn)輸問題的一個(gè)可行解?，F(xiàn)實(shí)上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一組可行解。ijx又由于總費(fèi)用不會(huì)為負(fù)值存在下界。這闡明，運(yùn)輸問題既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。 2 2、運(yùn)輸問題約束條件的系數(shù)矩陣、運(yùn)輸問題約束條件的系

5、數(shù)矩陣運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)對(duì)運(yùn)輸問題數(shù)學(xué)模型的構(gòu)造約束加以整理，可知其系數(shù)矩陣具有下述方式：m行n行1運(yùn)輸問題是一個(gè)具有mn個(gè)變量和n+m個(gè)等型約束的線性規(guī)劃問題。 41mnmmnnxxxxxxxxx,;,212222111211jmiijeep), 2 , 1;, 2 , 1(njmi() 1() 1() 1000110000101000ijimjmnmnmnpee2運(yùn)輸問題約束方程組的系數(shù)矩陣是一個(gè)只需0和1兩個(gè)數(shù)值的稀疏矩陣,其中1的總數(shù)為 2mn 個(gè)。3、約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也出

6、現(xiàn)一次4、約束條件系數(shù)矩陣的秩是m+n-1。即運(yùn)輸問題的基變量總數(shù)是m+n-1證明：因A的前m行對(duì)應(yīng)元素的和與后n行對(duì)應(yīng)元素的和相等，恰好都是：nmE) 1 , 1 , 1 (1所以A的行向量是線性相關(guān)的。從而 r(A)m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1階子式1112121311|00010000001000000110100111010000001000nmDp pp ppp 所以 r(A)=m+n-1.對(duì)于產(chǎn)銷平衡運(yùn)輸問題，除了上述特點(diǎn)外，還有以下特點(diǎn)： 1 一切構(gòu)造約束條件都是等式約束 2 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和 3 3、運(yùn)輸問題的解、運(yùn)輸問題的解運(yùn)輸

7、問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題是一種線性規(guī)劃問題。前面講述的單純形法是求解線性規(guī)劃問題非常有效的普通方法，因此可用單純形法求解運(yùn)輸問題。但是當(dāng)用單純形法求解運(yùn)輸問題時(shí)，先得在每個(gè)約束條件中引入一個(gè)人工變量，這樣一來，即使對(duì)于m=3、n=4這樣簡(jiǎn)單的運(yùn)輸問題，變量數(shù)目也會(huì)到達(dá)19個(gè)之多。因此，我們利用運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)，引入了表上作業(yè)法來求解運(yùn)輸問題 4.2 用表上作業(yè)法求解運(yùn)輸問題表上作業(yè)法的根本思想：先設(shè)法給出一個(gè)初始方案,然后根據(jù)確定的判別準(zhǔn)那么對(duì)初始方案進(jìn)展檢查、調(diào)整、改良，直至求出最優(yōu)方案，如以下圖所示。初始化最優(yōu)性檢驗(yàn)迭代Iteration最優(yōu)？yesSTOPn

8、o這和單純形法的求解思想完全一致，但是詳細(xì)的作法那么更加簡(jiǎn)捷。例1 某部門有3個(gè)同類型的工廠產(chǎn)地，消費(fèi)的產(chǎn)品由4個(gè)銷售點(diǎn)出賣，各工廠的消費(fèi)量、各銷售點(diǎn)的銷售量假定單位為t以及各工廠到銷售點(diǎn)的單位運(yùn)價(jià)元/t示于表4-2中，問如何調(diào)運(yùn)才干使總運(yùn)費(fèi)最??？ 銷地產(chǎn)地產(chǎn)量4124111621039108511622銷 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4 , 3 , 2 ,

9、1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij該運(yùn)輸問題的數(shù)學(xué)模型為：可以證明：約束矩陣的秩 r (A) = m +n -1.基變量的個(gè)數(shù)為 m+n-1.表上作業(yè)法v計(jì)算步驟：v1、給出初始方案v2、檢驗(yàn)?zāi)芊褡顑?yōu)v3、調(diào)整調(diào)運(yùn)方案 , Go to 2表上作業(yè)法v計(jì)算步驟：v1、給出初始方案v2、檢驗(yàn)?zāi)芊褡顑?yōu)v3、調(diào)整調(diào)運(yùn)方案 , Go to 2下面引見三種常用的方法。一、給出運(yùn)輸問題的初始可行解初始調(diào)運(yùn)方案l最小元素法l西北角法l沃格

10、爾(Vogel)法1。最小元素法思想：優(yōu)先滿足運(yùn)價(jià)或運(yùn)距最小的供銷業(yè)務(wù)。 銷地產(chǎn)地產(chǎn)量 4124111610398511622銷 量141214481A2A1B2B3B4B3A表 3-2228810 銷地產(chǎn)地產(chǎn)量 412411162109108511622銷 量 81414481A2A1B2B3B4B3A表 3-23210128 銷地產(chǎn)地產(chǎn)量 412112109108511622銷 量 8141214481A2A1B2B3B4B3A表 3-232104161068 銷地產(chǎn)地產(chǎn)量 4121182109108116銷 量 81214481A2A1B2B3B4B3A表 3-2321041610651

11、422148 銷地產(chǎn)地產(chǎn)量 412118210910811銷 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146 銷地產(chǎn)地產(chǎn)量 4128210910811銷 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611此時(shí)得到一個(gè)初始調(diào)運(yùn)方案初始可行解：,1013x, 614x, 821x, 223x,1432x, 834x其他變量全等于零。總運(yùn)費(fèi)為目的函數(shù)值3141ijijijxcz246685143228116410此解滿足一切約束條件，且基變量非零變量的個(gè)數(shù)為6等于m+n-1=3+4-1=6). 西北角

12、法西北角法是優(yōu)先滿足運(yùn)輸表中西北角左上角上空格的供銷需求。 銷地產(chǎn)地產(chǎn)量41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281611x 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281688 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量1214481A2A1B2B3B4B3A表 3-28168812x14 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-2816886 銷地產(chǎn)地產(chǎn)量 4124112

13、10398511622銷 量141214481A2A1B2B3B4B3A表 3-281688622x10 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-28168861064 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量1414481A2A1B2B3B4B3A表 3-2816886106423x12 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-281688610648 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4

14、B3A表 3-2816886106432x822 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064822814 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量1412481A2A1B2B3B4B3A表 3-2816886106482281434x14 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064822814此時(shí)得到一個(gè)初始調(diào)運(yùn)方案初始可行解：, 811x, 812x, 622x, 423x, 833x,1434x其他變量全等于零。

15、總運(yùn)費(fèi)為目的函數(shù)值3141ijijijxcz3726141183410612848此解滿足一切約束條件，且基變量非零變量的個(gè)數(shù)為6等于m+n-1=3+4-1=6). 沃格爾Vogel)法初看起來，最小元素法非常合理。但是，有時(shí)按某一最小單位運(yùn)價(jià)安排物品調(diào)運(yùn)時(shí)，卻能夠?qū)е虏坏貌徊捎眠\(yùn)費(fèi)很高的其他供銷點(diǎn)，從而使整個(gè)運(yùn)輸費(fèi)用添加。沃格爾法的思想： 對(duì)每一個(gè)供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià)，并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(shù)。假設(shè)罰數(shù)的值不大，當(dāng)不能按最小運(yùn)價(jià)安排運(yùn)輸時(shí)呵斥的運(yùn)費(fèi)損失不大；反之，假設(shè)罰數(shù)的值很大，不按最小運(yùn)價(jià)組織運(yùn)輸就

16、會(huì)呵斥很大的損失，故應(yīng)盡量按最大罰數(shù)安排運(yùn)輸。銷 地產(chǎn)地產(chǎn)量行罰數(shù)1234124111602103910181161銷 量8121448列罰數(shù)12513231A2A1B2B3B4B3A51422148銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 412411160021039101185112212銷 量8141248列罰數(shù)12513221331A2A1B2B3B4B3A8146146銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 41241116000103911185112212銷 量141248列罰數(shù)1251322133211A2A1B2B3B4B3A8146146281082銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 4121171039

17、6851122銷 量1448列罰數(shù)412561A2A1B2B3B4B3A814614628108241216124銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 412117010360851122銷 量1448列罰數(shù)4125 261A2A1B2B3B4B3A81461462810824121612494此時(shí)得到一個(gè)初始調(diào)運(yùn)方案初始可行解：,1213x, 414x, 821x, 224x3214,x, 834x其他變量全等于零?？傔\(yùn)費(fèi)為目的函數(shù)值3141ijijijxcz244685149228114412此解滿足一切約束條件，且基變量非零變量的個(gè)數(shù)為6等于m+n-1=3+4-1=6).比較上述三種方法給出的初始

18、基可行解，以沃格爾法給出的解的目的函數(shù)值最小，最小元素法次之，西北角法解的目的函數(shù)值最大。 普通說來，沃格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似值。 銷地產(chǎn)地產(chǎn)量 414681250837514銷 量6563201A2A1B2B3B4B3A課堂練習(xí)課堂練習(xí)表上作業(yè)法v計(jì)算步驟：v1、給出初始方案v2、檢驗(yàn)?zāi)芊褡顑?yōu)v3、調(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 met

19、hod)下面用最小元素法所確定的初始根本可行解來闡明。與單純性原理一樣，現(xiàn)目的是運(yùn)費(fèi)最少，故檢驗(yàn)每一個(gè)非基變量對(duì)應(yīng)于運(yùn)輸表中的空格的檢驗(yàn)數(shù)能否. 0ij?ij假設(shè)一切空格的檢驗(yàn)數(shù)全非負(fù)，那么不論怎樣均不能使運(yùn)輸費(fèi)用降低，即目的函數(shù)值已無法改良，這個(gè)解就是最優(yōu)解 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A3A1B2B3B4B思索空格(A1,B1),想象由產(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)出的物品

20、數(shù)量正好等于它的產(chǎn)量(保證新得到的解仍為基可行解)，應(yīng)將A2運(yùn)到B3的物品數(shù)量增1。同理A1運(yùn)往B3的物品數(shù)量減1，A1運(yùn)出的物品數(shù)量正好等于其產(chǎn)量按照上述想象，由產(chǎn)地A1供應(yīng)1個(gè)單位物品給銷地B1,由此引起的總運(yùn)費(fèi)變化是：11212313c -c +c -c= 4-2+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有些情況也可以不改動(dòng)方向繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此構(gòu)成的封鎖的折線稱為閉回路。規(guī)定：起始頂

21、點(diǎn)的空格為第一頂點(diǎn)，那么 =閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和 閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和 ij 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2143241323211111cccc1 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-221165121434321212cccc21 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-21341165

22、1023131434322222cccccc121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-21341192313142424cccc1121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-210611432834141323213131cccccc102111 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2124116111

23、314343333cccc12101121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-212111012檢驗(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ù)的任務(wù)量很大，而用對(duì)偶變量法就簡(jiǎn)便得多。nmvvvuuuY.2121 對(duì)產(chǎn)銷平衡運(yùn)輸問題，假設(shè)用u1,u2,um分別表示前m個(gè)約束等式相對(duì)應(yīng)的對(duì)偶變量，用v1,v2vn

24、 分別表示后n個(gè)等式相對(duì)應(yīng)的對(duì)偶變量，即有對(duì)偶向量這時(shí)可將運(yùn)輸問題的對(duì)偶規(guī)劃寫成：的符號(hào)不限jiijjinjjjmiiivunjmicvustvbuaZ,.1,.1.max11前面學(xué)習(xí)知道，線性規(guī)劃問題變量xj的檢驗(yàn)數(shù)可表示為：1jjjBjjjjczcc B PcYP由此可寫出運(yùn)輸問題某變量xij(對(duì)應(yīng)于運(yùn)輸表中(Ai,Bj)的檢驗(yàn)數(shù)如下：1212(,., ,.)()ijijijijijmijijjjniiczcYPcu uuv vvPcuv其中 分別稱為行位勢(shì)、列位勢(shì)。jivu ,有基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)為零，可從m+n-1個(gè)等式0)(jiijvuc2.2解出一切的行位勢(shì)、列位勢(shì)。2.1可以證

25、明，不論令 為何值， 一直不變。avi)(jivu 即 將不會(huì)隨 的取值而改動(dòng)。 ijiv為此，在求解方程組2.2時(shí)，為計(jì)算簡(jiǎn)便，可指定一個(gè)位勢(shì)等于一個(gè)較小的整數(shù)或零。 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv10410392jiijvuc行位勢(shì)列位勢(shì)設(shè)u1=1當(dāng)然，也可用采用解方程組的方法來求位勢(shì)：1314212332344112356uvuvuvuvuvuv兩種方法任選一種 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3

26、B4B3A表 3-2iujv1041039212111012)(jiijijvuc三。解的改良用閉回路法調(diào)整選擇進(jìn)基變量的原那么：,min|0Nklijiji j J即選擇非基變量中檢驗(yàn)數(shù)最小的一個(gè)進(jìn)基。在進(jìn)基格點(diǎn)所對(duì)應(yīng)的閉回路上，定義頂點(diǎn)的序號(hào)：自進(jìn)基格點(diǎn)起選定一個(gè)方向比如順時(shí)針方向，依次為第一格、第二格、在奇數(shù)格點(diǎn)上減少調(diào)整量 ，在偶數(shù)格點(diǎn)上添加調(diào)整量 。其中調(diào)整量為),( |minjixij為閉回路中偶數(shù)格點(diǎn) 銷地產(chǎn)地產(chǎn)量 41241116821039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv1041039212110122106022

27、22 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309jiijvuc)(jiijijvuc四。表上作業(yè)法計(jì)算中的兩個(gè)問題 無窮多個(gè)最優(yōu)解假設(shè)在最優(yōu)解中，某個(gè)非基變量的檢驗(yàn)數(shù)為零，那么該問題有無窮多個(gè)最優(yōu)解此時(shí)得到一個(gè)最優(yōu)解：,1213x, 414x, 821x, 224x,1432x, 834x其他變量全等于零?？傔\(yùn)費(fèi)為目的函數(shù)值3141ijijijxcz244685149228114412 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷

28、量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309 銷地產(chǎn)地產(chǎn)量 412124111621039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039134284444 銷地產(chǎn)地產(chǎn)量 441212411164210369108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121390此時(shí)得另一個(gè)最優(yōu)解：, 411x,1213x, 421x, 624x,1432x, 834x其他變量全等于零。總運(yùn)費(fèi)為目的函數(shù)值3141ijijijxcz24

29、468514962441244 退化情況與普通LP問題類似，運(yùn)輸問題也能夠出現(xiàn)退化了的根本可行解。有以下兩種情況：1在確定初始根本可行解時(shí)，假設(shè)已確定在空格 處),(ji要添上調(diào)運(yùn)量 ，而此時(shí)發(fā)點(diǎn)的當(dāng)前可發(fā)送量與收點(diǎn)的當(dāng)前需求量恰好相等。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收點(diǎn)的需求量已全部滿足。因此應(yīng)同時(shí)劃掉發(fā)送的行及接受的列。為了使調(diào)運(yùn)表上確保有(m+n-1)個(gè)基變量的值，就需求在所劃掉的行或列的任一空格添上調(diào)運(yùn)量0。這樣就得到有一個(gè)基變量取值為0的根本可行解退化解。ijx例如：下表給出一個(gè)34運(yùn)輸?shù)倪\(yùn)價(jià)及發(fā)送量與需求量。試用最小元素法求該問題的一個(gè)初始根本可行解。 銷地產(chǎn)地產(chǎn)量3114577

30、738121069銷 量3656481A2A1B2B3B4B3A表 4-26011634此時(shí)得到一個(gè)退化了的初始根本可行解：, 012x, 113x, 614x, 423x, 331x, 632x其他變量全等于零。 在用閉回路調(diào)整當(dāng)前根本可行解時(shí)，有多個(gè)偶數(shù)格值相等且都是極小值點(diǎn) 。此時(shí)只能取一個(gè)離基，其他的仍作為基格。例如：下表給出一個(gè)34運(yùn)輸問題的根本可行解及發(fā)送量與需求量、根本可行解的檢驗(yàn)數(shù)。試用閉回路法對(duì)其做出調(diào)整。 銷地產(chǎn)地產(chǎn)量 317339銷 量3646481A2A1B2B3B4B3A表 4-514112311633333333 銷地產(chǎn)地產(chǎn)量 347369銷 量3646481A2A

31、1B2B3B4B3A表 4-514112110333 運(yùn)輸問題的進(jìn)一步討論一、產(chǎn)銷不平衡運(yùn)輸問題對(duì)產(chǎn)銷不平衡問題，可轉(zhuǎn)化為平衡問題，然后按表上作業(yè)法求解。轉(zhuǎn)換方法： 假設(shè)產(chǎn)大于銷，添加一個(gè)假想的銷地可視為庫存地其銷量設(shè)定為余量，相應(yīng)的運(yùn)價(jià)設(shè)為0。 假設(shè)銷大于產(chǎn)，添加一個(gè)虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為缺乏量，相應(yīng)的運(yùn)價(jià)也設(shè)為0。例4 某市有3個(gè)造紙廠 ， 和 ，有4個(gè)集中用戶 和 ，各工廠的消費(fèi)量、各用戶的需用量以及各工廠到用戶的單位運(yùn)價(jià)元/t示于表3-14中，問如何調(diào)運(yùn)才干使總運(yùn)費(fèi)最??？1A2A3A1B,2B,3B4B 銷地產(chǎn)地產(chǎn)量31234811259567159銷 量43561A2A1B2B3B

32、4B3A表 3-142218可添加一個(gè)假想的銷地5B 銷地產(chǎn)地產(chǎn)量 31234081125905671509銷 量435641A2A1B2B3B4B3A表 3-145B補(bǔ)充：閉回路的數(shù)學(xué)定義定義：凡是能排成1 112222311 12 122321,.,.,ssssssi ji ji ji ji ji ji ji ji ji ji ji jxxxxxxxxxxxx或方式的變量的集合稱為一個(gè)閉回路，并將這些變量稱為這個(gè)閉回路的頂點(diǎn)。由此可以看出閉回路的幾何特點(diǎn)：閉回路都是一條封鎖折線，每個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn)每一行或每一列只需且僅有兩個(gè)頂點(diǎn)格子每?jī)蓚€(gè)頂點(diǎn)格子的連線都是程度的或垂直的?？梢宰C明的一個(gè)

33、重要結(jié)論：m+n-1個(gè)變量構(gòu)成基變量的充要條件是它不含閉回路，即不存在以這些變量為頂點(diǎn)的閉回路例題例題5：彈性需求問題：彈性需求問題v設(shè)有三煤礦供應(yīng)四地域，資料如下：設(shè)有三煤礦供應(yīng)四地域，資料如下：運(yùn)價(jià)運(yùn)價(jià) 地域地域煤礦煤礦甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量 A B C161419131320221923171525506050最低需求最低需求最高需求最高需求3050707003010不限不限解題思緒：v設(shè)法轉(zhuǎn)化為規(guī)范型設(shè)法轉(zhuǎn)化為規(guī)范型v此題產(chǎn)量此題產(chǎn)量160萬噸，最低需求萬噸，最低需求110萬噸，最高需求無萬噸，最高需求無限。本質(zhì)上比較現(xiàn)實(shí)的最高需求限。本質(zhì)上比較現(xiàn)實(shí)的最高需求210萬噸萬噸v產(chǎn)量大于

34、最小需求；小于最大需求。而規(guī)范型是：產(chǎn)量大于最小需求；小于最大需求。而規(guī)范型是：產(chǎn)量產(chǎn)量=銷量。銷量。v處置方法：想象一個(gè)虛擬煤礦處置方法：想象一個(gè)虛擬煤礦D，消費(fèi)，消費(fèi)50萬噸，但萬噸，但這個(gè)產(chǎn)量只能供應(yīng)可有可無的最高需求部分，于是這個(gè)產(chǎn)量只能供應(yīng)可有可無的最高需求部分，于是各地的需求也應(yīng)分為兩個(gè)部分：根本需求、機(jī)動(dòng)需各地的需求也應(yīng)分為兩個(gè)部分：根本需求、機(jī)動(dòng)需求求v虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零，但它對(duì)于根本需求來講，虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零，但它對(duì)于根本需求來講，運(yùn)費(fèi)為無窮大。運(yùn)費(fèi)為無窮大。建模：運(yùn)價(jià) 地域煤礦甲1甲2乙丙丁1丁2產(chǎn)量 A B C D161419M1614190131320M221

35、9230171225M1712250 50 60 50 50需求量302070301050 210210最優(yōu)解：運(yùn)價(jià) 地域煤礦甲1甲2乙丙丁1丁2產(chǎn)量 A B C D30205020030103020 50 60 50 50 需求量302070301050 210210運(yùn)輸模型的運(yùn)用運(yùn)輸模型的運(yùn)用v例題例題5：某機(jī)床廠定下一年：某機(jī)床廠定下一年合同分別于各季度末交貨。合同分別于各季度末交貨。知各季度消費(fèi)本錢不同，知各季度消費(fèi)本錢不同，允許存貨，存儲(chǔ)費(fèi)允許存貨，存儲(chǔ)費(fèi)0.12萬元萬元/臺(tái)季，三、四季度可以加臺(tái)季，三、四季度可以加班消費(fèi)，加班消費(fèi)才干班消費(fèi)，加班消費(fèi)才干8臺(tái)臺(tái)/季，加班費(fèi)用季，加班

36、費(fèi)用3萬元萬元/臺(tái)臺(tái)季度正常消費(fèi)才干單位本錢萬元交貨臺(tái)數(shù)12343032202810.5510.81111.125301545分析：分析：v可用線性規(guī)劃，但用運(yùn)輸問題更簡(jiǎn)單可用線性規(guī)劃，但用運(yùn)輸問題更簡(jiǎn)單v要決策的問題是各季度消費(fèi)量和交貨量設(shè)要決策的問題是各季度消費(fèi)量和交貨量設(shè)xij表示第表示第i季度消費(fèi)第季度消費(fèi)第j季度交貨的臺(tái)數(shù)季度交貨的臺(tái)數(shù)v因加班時(shí)間消費(fèi)本錢不同，故要區(qū)別開來，因加班時(shí)間消費(fèi)本錢不同，故要區(qū)別開來，三四季度可加班，視同添加兩個(gè)季度三四季度可加班，視同添加兩個(gè)季度v需求量合計(jì)需求量合計(jì)115臺(tái)，消費(fèi)才干合計(jì)臺(tái)，消費(fèi)才干合計(jì)126臺(tái)，供臺(tái)，供需不平衡，因此，添加一項(xiàng)閑置才干

37、。需不平衡，因此，添加一項(xiàng)閑置才干。建模：建模： 本錢本錢 交貨交貨消費(fèi)消費(fèi) 閑置閑置 1 2 3 4 才干才干產(chǎn)量產(chǎn)量1季度正常消費(fèi)季度正常消費(fèi)2季度正常消費(fèi)季度正常消費(fèi)3季度正常消費(fèi)季度正常消費(fèi)3季度加班消費(fèi)季度加班消費(fèi)4季度正常消費(fèi)季度正常消費(fèi)4季度加班消費(fèi)季度加班消費(fèi)10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 0 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 126126結(jié)果：結(jié)果： 消費(fèi)消費(fèi) 交貨交貨消費(fèi)消費(fèi) 閑置閑置 1 2 3 4 才干才干產(chǎn)量產(chǎn)量1季度正常消費(fèi)季度正常消費(fèi)2季度正常消費(fèi)季度正常消費(fèi)3季度正常消費(fèi)季度正常消費(fèi)3季度加班消費(fèi)季度加班消