運(yùn)籌學(xué)課件第三節(jié)運(yùn)輸問(wèn)題的進(jìn)一步討論

第三節(jié)運(yùn)輸問(wèn)題的進(jìn)一步討論一、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題供大于求供不應(yīng)求增加虛擬銷地

增加虛擬產(chǎn)地

產(chǎn)銷平衡的運(yùn)輸問(wèn)題對(duì)應(yīng)的運(yùn)價(jià)

？轉(zhuǎn)化各地之間的運(yùn)價(jià)在原問(wèn)題運(yùn)價(jià)表基礎(chǔ)上進(jìn)行擴(kuò)展：增加虛擬銷地，就地貯存的物品的不經(jīng)過(guò)運(yùn)輸，運(yùn)價(jià)等于零；增加虛擬產(chǎn)地，各個(gè)銷地所欠缺的物品，其運(yùn)價(jià)等于零；考慮轉(zhuǎn)運(yùn)，從一地運(yùn)往自身的單位運(yùn)價(jià)記為零或?yàn)樨?fù)；不存在運(yùn)輸線路的則記為M（一個(gè)足夠大的正數(shù)）；供應(yīng)大于需求：數(shù)學(xué)模型增加一個(gè)假想的目的地B1B2…BnBn+1(貯存)產(chǎn)量A1x11x12…x1nX1,n+1a1A2x21x22…x2nX2,n+1a2:::…:::Amxm1xm2…XmnXm,n+1am銷量b1b2…bn產(chǎn)地銷地c11c1nc2n000cmncm2cm1c22c21c12二、有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題特點(diǎn)是所調(diào)運(yùn)的物資不是由產(chǎn)地直接運(yùn)送到銷地，而是經(jīng)過(guò)若干中轉(zhuǎn)站送達(dá)。求解思路：轉(zhuǎn)化成一個(gè)等價(jià)的產(chǎn)銷平衡運(yùn)輸問(wèn)題，再用表上作業(yè)法求出最優(yōu)調(diào)運(yùn)方案。

第一步，將產(chǎn)地、轉(zhuǎn)運(yùn)點(diǎn)、銷地重新編排，轉(zhuǎn)運(yùn)點(diǎn)既作為產(chǎn)地又作為銷地；第二步，各地之間的運(yùn)價(jià)在原問(wèn)題運(yùn)價(jià)表基礎(chǔ)上進(jìn)行擴(kuò)展：從一地運(yùn)往自身的單位運(yùn)價(jià)記為零或?yàn)樨?fù)，不存在運(yùn)輸線路的則記為M（一個(gè)足夠大的正數(shù)）；第三步，由于經(jīng)過(guò)轉(zhuǎn)運(yùn)點(diǎn)的物資量既是該點(diǎn)作為銷地的需求量，又是該點(diǎn)作為產(chǎn)地時(shí)的供應(yīng)量，但事先又無(wú)法獲取該數(shù)量的確切值，因此通常將調(diào)運(yùn)總量作為該數(shù)值的上界。對(duì)于產(chǎn)地和銷地也作類似的處理。

例1:

某公司有A1、A2

兩個(gè)分廠生產(chǎn)某種產(chǎn)品，分別供應(yīng)B1、B2、B3

三個(gè)地區(qū)的銷售公司銷售。假設(shè)兩個(gè)分廠的產(chǎn)品質(zhì)量相同，假設(shè)有兩個(gè)中轉(zhuǎn)站T1、T2

，并且物資的運(yùn)輸允許在各產(chǎn)地、各銷地及各轉(zhuǎn)運(yùn)站之間，即可以在A1、A2、B1、B2、B3、T1、T2

之間相互轉(zhuǎn)運(yùn)。有關(guān)數(shù)據(jù)如下表所示，試求總費(fèi)用為最少的調(diào)運(yùn)方案。產(chǎn)地中轉(zhuǎn)站銷地產(chǎn)量A1A2T1T2B1B2B3產(chǎn)地A1

12131137A21

351929中轉(zhuǎn)T123

1284T2151

452銷地B13124

14B2119851

2B3324242

需求量475

產(chǎn)地、銷地及中轉(zhuǎn)站的有關(guān)數(shù)據(jù)、運(yùn)價(jià)（元/kg）

發(fā)送接受解：從表可以看出，從A1到B2直接運(yùn)費(fèi)單價(jià)為11元/kg；但從A1經(jīng)A2到B2，運(yùn)價(jià)為1+9=10元/kg；而從A1

經(jīng)T2

