线性规划单纯形法【推导+实例】

线性规划单纯形法【推导+实例】

引用

CSDN

1.

https://blog.csdn.net/v20000727/article/details/136836730

一、标准形式

线性规划的标准形式如下：

$$
\begin{aligned}
&\min \mathbf{c^T}x\
& s.t. \quad \boldsymbol{Ax = b}, \qquad (LP) \
& \qquad \quad \boldsymbol{x\geq 0}
\end{aligned}
$$

其中A 是m × n 的矩阵，c 是n维列向量，b 是m维列向量。当变量有上下界，不满足标准形式时，需要引入松弛变量将问题转化为标准形式。

二、极点、极方向

定义（极点）

对于任意凸集S ，S 内一向量x 如果是S 的极点，那么不存在不同于x 的两个向量y , z ，使得x = λ y + ( 1 − λ ) z , 0 ≤ λ ≤ 1 。

Note:

1. 极点不能表示成两个不同点的组合；
2. 极点不在S 中任何线段的内部；
3. 显然，多边形的顶点和圆周上的任意一点都是极点；

定义（方向）

设S 为R n 中的闭凸集,d 为非零向量, 如果对S 中的每一个x , 都有

{ x + λ d ∣ λ ⩾ 0 } ⊂ S ,

则称向量d 为S 的方向.

定义（极方向）

设d ( 1 ) 和d ( 2 ) 是S 的两个方向, 若对任何正数λ , 有d ( 1 ) ≠ λ d ( 2 ) , 则称d ( 1 ) 和d ( 2 ) 是两个不同的方向. 若S 的方向d 不能表示成该集合的两个不同方向的正 的线性组合,则称d 为S 的极方向.

显然,有界集不存在方向, 因而也不存在极方向. 对于无界集才有方向的概念.

例

设S = { x ∣ A x = b , x ⩾ 0 } 为非空集合,d 是非零向量. 证明d 为S 的方向的充要条件是d ⩾ 0 且A d = 0 .

证明 :

按照定义,d 为S 的方向的充要条件是: 对每一个x ∈ S , 有

{ x + λ d ∣ λ ⩾ 0 } ⊂ S . ( 1 )

根据集合S 的定义, (1)式即

A ( x + λ d ) = b , x + λ d ⩾ 0. ( 2 )

由于A x = b , x ⩾ 0 及λ 可取任意非负数, 因此由 (2)式知A d = 0 及d ⩾ 0 .

下面给出多面集的一个重要性质, 这就是所谓的表示定理.

定理（表示定理）

设S = { x ∣ A x = b , x ⩾ 0 } 为非空多面集,则有:

(1) 极点集非空, 且存在有限个极点x ( 1 ) , ⋯ , x ( k ) .

(2) 极方向集合为空集的充要条件是S 有界. 若S 无界, 则存在有限个极方向d ( 1 ) , ⋯ , d ( n ) .

(3)x ∈ S 的充要条件是:

x = ∑ j = 1 k λ j x ( j ) + ∑ j = 1 l μ j d ( j ) , ∑ j = 1 k λ j = 1 , λ j ⩾ 0 , j = 1 , ⋯ , k , μ j ⩾ 0 , j = 1 , ⋯ , l .

三、 线性规划基本性质

（1）最优解会在极点处取得

由表示定理可以推出如下的定理，具体的证明见《最优化理论与算法（陈宝林）》

定理

设线性规划(LP)的可行域非空, 则有下列结论:

• 若线性规划存在有限最优解, 则目标函数的最优值可在某个极点上达到.

Note：

• 也就是说一定会在某个极点上取得最优解

（2）基本可行解

在线性规划(LP)中, 设矩阵A 的秩为m ，又假设A = [ B , N ] ，其中B 是m 阶可逆矩阵（如果r a n k ( A ) < m ，说明有冗余行，可以消去）。如果A 的前m 列是线性相关的, 可以通过列调换, 使前m 列成为线性无关的, 因此关于B 可逆的假设不失一般性。同时记作

