线性规划算法- MATLAB和Simulink万博1manbetx - 万博1manbetx,s manbetx 845,万博尤文图斯

线性规划算法

线性规划定义

线性规划的问题是找到一个向量x使线性函数最小化f<年代up>Tx受线性约束：

$\underset{x}{最小值} f^{T} x$

使以下一项或多项有效：

·x≤b
Aeq·x＝说真的
l≤x≤u．

内点linprog算法

的linprog“内点”算法非常类似于<一个href="//www.tianjin-qmedu.com/help/optim/ug/quadratic-programming-algorithms.html" class="a">interior-point-convex quadprog算法。它还与linprog“interior-point-legacy”算法。这些算法有相同的大纲:

解决，意思简化和转换问题到一个标准形式。
生成初始点。初始点的选择对于高效求解内点算法尤为重要，这一步骤非常耗时。
预测校正迭代求解KKT方程。这一步通常是最耗时的。

Presolve

该算法首先试图通过去除冗余和简化约束来简化问题。在预解步骤中执行的任务包括:

检查是否有任何变量有相同的上界和下界。如果是，检查可行性，然后修复和删除变量。
检查任何线性不等式约束是否只涉及一个变量。如果是，请检查可行性，然后将线性约束更改为一个界。
检查任何线性等式约束是否只涉及一个变量。如果是，请检查可行性，然后修复并删除该变量。
检查任何线性约束矩阵是否有零行。如果是，检查是否可行，然后删除行。
确定边界和线性约束是否一致。
检查是否有变量只出现在目标函数的线性项中而不出现在任何线性约束中。如果是，检查可行性和有界性，然后将变量固定在适当的界限。
通过添加松弛变量，将线性不等式约束变为线性等式约束。

如果算法检测到一个不可行的或无界的问题，它会停止并发出适当的退出消息。

该算法可能会到达一个单一的可行点，这代表了解决方案。

如果算法在预解步骤中未检测到不可行或无界问题，并且如果预解未生成解决方案，则算法将继续其下一步骤。在达到停止标准后，该算法重建原始问题，撤消任何预解变换。最后一步是后求解步骤。

为简单起见，如果问题没有在预解步骤中解决，算法将所有的有限下界移到零。

生成初始点

为了设置初始点，x0，该算法执行以下操作。

初始化x0来的(n, 1)，在哪里n目标函数的元素数是向量吗f．
将所有有界组件转换为下限为0。如果组件我有一个有限的上界u(我),然后x0 (i) = u / 2．
对于只有一个边界的组件，如有必要，请修改该组件，使其严格位于边界内。
把x0靠近中心路径，执行一个预测-校正步骤，然后修改得到的位置和松弛变量，使其处于任何范围内。关于中心路径的详细信息，请参阅Nocedal和Wright<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［7］, 397页。

预估

类似于fmincon内点算法,内点算法试图找到一个点<一个href="//www.tianjin-qmedu.com/help/optim/ug/first-order-optimality-measure.html" class="a">Karush-Kuhn-Tucker(马)条件。为了描述线性规划问题的这些方程，考虑预处理后的线性规划问题的标准形式:

$\underset{x}{最小值} f^{T} x 受｛ \begin{matrix} \bar{一个} x ＝ \bar{b} \\ x + t ＝ u \\ x ， t \geq 0. \end{matrix}$

现在假设所有变量至少有一个有限界。如果有必要，通过移动和否定组件，这个假设意味着所有x组件的下限为0。
$\bar{一个}$ 是扩展的线性矩阵，它包括线性不等式和线性等式。<年代p一个ncl一个年代年代＝"inlineequation"> $\bar{b}$ 是相应的线性等式向量。<年代p一个ncl一个年代年代＝"inlineequation"> $\bar{一个}$ 还包括用于扩展向量的术语x与松弛变量年代将不平等的约束转化为平等的约束:

