2.2单纯形法的求解步骤

线性规划问题的求解有以下几个步骤：

(1)确定初始基本可行解。为了确定初始基本可行解，首先要找出初始可行解。 设一线性规划问题为

cx

jj 1

n

j

n

pjxj b

j 1 （2-14）

x 0，j 1,2，...，n j

可分为两种情况讨论。

①若Pj(j 1,2, ,n)中存在一个单位基，则将其作为初始可行基

10 0

01 0

B （2-15） （p1，p2，..，.pm）

00 1

②若Pj(j 1,2, ,n)中不存在一个单位基，则人为地构造一个单位初始基。

(2)检验最优解。得到初始基本可行解后，要检验该解是否为最优解。如果是最优解，则停止运算；否则转入（3）基变换。下面给出最优性判别定理。一般情况下，经过迭代后可以得到以非基变量表示基变量的表达式

xj bi-

j m 1

ax

ij

n

j

，m） （2-16） （i 1,2，

将式(2-11)代入式(2-10)的目标函数，整理后得

maxZ cibi (cj ciaij)xj （2-17）

i 1

i 1

i 1

m

n

n

令

，n） Z0 cibi,Zj ciaji （j m 1， （2-18）

i 1

i 1

n

m

于是

max z z0 (cj zj)xj （2-19）

j m 1n