运筹学 - 第2章 - 对偶理论习题

第二章 线性规划的对偶理论

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 CB 0 0 θ -2 0 θ x2 x5 －z XB x4 x5 －z －4 x1 -2 -4 -4 -4/-2 1/2 -7/2 -3 -3/(-7/2) －2 x2 [-4] -1 -2 -2/-4 1 0 0 0 －6 x3 -8 -4 -6 -6/-10 2 [-2] -2 -2/-2 0 x4 1 0 0 0 -1/4 -1/4 -1/2 (-1/2)/(-1/4) 0 x5 0 1 0 0 0 1 0 0 b -24 -8 0 6 -2 -120 -2 -6 x2 x3 －z -3 7/4 -1/2 1 0 0 0 1 0 -1/2 1/8 -1/4 1 -1/2 -1 4 4 -32 最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为 X*=（0，4，4）T 最优值为z*=32

2.5 设某线性规划问题的初始单纯形表和最优单纯形表分别为 表2—9（初始单纯形表） Cj CB 0 0 XB x4 x5 －z 5 x1 1 2 5 4 x2 1 1 4 3 x3 1 4 3 0 x4 1 0 0 0 x5 0 1 0 b 60 80 0

表2—10（最优单纯形表） Cj CB 4 5 XB x2 x1 －z 5 x1 0 1 0 4 x2 1 0 0 3 x3 -2 3 -4 0 x4 2 -1 -3 0 x5 -1 1 -1 b 40 20 -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 CB 4 5 4 5 XB x2 x1 －z x2 x3 5 x1 0 1 0 2/3 1/3 4 x2 1 0 0 1 0 8 x3 -2 [3] 1 0 1 0 x4 2 -1 -3 4/3 -1/3 0 x5 -1 1 -1 -1/3 1/3 b 40 20 -260 160/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 单 位 原材料 消 耗 产品 甲 1 2 1 5 乙 3 1 1 4 资源限量（kg） 90 80 45 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（初始单纯形表） Cj CB 0 0 0 XB x3 x4 x5 －z 5 x1 1 2 1 5 4 x2 3 1 1 4 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 0 0 1 0 b 90 80 45 0

表2—14（最优单纯形表） Cj CB 0 5 4 XB x3 x1 x2 －z 5 x1 0 1 0 0 4 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 2 1 -1 -1 0 x5 -5 -1 2 -3 b 25 35 10 -215 解 由表2—13和表2—14可知，当B=（p3，p1，p2）时，有

?1B?1???0?0?21?1?5???1? 2??

?25??1Bb??35?10??? ???当下式成立时，最优基不变。

?25??1?1Bb?B?b??35?10???1?????0??0??21?1?5??0???1??0?2????b3??25?5?b3?????35??b3??10??b3??????0??

即 25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0 解不等式有

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

25??10??35max??,????b?min???

?5??2???1同样可得 －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列将会发生改变，具体为

?1??1'Bp1??0?0?21?1?5??1??1/2???????1??1???1/2?????2???1/2??0?

代入原最优单纯形表中得到

表2—15 Cj CB 0 5 XB x3 x1 5 x1 5/4 5/4 4 x2 0 0 0 x3 1 0 0 x4 2 1 0 x5 -5 -1 b 25 35

本文来源：https://www.bwwdw.com/article/h37h.html