线性规划算法

本文部分内容来自。

csuzhucong

3754人浏览 · 2023-07-03 17:07:16

csuzhucong · 2023-07-03 17:07:16 发布

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家：点击跳转

本文部分内容来自网友博客

一，线性规划

1，线性规划

例如，一个企业“生产计划”的线性规划模型如下：

$max \, z = 50x_1+80x_2 \\ s.t. \, 0.5x_1 + 2x_2 \leq 40 \\ x_1+1.5x_2 \leq 45\\ x_1,x_2 \geq0$

$s.t.$ 是subject to的缩写，表示受限制于，其后跟约束条件。

线性规划问题三要素：

决策变量
目标函数
约束条件

线性规划问题的特点：

决策变量相互独立且连续变化
目标函数是线性函数
约束条件是线性不等式组

线性规划问题的解法：单纯形法、内点法

2，线性规划的标准形式

满足如下四个条件的线性规划模型：

所有决策变量的取值是非负的；
除决策变量非负约束外的其他约束是等式约束；
模型中目标函数需要极大化（也可以要求极小化）；
等式约束中常数项位于等号的右端（称为右端项，right hand side）

矩阵表示法：

3，线性规划的典范形式

典范形式是标准形式的基础上，额外满足：

右端项是非负的；
在等式约束中存在一组与等式约束个数相等的决策变量，它们的系数构成系数矩阵的一个单位子矩阵。

其中Z0是可行解（常数），因为有等式，所以max z的式子里面可以把x1 - xm都替换掉。

4，线性规划的可行域

线性规划的可行域是一个多面体，但可能是无界的。

若多面体S={x|Ax=b,x≥0}是非空的，则必存在极点。

二，单纯形法

单纯形算法遵循“初始点——判优——改进”的优化模式。

1，多面体表示定理、线性规划基本定理

（1）多面体表示定理

极点、极向量参考凸优化

（2）线性规划基本定理

于是线性规划可以表示成只有一个等式约束和若干个非负变量约束的线性规划问题：

${\rm min} \sum_{i \in \mathcal{K}}(\boldsymbol{c}^{\rm T} \boldsymbol{x}^i) \lambda_i + \sum_{j \in \mathcal{J}}(\boldsymbol{c}^{\rm T} \boldsymbol{d}^j) \mu_j , \\ {\rm s.t.} \sum_{i \in \mathcal{K}} \lambda_i = 1, \\ \lambda_i \geq 0, \mu_j \geq 0, i \in \mathcal{K} , j \in \mathcal{J}.$

这又分为2种情形：

于是极小化问题可转化为：

${\rm min} \sum_{i \in \mathcal{K}}(\boldsymbol{c}^{\rm T} \boldsymbol{x}^i) \lambda_i, \\ {\rm s.t.} \sum_{i \in \mathcal{K}} \lambda_i =1, \lambda_i \geq 0, i \in \mathcal{K}.$

转化后的问题，可行域是一个有限多面体，最优值一定在某个λi=1时取到。

即线性规划基本定理：最优解一定在某个顶点取到。

2，解空间、时间复杂度

（1）顶点

对于一般的线性规划问题标准形式而言，有n个变量，有m个约束。我们同样是在n个变量中任意抽取其中m个，然后将剩余的n−m个变量赋值为0，这样就构成了m乘m的方程组，求解这个方程组即可。

这个过程一定可以得到所有顶点，显然总数最多会有 C(n,m) 个。

（2）时间复杂度

单纯形简单的说就是遍历所有的顶点，虽然有剪枝，但是还是有可能遍历完所有顶点。

而顶点数和C(n,m)是一个量级的，这是一个指数级别的时间复杂度。

（3）基变量

在每个顶点处，有m个变量可能不为0，剩余的n−m个变量都为0，这m个称为基变量，n-m个称为非基变量。

3，寻找初始点

确定单纯形算法初始点的策略：两阶段法、大M法

两阶段法：

大M法：

4，判优规则

线性规划典范形式的矩阵表达式:

${\rm min} z=\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{b} + (\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N}) \boldsymbol{x}_{\boldsymbol{N}} \\ {\rm s.t.} \boldsymbol{x}_{\boldsymbol{B}}+\boldsymbol{B}^{-1}\boldsymbol{N}\boldsymbol{x}_{\boldsymbol{N}}=\boldsymbol{B}^{-1}\boldsymbol{b}, \boldsymbol{x}_{\boldsymbol{B}} \geq 0, \boldsymbol{x}_{\boldsymbol{N}} \geq 0.$

公式推导在下一节中。

5，改进规则

一个改进过程就是从一个顶点挪到另一个顶点，他们之间只有1个基变量不同。

具体可以分成三个部分：

（1）确定进入可行基的非基变量（称为转入规则（pivoting in））;

（2）确定离开可行基的基变量（称为转出规则（pivoting out））;

（3）进行可行基转换的线性方程组Gauss消去操作（称为转轴操作）。

PS：B一定是可逆矩阵。

由此可以将线性规划改写为如下形式：

在非基变量中我们选择其中一个分量 xq 进入到基变量中：

rq称为 reduced cost

多个可选的非基变量如何选择：

λ的选取：

6，示例

三，对偶单纯形法

1，对偶问题

（1）根据 reduced cost推导

原问题：

如果在某个顶点，对于所有q有 reduced cost rq>=0，那么这个顶点就是最优解。

最优解的充要条件可以表示成：

进一步：

对偶问题：

（2）根据拉格朗日乘数法推导

2，对偶问题和原问题的关系

弱对偶定理：

强对偶定理：

若原问题和对偶问题中有任意一个存在有界的最优解，则另外一个存在相同的最优解。
若原问题和对偶问题中有任意的最优解趋于无穷大，则另外一个不存在可行解。

3，实例

如果原问题是企业A拥有m种资源（有m个约束），计划生产n种产品（有n个变量），目标是最大化总收入；那么对偶问题就是，企业B想要收购这些资源，需要确定m种资源的报价（有m个变量），目标是最小化总成本，但企业A只有在卖资源的收益不低于卖产品的时候才会同意卖资源（n个约束）。

企业A生产书架、桌子和椅子三种产品，拥有48单位木材，20单位塑料，8单位钢材三项资源。已知：书架售价60元，生产一个书架需要8单位木材、4单位制造塑料和2单位钢材；桌子售价30元，生产一张桌子需要6单位木材、2单位塑料和1.5单位钢材；椅子售价20元，生产一把椅子需要1单位木材、1.5单位塑料和0.5单位钢材；

求三种产品各生产多少数量时，企业A能够最大化总收入。

对偶问题：

4，对偶单纯形

如果说线性规划的原问题的决策变量维数很多，而约束很少的话，我们把它转化为对偶问题后会得到一个约束很多，但是决策变量维数很少的对偶问题。

对偶单纯形法就是把问题转化成对偶问题再求解。

5，最优条件

（1）互补松弛定理

互补松弛定理：当且仅当 $r^Tx$ 为0时，原问题和对偶问题有最优解。

（2）KKT条件

第一部分和第二部分就代表是原问题可行解和对偶问题可行解。最后一部分代表的就是互补松弛条件。

四，内点法

单纯形算法虽然在实际应用中非常有效，至今占有绝对优势，但在理论上它还不是多项式算法。
1979年，前苏联数学家第一个给出了求解线性规划的多项式算法，这就是所谓的椭球算法。这个算法在理论上是重要的，但是计算结果很不理想，远不及单纯形方法有效。
人们提出进一步的问题：能否找到实用上也确实有效的多项式时间算法？正是在这样的背景下，产生了内点法。