선형계획법알고리즘- MATLAB和Simul金宝appink MathWorks한국 - 金宝app,下载188bet金宝搏,金宝搏官方网站

선형계획법알고리즘

선형계획법정의

선형계획법은다음과같이선형제약조건이적용된선형함수f^Tx를최소화하는벡터x를구하는문제입니다。

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

다음중하나이상이성립해야합니다。

A·x≤b
Aeq·x =说真的
L≤x≤u。

`linprog`의行内点알고리즘

linprog의“内点”알고리즘은quadprog의interior-point-convex알고리즘과아주유사합니다。이알고리즘은linprog의“interior-point-legacy”알고리즘과도많은특성을공유합니다。이러한알고리즘은다음과같이동일한특징을가집니다。

풀이전처리。이는문제를단순화하고표준형식으로변환하는과정을의미합니다。
초기점생성。초기점선택은行内点알고리즘을효율적으로푸는데특히중요하며,이단계에서시간이많이걸릴수있습니다。
马방정식을풀기위한예측자-수정자반복。이단계는일반적으로시간이가장많이걸립니다。

풀이전처리

이알고리즘은먼저중복항목을제거하고제약조건을단순화함으로써문제를단순화하려고합니다。풀이전처리단계중수행되는작업에는다음이포함될수있습니다。

상한과하한이동일한변수가있는지확인합니다。그럴경우,실현가능성을검사한후변수를수정하고제거합니다。
하나의변수만포함하는선형부등식제약조건이있는지확인합니다。그럴경우,실현가능성을검사한다음선형제약조건을범위로변경합니다。
하나의변수만포함하는선형등식제약조건이있는지확인합니다。그럴경우,실현가능성을검사한후변수를수정하고제거합니다。
0으로이루어진행을갖는선형제약조건행렬이있는지확인합니다。그럴경우,실현가능성을검사한다음행을삭제합니다。
범위와선형제약조건이일치하는지확인합니다。
목적함수의일차항으로만표시되고선형제약조건에는표시되지않는변수가있는지확인합니다。그럴경우,실현가능성과유계성(有界性)을검사한다음적합한범위에서변수를수정합니다。
여유변수를추가하여선형부등식제약조건을선형등식제약조건으로변경합니다。

알고리즘이실현불가능문제또는비유계문제를감지하면실행이중단되고적절한종료메시지를표시합니다。

알고리즘은해를나타내는하나의실현가능점에도달할수있습니다。

알고리즘이풀이전처리단계에서실현불가능문제또는비유계문제를감지하지않고풀이전처리에서해를생성하지않는경우알고리즘은다음단계로계속진행합니다。중지기준에도달하면알고리즘은풀이전처리에서의변환을실행취소하여원래문제를다시생성합니다。이최종단계를풀이후처리단계라고합니다。

문제를단순화하기위해,풀이전처리단계에서문제를풀지못한경우이알고리즘은모든유한하한을0으로이동시킵니다。

초기점생성하기

초기점x0을설정하기위해이알고리즘은다음을수행합니다。

x0을的(n, 1)로초기화합니다。여기서nf은목적함수벡터의요소개수입니다。
0을하한으로갖도록모든유계성분을변환합니다。성분我가유한상한u(我)를가질경우x0 (i) = u / 2입니다。
한쪽경계만있는성분의경우,명확하게그경계내에놓이도록성분을수정합니다(필요한경우)。
x0이중앙경로가까이놓이도록예측자-수정자스텝을한번실행한후,결과로생성되는위치변수와여유변수를범위내에제대로놓이도록수정합니다。중앙경로에대한자세한내용은노세달(Nocedal)과라이트(赖特)의문헌［7］397페이지를참조하십시오。

예측자-수정자

fmincon의内点알고리즘과유사하게内点알고리즘은카루쉬-쿤터커(马)조건이성립하는점을구하려고합니다。선형계획법문제에대한방정식을설명하기위해,전처리를거친다음과같은표준형식의선형계획법문제를살펴보겠습니다。

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

일단,모든변수가최소하나의유한경계를갖는다고가정하겠습니다。필요한경우성분을이동시키고부호를변환하여,이가정에서는모든x성분의하한이0이라고간주합니다。
$\bar{一个}$ 는선형부등식과선형등식모두를포함하는확장된선형행렬입니다。 $\bar{b}$ 는대응하는선형등식벡터입니다。 $\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알고리즘은반환된라그랑주승수에대해여기서다룬것과다른부호규칙을사용합니다。여기서는대부분의문헌에서사용하는것과동일한부호를사용합니다。λ를참조하십시오。