$\bar{一个} x ＝（ \begin{matrix} {一个}_{e 问} & 0 \\ 一个 & 我 \end{matrix} ）（ \begin{matrix} x_{0} \\ 年代 \end{matrix} ），$

在哪里x₀意味着原x矢量。
t是将上界转换为等式的松弛向量。

该系统的拉格朗日函数包括以下向量：

y，与线性等式相关的拉格朗日乘数
v，与下界(正性约束)相关的拉格朗日乘数
w，与上界相关的拉格朗日乘数

拉格朗日是

$l ＝ f^{T} x - y^{T} （ \bar{一个} x - \bar{b} ） - v^{T} x - w^{T} （ u - x - t ）．$

因此，该系统的KKT条件为

$\begin{matrix} f - {\bar{一个}}^{T} y - v + w ＝ 0 \\ \bar{一个} x ＝ \bar{b} \\ x + t ＝ u \\ v_{我} x_{我} ＝ 0 \\ w_{我} t_{我} ＝ 0 \\ （ x ， v ， w ， t ） \geq 0. \end{matrix}$

的linprog算法对返回的拉格朗日乘数使用了与本讨论给出的不同的符号约定。这个讨论使用了和大多数文学作品一样的符号。看到<一个href="//www.tianjin-qmedu.com/help/optim/ug/linprog.html">λ．

该算法首先根据牛顿-拉夫森公式预测步长，然后计算出校正步长。校正器试图减少非线性互补方程中的残差<年代p一个ncl一个年代年代＝"inlineequation">年代<年代ub>我z<年代ub>我= 0．牛顿-拉夫森阶跃是

（ \begin{matrix} 0 & - {\bar{一个}}^{T} & 0 & - 我 & 我 \\ \bar{一个} & 0 & 0 & 0 & 0 \\ - 我 & 0 & - 我 & 0 & 0 \\ V & 0 & 0 & X & 0 \\ 0 & 0 & W & 0 & T \end{matrix} ） （ \begin{matrix} Δ x \\ Δ y \\ Δ t \\ \begin{array}{l} Δ v \\ Δ w \end{array} \end{matrix} ） ＝ - （ \begin{matrix} f - {\bar{一个}}^{T} y - v + w \\ \bar{一个} x - \bar{b} \\ u - x - t \\ \begin{array}{l} V X \\ W T \end{array} \end{matrix} ） ＝ - （ \begin{matrix} r_{d} \\ r_{p} \\ r_{u b} \\ \begin{array}{l} r_{v x} \\ r_{w t} \end{array} \end{matrix} ） ，