x = [ x B x N ] ,

其中x B 的分量与B 中的列对应,x N 的分量与N 的列对应。这样, 可把A x = b 写成

( B , N ) [ x B x N ] = b ,

即

B x B + N x N = b .

上式两端左乘B − 1 , 并移项, 得到

x B = B − 1 b − B − 1 N x N ,

x N 的分量就是线性代数中所谓的自由末知量,它们取不同的值, 就会得到方程组的不同的解。特别地, 令x N = 0 , 则得到解

x = [ x B x N ] = [ B − 1 b 0 ] .

定义（基本解）

1. 将

x = [ x B x N ] = [ B − 1 b 0 ]

称为方程组A x = b 的一个基本解；

2. B 称为基矩阵，简称为基；

3. x B 的各分量称为基变量, 基变量的全体x B 1 , x B 2 , ⋯ , x B m 称为一组基;

4. x N 的各分量称为非基变量。

又若B − 1 b ⩾ 0 , 则称

x = [ x B x N ] = [ B − 1 b 0 ]

为约束条件A x = b , x ⩾ 0 的基本可行解。相应地, 称B 为可行基矩阵,x B 1 , x B 2 , ⋯ , x B m 为 一组可行基。若B 1 b > 0 , 即基变量的取值均为正数, 则称基本可行解是非退化的。如果满 足B − 1 b ⩾ 0 且至少有一个分量是零, 则称基本可行解是退化的基本可行解。

每一组基对应一个基本解， 一般地, 当A 是m × n 矩阵,A 的秩为m 时, 基本可行解的个数不会超过:

( n m ) = n ! m ! ( n − m ) ! .

定理（极点和基本可行解等价）

令K = { x ∣ A x = b , x ⩾ 0 } , A 是m × n 矩阵,A 的秩为m , 则K 的极点集与A x = b , x ⩾ 0 的基本可行解集等价。

证明见《最优化理论与算法（陈宝林）》第二章。

Note:

1. 线性规划的最优解会在某个极点达到；
2. 极点和基本可行解等价；
3. 所以线性规划问题的求解，可以归结为求最优基本可行解；
4. 这个思想是单纯形法的主要出发点。

四、单纯形法

由上节的介绍我们知道线性规划的最优解会出现在某个顶点，而单纯形法的主要思想是从一个顶点出发，去找下一个能让目标函数变小（或者变大）的顶点。而如何去寻找这样的顶点，从数学上来说其实就是基本可行解的转换。

（1）数学理论

考虑问题

min f = def c x s. t. A x = b , x ⩾ 0 ,

其中A 是m × n 矩阵,秩为m , c 是n 维行向量,x 是n 维列向量,b ⩾ 0 是m 维列向量。记：

A = ( p 1 , p 2 , ⋯ , p n ) .

现将A 分解成( B , N ) (可能经列调换), 使得其中B 是基矩阵,N 是非基矩阵, 设

x ( 0 ) = [ B − 1 b 0 ]

是基本可行解,在x ( 0 ) 处的目标函数值

f 0 = c x ( 0 ) = ( c B , c N ) [ B − 1 b 0 ] = c B B 1 b ,

其中c B 是c 中与基变量对应的分量组成的m 维行向量.c N 是c 中与非基变量对应的分量 组成的n − m 维行向量。现在分析怎样从基本可行解x ( 0 ) 出发, 求一个改进的基本可行解.

设

x = [ x B x N ]

是任一个可行解, 则由A x = b 得到

x B = B − 1 b − B − 1 N x N ,

在点x 处的目标函数值

f = c x = ( c B , c N ) [ x B x N ] = c B x B + c N x N = c B ( B − 1 b − B − 1 N x N ) + c N x N = c B B − 1 b − ( c B B − 1 N − c N ) x N = f 0 − ∑ j ∈ R ( c B B − 1 p j − c j ) x j = f 0 − ∑ j ∈ R ( z j − c j ) x j , ( 1 )