到B2只需l+5=6元/kg；若從A1

到A2

再經(jīng)B1到B2僅僅需l+1+1=3元/kg?？梢?jiàn)轉(zhuǎn)運(yùn)問(wèn)題比一般運(yùn)輸問(wèn)題復(fù)雜?，F(xiàn)在我們把此轉(zhuǎn)運(yùn)問(wèn)題化成一般運(yùn)輸問(wèn)題，要做如下處理：①由于問(wèn)題中的所有產(chǎn)地、中轉(zhuǎn)站、銷地都可以看成產(chǎn)地，也可以看成銷地，因此整個(gè)問(wèn)題可以看成一個(gè)有7個(gè)產(chǎn)地有7個(gè)銷地的擴(kuò)大的運(yùn)輸問(wèn)題；②對(duì)擴(kuò)大了的運(yùn)輸問(wèn)題建立運(yùn)價(jià)表，將表中不可能的運(yùn)輸方案用任意大的正數(shù)M代替；③所有中轉(zhuǎn)站的產(chǎn)量等于銷量，也即流入量等于流出量。每個(gè)中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量不會(huì)超過(guò)16kg，可以規(guī)定T1，T2的產(chǎn)量和銷量均為16kg。由于實(shí)際的轉(zhuǎn)運(yùn)量：這里si表示i點(diǎn)的流出量，dj表示j點(diǎn)的流入量，對(duì)中轉(zhuǎn)點(diǎn)來(lái)說(shuō)，因此si=dj=16。這樣可以在每個(gè)約束條件中增加一個(gè)松弛變量xii

，xii相當(dāng)于一個(gè)虛構(gòu)的中轉(zhuǎn)站，其意義就是自己運(yùn)給自己。(16-xii)就是每個(gè)中轉(zhuǎn)站的實(shí)際轉(zhuǎn)運(yùn)量，xii

的對(duì)應(yīng)運(yùn)價(jià)cii=0；④擴(kuò)大了的運(yùn)輸問(wèn)題中原來(lái)的產(chǎn)地與銷地由于也具有轉(zhuǎn)運(yùn)作用，所以同樣在原來(lái)的產(chǎn)量與銷量的數(shù)字上加上16kg，即兩個(gè)分廠的產(chǎn)量改為23、25kg，銷量均為16kg；三個(gè)銷地的每天銷量改為20、23、21kg，產(chǎn)量均為16kg，同時(shí)引進(jìn)xii

為松弛變量。于是得到帶有中轉(zhuǎn)運(yùn)輸?shù)漠a(chǎn)銷平衡運(yùn)輸表產(chǎn)地中轉(zhuǎn)站銷地產(chǎn)量A1A2T1T2B1B2B3產(chǎn)地A10121311323A2103519225中轉(zhuǎn)T1230128416T2151045216銷地B1312401416B21198510216B3324242016需求量16161616202321128帶有中轉(zhuǎn)站的產(chǎn)銷平衡運(yùn)輸表發(fā)送接受產(chǎn)地中轉(zhuǎn)站銷地產(chǎn)量A1A2T1T2B1B2B3產(chǎn)地A1

12131137A21

351929中轉(zhuǎn)T123

1284T2151

452銷地B13124

14B2119851

2B3324242

需求量475

使用生產(chǎn)B1B2B3生產(chǎn)量A12436≤a1≤11A2156a2=7A3324a3≥4使用量1046例2：產(chǎn)地A1至少發(fā)出6個(gè)單位物品，最多能生產(chǎn)11單位物品；A2必須發(fā)出7個(gè)單位物品；A3至少發(fā)出4個(gè)單位物品；確定最優(yōu)方案。

