运筹学_第2章_对偶理论习题.doc

第二章 线性规划的对偶理论
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中。
表2—7
Cj
－4
－2
－6
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x4
-2
[-4]
-8
1
0
-24
0
x5
-4
-1
-4
0
1
-8

－z
-4
-2
-6
0
0
0
θ
-4/-2
-2/-4
-6/-10
0
0

-2
x2
1/2
1
2
-1/4
0
6
0
x5
-7/2
0
[-2]
-1/4
1
-2

－z
-3
0
-2
-1/2
0
-120
θ
-3/(-7/2)
0
-2/-2

(-1/2)/(-1/4)
0

-2
x2
-3
1
0
-1/2
1
4
-6
x3
7/4
0
1
1/8
-1/2
4

－z
-1/2
0
0
-1/4
-1
-32
最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为
X*=（0，4，4）T
最优值为z*=32
2.5 设某线性规划问题的初始单纯形表和最优单纯形表分别为
表2—9（初始单纯形表）
Cj
5
4
3
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x4
1
1
1
1
0
60
0
x5
2
1
4
0
1
80

－z
5
4
3
0
0
0

表2—10（最优单纯形表）
Cj
5
4
3
0
0
b
CB
XB
x1
x2
x3
x4
x5
4
x2
0
1
-2
2
-1
40
5
x1
1
0
3
-1
1
20

－z
0
0
-4
-3
-1
-260
现在要问：
（1）c3在什么范围内变化，表中最优解不变？
（2）c3从3变为8，求新的最优解
解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。
（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表2—11中所示的新的最优解。
表2—11
Cj
5
4
8
0
0
b
CB
XB
x1
x2
x3
x4
x5
4
x2
0
1
-2
2
-1
40
5
x1
1
0
[3]
-1
1
20

－z
0
0
1
-3
-1
-260
4
x2
2/3
1
0
4/3
-1/3
160/3

5
x3
1/3
0
1
-1/3
1/3
20/3

－z
0
0
-4
-3
-1
-740/3
即新的最优解为X*=（0，160/3，20/3）T。
2.6 某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、B、C三种原材料的数量以及单位产品的利润如下表所示：
表2—12
产品
单
位
消
耗
原材料

甲
乙
资源限量（kg）
A
B
C
1
2
1
3
1
1
90
80
45
单位产品利润（千元/件）
5
4

若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（初始单纯形表）
Cj
5
4
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x3
1
3
1
0
0
90
0
x4
2
1
0
1
0
80
0
x5
1
1
0
0
1
45

－z
5
4
0
0
0
0

表2—14（最优单纯形表）
Cj
5
4
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x3
0
0
1
2
-5
25
5
x1
1
0
0
1
-1
35
4
x2
0
1
0
-1
2
10

－z
0
0
0
-1
-3
-215
解 由表2—13和表2—14可知，当B=（p3，p1，p2）时，有

当下式成立时，最优基不变。

即 25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0
解不等式有
－5≤Δb3≤5
此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb3，即

同样可得 －5≤Δb3≤5
因此，不影响最优基的b3的变化范围是[40，50]。
2.7 在例2.11的生产计划问题中：（1）若生产产品甲的工艺结构发生了改进，这时关于它的技术向量变为p1‘=（1，2，1/2）T，试分析对原最优计划有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A、B、C原材料各为2、4、1kg，每件可获利润8千元。问该厂是否应该生产该产品和生产多少？
解 （1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生改变，具体为

代入原最优单纯形表中得到
表2—15
Cj
5
4
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x3
5/4
0
1
2
-5
25
5
x1
5/4
0
0
1
-1
35
4
x2
-1/2
1
0
-1
2
10

将第1列化为单位向量，并用对偶单纯形法迭代一次得到如表2—16所示的新的最优生产计划。
表2—16
Cj
5
4
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x3
0
0
1
1
[-4]
-10
5
x1
1
0
0
4/5
-4/5
28
4
x2
0
1
0
-3/5
8/5
24

－z
0
0
0
-8/5
-12/5
——
θ
——
——
——
——
(-12/5)/-4
b
0
x5
0
0
-1/4
-1/4
1
5/2
5
x1
1
0
-1/5
3/5
0
30
4
x2
0
1
2/5
-1/5
0
20

－z
0
0
-3/5
-11/5
0
-230
即，工艺改进后新的最优生产计划为甲、乙各生产30件和20件，利润为230千元。
（2）设新产品的产量为x3‘（件），其技术系数向量为p3‘=（2，4，1）T，由表2—14可求出
σ3‘= c3’－CB B-1pj‘ = 8－（0，1，3）（2，4，1）T=1>0
即安排生产产品丙是有利的。
对应x3‘在最优单纯形表中的列向量为

代入到最优表2—14中，并用单纯形法迭代一次得新的最优表2—17。
表2—17
Cj
5
4
0
0
0
8
b
CB
XB
x1
x2
x3
x4
x5
x3‘
0
x3
0
0
1
2
-5
[5]
25
5
x1
1
0
0
1
-1
3
35
4
x2
0
1
0
-1
2
2
10

－z
0
0
0
-1
-3
1
-215
8
x3‘
0
0
1/5
2/5
-1
1
5
5
x1
1
0
-3/5
-1/5
2
0
20
4
x2
0
1
2/5
-1/5
0
0
20

－z
0
0
-1/5
-7/5
-2
0
-220
由表2—17，得最优解
X*=（20，20，5）T
即该工厂生产产品甲、乙、丙分别为20，20，5件，可使工厂获得最大利润220千元。
2.8 红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表2—18所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）

表2—18
时 间
所需售货员人数
星期日
28人
星期一
15人
星期二
24人
星期三
25人
星期四
19人
星期五
31人
星期六

28人
解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，……，x7星期日开始上班的人数。我们的目标是要求售货人员的总数最少。因为每个售货员都工作五天，休息两天，所以我们只要计算出连续工作五天的售货人数，也就计算出了售货员的总数。我们把连续工作五天的售货员按照开始工作的时间分成7类，各类的人数分别为x1，x2，…，x7，即有
目标函数： min x1+x2+x3+x4+x5+x6+x7.
我们再按照每天所需售货员的人数写出约束条件，例如星期日需要28人，我们知道商场中的全休售货员中除了星期一开始上班和星期二开始上班的人外都应该上班，即有 x3+x4+x5+x6+x7≥28，这样我们就建立了如下的数学模型：
目标函数： min x1+x2+x3+x4+x5+x6+x7
x3+x4+x5+x6+x7≥28
x4+x5+x6+x7+x1≥15
x5+x6+x7+x1+x2≥24
x6+x7+x1+x2+x3≥25
x7+x1+x2+x3+ x4≥19
x1+x2+x3+x4+x5≥31
x2+x3+x4+x5+x6≥28
x1、x2、x3、x4、x5、x6、x7≥0