ax z = x1 + x2 3x1 + x2 ≥ 2
s.t.x1 + 2x2 ≤ 5 x1, x2 ≥ 0
解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在 A 点取得最优值， 最优值 z=5
（2） min z = x1 − 6x2 2x1 + x2 ≤ 1
s.t.− x1 + x2 ≤ 7 x1, x2 ≥ 0
解：图中阴影部分表示可行域，由图可知原问题在点 A 处取得最优值，最优值 z=-6.
（3） max z = 3x1 + 2x2
− x1 + x2 ≤ 1 s.t.x1 − 2x2 ≥ −4
x1, x2 ≥ 0
解：如图 所示，可行域为图 中阴影部 分，易得 原线性规 划问题 为无界 解。
所以 x(2) , x(4) , x(6) 是原问题的基可行解， x(6) 是最优解，最优值是 z = −3 。
（2） max z = x1 + x2 − 2x3 + x 4 − x5
x1 + x2 + x3 + x4 = 1 s.t.− x1 + 2x2 + x5 = 4
xi ≥ 0,i = 1,2,3,4,5
解：易知
x1
的系数列向
量
p1
= 1− 1
，
x2
的系数列向
量
p2
=
1
2
，
x3
的系
数列向量
1
1
0
p3
=
0
，
x4
的系数列向量
p4
=
0
，
x5
的系数列向量
p5
=
1
。
x1 + x 2 = 1− x3 − x 4
①因为 p1, p2 线性无关，故有
，令非基变量为 x3 = x 4 = x5 = 0 ，得
− x1 + 2x2 = 4 − x5
x1 x 2
=−2 3
=5 3
，所以得到一个基解
x (1)
=
(−
2,5 33
,0,0,0) ，是非基可行解；
②因为 p1, p3 线性无关，可得基解 x (2) = (−4,0,5,0,0) ，是非基可行解；
③因为 p1, p4 线性无关，可得基解 x (3) = (−4,0,0,5,0) ，是非基可行解；
(
2 5
,0,
11 5
,0)
，
z
2
=
43 ； 5
③因为 p1, p4
线性无关，可得基解 x (3)
=
(−
1 ,0,0, 11) 36
，是非基可行解；
④因为 p2 , p3 线性无关，可得基解 x (4) = (0,2,1,0) ， z4 = −1；
⑤因为 p2 , p4 线性相关， x2 , x4 不能构成基变量； ⑥因为 p3, p4 线性无关，可得基解 x (6) = (0,0,1,1) ， z6 = −3 ；
（4） min z = 2x1 − 5x2 x1 + 2x2 ≥ 6
s.t.x1 + x2 ≤ 2 x1, x2 ≥ 0
解：由图可知该线性规划可行域为空，则原问题无可行解。
1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。
（1） min z = 5x1 − 2x2 + 3x3 − 6x4
所以原线性规划的基可行解是 x(4) , x(7) , x(9) , x(10) ，最优解是 x(7) ，最优值是 z = −1。
1.3 用单纯形法求解下列线性规划问题；
（1） max z = 2x1 + 3x2
x1 + 3x2 ≤ 5 s.t.x1 + x2 ≥ 2
x1, x2 ≥ 0
解：引入松弛变量 x3 ，剩余变量 x 4 和人工变量 x5 ，把原问题化为规范式
x1 + 2x2 + 3x3 + 4x4 = 7 s.t.2x1 + x2 + x3 + 2x4 = 3
x1, x 2 , x3, x 4 ≥ 0
解：易知
x1 的系数列向量 p1
=
1
2
，x
2
的系数列向量
p2
=
12，x 3
的系数列向量
p3
=
13，
x4
的系数列向量 p4
=
4 2
。
①因为
p1, p2
线性无关，故有
x1
+ 2x2
=
7 − 3x3
− 4x4
，令非基变量为
x3
=
x4
=
0 ，得
2x1 + x2 = 3 − x3 − 2x4
x1 x 2
= =
−1 3
11 3
，所以得到一个基解
x (1)
=
(−
1 ,11 33
,0,0)
是非基可行解；
②因为 p1, p3 线性无关，可得基解 x (2)
=
x1
x2
x3
x4
x5
1+ 2 M 3
x2
1
3
x5
2
3
0
-1- M
3
1
1
3
0
−1
3
-M
0
0
0
-1
1
以 x1 为换入基， x5 作为换出基有
x1
x2
x3
x4
x5
0
x2
0
x1
1
0
−1
2
1
1
2
0
−1
2
3
− 3 −M 2
2
1
−1
2
2
−3 3 22
5 3 1 3
-5.5
1.5 0.5
以 x 4 换入， x2 换出有
max z = 2x1 + 3x2 − Mx5
x1 + 3x 2 + x3 = 5 s.t.x1 + x2 − x4 + x5 = 2 ，其中 M 无限大，
xi ≥ 0,i = 1,2...5
构造初始单纯形表并计算如下：
x1
x2
x3
x4
x5
2+M
3+M
0
-M
0
x3
1
3
1
0
0
5
x5
1
1
0
-1
1
2
以 x 2 作为换入基， x3 作为换成基，计算得
⑦因为 p2 , p5 线性无关，可得基解 x (7) = (0,1,0,0,2) ， z7 = −1；
⑧因为 p3, p4 线性相关， x3, x 4 不能构成基变量；
⑨因为 p3, p5 线性无关，可得基解 x (9) = (0,0,1,0,4) ， z9 = −6 ；
⑩因为 p4 , p5 线性无关，可得基解 x (10) = (0,0,0,1,4) ， z10 = −3 ；
④因为 p1, p5 线性无关，可得基解 x (4) = (1,0,0,0,5) ， z4 = −4 ；
⑤因为 p2 , p3 线性相关，得基解 x (5) = (0,2,−1.0,0) ，是非基可行解；
⑥因为 p2 , p4 线性无关，可得基解 x (6) = (0,2,0,−1,0) ，是非基可行解；
x1
0
x4
0
x1
1
x2
x3
-3
-2
2
1
3
1
x4
x5
0
−3−M
-10
1
-1
3
0
0
5
根据单纯形表可知，原问题的最优解为 x* = (5,0,0,3) ，最优值为 z* = 10
（2） max z = x1 + x2 − 2x3
3x1 + x 2 − x3 ≤ 5 s.t.x1 − 4x2 + x3 ≥ 7