使用生產(chǎn)B1B2B3B4（虛擬）生產(chǎn)量A1243M6（必須發(fā)出的）A1`24305A2156M7（必須發(fā)出的）A3324M4（必須發(fā)出的）A3`32403使用量10465解：當(dāng)A1的產(chǎn)量a1=6（min)，A1,A2的產(chǎn)量之和=13，總需求量為20，所以在產(chǎn)銷平衡的情況下A3的產(chǎn)量最大為7；如果A1,A3的產(chǎn)量均取最大11，7，則總產(chǎn)量大于總需求20，此時(shí)應(yīng)增加一個(gè)虛銷地B4,需求量為5。例3：某公司承擔(dān)4條航線運(yùn)輸任務(wù)，已知（1）各條航線的起點(diǎn)和終點(diǎn)以及每天的航班數(shù)；各個(gè)城市之間的航行時(shí)間；每次裝船、卸船時(shí)間均為1天；問(wèn)題：公司至少需要配備多少條船才能滿足需要？航線起點(diǎn)城市終點(diǎn)城市每天航班數(shù)量1234EBADDCFB3211從至ABCDEFABCDEF0121477103138823015551413150172078517037852030航線裝船（天）卸船（天）航行（天）小記（天）航班數(shù)量所需船數(shù)12341111111117371319591532115710915所需要船只共91條船。城市ABCDEF每天到達(dá)每天需要余缺數(shù)01-112-120231203-3101各個(gè)港口之間調(diào)度。每天到達(dá)某一個(gè)港口的船只數(shù)量與它所需要發(fā)出船只數(shù)量不相等而產(chǎn)生的。將多余船只調(diào)往需要的港口，應(yīng)采用合理的運(yùn)輸方案，單位運(yùn)價(jià)為一對(duì)港口城市之間的航行時(shí)間。至由ABE多余船只C2352D1413172F7831缺少船只1135用表上作業(yè)方法求解運(yùn)輸問(wèn)題，得到最優(yōu)解按照這兩個(gè)方案調(diào)運(yùn)船只，其目標(biāo)函數(shù)等于40。，說(shuō)明各個(gè)港口之間調(diào)度所需要船只至少40艘。所以，總的需求：91+40=131

有m個(gè)產(chǎn)地A1,A2,…,Am和n個(gè)目的地B1,B2,B3,…,Bn都可以作為中間轉(zhuǎn)運(yùn)站使用，因此，發(fā)送和接受物品的地點(diǎn)有m+n個(gè)。ai:第i個(gè)產(chǎn)地的產(chǎn)量bj:第j個(gè)目的地的需求量xij:第i個(gè)產(chǎn)地運(yùn)到第j個(gè)目的地?cái)?shù)量Cij：第i個(gè)產(chǎn)地運(yùn)到第j個(gè)目的地的單位運(yùn)價(jià)Ci：第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)單位物品的費(fèi)用ti:第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)物品的數(shù)量產(chǎn)地與目的地統(tǒng)一編號(hào)，產(chǎn)地在前，目的地在后4個(gè)約束條件兩邊均加上Q;令xii=Q-ti,xjj=Q-tjxij≥0(i,j=1,2,…,m+n)說(shuō)明:當(dāng)i=j時(shí),所有的cij=-ci產(chǎn)地銷地發(fā)送量1……….mm+1…..m+n產(chǎn)地1.mx11…………….….x1m.Xm1………..…xmmX1,m+1…….x1,m+n.Xm,m+1…xm,m+nQ+a1Q+am目的地m+1.m+nxm+1,1……xm+1,m.Xm+n,1…xm+n,mXm+1,m+1….xm+1,m+n.Xm+n,m+1….xm+n,m+nQQ接受量Q…QQ+bm+1….Q+bm+n發(fā)送接受

接受發(fā)送產(chǎn)地銷地發(fā)送量1……….mm+1…..m+n產(chǎn)地1.m-c1…………….….c1m.cm1………..…-cmc1,m+1…….c1,m+n.cm,m+1…cm,m+nQ+a1Q+am目的地m+1.m+ncm+1,1……cm+1,m.cm+n,1…cm+n,m-cm+1……..….cm+1,m+n.cm+n,m+1……….-cm+nQQ接受量Q…QQ+bm+1….Q+bm+n12345104020305225643543153運(yùn)輸系統(tǒng)，2個(gè)產(chǎn)地1，2；一個(gè)中間轉(zhuǎn)運(yùn)站3；2個(gè)目的地4，5；產(chǎn)地的產(chǎn)量a1=10,a2=40,a3=a4=a5=0;目的地接受量b1=b2=b3=0,b4=30,b5=20例4：

接受發(fā)送產(chǎn)地轉(zhuǎn)運(yùn)銷地發(fā)送量12345產(chǎn)地1-4532M6025-12M490轉(zhuǎn)運(yùn)332-35550銷地42M5-36505M456-550接受量5050508070接受發(fā)送產(chǎn)地轉(zhuǎn)運(yùn)銷地發(fā)送量12345產(chǎn)地1501060250202090轉(zhuǎn)運(yùn)350050銷地4505055050接受量5050508070用最小元素法求解初始運(yùn)輸方案接受發(fā)送產(chǎn)地轉(zhuǎn)運(yùn)銷地發(fā)送量12345產(chǎn)地1