交通運(yùn)輸與物流工程專業(yè)

交通運(yùn)輸與物流工程專業(yè)運(yùn)籌學(xué)教程同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院2006第三章運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題及其數(shù)學(xué)模型運(yùn)輸問(wèn)題基本理論運(yùn)輸問(wèn)題表上作業(yè)法運(yùn)輸問(wèn)題模型建立3.1運(yùn)輸問(wèn)題及其數(shù)學(xué)模型一、一般運(yùn)輸問(wèn)題設(shè)某種貨物有m個(gè)產(chǎn)地A1，A2，…,Am,產(chǎn)量分別為a1,a2,…,am,有n個(gè)銷地B1,B2,…,Bn,銷量分別為b1,b2,…,bn，而且從Ai到Bj的單位運(yùn)價(jià)為Cij。若產(chǎn)銷平衡（ai=bj），問(wèn)如何制定調(diào)運(yùn)方案，可以使總運(yùn)費(fèi)最??？B1,B2,…,Bn產(chǎn)地

銷量

b1,b2,…,bn產(chǎn)量銷地ai=bj產(chǎn)銷平衡表/單位運(yùn)價(jià)表設(shè)Xij表示從產(chǎn)地Ai調(diào)運(yùn)至銷地Bj的貨物量i=1,2,…,m;j=1,2,…,n，則運(yùn)輸問(wèn)題的（LP）模型如下：

minz=

j=1,2,…,n

i=1,2,…,m

Xij>=0二、運(yùn)輸問(wèn)題模型B1,B2,…,BnAi

bj

b1,b2,…,bnaiBj

運(yùn)輸問(wèn)題的上述（LP）模型，可以形象地表示如下：B1,B2,…,BnAi

bj

b1,b2,…,bnaiBj

若隱含m*n個(gè)決策變量，可以省略地表示如下如下：運(yùn)輸模型2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106例1：（LP）模型供應(yīng)地約束需求地約束B(niǎo)1B2B3B46753A1x11x12x13x14148427A2x21x22x23x242759106A3x31x32x33x341922131213運(yùn)輸模型B1B2B3B46753A1148427A22759106A31922131213運(yùn)輸模型3.2運(yùn)運(yùn)輸問(wèn)題基基本理論一、運(yùn)輸問(wèn)問(wèn)題基本特特征（一）決策策變量的個(gè)個(gè)數(shù)：m*n;（二）約束束方程的個(gè)個(gè)數(shù)：m+n；（三）獨(dú)立立方程的個(gè)個(gè)數(shù)：m+n-1：（WHY）（四）系數(shù)數(shù)矩陣的特特殊結(jié)構(gòu)（（P80）——變量Xij的系數(shù)向量量AijAij=(0,0,……,1,……,0,0,0,……,1,……,0)Ti分量j分量二、運(yùn)輸問(wèn)問(wèn)題的對(duì)偶偶問(wèn)題設(shè)Ui，Vj，i=1,2,…,mj=1,2,…,n，為運(yùn)輸問(wèn)題的對(duì)偶變量，則運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題如下：

maxw=

Ui+Vj<=Cij(i=1,…,m;j=1,…,n)

Ui,Vj自由變量

