胡运权《运筹学教程》习题答案(第一章)[1]

2011/03/21

第一章习题解答1.1用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。min Z= 2 x1+ 3 x 2 4 x1+ 6 x 2≥ 6 st . 2 x1+ 2 x 2≥ 4 x,x≥ 0 1 2

第一章习题解答(1) min Z= 2 x1+ 3 x 2 4 x1+ 6 x 2≥ 6 st . 2 x1+ 2 x 2≥ 4 x,x≥ 0 1 2

(1)

( 2)

max Z= 3 x1+ 2 x 2 2 x1+ x 2≤ 2 st . 3 x1+ 4 x 2≥ 12 x, x≥ 0 1 2

无穷多最优解， 1 x1= 1, x 2=, Z= 3是一个最优解 3

( 3)

max Z= x1+ x 2 6 x1+ 10 x 2≤ 120 st . 5≤ x1≤ 10 5≤ x≤8 2

( 4)

max Z= 5 x1+ 6 x 2 2 x1 x 2≥ 2 st . 2 x1+ 3 x 2≤ 2 x,x≥ 0 1 2

max Z= 3 x 1+ 2 x 2 2 x1+ x 2≤ 2 (2) st . 3 x 1+ 4 x 2≥ 12 x, x≥ 0 1 2该问题无解

第一章习题解答max Z= x1+ x 2 6 x1+ 10 x 2≤ 120 ( 3) st . 5≤ x1≤ 10 5≤ x≤8 2 唯一最优解，唯最优解 x1= 10, x 2= 6, Z= 16max Z= 5 x1+ 6 x 2 2 x1 x 2≥ 2 ( 4) st . 2 x1+ 3 x 2≤ 2 x,x≥0 1 2 该问题有无界解

第一章习题解答1.2将下述线性规划问题化成标准形式。min Z= 3 x1+ 4 x 2 2 x3+ 5 x 4 4 x1 x 2+ 2 x3 x 4= 2 x+ x x+ 2 x≤ 14 2 3 4 st 1 . 2 x1+ 3 x 2+ x3 x 4≥ 2 x1, x 2, x3≥ 0, x 4无约束 min st x 1 Z= 2 x1 2 x 2+ 3 x 3 x1+ x 2+ x 3= 4 2 x1+ x 2 x 3≤ 6≤ 0, x 2≥ 0, x 3无约束

(1)

(2)

第一章习题解答minZ= 3x1+ 4x2 2x3+ 5x4 4x1 x2+ 2x3 x4= 2 x+ x x+ 2x≤ 14 (1) 4 . st 1 2 3 2x1+ 3x2+ x3 x4≥ 2 x1, x2, x3≥ 0, x4无约束 max Z= 3 x1 4 x 2+ 2 x3 5 x 41+ 5 x 42 4 x1+ x 2 2 x3+ x 41 x 42= 2 x+ x x+ 2 x 2 x+ x= 14 1 2 3 41 42 5 st 2 x1+ 3 x 2+ x3 x 41+ x 42 x6= 2 x1, x 2, x3, x 41, x 42, x 6≥ 0 (2)

第一章习题解答min st x 1 Z= 2 x1 2 x 2+ 3 x 3 x1+ x 2+ x 3= 4 2 x1+ x 2 x 3≤ 6≤ 0, x 2≥ 0, x 3无约束

max Z= 2 x1+ 2 x 2 3 x 31+ 3 x 32 x1+ x 2+ x 31 x 32= 4 st 2 x1+ x 2 x 31+ x 32+ x 4= 6 x1, x 2, x 31, x 32, x 4≥ 0

2011/03/21

第一章习题解答1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。max Z= 3 x1+ x 2+ 2 x 3 12 x1+ 3 x 2+ 6 x 3+ 3 x 4= 9 8 x+ x 4 x+ 2 x= 10 1 2 3 5 st 3 x1 x 6= 0 x j≥ 0( j= 1,, 6), min Z= 5 x1 2 x 2+ 3 x 3+ 2 x 4 x1+ 2 x 2+ 3 x 3+ 4 x 4= 7 st 2 x1+ 2 x 2+ x 3+ 2 x 4= 3 x≥ 0, ( j= 1, 4 ) j

第一章习题解答(1) max Z= 3 x1+ x 2+ 2 x 3 12 x1+

3 x 2+ 6 x 3+ 3 x 4= 9 8 x+ x 4 x+ 2 x= 10 1 2 3 5 st 3 x1 x 6= 0 x j≥ 0( j= 1,, 6),

(1)

x1 0 0 0 0.75

x2 3 0 0 0

x3 0 1.5 0 0

基可行解 x4 x5 0 0 3 0 3.5 8 5 2

x6 0 0 0 2.25

Z 3 3 0 2.25

(2)

第一章习题解答(2) min Z= 5 x1 2 x 2+ 3 x 3+ 2 x 4 x1+ 2 x 2+ 3 x 3+ 4 x 4= 7 st 2 x1+ 2 x 2+ x 3+ 2 x 4= 3 x≥ 0, ( j= 1, 4 ) j

