运筹学基础及应用第四版胡运权主编课后练习答案
运筹学基础及应用 习题解答
习题一 P46 1．１ （a)
该问题有无穷多最优解,即满足2
1
0664221≤≤=+x x x 且的所有()21,x x ,此时目标函数值3=z 。 （b)
用图解法找不到满足所有约束条件的公共范围,所以该问题无可行解。 1．2
(a) 约束方程组的系数矩阵
????
? ??--=1000030204180036312A
4
最优解()T x 0,0,7,0,10,0=。 (b) 约束方程组的系数矩阵
?
??
? ??=21224321A
最优解T
x ???
??=0,511,0,5
2。
1.3
(a)
(1) 图解法
最优解即为??
?=+=+82594321
21x x x x 的解???
??=23,1x ,最大值235=z
(２）单纯形法
首先在各约束条件上添加松弛变量,将问题转化为标准形式 ???=++=+++++=8
25943 ..00510 max 421321
4321x x x x x x t s x x x x z
则43,P P 组成一个基。令021==x x
得基可行解()8,9,0,0=x ,由此列出初始单纯形表 21σσ>。5
839,58min =??
? ??=θ
02>σ,2328,1421min =???
?
?=θ
0,21<σσ,表明已找到问题最优解0 , 0 , 2
3
1,4321====x x x x 。最大值 2
35*=z (b) （１) 图解法
最优解即为??
?=+=+5
24262121x x x x 的解???
??=23,27x ,最大值
217=z
(2) 单纯形法
首先在各约束条件上添加松弛变量,将问题转化为标准形式
1234523124125
max 2000515.. 6224
5z x x x x x x x s t x x x x x x =+++++=??
++=??++=?
21=+x x 2621+x x
则3P ,4P ，5P 组成一个基。令021==x x
得基可行解()0,0,15,24,5x =，由此列出初始单纯形表
21σσ>。245min ,,461θ??=-= ??
?
02>σ,15
33min ,24,5
22θ??==
???
新的单纯形表为
0,21<σσ，表明已找到问题最优解11x =，2 2x =,315
2
x =
,40x =，50x =。最大值 *172
z = 1．6 (a ）
在约束条件中添加松弛变量或剩余变量,且令
()
0,0 ''2'2''2'22≥≥-=x x x x x ,
z z x x -=-=' ,3'
3
该问题转化为
??
?
????≥=-+-=---+=++-+++-+--=0,,,,,63382412
4332x ..0023' max 54'3''2'21'
3''2'215'
3''2'214'3''2'2154'
3''2'21x x x x x x x x x x x x x x x x x x x t s x x x x x x z
其约束系数矩阵为
????
?
??------=003113102114014332A
在A 中人为地添加两列单位向量87,P P
????
? ??------100031130110211400014332 令7654'
3''2'2
10023' max Mx Mx x x x x x x z --++-+--= 得初始单纯形表
（b ） 在约束条件中添加松弛变量或剩余变量，且令(
)'
''
'''
33333 0,0
x x x x x =-≥≥，
'z z =-
该问题转化为
'''
123345'''
12334'''
12335'''
1233'''123345max '3500x 2623316.. 5510,,,,,0z x x
x x x x x x x x x x x x x s t x x x x x x x x x x =--+-++?++--=?+--+=??++-=?
?≥?
其约束系数矩阵为
121110************A --??
?=-- ?
?-??
在A 中人为地添加两列单位向量87,P P
121110102133010011550001--?? ?- ? ?-??
令'
''
12334567max '3500z x x x x x x Mx Mx =--+-++--
1.7
(a)解1：大Ｍ法
在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得
123456789max 22000z x x x x Mx x Mx x Mx =-++-+-+-
1234513672389123456789622,,20,,,,,,,,0
x x x x x x x x x s t x x x x x x x x x x x x x ++-+=??-+-+=?
?
--+=??≥?
由单纯形表计算结果可以看出，40σ>且40(1,2,3)i a i <=，所以该线性规划问题有无界解 解2:两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量468,,,x x x 再加上人工变量
579,,,x x x 得第一阶段的数学模型
第一阶段求得的最优解*
T
X (,,,0,0,0,0,0,0)442
=，目标函数的最优值*
0ω=。
因人工变量5790x x x ===，所以*T 377
(,
,,0,0,0,0,0,0)442
X =
是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题
由表中计算结果可以看出，40σ>且40(1,2,3)i a i <=,所以原线性规划问题有无界解。
(ｂ)解1：大M 法
在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得
12345
67min 2300z x x x x x Mx Mx =+++++-
123461257123456789428326,,,,,,,,,,0
x x x x x x x x x s t x x x x x x x x x ++-+=??+-+=?
?
??≥?