三、運(yùn)輸問(wèn)問(wèn)題的基本本定理（一）基本本概念1。閉回路及其其頂點(diǎn)；設(shè)E是運(yùn)輸問(wèn)題題的一組決決策變量，，如果對(duì)E中的變量做做適當(dāng)?shù)呐排帕泻缶哂杏腥缦绿厥馐獾男蛄薪Y(jié)結(jié)構(gòu)：Xi1j1Xi1j2Xi2j2,…,Xisjs,Xisj1其中，i1,i2,…,is各不相同，，j1,j2,…,js2各不相同，，則稱E為運(yùn)輸問(wèn)題題的一個(gè)閉閉回路。E中變量成為為閉回路的的頂點(diǎn)。（二）基本本定理定理1：運(yùn)輸問(wèn)題的的(m+n)個(gè)約束方程程中只有(m+n-1)個(gè)獨(dú)立方程程，而且任任意一組(m+n-1)個(gè)方程都是是相互獨(dú)立立的。2。孤立點(diǎn)及其其性質(zhì)；設(shè)E為運(yùn)輸問(wèn)題題的一組變變量，Xij是其中一個(gè)個(gè)變量，如如果它是i行或j列屬于E的唯一變量量，則稱Xij為E的一個(gè)孤立立點(diǎn)。若Xij為E的一個(gè)孤立立點(diǎn)，則Xij不可能是E中閉回路的的一個(gè)頂點(diǎn)點(diǎn)。定理2：運(yùn)輸問(wèn)題中中變量組E（包含m+n-1個(gè)變量)能夠構(gòu)成基基本變量組組XB的充要條件件：變量組E中不存在閉閉回路。定理3：設(shè)E為運(yùn)輸問(wèn)題題的一基本本變量組XB，若變量XijE，則變量組“{Xij}E”（包含m+n個(gè)變量）一一定存在唯唯一一條閉閉回路。定理4：如果運(yùn)輸問(wèn)問(wèn)題中均是是整數(shù)，則則其任意基基本解中各各變量的取取值均為整整數(shù)。3.3運(yùn)運(yùn)輸問(wèn)問(wèn)題表上上作業(yè)法法初始基本本可行解解檢驗(yàn)數(shù)的的計(jì)算方方法迭代規(guī)則則與轉(zhuǎn)軸軸運(yùn)算方方法多重最優(yōu)優(yōu)解與退退化問(wèn)題題8131314663.3.1初初始基本本可行解解的求法法_西北角角法3.3.1初初始基本本可行解解的求法法_最小元元素法5c12-z12=c12-(c11-c21+c22)=7––(6-8+4)=53.3.2檢檢驗(yàn)數(shù)的的計(jì)算方方法_閉回路路法5c13-z13=c13-(c11-c21+c23)=5––(6-8+2)=555c14-z14=c13-(c11-c21+c21-c23+c33-c14)=3-(6-8+2-10+6)=7755c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=9-9575c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11-115795c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3-3579-11v4=03.3.2檢檢驗(yàn)數(shù)的的計(jì)算方方法_位勢(shì)法法位勢(shì)法(2)u3+v4=c34u3=6位勢(shì)法(3)u3+v3=c33v3=4位勢(shì)法(4)u2+v3=c23u2=-2位勢(shì)法(5)u2+v2=c22v2=6位勢(shì)法(6)u2+v1=c21v1=10位勢(shì)法(7)u1+v1=c11u1=-4位勢(shì)法(8)c12-z12=c12–(u1+v2)=7-(-4)-6=55位勢(shì)法(9)c13-z13=c13–(u1+v3)=5-(-4)-4=555位勢(shì)法(10)c14-z14=-c14u1+v4=3-(-4)-0=7755位勢(shì)法(11)c24-z24=c24–(u2+v4)=7-(-2)-0=99557位勢(shì)法(12)c31-z31=c31–(u3+v1)=5––6-10=-11-115579位勢(shì)法(13)c32-z32=c32–(u3+v2)=9––6-6=-3-35579-11x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-35579-113.3.3迭迭代規(guī)則則與轉(zhuǎn)軸軸運(yùn)算方方法轉(zhuǎn)軸運(yùn)算算,重新計(jì)計(jì)算檢驗(yàn)驗(yàn)數(shù),確定進(jìn)進(jìn)基、離離基變量量x14進(jìn)基,min{x11,x34}=min{14,13}=13,x34離基1155-4-28轉(zhuǎn)軸運(yùn)算算,重新新計(jì)算檢檢驗(yàn)數(shù)所有cij–zij>0,得到最優(yōu)優(yōu)解。Minz=6×1+3××13+8××2+4×13+2×12+5×194運(yùn)運(yùn)輸問(wèn)問(wèn)