线性规划算法- MATLAB和Simulink MathWorks澳大利亚金宝app - 金宝app,下载188bet金宝搏,金宝搏官方网站

线性规划算法

线性规划的定义

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

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

这样的一个或多个以下控制:

·x≤b
Aeq·x=说真的
l≤x≤u。

内点linprog算法

的linprog“内点”算法非常相似<一个href="//www.tatmou.com/au/au/help/optim/ug/quadratic-programming-algorithms.html" class="a">interior-point-convex quadprog算法。它也有许多共同特征linprog“interior-point-legacy”算法。这些算法具有相同的概要:

Presolve,意思是简化和转换问题的标准形式。
生成一个初始点。一个初始点的选择尤其重要解决内点算法有效,这一步可以耗时。
预估解决马方程迭代。这一步通常是最耗时的。

Presolve

该算法首先尝试通过删除冗余和简化约束简化问题。presolve阶段中执行的任务可以包括以下:

检查如果任何变量有上界和下界。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性不等式约束只涉及一个变量。如果是这样的话,检查的可行性,然后改变线性约束绑定。
检查任何线性等式约束包括只有一个变量。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性约束矩阵为零行。如果是这样的话,检查的可行性,然后删除行。
确定范围和线性约束是一致的。
检查任何变量只出现在目标函数为线性的条件并没有出现在任何线性约束。如果是这样的话,检查可行性和有界性,然后固定在适当的范围的变量。
改变任何线性不等式约束线性等式约束通过增加松弛变量。

如果算法检测到一个不可行或无限问题,停止和一个适当的出口问题的消息。

算法可能到达一个可行点,代表了解决方案。

如果算法没有检测到一个不可行或无限问题在presolve步骤中,如果presolve还没有产生解决方案,该算法继续下一个步骤。达到停止条件后,该算法重建原始问题,取消任何presolve转换。这最后一步是postsolve一步。

为简单起见,如果这个问题不解决presolve步骤,算法转移所有有限的下界为零。

生成初始点

设置起始点,x0,该算法如下。

初始化x0来的(n, 1),在那里n是目标函数向量的元素的数量吗f。
转换所有的组件有一个下界的0。如果组件我有一个有限的上限u(我),然后x0 (i) = u / 2。
对于只有一个绑定的组件,必要时修改组件严格躺在里面的束缚。
把x0靠近中央路径,需要一个预估的步骤,然后修改产生的位置和松弛变量躺在任何范围内。中央路径的详细信息,请参见Nocedal和赖特<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7],397页。

预估

类似于fmincon内点算法,内点算法试图找到一个地方<一个href="//www.tatmou.com/au/au/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) 。$

因此,这个系统的马条件

$\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.tatmou.com/au/au/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.tatmou.com/au/au/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.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2从<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1第二排的,请注意<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2是一样的第二个矩阵的行吗<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1。第一行的<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2来自于解决的最后两行<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1对于Δv和ΔwΔ,然后解决t。

方程2是对称的,但它不是正定的-D术语。因此,您不能使用柯列斯基分解解决它。再走几步导致不同的方程是正定的,因此可以有效地解决了柯列斯基分解。

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

更多的算法细节,看到Mehrotra<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[6]。

计算修正牛顿一步后,算法执行更多的计算得到当前步骤较长,和准备更好的后续步骤。这些多个校正计算可以提高性能和鲁棒性。详情,请参阅Gondzio<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[4]。

预估算法在很大程度上是一样的quadprog“interior-point-convex”版本,除了二次项。看到<一个href="//www.tatmou.com/au/au/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线性规划

介绍

interior-point-legacy方法是基于<一个cl一个年代年代="indexterm" name="d123e34759">LIPSOL (<一个href="//www.tatmou.com/au/au/help/optim/ug/selected-bibliography.html" class="a">[52]),这是一个变体<一个cl一个年代年代="indexterm" name="d123e34764">Mehrotra预估的算法(<一个href="//www.tatmou.com/au/au/help/optim/ug/selected-bibliography.html" class="a">[47]),一个<一个cl一个年代年代="indexterm" name="d123e34769">内点方法。

主要算法

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

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

是<年代p一个ncl一个年代年代="emphasis">二元性的差距衡量互补的剩余部分F当<年代p一个ncl一个年代年代="inlineequation">(x, z,年代,w)≥0。

该算法是一个<年代p一个ncl一个年代年代="emphasis">非算法,这意味着原始和双程序同时得到解决。它可以被视为一个Newton-like方法,应用线性二次系统<年代p一个ncl一个年代年代="inlineequation">F(x, y, z,年代,w)= 0在<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程7,同时保持迭代x,z,w,年代积极的,因此内点法的名称。严格的内部地区(迭代所代表的不等式约束<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程5。)

该算法的一种变体<一个cl一个年代年代="indexterm" name="d123e34944">预估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}) - μ \hat{e},$

在哪里<年代p一个ncl一个年代年代="inlineequation">μ> 0被称为<年代p一个ncl一个年代年代="emphasis">定心参数,必须仔细选择。<年代p一个ncl一个年代年代="inlineequation"> $\hat{e}$ 是一个0 - 1向量与相应的二次方程F(v),即。,perturb一个t我on年代一个re only applied to the complementarity conditions, which are all quadratic, but not to the feasibility conditions, which are all linear. The two directions are combined with a step length parameter<年代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。

