③因为 p1 , p 4 线性无关，可得基解 x ④因为 p1 , p 5 线性无关，可得基解 x ⑤因为 p 2 , p 3 线性相关，得基解 x
(5)
( 3)
( 4)
(0,2,1.0,0) ，是非基可行解；
( 6)
⑥因为 p 2 , p 4 线性无关，可得基解 x ⑦因为 p 2 , p 5 线性无关，可得基解 x
（1） min z 5x1 2 x 2 3x 3 6 x 4
x1 2 x 2 3x 3 4 x 4 7 s.t.2x1 x 2 x 3 2x 4 3 x1 , x 2 , x 3 , x 4 0
1 2 3 解： 易知 x1 的系数列向量 p1 ， x 的系数列向量 p 2 ， x 的系数列向量 p 3 ， 2 2 1 3 1 4 x 4 的系数列向量 p 4 。 2
(0,2,0,1,0) ，是非基可行解； (0,1,0,0,2) ， z 7 1 ；
(7)
⑧因为 p 3 , p 4 线性相关， x 3 , x 4 不能构成基变量； ⑨因为 p 3 , p 5 线性无关，可得基解 x
(9)
(0,0,1,0,4) ， z 9 6 ； (0,0,0,1,4) ， z10 3 ；
解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。
（4） min z 2 x1 5x 2
x1 2 x 2 6 s.t.x1 x 2 2 x1 , x 2 0
解：由图可知该线性规划可行域为空，则原问题无可行解。
1.2
对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。
（2） max z x1 x 2 2 x 3 x 4 x 5
x1 x 2 x 3 x 4 1 s.t. x1 2 x 2 x 5 4 x i 0, i 1,2,3,4,5
解：易知 x1 的系数列向量 p1
1 1 ， x 的系数列向量 p ， x 的系数列向量 2 3 2 1 2
x1 3x 2 5 s.t.x1 x 2 2 x1 , x 2 0
解：引入松弛变量 x 3 ，剩余变量 x 4 和人工变量 x 5 ，把原问题化为规范式
②因为 p1 , p 3 线性无关，可得基解 x
43 2 11 ( ,0, ,0) ， z 2 ； 5 5 5 11 1 ( 3) ③因为 p1 , p 4 线性无关，可得基解 x ( ,0,0, ) ，是非基可行解； 6 3
( 2) ( 4)
④因为 p 2 , p 3 线性无关，可得基解 x
习题一 1.1 利用图解法求下列线性规划问题： （1） max z x1 x 2
3x1 x 2 2 s.t.x1 2 x 2 5 x1 , x 2 0
解：根据条件，可行域为下面图形中的阴影部分， ，有图形可知，原问题在 A 点取得最优值， 最优值 z=5
1 1 0 p 3 ， x 4 的系数列向量 p 4 ， x 5 的系数列向量 p 5 。 0 0 1
①因为 p1 , p 2 线性无关，故有
x x2 1 x3 x4 1 x 1 2 x 2 4 x 5
(0,2,1,0) ， z 4 1 ；
⑤因为 p 2 , p 4 线性相关， x 2 , x 4 不能构成基变量； ⑥因为 p 3 , p 4 线性无关，可得基解 x 所以 x
( 2) (6)
(0,0,1,1) ， z 6 3 ；
, x ( 4 ) , x ( 6 ) 是原问题的基可行解， x ( 6) 是最优解，最优值是 z 3 。
（2） min z x1 6 x 2
2 x 1 x 2 1 s.t. x1 x 2 7 x1 , x 2 0
解：图中阴影部分表示可行域，由图可知原问题在点 A 处取得最优值，最优值 2 x 2
x 1 x 2 1 s.t.x1 2x 2 4 x1 , x 2 0
① 因为 p1 , p 2 线性无关，故有
x 2x 2 7 3x 3 4x 4 1 2 x 1 x 2 3 x 3 2 x 4
，令非基变量为 x 3 x 4 0 ，得
x 1 1 3 1 11 (1) ，所以得到一个基解 x ( , ,0,0) 是非基可行解； 3 3 x 11 2 3
，令非基变量为 x 3 x 4 x 5 0 ，得
x 2 1 3 2 5 (1) ，所以得到一个基解 x ( , ,0,0,0) ，是非基可行解； 3 3 x 5 2 3
②因为 p1 , p 3 线性无关，可得基解 x
( 2)
(4,0,5,0,0) ，是非基可行解； (4,0,0,5,0) ，是非基可行解； (1,0,0,0,5) ， z 4 4 ；
⑩因为 p 4 , p 5 线性无关，可得基解 x 所以原线性规划的基可行解是 x
( 4)
(10 )
, x ( 7 ) , x ( 9) , x (10 ) ，最优解是 x ( 7 ) ，最优值是 z 1 。
1.3 用单纯形法求解下列线性规划问题； （1） max z 2 x1 3x 2