運籌學資料2運輸問題.ppt

1、運 輸 規(guī) 劃 (Transportation Problem,運輸規(guī)劃的數學模型,表上作業(yè)法,產銷不平衡的運輸問題,3-1 運輸問題 問題的提出 從m個發(fā)點A1, A2, .Am向n個收點B1, B2. Bn發(fā)送某種貨物。 Ai發(fā)點的發(fā)量為ai，Bj收點的收量為bj。由Ai 運往Bj 單位貨物的運費為Cij，由Ai 運往Bj 貨物的運量為Xij。問如何調配，才能使運費最省,當發(fā)點的發(fā)量總和為 ai，收點的收量總和為 bj相等時，稱此運輸問題為平衡運輸問題。否則稱此運輸問題為非平衡運輸問題。若沒有特別說明，均假定運輸問題為平衡的運輸問題,運輸問題的數學模型： Min S= cijxij i j

2、 xij =ai (i=1,2.m) j xij =bj (j=1,2n) i xij 0(i=1,2.m; j=1,2n,運輸問題的數學模型： 其中 ai 0, bj 0, cij 0 且共有 m+n 個約束方程。 并成立： ai = bj i j,運輸問題的圖表形式,運輸問題解的結構 由于 ai = bj成立 i j 其m+n個約束方程并不是獨立的。實際上只有m+n-1個是獨立的。即約束方程系數矩陣的秩為m+n-1,3-2 運輸問題的求解 確定初始方案 1 西北角法,1）從圖的西北角開始，填入a1與b1較小的值， b1 =2，即從A1運給B1 （2噸） B1已經滿足，劃去b1列，并將a1=

3、4-2=2,2）向a1，b1運價較大方向移動一格（或向右，或向下）此時向右移動一格（A1，B2）B2需要4噸，而A1只有2噸，A1已發(fā)完，劃去A1行，并把b2改成（4-2）=2,3）繼續(xù)進行,4）繼續(xù)進行,5）繼續(xù)進行,6）繼續(xù)進行,7）得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，總運費=6*2+5*2+4*2+7*3+5*1+8*3=80（元,2 最小元素法,1）從最小元素開始（3）即A1優(yōu)先滿足B3 3個單位， B3 已經滿足，劃去B3列,2）再從最小元素開始（4）即A1優(yōu)先滿足B4 1個單位， A1 已經滿足，劃去A1行,3）再從最小元素開始（4

4、）即A2優(yōu)先滿足B1 2個單位， B1 已經滿足，劃去B1列,4）再從最小元素開始（4）即A2優(yōu)先滿足B2 4個單位， B2 A2已經滿足，劃去B2列A2 行,4）最后把A3滿足B4 3個單位， 得到初始方案,5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3 總運費=3*3+4*1+4*2+4*4+8*3=61（元,3.差值法（伏格法） 每次從當前運價表上，計算各行各列中兩個運價之差值（行差值hi，列差值kj），優(yōu)先取最大差值的行或列中最小的格來確定運輸關系，直到求出初始方案,差值法初始方案如下： X13=3，X14=1，X21=2，X22=1，X24=3，X32=

5、3，費用=3*3+4*1+4*2+4*1+5*3+6*3=58（元,西北角法得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，總運費=6*2+5*2+4*2+7*3+5*1+8*3=80（元,最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3 總運費=3*3+4*1+4*2+4*4+8*3=61（元,西北角法得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，總運費=6*2+5*2+4*2+7*3+5*1+8*3=80（元） 最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=

6、4，X34=3，總運費=3*3+4*1+4*2+4*4+8*3=61（元） 差值法初始方案如下： X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，總運費=3*3+4*1+4*2+4*1+5*3+6*3=58（元,求最優(yōu)方案 1 閉回路 在初始調運方案表中，從任意空格出發(fā)，沿著縱向或橫向行進，遇到適當填有數據的方格90度轉彎，繼續(xù)行進，總能回到原來空格。這個封閉的曲線稱為閉回路。 可以證明：每個空格對應著唯一的閉回路,求最優(yōu)方案 1 閉回路 在初始調運方案表中，從任意空格出發(fā)，沿著縱向或橫向行進，遇到適當填有數據的方格90度轉彎，繼續(xù)行進，總能回到原來空格。這個封閉的曲線

7、稱為閉回路。 可以證明：每個空格對應著唯一的閉回路,如下表,如下表,如下表,如下表,求檢驗數 要判斷一個調運方案是否已是最優(yōu)，就要判斷方案所對應的基礎可行解是否最優(yōu)。在單純形法中，根據非基變量（空格）的檢驗數來判別的。若檢驗數中沒有正值，則已求得最優(yōu)。 如何根據初始調運表求得檢驗數,1） 閉回路法 空格Xij的檢驗數=（第奇數次拐角點運價之和減去第偶數次拐角點運價之和,空格X21的檢驗數= 6-5+4-4 = 1,空格X14的檢驗數=5-4+5-4 = 2,空格X31的檢驗數 = 6-5+4-5+8-7=1,檢驗數都為正值，原方案不是最優(yōu)解,2） 位勢法 對初始調運方案，定義一組新的變量（對偶

8、）ui和vj (i=1,2,m;j=1,2,n) 對于基變量Xij有： ui+vj=Cij 稱ui與vj為相應的各行與各列的位勢,u1+v1=6 u1+v2=5 u2+v2=4 u2+v3=7 u2+v4=5 u3+v4=8 有七個變量，但只有六個方程，有一個自由變量，一般令u1=0,u1+v1=6 u1+v2=5 u2+v2=4 u2+v3=7 u2+v4=5 u3+v4=8 一般令u1=0，求出解,空格（非基變量）的檢驗數 =（ui+vj)-Cij 與閉合回路法相同,調整方案 從一個方案調整到最優(yōu)方案的過程，就是單純形法的過程。 選擇檢驗數（一般取最大）為正值的空格所對應的變量為進基變量，

9、在進基變量的回路中，比較奇數拐角點的運量，選擇一個具有最小運量的基變量作為出基變量， 并調整運量=min(奇數拐角點的運量,選擇（A1，B3）（檢驗數最大）調整，最小運量=min(2,3)=2,最小運量=min(2,3)=2,奇數點減去2，偶數點加上2，得到新的方案?？傔\費=6*2+3*2+4*4+7*1+5*1+8*3=70（元） 原方案運費為80（元,繼續(xù)求檢驗數,繼續(xù)調整運量,繼續(xù)調整運量。最小運量=1 總運費=6*1+3*3+4*1+4*4+5*1+8*3=64（元,繼續(xù)計算檢驗數,繼續(xù)調整運量。最小運量=1,得到新的調運方案，總運費=3*3+4*1+4*2+4*4+8*3=61（元,繼續(xù)計算檢驗數,總運費=4*4+4*2+4*4+5*3=55（元,計算檢驗數：空格的檢驗數全為非正，此時是最優(yōu)解。 最優(yōu)調運方案：X21=2，X22=4，X14=4，X33=3。最小運費55（元,例3-1 某石油公司設有四個煉油廠，它們生產普通汽油，并為七個銷售區(qū)服務，生產和需求情況如下,從煉油廠運往第j個銷售區(qū)每公升汽油平均運費（單位：角/公升），應如何調運，使運費最省,解：平衡問題，用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素法求初始方案,用最小元素