运筹学练习题答案

一、判断题

1× 2√ 3× 4 √5× 6×

二．若x3的系数变为，则线性规划的最终单纯形表如下

cj CB XB b 1 x2 6  x3 4 -1 0 1 1 2 检验数 2 1  0 0 x1 x2 x3 x4 x5 3 1 0 2 1 -1 0 0 --2 -2-1 若最优解不变，满足条件：

10 20， 2101即2 12所以，1/21

三、解：对偶线性规划问题为：

- 1 -

练习题 答 案

minw8y110y26y310y17y24y31y6y8y2123 y2y6y41234y5yy3123y1无约束；y20,y30

四、 （1）、将原问题划为标准形得：

MaxZ2x13x26x30x40x5

x450x13x22x3x580 x14x23x3x,x,x,x,x023451 C(j) Basis X4 X5 X3 X5 X1 X5 C(i) 0 0 8 0 5 0 5 X1 1 1 5 [1/2] -1/2 1 1 0 0 6 X2 3 4 6 3/2 -1/2 -6 3 1 -9 8 X3 [2] 3 8 1 0 0 2 1 -2 0 X4 1 0 0 1/2 -3/2 -4 1 -1 -5 0 X5 0 1 0 0 1 0 0 1 0 R. H. S. 50 80 0 25 5 -200 50 30 -250 25 80/3 50 C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 所以，最优解：X=（50，0，0，0，0，30）；最优值Z＝250 （2）最优解满足约束条件：x12x2100，则最优解不变。

五、解：用伏格尔法确定初始调运方案为：

- 2 -

练习题 答 案

A1 A2 A3 A4 供 B1 25 25 B2 20 5 25 B3 15 30 5 50 销 15 20 30 35 11=2；12=-2；13=3；21=1；23=5；32=-1 有ij0,所以需要调整为： 供 A1 A2 A3 A4 B1 25 25 B2 15 10 25 B3 15 5 30 50 销 15 20 30 35 11=1；12=2；13=2；21=0；23=4；34=1 因为ij0，所以为最优方案。

Min Z=25*7+15*2+10*6+15*9+5*3+30*4=535

六、（1）最小树如下图

权值26 (2)各点的标号分别为：

A[0],D[2],C[5],B[6],E[5],G[10],F[13],S[12]

A到S的最短路径：ADES 最短距离：12

- 3 -