《運輸問題》ppt課件

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

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

3、位物品的運價是 ，問ijc怎樣調運這些物品才干使總運費最小？ 銷地產(chǎn)地產(chǎn)量銷 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama運價表 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當產(chǎn)銷平衡時，其模型如下：0,0,0ijijabc假設：當產(chǎn)大于銷時，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當產(chǎn)小于銷時，其模型是：min ()0ijijijiijjijijZc xxaxbabx 1 1、平衡運輸問題必有可行解，

4、也、平衡運輸問題必有可行解，也必有最優(yōu)解；必有最優(yōu)解；運輸問題數(shù)學模型的特點運輸問題數(shù)學模型的特點證明 記.11dbaminjji那么令dbaxjiij), 2 , 1;, 2 , 1(njmi那么 為運輸問題的一個可行解。現(xiàn)實上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一組可行解。ijx又由于總費用不會為負值存在下界。這闡明，運輸問題既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。 2 2、運輸問題約束條件的系數(shù)矩陣、運輸問題約束條件的系

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

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

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

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

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

10、爾(Vogel)法1。最小元素法思想：優(yōu)先滿足運價或運距最小的供銷業(yè)務。 銷地產(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此時得到一個初始調運方案初始可行解：,1013x, 614x, 821x, 223x,1432x, 834x其他變量全等于零?？傔\費為目的函數(shù)值3141ijijijxcz246685143228116410此解滿足一切約束條件，且基變量非零變量的個數(shù)為6等于m+n-1=3+4-1=6). 西北角

12、法西北角法是優(yōu)先滿足運輸表中西北角左上角上空格的供銷需求。 銷地產(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此時得到一個初始調運方案初始可行解：, 811x, 812x, 622x, 423x, 833x,1434x其他變量全等于零。

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

16、會呵斥很大的損失，故應盡量按最大罰數(shù)安排運輸。銷 地產(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此時得到一個初始調運方案初始可行解：,1213x, 414x, 821x, 224x3214,x, 834x其他變量全等于零。總運費為目的函數(shù)值3141ijijijxcz244685149228114412此解滿足一切約束條件，且基變量非零變量的個數(shù)為6等于m+n-1=3+4-1=6).比較上述三種方法給出的初始

18、基可行解，以沃格爾法給出的解的目的函數(shù)值最小，最小元素法次之，西北角法解的目的函數(shù)值最大。 普通說來，沃格爾法得出的初始解的質量最好，常用來作為運輸問題最優(yōu)解的近似值。 銷地產(chǎn)地產(chǎn)量 414681250837514銷 量6563201A2A1B2B3B4B3A課堂練習課堂練習表上作業(yè)法v計算步驟：v1、給出初始方案v2、檢驗能否最優(yōu)v3、調整調運方案 , Go to 2二、解的最優(yōu)性檢驗前面得到了初始基可行解，普通來說此解并非最優(yōu)。下面引見最優(yōu)性檢驗的兩種方法。1 閉回路法(Cycle method)2 對偶變量法dual variable method也稱為位勢法 閉回路法cycle met

19、hod)下面用最小元素法所確定的初始根本可行解來闡明。與單純性原理一樣，現(xiàn)目的是運費最少，故檢驗每一個非基變量對應于運輸表中的空格的檢驗數(shù)能否. 0ij?ij假設一切空格的檢驗數(shù)全非負，那么不論怎樣均不能使運輸費用降低，即目的函數(shù)值已無法改良，這個解就是最優(yōu)解 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A3A1B2B3B4B思索空格(A1,B1),想象由產(chǎn)地A1供應一個單位的物品給銷地B1，為使運入銷地B1的物品總量不大于它的銷量，應將A2運到B1的物品數(shù)量減1，即將格子A2,B1中填入的數(shù)字8改為7；另一方面，為使產(chǎn)地A2運出的物品

20、數(shù)量正好等于它的產(chǎn)量(保證新得到的解仍為基可行解)，應將A2運到B3的物品數(shù)量增1。同理A1運往B3的物品數(shù)量減1，A1運出的物品數(shù)量正好等于其產(chǎn)量按照上述想象，由產(chǎn)地A1供應1個單位物品給銷地B1,由此引起的總運費變化是：11212313c -c +c -c= 4-2+3-4 =1根據(jù)檢驗數(shù)的定義，它正是非基變量x11(或者說空格(A1,B1)的檢驗數(shù)定義1：基變量有數(shù)字的對應的格為基格；非基變量空格對應的頂點為非基格。定義2：從每一空格非基格出發(fā)，沿程度或垂直方向前進，每碰到數(shù)字格轉90o有些情況也可以不改動方向繼續(xù)前進，直到回到出發(fā)的空格為止，由此構成的封鎖的折線稱為閉回路。規(guī)定：起始頂

21、點的空格為第一頂點，那么 =閉回路上奇數(shù)次頂點運價之和 閉回路上偶數(shù)次頂點運價之和 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檢驗數(shù)中有負數(shù)，闡明原方案不是最優(yōu)解。 對偶變量法位勢法(dual variable method) 用閉回路法斷定一個運輸方案能否最優(yōu)，需求找出一切空格的閉回路，并計算其檢驗數(shù)。當運輸問題的產(chǎn)地和銷地很多時，空格的數(shù)目很大，計算檢驗數(shù)的任務量很大，而用對偶變量法就簡便得多。nmvvvuuuY.2121 對產(chǎn)銷平衡運輸問題，假設用u1,u2,um分別表示前m個約束等式相對應的對偶變量，用v1,v2vn

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

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

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

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

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

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

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

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

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

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

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

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

37、。需不平衡，因此，添加一項閑置才干。建模：建模： 本錢本錢 交貨交貨消費消費 閑置閑置 1 2 3 4 才干才干產(chǎn)量產(chǎn)量1季度正常消費季度正常消費2季度正常消費季度正常消費3季度正常消費季度正常消費3季度加班消費季度加班消費4季度正常消費季度正常消費4季度加班消費季度加班消費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結果：結果： 消費消費 交貨交貨消費消費 閑置閑置 1 2 3 4 才干才干產(chǎn)量產(chǎn)量1季度正常消費季度正常消費2季度正常消費季度正常消費3季度正常消費季度正常消費3季度加班消費季度加班消