线性规划习题(17)

求： （1）线性规划问题的最优解； 首先将问题标准化：

max z ? 3x1＋x2＋5 x3 ?6 x1＋3x 2＋5 x3 ? x 4 ? 45 ? ?3x1＋4 x2＋5 x3 ? x5 ? 30 ? x ，x ，x , x , x ? 0 ? 1 2 3 4 5

cj CB 0 0 0 5 XB x4 x5 x4 x3 b 45 30 15 6 3 x1 6 3 3 3 3/5 0

T

1 x2 3 4 1 -1 4/5 -3

5 x3 5 【5】 5 0 1 0

T

0 x4 1 0 0 1 0 0

0 x5 0 1 0 -1 1/5 -1

?i

9 6

最优解为 X*=(x1,x2,x3,x4,x5) =(0,0,6,15,0) ，最优目标值 z*=30 （2）求对偶问题的数学模型及其最优解；

min w ? 45 y1 ? 30 y 2 ?6 y1 ? 3 y 2 ? 3 ?3 y ? 4 y ? 1 ? 1 2 ? ?5 y1 ? 5 y 2 ? 5 ? y1 ? 0, y 2 ? 0 ?

y1*=0,y2*=1 (3) 最优解不变的情况下，求产品 A 的利润允许变化范围；

最优解不变的情况下， ?c1 ? 0, c1 ? 3 （4）假定能以 10 元的价格购进 15 单位的材料，这样做是否有利，为什么？ 有利 单位材料的影子价格是 1 元，10 元钱购进 15 单位的材料的单位价格为 2/3 元，低于影 子价格。同时，在保持最优基不变的情况下

? 30 ? b2 ? 15

购进 15 吨的原材料，最优基不变。该材料的影子价格仍为 1 元。 （5）当可利用的资源增加到 60 单位时，求最优解。

b ' ? B ?1b ?1 ? 1? ?45? ?? 15? 1 ??? ? ? ? ?? ? ?0 5 ? ?60 ? ? 12 ? ? ?

cj CB 0 5 0 5 XB x4 x3 x5 x3 b -15 12 15 9

3 x1 3 3/5 0 -3 6/5 -3

T

1 x2 -1 4/5 -3 1 3/5 -2

5 x3 0 1 0 0 1 0

T

0 x4 1 0 0 -1 1/5 -1

0 x5 【-1】 1/5 -1 1 0 0

最优解为 X*=(x1,x2,x3,x4,x5) =(0,0,9,0,15) ，最优目标值 z*=45 （6）当产品 B 的原材料消耗减少为 2 个单位时，是否影响当前的最优解，为什么？ x2 在最有表是非基变量，该产品的原材料消耗只影响 x2 的检验数。

P2' ? B ?1 P2 ?1 ? 1? ?3? ? 1 ? 1 ? ? ? ? ? ?2? ?? ?0 5 ? ? 2 ? ? 5 ? ? ? ? ?

? 2 ? c 2 ? C B B ?1 P2'

?1? ? 1 ? ?0 5?? 2 ? ? ?1 ? ? ?5? 所以最优解不变

?2 ? 0

（7）增加约束条件 2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？ 增加的约束条件，相当于增加了一个约束方程

2 x1 ? x2 ? 3x3 ? x6 ? 20

cj CB 0 5 0 0 5 0 XB x4 x3 x6 x4 x3 x6 b 15 6 20 15 6 2

2 x1 3 3/5 2 0 3 3/5 4/5 0

4 x2 -1 4/5 1 -3 -1 4/5 -7/5 -3

1 x3 0 1 3 0 0 1 0 0

0 x4 1 0 0 0 1 0 0 0

0 x5 -1 1/5 0 -1 -1 1/5 -3/5 -1