运筹学基础(第2版)何坚勇运输问题

运输问题是线性规划问题，由于其约束条件的特殊性，产生了特殊的解法。第五章 运输问题第一页，共一百二十五页。从3个发点A1，A2,，A3，向4个收点B1，B2，B3，B4发送某种货物。Ai

供应量为14，27，19。Bj

收点的收量为22，13，12，13。由Ai

运往Bj

单位货物的运费为Cij，由Ai

运往Bj

货物的运量为Xij。问如何调配，才能使运费最省？第二页，共一百二十五页。32131运输问题网络图s2=A2

24

B4s3=A3B1B2B3s1=A1供应量供应地运价需求量需求地6753851047

296B1第三页，共一百二十五页。运输问题线性规划模型供应地约束需求地约束第四页，共一百二十五页。5.1运输问题数学模型和特点第五页，共一百二十五页。5.1.1产销平衡问题的数学模型问题的提出 从m个发点A1,

A2,

…..Am向n个收点B1,B2…..Bn发送某种货物。Ai发点的发量为ai，Bj收点的收量为bj。由Ai

运往Bj

单位货物的运费为Cij，由Ai

运往Bj

货物的运量为Xij。问如何调配，才能使运费最省？第六页，共一百二十五页。当发点的发量总和为

ai，收点的收量总和为bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。续第七页，共一百二十五页。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第八页，共一百二十五页。运输问题的数学模型：0,

bj其中

ai

0,

cij

0且共有

m+n 个约束方程。并成立：imnai

=

bjj第九页，共一百二十五页。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)•第十页，共一百二十五页。由于

ai

=

bj成立其m+n个约束方程并不是独立的。实际上只有

m+n-1个是独立的。即约束方程系数矩阵的秩为

m+n-1。运输问题解的结构nmij第十一页，共一百二十五页。PijPij=ei+em+j(i=1，….，m，j=1，…，n)

ei为第i个分量为1其余分量为0的m+n维向量。

em+j为第m+j个分量为1其余分量为0的m+n维分量。第十二页，共一百二十五页。运输问题矩阵描述•min

CX；AX=b

（5.1.3）x

0S.T•其中A为第十三页，共一百二十五页。X11

X12…

X1nX21

X22…X2n….

Xm1Xm2…

Xmn11….121113….41115678111…..11111na1a2..amb1b1….bn第十四页，共一百二十五页。5.1.2运输问题数学模型的特点第十五页，共一百二十五页。(1)有m n列，每列有(m+n)个元素，其中有两个1，其余为0。对于列Pij来说，两个1的位置为i与m+j个分量Pij=ei+e

