-M x6 8 1 4 2 -1 0 1 0
-M x7 6 3 2 0 0 -1 0 1
检验数j 0 -2 -3 -1 0 0 -M -M
Cj CB XB
-2 -3 -1 0 0 -M -M 比
b x1 x2 x3 x4 x5 x6 x7 值
-M x6 8 1 4 2 -1 0 1 0
-M x7 6 3 2 0 0 -1 0 1
A
1 2
2 2
3 1
4 2
p1 p2 p3 p4
序号 向量组
A
1 2
2 2
3 1
4 2
是否线性无关 是否为基
1
p1 p2
√
√
2
p1 p3
√
√
3
p1 p4
√
√
4
p2 p3
√
√
5
p2 p4
√
√
6
p3 p4
√
√
序号 1
基 p1 p2
基解
(-4, 11/2, 0 , 0)
是否为基可行解
×
2
p1 p3
(2/5, 0, 11/5 , 0) √
10/2=5
1 -3 0 -2 0
0
1
1
-1 -2
0 1/2 0 1/2 1/2 1 -3/2 0 -1/2 1/2
0 -3/2 0 -3/2 -1/2
同理： （2）为无界解
3 用单纯形法中的大M法求解下列线性规划问题，并指出属 那一类解
min Z 2x1 3x2 x3
化为标准式有
st. 3x1x1
4x2 2x2
9 8
x1, x2 0
max Z 2x1 x2
5x2 15
st.
6xx11
2
x2 x2
24 5
x1, x2 0
Cj
10 5 0 0 比
CB XB
b
x1
x2
x3
x4
值
0 x3
9
3
4
1
0 9/3=3
0 x4
8
5
20
1
8/5
检验数j 0 10 5 0 0
0 x3 21/5 0 14/5 1 -3/5 3/2
不是基，故 X (5,15, 0, 20, 0)
不是基解，更不可能是基可行解
2 1 0
1 3
0
4 7 1
X (9, 7, 0, 0, 0)
是基，故 X (9, 7, 0, 0,8) 是基解
又由于其每个分量非负，故为基可行解 为非可行域上的点，故不是
2 1 1 0 0
A 1 3
0
1
0
k=0－（3×1/2＋0×1/2）＝－3/2
综上所述：
a=3, b=2, c=4, d=-2, e=2, f=3, g=1, h=0 i=5, j=5, k=-3/2, l=0
7、设 X 0 是线性规划问题 max z CX , AX b, X 0
的最优解。若目标函数中用 C 代替 C后，问题的最
检验数j 14M 4M-2 6M-3 2M-1 -M -M 0 0
Cj
-2 -3 -1 0 0 -M -M 比
CB XB
b x1 x2 x3 x4 x5 x6 x7 值
-M x6 8 1 4 2 -1 0 1 0 2
-M x7 6 3 2 0 0 -1 0 1 3
检验数j 14M 4M-2 6M-3 2M-1 -M -M 0 0
课后练习（一）
1 用图解法求下列线性规划问题，并指出问题具有唯一
最优解、无穷多最优解、无界界还是无可行解。
min Z 2x1 3x2
4x1 6x2 6 s.t 4x1 2x2 4
x1, x2 0
无穷多最优解
max Z 3x1 2x2
2x1 x2 2
s.t.3x1 4x2 12
st.
x1 x2 x3 4 2x1 x2 x3 6
x1 0, x2 0, x3无约束
解：
max Z ' 2x1' 2x2 3(x3' x3'' ) 0x4
st.
x1' 2 x1'
x2 (x3' x3'' )
4
x2 (x3' x3'' ) x4 6
x1'
2
4
2 24
2
4
4/5
Cj CB XB -3 x2 -M x7 检验数j
-2 -3 -1 0 0 -M -M 比
b x1 x2 x3 x4 x5 x6 x7 值
2 1/4 1 1/2 -1/4 0 1/4 0 8
2 5/2 0 -1 1/2 -1 -1/2 1
2M 6 5 M 5 0 M 1 M 3 M 3 M 3 0
22
2
2
4、求解线性规划问题当某一变量的取值无约束时，通
常用 xj x'j x'j' 来替换，其中 x'j 0 ，x'j' 0。
试说明，能否在基变量中同时出现，为什么？
不可能。因为 Pj' Pj'' 故 Pj' Pj'' 0
5、 下表为用单纯形法计算时某一步的表格。已知该线
性规划的目标函数为 max Z 5x1 3x2约束形式为
10 x1 8/5 1 2/5 0 1/5
4
检验数j -80/5 0
1
0
-2
5 x2 3/2 0
10 x1 1
1
检验数j -175/10 0
1 5/14 -3/14 0 -1/7 2/7 0 -5/14 -25/14
同理： （2） X*=(3.5, 1.5, 7.5, 0, 0) Z*=8.5
2 用单纯形法求解下列线性规划问题
4x2 2x2
2x3
8 6
x1, x2 , x3 0
max Z 2x1 3x2 x3 0x4 0x5 Mx6 Mx7
st. 3x1x1
4x2 2x3 x4
x6
8
2x2
x5
x7 6
x1~7 0
Cj
-2 -3 -1 0 0 -M -M 比
CB XB
b x1 x2 x3 x4 x5 x6 x7 值
优解变为 X
求证： (C C)( X X 0 ) 0
证明：因为 CX 0 CX *故C( X * X 0 ) 0 又C* X * C* X 0 , 有C*( X * X 0 ) 0
xj 0 ( j 1, 2,3, 4)
Cj
2 -1 1 0 0 0 比
CB
XB
b
x1
x2
x3
x4
x5
x6
值
0
x4
60
3
1
1
1
0
0 60/3=20
0
x5 10
1
-1 2
0
1
0 10/1=10
0
x6 20
1
1
-1
0
0
1 20/1=20
检验数j 0
2 -1 1
0
0
0
0
x4 30
0
2
x1 10
1
0
x6 10
再有
B1
1/ 1/
2 2
0 1
那么
1/ 2 1/ 2
0 b c 1 1 3
d e
1 0
2 i
1
1
½ b=1 ½ c=2 ½ d=-1 ½ c+3=i ½ d+e=1
b=2 c=4 d=-2 i=5 e=2
又有
B1b
1/ 1/
2 2
0 1
6 1
f 4
f=3
还剩下检验数 a、j、k
m
检验数的定义为 j c j ciaij i 1
4 7 1 2 1
2 1 1
1
3
0
不是基，故
X (15,5,10, 0, 0)
4 7 1
不是基解，更不可能是基可行解
课后练习（二）
1、分别用图解法和单纯形法求解下述线性规划问题，并 指出单纯形法迭代的每一步相当于图解法可行域中的哪一 个顶点
max Z 10x1 5x2
st. 35xx11
0 1 0 0 1
1 0 1 1 2 0 0 1 0
是基
0 1 0 2 0 1 是基 1 0 0
1 1 0 1 0 0 0 0 1
是基
基解有(a), (b), (f); 基可行解有(a) (f).
5 已知某线性规划问题的约束条件为
2x1 x2 x3
25
st.4xx11
3x2 7x2
x3
x4 2x4
4
下表中所列的解均满足约束条件1-3，试指出表中哪些是可行
解，哪些是基解，哪些是基可行解。
序号
X1
X2
X3
X4
X5
A
2
4
3
0
0
B
10
0
-5
0
4
C
3
0
2
7
4
D
1
4.5
4
0
-0.5
E
0
2
5
6
2
F
0
4
5
2
0
可行解有(a), (c), (e), (f);
p1 p2 p3 p4 p5
1 0 1 0 0 A 1 2 0 1 0