第二章线性规划的对偶理论
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。故原问题的最优解为
X*=（0，0，4，4）T
2.4用对偶单纯形法求解下列线性规划
min z=4x1+2x2+6x3
2x1 +4x2 +8x3 ≥24
4x1 + x2 + 4x3≥8
x1、x2，x3≥0
解将问题改写成如下形式
max（－z）=－4x1－2x2－6x3
－2x1－4x2 －8x3 + x4=－24
－4x1－x2－4x3+x5 =－8
x1、x2，x3，x4，x5≥0
显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为
X*=（0，4，4）T
最优值为z*=32
2.5设某线性规划问题的初始单纯形表和最优单纯形表分别为
现在要问：
（1）c3在什么范围内变化，表中最优解不变？
（2）c3从3变为8，求新的最优解
解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。
（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表2—11中所示的新的最优解。
即新的最优解为X=（0，160/3，20/3）。
2.6某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、
B、C三种原材料的数量以及单位产品的利润如下表所示：
若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为：
max z=5x1+4x2
x1 +3x2 ≤90
2x1 + x2≤80
x1 + x2≤45
x1、x2，x3≥0
用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表2—13和3—14所示，试分析使最优基不变的b3的变化范围。
解 由表2—13和表2—14可知，当B=（p 3，p 1，p 2）时，有
⎪⎪⎪⎭⎫ ⎝⎛---=-2101105211B ⎪⎪⎪⎭
⎫ ⎝⎛=-1035251b B 当下式成立时，最优基不变。
0103552500210110521103525333311≥⎪
⎪⎪
⎭⎫
⎝
⎛∆+∆-∆-=⎪⎪⎪⎭⎫ ⎝⎛∆⎪⎪⎪⎭⎫ ⎝⎛---+⎪⎪⎪⎭⎫ ⎝⎛=∆+--b b b b b B b B
即 25－5Δb 3≥0，35－Δb 3≥0，10+Δb 3≥0
解不等式有
－5≤Δb 3≤5 此外，以B -1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb 3，即
⎭⎬⎫⎩⎨⎧----≤∆≤⎭⎬⎫⎩⎨⎧-525,135min 210max b
同样可得 －5≤Δb 3≤5
因此，不影响最优基的b 3的变化范围是[40，50]。
2.7 在例2.11的生产计划问题中：（1）若生产产品甲的工艺结构发生了改进，
这时关于它的技术向量变为p 1‘
=（1，2，1/2）T ，试分析对原最优计划有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A 、B 、C 原材料各为2、4、1kg ，每件可获利润8千元。问该厂是否应该生产该产品和生产多少？
解 （1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生改变，具体为
⎪⎪⎪
⎭
⎫ ⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛---=-02/12/12/111210110521'11p B
代入原最优单纯形表中得到
