-1 x3 -1 1 2-M
0 x4 -1 0 -M
0 x5 -2 1 3-2M
-M x6 1 0 0
i
4/5 -
【5 】
-2 -8+5M
j
cj CB -2 -3 XB x1 x2 b 4/5 18/5
-2 x1 1 0 0
-3 x2 0 1 0
-1 x3 -1/5 3/5 【 】 2/5
0 x4 -1/5 -2/5 -8/5
-2 b 8 2 x1 1 -2 -2+M -3 x2 2 -1 x3 1 1 -1+M 0 x4 -1 0 -M 0 x5 0 1 0 -M x6 1 0 0
cj CB -M 0 XB x6 x5
i
4 2
【1 】
-3+2M
j
cj CB -M -3 XB x6 x2 b 4 2
-2 x1
-3 x2 0 1 0
i
-3 4/3 【-2】 1/2
j
cj CB -1 1 XB x3 x1
用 原 最 对 优 偶 单 纯 法 形 表
i
j
新 最 优 单 纯 形 表
最优解变为x*=(6,0,1)T,最优值变为z*=5
cj CB 0 1 XB x4 x1 b 2 6
1 x1 0 1 0
-2 x2 -3 2 -4
x1 2 x2 x3 8 2 x1 x2 x3 2 x 0, j 1,2,3 j
对偶问题: min w 8 y1 2 y2
y1 2 y2 2 2 y y 3 1 2 y1 y2 1 y j 0, j 1,2
2 y1 y2 1 y 2 y 2 1 2 1 2 y1 y j 0, j 1,2
根据对偶理论，对偶规划的最优解为 Y*=( 0,1)。
3(1).当b1由14变为10时，最优解有何变化？
1 2 10 2 XB B b 0 1 6 6
1 x1 2
-2 x2 1 2 -2 -2 x2 -3 2 -4
-1 x3 -2 0 -1 -1 x3 -2 0 -1
0 x4 1 0 0 0 x4 1 0 0
0 x5 0 1 -2 0 x5 -2 1 -1
i
7 6
【 1】
1 1
j
cj CB 0 1 XB x4 x1 b 2 6
i
最 优 单 纯 形 表
2 2 0 (3) 2 2 6 0
3 1 0 (2) 2 0 1 0
5 0 0 (2) 2 1 2 0
所以最优解不变。
1 2 (4)当p2由 变为 时，最优解有何变化？ 2
1
2 3 (2) (1) (1) 2 3 0
1
6 b2 1
cj CB 0 XB x4 x1 b 2 6
21
x1 0 1 0
-2 x2 -3 2 -4 -6
-1 x3 -2 0 -1 -1
0 x4 1 0 0
0 x5 -2 1 -1 -2
i
21
j
仍 原 是 最 最 优 优 单 单 纯 纯 形 形 表 表
(3)当c1由1变为2时，最优解有何变化？
大M规划： max z 2 x1 3x2 x3 Mx6
x1 2 x2 x3 x4 x6 8 x5 2 2 x1 x2 x3 x 0, j 1,,6 j
大M规划：
max z 2 x1 3x2 x3 Mx6 x1 2 x2 x3 x4 x6 8 x5 2 2 x1 x2 x3 x 0, j 1,,6 j
(3)当p2由 变为
2 1
1 4
时，最优解有何变化？
1.标准形：
max z 2 x1 3x2 x3 x1 2 x2 x3 x4 8 x5 2 2 x1 x2 x3 x 0, j 1,,6 j
（Operations Research）
运
筹
学
复习题答案
一. 用图解法求解下列线性规划问题。并说明是唯一最优 解，无穷多最优解，无界解还是无可行解。 1.
max z x1 3 x2 s.t. x1 2 x2 10 x1 x2 1 x2 4 x j 0, j 1,2
2 3
时，最优解有何变化？
1.标准形：
max z x1 2 x2 x3 2 x1 x2 2 x3 x4 14 x5 6 x1 2 x2 x 0, j 1,,5 j
cj CB 0 0 XB x4 x5 b 14 6
x1 1 0 0
-3 x2 1/3 5/3 2 c -2/3 1 3
-1 x3 0 1 0
0 x4 -1/3 -2/3
c1 4 -4/3 3
0 x5 -1/3
-M x6 1/3
i
j
1/3 2/3 c1 1 4 3M c1 -1/3 -M+4/3 3 3
原 最 优 单 纯 形 表
2 c1 1
6 M (2 c1 ) (1)
4 3M c1 0 3
cj CB -2 -1 XB x1 x3 b 2 6
-2 x1 1 0 0
-3 x2 1/3 -1 5/3 2 -2/3
-1 x3 0 1 0
0 x4 -1/3 -2/3 -4/3
-1 x3 -2 0 -1
0 x4 1 0 0
0 x5 -2 1 -1
i
j
原 最 优 单 纯 形 表
(2)最优基不变的情况下，△b2的变化范围？
1 2 14 2 2b2 0 XB B b 0 1 0 6 b 6 b 2 2
1 0 0
-1 x3 -2 0 -1
0 x4 1 0 0
0 x5 -2 1 -1
i
1/2 -
j
-2 1 x2 x1 1/2 15/2
用 原 最 单 优 纯 单 形 法 纯 形 表
0 1 0
-1/2 -3/2 -1/2
1/4 3/4 -1/4
-1/2 -1/2 -1/2
j
最优解变为x*=(15/2,1/2,0)T,最优值变为z*=13/2.
-3 x2 1/3 5/3 -2/3
-1 x3 0 1 0
0 x4 -1/3 -2/3 -4/3
0 x5
-M x6 1/3 2/3 -M+4/3
i
4
【-1/3 】 1
1/3 -1/3
j
cj CB 0 -1 XB x5 x3 b 3 8
用 原 最 对 优 偶 单 纯 法 形 表 新 最 优 单 纯 形 表
一. 用图解法求解下列线性规划问题。并说明是唯一最优 解，无穷多最优解，无界解还是无可行解。
2.
max z x1 x2 s.t. 2 x1 x2 4 x1 x2 2 x j 0, j 1,2
二.已知线性规划问题:
max z x1 2 x2 x3 2 x1 x2 2 x3 14 6 x1 2 x2 x 0, j 1,2,3 j
1 2 2 4 B p2 0 1 3 3 2 2 0 4 1 (3) 1
1
3
cj CB 0 1 XB x4 x1 b 2 6
1 x1 0 1 0
-2 x2 -3 【 4】 2 -3 -4 1
0 x5 -1/3 1/3 -1/3
-M x6 1/3 2/3 -M+4/3
i
j
-3
2 1 (3)当p2由 变为 时，最优解有何变化？ 1 4
仍 原 最 是 优 最 单 优 纯 单 形 纯 表 形 表
1 / 3 1 / 3 1 1 B p2 2 / 3 1/ 3 4 2
-2 x1 -3 1 -1
-3 x2 -1 2 -1
-1 x3 0 1 0
0 x4 1 -1 -1
0 x5 1 0 0
-M x6 -1 1 -M+1
i
j
最优解变为x*=(0,0,8)T,最优值变为z*=-8。
cj CB -2 -2+ △ c1 -1 XB x1 x3 b 2 6
-2+-2 △c 1
x1 0 1 0
j
最优解x*=(6,0,0)T,最优值z*=6×1=6
2. 原问题: max z x1 2 x2 x3
2 x1 x2 2 x3 14 6 x1 2 x2 x 0, j 1,2,3 j
对偶问题: min w 14 y1 6 y2
ij最 优 单 源自 形 表最优解x*=(2,0,6)T,最优值z*=-10.
2. 原问题:
max z 2 x1 3 x2 x3 x1 2 x2 x3 8 2 x1 x2 x3 2 x 0, j 1,2,3 j
原问题变形为： max z 2 x1 3 x2 x3
三.已知线性规划问题:
max z 2 x1 3 x2 x3 x1 2 x2 x3 8 2 x1 x2 x3 2 x 0, j 1,2,3 j
1.用大M法求解；
2.写出其对偶规划；