이알고리즘은먼저뉴턴——랩슨(牛顿)식에서스텝을예측한후수정자스텝을계산합니다。수정자는비선형상보성방정식年代_我z_我= 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_d——쌍대문제(双)잔차
r_p——원문제(原始)잔차
r_乌兰巴托- - - - - -상한잔차
r_vx- - - - - -하한상보성잔차
r_wt- - - - - -상한상보성잔차

반복과정표시에는다음수량이보고됩니다。

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

수식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의정의에서모든역행렬은대각행렬이기때문에계산하기가간단합니다。

수식1에서수식2를도출하기위해서는수식2의두번째행이수식1의두번째행렬행과같다는것을알고있어야합니다。수식2의첫번째행은Δv와Δw를구하기위해수식1의마지막두행을푼후Δt를구하는과정에서도출됩니다。

수식2는대칭이지만- d항으로인해양의정부호가아닙니다。따라서,촐레스키분해(柯列斯基分解)를사용하여풀수없습니다。몇단계를더거쳐양의정부호인다른부등식을생성한후,촐레스키분해를사용하여효율적으로풀수있습니다。

수식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)

일반적으로,뉴턴스텝을구하는가장효율적인방법은촐레스키분해를사용하여수식3을풀어Δy를구하는것입니다。Δy에곱한행렬은확실히대칭이고,퇴화(退化)가없는경우양의정부호이므로촐레스키분해가가능합니다。그후에뉴턴스텝을구하려면역대입하여Δx,Δt,Δv,Δw를구해야합니다。하지만, $\bar{一个}$ 에조밀한열이있는경우수식2를대신푸는것이더효율적일수있습니다。linprog의行内点알고리즘은열의밀도를기반으로하여해알고리즘을선택합니다。

알고리즘에대한자세한내용은메로트라(Mehrotra)의문헌［6］을참조하십시오。

수정된뉴턴스텝을계산한후,이알고리즘은더긴현재스텝을구하고더나은후속스텝을준비하기위해더많은계산을수행합니다。이러한여러수정계산은성능과견고성을모두향상시킬수있습니다。자세한내용은곤지오(Gondzio)의문헌［4］을참조하십시오。

예측자-수정자알고리즘은2차항을제외하고는비희소quadprog“interior-point-convex”버전과대체로같습니다。비희소예측자-수정자항목을참조하십시오。

중지조건

예측자-수정자알고리즘은실현가능점(허용오차내에서제약조건을충족함)에도달할때까지반복하며,여기서반복스텝의상대적크기는작습니다。구체적으로,다음과같이정의합니다。

$ρ ＝马克斯（ 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_c는기본적으로해에서각각0으로구성된벡터인상보성잔차十五와tw의크기를측정합니다。

Interior-Point-Legacy선형계획법

소개

interior-point-legacy방법은메로트라(Mehrotra)의예측자-수정자알고리즘([47])의변형인 원문제——쌍대문제(非)内点방법에해당하는LIPSOL ([52])을기반으로합니다。

주알고리즘

이알고리즘은먼저일련의전처리단계를적용합니다(전처리참조)。전처리후문제의형식은다음과같습니다。

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

