運籌學基礎(第2版)-運輸問題課件

運輸問題是線性規(guī)劃問題，由于其約束條件的特殊性，產(chǎn)生了特殊的解法。第五章運輸問題第五章運輸問題1例:從3個發(fā)點A1，A2,，A3，向4個收點B1，B2，B3，B4發(fā)送某種貨物。Ai供應量為14，27，19。Bj收點的收量為22，13，12，13。由Ai運往Bj單位貨物的運費為Cij，由Ai運往Bj貨物的運量為Xij。問如何調(diào)配，才能使運費最?。坷?從3個發(fā)點A1，A2,，A3，向4個收點B1，B2，22321341運輸問題網(wǎng)絡圖s2=A2s3=A3B1B2B3B4s1=A1供應量供應地運價需求量需求地6753842759106B12321341運輸問題網(wǎng)絡圖s2=A2s3=A3B1B2B33運輸問題線性規(guī)劃模型供應地約束需求地約束運輸問題線性規(guī)劃模型供應地約束需求地約束45.1運輸問題數(shù)學模型和特點5.1運輸問題數(shù)學模型和特點55.1.1產(chǎn)銷平衡問題的數(shù)學模型問題的提出從m個發(fā)點A1,A2,…..Am向n個收點B1,B2…..Bn發(fā)送某種貨物。Ai發(fā)點的發(fā)量為ai，Bj收點的收量為bj。由Ai運往Bj單位貨物的運費為Cij，由Ai運往Bj貨物的運量為Xij。問如何調(diào)配，才能使運費最省？5.1.1產(chǎn)銷平衡問題的數(shù)學模型問題的提出從6當發(fā)點的發(fā)量總和為ai，收點的收量總和為bj相等時，稱此運輸問題為平衡運輸問題。否則稱此運輸問題為非平衡運輸問題。若沒有特別說明，均假定運輸問題為平衡的運輸問題。續(xù)當發(fā)點的發(fā)量總和為ai，收點的收量總和為7MinZ=cijxij

i

j

xij=ai(i=1,2…..m)

xij=bj(j=1,2……n)

xij0(i=1,2…..m;j=1,2……n)5.1.1運輸問題的數(shù)學模型mnjinmMinZ=cijxij5.1.1運輸問題的數(shù)學8運輸問題的數(shù)學模型：其中ai0,bj0,cij0且共有m+n個約束方程。并成立：ai=bj

i

jmn運輸問題的數(shù)學模型：mn9X=(X11，X12，…，X1n，X21，X22…，X2n，…，Xm1，Xm2，…，Xmn)TC=(C11，C12，…，C1n，C21，C22…，C2n，…，Cm1，Cm2，…，Cmn)A=(P11，P12，…，P1n，P21，P22…，P2n，…，Pm1，Pm2，…，Pmn)