(1）

在哪里X，V，W,T对角矩阵对应于这些向量吗x，v，w,t分别。方程最右边的剩余向量为:

r<年代ub>d，对偶残差
r<年代ub>p，原始残差
r<年代ub>乌兰巴托，上界残差
r<年代ub>vx，下界互补残差
r<年代ub>wt，上界互补残差

迭代显示报告这些数量:

$\begin{array}{l} 原始的不可行性＝ {为 r_{p} 为}_{1} + {为 r_{u b} 为}_{1} \\ 双不可行性＝ {为 r_{d} 为}_{\infty} ． \end{array}$

来解决<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式1，首先将其转换为对称矩阵形式

（ \begin{matrix} - D & {\bar{一个}}^{T} \\ \bar{一个} & 0 \end{matrix} ） （ \begin{matrix} Δ x \\ Δ y \end{matrix} ） ＝ - （ \begin{matrix} R \\ r_{p} \end{matrix} ） ，

(2）

在哪里

$\begin{array}{l} D ＝ X^{- 1} V + T^{- 1} W \\ R ＝ - r_{d} - X^{- 1} r_{v x} + T^{- 1} r_{w t} + T^{- 1} W r_{u b} ． \end{array}$

定义中的所有矩阵逆D和R很容易计算，因为矩阵是对角线的。

获得<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式2从<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式1，注意第二行<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式2与的第二个矩阵行相同<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式1．第一行<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式2来自于求解最后两行的<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式1对于Δv和Δw，然后求Δt．

方程式2是对称的，但它不是正定的，因为-D术语。因此，你不能用乔尔斯基分解来解决它。再多几个步骤就可以得到一个不同的正定方程，因此可以用乔尔斯基分解法有效地求解。

第二组<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式2是

$\bar{一个} Δ x ＝ - r_{p}$

第一组行是

$- D Δ x + {\bar{一个}}^{T} Δ y ＝ - R ．$

替换

$Δ x ＝ D^{- 1} {\bar{一个}}^{T} Δ y + D^{- 1} R$

给了

\bar{一个} D^{- 1} {\bar{一个}}^{T} Δ y ＝ - \bar{一个} D^{- 1} R - r_{p} ．

(3）

通常，求牛顿步的最有效方法是解<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式3对于Δy使用柯列斯基分解。乔尔斯基分解是可能的，因为矩阵乘以Δy是明显对称的，并且在没有简并的情况下是正定的。之后，求牛顿步，回代求Δx,Δt,Δv,Δw.但是，什么时候<年代p一个ncl一个年代年代＝"inlineequation"> $\bar{一个}$ 有一个密集的柱，它能更有效地解决吗<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式2代替。的linprog内点算法根据列的密度选择求解算法。

有关更多算法详细信息，请参阅Mehrotra<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［6］．

在计算正确的牛顿步后，算法执行更多的计算，以获得更长的当前步，并为更好的后续步骤做准备。这些多重校正计算可以提高性能和鲁棒性。详情请参见Gondzio<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［4］．

预测-校正算法与完整的基本相同quadprog“内点凸”版本，除了二次项。看到<一个href="//www.tianjin-qmedu.com/help/optim/ug/quadratic-programming-algorithms.html" class="a">全预测校正器．

停车条件

预测-校正算法迭代，直到它到达一个可行的点(满足约束到公差范围内)，并且相对步长较小。具体来说,定义

$ρ ＝马克斯（ 1 ，为 \bar{一个} 为，为 f 为，为 \bar{b} 为）．$

当这些条件都满足时，算法停止:

$\begin{matrix} {为 r_{p} 为}_{1} + {为 r_{u b} 为}_{1} \leq ρ 托尔康 \\ {为 r_{d} 为}_{\infty} \leq ρ 托尔芬 \\ r_{c} \leq TolFun, \end{matrix}$

在哪里

$r_{c} ＝ \underset{我}{马克斯} （最小值（ | x_{我} v_{我} | ， | x_{我} | ， | v_{我} | ），最小值（ | t_{我} w_{我} | ， | t_{我} | ， | w_{我} | ））．$

r<年代ub>c本质上度量了互补残差的大小十五和太瓦，它们都是解处的0向量。

Interior-Point-Legacy线性规划

介绍

内点遗留方法是基于<一个cl一个年代年代＝"indexterm" name="d123e33143">利普索尔(<一个href="//www.tianjin-qmedu.com/help/optim/ug/selected-bibliography.html" class="a">[52]，是。的变体<一个cl一个年代年代＝"indexterm" name="d123e33148">Mehrotra预估校正算法(<一个href="//www.tianjin-qmedu.com/help/optim/ug/selected-bibliography.html" class="a">[47]),一个<一个cl一个年代年代＝"indexterm" name="d123e33153">内点方法。

主要算法

算法首先应用一系列<一个cl一个年代年代＝"indexterm" name="d123e33162">预处理步骤(见<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理）.预处理后，问题有形式

\underset{x}{最小值} f^{T} x 这样 ｛ \begin{matrix} 一个 \cdot x ＝ b \\ 0 \leq x \leq u ． \end{matrix}

（4）

上界约束隐式包含在约束矩阵中一个．加上原始松弛变量年代，<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式4就变成了

\underset{x}{最小值} f^{T} x 这样 ｛ \begin{matrix} 一个 \cdot x ＝ b \\ x + 年代 ＝ u \\ x \geq 0 ， 年代 \geq 0. \end{matrix}

（5）

它被称为<年代p一个ncl一个年代年代＝"emphasis">原始的问题:x由原始变量和年代由原始松弛变量组成。的<年代p一个ncl一个年代年代＝"emphasis">双问题是

马克斯 b^{T} y - u^{T} w 这样 ｛ \begin{matrix} {一个}^{T} \cdot y - w + z ＝ f \\ z \geq 0 ， w \geq 0 ， \end{matrix}

（6）

在哪里y和w由双变量和z由双休闲裤组成。的<一个cl一个年代年代＝"indexterm" name="d123e33210">这个线性规划的最优性条件，即原始<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式5和双<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式6,都是

\begin{array}{l} F （ x ， y ， z ， 年代 ， w ） ＝ （ \begin{matrix} 一个 \cdot x - b \\ x + 年代 - u \\ {一个}^{T} \cdot y - w + z - f \\ x_{我} z_{我} \\ {年代}_{我} w_{我} \end{matrix} ） ＝ 0 ， \\ x \geq 0 ， z \geq 0 ， 年代 \geq 0 ， w \geq 0 ， \end{array}

(7)

在哪里x<年代ub>我z<年代ub>我和年代<年代ub>我w<年代ub>我表示组件式乘法。

二次方程<年代p一个ncl一个年代年代＝"inlineequation">x<年代ub>我z<年代ub>我= 0和<年代p一个ncl一个年代年代＝"inlineequation">年代<年代ub>我w<年代ub>我= 0被称为“<年代p一个ncl一个年代年代＝"emphasis">互补性线性规划的条件;其他(线性)方程称为<一个cl一个年代年代＝"indexterm" name="d123e33269">可行性条件。数量

x<年代up>Tz+年代<年代up>Tw

是<年代p一个ncl一个年代年代＝"emphasis">二元性的差距的互补部分的残差F什么时候<年代p一个ncl一个年代年代＝"inlineequation">（x、 z，s，w)≥0．

算法是<年代p一个ncl一个年代年代＝"emphasis">非算法，即原始程序和对偶程序同时求解。它可以被认为是一种牛顿方法，应用于线性二次方程组<年代p一个ncl一个年代年代＝"inlineequation">F（x, y, z,年代,w) = 0在<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式7，同时保持迭代x，z，w,年代正的，因此命名内点方法。(迭代在严格的内部区域，由中的不等式约束表示<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式5．）

这个算法是<一个cl一个年代年代＝"indexterm" name="d123e33328">由Mehrotra提出的预测-校正算法。考虑一个迭代<年代p一个ncl一个年代年代＝"inlineequation">v= (x、 y；z；s；w］，在哪里<年代p一个ncl一个年代年代＝"inlineequation">［x, z,年代;w] > 0首先计算所谓的<年代p一个ncl一个年代年代＝"emphasis">预测方向

$Δ v_{p} ＝ - {（ F^{T} （ v ））}^{- 1} F （ v ），$

也就是牛顿方向;那么所谓的<年代p一个ncl一个年代年代＝"emphasis">校正器方向

$Δ v_{c} ＝ - {（ F^{T} （ v ））}^{- 1} F （ v + Δ v_{p} ） - μ \overset{＾}{e} ，$

在哪里<年代p一个ncl一个年代年代＝"inlineequation">μ> 0被称为<年代p一个ncl一个年代年代＝"emphasis">定心参数，必须谨慎选择。<年代p一个ncl一个年代年代＝"inlineequation"> $\overset{＾}{e}$ 是一个0-1向量，其中的向量对应于F（v)也就是说，扰动只适用于互补条件，它们都是二次的，而不适用于可行性条件，它们都是线性的。这两个方向与一个步长参数相结合<年代p一个ncl一个年代年代＝"inlineequation">α> 0和更新v获取新的迭代v⁺：

$v^{+} ＝ v + α （ Δ v_{p} + Δ v_{c} ），$

步长参数在哪里α是为了

v<年代up>+= (x<年代up>+；y<年代up>+；z<年代up>+；s<年代up>+；w<年代up>+］

满足

［x<年代up>+；z<年代up>+；s<年代up>+；w<年代up>+] > 0.

在求解上述预测/校正方向时，该算法对的Cholesky因子进行修正，计算一个(稀疏)直接分解<年代p一个ncl一个年代年代＝"inlineequation">一个?<年代up>T．如果一个有<一个cl一个年代年代＝"indexterm" name="d123e33441">密集列，它使用<一个cl一个年代年代＝"indexterm" name="d123e33444">谢尔曼·莫里森公式。如果该解不充分（残差太大），它将对阶跃方程的增广系统形式执行LDL分解以找到解。（见<一个href="//www.tianjin-qmedu.com/help/matlab/ref/ldl.html" class="a">例4 - D的结构在MATLAB<年代up>®低密度脂蛋白函数引用页面。)

算法然后循环，直到迭代收敛。主要的停止标准是:

$马克斯（ \frac{为 r_{b} 为}{马克斯（ 1 ，为 b 为）} ， \frac{为 r_{f} 为}{马克斯（ 1 ，为 f 为）} ， \frac{为 r_{u} 为}{马克斯（ 1 ，为 u 为）} ， \frac{| f^{T} x - b^{T} y + u^{T} w |}{马克斯（ 1 ， | f^{T} x | ， | b^{T} y - u^{T} w | ）} ） \leq t o l ，$

在哪里

$\begin{matrix} r_{b} ＝一个 x - b \\ r_{f} ＝ {一个}^{T} y - w + z - f \\ r_{u} ＝｛ x ｝ + 年代 - u \end{matrix}$

分别为原残差、对偶残差和上界可行性(<年代p一个ncl一个年代年代＝"inlineequation">｛x｝是指x有有限的上界)，以及

$f^{T} x - b^{T} y + u^{T} w$

原始目标值和二元目标值的区别，和<年代p一个ncl一个年代年代＝"emphasis">托尔是一些宽容。的总和<一个cl一个年代年代＝"indexterm" name="d123e33485">停止标准测量在最优条件中的总相对误差<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式7．

原始不可行性的衡量是<年代p一个ncl一个年代年代＝"inlineequation">||r<年代ub>b||，而双重不可行性的测度为<年代p一个ncl一个年代年代＝"inlineequation">||r<年代ub>f||这里的范数是欧几里得范数。

预处理

该算法首先试图通过去除冗余和简化约束来简化问题。在预解步骤中执行的任务包括:

检查是否有任何变量有相同的上界和下界。如果是，检查可行性，然后修复和删除变量。
检查任何线性不等式约束是否只涉及一个变量。如果是，请检查可行性，然后将线性约束更改为一个界。
检查任何线性等式约束是否只涉及一个变量。如果是，请检查可行性，然后修复并删除该变量。
检查任何线性约束矩阵是否有零行。如果是，检查是否可行，然后删除行。
确定边界和线性约束是否一致。
检查是否有变量只出现在目标函数的线性项中而不出现在任何线性约束中。如果是，检查可行性和有界性，然后将变量固定在适当的界限。
通过添加松弛变量，将线性不等式约束变为线性等式约束。

如果算法检测到一个不可行的或无界的问题，它会停止并发出适当的退出消息。

该算法可能会到达一个单一的可行点，这代表了解决方案。

为简单起见，该算法将所有下界都移到零。

而这些预处理步骤可以大大加快算法的迭代部分，如果<一个cl一个年代年代＝"indexterm" name="d123e33534">需要拉格朗日乘数，由于算法中计算的乘数是针对变换后的问题，而不是原始问题，所以必须撤消预处理步骤。因此，如果乘数是<年代p一个ncl一个年代年代＝"emphasis">不如果请求返回，则不会计算此转换，并可能在计算上节省一些时间。

对偶单纯形算法

在高水平上linprog“对偶单纯形”算法本质上是执行一个单纯形算法对偶问题．

该算法首先进行预处理，如<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理．详情请参见Andersen和Andersen<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［１］还有Nocedal和Wright<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［7］这种预处理将原来的线性规划问题简化为<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式4：

$\underset{x}{最小值} f^{T} x 这样｛ \begin{matrix} 一个 \cdot x ＝ b \\ 0 \leq x \leq u ． \end{matrix}$

一个和b是原始约束矩阵的变换版本。这是最基本的问题。

最初的可行性可以定义为<年代up>+函数

$x^{+} ＝｛ \begin{array}{l} x & 如果 x > 0 \\ 0 & 如果 x \leq 0. \end{array}$

原始不可行性的衡量是

$原始的不可行性＝ \sqrt{{（ {（磅 - x ）}^{+} ）}^{2} + {（ {（ x - 乌兰巴托）}^{+} ）}^{2} + {（ {（一个 x - b ）}^{+} ）}^{2} + {| Aeq x - 说真的 |}^{2}} ．$

如中所述<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程式6在美国，对偶问题是求向量y和w，和松弛变量向量z解决

$马克斯 b^{T} y - u^{T} w 这样｛ \begin{matrix} {一个}^{T} \cdot y - w + z ＝ f \\ z \geq 0 ， w \geq 0. \end{matrix}$

双重不可行性的度量是

$双不可行性＝ {为 {一个}^{T} y + z - w - f 为}_{2} ．$

这是众所周知的(例如，见<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［7］)，对偶问题的任何有限解都给出原问题的解，原问题的任何有限解都给出对偶问题的解。此外，如果原始问题或对偶问题中的一个是无界的，那么另一个问题是不可行的。如果原始问题或对偶问题中有一个是不可行的，那么另一个问题要么是不可行的，要么是无界的。因此，这两个问题在获得有限解(如果存在)方面是等价的。由于原始问题和对偶问题在数学上是等价的，但计算步骤不同，因此通过对偶问题的求解可以更好地解决原始问题。

帮助缓解退化（参见Nocedal和Wright<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［7］(第366页)，对偶单纯形算法首先扰动目标函数。

对偶单纯形算法的第1阶段是寻找对偶可行点。该算法通过求解一个辅助线性规划问题来实现这一点。

第一阶段大纲

在第1阶段，算法找到一个初始的基本可行解(见<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">基本和非基本变量通过求解一个辅助的分段线性规划问题。辅助问题的目标函数为<年代p一个ncl一个年代年代＝"emphasis">线性罚函数 $P ＝ \sum_{j} P_{j} （ x_{j} ）$ ，

在哪里P<年代ub>j（x<年代ub>j)定义为

$P_{j} （ x_{j} ）＝｛ \begin{array}{l} x_{j} - u_{j} & 如果 x_{j} > u_{j} \\ 0 & 如果 l_{j} \leq x_{j} \leq u_{j} \\ l_{j} - x_{j} & 如果 l_{j} > x_{j} ． \end{array}$

P（x)衡量多少一个点x违背了上下限条件。辅助问题是

$\underset{x}{最小值} \sum_{j} P_{j} 受｛ \begin{matrix} 一个 \cdot x \leq b \\ 一个 e 问 \cdot x ＝ b e 问． \end{matrix}$

当且仅当辅助问题的最小值为0时，原问题有一个可行基点。

该算法通过启发式方法为辅助问题找到初始点，并在必要时添加松弛和人工变量。然后利用这个初始点和单纯形算法来解决辅助问题。该解是主算法第二阶段的初始点。

在阶段2中，求解器重复选择一个进入变量和一个离开变量。算法根据Forrest和Goldfarb提出的技术选择离开变量<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［3］称为双最陡边定价。该算法利用Koberstein提出的Harris比率变异检验来选择进入变量<一个href="//www.tianjin-qmedu.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">［5］．为了帮助缓解退化，该算法可以在阶段2引入额外的扰动。

第二阶段概述

求解器迭代，试图在降低原不可行性的同时保持对偶可行性，直到简化的扰动问题的解既是原可行的，也是对偶可行的。该算法解开了它所引入的扰动。如果扰动问题的解对未扰动问题是对偶不可行的，则求解器使用原始单纯形或阶段1算法恢复对偶可行性。最后，求解器展开预处理步骤，将解返回到原始问题。

基本和非基本变量

本节定义了术语<年代p一个ncl一个年代年代＝"emphasis">基础，<年代p一个ncl一个年代年代＝"emphasis">nonbasis,<年代p一个ncl一个年代年代＝"emphasis">基本可行解万博尤文图斯一个线性规划问题。该定义假定问题以下列标准形式给出:

$\underset{x}{最小值} f^{T} x 这样｛ \begin{matrix} 一个 \cdot x ＝ b ， \\ l b \leq x \leq u b ． \end{matrix}$

(注意,一个和b不是矩阵和向量定义了原始问题中的不等式吗?)假设一个是一个米-借-n矩阵的秩<年代p一个ncl一个年代年代＝"inlineequation">米<n，其列为{一个₁，一个₂、……一个<年代ub>n}。假设<年代p一个ncl一个年代年代＝"inlineequation"> $｛ {一个}_{我_{1}} ， {一个}_{我_{2}} ， .．. ， {一个}_{我_{米}} ｝$ 列空间的基是一个，带索引集B= {我₁，我₂、……我<年代ub>米},N={1, 2，…n} \B是的补充B．的子矩阵一个_B被称为<年代p一个ncl一个年代年代＝"emphasis">基础和余子矩阵一个_N被称为<年代p一个ncl一个年代年代＝"emphasis">nonbasis．的向量<年代p一个ncl一个年代年代＝"emphasis">基本变量是x_B向量<年代p一个ncl一个年代年代＝"emphasis">非基本变量是x_N．在第2阶段的每次迭代中，算法将当前基的一列替换为非基的一列，并更新变量x_B和x_N相应的行动。

如果x是解决方案<年代p一个ncl一个年代年代＝"inlineequation">·x＝b以及所有的非基本变量x_N等于它们的上界或下界，x被称为<年代p一个ncl一个年代年代＝"emphasis">基本的解决方案．如果，另外，基本变量x_B满足上界和下界，所以x是一个可行的点,，x被称为<年代p一个ncl一个年代年代＝"emphasis">基本可行解．

参考文献

安徒生，E. D.和K. D.安徒生。线性规划中的预解．数学。编程71,1995，第221-245页。

[2] 阿普盖特，D.L.，R.E.比克斯比，V.Chvátal和W.J.库克，旅行推销员问题:一个计算研究，普林斯顿大学出版社，2007。

Forrest, J. J.和D. Goldfarb。线性规划的最陡边单纯形算法．数学。编程57,1992，第341-374页。

[4] Gondzio, J. <线性规划的原始对偶方法中的多重中心性校正>计算优化与应用， 1996年第6卷第2期，第137-156页。可以在<一个href="https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps" target="_blank">https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps．

[5] Koberstein,。求解大规模线性规划问题的对偶单纯形算法进展：快速稳定实现技术. 计算优化。和申请412008，第185-204页。

[6] 关于原始-对偶内点法的实现暹罗优化杂志， 1992年第2卷，第575-601页。

Nocedal, J.和S. J. Wright。数值优化,第二版。施普林格运筹学系列，斯普林格出版社，2006。