運籌學運輸問題表上作業(yè)法

1、運 籌 學,李細霞2013物流工程1班2014~2015學年第二學期,課程主要內容,Transportation problem,3,第三章 運輸問題,學習目標,主要內容,思考,運輸問題要解決什么？什么叫一個運輸方案？什么叫一個最優(yōu)的運輸方案？若用xij表示從Si到Dj的運量，那么在產銷平衡的條件下，求總運費最小的方案。,問題描述,7,表格模型,,8,生產量：A1-7噸， A2-4噸， A3-9噸銷售量：B1-3噸，B

2、2-6噸，B3-5噸，B4-6噸,舉例,產銷平衡？,9,調運示意圖,10,此問題是線性規(guī)劃問題嗎？,請建立此問題的模型,目標？約束條件？,思考,11,二、建立模型,設：xij——第i產地到第j銷地之間的調運量，則有,Min z = ? ? cij· xij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij?0,(i=1,2,┄,3；j=1,2,┄,4),,,產量限制,銷量限制,x2

3、1+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,可否用單純形法求解？,12,??ai=?bj,產銷平衡運輸問題的一般表示,,13,調運模型為：,,m×n個變量,m個約束,n個約束,共有m+n個約束條件？,,14,約束條件展開,15,約束條件的系數矩陣,有何特點？,16,1.變量數：m?n個2.約束方程數：m+n個 最大

4、獨立方程數：m+n-13.系數列向量結構：,產銷平衡運輸問題模型的特點,Why?,0…1.1.0,17,,,定理,平衡條件下的運輸問題一定有最優(yōu)解,唯一最優(yōu)解？無窮多最優(yōu)解？,18,基本可行解,檢驗數,基變換,用單純形法求解線性規(guī)劃問題的步驟,表上作業(yè)法,19,單純形法在求解運輸問題時的一種簡化方法,,20,1.西北角法 2.最小元素法3.伏格爾法,,1.閉回路法2.位勢法,,閉回路法,,表上作業(yè)法步驟,舉例,,,

5、,產量,,,,,產地,銷地,A1 A2 A3,B1 B2 B3 B4,銷量,4,1,3,10,2,5,3 6 5 6,7 4 9,3,11,9,8,7,10,運價,總產=總銷,22,23,西北角法,3,4,2,2,3,6,有何疑問？,24,西北角法的優(yōu)劣？,太簡單咯！,最優(yōu)解有點望塵莫及呢,25,幾點疑問,為什么要從西北角開始？,為什么每次填數一定要填最大允許量，然后劃掉一行（或一列）？,為什么有數

6、格只有6個？（總共有12個格）,26,基本可行解,一個基本可行解：有m+n-1個基變量（有數格），其余為非基變量（空格）,m+n-1個變量不能構成閉回路,充要條件,運輸問題的m+n個約束方程中，有且只有m+n-1個有效方程,舉例,下面這些有數格組成了閉回路（不能作為基本可行解）,什么是閉回路？,下面這些有數格沒有組成閉回路（可以作為基本可行解）,29,幾點疑問的解答,為什么要從西北角開始？,為什么每次填數一定要填最大允許量，然后劃掉一

7、行（或一列）,為什么有數格只有6個？（總共有12個格）,m+n-1個變量不能構成閉回路,只有6個有數格,基變量的個數為m+n-1（3+4-1）,,,,30,所有問題答案歸結一句話：保證初始方案是運輸問題（線性規(guī)劃問題）的基本可行解,Why？隨便一個可行解不行么？,31,最小元素法,3,11,3,10,1,9,2,8,7,4,10,5,3,1,4,6,3,3,32,最小元素法的優(yōu)劣？,也很簡單哦,最優(yōu)解可望，但還是有一定距離的,33,伏

8、格爾法,34,,,,,,,產地,銷地,A1 A2 A3,B1 B2 B3 B4,行差額,列差額,3 11 3 10 1 9 2 8 7 4 10 5,0 1 1,2 5 1 3,,0 1 2,2 - 1 3,,0 1 -,2 - 1 2,,7 6 -,- - 1 2,,,Vogel法:,,,,,,,,產地,銷地,A1 A2 A3,B1 B2

9、B3 B4,7 4 9,產量,銷量,3 6 5 6,6,3,5,2,1,3,產銷平衡表,單位運價表,伏格爾法（差額法）,對最小元素法的改進,35,伏格爾法的優(yōu)劣？,離最優(yōu)解貌似很近了哦,求解過程有點麻煩呢！,用Vogel法求出的初始解叫做“近似最優(yōu)解”,36,課堂練習：用最小元素法求初始解,37,只有5個有數格，不是基本可行解嗎？,5,3,4,1,7,課堂練習答案,38,應用舉例：用最小元素法或伏格爾法求初始解,,“總

10、利潤最大”而不是“運費最小”，“最小元素”怎么找？,39,最優(yōu)性檢驗——閉回路法,表示什么？,每個空格都能找到閉回路嗎？有的話，是否唯一？,每個空格有且只有一條閉回路！,46,如何判斷初始方案是否達到最優(yōu)？,若存在某些檢驗數小于0，則說明調整后運價將減少。（不是最優(yōu)解） 若存在某些檢驗數等于0，則說明調整后運價將不發(fā)生改變。（多個最優(yōu)解）若所有檢驗數大于0，說明調整后運價將增加。（唯一最優(yōu)解）,最優(yōu)方案：所有檢驗數≥0,注意是目標最

