運(yùn)籌學(xué)基礎(chǔ)(第2版)何堅(jiān)勇運(yùn)輸問(wèn)題

運(yùn)輸問(wèn)題是線性規(guī)劃問(wèn)題，由于其約束條件的特殊性，產(chǎn)生了特殊的解法。第五章 運(yùn)輸問(wèn)題第一頁(yè)，共一百二十五頁(yè)。從3個(gè)發(fā)點(diǎn)A1，A2,，A3，向4個(gè)收點(diǎn)B1，B2，B3，B4發(fā)送某種貨物。Ai

供應(yīng)量為14，27，19。Bj

收點(diǎn)的收量為22，13，12，13。由Ai

運(yùn)往Bj

單位貨物的運(yùn)費(fèi)為Cij，由Ai

運(yùn)往Bj

貨物的運(yùn)量為Xij。問(wèn)如何調(diào)配，才能使運(yùn)費(fèi)最??？第二頁(yè)，共一百二十五頁(yè)。32131運(yùn)輸問(wèn)題網(wǎng)絡(luò)圖s2=A2

24

B4s3=A3B1B2B3s1=A1供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753851047

296B1第三頁(yè)，共一百二十五頁(yè)。運(yùn)輸問(wèn)題線性規(guī)劃模型供應(yīng)地約束需求地約束第四頁(yè)，共一百二十五頁(yè)。5.1運(yùn)輸問(wèn)題數(shù)學(xué)模型和特點(diǎn)第五頁(yè)，共一百二十五頁(yè)。5.1.1產(chǎn)銷(xiāo)平衡問(wèn)題的數(shù)學(xué)模型問(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)最省？第六頁(yè)，共一百二十五頁(yè)。當(dāng)發(fā)點(diǎn)的發(fā)量總和為

ai，收點(diǎn)的收量總和為bj相等時(shí)，稱(chēng)此運(yùn)輸問(wèn)題為平衡運(yùn)輸問(wèn)題。否則稱(chēng)此運(yùn)輸問(wèn)題為非平衡運(yùn)輸問(wèn)題。若沒(méi)有特別說(shuō)明，均假定運(yùn)輸問(wèn)題為平衡的運(yùn)輸問(wèn)題。續(xù)第七頁(yè)，共一百二十五頁(yè)。Min

Z=cijxiji

jxij

=ai

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

=bj

(j=1,2……n)xij0

(i=1,2…..m;

j=1,2……n)jmninm第八頁(yè)，共一百二十五頁(yè)。運(yùn)輸問(wèn)題的數(shù)學(xué)模型：0,

bj其中

ai

0,

cij

0且共有

m+n 個(gè)約束方程。并成立：imnai

=

bjj第九頁(yè)，共一百二十五頁(yè)。X=(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)?第十頁(yè)，共一百二十五頁(yè)。由于

ai

=

bj成立其m+n個(gè)約束方程并不是獨(dú)立的。實(shí)際上只有

m+n-1個(gè)是獨(dú)立的。即約束方程系數(shù)矩陣的秩為

m+n-1。運(yùn)輸問(wèn)題解的結(jié)構(gòu)nmij第十一頁(yè)，共一百二十五頁(yè)。PijPij=ei+em+j(i=1，….，m，j=1，…，n)

ei為第i個(gè)分量為1其余分量為0的m+n維向量。

em+j為第m+j個(gè)分量為1其余分量為0的m+n維分量。第十二頁(yè)，共一百二十五頁(yè)。運(yùn)輸問(wèn)題矩陣描述?min

CX；AX=b

（5.1.3）x

0S.T?其中A為第十三頁(yè)，共一百二十五頁(yè)。X11

X12…

X1nX21

X22…X2n….

Xm1Xm2…

