第二章单纯形法.pdfVIP

一单纯形法的一般原理

•1确定初始基可行解

•对的线性规划问题

n

maxzcx

jj

j1

n

Pxb

•st.jj

j1

xj0(j1,,n)

•假定在上述约束条件的系数矩阵中总存在一个

单位矩阵：

•

•10···0

•(P,P,,P)

12m01···0

•···

•00···1

•

•式中P,P,,P称为基向量，对应基向量的变

12m

•量x,,x称为基变量。模型中其它的变量

1m

•xm+1,,xn称为非基变量。在中令所有非

基变量等于零，得到一个解，

TT

X(x,,x,,x)(b,,b,0,,0)

1mn1m

•因为b0,这个解为基可行解。

•

2从一个基可行解转换为另一个基可行解

•设初始可行基中前m个为基变量，即

X(0)(x0,,x0,0,0)T(b,,b,0,,0)T

1m1m

•代入约束条件，有

m

0

•Pxb式（1）

ii

i1

写出（1）式系数矩阵的增广矩阵

PPPPm+1PPnb

12mj

100a1,m+1a1,ja1,nb1

010a2,m+1a2,ja2,nb2



1aam,jam,nbm

00m,m+1

P,P,,P是一组基，其他非基向量可以用

•12m

m