线性规划算法- MATLAB & Simulink - 卡塔尔世界杯8强比赛直播

线性规划算法

线性规划的定义

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

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

使下列一项或多项成立:

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

内点linprog算法

的linprog“内点”算法非常类似<一个href="//www.ru-cchi.com/help/optim/ug/quadratic-programming-algorithms.html" class="a">interior-point-convex quadprog算法．它也有许多与linprog“interior-point-legacy”算法。这些算法有相同的总体轮廓:

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

Presolve

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

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

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

算法可能会到达一个单一可行点，这个点代表解。

如果算法在求解步骤中没有检测到不可行的或无界问题，并且如果求解步骤没有产生解，则算法继续进行下一步。在达到停止条件后，算法重构原问题，撤销任何解变换。最后一步是后解步骤。

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

生成初始点

要设置起始点，x0，算法执行以下操作。

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

预估

类似于fmincon内点算法,内点算法试图找到一个点<一个href="//www.ru-cchi.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.ru-cchi.com/help/optim/ug/linprog.html">λ．

该算法首先根据Newton-Raphson公式预测步长，然后计算校正步长。该校正器试图减小非线性互补方程中的残差<年代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.ru-cchi.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.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2从<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1，注意第二行<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2是否与矩阵的第二行相同<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1．第一行<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2来自于解的最后两行<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1对于Δv和Δw，然后求解Δt．

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

第二组行<一个href="//www.ru-cchi.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.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程3对于Δy使用柯列斯基分解。Cholesky分解是可能的，因为矩阵乘以Δy显然是对称的，在没有简并的情况下，是正定的。之后，找牛顿步，回代找Δx,Δt,Δv,Δw．然而,当<年代p一个ncl一个年代年代＝"inlineequation"> $\bar{一个}$ 有了密集的柱，是否能更有效地解决<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2代替。的linprog内点算法根据列的密度选择求解算法。

更多算法细节，参见Mehrotra<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[6]．

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

预测-校正算法与完整的算法大致相同quadprog“interior-point-convex”版本，除了二次项。看到<一个href="//www.ru-cchi.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 ρ TolCon \\ {‖ r_{d} ‖}_{\infty} \leq ρ TolFun \\ r_{c} \leq TolFun, \end{matrix}$

在哪里

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

r<年代ub>c实质上是衡量互补残差的大小十五而且太瓦，它们都是解处的零向量。

Interior-Point-Legacy线性规划

简介

内部点遗留方法是基于<一个cl一个年代年代＝"indexterm" name="d124e34915">LIPSOL (<一个href="//www.ru-cchi.com/help/optim/ug/selected-bibliography.html" class="a">[52])的变体<一个cl一个年代年代＝"indexterm" name="d124e34920">Mehrotra预测-校正算法(<一个href="//www.ru-cchi.com/help/optim/ug/selected-bibliography.html" class="a">[47]),一个<一个cl一个年代年代＝"indexterm" name="d124e34925">内点方法。

主要算法

该算法首先应用一系列的<一个cl一个年代年代＝"indexterm" name="d124e34934">预处理步骤(见<一个href="//www.ru-cchi.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.ru-cchi.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="d124e34982">该线性规划的最优性条件，即原始<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程5和双<一个href="//www.ru-cchi.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="d124e35041">可行性条件。的数量

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

是<年代p一个ncl一个年代年代＝"emphasis">二元性的差距的互补部分的残差F当<年代p一个ncl一个年代年代＝"inlineequation">（x, z,年代,w)≥0．

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

该算法是<一个cl一个年代年代＝"indexterm" name="d124e35100">Mehrotra提出的预测校正算法。考虑一个迭代<年代p一个ncl一个年代年代＝"inlineequation">v= (x, y, z,年代;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>+,<年代up>+w;<年代up>+］

满足

［x<年代up>+z;<年代up>+,<年代up>+w;<年代up>+) > 0。

在求解前面的预测器/校正器方向时，算法在的Cholesky因子的修改上计算一个(稀疏的)直接因子分解<年代p一个ncl一个年代年代＝"inlineequation">一个?<年代up>T．如果一个有<一个cl一个年代年代＝"indexterm" name="d124e35213">密集的列，它反而使用<一个cl一个年代年代＝"indexterm" name="d124e35216">Sherman-Morrison公式。如果该解是不充分的(残差太大)，它将对步骤方程的增广系统形式执行LDL分解以找到解。(见<一个href="//www.ru-cchi.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="d124e35257">停止准则测量在最优条件下的总相对误差<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程7．

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

预处理

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

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

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

算法可能会到达一个单一可行点，这个点代表解。

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

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

对偶单纯形算法

在较高的水平上linprog对偶单纯形的算法本质上执行了一个单纯形算法对偶问题．

算法首先进行预处理，如<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理．详情请参见安徒生<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[1]Nocedal和Wright<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]第13章。这种预处理将原来的线性规划问题简化为<一个href="//www.ru-cchi.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.ru-cchi.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.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7])对偶问题的任何有限解都是原问题的一个解，原问题的任何有限解都是对偶问题的一个解。此外，如果原问题或对偶问题中有一个是无界的，那么另一个问题也是不可行的。如果原问题或对偶问题中有一个不可行，那么另一个问题要么不可行，要么无界。因此，如果存在有限解，这两个问题在获得有限解方面是等价的。由于原问题和对偶问题在数学上是等价的，但计算步骤不同，因此通过求解对偶问题可以更好地解决原问题。

为了帮助减轻退化(参见Nocedal和Wright<一个href="//www.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]，第366页)，对偶单纯形算法从扰动目标函数开始。

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

第一阶段概述

在第1阶段，算法找到一个初始的基本可行解(见<一个href="//www.ru-cchi.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.ru-cchi.com/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[3]称为双最陡边缘定价。该算法利用Koberstein提出的Harris比值检验的变异来选择输入变量<一个href="//www.ru-cchi.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年。

[3]福雷斯特，J. J.和D.戈德法布。线性规划的最陡边单纯形算法．数学。编程57,1992，第341-374页。

[4] Gondzio J. "线性规划的原对偶方法中的多重中心性修正"。计算优化及其应用， 1996年第2期，第6卷，第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,。求解大规模LP问题的对偶单纯形算法进展:快速稳定的实现技术．计算Optim。应用41,2008，页185-204。

[6] Mehrotra, S. <关于原对偶内点法的实现>。SIAM优化期刊1992年，第2卷，第575-601页。

[7]诺西德尔，J.和S. J.赖特。数值优化,第二版。施普林格系列运筹学，Springer- verlag, 2006。