Xmn11….121113….41115678111…..11111na1a2..amb1b1….bn第十四頁(yè)，共一百二十五頁(yè)。5.1.2運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn)第十五頁(yè)，共一百二十五頁(yè)。(1)有m n列，每列有(m+n)個(gè)元素，其中有兩個(gè)1，其余為0。對(duì)于列Pij來(lái)說(shuō)，兩個(gè)1的位置為i與m+j個(gè)分量Pij=ei+e

m+jei為第i個(gè)分量為1其余分量為0的m+n維單位向量em+j為第m+j分量為1，其余分量為0的m+j分量為0的m+n 維單位向量。第十六頁(yè)，共一百二十五頁(yè)。如第十七頁(yè)，共一百二十五頁(yè)。（2）E0….00E….0……00…EII…I第十八頁(yè)，共一百二十五頁(yè)。A=A有(m+n)行，每行前m行有n個(gè)1并連 在一起，其余為零。E=(1，1，1，…..，）（3）運(yùn)輸問(wèn)題有最優(yōu)解m

n證明由于 ai

=

bj=d成立i

j5.1.6令Xij=ai

bj/dI=1，2，…mJ=1，2，…n代入5.1.1第十九頁(yè)，共一百二十五頁(yè)。S

Xi

j

=nbj

(ai

/d

)

=

aij=1(

i=1，2，…m)Xi

j

=ai

bj/d

=ai

(bj

/d

)

=

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

0，bj0，所以Xij

0?nj=1nai

bj/d

=j=1mmmi=1i=1i=1第二十頁(yè)，共一百二十五頁(yè)。xu5.1.6是運(yùn)輸問(wèn)題的可行解。由定理2.4.6可得運(yùn)輸問(wèn)題必有基 本可行解。由Xi

j

的定義知，

Xi

j

min(ai

，bj）可 行域是有界的。必有最優(yōu)解。第二十一頁(yè)，共一百二十五頁(yè)。（4）矩陣A的秩為（m+n-1）A是一個(gè)（m+n） （

m*n）型矩陣 一般來(lái)說(shuō)：

（m+n） （

m*n）因此秩最大為（m+n）又前m方程與后n個(gè)方程和相等。故r（A） ，實(shí)際是等于（m+n-1）。第二十二頁(yè)，共一百二十五頁(yè)。X11X12…X1nX21

X22…X2n….

Xm1Xm2…Xmn11….121113….4111567811111…..111na1a2..amb1b1….bn第二十三頁(yè)，共一百二十五頁(yè)。A(m+n)(mn)11

p

121np21p31…

pp

…

p0

0

….

0m111?….11

1

….

11…..1第二十四頁(yè)，共一百二十五頁(yè)。p…

p11

p

12

1np21

p

31

…

p

m1線性無(wú)關(guān)，而p

ij與

p

ij

只差一個(gè)分量。由向量相關(guān)理論可知：一組線性無(wú)關(guān)向量組在 相同的位置上加相同多的分量后得到的新向量 也線性無(wú)關(guān)?！?/p>

p

1n因此p11

p

12p

31r(A)=

(m+n-1)p

21…p

m1也線性無(wú)關(guān)。第二十五頁(yè)，共一百二十五頁(yè)。5.2表上作業(yè)法由于運(yùn)輸問(wèn)題的特殊性，因此求解運(yùn)輸 問(wèn)題往往不用單純形法。而用表上作業(yè) 法。1、用西北角法或最小元素法確定基本可 行解。2、用位勢(shì)法求解檢驗(yàn)數(shù)3、用閉回路調(diào)整法求最優(yōu)解第二十六頁(yè)，共一百二十五頁(yè)。收點(diǎn)發(fā)點(diǎn)B1B2…Bn發(fā)量A1a1A2a2……Amam收量b1b2…bn第二十七頁(yè)，共一百二十五頁(yè)。例5.2.1表5.3收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A17A24A39收量3656第二十八頁(yè)，共一百二十五頁(yè)。收點(diǎn)發(fā)點(diǎn)B1B2B3B4A1311310A21928A374105第二十九頁(yè)，共一百二十五頁(yè)。1、西北角法?(I，j)，?從（1，1）開(kāi)始，比較a1，b1。?X11=min（a1，b1）=b1=3第三十頁(yè)，共一百二十五頁(yè)。收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A17A24A39收量3656第三十一頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)量A1347-3

-4A2224-2A3369-3-6收量3-36-4-25-2-36?X11=min（a1，b1）=b1=3?X12=min（a"1，b2）=

a"1

=422?X

=min（ab"

）=

b"

=22，

2

第2三十二頁(yè)，共一百二十五頁(yè)。表5.5B1B2B3B4發(fā)量A1347

–3-

4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=3

3+

4

11+

2

9+

2第三十三頁(yè)，共一百二十五頁(yè)。2+

3

10+

65=133(2、最小元素法(表5.6-7)B1B2B3B4發(fā)量A1311341037-4-3A21392184-3A374610539-6-3收量3-36-65-1-46-3?C21=1，X21=min（a2，b1）=b1=3?C23=2，

X23=min（a"2，b3）=

min（

1，5）=

a"2

=1第三十四頁(yè)，共一百二十五頁(yè)。5.2.2位勢(shì)法求檢驗(yàn)數(shù)Pijij=Cij-Zij=

Cij-CBB-1

5.2.1(i=1，2…..m；

j=1，2……n)Max

f=aiui+bjvjst

ui+

vj2……n)Cij(i=1，2…..m)

(j=1，ui，vj

無(wú)正負(fù)W=(u1，…，um，v1，…，vn）5.2.3Ui=(xi1,xi2,xi3,xi4in

j

1j

2jmj…..x

),

v

=(x

,x

,x…x

)I=1m

nj=1第三十五頁(yè)，共一百二十五頁(yè)。Min

Z=cijxiji

jxij

=ai

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

=bj

(j=1,2……n)xij0

(i=1,2…..m;

j=1,2……n)jmnin

m第三十六頁(yè)，共一百二十五頁(yè)。運(yùn)輸問(wèn)題線性規(guī)劃模型供應(yīng)地約束需求地約束第三十七頁(yè)，共一百二十五頁(yè)。5.2.3代5.2.1ij=Cij-WPij=

Cij-

(u1，…，um，v1，…，vn)(

ei+e

m+j)=Cij-

(ui+vj）(i=1，2…..m；j=1，2……n)5.2.4A=X11X12…X1nX21X22…X2n….

Xm1Xm2…Xmn11….121113….41115116111第三十八頁(yè)，共一百二十五頁(yè)?；兞康?/p>

:（i，j）Cij-

(ui+vj）=0

JB

（5.2.5）因?yàn)闉橐阎?/p>

5.2.5）有（m+n）個(gè)未知量令Vn=0

（5.2.6）非基變量檢驗(yàn)數(shù):ij=

=Cij-

(ui+vj）(i，j）JN

（

5.2.7）第三十九頁(yè)，共一百二十五頁(yè)。A、公式求檢驗(yàn)數(shù)第四十頁(yè)，共一百二十五頁(yè)。表5.5B1B2B3B4發(fā)量A1347

–3-

4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=3

3+

4

11+

29+

2

2+

3

10+

6

5=133(第四十一頁(yè)，共一百二十五頁(yè)。5.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=0第四十二頁(yè)，共一百二十五頁(yè)。代入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，第四十三頁(yè)，共一百二十五頁(yè)。代入公式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第四十四頁(yè)，共一百二十五頁(yè)。ij=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)=-13?ij0，故不是最優(yōu)解第四十五頁(yè)，共一百二十五頁(yè)。B、檢驗(yàn)數(shù)表格求解1、作表格（3+1)×(4+1）的表2、第(3+1)行為vj行，(4+1)列為ui列ij，3、右上角標(biāo)出C

其中非基變量用 框住。第四十六頁(yè)，共一百二十五頁(yè)。表5.8B1B2B3B4uiA1311310-1A21928-3A374非1055vj4

71250?V4=0，?基變量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0JB(5.2.5)（第i四十，七頁(yè)，共j一百）二十五頁(yè)。計(jì)算：V4=0，基變量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0（I，j）Cij=

(ui+vj）5.2.10JB

5.2.5因?yàn)椋篤4=0，C34=(u3+v4）=u3=5，第四十八頁(yè)，共一百二十五頁(yè)。B1B2B3B4uiA1311310-1A21928-3A37非41055vj471250Cij=

(ui+vj）5.2.10C22=

(u2+v2）

v2=

C22-u2=9-（-3）=12u1=

C12-v2

=11-12=-1第四十九頁(yè)，共一百二十五頁(yè)。B1B2B3B4uiA1311-131110-1A20192118-3A3-27-1341055vj471250ij=

=Cij-

(ui+vj）

(i，j）

JN(5.2.7)13=

=C13-

(u1+v3）=3-(-1+5)=-114=

=C14-

(u1+v4）=10-(-1+0)=11?

==C

-(u+v

）=1-第(五十頁(yè)-，共3一百+二十五4頁(yè)。)=0例5.2.2以例5.2.1的最小元素法求得的基本可行解 為例。見(jiàn)表5.7用位勢(shì)法計(jì)算檢驗(yàn)數(shù)。第五十一頁(yè)，共一百二十五頁(yè)。最小元素法(表5.6-7)B1B2B3B4發(fā)量A1311341037-4-3A21

3解92184-3A374610539-6-3收量3-36-65-1-46-3第五十二頁(yè)，共一百二十五頁(yè)。表5.11B1B2B3B4uiA11321131010A21192-189A3107非

74121055vj-8-1-70第五十三頁(yè)，共一百二十五頁(yè)。5.2.3用閉回路法調(diào)整當(dāng)前基本可行解定義5.2.將變量Xij在調(diào)運(yùn)表中所對(duì)應(yīng)的空格記做

(i，j)稱(chēng)為格點(diǎn)。而Xij系數(shù)列向量Pij也稱(chēng)作格

點(diǎn)(i，j)所對(duì)應(yīng)的系數(shù)列向量，若Xij為基變量，則(i，j)稱(chēng)為基格，否則為非基格。表5.6.7，基格(1，3)，(1，4)(2，1)(2，3)非基格(1，1)，(2，4)(3，1)(2，3)第五十四頁(yè)，共一百二十五頁(yè)。(表5.6-7)B1B2B3B4發(fā)量A1311341037-4-3A21392184-3A374610539-6-3收量3-36-65-1-46-3第五十五頁(yè)，共一百二十五頁(yè)。定義5.2.2定義5.2.2若一組格點(diǎn)經(jīng)過(guò)適當(dāng)?shù)呐判蚝?，能?xiě)成以下形式：(I1，j1)，(I1，j2)，(I2，j2)(I2j3)，(I3，j3)….(Is,，js)，(Is，ji)1則這組格成了閉回路。第五十六頁(yè)，共一百二十五頁(yè)。閉回路特點(diǎn)(1)格點(diǎn)數(shù)大于4第五十七頁(yè)，共一百二十五頁(yè)。(2)形式A：第1格與第2格行號(hào)同，第2與第3 格列號(hào)同，第3、第4格行號(hào)同，第4、第5 格列號(hào)同…最后一格與第一格列號(hào)同。形式B：第1格、第2格列號(hào)同。第2格、第

3格行號(hào)同…最后一格與第一格行號(hào)同。第五十八頁(yè)，共一百二十五頁(yè)。（3）連線構(gòu)成閉回路，一行或一列只包含兩個(gè) 格點(diǎn)，都處在每條邊的端點(diǎn)上。第五十九頁(yè)，共一百二十五頁(yè)。5.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)第六十頁(yè)，共一百二十五頁(yè)。表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)第六十一頁(yè)，共一百二十五頁(yè)。5.13B1B2B3B4B5B6B7A1A2A3A4?包含了閉回路，非構(gòu)成閉回路成格組(1，1)，(1，2)(1，4)(3，4)(3，2)格組(2，5)，(2，6)(2，7)(3，7)(3，6)(3，5)第六十二頁(yè)，共一百二十五頁(yè)。B1B2B3B4uiA1311-131110-1A20192118-3A3-27-13

41055vj471250第六十三頁(yè)，共一百二十五頁(yè)。表5.5B1B2B3B4發(fā)量A1347

–3-

4A2224-2-2A3369-3-6收量3-36-4-25-2-36-6Z=3

3+4

11+2

9+2

2+3

10+6

5=133(萬(wàn)第六十四頁(yè)，共一百二十五頁(yè)。表5.14B1B2B3B4發(fā)量A1347

–3-4A22-2

+4-2-2A30+3-69-3-6收量3-36-4-25-2-36-611+

2

9+

2 2+

3 10+

6

5=133(元)32

=

-13Z=3

3+

4?

=minXij|(i，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)第六十五頁(yè)，共一百二十五頁(yè)。表5.15B1B2B3B4發(fā)量A1347

–3-

4A244-2-2A32169-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+11

4+2

4+4

2+10

1+5

6=109(元)<Z(0)=133

(元)第六十六頁(yè)，共一百二十五頁(yè)。產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的算法其步驟如下．第六十七頁(yè)，共一百二十五頁(yè)。第l步：用西北角規(guī)則或最小元素法求初始基本可 行解。第六十八頁(yè)，共一百二十五頁(yè)。第2步用位勢(shì)法求非基變量的檢驗(yàn)數(shù)。若最優(yōu)準(zhǔn)ij則。

0

得到滿足，則當(dāng)前基本可行解就是最優(yōu)解（當(dāng)前調(diào)運(yùn)方案就是最優(yōu)調(diào)運(yùn)方案），計(jì)算停止。否則轉(zhuǎn)第3步。第六十九頁(yè)，共一百二十五頁(yè)。第3步：取一個(gè)檢驗(yàn)數(shù)最小的非基變量作進(jìn)基變量，其對(duì)應(yīng) 的格為進(jìn)基格（編號(hào)為第1格）。以進(jìn)基格為起始點(diǎn)作出一個(gè)其余頂點(diǎn)均為基格的閉回 路，在該閉回路上，從所有偶數(shù)號(hào)格點(diǎn)的調(diào)運(yùn)量中選出最小值作為調(diào)整量，該格即為離基格，對(duì)應(yīng)的變量為離基變量。第七十頁(yè)，共一百二十五頁(yè)。第4步對(duì)閉回路上的運(yùn)輸量作出調(diào)整：所有奇數(shù)號(hào)格的調(diào)運(yùn)量加上調(diào)整量； 所有偶數(shù)號(hào)格的調(diào)運(yùn)量減去調(diào)整量， 其余的Xij取值不變，這樣就得到了一個(gè) 新的調(diào)運(yùn)方案轉(zhuǎn)第2步。第七十一頁(yè)，共一百二十五頁(yè)。例5.2.3判斷以表5.15所體現(xiàn)的X(1)是否為最優(yōu)解。 若不是，試求出最優(yōu)解。解:對(duì)X(1)用位勢(shì)法求其檢驗(yàn)數(shù)，為此建立表5.16，計(jì)算ui，vj及ij?第七十二頁(yè)，共一百二十五頁(yè)。表5.15B1B2B3B4發(fā)量A1347

–3-

4A244-2-2A32169-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+

11

4+

2

4+

4

2+

10

1+

56=109(元)<Z(0)=133(元)第七十三頁(yè)，共一百二十五頁(yè)。表5.161B1B2B3B4uiA1311-143-21012A21311392118-3A311741055vj-97-150ij

=

minij|ij<0

=

13

=-14 （

i，j）JN非優(yōu)，建第七十四頁(yè)，共一百二十五頁(yè)。表5.17B1B2B3B4發(fā)量A134-10+17A244A32+

11-

169收量3656X(2)=(3，3，1，0，0，0，4，0，0，3，0，6）TZ(2)

=33+11

3+

3

1+

2

4+4

3+

5

6=95(元)<Z(1)=109

(元)第七十五頁(yè)，共一百二十五頁(yè)。?=

min(1，4)=1=

X33表5.18B1B2B3B4uiA13113-21012A2-11-192-3811A31174141055vj-97-1-90不都大于0,也不是最 優(yōu)解．ij

=

minij|

ij<24

=-3 （

i，j）

JN非優(yōu)，建閉回路。第七十六頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)量A133-31+37A24-30+34A33+

36-39收量3656X(3)=(3，0，4，0，0，0，1，3，0，6，0，3）TZ(3)

=33+

3

4+

2

1+

8

3+

4

6+

53=86(元)<Z(2)=95(元)min(6，3，4)=3=

X12?再判斷X(3)是否為最優(yōu)解．建立表5.20，計(jì)算ui，vj及ij第七十七頁(yè)，共一百二十五頁(yè)。表5.20B1B2B3B4uiA133

1131

109A2-112

9288A387411

1055vj-67-1-60不都大于0,也不是最 優(yōu)解．ij

=

minij|ij<0=

21

=-1 （

i，j）

JN非優(yōu)，建閉回路。第七十八頁(yè)，共一百二十五頁(yè)。表5.21B1B2B3B4發(fā)量A13-14+17A20+11-134A3639收量3656X(4)=(2，0，5，0，1，0，0，3，0，6，0，3）TZ(4)

=32+3

5+1

1+8

3+4

6+5

3=85(元)<Z(3)=86(元)第七十九頁(yè)，共一百二十五頁(yè)。表5.22B1B2B3B4uiA1321130*1010A21291288A39774121055vj-7-1-70都大于0，是最 優(yōu)解?X

11=2，

X

13=5，

X

21=1，

X

24=3，

X

32=6，

X

34=3，

XI4

=0第八十頁(yè)，共一百二十五頁(yè)。5.2.4表上作業(yè)法計(jì)算中的兩個(gè)問(wèn)題1、無(wú)窮多個(gè)最優(yōu)解2、退化問(wèn)題第八十一頁(yè)，共一百二十五頁(yè)。1、無(wú)窮多個(gè)最優(yōu)解某個(gè)非基變量檢驗(yàn)數(shù)等于零第八十二頁(yè)，共一百二十五頁(yè)。表5.23B1B2B3B4發(fā)量A12-25=0140*+27A21+23-24A3639收量3656X(5=(0，0，5，2，3，0，0，1，0，6，0，3）TZ(5)

=35+10

2+

1

3+8

1+

4 6+

5 3=85(元)第八十三頁(yè)，共一百二十五頁(yè)。?表22中14

=0

，作閉回路2、退化問(wèn)題（1）在確定初始可行解時(shí)，若已確定的空格（i j）處要填上調(diào)運(yùn)量Xij，而此時(shí)剛好有a

i=b"j，Xij

=a

i=b

j，說(shuō)明此時(shí)Ai的發(fā)運(yùn) 量已經(jīng)用完，而B(niǎo)i的需求已滿足。因此要畫(huà)掉第 i行，j列。第八十四頁(yè)，共一百二十五頁(yè)。x為了保證調(diào)運(yùn)表上有（m+n-1）個(gè)基變量 的值，就要在第i行，j列中任找一個(gè)空格（i，j1）或（i1，j），設(shè)置調(diào)運(yùn)量為Xij1=0，或Xi1j

=0。第八十五頁(yè)，共一百二十五頁(yè)。例5.2.4B1B2B3B4發(fā)量A1311457A277384A3121069收量3656下表為3

4運(yùn)輸問(wèn)題的Cij及發(fā)運(yùn)量和需求

量，試用最小素法求該問(wèn)題的一個(gè)可行解。第八十六頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)量A1311457

–1-6A2770*384-4A3121069-3-6收量3

-36

-65-4-16-6第八十七頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)量A1167A2044A3369收量3656第八十八頁(yè)，共一百二十五頁(yè)。(2)在用閉回路調(diào)整時(shí)出現(xiàn)退化?=minXij|(i，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)如果兩個(gè)或兩個(gè)以上偶數(shù)格點(diǎn)Xij都為極小值 則只能取一個(gè)為離基格，其余作為基格。出 現(xiàn)了退化問(wèn)題第八十九頁(yè)，共一百二十五頁(yè)。例5.2.5表5.26為3×4問(wèn)題的基本可行解及發(fā)運(yùn)量

和需求量。表5.27為基本可行解的檢驗(yàn)數(shù)。 用閉回路法對(duì)其作出調(diào)整。第九十頁(yè)，共一百二十五頁(yè)。表5.26B1B2B3B4發(fā)運(yùn)量A13317A233A3369需求量3656第九十一頁(yè)，共一百二十五頁(yè)。B1B2B3B4A1-2A2-1-1-3A31114第九十二頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)運(yùn)量A13317A2303A3369需求量3656第九十三頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)運(yùn)量A133

-31+37A23-30+33A33

+36-39需求量3656第九十四頁(yè)，共一百二十五頁(yè)。作業(yè)答案P170,5.2第九十五頁(yè)，共一百二十五頁(yè)。第九十六頁(yè)，共一百二十五頁(yè)。B1B2B3B4發(fā)量A161a′17-6

-1A2538-5-3A30*33-3收量6-66-1-53-33?X11=min（a1，b1）=b1=6?X12=min（a′1，b2）=

a′1

=122?X

=min（ab′

）=

b′

=52，

2

2第九十七頁(yè)，共一百二十五頁(yè)。表5.114非B1B2B3B4uiA1587316A24910717A38299vj7-11-8-70?V4=0，基變量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0JB5.2.5（第I九十，八頁(yè)，共一j百二）十五頁(yè)。表5.12檢驗(yàn)數(shù)B1B2B3B4uiA158-2

7-13

316A2-2

4910-10717A38104非3299vj7-11-8-70ij=

=Cij-

(ui+vj）

(I，j）

JN5.2.713=

=C13-

(u1+v3）=7-(-7+16)=-2?

==C

-(u+v

）=3-第(九十1九頁(yè)6，共+一百二0十五)頁(yè)。=-13B1B2B3B4發(fā)量A161-10+17-6

-1A25+13-18-5-3A30*+13-13-3收量6-66-1-53-33=min

Xij|(I，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)=min

1，3，3

=1第一百頁(yè)，共一百二十五頁(yè)。表5.14VUB1B2B3B4uiA158733A24910717A384非299vj2

7-8-70?V4=0，基變量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0

JB5.2.5（第一百I(mǎi)零一，頁(yè)，，共一百j二十五）頁(yè)。表5.15檢驗(yàn)數(shù)ij=

=Cij-(ui+vj）

(I，j）

JN5.2.7B1B2B3B4uiA1513

8非11

733A2-15

4910-10717A3-3

83

4非299vj2

7-8-7013=

=C13-

(u1+v3）=7-(-7+3)=11?

==C

-(u

+v

）=8-第(一百3零3二頁(yè)-，共8一百)二十=五頁(yè)1。3B1B2B3B4發(fā)量A16-21

+27A20+262-28A31

+2-223收量6633=min=minXij|(I，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)2，2，6

=2第一百零三頁(yè)，共一百二十五頁(yè)。表5.17檢驗(yàn)數(shù)5.2.7B1B2B3B4uiA15-2

8非11

733A24915

105

72A3-3

8-12

4非299vj2

77-70ij=

=Cij-

(ui+vj）

(I，j）

JN13=

=C13-

(u1+v3）=7-(-7+3)=11?

==C

-(u+v

）=8-第一(百零3四頁(yè)+，共7一百二)十五=頁(yè)。-2B1B2B3B4發(fā)量A14-03

+

07A20+0608A30+030-03收量6633=min=minXij|(I，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)0，4，6

=0第一百零五頁(yè)，共一百二十五頁(yè)。表5.19檢驗(yàn)數(shù)ij=

=Cij-

(ui+vj）(I，j）

JN5.2.7B1B2B3B4uiA15-2

8非-1

733A2493

105

72A39

84212

9-3vj7275013=

=C13-

(u1+v3）=7-(5+3)=-1?

==C

-(u

+v

）=8-第一(百零3六頁(yè)+，共一7百二)十五=頁(yè)。-2B1B2B3B4發(fā)量A14

-40*+437A22+46-408A30303收量6633=min

Xij|(I，j)為閉回路上所有偶數(shù)號(hào)格點(diǎn)=min

4，6

=4第一百零七頁(yè)，共一百二十五頁(yè)。表5.21檢驗(yàn)數(shù)ij=

=Cij-

(ui+vj）(I，j）

JN5.2.7B1B2B3B4uiA12

5

581

733A2493

103

7-4A3894210

9-1vj0

753013=

=C13-

(u1+v3）=7-(5+3)=-1?

==C

-(u+v

）=5-第一(百零3八3頁(yè)，+共一0百二)十五=頁(yè)。2B1B2B3B4發(fā)量A10437A26208A30303收量6633X(1)=(0，4，0，0，6，2，0，0，0，0，3，0）TZ(1)

=84+

3

3+

6

4+

9

2+

3

2=89第一百零九頁(yè)，共一百二十五頁(yè)。5.2最小元素法第一百一十頁(yè)，共一百二十五頁(yè)。B1B2B3B4B5發(fā)量A125125250-2525-A2107603305100-60-30-10A380670450-70-80收量25-2511525-10-8060-6030-3070-70第一百一十一頁(yè)，共一百二十五頁(yè)。表5.22UVB1B2B3B4B5uiA11015201

201

405A2204015300

3030A3303540552525vj510-1500?V5=0，?基變量:X11

，X12

，X22

，X23

，X24

，X32

，X35C

-

(u

+v

）=0

J5.2.5（第一百I(mǎi)一I十二，頁(yè)，共一百j二十）五頁(yè)。表5.23檢驗(yàn)數(shù)ij

=Cij-

(ui+vj）(I，j）

JN5.2.7B1B2B3B4B5uiA1101530

2015

2035

405A2-15

204015300

3030A30

303530

4030552525vj510-150013

=C13-

(u1+v3）=20-(-15+5)=30?

=C

-(u

+v

）=20-第一(百一5十三+頁(yè)+，共0一百)二十=五頁(yè)1。5ij|ij

=

min

ij<0=

21

=-15 （

I，j）

JNB1B2B3B4B5發(fā)量A125-1525+1050A20+1010-106030100A38070150收量25115603070非優(yōu)，建X(1)=(15，35，0，0，0，10，0，60，30，0，0，80

，0，0，

70）T25+

60Z(1)

=15

10+

35

15+

10

15+

3030

+

80

35+

70

2第一百一十四頁(yè)，共一百二十五頁(yè)。表5.25檢驗(yàn)數(shù)ij

=Cij-

(ui+vj）(I，j）

JN5.2.7B1B2B3B4B5uiA1101515

200

2035

405A22015

40153015

3015A30

303515

4015

552525vj510015