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

交通運(yùn)輸與物流工程專業(yè)運(yùn)籌學(xué)教程同濟(jì)大學(xué)20061第三章運(yùn)輸問題運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題基本理論運(yùn)輸問題表上作業(yè)法運(yùn)輸問題模型建立23.1運(yùn)輸問題及其數(shù)學(xué)模型一、一般運(yù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），問如何制定調(diào)運(yùn)方案，可以使總運(yùn)費(fèi)最??？3B1,B2,…,Bn產(chǎn)地

銷量

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

minz=

j=1,2,…,n

i=1,2,…,m

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

bj

b1,b2,…,bnaiBj

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

bj

b1,b2,…,bnaiBj

若隱含m*n個(gè)決策變量，可以省略地表示如下如下：運(yùn)輸模型72321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106例1：8（LP）模型供應(yīng)地約束需求地約束9B1B2B3B46753A1x11x12x13x14148427A2x21x22x23x242759106A3x31x32x33x341922131213運(yùn)輸模型10B1B2B3B46753A1148427A22759106A31922131213運(yùn)輸模型113.2運(yùn)輸問題基本理論一、運(yùn)輸問題基本特征（一）決策變量的個(gè)數(shù)：m*n;（二）約束方程的個(gè)數(shù)：m+n；（三）獨(dú)立方程的個(gè)數(shù)：m+n-1：（WHY）（四）系數(shù)矩陣的特殊結(jié)構(gòu)（P80）——變量Xij的系數(shù)向量AijAij=(0,0,…,1,…,0,0,0,…,1,…,0)T

i分量j分量12二、運(yùn)輸問題的對(duì)偶問題設(shè)Ui，Vj，i=1,2,…,mj=1,2,…,n，為運(yùn)輸問題的對(duì)偶變量，則運(yùn)輸問題的對(duì)偶問題如下：

maxw=

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

Ui,Vj自由變量

13三、運(yùn)輸問題的基本定理（一）基本概念1。閉回路及其頂點(diǎn)；設(shè)E是運(yùn)輸問題的一組決策變量，如果對(duì)E中的變量做適當(dāng)?shù)呐帕泻缶哂腥缦绿厥獾男蛄薪Y(jié)構(gòu)：Xi1j1Xi1j2Xi2j2,…,Xisjs,Xisj1

其中，i1,i2,…,is各不相同，j1,j2,…,js2各不相同，則稱E為運(yùn)輸問題的一個(gè)閉回路。E中變量成為閉回路的頂點(diǎn)。14（二）基本定理

定理1：運(yùn)輸問題的(m+n)個(gè)約束方程中只有(m+n-1)個(gè)獨(dú)立方程，而且任意一組(m+n-1)個(gè)方程都是相互獨(dú)立的。

2。孤立點(diǎn)及其性質(zhì)；設(shè)E為運(yùn)輸問題的一組變量，Xij是其中一個(gè)變量，如果它是i行或j列屬于E的唯一變量，則稱Xij為E的一個(gè)孤立點(diǎn)。若Xij為E的一個(gè)孤立點(diǎn)，則Xij不可能是E中閉回路的一個(gè)頂點(diǎn)。15

定理2：運(yùn)輸問題中變量組E（包含m+n-1個(gè)變量)能夠構(gòu)成基本變量組XB的充要條件：

變量組E中不存在閉回路。定理3：設(shè)E為運(yùn)輸問題的一基本變量組XB，若變量XijE，則變量組“{Xij}

E”（包含m+n個(gè)變量）一定存在唯一一條閉回路。定理4：如果運(yùn)輸問題中均是整數(shù)，則其任意基本解中各變量的取值均為整數(shù)。163.3運(yùn)輸問題表上作業(yè)法初始基本可行解檢驗(yàn)數(shù)的計(jì)算方法迭代規(guī)則與轉(zhuǎn)軸運(yùn)算方法多重最優(yōu)解與退化問題178131314663.3.1初始基本可行解的求法_西北角法183.3.1初始基本可行解的求法_最小元素法195c12-z12=c12-

(c11-c21+c22)=7–(6-8+4)=53.3.2檢驗(yàn)數(shù)的計(jì)算方法_閉回路法205c13-z13=c13-(c11-c21+c23)=5–(6-8+2)=55215c14-z14=c13-(c11-c21+c21-c23+c33-c14)=3-(6-8+2-10+6)=775225c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=9-957235c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11-11579245c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3-3579-1125v4=03.3.2檢驗(yàn)數(shù)的計(jì)算方法_位勢(shì)法26位勢(shì)法(2)u3+v4=c34 u3=627位勢(shì)法(3)u3+v3=c33 v3=428位勢(shì)法(4)u2+v3=c23 u2=-229位勢(shì)法(5)u2+v2=c22 v2=630位勢(shì)法(6)u2+v1=c21 v1=1031位勢(shì)法(7)u1+v1=c11 u1=-432位勢(shì)法(8)c12-z12=c12–(u1+v2)=7-(-4)-6=5533位勢(shì)法(9)c13-z13=c13–(u1+v3)=5-(-4)-4=55534位勢(shì)法(10)c14-z14=-c14u1+v4=3-(-4)-0=775535位勢(shì)法(11)c24-z24=c24–(u2+v4)=7-(-2)-0=9955736位勢(shì)法(12)c31-z31=c31–(u3+v1)=5–6-10=-11-11557937位勢(shì)法(13)c32-z32=c32–(u3+v2)=9–6-6=-3-35579-1138x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-35579-113.3.3迭代規(guī)則與轉(zhuǎn)軸運(yùn)算方法39轉(zhuǎn)軸運(yùn)算,重新計(jì)算檢驗(yàn)數(shù),確定進(jìn)基、離基變量x14進(jìn)基,min{x11,x34}=min{14,13}=13,x