1

不需要修改生产计划
2
已知线性规划问题
max Z = -5x 1 + 5x 2 +13x 3 -x 1 + x 2 + 3x 3 ≤ 20 s.t. 12x 1 + 4x 2 +10x 3 ≤ 90 x , x , x ≥ 0 1 2 3 (a) (b)
先用单纯形方法求出最优解，然后分析在下列各条件 下，最优解分别有什么变化？
３
目标函数中x3的系数由１３变为８；
从最优单纯形表中我们可以看到x3为非基变量，则只 要 c j j 最优解不会发生变化， x3仍然为非基变量。
CB
5 0
XB
X2 S2
-5 X1 -1 16 0
5 X2 1 0 0
13 X3 3 -2 -2
0 S1 1 -4 -5
0 S2 0 1 0
b
b1=45
5 b1 / 3 0 3 b1 / 5 0
60 30 b1
（３）由于技术上的突破，每单位产品B原材料的需 要减少为２单位，这时是否需要改变生产计划？为什么？
1 / 3 1 / 3 3 1 j c j CB B Pj 1 3 5 1 0 1 / 5 2 / 5 2
第四章作业答案
作业
1 某公司制造三种产品A,B,C，需要两种资源 （劳动力和原材料），要求确定总利润最大的 最优生产计划，该问题的线性规划模型如下：
max Z = 3x 1 + x 2 + 5x 3 6x1 + 3x 2 + 5x 3 ≤ 45 s.t. 3x 1 + 4x 2 + 5x 3 ≤ 30 x , x , x ≥ 0 1 2 3
1 X2 0 1 1 1 0 1
0 X3 1 0 0 0 1 -1
0 X4 0 1 0 0 0 1
0 X5 0 0 1 0 0 0 10 15 b 10 25 10
0
2 0 1
X5
X1 X4 X2
0
0 1 0 0 0
1
1 0 0 1 0
0
-2 1 -1 0 -2
0
0 0 1 0 0
1
0 0 -1 1 -1
2
0 1
X1
X4 X2
1
0 0 0 2
0
0 1 0 1 X2 0 0 1
1
-1 0 -2 0 X3 1 1 -1
0
1 0 0 0 X4 0 -1 1
0
-1 1 -1 0 X5 0 1 0
10+2λ
5-5λ 10+2λ
CB 2 0 1
XB X1 X5 X2
X1 1 0 0
b 10+2λ 5λ-5 15-3λ
0 S2 0 1 0 0 1 0 0 1 0
b 20 90 20/3 70/3
20 10
１
1
约束条件(a)的右端常数由２０变为３０；
1 0 B 4 1
20 b 10
20 b1 0 10 4b1 0
20 b1 5 / 2
1

