(19)--2.3.3最优性检验和解的判别.pdf

最优性检验

和解的判定

线性规划问题的数学模型

一、从初始基可行解转换为另一基可行解

设线性规划问题

n

maxzcx

ii

i1

m

Pxb

ii

s.t.i1

xi0,i1,2,,n



其可行域记为C.

线性规划问题的数学模型

设其初始基可行解为

（0）000T

（，，，)

Xxxx

12n

其中非零坐标有m个。不失一般性，假设前m个坐标非

零，即

（0）000T

（，，，,0,,0)

Xxxx

12m

因X（0）C，故

m

Px0b（1）

i

i

i1

假设约束方程的增广矩阵为：

PPPPPPb

12mm1jn

100a1,m1a1ja1nb1



010aaab

2,m12j2n2





001a