记：Z0=CBB-1b
(1-1) (1-2) (1-3)
(1-4)
2 最优解判别定理
定理：设B是线性规划(1-1)’～(1-2)’的基
b’=B-1b=(b’1 ,b’2 ,…..b’m )T ≥0 X(0)是与B对应的基可行解，即
X(0) ＝（ b’1 ,b’2 ,…0 ..b’m,0,…..0) T 如果X所有的检验数 j ≤0,则X 是最优解。

X
1

X
2


X
3
X 4


X
5


(1,2,0,0)T
( 45 ,0, 14 ,0)T 13 13
(34 ,0,0, 7 )T
5
5
(0, 45 , 7 ,0)T 16 16
(0, 68 ,0, 7 )T 29 29

X
6

(0,0, 68 , 45)T 31 31
注：基向量的下标视约束方程而异，不一定是1,2,…,m
例 2 求初始基可行解
max z = 3x1-2x2+5x3+9x4-x5
x1
s.t.

x2 x3
x4 x5 8 6x4 - 3 x5 12 x4 2x5 4
Hale Waihona Puke x1, , x5 0解：
系数矩阵A
b
1 0… 0… 0 a1,m+1… a1,m+t… a1n
b1
0 1… 0… 0 ┇
a2,m+1… a2,m+t… a2n ┇
b2 ┇
0 0… 1… 0 al,m+1… al,m+t… aln
┇
┇
bl
0 0… 0… 1 am,m+1… am,m+t… amn
┇
bm
新的基可行解的产生
e 用关于行的初等变换将
a'lj
=
alj al ,m +t
b'l
=
bl al ,m +t
新的基可行解的产生
已知 b1>0, 若 b’t >0, 则需 al,m+t >0.
当i≠l时， a'ij =aij +a'lj
-ai,m+t
=
aij
-
ai,m+t al ,m +t
• aij
b'i = bi +b'l -ai,m+t
x1 , x2 , x3 , x4 0
约束方程组的系数矩阵：
2 3 1 4 A (P1, P2, P3, P4 ) 1 2 6 7
共有6个基Bj,对应6个基本解Xj，j=1，2，…，6
B1 B2 B3 B4 B5 B6
(P1 , P2 ) (P1 , P3 ) (P1 , P4 ) (P2 , P3 ) (P2 , P4 ) (P3 , P4 )
x1 3x2 x3 2x4 1
x1, x2 , x3, x4 0
x (0,3 2,0, 7 4) , 证明x是最优解

证明：取基B=（ 可行解。且B=： 1
P2 ，P4），容易验证
6
，B-1
=
1 2
X 是与B对应的基
6
3 2
16
X (0) (b1, b2 ,..., bm ,0,..., 0)T
用A的列向量 Pm+t 替换B中的 Pl ， 所得的新矩阵为：
B1 (P1, P2 ,..., Pl1, Pmt , Pl1,..., Pm )
新的基可行解的产生
若新矩阵仍未非奇异矩阵，则可取其为新基。
称 Pm+t 为入基向量，Pl 为出基向量，对应的 X m+t 为入基变量，X l 为出基变量。
谢谢！
┇
┇
┇
0 0… a’ml… 1 a’m,m+1… 0 … a’mn b’m
新的基可行解的产生
由表1-2可知,基B1对应的基本解X(1)为
x (1) j

b
' j
,当j

m, 且j
l
x (1) mt
bl'
x (1) j
0, 对其余的j
为使 x(1) 成为可行解,必须使所有的 b’j 成为非负数. 表1-2中，利用行初等变换将入基向量化为单位向量，因此，
取初始基B0 （P2, P1, P5） I，
则初始基本解X0 （4,7,0,0,1,0)T
三：最优性准则
1、目标函数的非基变量表达式
设问题为 max Z=CX
(1-1)
s.t. AX=b,b≥0
(1-2)
X≥0
(1-3)
设基A＝变（量B,N），其中B是基，相应地，设基变量构成的向量为XB，非
其中，由于X2，X5，X6,中存在负值，故只有X1，X3， X4是基可行解，其对应的目标函数值分别是：
Z1 CX1 8, Z3 CX 3 23.4, Z4 CX 4 10.1875
目标函数值最大者为X3，但这并不是最优解。实际上，任
取 >0，令
X (345 3.1,0, , 7 5 1.3)T
,
cm
2

