st.
x1' 2x1'
x2 (x3' x3'' )
4
x2 (x3' x3'' ) x4 6
x1' 0 x2 0 x3' ,x3'' 0 x4 0
3 对下述线性规划问题找出所有基解，指出那些是基可行 解，并确定最优值。
min
Z
5 x1
2x 2
3x 3
2x 4
x 2x 3x 4x 7
s.t
.
X(9,7,0,0,0)
为非可行域上的点，故不是
2 1 1 0 0
A 1
3
0
1
0
4 7 1 2 1
2 1 1
1
3
0
不是基，故
X(15,5,10,0,0)
4 7 1
不是基解，更不可能是基可行解
课后练习（二）
1、分别用图解法和单纯形法求解下述线性规划问题，并 指出单纯形法迭代的每一步相当于图解法可行域中的哪一 个顶点
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
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
2x3
8 6
x1, x2 , x3 0
maxZ2x13x2x30x40x5Mx6Mx7
st.3x1x1
4x2 2x3 x4
x6
2x2
x5
x7
x1~70
8 6
Cj
-2 -3 -1 0 0 -M -M 比
5x1
st.
3x1 4x1
6x2 3x2 2x2
4x3 4x4 20 2x3 8x4 25 x3 3x4 10
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
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
X(9,7,0,0,8) X(15,5,10,0,0)
2 1 1 0 0
A 1
3
0
1
0
4 7 1 2 1
2 1 0
1
3
1
4 7 2
不是基，故 X(5,15,0,20,0)
不是基解，更不可能是基可行解
2 1 0
1
3
0
是基，故 X(9,7,0,0,8) 是基解
4 7 1
又由于其每个分量非负，故为基可行解
解答-运筹学-第一章-线性规划 及其单纯形法习题
2、将下述线性规划问题化成标准形式
min Z 2 x1 2 x2 3x3
st.
x1 x2 x3 4 2 x1 x2 x3 6
x1 0, x2 0, x3无约束
解：
maxZ' 2x1' 2x2 3(x3' x3'' )0x4
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
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
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
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
√
√
5
p2 p4
√√6来自p3 p4√√
序号 1
基 p1 p2
基解
(-4, 11/2, 0 , 0)
是否为基可行解
×
2
p1 p3
(2/5, 0, 11/5 , 0) √
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)
×
同理： （2） X*=(3.5, 1.5, 7.5, 0, 0) Z*=8.5
2 用单纯形法求解下列线性规划问题
max Z 2x1 x2 x3
3x1
st.
x1 x1
x2
x3 60
x2
2x3 10
x2
x3 20
x j 0 ( j 1, 2,3)
maxZ 6x1 2x2 10x3 8x4
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
m ax Z 10 x1 5 x2
s
t
.
3 5
x x
1 1
4 2
x2 x2
9 8
x 1 , x 2 0
m ax Z 2 x1 x2
5 x2 15
s
t
.
6
x1 x1
2 x2 x2
24 5
x 1 , x 2 0
Cj
10 5 0 0 比
CB XB
b
x1
x2
x3
x4
值
0 x3
1
2x 1
2
2x 2
3
x 3
4
2x 4
3
x 0( j 1,...., 4) j
关键：判断2个列向量线性相关性，若线性无关，则成为基
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
1
0
0
0 0 1
是基
基解有(a), (b), (f); 基可行解有(a) (f).
5 已知某线性规划问题的约束条件为
2x1 x2 x3
25
st.4xx11
3x2 7x2
x3
x4 2x4
x5
30 85
x1 x2 x3 x4 x5 0
判断下列各点是否为该线性规划问题可行域上的顶点：
X(5,15,0,20,0)