第一章习题解答1.4分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。(1) max Z= 10 x1+ 5 x 2 3 x1+ 4 x 2≤ 9 st . 5 x1+ 2 x 2≤ 8 x,x≥ 0 1 2

x1 0 0 2/5

x2 0.5 0 0

基可行解 x3 2 1 11/5

x4 0 1 0

Z 5 5 43/5

第一章习题解答(2) max Z= 2 x1+ x 2 3 x1+ 5 x 2≤ 15 st . 6 x1+ 2 x 2≤ 24 x,x≥ 0 1 2

第一章习题解答l.5上题(1)中，若目标函数变为max Z= cx1+ dx2,讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。解：得到最终单纯形表如下： Cj→ CB d c基 x2 x1σj b 3/2 1 c x1 0 1 0 d x2 1 0 0 0 x3 5/14 -2/14 0 x4 -3/4 10/35

-5/14d+2/14c 3/14d-10/14c

2011/03/21

第一章习题解答当c/d在3/10到5/2之间时最优解为图中的A点；当 c/d大于5/2且c大于等于0时最优解为图中的B点；当c/d小于3/10且d大于0时最优解为图中的C点；当c/d大于 5/2且c小于等于0时或当c/d小于3/10且d小于0时最优解为图中的原点。为图中的原点

第一章习题解答l.6考虑下述线性规划问题：

max Z= c1 x1+ c 2 x 2 a11 x1+ a12 x 2≤ b1 st . a 21 x1+ a 22 x 2≤ b2 x1, x 2≥ 0 式中，1≤c1≤3, 4≤c2≤6, -1≤a11≤3, 2≤a12≤5, 8≤b1≤12, 2≤a21≤5, 4≤a22≤6, 10≤b2≤14,试确定目标函数最优值的下界和上界。

第一章习题解答解：上界对应的模型如下(c,b取大，a取小)

第一章习题解答解：下界对应的模型如下( c,b取小，a取大)

max Z= 3 x1+ 6 x 2 1 x1+ 2 x 2≤ 12 st . 2 x1+ 4 x 2≤ 14 x1, x 2≥ 0 最优值(上界)为：21

max Z= x1+ 4 x 2 3 x1+ 5 x 2≤ 8 st . 4 x1+ 6 x 2≤ 10 x,x≥ 0 1 2 最优值(下界)为：6.4

第一章习题解答l.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪—类解。max Z= 3x1 x2+ 2 x3 x1+ x2+ x3≥ 6 2 x+ x≥ 2 (1) 1 3 st 2 x2 x3= 0 x j≥ 0, j= 1,,3) ( 该题是无界解。

第一章习题解答min Z= 2 x1+ 3x2+ x3 x1+ 4 x2+ 2 x3≥ 8 (2) st. 3x1+ 2 x2≥ 6 x, x≥ 0 1 2该题是无穷多最优解。 9 4最优解之一： 1=, x2=, x3= 0, Z= 6 x 5 5

2011/03/21

第一章习题解答max Z= 4 x1+ x2 3x1+ x2= 3 4 x+ 3x x= 6 (3) 1 2 3 st

x1+ 2 x2+ x4= 4 x j≥ 0, j= 1,,4) ( 该题是唯一最优解： 2 9 17 x1=, x2=, x3= 1, x4= 0, Z= 5 5 5

第一章习题解答max Z= 10x1+ 15x2+ 12x3 5x1+ 3x2+ x3≤ 9 5x+ 6 x+ 15x≤ 15 (4) 1 2 3 st 2 x1+ x2+ x3≥ 5 x j≥ 0, j= 1,,3) ( 该题无可行解。

第一章习题解答1.8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数a～l值。项目 X4 X5 Cj-Zj X1 X5 Cj-Zj (f) 4 6 1 X1 (b) -1 1 a (g) (h) 0 X2 (c) 3 -1 2 (i) -7 X3 (d) (e) 2 -1 1 j X4 1 0 0 1/2 1/2 k X5 0 1 0 0 1 (l)

第一章习题解答1.9若X(1)、X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。设X max Z= C T X满足： AX= b X≥ 0对于任何 0< a< 1,两点连线上的点(1 )

和X

(2)

X满足：

X= aX

(1 )

+ (1 a ) X(1 ) (1 )

(2)

也是可行解，且(2) (2) (2)

C T X= C T aX= C aXT

+ C T (1 a ) X aC XT

b=2, c=4, d=-2, g=1, h=0, f=3, i=5, e=2, l=0, a=3, j=5, k= -1.5

+ CT X

=C XT

(2)

,所以 X也是最优解。

第一章习题解答1.10线性规划问题max Z=CX,AX=b,X≥0,设 X0为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X*,求证 * * 0 (C -C)(X -X )≥0X 0是 max Z= CX的最优解故的最优解，故 CX 0 CX *≥ 0; X *是 max Z= C * X的最优解，故 C * X * C * X 0≥ 0; (C * C )( X * X 0 )= C(X 0 X *)+ C*(X * X 0)≥ 0

第一章习题解答1.11考虑线性规划问题(i ) (ii ) min Z=α x1+ 2 x 2+ x3 4 x …… 此处隐藏：9909字，全部文档内容请下载后查看。喜欢就下载吧 ……