优解变为 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
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
3
p1 p4
(-1/3, 0, 0, 11/6)
×
4
p2 p3
(0, 1/2, 2, 0)
√
5
p2 p4
(0, -1/2, 0, 2)
×
6
p3 p4
(0, 0, 1, 1) √
4、已知线性规划问题 :
max Z x1 3x2
x1
x3
5
1
st.
x1
2x2 x2
x4
10 2
x5 4
3
x1 ... x5 0
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
F04ຫໍສະໝຸດ 520可行解有(a), (c), (e), (f);
p1 p2 p3 p4 p5
1 0 1 0 0 A 1 2 0 1 0
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 用单纯形法求解下列线性规划问题
0
检验数j -20 0
4
-5
-1 2
2
-3
1 -3
1
-3
0
1
0
-1
0 -2
0 30/4=7.5
0
-
1
10/2=5
0
0
x4 30
0
2
x1 10
1
0
x6 10
0
检验数j -20 0
0
x4 10
0
2
x1 15
1
-1
x2
5
0
检验数j -25 0
4
-5
1
-3
0 30/4=7.5
-1 2
0
1
0
-
2
-3
0
-1
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) √
项目 X1 X2 X3 X4
X5
X4 6 (b) (c) (d) 1 0
X5 1 -1
3 (e) 0 1
Cj-ZJ
(a) -1 2
00
X1 (f) (g) 2 -1 1/2 0
X5 4 (h) (i) 1 1/2 1
Cj-ZJ
0
-7 (j) (k) (l)
首先由于x1、x5为基变量，故g=1, h=0, l = 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
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约束形式为
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
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'
如何求得c呢？
m
j c j ciaij i 1
对初始单纯形表的检验数行即为目标函数中的系数C。
c1 a, c2 1, c3 2, c4 c5 0
对迭代后的单纯形表有： 2 7 c2 (2*c1 0*i) a=c1=3
至此我们已获得所有的目标函数的系数 j=2－（3×－1＋0×1）＝5
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
m
由检验数的定义可知： j c j ciaij i 1 －1＝3 －（0×0 ＋e×5）
e=4/5
g=0－（0×1/5＋1×5）
g=－5
综上所述： a=2, b=0, c=0, d=1, e=4/5, f=0, g=-5
由于所有检验非正，故该解是最优解 这个表格为最终单纯形表
6、已知某线性规划问题的初始单纯形表和用单纯刑法迭代 后得到的表如下所示，试求括弧中未知数a~l的值
不是基，故 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后，问题的最
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
x3、x4为松弛变量，表中解代入目标函数后得Z=10