最优解不发生变化
５、新增一个约束条件 2x1 3x2 5x3 50 ； 将最优解X1=0，X2=20，X3=0带入新增约束条件， 有新增约束条件不满足，最优解发生变化。
-5 CB XB 5 0 0 X2 S2 S3
5
13 X3 3 -2 5 -2
0
0
0 S3 0 0 1 b 20 10 50
0
0
-3
1
0
1<λ<5,(10+2 λ,15-3λ,0,0,5λ-5)
2
CB 2 0 1 XB X1 X5 X2 X1 1 0 0 0 2 CB 2 0 0 XB X1 X5 X3 X1 1 0 0
2 2 0 5- λ
-3/2 1 9/2-7 λ/2
0 -3 1 -3-2λ
0 0 0
1 0 0 0
½ 0 -5/2+ λ/2
0 1 0 0
3 4
0 0 3+2λ
X4 X5 X1
0 0 1 0
12 6 4
λ>5，最优解为（4,0,0,12,6）
4
０ 25 参数时 试分析下列参数线性规划问题，当 最优解的变化。
20 10
由上表可知，σ3=-2，Δ c3=-5≤- σ3,故最优解不发生 变化。
４、X1的系数列向量由 1 变为 0
12
5
1 0 0 j c j CB B Pj 5 5 0 5 0 4 1 5
不需要改变生产计划
（４）假如这时，又试制成新产品D，生产一个单位新 产品D需要劳动力４单位，原材料３单位，而每单位的新 产品D的利润为1元，请问这时生产计划是否要进行修改？ 为什么？
1 / 3 1 / 3 4 j c j CB B Pj 1 3 5 2 0 1 / 5 2 / 5 3
10
10 5 10
1 0 0 2 2 5 B 1b 1 1 1 0 0 1 2 2
10 2 10 2 5 5 5 B 1b 5 10 2 10 2
X1 X2 -1 1
S1 S2 1 -4 0 -5 0 1 0 0
16 0 2 0 3 0
-5 CB XB X1 5 X2 -1 0 S2 16 0 S3 2 0 5 X2 -1 0 S2 16 0 S3 5 0 5 X2 11/4 0 S2 27/2 13 X3 -5/4
5 X2 1 0 3 0 1 0 0 0 1 0 0
-5 CB XB X1 5 X2 11/4 0 S2 27/2 13 X3 -5/4 -3/2
5 X2 1 0 0 0
13 X3 0 0 1 0
0 S1 -5/4 -5/2 3/4 -7/2
0 S2 0 1 0 0
S3 3/4 -1/2 -1/4 -1/2
b 25/2 15 5/2
最优解为X1=0，X2=12.5，X3=2.5，S1=0，S2=15，S3=0
max Z = 2x 1 + x 2 x 1 ≤ 10 + 2λ x 1 + x 2 ≤ 25 - λ s.t. x 2 ≤ 10 + 2λ x , x ≥ 0 1 2
X = (10,10,0,5,0)T
2 CB 0 0 0 XB X3 X4 X5 X1 1 1 0 2 2 0 X1 X4 1 0
C1 ≤12 C1 ≥3 C1 ≤6 3 ≤ C1 ≤6
C1=2最优解发生变化
（１）求出使得最优解不变的产品A的单位利润变动 范围。问 c 2 时最优解是否会发生变化。
1
2
0
2
-10/3
1/3
-4/3
（１）求出使得最优解不变的产品A的单位利润变动 范围。问 c 2 时最优解是否会发生变化。
1
2
0
0
s1
3 3/5
-1
-1 4/5
-3
1 1 0
0
-1 1/5
-1
15 6
最优解为：[0,0,6,15,0]
最优值为30
（２）求出使得最优解不发生变化的劳动力资源 b1 变 动范围。
1 1 3 1 3 B 1 2 5 5
5 b 3
CB 5 0 5 13
XB X2 S2 X2 X3
-5 X1 -1 16 0 23 -8 -16
5 X2 1 0 0 1 0 0
13 X3 3 -2 -2 0 1 0
0 S1 1 -4 -5 -5 2 -1
0 S2 0 1 0 3/2 -1/2 -1
b 20 -10 5 5
最优解为[0,5,5,0,0]
3
试分析下列参数线性规划问题，当 0 参数时 最优解的变化。
max Z = (3 + 2λ)x 1 + (5 - λ)x 2 x1 ≤ 4 2x 2 ≤ 12 s.t. 3x 1 + 2x 2 ≤ 18 x , x ≥ 0 1 2
X (2,6,2,0,0)T
3 CB 0 0 0 XB X3 X4 X5 X1 1 0 3 3 0 5 X3 X2 1 0
5 X2 1 0 0 1 0 0 -1/5 2/5 0
13 X3 3 -2 -2 0 1 0 0 1 1/2
0 S1 1 -4 -5 -5 2 -1 1 0 0
0 S2 0 1 0 3/2 -1/2 -1 3/10 -11/10 -5/4
b 30 -30 -15 15
3 9
最优解为[0,0,9,3,0]
1
0 -1/3 0 1/3 -1
6
2 6 2
3+2λ CB 0 XB X3 X1 0
5- λ X2 0
0 X3 1
0 X4 1/3
0 X5 -1/3 b 2
5- λ 3+2λ
X2 X1
0 1 0
1 0 0
0 0 0
1/2 -1/3 -3/2+7 λ /6
0 1/3 -1-2 λ/3
6 2
0≤λ ≤9/7，最优解为（2,6,2,0,0）
5 X2 0 2 2 5 0 1
0 X3 1 0 0 0 1 0
0 X4 0 1 0 0 0 1/2
0 X5 0 0 1 0 0 0 4 6 b 4 12 18
0
0 5 3