《管理运筹学》第四版 第6章 单纯形法的灵敏度分析与对偶 课后习题解析
- 格式：docx
- 大小：283.58 KB
- 文档页数：10
《管理运筹学》第四版课后习题解析
第6章单纯形法的灵敏度分析与对偶
1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤8
2．解：
（1）c 1≥−0.5 （2）−2≤c 3≤0 （3）c s 2≤0.5
3．解：
（1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤150
4．解： （1）b 1≥−4 （2）0≤b 2≤10 （3）b 3≥4
5. 解：
最优基矩阵和其逆矩阵分别为：⎪⎪⎭⎫ ⎝⎛=1401B ，⎪⎪⎭
⎫ ⎝⎛-=-14011
B ； 最优解变为130321
===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321
===x x x ，，，最小值变为-96；
6．解：
（1）利润变动范围c 1≤3，故当c 1=2时最优解不变。
（2）根据材料的对偶价格为1判断，此做法有利。
（3）0≤b 2≤45。
（4）最优解不变，故不需要修改生产计划。
（5）此时生产计划不需要修改，因为新的产品计算的检验数为−3小于零，对原生产计划没有影响。
7. 解：
(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为
,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件：
解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。
(2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。
（3）B 食品的加工工序改良之后，仍不投产B ，最大利润不变；
若是考虑生产甲产品，则厂家最大获利变为169.7519万元，其中
667.31110,167.144321====x x x x ，，；
（4）若是考虑生产乙产品，则厂家最大获利变为163.1万元，其中
382.70,114321====x x x x ，，；
所以建议生产乙产品。
8．解：
均为唯一最优解，根据从计算机输出的结果看出，如果松弛或剩余变量为零且对应的对偶价格也为零，或者存在取值为零的决策变量并且其相差值也为零时，可知此线性规划有无穷多组解。
9．解：
（1）min f = 10y 1+20y 2. s.t.y 1+y 2≥2 y 1+5y 2≥1 y 1+y 2≥1 y 1,y 2≥0
（2）max z = 100y 1+200y 2. s.t. 1/2y 1+4y 2≤4 2y 1+6y 2≤4 2y 1+3y 2≤2 y 1,y 2≥0
10．解：
（1）min f =−10y 1+50y 2+20y 3. s.t. −2y 1+3y 2+y 3≥1 −3y 1+y 2≥2
−y 1+y 2+y 3 =5
y 1，y 2≥0，y 3没有非负限制。
（2）max z = 6y 1−3y 2+2y 3. s.t.y 1−y 2−y 3≤1
2y 1+y 2+y 3 =3 −3y 1+2y 2−y 3≤−2
y 1，y 2≥0，y 3没有非负限制
11. 解：
,,,, 1 1 1 1 1 109876max 54321544332215154321≥≤+≤+≤+≤+≤+++++=y y y y y y y y y y y y y y y y y y y y z 约束条件：
用对偶问题求解极大值更简单，因为利用单纯形法计算时省去了人工变量。
12. 解:
（1）该问题的对偶问题为
0, 5 332 23 12y 4max 212121212
1≥≤+≤+≤++=y y y y y y y y y f 约束条件：
求解得max f=12，如下所示：
（2）该问题的对偶问题为
,
,01
6
7
58
4 33
3 2
5 3
2 min
3
2
13
2 13
2 1
3 2
1
3
2
1
≥
-
≤
+
-
-
≤
+
-
-
≤
+
-
+
+
=
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
z
约束条件：
求得求解得min z=24，如下所示：
思考：
在求解
中元素的符号没有要求
为非负行向量，列向量其中：约束条件：b C X b AX CX f 0
min ≥≥=
中元素的符号没有要求
为非正行向量，列向量其中：约束条件：b C X b AX CX z 0
max ≥≥=
以上两种线性规划时一般可以选取对偶单纯形法。
13.解：
（1）错误。
原问题存在可行解，则其对偶问题可能存在可行解，也可能无可行解；
（2）正确；
（3）错误。
对偶问题无可行解，则原问题解的情况无法判定，可能无可行解，可能有可行解，甚至为无界解； （4）正确；
14．解：
123
1231
1232233max 2342820,1,,3;0,1,,3
i j z x x x x x x s x x x s x x s x i s j =----+-+=-⎧⎪
+++=⎪⎨
-++=-⎪
⎪==⎩
≥≥ 用对偶单纯形法解如表6-1所示。
表6-1
续表
最优解为x1=6，x2=2，x3=0，目标函数最优值为10。
15. 解：原问题约束条件可以表示为：ta
b
AX+
=，其中b
a和为常数列向量。
令0
=
t，将问题化为标准型之后求解，过程如下：
其中最优基矩阵的逆矩阵为
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
-
=
-
1
1
1
1
1
1
B，
则
⎪
⎪
⎪
⎭
⎫
⎝
⎛
=
⎪
⎪
⎪
⎭
⎫
⎝
⎛
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
-
=
-
3
2
5
3
10
5
1
1
1
1
1
*1b
B
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
=
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
=
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
⎪
⎪
⎪
⎭
⎫
⎝
⎛
-
-
=
-
t
t
t
t
t
t
t
ta
B3
1
3
1
1
1
1
1
1
*1
则⎪⎪⎪
⎭⎫ ⎝⎛+-+=+-t t t ta b B 3325*
1）（ 从而， 1)当
3
0≤≤t 时，最优单纯形表为 此时05>+t ，032>-t ，03>+t ，线性规划问题的最优解为)3,5(),(21t t x x ++=，目标函数最大值为t 311+；
2）当2
7
23≤≤t 时，由032<-t 可知，)3,5(),(21t t x x ++=并非最优解，利用对偶
此时027>-t ，032>+-t ，03>+t ，从而线性规划问题的最优解为
)3,27(),(21t t x x +-=，目标函数的最大值为13； 3）当
102
7
≤≤t 时，
，由027<-t 可知，)3,27(),(21t t x x +-=并非最优解，利用
此时，，，从而线性规划问题的最优解为
)10,0(),(21t x x -=，目标函数的最大值为t 220-；
16.解：先写出原问题的对偶问题
, (4)
14 (3) 123 (2) 232 )1( 24 2020min 21212121212
1≥≥+≥+≥+≥++=y y y y y y y y y y y y f 约束条件：
将5
3
,10121==y y 代入对偶问题的约束条件，得有且只有（2）、（4）式等式成立，
也就是说，其对应的松弛变量取值均为0，（1）和（3）式对应的松弛变量不为0，
从而由互补松弛定理有031==x x ；又因为0,021>>y y ，从而原问题中的两个约束应该取等式，把031==x x 代入其中，得到
027>+-t 05>+t 010>-t
20
320424242=+=+x x x x
解方程组得到2,642==x x 。
经验证2,0,6,04321====x x x x 满足原问题约束条件，从而其为原问题的最优解，对应的目标函数最大值为14；。
