第6章 对偶原理及灵敏度分析

习 题 6

6.1 试建立下述LP问题的对偶关系表，并写出其对偶问题： （1）max z=4x1+3x2+6x3

?3x1?x2?x3?60??2x1?2x2?3x3?40s.t. ?

2x?2x?x?623?1?x?0,x?0,x?023?1（2）min w=60x1+10x2+20x3

?3x1?x2?x3?2??x1?x2?x3??1s.t. ?

x?2x?x?123?1?x?0,x?0,x?023?1（3）min w=5x1-3x2

?2x1?x2?4x3?2??x1?x2?2x3?1s.t. ?

3x?x?x?323?1?x?0,x?0,x?023?1（4）max z=4x1+3x2+6x3

?x1?2x2?4x3?10?s.t. ?2x1?5x2?3x3?15

?x?0,x?0,x?023?1（5）min w=2x1+2x2+4x3

?2x1?3x2?5x3?2??3x1?x2?7x3?3s.t. ?

x?4x?6x?523?1?x?0,x?03?2(6) min w=2x1+3x2+6x3+x4

?3x1?4x2?4x3?7x4?21??2x1?7x2?3x3?8x4?18s.t. ?

x?2x?5x?3x?4234?1?x?0,x?0,x?0?124

6.2 已知LP问题： min z= 5x1+6x2+3x3

?5x1?5x2?3x3?50?x?x2?x3?20?1?7x1?6x2?9x3?30??x1?x2?x3?7s.t. ?

2x?4x?15x?1023?1?6x?5x?4512??x2?10x3?20?x?0,x?0,x?023?1试通过求解其对偶问题来确定该LP问题的最优解。 6.3 已知LP问题： max z= x1+2x2

?x1?x2?2?s.t.??x1?x2?1 ?x?0,x?02?1（1）试证明它与其对偶问题均无可行解。

（2）试构造一个LP问题，使其本身及其对偶问题均无可行解。 6.4 不用单纯形法，利用对偶性质和其它简便方法求解下述LP问题： (1) max w=4x1+3x2+6x3

?3x1?x2?3x3?30?s.t. ?2x1?2x2?3x3?40

?x?0,x?0,x?023?1(2) max z=x1-x2+x3

?x3?4?x1? ?x1?x2?2x3?3?x?0,x?0,x?023?1

6.5 已知LP问题：max z= 6x1+8x2

?5x1?2x2?20?s.t.?x1?2x2?10 ?x?0,x?02?1(1)写出它的对偶问题。 (3)用单纯形法求解原始问题。 (5)用对偶单纯形法求解对偶问题。 (6)该问题是否满足互补松弛性？为什么？

6.6用对偶单纯形法求解下述LP问题: (1)min z= x1+x2

?x1?2x2?4??5?x1s.t. ?

?3x1?x2?6?x?0,x?0?12(2) min z= 3x1+2x2+x3

?x1?x2?x3?6??x3?4?x1s.t. ?

x2?x3?3??x?0,x?0,x?023?1

6.7 某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示：

产品 单耗（台时/件） 设备有效台时 设备 甲 乙 丙 A B 产值（千元/件） 1 2 1 2 1 2 3 2 1 400 500 （1） （2）

如何充分发挥设备能力，使产品总产值最大？

若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？

6.8 试就6.7题解答下列问题：

（1）试分别确定甲产品单位产值、B设备供量各自的影响范围。

（2）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？

（3）若每月A设备提供量减少200台时，B设备供量增加100台时，试问最优解与影子价格有何变化？

6.9 已知LP问题 max z=5x1+2x2+3x3

?x1?5x2?2x3?b1?s.t. ?x1?5x2?6x3?b2

?x?0,x?0,x?023?1对于给定的常数b1和b2，其最优单纯形表是：

cj 基 解 5 2 3 0 0 x1 x2 x3 x4 x5 5 0 x1 x5 30 10 150 1 λ0 λ1 2 2 1 0 -8 -1 1 检验行 0 λ3 7 λ4 λ5 5是常数。试求：

其中λ1，λ2，λ3，λ4，λ（1）b1和b2的值。 （2）对偶问题的最优解。

（3）λ1，λ2，λ3的值。

（4）参数c1, c2, c3的影响范围。 （5）参数b1，b2的影响范围。 （6）参数a12,a13,a23的影响范围。 （7）参数a11,a21的影响范围。 6.10 已知LP问题 max z=-5x1+5x2+13x3

?x1?x2?3x3?20?s.t. ?12x1?4x2?10x3?90

?x?0,x?0,x?023?1试用单纯形法求出最优解，然后分别对下述情况进行灵敏度分析： （1）分别确定参数c1,b1,a22的影响范围。 （2）参数b1从20变为30。 （3）参数b2从90变为70。 （4）参数c3从13变为8。

?c1???2?????（5）x1的系数变为a11?0

??????5???a21????c2??6?????（6）x2的系数变为a12?2

??????5???a22???（7）增加一个约束条件2x1+3x2+5x3≤50 （8）把约束条件2变为10x1+5x2+10x3≤100

6.11 已知LP问题 max z=2x1+7x2-3x3

?x1?3x2?4x3?30?s.t. ?x1?4x2?x3?10

?x?0,x?0,x?023?1给它引进松弛变量x4,x5后，用单纯形法求得其最优方程组如下：

x2?x3?2x5?20?z??x2?5x3?x4?x5?20 ???x?4x?x?x5?1023?1试对下述情况分别进行灵敏度分析： （1）

b1减少20，同时b2增加10.