在解决前预测/校正方向,算法计算(稀疏)直接修改的柯列斯基因素分解<年代p一个ncl一个年代年代="inlineequation">一个?<年代up>T。如果一个有<一个cl一个年代年代="indexterm" name="d123e35057">密集的列,而不是使用<一个cl一个年代年代="indexterm" name="d123e35060">Sherman-Morrison公式。如果这个解决方案是不够的(剩余太大),它执行一个低密度脂蛋白分解一个增广系统的方程形式的一步找到解决办法。(见<一个href="//www.tatmou.com/au/au/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="d123e35101">停止标准措施的总相对误差最优性条件<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程7。

预处理

该算法首先尝试通过删除冗余和简化约束简化问题。presolve阶段中执行的任务可以包括以下:

检查如果任何变量有上界和下界。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性不等式约束只涉及一个变量。如果是这样的话,检查的可行性,然后改变线性约束绑定。
检查任何线性等式约束包括只有一个变量。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性约束矩阵为零行。如果是这样的话,检查的可行性,然后删除行。
确定范围和线性约束是一致的。
检查任何变量只出现在目标函数为线性的条件并没有出现在任何线性约束。如果是这样的话,检查可行性和有界性,然后固定在适当的范围的变量。
改变任何线性不等式约束线性等式约束通过增加松弛变量。

如果算法检测到一个不可行或无限问题,停止和一个适当的出口问题的消息。

算法可能到达一个可行点,代表了解决方案。

为了简单起见,该算法转移所有下界为零。

虽然这些预处理步骤可以做得加快迭代算法的一部分,如果<一个cl一个年代年代="indexterm" name="d123e35150">拉格朗日乘数法,预处理步骤必须消除由于乘数计算算法为转换后的问题,而不是原始的。因此,如果乘数<年代p一个ncl一个年代年代="emphasis">不要求,这种转变不是计算,可能会节省一些时间计算。

对偶单纯形算法

在高级别上,linprog对偶单纯形的算法本质上执行一个单纯形算法对偶问题。

该算法首先预处理中描述<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理。,安德森,安德森<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[1]和Nocedal莱特<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]第13章。这种预处理降低了原始形式的线性规划问题<一个href="//www.tatmou.com/au/au/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.tatmou.com/au/au/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.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]),任何有限的对偶问题的解决方案给原始问题的解,以及任何有限解决原始问题给出了对偶问题的解决方案。此外,如果原始或对偶问题是无界的,然后另一个问题是不可行的。如果原始或对偶问题是不可行的,那么另一个问题是不可行或无限。因此,这两个问题是等价的获得有限的解决方案,如果一个人的存在。因为原始和对偶问题在数学上是等价的,但计算的步骤不同,它可以更好地解决原始问题的对偶问题的解决。

帮助缓解退化(见Nocedal和赖特<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7],366页),首先扰动目标函数对偶单纯形算法。

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

第一阶段概述

在阶段1中,该算法找到一个初始基本可行解(见<一个href="//www.tatmou.com/au/au/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。

算法找到一个初始点辅助问题的启发式方法,必要时增加松弛和人工变量。然后算法一起使用这个初始点单纯形算法解决辅助问题。解决方案的初始点是第二阶段的主要算法。

在第二阶段,解决重复选择一个输入变量和一个变量。该算法选择离开变量根据福勒斯特技术建议和戈德法布<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[3]被称为双重steepest-edge定价。算法选择一个输入变量使用哈里斯的比率的变化由Koberstein测试建议<一个href="//www.tatmou.com/au/au/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[5]。为了帮助缓解退化,算法可以在第二阶段引入额外的扰动。

第二阶段概述

迭代的求解程序,试图保持双重可行性,同时减少原始的不可行性,直到解决减少,摄动问题是原始可行和对偶可行。该算法展开的扰动。如果解决方案(摄动问题)是双非微扰(原始)问题不可行,那么解决恢复双重使用原始单纯形或第一阶段算法的可行性。最后,解算器打开预处理步骤回到最初的问题的解决方案。

基本和非基本变量

本节定义了条件<年代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中,该算法替换当前基础的一列一列的nonbasis并更新变量x_B和x_N相应的行动。

如果x是一个解决方案<年代p一个ncl一个年代年代="inlineequation">·x=b和所有的非基本变量x_N等于其较低或上界,x被称为<年代p一个ncl一个年代年代="emphasis">基本的解决方案。此外,如果基本变量x_B满足他们的上下边界,所以x是一个可行的点,x被称为<年代p一个ncl一个年代年代="emphasis">基本可行解。

引用

[1]安徒生,e D。,K. D. Andersen.Presolving在线性规划。数学。编程71年,1995年,页221 - 245。

[2]阿普尔盖特,d . L。,R。E. Bixby, V. Chvátal and W. J. Cook,旅行商问题:计算研究》,普林斯顿大学出版社,2007年。

[3]福勒斯特,J·J。和d·戈德法布。Steepest-edge线性规划的单纯形算法。数学。编程57,1992年,页341 - 374。

[4]Gondzio, j .“多个中心修正原始对偶线性规划的方法。”计算优化和应用程序2号、卷6日,1996年,页137 - 156。可以在<一个href="https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps" target="_blank">https://www.maths.ed.ac.uk/ gondzio /软件/ correctors.ps。

[5]Koberstein,。进步对偶单纯形算法求解大规模LP问题:快速和稳定的技术实现。计算Optim。和应用41岁,2008年,页185 - 204。

[6]Mehrotra,美国“在一个非内点方法的实现。”暹罗杂志上优化,卷2,1992年,页575 - 601。

[7]Nocedal, J。,S. J. Wright.数值优化,第二版。施普林格系列在运筹学,斯普林格出版社,2006年版。