11、小化的問題,思考,如果將運輸問題的運價表改為利潤表，則應如果求初始方案，如何判斷方案是否最優(yōu)？,48,最優(yōu)性檢驗——位勢法（對偶變量法）,設 U1,U2,…Um,V1, V2,…, Vn 是對應m+n個約束條件的對偶變量其中Ui對應第i個產地的產量約束， Vj對應第j個銷地的銷量約束稱Ui為行位勢， Vj為列位勢,49,2. 令u1=0，則依cij=ui+vj 計算各ui和vj,3.計算空格處位勢；?ij=cij-（ui+vj）

12、,1.在表中增加一行一列,填上行位勢ui,列位勢vj, 在對應初始方案有數格處寫0（基變量檢驗數為0）；,位勢法的圖表形式:,,,,ui,,,,,產地,銷地,A1 A2A3,B1 B2 B3 B4,vj,,u3=-5,3,11,3,10,1,9,2,8,7,4,10,5,0,0,0,0,0,0,v3=3,v4=10,u1=0,u2=-1,v1=2,v2=9,1,2,1,-1,10,12,50,,,位勢法計算非基

13、變量xij檢驗數的公式 σij=cij-（ui+vj）,比較檢驗數計算的兩種方法,51,52,三、方案改進（閉回路法）當至少有一個非基變量的檢驗數是負值時，說明作業(yè)表上當前的調運方案不是最優(yōu)的，應進行調整。 步驟：1.若檢驗數σij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路，并求出調整量θ,若有多個檢驗數小于零，則取其中最小的負數,53,繼續(xù)上例，因σ24= -1 ，畫出以x24為起始變量的閉回路,54,

14、,?計算調整量： θ =Min（3，1）=12. 按照下面的方法調整調運量： 閉回路上，奇數次頂點的調運量減去θ ，偶數次頂點（包括起始頂點）的調運量加上θ ；閉回路之外的變量調運量不變。,55,3. 得到調整后的調運方案：,4.計算新方案的檢驗數，重復上述步驟，直至所有檢驗數都 ≥0，即得到最優(yōu)方案。,56,最優(yōu)調運方案,,相應的最小總運費為：,運輸問題的應用,產銷不平衡問題生產與存儲問題轉運問題,,由于在變量個數相等

