《运筹学教程》第二章习题答案
1、（1）解：引入松弛变量x4≥0,x5≥0,化不等式为等式为：
minz=2X1 +3X2+4X3
s.t. X1+3X2+2X3+X4=7
4X1+2X2+X5=9
X1,X2,X4,X5≥0
化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ：
minz=2X1 +3X2+4X3′-4X3〞
s.t. X1+3X2+2 X3′-2 X3〞+X4=7
4X1+2X2+X5=9
X1,X2, X3′，X3〞，X4,X5 ≥0
(2)解：引入松弛变量x5≥0,剩余变量X6≥0，化不等式为等式为：
maxz=X1 -5X2+4X3- X4
s.t. X1+2X3+X5=7
X2-2X4-X6=9
X1,X2，X4,X5 ，X6≥0
化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ：
maxz=X1 -5X2+4X3′-4X3〞- X4
s.t. X1+2 X3′-2 X3〞+X5=7
X2-2X4-X6=9
X1,X2, X3′，X3〞，X4,X5 , X6≥0
化极大的目标函数为极小的目标函数： minz=-X1+5X2-4X3′+4X3〞+X4
s.t. X1+2 X3′-2 X3〞+X5=7
X2-2X4-X6=9
X1,X2, X3′，X3〞，X4,X5 , X6≥0
2、(1)是 不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。
(2)不是 不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。
(3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。
3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。
（1）123123123123max2..2644,,0zxxxstxxxxxxxxx
1 第二章线性规划的对偶理论与灵敏度分析
一、学习目的与要求
1、掌握对偶理论及其性质
2、掌握对偶单纯形法
3、熟悉灵敏度分析的概念和内容
4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响
5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围
6、了解参数线性规划的解法
二、课时 6学时
第一节 线性规划的对偶问题
一、对偶问题的提出
定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？
(2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为
0502120343056max21212121xxxxxxxz 2 X*=(15,20)’ Z*=1440元
解(2)：设y1为付给木工每个工时的价格，y2为付给油工每个工时的价格
2.1 用图解法求解下列线性规划问题，并指出各问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
（1）0,84821234..2max2121212121xxxxxxxxtsxxz
解：首先划出平面直角坐标系
X2
4 x1 +3x2=12
X1
Z=2x1+2
2x1+x2=8
4 x1 - x2=8
1234842121xxxx 解：14921xx
所以：2111492maxz
所以有唯一解
(2)0,414234223max2121212121xxxxxxxxxx
解：
X2
-X1+2X2=4
Z=3X1+2X2
X1-X2=3
X1
3X1+2X2=14
1423422121xxxx 解得：4132521xx
所以:144132253maxz
第二章 线性规划的对偶理论
2.1 写出下列线性规划问题的对偶问题
max z=2x1+2x2－4x3
x1 + 3x2 + 3x3 ≤30
4x1 + 2x2 + 4x3≤80
x1、x2，x3≥0
解：其对偶问题为
min w=30y1+ 80y2
y1+ 4y2 ≥2
3y1 + 2y2 ≥2
3y1 + 4y2 ≥－4
y1、y2≥0
2.2 写出下列线性规划问题的对偶问题
min z=2x1+8x2－4x3
x1 + 3x2－3x3 ≥30
－x1 + 5x2 + 4x3 = 80
4x1 + 2x2－4x3≤50
x1≤0、x2≥0，x3无限制
解：其对偶问题为
max w=30y1+80 y2+50 y3
y1－ y2 + 4 y3 ≥2
3y1+5y2 + 2y3 ≤8
－3y1 + 4y2－4y3 =－4
y1≥0，y2无限制，y3≤0
2.3 已知线性规划问题
max z=x1+2x2+3x3+4x4
x1 + 2x2 + 2x3 +3x4≤20
2x1 + x2 + 3x3 +2x4≤20
x1、x2，x3，x4≥0
其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为 min w=20y1+ 20y2
y1 + 2y2 ≥1 （1）
2y1 + y2 ≥2 （2）
2y1 +3y2 ≥3 （3）
3y1 +2y2 ≥4 （4）
y1、y2≥0
将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以
2x3* +3x4* = 20
3x3* +2x4* = 20
解得x3* = x4* = 4。故原问题的最优解为