X=(X11，X12，…，X1n，X21，X22…，10

由于ai=bj成立

其m+n個約束方程并不是獨立的。實際上只有m+n-1個是獨立的。即約束方程系數(shù)矩陣的秩為m+n-1。運輸問題解的結構nmij運輸問題解的結構nmij11PijPij=ei+em+j(i=1，….，m，j=1，…，n)ei為第i個分量為1其余分量為0的m+n維向量。em+j為第m+j個分量為1其余分量為0的m+n維分量。PijPij=ei+em+jei為第i個分量為1其余分量為012運輸問題矩陣描述minCX；S.TAX=b（5.1.3）x0其中A為運輸問題矩陣描述minCX；其中A為13A(m+n)(mn)X11X12…X1nX21X22…X2n….Xm1Xm2…Xmn1….1111….11111111…..111A=na1a2..amb1b1….bnA(m+n)(mn)X11X12…X1n145.1.2運輸問題數(shù)學模型的特點5.1.2運輸問題數(shù)學模型的特點15(1)有mn列，每列有(m+n)個元素，其中有兩個1，其余為0。對于列Pij來說，兩個1的位置為i與m+j個分量Pij=ei+em+jei為第i個分量為1其余分量為0的m+n維單位向量em+j為第m+j分量為1，其余分量為0的m+j分量為0的m+n維單位向量。(1)有mn列，每列有(m+n)個元素，其中有兩個1，16如如17（2）A有(m+n)行，每行前m行有n個1并連在一起，其余為零。

E0….00

E….0

……00…EII…IA=E=(1，1，1，…..，）（2）A有(m+n)行，每行前m行有n個1并連在一起，其余為18（3）運輸問題有最優(yōu)解證明由于ai=bj=d成立

令Xij=aibj/d5.1.6I=1，2，…mJ=1，2，…n代入5.1.1nmij（3）運輸問題有最優(yōu)解證明由于ai=bj=d19續(xù)Xij=aibj/d

=bj(ai/d)

=ai(i=1，2，…m)

Xij=aibj/d

=ai(bj/d)

=bj(j=1，2，…n)

ai0，bj0，所以Xij0

nj=1nj=1nj=1mmmi=1i=1i=1續(xù)Xij=aibj/d=bj(ai/20xu5.1.6是運輸問題的可行解。由定理2.4.6可得運輸問題必有基本可行解。由Xij的定義知，Xijmin(ai，bj）可行域是有界的。必有最優(yōu)解。xu5.1.6是運輸問題的21（4）矩陣A的秩為（m+n-1）A是一個（m+n）（m*n）型矩陣一般來說：（m+n）（m*n）因此秩最大為（m+n）又前m方程與后n個方程和相等。故r（A），實際是等于（m+n-1）。（4）矩陣A的秩為（m+n-1）A是一個（m+n）（m*22A(m+n)(mn)X11X12…X1nX21X22…X2n….Xm1Xm2…Xmn1….1111….11111111…..111A=na1a2..amb1b1….bnA(m+n)(mn)X11X12…X1n23A(m+n)(mn)p11p

12…p

1np

21p

31…p

m100….011….111….11…..1A=A(m+n)(mn)p11p12…p124證明p11p

12…p

1np

21p

31…p

m1線性無關，而pij與p

ij只差一個分量。由向量相關理論可知：一組線性無關向量組在相同的位置上加相同多的分量后得到的新向量也線性無關。因此p11p12…p1np21

p31…pm1也線性無關。r(A)=(m+n-1)證明p11p12…p1np255.2表上作業(yè)法由于運輸問題的特殊性，因此求解運輸問題往往不用單純形法。而用表上作業(yè)法。1、用西北角法或最小元素法確定基本可行解。2、用位勢法求解檢驗數(shù)3、用閉回路調(diào)整法求最優(yōu)解5.2表上作業(yè)法由于運輸問題的特殊性，因此求解運輸問題往往不26調(diào)運表B1B2…Bn發(fā)量A1a1A2a2……Amam收量b1b2…bn發(fā)點收點調(diào)運表B1B2…Bn發(fā)量A1a1A2a2……Amam收量b127例5.2.1表5.3B1B2B3B4發(fā)量A17A24A39收量3656收點發(fā)點例5.2.1表5.3B1B2B3B4發(fā)量A17A24A39收285.2運價表

B1B2B3B4A1311310A21928A374105收點發(fā)點5.2運價表B1B2B3B4A1311310A21928291、西北角法(I，j)，從（1，1）開始，比較a1，b1。X11=min（a1，b1）=b1=31、西北角法(I，j)，30表5.3B1B2B3B4發(fā)量A17A24A39收量3656收點發(fā)點表5.3B1B2B3B4發(fā)量A17A24A39收量3656收31表5.4B1B2B3B4發(fā)量A1347-3-4A2224-2A3369-3-6收量3-36-4-25-2-36X11=min（a1，b1）=b1=3X12=min（a'1，b2）=a'1=4X22=min（a2，b'2）=b'2=2X23=min（a'2，b3）=min（2，5）=a'2=2X33=min（a3，b'

3）=min（9，3）=b'3=3X34=min（a'3，b4）=6表5.4B1B2B3B4發(fā)量A1347-3-4A2224-32表5.5B1B2B3B4發(fā)量A1347–3-4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=33+411+29+22+310+65=133(萬)表5.5B1B2B3B4發(fā)量A1347–3-4A2224332、最小元素法(表5.6-7)B1B2B3B4發(fā)量A13113107-4-3A219284-3A3741059-6-3收量3-36-65-1-46-3364133C21=1，X21=min（a2，b1）=b1=3C23=2，X23=min（a'2，b3）=min（1，5）=a'2=1C13=3，X13=min（a1，b'3）=min（7，4）=b'3=4C32=4，X32=min（a2，b2）=b2=6C34=5，X34=min（a'3，b

4）=min（3，6）=a'3=3C14=10，X14=min（a′

1，b′4

）=a′1=

b′4=3Z=43+310+31+12+64+35=86(元)2、最小元素法(表5.6-7)B1B2B3B4發(fā)量A1311345.2.2位勢法求檢驗數(shù)ij=Cij-Zij=Cij-CBB-1Pij5.2.1(i=1，2…..m；j=1，2……n)Maxf=aiui+bjvj

stui+vjCij

(i=1，2…..m)

(j=1，2……n)ui，vj無正負W=(u1，…，um，v1，…，vn）5.2.3Ui=(xi1,xi2,xi3,xi4…..xin),vj=(x1j,x2j,x…xmj)mI=1j=1n5.2.2位勢法求檢驗數(shù)ij=Cij-Zij=Cij-C35MinZ=cijxij

i

j

xij=ai(i=1,2…..m)

xij=bj(j=1,2……n)

xij0(i=1,2…..m;j=1,2……n)5.1.1運輸問題的數(shù)學模型mnjinmMinZ=cijxij5.1.1運輸問題的數(shù)學36運輸問題線性規(guī)劃模型供應地約束需求地約束運輸問題線性規(guī)劃模型供應地約束需求地約束375.2.3代5.2.1ij=Cij-WPij=Cij-(u1，…，um，v1，…，vn)(ei+em+j)=Cij-(ui+vj）5.2.4

(i=1，2…..m；j=1，2……n)

A=nX11X12…X1nX21X22…X2n….Xm1Xm2…Xmn1….1111….11111111…..1115.2.3代5.2.1ij=Cij-WPij=Cij-38基變量的:Cij-(ui+vj）=0（i，j）JB（5.2.5）因為為已知，而（5.2.5）有（m+n）個未知量令Vn=0（5.2.6）非基變量檢驗數(shù):ij==Cij-(ui+vj）(i，j）JN

（5.2.7）基變量的:39A、公式求檢驗數(shù)A、公式求檢驗數(shù)40表5.5B1B2B3B4發(fā)量A1347–3-4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=33+411+29+22+310+65=133(萬)表5.5B1B2B3B4發(fā)量A1347–3-4A2224415.2.1例表5.5基變量:X11，

X12，X22，

X23，

X33，

X34C11-(u1+v1）=0C12-(u1+v2）=0C22-(u2+v2）=0C23-(u2+v3）=0C33-(u3+v3）=0C34-(u3+v4）=0V4=05.2.1例表5.5基變量:X11，X12，X2242代入Cij3-(u1+v1）=011-(u1+v2）=09-(u2+v2）=02-(u2+v3）=010-(u3+v3）=05-(u3+v4）=0V4=0解出：u1=-1，u2=-3，u3=5，v1=4，v2=12，u3=5，代入Cij3-(u1+v1）=043代入公式5.2.7ij=Cij-(ui+vj）(i，j）JN

5.2.713==C13-(u1+v3）=3-(-1+5)=-114==C14-(u1+v4）=10-(-1+0)=1121==C21-(u2+v1）=1-(-3+4)=0代入公式5.2.7ij=Cij-(ui+vj）(i，j44代入公式5.2.7ij=Cij-(ui+vj）(I，j）JN

5.2.724==C24-(u2+v4）=8-(-3+0)=1131==C31-(u3+v1）=7-(5+4)=-232==C32-(u3+v2）=4-(5+12)=-13ij0，故不是最優(yōu)解代入公式5.2.7ij=Cij-(ui+vj）(I，j45B、檢驗數(shù)表格求解1、作表格（3+1)×(4+1）的表2、第(3+1)行為vj行，(4+1)列為ui列3、右上角標出Cij，其中非基變量用框住。B、檢驗數(shù)表格求解1、作表格（3+1)×(4+1）的表46表5.8B1B2B3B4uiA1311

-1A292

-3A3

1055vj412507174非3108V4=0，基變量:X11，

X12，X22，

X23，

X33，

X34Cij-(ui+vj）=0（i，j）JB(5.2.5)Cij=(ui+vj）ui=Cij-vj）(5.2.10)

因為：V4=0，C34=(u3+v4）=u3=5，V3=C33-u3=10-5=5C23=(u2+v3），u2=C23-v3=2-5=-3表5.8B1B2B3B4uiA1347計算：V4=0，基變量:X11，

X12，X22，

X23，

X33，

X34Cij-(ui+vj）=0（I，j）JB

5.2.5Cij=(ui+vj）5.2.10

因為：V4=0，C34=(u3+v4）=u3=5，計算：V4=0，48表5.9B1B2B3B4uiA1311

-1A292

-3A3

1055vj

4

1250717非43108Cij=(ui+vj）5.2.10

C22=(u2+v2）v2=C22-u2=9-（-3）=12u1=C12-v2=11-12=-1V1=C11-u1=3-（-1）=4表5.9B1B2B3B4uiA1311-1A292-49表5.10B1B2B3B4uiA1311

-1

11-1A2092

11-3A3-2

-131055vj4125071743108ij==Cij-(ui+vj）(i，j）JN

(5.2.7)13==C13-(u1+v3）=3-(-1+5)=-114==C14-(u1+v4）=10-(-1+0)=1121==C21-(u2+v1）=1-(-3+4)=024==C24-(u2+v4）=8-(-3+0)=1131==C31-(u3+v1）=7-(5+4)=-232==C32-(u3+v2）=4-(5+12)=-13有ij0，故不是最優(yōu)解表5.10B1B2B3B4uiA1311-111-1A50例5.2.2以例5.2.1的最小元素法求得的基本可行解為例。見表5.7用位勢法計算檢驗數(shù)。例5.2.2以例5.2.1的最小元素法求得的基本可行解為例。51最小元素法(表5.6-7)B1B2B3B4發(fā)量A13113107-4-3A219284-3A3741059-6-3收量3-36-65-1-46-33解64133最小元素法(表5.6-7)B1B2B3B4發(fā)量A13113152表5.11B1B2B3B4uiA112

31010A2112-1

9A310

4125

5vj

-8-1-7077非8311910表5.11B1B2B3B4uiA11231010A2535.2.3用閉回路法調(diào)整當前基本可行解定義5.2.將變量Xij在調(diào)運表中所對應的空格記做(i，j)稱為格點。而Xij系數(shù)列向量Pij也稱作格點(i，j)所對應的系數(shù)列向量，若Xij為基變量，則(i，j)稱為基格，否則為非基格。表5.6.7，基格(1，3)，(1，4)(2，1)(2，3)非基格(1，1)，(2，4)(3，1)(2，3)5.2.3用閉回路法調(diào)整當前基本可行解定義5.2.將變量Xi54(表5.6-7)B1B2B3B4發(fā)量A13113107-4-3A219284-3A3741059-6-3收量3-36-65-1-46-3364133(表5.6-7)B1B2B3B4發(fā)量A13113107-4-55定義5.2.2定義5.2.2若一組格點經(jīng)過適當?shù)呐判蚝螅軐懗梢韵滦问剑?I1，j1)，(I1，j2)，(I2，j2)(I2,，j3)，(I3，j3)….(Is,，js)，(Is，ji)1則這組格點構成了閉回路。定義5.2.2定義5.2.2若一組格點經(jīng)過適當?shù)呐判蚝?，能?6閉回路特點(1)格點數(shù)大于4閉回路特點(1)格點數(shù)大于457(2)形式A：第1格與第2格行號同，第2與第3格列號同，第3、第4格行號同，第4、第5格列號同…最后一格與第一格列號同。形式B：第1格、第2格列號同。第2格、第3格行號同…最后一格與第一格行號同。(2)形式A：第1格與第2格行號同，第2與第3格列號同，第58（3）連線構成閉回路，一行或一列只包含兩個格點，都處在每條邊的端點上。（3）連線構成閉回路，一行或一列只包含兩個格點，都處在每條邊595.12B1B2B3B4B5B6B7B8B9A1a1A2a2A3a3A4a4b1b2b3b4b5b6b7b8b9格組(1，1)，(1，2)(3，2)(3，1)格組(1，3)，(1，4)(2，4)(2，5)(3，5)(3，3)格組(1，6)，(1，7)(4，7)(4，9)(2，9)(2，6)5.12B1B2B3B4B5B6B7B8B9A1a1A2a260表5.12，格組(1，1)，(1，2)(3，2)(3，1)格組(1，3)，(1，4)(2，4)(2，5)(3，5)(3，3)格組(1，6)，(1，7)(4，7)(4，9)(2，9)(2，6)表5.12，格組(1，1)，(1，2)(3，2)(3，1615.13B1B2B3B4B5B6B7A1A2A3A4包含了閉回路，非構成閉回路成格組(1，1)，(1，2)(1，4)(3，4)(3，2)格組(2，5)，(2，6)(2，7)(3，7)(3，6)(3，5)5.13B1B2B3B4B5B6B7A1A2A3A4包含了閉62表5.10B1B2B3B4uiA1311

-1

11-1A2092

11-3A3-2

-131055vj4125071743108表5.10B1B2B3B4uiA1311-111-1A63表5.5B1B2B3B4發(fā)量A1347–3-4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=33+411+29+22+310+65=133(萬)表5.5B1B2B3B4發(fā)量A1347–3-4A222464表5.14B1B2B3B4發(fā)量A1347–3-4A22-

2+4-2-2A30+

3-69-3-6收量3-36-4-25-2-36-6Z=33+411+29+22+310+65=133(元)ij=minij|ij<0=32=-13（I，j）JN表5.5初始方案，5.10檢驗數(shù)不大于032=-13=minXij|(i，j)為閉回路上所有偶數(shù)號格點=min(2，3)=2=X22表5.14B1B2B3B4發(fā)量A1347–3-4A22-65表5.15B1B2B3B4發(fā)量A1347–3-4A2

44-2-2A32

169-3-6收量3-36-4-25-2-36-6X(1)=(3，4，0，0，0，0，4，0，0，2，1，6）TZ(1)=33+114+24+42+101+56=109(元)<Z(0)=133(元)表5.15B1B2B3B4發(fā)量A1347–3-4A266產(chǎn)銷平衡運輸問題的算法其步驟如下．產(chǎn)銷平衡運輸問題的算法其步驟如下．67第l步：用西北角規(guī)則或最小元素法求初始基本可行解。第l步：用西北角規(guī)則或最小元素法求初始基本可行解。68第2步用位勢法求非基變量的檢驗數(shù)。若最優(yōu)準則。ij0得到滿足，則當前基本可行解就是最優(yōu)解（當前調(diào)運方案就是最優(yōu)調(diào)運方案），計算停止。否則轉(zhuǎn)第3步。第2步用位勢法求非基變量的檢驗數(shù)。若最優(yōu)準則。ij069第3步：取一個檢驗數(shù)最小的非基變量作進基變量，其對應的格為進基格（編號為第1格）。以進基格為起始點作出一個其余頂點均為基格的閉回路，在該閉回路上，從所有偶數(shù)號格點的調(diào)運量中選出最小值作為調(diào)整量，該格即為離基格，對應的變量為離基變量。第3步：取一個檢驗數(shù)最小的非基變量作進基變量，其對應的格為進70第4步對閉回路上的運輸量作出調(diào)整：所有奇數(shù)號格的調(diào)運量加上調(diào)整量；所有偶數(shù)號格的調(diào)運量減去調(diào)整量，其余的Xij取值不變，這樣就得到了一個新的調(diào)運方案轉(zhuǎn)第2步。第4步對閉回路上的運輸量作出調(diào)整：71例5.2.3判斷以表5.15所體現(xiàn)的X(1)是否為最優(yōu)解。若不是，試求出最優(yōu)解。解:對X(1)用位勢法求其檢驗數(shù)，為此建立表5.16，計算ui，vj及ij

例5.2.3判斷以表5.15所體現(xiàn)的X(1)是否為最優(yōu)解72表5.15B1B2B3B4發(fā)量A1347–3-4A2

44-2-2A32

169-3-6收量3-36-4-25-2-36-6X(1)=(3，4，0，0，0，0，4，0，0，2，1，6）TZ(1)=33+114+24+42+101+56=109(元)<Z(0)=133(元)表5.15B1B2B3B4發(fā)量A1347–3-4A273表5.16B1B2B3B4uiA1311

-14

-212A213132

11-3A311

41055vj-9-150171731089ij=minij|ij<0=13=-14（i，j）JN非優(yōu)，建閉回路。表5.16B1B2B3B4uiA1311-14-21274表5.17B1B2B3B4發(fā)量A134-10+17A2

44A32+1

1-169收量3656X(2)=(3，3，1，0，0，0，4，0，0，3，0，6）TZ(2)=33+113+31+24+43+56=95(元)<Z(1)=109(元)=minXij|(I，j)為閉回路上所有偶數(shù)號格點=min(1，4)=1=X33再判斷X(2)是否為最優(yōu)解。建立表5.18，計算ui，vj及ij

表5.17B1B2B3B4發(fā)量A134-10+17A275表5.18B1B2B3B4uiA13113

-212A2-1-1

2

-311A311

414

55vj-9-1-90717108910不都大于0,也不是最優(yōu)解．ij=minij|ij<0=24=-3（i，j）JN非優(yōu)，建閉回路。表5.18B1B2B3B4uiA13113-212A276表5.19B1B2B3B4發(fā)量A133-31+37A2

4-3

0+34A33+3

6-39收量3656X(3)=(3，0，4，0，0，0，1，3，0，6，0，3）TZ(3)=33+34+21+83+46+53=86(元)<Z(2)=95(元)=minXij|(i，j)為閉回路上所有偶數(shù)號格點=min(6，3，4)=3=X12再判斷X(3)是否為最優(yōu)解．建立表5.20，計算ui，vj及ij表5.19B1B2B3B4發(fā)量A133-31+37A277表5.20B1B2B3B4uiA133

3

19A2-12

2

88A38

411

5

5vj-6-1-607171091110不都大于0,也不是最優(yōu)解．ij=minij|ij<0=21=-1（i，j）JN非優(yōu)，建閉回路。表5.20B1B2B3B4uiA133319A2-178表5.21B1B2B3B4發(fā)量A13-1

4+17A20+1

1-1

34A36

39收量3656X(4)=(2，0，5，0，1，0，0，3，0，6，0，3）TZ(4)=32+35+11+83+46+53=85(元)<Z(3)=86(元)表5.21B1B2B3B4發(fā)量A13-14+1779表5.22B1B2B3B4uiA132

30*10A212

1

88A39

412

55vj-7-1-707710911102都大于0，是最優(yōu)解X11=2，X13=5，X21=1，X24=3，X32=6，X34=3，XI4=0表5.22B1B2B3B4uiA13230*10A21805.2.4表上作業(yè)法計算中的兩個問題1、無窮多個最優(yōu)解2、退化問題5.2.4表上作業(yè)法計算中的兩個問題1、無窮多個最優(yōu)解811、無窮多個最優(yōu)解某個非基變量檢驗數(shù)等于零1、無窮多個最優(yōu)解某個非基變量檢驗數(shù)等于零82表5.23B1B2B3B4發(fā)量A12-2

5

14=00*+27A21+2

3-24A36

39收量3656X(5=(0，0，5，2，3，0，0，1，0，6，0，3）TZ(5)=35+102+13+81+46+53=85(元)

表22中14=0，作閉回路表5.23B1B2B3B4發(fā)量A12-2832、退化問題（1）在確定初始可行解時，若已確定的空格（i，j）處要填上調(diào)運量Xij，而此時剛好有ai=b'j，Xij=ai=bj，說明此時Ai的發(fā)運量已經(jīng)用完，而Bi的需求已滿足。因此要畫掉第i行，j列。2、退化問題（1）在確定初始可行解時，若已確定的空格（i，j84x為了保證調(diào)運表上有（m+n-1）個基變量的值，就要在第i行，j列中任找一個空格（i，j1）或（i1，j），設置調(diào)運量為Xij1=0，或Xi1j=0。x為了保證調(diào)運表上有（m+n-1）個基變量的值，就要在第i行85例5.2.4B1B2B3B4發(fā)量A1311

457A277

384

A312

10

6

9收量3

6

56

下表為34運輸問題的Cij及發(fā)運量和需求量，試用最小素法求該問題的一個可行解。例5.2.4B1B2B3B4發(fā)量A131186例5.2.4調(diào)運表B1B2B3B4發(fā)量A1311457–1-6

A2770*384-4A31210

6

9-3-6收量3-36-65-4-16-6例5.2.4調(diào)運表B1B2B3B4發(fā)量A1311457–187例5.2.4調(diào)運方案B1B2B3B4發(fā)量A1

167A2

04

4

A336

9

收量3

6

56

例5.2.4調(diào)運方案B1B2B3B4發(fā)量A188(2)在用閉回路調(diào)整時出現(xiàn)退化=minXij|(i，j)為閉回路上所有偶數(shù)號格點如果兩個或兩個以上偶數(shù)格點Xij都為極小值，則只能取一個為離基格，其余作為基格。出現(xiàn)了退化問題(2)在用閉回路調(diào)整時出現(xiàn)退化=minXij|(i，j)89例5.2.5表5.26為3×4問題的基本可行解及發(fā)運量和需求量。表5.27為基本可行解的檢驗數(shù)。用閉回路法對其作出調(diào)整。例5.2.5表5.26為3×4問題的基本可行解及發(fā)運量和需求90表5.26B1B2B3B4發(fā)運量A133

1

7A2

3

3

A3

3

6

9

需求量3

6

56

表5.26B1B2B3B4發(fā)運量A13391表5.27B1B2B3B4A1

-2A2-1-1

-3A311

14

表5.27B1B2B3B4A1-92表5.28B1B2B3B4發(fā)運量A1331

7A2

303

A3

3

6

9

需求量3

6

56

min=ij=24閉回路如圖=minXij|(i，j)為閉回路上所有偶數(shù)號格點=minX34,X12,X23=X12=X23=3表5.28B1B2B3B4發(fā)運量A13393表5.28B1B2B3B4發(fā)運量A133-3

1+3

7A2

3-3

0+33

A3

3+3

6-3

9

需求量3

6

56

min=ij=24閉回路如圖=minXij|(i，j)為閉回路上所有偶數(shù)號格點=minX34,X12,X23=X12=X23=3表5.28B1B2B3B4發(fā)運量A133-394作業(yè)答案P170,5.2作業(yè)答案P170,5.295運籌學基礎(第2版)---運輸問題課件96題5.11基本可行解B1B2B3B4發(fā)量A161a′17-6-1A2538-5-3A30*33-3收量6-66-1-53-33X11=min（a1，b1）=b1=6X12=min（a′1，b2）=a′1=1X22=min（a2，b′2）=b′2=5X23=min（a′2，b3）=min（2，5）=a′2=3X33=min（a3，b′

3）=0X34=min（a′

3，b4）=3題5.11基本可行解B1B2B3B4發(fā)量A161a′17-697表5.11B1B2B3B4uiA158

16A2910

17A3

299vj-11-8-707484非737V4=0，基變量:X11，

X12，X22，

X23，

X33，

X34Cij-(ui+vj）=0（I，j）JB

5.2.5Cij=(ui+vj）ui=Cij-vj）5.2.10

因為：V4=0，C34=(u3+v4）=u3=9，V3=C33-u3=2-9=-7C23=(u2+v3），u2=C23-v3=10-(-7)=17表5.11B1B2B3B4uiA1598表5.12檢驗數(shù)B1B2B3B4uiA158

-2-1316A2-2910

-1017A310

3299vj-11-8-707484非737ij==Cij-(ui+vj）(I，j）JN

5.2.713==C13-(u1+v3）=7-(-7+16)=-214==C14-(u1+v4）=3-(16+0)=-1321==C21-(u2+v1）=4-(-11+17)=-224==C24-(u2+v4）=7-(17+0)=-1031==C31-(u3+v1）=8-(9-11)=1032==C32-(u3+v2）=4-(9-8)=-3有ij0，故不是最優(yōu)解表5.12檢驗數(shù)B1B2B3B4uiA1599題5.13閉回路B1B2B3B4發(fā)量A161-10+17-6-1A25+13-18-5-3A30*+13-13-3收量6-66-1-53-33=minXij|(I，j)為閉回路上所有偶數(shù)號格點=min1，3，3=1題5.13閉回路B1B2B3B4發(fā)量A161-1100表5.14VUB1B2B3B4uiA15

33A2910

17A3

299vj2-8-707484非787V4=0，基變量:X11，

X12，X22，

X23，

X33，

X34Cij-(ui+vj）=0（I，j）JB

5.2.5Cij=(ui+vj）ui=Cij-vj）5.2.10

因為：V4=0，C34=(u3+v4）=u3=9，V3=C33-u3=2-9=-7C23=(u2+v3），u2=C23-v3=10-(-7)=17表5.14VUB1B2B3B4uiA15101表5.15檢驗數(shù)B1B2B3B4uiA1513

11

33A2-15910

-1017A3-3

3299vj2-8-707484非77ij==Cij-(ui+vj）(I，j）JN

5.2.713==C13-(u1+v3）=7-(-7+3)=1112==C12-(u1+v2）=8-(3-8)=1321==C21-(u2+v1）=4-(2+17)=-1524==C24-(u2+v4）=7-(17+0)=-1031==C31-(u3+v1）=8-(9+2)=-332==C32-(u3+v2）=4-(9-8)=3有ij0，故不是最優(yōu)解8非表5.15檢驗數(shù)B1B2B3B4uiA151102題5.16閉回路B1B2B3B4發(fā)量A16-2

1+2

7A20+262-28A31+2

2-23收量6633=minXij|(I，j)為閉回路上所有偶數(shù)號格點=min2，2，6=2題5.16閉回路B1B2B3B4發(fā)量A16-21+2103表5.17檢驗數(shù)B1B2B3B4uiA15-2

11

33A2

4915

52A3-3

-12299vj27-70784非77ij==Cij-(ui+vj）(I，j）JN

5.2.713==C13-(u1+v3）=7-(-7+3)=1112==C12-(u1+v2）=8-(3+7)=-223==C23-(u2+v3）=10-(2-7)=1524==C24-(u2+v4）=7-(2+0)=531==C31-(u3+v1）=8-(9+2)=-332==C32-(u3+v2）=4-(9+7)=-12有ij0，故不是最優(yōu)解8非10表5.17檢驗數(shù)B1B2B3B4uiA15-104題5.18閉回路B1B2B3B4發(fā)量A14-0

3+0

7A20+0608A30+03

0-03收量6633=minXij|(I，j)為閉回路上所有偶數(shù)號格點=min0，4，6=0題5.18閉回路B1B2B3B4發(fā)量A14-03+0105表5.19檢驗數(shù)B1B2B3B4uiA15-2

-1

33A2

493

52A39

4212-3vj27507877ij==Cij-(ui+vj）(I，j）JN

5.2.713==C13-(u1+v3）=7-(5+3)=-112==C12-(u1+v2）=8-(3+7)=-223==C23-(u2+v3）=10-(2+5)=324==C24-(u2+v4）=7-(2+0)=531==C31-(u3+v1）=8-(2-3)=934==C34-(u3+v4）=9-(0-3)=12有ij0，故不是最優(yōu)解8非109表5.19檢驗數(shù)B1B2B3B4uiA15-106題5.20閉回路B1B2B3B4發(fā)量A14-4

0*+437A22+46-408A303

0

3收量6633=minXij|(I，j)為閉回路上所有偶數(shù)號格點=min4，6=4題5.20閉回路B1B2B3B4發(fā)量A14-40107表5.21檢驗數(shù)B1B2B3B4uiA1258

1

33A2

493

3-4A39

4210-1vj05307877ij==Cij-(ui+vj）(I，j）JN

5.2.713==C13-(u1+v3）=7-(5+3)=-111==C11-(u1+v1）=5-(3+0)=223==C23-(u2+v3）=10-(2+5)=324==C24-(u2+v4）=7-(-4+0)=331==C31-(u3+v1）=8-(0-1)=934==C34-(u3+v4）=9-(0-1)=10有ij>0，故是最優(yōu)解1095表5.21檢驗數(shù)B1B2B3B4uiA1258108題5.22閉回路B1B2B3B4發(fā)量A10437A26208A303

0

3收量6633X(1)=(0，4，0，0，6，2，0，0，0，0，3，0）TZ(1)=84+33+64+92+32=89

題5.22閉回路B1B2B3B4發(fā)量A10437A261095.2最小元素法5.2最小元素法110題5.21基本可行解B1B2B3B4B5發(fā)量A12525

50-25-25A2106030100-60-30-10A380

7050-70-80收量25-2511525-10-8060-6030-3070-701234567題5.21基本可行解B1B2B3B4B5發(fā)量A125255111表5.22UVB1B2B3B4B5uiA11015

115A2

4015

30030A3

35

2525vj510-15002030204020304055V5=0，基變量:X11，

X12，X22，

X23，

X24，

X32，

X35Cij-(ui+vj）=0（I，j）JB

5.2.5Cij=(ui+vj）ui=Cij-vj）5.2.10

因為：V5=0，C35=(u3+v4）u3=25，V2=C32-u3=35-25=10C22=(u2+v2），u2=C22-v2=40-10=30V3=C23-u2=15-30=-15表5.22UVB1B2B3B4B5uiA11015112表5.23檢驗數(shù)B1B2B3B4B5uiA11015

3015355A2-154015

30030A30

3530302525vj510-150020302040ij=Cij-(ui+vj）(I，j）JN

5.2.713=C13-(u1+v3）=20-(-15+5)=3014=C14-(u1+v4）=20-(5+0)=1515=C15-(u1+v5）=40-(5+0)=3521=C21-(u2+v1）=20-(5+30)=-1525=C25-(u2+v5）=30-(30+0)=031==C31-(u3+v1）=30-(25+5)=033==C33-(u3+v3）=40-(25-15)=3034==C34-(u3+v4）=55-(25+0)=30有ij0，故不是最優(yōu)解20304055表5.23檢驗數(shù)B1B2B3B4B5uiA1113題5.24基本可行解B1B2B3B4B5發(fā)量A125-1525+10

50A20+1010-106030100A380

70150收量25115603070ij=minij|ij<0=21=-15（I，j）JN非優(yōu)，建閉回路X(1)=(15，35，0，0，0，10，0，60，30，0，0，80，0，0，70）TZ(1)=1510+3515+1025+6015+3030+8035+7025=7225

題5.24基本可行解B1B2B3B4B5發(fā)量A125-152114表5.25檢驗數(shù)B1B2B3B4B5uiA11015

150355A2201515

301515A30

3515152525vj510015040302040ij=Cij-(ui+vj）(I，j）JN

5.2.713=C13-(u1+v3）=20-(0+5)=1514=C14-(u1+v4）=20-(5+15)=015=C15-(u1+v5）=40-(5+0)=3522=C22-(u2+v2）=40-(15+10)=1525=C25-(u2+v5）=30-(15+0)=1531==C31-(u3+v1）=30-(25+5)=033==C33-(u3+v3）=40-(25+0)=1534==C34-(u3+v4）=55-(25+15)=15有ij0，故是最優(yōu)解20304055表5.25檢驗數(shù)B1B2B3B4B5uiA11015115運籌學基礎(第2版)---運輸問題課件116運籌學基礎(第2版)---運輸問題課件117題5.11′基本可行解B1B2B3B4發(fā)量A1610*a′17-6-1A2（0*）530*8-5-3A30*33-3收量6-66-1-53-33題5.11′基本可行解B1B2B3B4發(fā)量A1610*a′1118表5.11B1B2B3B4uiA158

6A291077A3

299vj-12307484非732V4=0，基變量:X11，

X12，X22，

X23，

X33，

X34