CB B1Pm2 ,..., cn

CB B1Pn )
( m1, m2,..., n)
其中
j c j CB B1Pj , j m 1,..., n
于是有：
Z Z0 ( m1, m2,..., n)(xm1,xm2,...,xn )T
到最优解为止。若原问题无最优解，也可根据最优性理 论及时发现，停止计算。
流程框图
开始
初始基 可行解
是最优 解？
Y
输出最 优解
N
无最优解
N 生成更优的 基可行解
Y
停
二、初始基可行解
1．确定初始基可行解 对标准型的线性规划问题 ：
max Z c1x1 c2 x2 ... cn xn x1 a1.m1xm1 ... a1.n xn b1
6 16
1 16
1 1

-
1 2
由最优解判别定理知：X 是最优解.
X
二、基可行解的迭代与改进
（一）新的基可行解的产生 （二）基可行解的改进
新的基可行解的产生
设线性规划的约束方程组的系数矩阵为A=(I,N)，取基
（标准基） B0 =I P1, P2,...Pm
则其对应的初始基可行解为:
表1-1化为了表1-2
Pm +t
化为单位向量
,同时 l
x1 x2… xl… xm xm+1… xm+t… xn
b
1 0… a’1l… 0 a’1,m+1… 0 … a’1n b’1
0 1… a’2l… 0 a’2,m+1… 0 … a’2n b’2
┇
┇
┇
0 0… a’ll… 0 a’l,m+1… 1 … a’ln b’l
容易验证 X 是可行点，且其目标函数值为：
Z CX 23.4 19.3 23.4 CX 3
一.单纯型法的基本思路
如果线性规划问题存在最优解，一定有一个基可行解是 最优解。 因此单纯形法迭代的基本思路是：先找出一 个基可行解，判断其是否为最优解，如果为否，则转换 到相邻的基可行解，并使目标函数值不断增大，一直找
命题： 若检验数σm+t >0，按上式θ准则
选取主元al,m+t并进行换基迭代后所得到的 新基可行解X(1)优于原来的基可行解X(0)。
证明： X(1)所对应的目标函数值为
CX 1 =Z0 b'σ l m+t >Z0 =CX 0
此命题表明，只要选取正检验数对应的 变量为入基变量，并对该元素按θ准则确定 主元，再进行换基迭代，则必可得到一个优 于原基可行解的新的基可行解。

(
P1
,
P2
,
P3
,
P4，P5
)


1 0
0 1
0 0
1 6
1 3
0 0 1 1 2
取初始基B0 I （P1, P2 , P3），
则初始基本解X0 （b1, b2 ,b3,0,0)T (8,12,4,0,0)T
例 3 求初始基可行解
max z = 4x1-5x2-x3+2x4+3x5-x6
缺点：当基可行解个数很多时，穷举法的工作 量太大。所以，若事先无法判断是否存在最优 解，采用穷举法可能导致错误结论。
举例说明
设：
max Z 2x1 3x2 4x3 7x4
s.t.2xx11
3x2 2x2

x3 4x4 8 6x3 7x4 3

x2 x3 x4 2x6 7
s.t.

x1

5 x3
-
x4
-
3x6

4
4x3 2x4 x5 x6 4
x1, , x6 0
0 1 1 1 0 2
系数矩阵A

(
P1
,
P2
,
P3
,
P4，P5
,
P6
)


1
0
5
1 0 3
0 0 4 2 1 1
原问题可表为：