15、的情況下，表上作業(yè)法的計算遠比單純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運輸問題的數學模型。下面介紹幾個典型的例子。,設有三個化肥廠(A，B，C)供應四個地區(qū)(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農用化肥。各化肥廠年產量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示。試求出總的運費最節(jié)省的化肥調撥方案。,產銷不平衡問題,,,,這是一個產銷不平衡的運輸問題，總產量為160萬噸，四個地區(qū)的最低需求為110

16、萬噸，最高需求為無限。根據現(xiàn)有產量，第Ⅳ個地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于產量。為了求得平衡，在產銷平衡表中增加一個假想的化肥廠D，其年產量為50萬噸。由于各地區(qū)的需要量包含兩部分，如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應運價為M(任意大正數)，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應運價為0。對凡是需求分兩種情況的地區(qū)，實際上可按照兩個地

17、區(qū)看待。這樣可以寫出這個問題的產銷平衡表和單位運價表。,產銷平衡表,單位運價表,根據表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案,請簡單描述此方案,生產與儲存問題,某廠按合同規(guī)定須于當年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如表所示。又如果生產出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用0.15萬元。要求在完成合同的情況下，作出使該廠全年生產費用(包括儲

18、存、維護費用) 最小的方案。,解：由于每個季度生產出來的柴油機不一定當季交貨，所以設xij為第i季度生產的用于第j季度交貨的柴油機數。根據合同要求，必須滿足,又每季度生產的用于當季和以后各季交貨的柴油機數不可能超過該季度的生產能力，故又有：,第i季度生產的用于j季度交貨的每臺柴油機的實際成本cij應該是該季度單位成本加上儲存、維護等費用。cij的具體數值見下表：,設用ai表示該廠第i季度的生產能力，bj表示第i季度的合同供應量，則問題可

19、寫成：,目標函數：約束條件：,顯然，這是一個產大于銷的運輸問題模型。注意到這個問題中當i＞j時，xij=0，所以應令對應的cij=M，再加上一個假想的需求D，就可以把這個問題變成產銷平衡的運輸模型，并寫出產銷平衡表和單位運價表(合在一起，見下表)。,經用表上作業(yè)法求解，可得多個最優(yōu)方案，下表是最優(yōu)方案之一。,即第Ⅰ季度生產25臺，10臺當季交貨，15臺Ⅱ季度交貨；Ⅱ季度生產5臺，用于Ⅲ季度交貨；Ⅲ季度生產30臺，其中20臺于當季交貨

20、，10臺于Ⅳ季度交貨。Ⅳ季度生產10臺，于當季交貨。按此方案生產，該廠總的生產費用(包括儲存、維護費用)為773萬元。,轉運問題,①每個產地的產品不一定直接發(fā)運到銷售點，可以將其中幾個產地集中一起運；②運往各銷地的產品可以先運給其中幾個銷地，再轉運給其他銷地；③除產、銷地之外，中間還可以有幾個轉運站，在產地之間、銷地之間或產地與銷地間進行轉運。,71,產地：原產地、中間轉運站、轉運物資的銷地銷地：原銷地、中間轉運站、轉運物資的產地

21、如果是產銷不平衡問題，先通過增加虛擬的產地或銷地轉化為產銷平衡問題。設各轉運站轉運物資的數量均為總產量∑ ai（或總銷量∑ bj ）專職轉運站的產量和銷量均為∑ ai原產地Ai的產量均為（ai+∑ ai）原銷地Bj的銷量均為（ bj+∑ ai）將各條線路實際的運輸單價列成單位運價表，其中不可能的運輸其單位運價用M表示。,擴展運輸表的構建步驟,舉例：A、B兩個化肥廠每年各生產磷肥900萬噸和600萬噸，這些化肥要運到三個港口

22、，已知三個港口C、D、E每年能承擔的船運量分別為700、400、300萬噸，兩個工廠及三個港口之間單位運價如下表所示，為按需要把磷肥運到各港口，怎樣安排運輸才能使運費最少？,73,表1,表2,表3,產銷平衡運輸表的構建,F,發(fā)量,收量,900+1500=2400,600+1500=2100,1500,1500,1500,1500,1500,700+1500=2200,400+1500=1900,300+1500=1800,100,0,0

23、,0,0,0,將表2和表3合并為一張表（加上單位運價）,例：已知各產地、銷地、中間轉運站及相互之間每噸產品的運價如表所示，問在考慮到產銷地之間直接運輸和非直接運輸的各種可能方案的情況下，如何將三個廠每天生產的產品運往銷售地，使總的運費最少。,(1) 由于問題中所有產地、中間轉運站、銷地都可以看作產地，又可看作銷地。因此把整個問題當作有11個產地和11個銷地的擴大的運輸問題。(2) 對擴大的運輸問題建立單位運價表。方法將表中不可能的運輸

24、方案的運價用任意大的正數M代替。,(3) 所有中間轉運站的產量等于銷量。由于運費最少時不可能出現(xiàn)一批物資來回倒運的現(xiàn)象，所以每個轉運站的轉運數不超過20噸?？梢砸?guī)定T1，T2，T3，T4的產量和銷量均為20噸。由于實際的轉運量,可以在每個約束條件中增加一個松弛變量xii，xii相當于一個虛構的轉運站，意義就是自己運給自己。(20-xii)就是每個轉運站的實際轉運量，xii的對應運價cii=0。,(4) 擴大的運輸問題中原來的產地與銷地

25、因為也有轉運站的作用，所以同樣在原來產量與銷量的數字上加20噸，即三個廠每天糖果產量改成27，24，29噸，銷量均為20噸；四個銷售點的每天銷量改為23，26，25，26噸，產量均為20噸，同時引進xii作為松弛變量。,下面寫出擴大運輸問題的產銷平衡表與單位運價表，由于這是一個產銷平衡的運輸問題，所以可以用表上作業(yè)法求解(計算略),帶有約束的運輸問題及推廣應用,在某軍供點B1處有10車物資，4車運往A1點，6車運往A2點；在B2處有2車

26、物資運往A3點；在B3處有3車物資運往A4點。車隊只有兩輛卡車、兩輛加載車可供使用，空車送貨前集中在A0處, 并要求: 1) B2處兩車特種物資需要提前用加載車運往A3點；2)送完所有物資后，所有車輛返回到A0點。問如何運輸，才能使空車行駛里程最少？已知各供需點間的距離如表所示。,某航運公司承擔六個港口城市A、B、C、D、E、F的四條固定航線的物資運輸任務。已知各條航線的起點、終點城市及每天航班數見下表。,,假定各條航線使用相同型號的船

27、只，又各城市間的航程天數見下表：,又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應配備多少條船，才能滿足所有航線的運貨需求?,解 該公司所需配備船只分兩部分。(1) 載貨航程需要的周轉船只數。例如航線1，在港口E裝貨1天，E→D航程17天，在D卸貨1天，總計19天。每天3航班，故該航線周轉船只需57條。各條航線周轉所需船只數見表。,以上累計共需周轉船只數91條 .,(2) 各港口間調度所需船只數。有些港口每天到達船數多于需要

28、船數，例如港口D，每天到達3條，需求1條；而有些港口到達數少于需求數，例如港口B。各港口每天余缺船只數的計算見表。,為使配備船只數最少，應做到周轉的空船數為最少。因此建立以下運輸問題，其產銷平衡表見表。,單位運價表應為相應各港口之間的船只航程天數，見表。,用表上作業(yè)法求出空船的最優(yōu)調度方案,由表3-39知最少需周轉的空船數為2×1+13×1+5×1+17×1+3×1=40條。