運(yùn)籌學(xué)資料2運(yùn)輸問(wèn)題.ppt

1、運(yùn) 輸 規(guī) 劃 (Transportation Problem,運(yùn)輸規(guī)劃的數(shù)學(xué)模型,表上作業(yè)法,產(chǎn)銷不平衡的運(yùn)輸問(wèn)題,3-1 運(yùn)輸問(wèn)題 問(wèn)題的提出 從m個(gè)發(fā)點(diǎn)A1, A2, .Am向n個(gè)收點(diǎn)B1, B2. Bn發(fā)送某種貨物。 Ai發(fā)點(diǎn)的發(fā)量為ai，Bj收點(diǎn)的收量為bj。由Ai 運(yùn)往Bj 單位貨物的運(yùn)費(fèi)為Cij，由Ai 運(yùn)往Bj 貨物的運(yùn)量為Xij。問(wèn)如何調(diào)配，才能使運(yùn)費(fèi)最省,當(dāng)發(fā)點(diǎn)的發(fā)量總和為 ai，收點(diǎn)的收量總和為 bj相等時(shí)，稱此運(yùn)輸問(wèn)題為平衡運(yùn)輸問(wèn)題。否則稱此運(yùn)輸問(wèn)題為非平衡運(yùn)輸問(wèn)題。若沒有特別說(shuō)明，均假定運(yùn)輸問(wèn)題為平衡的運(yùn)輸問(wèn)題,運(yùn)輸問(wèn)題的數(shù)學(xué)模型： 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,運(yùn)輸問(wèn)題的數(shù)學(xué)模型： 其中 ai 0, bj 0, cij 0 且共有 m+n 個(gè)約束方程。 并成立： ai = bj i j,運(yùn)輸問(wèn)題的圖表形式,運(yùn)輸問(wèn)題解的結(jié)構(gòu) 由于 ai = bj成立 i j 其m+n個(gè)約束方程并不是獨(dú)立的。實(shí)際上只有m+n-1個(gè)是獨(dú)立的。即約束方程系數(shù)矩陣的秩為m+n-1,3-2 運(yùn)輸問(wèn)題的求解 確定初始方案 1 西北角法,1）從圖的西北角開始，填入a1與b1較小的值， b1 =2，即從A1運(yùn)給B1 （2噸） B1已經(jīng)滿足，劃去b1列，并將a1=

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

4、）即A2優(yōu)先滿足B1 2個(gè)單位， B1 已經(jīng)滿足，劃去B1列,4）再?gòu)淖钚≡亻_始（4）即A2優(yōu)先滿足B2 4個(gè)單位， B2 A2已經(jīng)滿足，劃去B2列A2 行,4）最后把A3滿足B4 3個(gè)單位， 得到初始方案,5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3 總運(yùn)費(fèi)=3*3+4*1+4*2+4*4+8*3=61（元,3.差值法（伏格法） 每次從當(dāng)前運(yùn)價(jià)表上，計(jì)算各行各列中兩個(gè)運(yùn)價(jià)之差值（行差值hi，列差值kj），優(yōu)先取最大差值的行或列中最小的格來(lái)確定運(yùn)輸關(guān)系，直到求出初始方案,差值法初始方案如下： X13=3，X14=1，X21=2，X22=1，X24=3，X32=

5、3，費(fèi)用=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，總運(yùn)費(fèi)=6*2+5*2+4*2+7*3+5*1+8*3=80（元,最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3 總運(yùn)費(fèi)=3*3+4*1+4*2+4*4+8*3=61（元,西北角法得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，總運(yùn)費(fèi)=6*2+5*2+4*2+7*3+5*1+8*3=80（元） 最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=

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

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

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

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