m+jei为第i个分量为1其余分量为0的m+n维单位向量em+j为第m+j分量为1，其余分量为0的m+j分量为0的m+n 维单位向量。第十六页，共一百二十五页。如第十七页，共一百二十五页。（2）E0….00E….0……00…EII…I第十八页，共一百二十五页。A=A有(m+n)行，每行前m行有n个1并连 在一起，其余为零。E=(1，1，1，…..，）（3）运输问题有最优解m

n证明由于 ai

=

bj=d成立i

j5.1.6令Xij=ai

bj/dI=1，2，…mJ=1，2，…n代入5.1.1第十九页，共一百二十五页。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第二十页，共一百二十五页。xu5.1.6是运输问题的可行解。由定理2.4.6可得运输问题必有基 本可行解。由Xi

j

的定义知，

Xi

j

min(ai

，bj）可 行域是有界的。必有最优解。第二十一页，共一百二十五页。（4）矩阵A的秩为（m+n-1）A是一个（m+n） （

m*n）型矩阵 一般来说：

（m+n） （

m*n）因此秩最大为（m+n）又前m方程与后n个方程和相等。故r（A） ，实际是等于（m+n-1）。第二十二页，共一百二十五页。X11X12…X1nX21

X22…X2n….

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

p

121np21p31…

pp

…

p0

0

….

0m111•….11

1

….

11…..1第二十四页，共一百二十五页。p…

p11

p

12

1np21

p

31

…

p

m1线性无关，而p

ij与

p

ij

只差一个分量。由向量相关理论可知：一组线性无关向量组在 相同的位置上加相同多的分量后得到的新向量 也线性无关。…

p

1n因此p11

p

12p

31r(A)=

(m+n-1)p

21…p

m1也线性无关。第二十五页，共一百二十五页。5.2表上作业法由于运输问题的特殊性，因此求解运输 问题往往不用单纯形法。而用表上作业 法。1、用西北角法或最小元素法确定基本可 行解。2、用位势法求解检验数3、用闭回路调整法求最优解第二十六页，共一百二十五页。收点发点B1B2…Bn发量A1a1A2a2……Amam收量b1b2…bn第二十七页，共一百二十五页。例5.2.1表5.3收点发点B1B2B3B4发量A17A24A39收量3656第二十八页，共一百二十五页。收点发点B1B2B3B4A1311310A21928A374105第二十九页，共一百二十五页。1、西北角法•(I，j)，•从（1，1）开始，比较a1，b1。•X11=min（a1，b1）=b1=3第三十页，共一百二十五页。收点发点B1B2B3B4发量A17A24A39收量3656第三十一页，共一百二十五页。B1B2B3B4发量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三十二页，共一百二十五页。表5.5B1B2B3B4发量A1347

–3-

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

3+

4

11+

2

9+

2第三十三页，共一百二十五页。2+

3

10+

65=133(2、最小元素法(表5.6-7)B1B2B3B4发量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第三十四页，共一百二十五页。5.2.2位势法求检验数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=(u1，…，um，v1，…，vn）5.2.3Ui=(xi1,xi2,xi3,xi4in

j

1j

2jmj…..x

),

v

=(x

,x

,x…x

)I=1m

nj=1第三十五页，共一百二十五页。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第三十六页，共一百二十五页。运输问题线性规划模型供应地约束需求地约束第三十七页，共一百二十五页。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第三十八页，共一百二十五页。基变量的

:（i，j）Cij-

(ui+vj）=0

JB

（5.2.5）因为为已知，而（

5.2.5）有（m+n）个未知量令Vn=0

（5.2.6）非基变量检验数:ij=

=Cij-

(ui+vj）(i，j）JN

（

5.2.7）第三十九页，共一百二十五页。A、公式求检验数第四十页，共一百二十五页。表5.5B1B2B3B4发量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(第四十一页，共一百二十五页。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第四十二页，共一百二十五页。代入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，第四十三页，共一百二十五页。代入公式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第四十四页，共一百二十五页。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，故不是最优解第四十五页，共一百二十五页。B、检验数表格求解1、作表格（3+1)×(4+1）的表2、第(3+1)行为vj行，(4+1)列为ui列ij，3、右上角标出C

其中非基变量用 框住。第四十六页，共一百二十五页。表5.8B1B2B3B4uiA1311310-1A21928-3A374非1055vj4

71250•V4=0，•基变量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0JB(5.2.5)（第i四十，七页，共j一百）二十五页。计算：V4=0，基变量:X11

，X12

，X22

，X23

，X33

，X34Cij-

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

(ui+vj）5.2.10JB

5.2.5因为：V4=0，C34=(u3+v4）=u3=5，第四十八页，共一百二十五页。B1B2B3B4uiA1311310-1A21928-3A37非41055vj471250Cij=

(ui+vj）5.2.10C22=

(u2+v2）

v2=

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

C12-v2

=11-12=-1第四十九页，共一百二十五页。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-第(五十页-，共3一百+二十五4页。)=0例5.2.2以例5.2.1的最小元素法求得的基本可行解 为例。见表5.7用位势法计算检验数。第五十一页，共一百二十五页。最小元素法(表5.6-7)B1B2B3B4发量A1311341037-4-3A21

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

74121055vj-8-1-70第五十三页，共一百二十五页。5.2.3用闭回路法调整当前基本可行解定义5.2.将变量Xij在调运表中所对应的空格记做

(i，j)称为格点。而Xij系数列向量Pij也称作格

点(i，j)所对应的系数列向量，若Xij为基变量，则(i，j)称为基格，否则为非基格。表5.6.7，基格(1，3)，(1，4)(2，1)(2，3)非基格(1，1)，(2，4)(3，1)(2，3)第五十四页，共一百二十五页。(表5.6-7)B1B2B3B4发量A1311341037-4-3A21392184-3A374610539-6-3收量3-36-65-1-46-3第五十五页，共一百二十五页。定义5.2.2定义5.2.2若一组格点经过适当的排序后，能写成以下形式：(I1，j1)，(I1，j2)，(I2，j2)(I2j3)，(I3，j3)….(Is,，js)，(Is，ji)1则这组格成了闭回路。第五十六页，共一百二十五页。闭回路特点(1)格点数大于4第五十七页，共一百二十五页。(2)形式A：第1格与第2格行号同，第2与第3 格列号同，第3、第4格行号同，第4、第5 格列号同…最后一格与第一格列号同。形式B：第1格、第2格列号同。第2格、第

3格行号同…最后一格与第一格行号同。第五十八页，共一百二十五页。（3）连线构成闭回路，一行或一列只包含两个 格点，都处在每条边的端点上。第五十九页，共一百二十五页。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)第六十页，共一百二十五页。表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.13B1B2B3B4B5B6B7A1A2A3A4•包含了闭回路，非构成闭回路成格组(1，1)，(1，2)(1，4)(3，4)(3，2)格组(2，5)，(2，6)(2，7)(3，7)(3，6)(3，5)第六十二页，共一百二十五页。B1B2B3B4uiA1311-131110-1A20192118-3A3-27-13

41055vj471250第六十三页，共一百二十五页。表5.5B1B2B3B4发量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(万第六十四页，共一百二十五页。表5.14B1B2B3B4发量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)为闭回路上所有偶数号格点第六十五页，共一百二十五页。表5.15B1B2B3B4发量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

(元)第六十六页，共一百二十五页。产销平衡运输问题的算法其步骤如下．第六十七页，共一百二十五页。第l步：用西北角规则或最小元素法求初始基本可 行解。第六十八页，共一百二十五页。第2步用位势法求非基变量的检验数。若最优准ij则。

0

得到满足，则当前基本可行解就是最优解（当前调运方案就是最优调运方案），计算停止。否则转第3步。第六十九页，共一百二十五页。第3步：取一个检验数最小的非基变量作进基变量，其对应 的格为进基格（编号为第1格）。以进基格为起始点作出一个其余顶点均为基格的闭回 路，在该闭回路上，从所有偶数号格点的调运量中选出最小值作为调整量，该格即为离基格，对应的变量为离基变量。第七十页，共一百二十五页。第4步对闭回路上的运输量作出调整：所有奇数号格的调运量加上调整量； 所有偶数号格的调运量减去调整量， 其余的Xij取值不变，这样就得到了一个 新的调运方案转第2步。第七十一页，共一百二十五页。例5.2.3判断以表5.15所体现的X(1)是否为最优解。 若不是，试求出最优解。解:对X(1)用位势法求其检验数，为此建立表5.16，计算ui，vj及ij•第七十二页，共一百二十五页。表5.15B1B2B3B4发量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(元)第七十三页，共一百二十五页。表5.161B1B2B3B4uiA1311-143-21012A21311392118-3A311741055vj-97-150ij

=

minij|ij<0

=

13

=-14 （

i，j）JN非优，建第七十四页，共一百二十五页。表5.17B1B2B3B4发量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

(元)第七十五页，共一百二十五页。•=

min(1，4)=1=

X33表5.18B1B2B3B4uiA13113-21012A2-11-192-3811A31174141055vj-97-1-90不都大于0,也不是最 优解．ij

=

minij|

ij<24

=-3 （

i，j）

JN非优，建闭回路。第七十六页，共一百二十五页。B1B2B3B4发量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)是否为最优解．建立表5.20，计算ui，vj及ij第七十七页，共一百二十五页。表5.20B1B2B3B4uiA133

1131

109A2-112

9288A387411

1055vj-67-1-60不都大于0,也不是最 优解．ij

=

minij|ij<0=

21

=-1 （

i，j）

JN非优，建闭回路。第七十八页，共一百二十五页。表5.21B1B2B3B4发量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(元)第七十九页，共一百二十五页。表5.22B1B2B3B4uiA1321130*1010A21291288A39774121055vj-7-1-70都大于0，是最 优解•X

11=2，

X

13=5，

X

21=1，

X

24=3，

X

32=6，

X

34=3，

XI4

=0第八十页，共一百二十五页。5.2.4表上作业法计算中的两个问题1、无穷多个最优解2、退化问题第八十一页，共一百二十五页。1、无穷多个最优解某个非基变量检验数等于零第八十二页，共一百二十五页。表5.23B1B2B3B4发量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(元)第八十三页，共一百二十五页。•表22中14

=0

，作闭回路2、退化问题（1）在确定初始可行解时，若已确定的空格（i j）处要填上调运量Xij，而此时刚好有a

i=b"j，Xij

=a

i=b

j，说明此时Ai的发运 量已经用完，而Bi的需求已满足。因此要画掉第 i行，j列。第八十四页，共一百二十五页。x为了保证调运表上有（m+n-1）个基变量 的值，就要在第i行，j列中任找一个空格（i，j1）或（i1，j），设置调运量为Xij1=0，或Xi1j

=0。第八十五页，共一百二十五页。例5.2.4B1B2B3B4发量A1311457A277384A3121069收量3656下表为3

4运输问题的Cij及发运量和需求

量，试用最小素法求该问题的一个可行解。第八十六页，共一百二十五页。B1B2B3B4发量A1311457

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

-36

-65-4-16-6第八十七页，共一百二十五页。B1B2B3B4发量A1167A2044A3369收量3656第八十八页，共一百二十五页。(2)在用闭回路调整时出现退化•=minXij|(i，j)为闭回路上所有偶数号格点如果两个或两个以上偶数格点Xij都为极小值 则只能取一个为离基格，其余作为基格。出 现了退化问题第八十九页，共一百二十五页。例5.2.5表5.26为3×4问题的基本可行解及发运量

和需求量。表5.27为基本可行解的检验数。 用闭回路法对其作出调整。第九十页，共一百二十五页。表5.26B1B2B3B4发运量A13317A233A3369需求量3656第九十一页，共一百二十五页。B1B2B3B4A1-2A2-1-1-3A31114第九十二页，共一百二十五页。B1B2B3B4发运量A13317A2303A3369需求量3656第九十三页，共一百二十五页。B1B2B3B4发运量A133

-31+37A23-30+33A33

+36-39需求量3656第九十四页，共一百二十五页。作业答案P170,5.2第九十五页，共一百二十五页。第九十六页，共一百二十五页。B1B2B3B4发量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第九十七页，共一百二十五页。表5.114非B1B2B3B4uiA1587316A24910717A38299vj7-11-8-70•V4=0，基变量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0JB5.2.5（第I九十，八页，共一j百二）十五页。表5.12检验数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九页6，共+一百二0十五)页。=-13B1B2B3B4发量A161-10+17-6

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

Xij|(I，j)为闭回路上所有偶数号格点=min

1，3，3

=1第一百页，共一百二十五页。表5.14VUB1B2B3B4uiA158733A24910717A384非299vj2

7-8-70•V4=0，基变量:X11

，X12

，X22

，X23

，X33

，X34Cij-

(ui+vj）=0

JB5.2.5（第一百I零一，页，，共一百j二十五）页。表5.15检验数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二页-，共8一百)二十=五页1。3B1B2B3B4发量A16-21

+27A20+262-28A31

+2-223收量6633=min=minXij|(I，j)为闭回路上所有偶数号格点2，2，6

=2第一百零三页，共一百二十五页。表5.17检验数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四页+，共7一百二)十五=页。-2B1B2B3B4发量A14-03

+

07A20+0608A30+030-03收量6633=min=minXij|(I，j)为闭回路上所有偶数号格点0，4，6

=0第一百零五页，共一百二十五页。表5.19检验数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六页+，共一7百二)十五=页。-2B1B2B3B4发量A14

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

Xij|(I，j)为闭回路上所有偶数号格点=min

4，6

=4第一百零七页，共一百二十五页。表5.21检验数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页，+共一0百二)十五=页。2B1B2B3B4发量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第一百零九页，共一百二十五页。5.2最小元素法第一百一十页，共一百二十五页。B1B2B3B4B5发量A125125250-2525-A2107603305100-60-30-10A380670450-70-80收量25-2511525-10-8060-6030-3070-70第一百一十一页，共一百二十五页。表5.22UVB1B2B3B4B5uiA11015201

201

405A2204015300

3030A3303540552525vj510-1500•V5=0，•基变量:X11

，X12

，X22

，X23

，X24

，X32

，X35C

-

(u

+v

）=0

J5.2.5（第一百I一I十二，页，共一百j二十）五页。表5.23检验数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十三+页+，共0一百)二十=五页1。5ij|ij

=

min

ij<0=

21

=-15 （

I，j）

JNB1B2B3B4B5发量A125-1525+1050A20+1010-106030100A38070150收量25115603070非优，建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第一百一十四页，共一百二十五页。表5.25检验数ij

=Cij-

(ui+vj）(I，j）

JN5.2.7B1B2B3B4B5uiA1101515

200

2035

405A22015

40153015

3015A30

303515

4015

552525vj510015