其中R 是非基变量下标集,

z j = c B B − 1 p j .

由 (1) 式可知, 适当选取自由末知量x j ( j ∈ R ) 的数值就有可能使得

∑ j ∈ R ( z j − c j ) x j > 0 ,

从而得到使目标函数值减少的新的基本可行解。为此, 在原来的n − m 个非基变量中, 使 得n − m − 1 个变量仍然取零值, 而令一个非基变量, 比如x k 增大, 即取正值, 以便实现我们的目的。那么怎样确定下标k 呢? 根据 (1) 式, 当x j ( j ∈ R ) 取值相同时,z j − c j (正 数)越大, 目标函数值下降越多, 因此选择x k , 使

z k − c k = max j ∈ R { z j − c j } ,

这里假设z k − c k > 0. x k

x k 由零变为正数后, 得到方程组A x = b 的解

x B = B − 1 b − B − 1 p k x k = b ‾ − y k x k ,

其中b ˉ 和y k 是m 维列向量,b ˉ = B − 1 b , y k = B − 1 p k

把x B 按分量写出, 即

x B = [ x B 1 x B 2 ⋮ x B m ] = [ b ˉ 1 b ˉ 2 ⋮ b ˉ m ] − [ y 1 k y 2 k ⋮ y m k ] x k , ( 2 )

x N = ( 0 , ⋯ , 0 , x k , 0 , ⋯ , 0 ) T ,

在新得到的点, 目标函数值是

f = f 0 − ( z k − c k ) x k . ( 3 )

再来分析怎样确定x k 的取值。一方面, 根据(3) 式,x k 取值越大函数值下降越多; 另一方面, 根据 (2) 式,x k 的取值受到可行性的限制, 它不能无限增大 (当y k ⩽ 0 时)。对 某个i , 当y i k ⩽ 0 时,x k 取任何正值时, 总成立x B i ⩾ 0 ，而当y i k > 0 时, 为保证

x B i = b ˉ i − y i k x k ⩾ 0 ,

就必须取值

x k ⩽ b ˉ i y i k

因此, 为使x B ⩾ 0 , 应令

x k = min { b ˉ i y i k ∣ y i k > 0 } = b ˉ r y r k ,

x k 取值b ˉ r / y r k 后, 原来的基变量x b = 0 , 得到新的可行解这个解一定是基本可行解。因为原来的基

B = ( p B 1 , ⋯ , p B r , ⋯ , p B m )

中的m 个列是线性无关的, 其中不包含p k 。由于y k = B − 1 p k ，故

p k = B y k = ∑ i = 1 m y i k p B t ,

即p k 是向量组p B 1 , ⋯ , p B r , ⋯ , p B m 的线性组合, 且系数y r k ≠ 0 。因此用p k 取代p B r 后, 得到的向量组

p B 1 , ⋯ , p k , ⋯ , p B m ,

也是线性无关的。因此新的可行解x 的正分量对应的列线性无关,故x 为基本可行解。

经上述转换,x k 由原来的非基变量变成基变量,而原来的基变量x B r 变成非基变量。在新的基本可行解处, 目标函数值比原来减少了( z k − c k ) x k 。重复以上过程, 可以进一步 改进基本可行解, 直到在 (1) 式中所有z j − c j 均非正数, 以致任何一个非基变量取正值都不能使目标函数值减少时为止。

定理 （单纯形法判别数）

1. 若在极小化问题中, 对于某个基本可行解, 所有z j − c j ⩽ 0 ，则这个基本可行解是最优解;
2. 若在极大化问题中, 对于某个基本可行解, 所有z j − c j ⩾ 0 ，则这个基本可行解是最优解。

其中:

z j − c j = c B B − 1 p j − c j , j = 1 , ⋯ , n .

在线性规划中, 通常称z j − c j 为判别数或检验数。

（2）实例

Reference

1. 陈宝林.《最优化理论与算法》第二版