单纯形法的计算方法

第4章 单纯形法的计算方法

单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。

4.1 初始基可行解的确定

为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z =n

j j j=1c x ∑

1,1,2,...,0,1,2,...n

ij j i j j

a x

b i m

x j n =⎧==⎪⎨⎪≥=⎩∑

从Pj ( j = 1 , 2 , ⋯ , n )中一般能直接观察到存在一个初始可行基

121(,,...,)n B P P P 0 0⎛⎫ ⎪0 1 0 ⎪== ⎪ ⎪0 0 1⎝⎭

（2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对

j x 及ij a ( i = 1 , 2 , ⋯ , m ; j = 1 , 2 , ⋯ , n )进行编号, 则可得下列方

程组

11,1111

22,1122,1112.........,,...,0

m m n n m m n n m m m m nn n n

n x a x a x b x a x a x b x a

x a x b x x x +++++++++=⎧⎪

+++=⎪⎪

⎨⎪+++=⎪⎪≥⎩

显然得到一个m ×m 单位矩阵

121(,,...,)n B P P P 0 0⎛⎫ ⎪0 1 0 ⎪== ⎪ ⎪0 0 1⎝⎭ 以B 作为可行基。将上面方程组的每个等式移项得

111,111222,112,11.........m m n n

m m n n

m m m m m mn n x b a x a x x b a x a x x b a x a x ++++++=---⎧⎪

=---⎪⎨ ⎪⎪=---⎩

令12...0,m m n x x x ++====由上式得

(1,2,...,)i i x b i m == 又因i b ≥0, 所以得到一个初始基可行解

12()12()(,,...,,0,...,0)(,,...,,0,...,0)T

m n m T

m n m X x x x b b b --= =

个

个

（3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约束情况, 若不存在单位矩阵时, 就采用人造基方法。即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。

4.2 最优性检验和解的判别

对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。一般情况下, 经过迭代后可以得到：

1

(1,2,...,)n

i i ij

j j m x b a

x i m '

'

=+=-=∑

将上代入目标函数，整理后得 11

1

()m n m

i i j

i ij

j i j m i z c b c c a

x '

'

==+==+

-∑∑∑

令

01

1

,,1,...,m

m

i i j i ij i i z c b z c a j m n '

'=====+∑∑

于是

01

()n

j

j j j m z z c

z x =+=+-∑

再令

(1,...,)j j j c z j m n σ=-=+ 则

01

n

j

j j m z z x σ

=+=+

∑

(1) 最优解的判别定理

若(0)12(,,...,,0,...,0)T m X b b b '''=为对应于基B 的一个基可行解，且对于一切

1,...,,j m n =+且有0,j σ≤则(0)X 为最优解。称j σ为检验数。

(2) 无穷多最优解的判别定理

若(0)12(,,...,,0,...,0)T m X b b b '''=为一个基可行解， 且对于一切 1,...,,j m n =+且有0,j σ≤ 又存在某个非基变量的检验数0m k σ+=，则线性规划问题有无穷多最优解。

(3) 无界解判别定理

若(0)12(,,...,,0,...,0)T m X b b b '''=为一个基可行解，有一个m k σ+> 0 ,并且对i = 1 , 2 , ⋯, m ,有,i m k a + ≤0 , 那么该线性规划问题具有无界解(或称无最优解)。

4.3 基变换

若初始基可行解(0)X 不是最优解及不能判别无界时, 需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立),得到一个新的可行基, 这称为基变换。为了换基, 先要确定换入变量, 再确定换出变量, 让它们相应的系数列向量进行对换, 就得到一个新的基可行解。

(1) 换入变量的确定 由01

n

j

j j m z z x σ

=+=+

∑看到, 当某些j σ > 0 时, j x 增加则目标函数值还可以

增大, 这时要将某个非基变量j x 换到基变量中去(称为换入变量)。若有两个以上的j σ > 0 , 则为了使目标函数值增加得快, 从直观上一般选j σ> 0 中的大者, 即

max(0)j k σσ>= 则对应的k x 为换入变量。 (2) 换出变量的确定

设12,,...,m P P P 是一组独立的向量组，它们对应的基可行解是(0)X

。将它代入约束方程组得到

(0)1m

i i i x P b ==∑

其他的向量12,,...,,...,m m m t n P P P P +++ 都可以用12,,...,m P P P 线性表示，若确定非基变量m t P +为换入变量，必然可以找到一组不全为零的数（i=1,2，...,m ）使得 ,1m

m t i m t t i P P β++==∑

在上式两边同乘一个正数θ，然后将它加到式(0)1

m

i i i x P b ==∑上，得到

(0),1

1

()m m

i i m t i m t i i i x P P P b θβ++==+-=∑∑

或

(0),1()m

i i m t i m t i x P P b θβθ++=-+=∑

当θ取适当值时, 就能得到满足约束条件的一个可行解( 即非零分量的数目不大于m 个)。就应使(0),()i i m t x θβ+-( i = 1 , 2 , ⋯ , m ) 中的某一个为零,并保证其余的分量为非负。这个要求可以用以下的办法达到: 比较各比值

(0)

,i i m t

x β+( i = 1 ,

2 , ⋯ , m )。又因为θ必须是正数, 所以只选择

(0)

,i i m t

x β+> 0 ( i = 1 , 2 , ⋯ , m )