(4）

상한제약조건이제약조건행렬一에암묵적으로포함되어있습니다。원문제여유변s수를추가하면수식4가다음과같이됩니다。

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

(5）

이를원문제라고합니다。x는원문제변수로구성되는고年代원문제여유변수로구성됩니다。쌍대문제는다음과같습니다。

马克斯 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쌍대여유변수로구성됩니다。이선형계획(즉원문제수식5및쌍대문제수식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_我z_我와年代_我w_我는성분별곱셈을나타냅니다。

2차방정식x_我z_我= 0및年代_我w_我= 0은선형계획에대한상보성조건이라고하고,다른(선형)방정식은실현가능성조건이라고합니다。다음수량은

x^Tz + s^Tw

쌍대격차이며,이는(x, z s w)≥0F의인경우상보성부분의잔차를측정합니다。

이알고리즘은원문제——쌍대문제알고리즘이며,이는원문제계획과쌍대문제계획을모두동시에푼다는것을의미합니다。이는뉴턴의방법과유사한것으로간주될수있으며,수식72차에서선형시스템F (x, y, z s w) = 0에적용될수있지만이와동시에반복요소x, z, w s를양수로유지하므로行内点방법이라고합니다。이반복요소들은수식5의부등식제약조건으로나타낸엄격한내부영역에있습니다。

이알고리즘은메로트라가제안한예측자-수정자알고리즘의변형입니다。반복v = [x, y, z,年代;w)를살펴보겠습니다。여기서[x, z,年代;w] > 0입니다。먼저,다음과같이예측방향을계산합니다。

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

이는뉴턴방향입니다。그런다음다음과같이수정자방향을계산합니다。

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

여기서μ> 0은중심화파라미터라고하며신중하게선택해야합니다。 $\overset{＾}{e}$ 2는F (v)에서차방정식에대응하는1을갖는0 - 1벡터입니다。즉,섭동은모두2차인상보성조건에만적용되며모두선형인실현가능성조건에는적용되지않습니다。이두방향을스텝길이파라미터α> 0에결합하고새반복v⁺를구하도록다음과같이v를업데이트합니다。

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

여기서스텝길이파라미터α는다음이

v⁺= [x⁺y;⁺z;⁺,⁺w;⁺］

다음을충족하도록선택됩니다。

[x⁺z;⁺,⁺w;⁺) > 0。

앞에서설명한예측자/수정자방향에대한풀이과정에서이알고리즘은一个?^T의촐레스키인수를수정할때(희소)직접분해를계산합니다。一个에조밀한열이있는경우셔먼——모리슨(Sherman-Morrison)식을대신사용합니다。해가적합하지않으면(잔차가너무큼)확장된시스템형식의스텝방정식에대해LDL분해를수행하여해를구합니다。MATLAB^®低密度脂蛋白함수도움말페이지의예제의4 - D구조를참조하십시오。

그런다음반복이수렴할때까지루프를실행합니다。주요중지기준은다음과같은표준조건입니다。

$马克斯（ \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}$

이는각각원문제잔차,쌍대문제잔차,상한실현가능성이며({x}는유한상한이있는x를의미함)다음은

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

원문제목적함수값과쌍대문제목적함수값사이의차이이고托尔은허용오차입니다。중지기준에있는합은수식7의최적성조건에서총상대오차를측정합니다。

원문제실현불가능성에대한측정값은| | r_b||이고,쌍대문제실현불가능성에대한측정값은| | r_f||입니다。여기서노름은유클리드노름입니다。

전처리

상한과하한이동일한변수가있는지확인합니다。그럴경우,실현가능성을검사한후변수를수정하고제거합니다。
하나의변수만포함하는선형부등식제약조건이있는지확인합니다。그럴경우,실현가능성을검사한다음선형제약조건을범위로변경합니다。
하나의변수만포함하는선형등식제약조건이있는지확인합니다。그럴경우,실현가능성을검사한후변수를수정하고제거합니다。
0으로이루어진행을갖는선형제약조건행렬이있는지확인합니다。그럴경우,실현가능성을검사한다음행을삭제합니다。
범위와선형제약조건이일치하는지확인합니다。
목적함수의일차항으로만표시되고선형제약조건에는표시되지않는변수가있는지확인합니다。그럴경우,실현가능성과유계성(有界性)을검사한다음적합한범위에서변수를수정합니다。
여유변수를추가하여선형부등식제약조건을선형등식제약조건으로변경합니다。

알고리즘이실현불가능문제또는비유계문제를감지하면실행이중단되고적절한종료메시지를표시합니다。

알고리즘은해를나타내는하나의실현가능점에도달할수있습니다。

문제를단순화하기위해알고리즘은모든하한을0으로이동시킵니다。

라그랑주승수가필요한경우이러한전처리단계는알고리즘에서반복되는부분의속도를높이는데크게기여할수있지만,알고리즘실행도중에계산되는승수는원래문제에대한것이아니라변환된문제에대한것이므로전처리단계의실행을취소해야합니다。따라서,승수가필요하지않은경우에는이러한역변환에대한계산과정이없으므로계산차원에서시간을일부절약할수있습니다。

对偶单纯形알고리즘

대략적으로설명하자면linprog의对偶单纯形的알고리즘은기본적으로(双)쌍대문제에대해단체알고리즘을수행합니다。

이알고리즘은먼저전처리에설명된대로전처리를수행합니다。자세한내용은앤더슨(安德森)과앤더슨(安德森)의문헌［1］및노세달(Nocedal)과라이트(赖特)의문헌［7］13장을참조하십시오。이전처리는다음과같이원래선형계획법문제를수식4형식으로줄여줍니다。

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

와b는원래제약조건행렬을변환한것입니다。이것이바로원문제(原始)입니다。

원문제실현가능성은다음과같이⁺함수로정의될수있습니다。

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

원문제실현불가능성의측정값은다음과같습니다。

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

수식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} ．$

쌍대문제에대한임의의유한해는원문제의해를제공하고원문제에대한임의의유한해는쌍대문제의해를제공하는것으로잘알려져있습니다(예를들어,［7］참조)。또한,원문제와쌍대문제중어느한쪽이비유계이면다른쪽문제는실현가능하지않습니다。그리고원문제와쌍대문제중어느한쪽이실현가능하지않으면다른쪽문제는실현가능하지않거나비유계입니다。따라서,유한해가존재할경우이를구한다는차원에서두문제는동일합니다。원문제와쌍대문제가수학적으로동일하지만계산단계는다르기때문에쌍대문제를풀어서원문제를푸는것이더나을수있습니다。

퇴화(退化)를완화시키는데도움이되도록(노세달(Nocedal)과라이트(赖特)의문헌［7］366페이지참조),쌍대문제단체알고리즘은먼저목적함수에섭동을적용합니다。

쌍대문제단체알고리즘의단계1은쌍대문제실현가능점을구하는것입니다。이알고리즘은보조선형계획법문제를풀어이를수행합니다。

단계1개요

단계1에서알고리즘은보조적인조각별선형계획법문제를풀어서실현가능한초기기저해(정의는기저변수와비기저변수참조)를구합니다。보조문제의목적함수는선형벌점함수 $P ＝ \sum_{j} P_{j} （ x_{j} ）$ 입니다。

여기서P_j(x_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에대한초기점입니다。

단계2에서솔버는진입변수와탈락변수를반복적으로선택합니다。알고리즘은쌍대최대경사면가격결정(双Steepest-Edge定价)이라고하는포레스트(Forrest)와골드파브(Goldfarb)가제안한기법［3］에따라탈락변수를선택합니다。진입변수는코버슈타인(Koberstein)［5］이제안한변형된해리스의비율판정법(哈里斯的比值判别法)을사용하여선택합니다。퇴화(退化)를완화하는데도움이되도록이알고리즘은단계2중에추가적인섭동을적용할수있습니다。

단계2개요

솔버는원문제실현불가능성을줄이는동시에쌍대문제실현가능성을유지하려고하면서,축소되고섭동된문제의해가원문제와쌍대문제둘모두에서실현가능해질때까지반복합니다。알고리즘은적용한섭동을취소합니다。(섭동된문제의)해가섭동되지않은(원래)문제에대해쌍대문제실현이불가능할경우솔버는원문제단체알고리즘이나단계1알고리즘을사용하여쌍대문제실현가능성을복원합니다。마지막으로,솔버는전처리단계를취소하여해를원래문제로되돌립니다。

기저변수와비기저변수

이섹션에서는선형계획법문제에서기저，비기저,그리고실현가능한기저해라는용어를정의합니다。이정의에서는문제가다음과같은표준형식으로지정되었다고가정합니다。

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

참고로와,b는원래문제에서부등식을정의하는데사용한행렬및벡터와는다릅니다。一个는열이{₁,一个₂， ...,一个_n}인랭크m < nm×n의행렬이라고간주합니다。 $｛ {一个}_{我_{1}} ， {一个}_{我_{2}} ，．.. ， {一个}_{我_{米}} ｝$ 은인덱스집합B ={我₁,我₂， ...,我_米}을갖는一의열공간에대한기저이고N ={1,2,…n} \ B는B의여집합이라고가정하겠습니다。부분행렬_B는기저라고하고상보부분행렬_N은비기저라고합니다。기저변수의벡터는x_B이고비기저변수의벡터는x_N입니다。단계2의각반복마다알고리즘은현재기저의한열을비기저의한열로대체하고이에따라변수x_B와x_N을업데이트합니다。

x가A·x =의해이고x_N의모든비기저변수가하한또는상한과같을경우x를기저해라고합니다。또한x_B의기저변수가하한과상한을충족하여x가실현가능점이되는경우x를실현가능한기저해라고합니다。

참고문헌

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

Applegate, D. L.， R. E. Bixby, V. Chvátal和W. J. Cook，旅行推销员问题:计算研究，普林斯顿大学出版社，2007。

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

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

解决大规模LP问题的对偶单纯形算法的进展:快速和稳定的实现技术。计算Optim。和应用程序41,2008,185-204页。

[6] Mehrotra, S.《关于原-对偶内点方法的实现》。优化学报，Vol. 2, 1992, pp . 575-601。

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