심플렉스 알고리즘

수학적 최적화에서 단치히의 심플렉스 알고리즘(또는 심플렉스법)은 선형 프로그래밍에 널리 쓰이는 알고리즘이다.^[1]

알고리즘의 이름은 심플렉스(simplex)의 개념에서 따온 것으로 T. S. Motzkin이 제안했다.^[2] 단순화는 실제로 방법에는 사용되지 않지만, 단순화된 원뿔에 의해 작동하며, 이는 추가적인 제약이 있는 적절한 단순화가 된다는 것이 하나의 해석이다.^[3][4][5][6] 문제의 간단한 원뿔은 폴리토프라고 불리는 기하학적 물체의 모서리(즉, 정점 부근)이다. 이 폴리토프의 모양은 객관적 기능에 적용되는 제약조건에 의해 정의된다.

역사

조지 단치히는 제2차 세계 대전 동안 책상 계산기를 사용하여 미 육군 공군의 계획 방법을 연구했다. 1946년 동안 그의 동료는 그가 다른 직업을 갖는 것을 방해하기 위해 계획 과정을 기계화해야 한다고 그에게 도전했다. 단치히는 이 문제를 와실리 레온티프의 작품에서 영감을 받은 선형 불평등이라고 공식화했지만, 당시 그는 자신의 공식화의 일부로서 목적을 포함하지 않았다. 목적이 없으면 방대한 해법이 실현 가능하기 때문에, 「최상의」 실현 가능한 해답을 찾기 위해서는, 목표 자체를 특정하는 것이 아니라, 목표를 달성할 수 있는 방법을 기술하는 군에서 정한 「지상 규칙」을 사용해야 한다. 단치히의 핵심 통찰은 그러한 지상 규칙 대부분이 최대화가 필요한 선형 목표 함수로 번역될 수 있다는 것을 깨닫는 것이었다.^[7] 심플렉스 방식의 개발은 진화적이었고 약 1년에 걸쳐 이루어졌다.^[8]

단치히가 1947년 중반에 그의 공식화의 일부로 객관적인 기능을 포함시킨 후, 문제는 수학적으로 더 다루기 쉬웠다. 단치히는 제르지 네이먼 교수의 수업에서 숙제로 오인(그리고 나중에 실제로 해결된) 미해결 문제들 중 하나가 선형 프로그램을 위한 알고리즘을 찾는 데 적용된다는 것을 깨달았다. 이 문제에는 변수 0과 1 사이에 각각 경계인 일반 선형 프로그램에 대한 라그랑주 승수의 존재와 르베그 통합의 형태로 표현된 선형 제약 조건을 만족시키는 것이 포함되었다. 단치히는 이후 박사학위를 따기 위한 논문으로 '숙제'를 발표했다. 본 논문에서 사용된 칼럼 기하학은 단치히에게 Simplex 방법이 매우 효율적일 것이라고 믿게 하는 통찰력을 주었다.^[9]

개요

심플렉스 알고리즘은 표준 형태의 선형 프로그램에서 작동한다.

${C\mathbf{}}^{}$ ${}^{}\mathbf{}$ ${\$$T} \mathbf {x} }$

$A{\displaystyle }$ ${\displaystyle x\mathbf{}}$ ${\displaystyle \le }$ ${\displaystyle b\mathbf{}}$ ${\$ 및$$ $x{\displaystyle \mathbf{}}$ ${\displaystyle \ge }$ 0 ${\displaystyle \mathbf {x} \geq$ 0$}$의 적용 대상

with ${\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}$ the coefficients of the objective function, ${\displaystyle (\cdot )^{\mathrm {T} }}$ is the matrix transpose, and ${\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}$ are the variables 문제의 $A{\displaystyle }$ ${\displaystyle A}$은(는) p×n 행렬이며$$, $b{\displaystyle \mathbf{}}$= ${\displaystyle ({b\mathrm{}}_{}}$ 1,${\displaystyle }$…${\displaystyle }$, b ${\displaystyle p_{}}$) ${\displaystyle \mathbf {b} =(b_{1}}\,\dots,\,b_{$p$\}\}\}\}\}.$ 어떤 선형 프로그램이라도 표준 형태로 하나로 변환하는 간단한 과정이 있기 때문에, 이러한 형태의 선형 프로그램을 사용하면 일반성을 잃지 않게 된다.

In geometric terms, the feasible region defined by all values of ${\displaystyle \mathbf {x} }$ such that ${\textstyle A\mathbf {x} \leq \mathbf {b} }$ and ${\displaystyle \forall i,x_{i}\geq 0}$ is a (possibly unbounded) convex polytope. 이 폴리토프의 극한 지점 또는 정점은 기본 실현 가능한 해결책(BFS)으로 알려져 있다.

표준형식의 선형 프로그램의 경우, 목표함수가 실현 가능한 영역에 대해 최대값을 갖는 경우, 극단점 중 하나에 대해 (적어도) 이 값을 갖는다는 것을 보여줄 수 있다.^[10] 이것은 그 자체로 극한점이 한정되어 있기 때문에 문제를 유한한 계산으로 감소시키지만 극한점의 수는 가장 작은 선형 프로그램을 제외한 모든 경우에 감당할 수 없을 정도로 크다.^[11]

또한 극한 지점이 목표 함수의 최대 지점이 아닌 경우, 목표 함수의 값이 점으로부터 멀어지는 가장자리에서 엄격히 증가하도록 점을 포함하는 가장자리가 있음을 보여줄 수 있다.^[12] 가장자리가 유한하면 가장자리는 객관적 함수가 더 큰 값을 갖는 또 다른 극한점에 연결되고, 그렇지 않으면 목표 함수는 가장자리의 위쪽에 한이 없고 선형 프로그램에는 해결책이 없다. 심플렉스 알고리즘은 폴리토프의 가장자리를 따라 걸으면서 이러한 통찰력을 점점 더 큰 객관적 가치를 지닌 극한점에 적용한다. 이는 최대 값에 도달하거나 무한 에지를 방문할 때까지 계속된다(문제가 해결책이 없다는 것을 제외). 폴리토프의 정점 수는 한정되어 있기 때문에 알고리즘은 항상 종료된다. 더욱이 우리는 정점 사이를 항상 같은 방향(목표 함수의 정점)으로 점프하기 때문에 방문한 정점의 수가 적기를 바란다.^[12]

선형 프로그램의 해결은 두 단계로 이루어진다. 1단계로 알려진 첫 번째 단계에서는 시작 극점이 발견된다. 프로그램의 성격에 따라 이것은 사소한 것일 수도 있지만, 일반적으로는 원래의 프로그램의 변형된 버전에 심플렉스 알고리즘을 적용하면 해결할 수 있다. 1단계의 가능한 결과는 기본적인 실현 가능한 해결책이 발견되거나 실현 가능한 지역이 비어 있다는 것이다. 후자의 경우 선형 프로그램을 실행불능이라고 한다. 두 번째 단계인 2단계에서는 1단계에서 발견된 기본 실현 가능한 솔루션을 출발점으로 하여 심플렉스 알고리즘을 적용한다. 2단계에서 가능한 결과는 최적의 기본 실현 가능한 해결책 또는 목표 기능이 위에서 제한되지 않는 무한 에지 중 하나이다.^[13][14][15]

표준형식

선형 프로그램을 표준 형태로 1로 변환하는 작업은 다음과 같이 수행할 수 있다.^[16] 첫째, 0이 아닌 하한을 갖는 각 변수에 대해 변수와 바운드의 차이를 나타내는 새로운 변수가 도입된다. 그러면 원래의 변수는 대체에 의해 제거될 수 있다. 예를 들어, 제약 조건이 주어진 경우

${\displaystyle x_{1}\geq 5}$

새로운 변수 $y{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$$1$}가 도입됨

${\displaystyle {\regated}y_{1}=x_{1}-5\\\x_{1}=y_{1}+5\end}}}}$

두 번째 방정식을 사용하여 선형 $프로그램$에서 ${\displaystyle {x\mathrm{}}_{}}$ 1$${\$displaystyle x_{1$}을 제거할 수 있다. 이러한 방식으로 모든 하한 제약조건은 비부정성 제약조건으로 변경될 수 있다.

둘째, 남아 있는 각각의 불평등 제약조건에 대해, 제약조건을 평등 제약조건으로 바꾸기 위해 느슨한 변수라고 불리는 새로운 변수가 도입된다. 이 변수는 불평등 양면의 차이를 나타내며 비부정적이라고 가정한다. 예를 들어, 불평등들은

${\displaystyle {\displaysty}x_{2}+2x_{3}}}&\leq 3\\-x_{4}+3x_{5}}&\geq 2\end{aigned}}$

로 대체되다

${\displaystyle {\displaysty}x_{2}+2x_{3}+s_{1}}&=3\\-x_{4}+3x_{5}-s_{2}=2\\s_{1},\,s_{2}&\geq 0\end}}}}$

이런 형태의 불평등에 대해 대수적 조작을 하는 것이 훨씬 더 쉽다. 두 번째와 같이 ≥이 나타나는 불평등에서, 일부 저자들은 도입되는 변수를 잉여변수로 언급한다.

셋째, 제한되지 않은 각 변수는 선형 프로그램에서 제거된다. 이것은 두 가지 방법으로 할 수 있는데, 하나는 변수가 나타나는 방정식 중 하나에서 변수를 풀어서 대체하여 변수를 제거하는 것이다. 다른 하나는 변수를 두 개의 제한된 변수의 차이로 대체하는 것이다. 예를 들어 $z{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}가 제한되지$$ 않은 경우 쓰기

${\displaystyle {\required}&z_{1}=z_{1}^{+}-z_{1}^{-}\\\&z_{1}^{1}^{+}}\,z_}^{1}^{-}\geq 0\end{igned}}}}}}}}}}}}}$

이 방정식을 사용하여 ${\displaystyle {선형\mathrm{}}_{}}$ 프로그램에서$$z 1 {\$displaystyle$z_${1$}을$$ 제거할 수 있다.

이 과정이 완료되면 실현 가능한 지역은 다음과 같다.

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b},\\all i\ x_{i}\geq 0}$

$또한{\displaystyle \mathbf{}}$ A ${\$의 순위가 행의 수라고$$ 가정하는 것도 유용하다. 그렇지 않으면 시스템 $A{\displaystyle \mathbf{}}$ ${\displaystyle x\mathbf{}}$= b ${\$에 중복$$ 방정식이 있거나 시스템이 일관되지 않고 선형 프로그램에 해결 방법이 없으므로 일반성이 손실되지 않는다.^[17]

심플렉스 테이블라우

표준 형태의 선형 프로그램은 형식의 표로 나타낼 수 있다.

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&\0&\\mathbf {A} &\mathbf {b} \end{bmatrix}}}}}}$

첫 번째 행은 목표 함수를 정의하고 나머지 행은 제약조건을 지정한다. 첫 번째 열의 0은 벡터 b와 동일한 차원의 제로 벡터를 나타낸다(다른 저자는 정확한 레이아웃에 대해 서로 다른 규약을 사용한다). 순서 p의 ID 행렬(A의 행 수)을 포함하도록 A의 열을 재배열할 수 있다면, 테이블au는 표준형이라고 한다.^[18] ID 행렬의 열에 해당하는 변수를 기본 변수라고 하고, 나머지 변수를 비기본 변수 또는 자유 변수라고 한다. 비기본변수의 값을 0으로 설정하면 기본변수의 값을 b의 항목으로 쉽게 얻을 수 있으며, 이 해결책은 기본적인 실현 가능한 해결책이다. 여기서 대수적 해석은 각 행으로 대표되는 선형 방정식의 계수가 $0{\displaystyle \mathrm{}}$ ${\displaystyle 0$ $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$또는 일부 다른 숫자라는 것이다. 각 행에는 값 $1$이 있는 $1개$의 ${\displaystyle 1}$ 열$$$,$ $계수{\displaystyle }$ $0$이 있는 ${\displaystyle \mathrm{p}}$- 1 ${\displaystyle p-1}$ 열$$및$$ 일부 다른 계수가 있는 나머지 열(이 다른 변수는 우리의 비기본 변수를 나타낸다)이 있다. 비기본 변수의 값을 0으로 설정함으로써 각 행에서 해당 $열의$ 1 ${\displaystyle 1}$로 나타내는 변수의 값이 해당 $행$의 b$${\$displaystyle$b} 값과$$ 같음을 보장한다.

반대로, 실현 가능한 기본적인 해법이 주어진다면, 0이 아닌 변수에 해당하는 열을 비정렬 행렬로 확장할 수 있다. 해당 테이블au에 이 행렬의 역수를 곱하면 그 결과는 표준 형태의 테이블au가 된다.^[19]

내버려두다

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{D}^{{D}^{}}}}}}}T}&0\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}$

표준으로 되어 있다 추가 행 추가 변환을 적용하여 목표 함수에서 계수 cTB를
제거할 수 있다. 이 프로세스를 가격 책정이라고 하며 표준 테이블라우를 초래한다.

${\displaystyle {\begin{bmatrix}1&-{\bar {\mathbf{c}}}}}}{D}^{T}&z_{B}\0>I&\mathbf {D} &\mathbf {b} \end{bmatrix}}$

여기서 z는_B 해당 기본 실행 가능한 솔루션에서 목표 함수의 값이다. 업데이트된 계수는 상대 비용 계수로도 알려져 있으며, 비기본 변수에 대한 목표 함수의 변화율이다.^[14]

피벗 작업

기본 실행 가능한 솔루션에서 인접 기본 실행 가능한 솔루션으로 이동하는 기하학적 작동은 피벗 작동으로 구현된다. 첫째, 비기본 열에서 비제로 피벗 요소를 선택한다. 이 요소를 포함하는 행에 역수를 곱하여 이 요소를 1로 변경한 다음 행의 배수를 다른 행에 추가하여 열의 다른 항목을 0으로 변경한다. 그 결과 피벗 요소가 행 r에 있으면 열이 ID 매트릭스의 r번째 열이 된다. 이 열의 변수는 이제 기본 변수가 되어 작업 전 ID 매트릭스의 r번째 열에 해당하는 변수를 대체한다. 실제로 피벗 열에 해당하는 변수를 기본 변수 집합으로 입력하여 입력 변수라고 하며, 대체되는 변수를 기본 변수 집합에서 이탈하여 이탈 변수라고 한다. 테이블라우는 여전히 표준형이지만 한 요소에 의해 기본 변수 집합이 변경된다.^[13][14]

알고리즘.

표준 탁자에 의해 선형 프로그램이 제공되도록 하라. 심플렉스 알고리즘은 개선된 기본 실현 가능한 솔루션을 제공하는 연속적인 피벗 연산을 수행함으로써 진행된다. 각 단계에서 피벗 요소의 선택은 대체로 이 피벗이 솔루션을 개선해야 한다는 요건에 의해 결정된다.

변수 선택 입력

입력 변수는 일반적으로 0에서 양수로 증가하므로, 이 변수에 대한 객관적 함수의 파생상품이 음수일 경우 목표함수의 값이 감소한다. 동등하게, 피벗 열을 선택하면 목표 함수의 값이 증가하여 테이블라우의 목표 행에 해당하는 항목이 양의 값이다.

만약 둘 이상의 열이 있어서 객관적인 행의 항목이 양수라면, 기본 변수 집합에 어떤 열을 추가할지 선택할 수 있는 것은 다소 임의적이며, Devex^[21] 알고리즘과 같은 몇 가지 입력 변수 선택 규칙이^[20] 개발되었다.

목표 행의 모든 항목이 0보다 작거나 같으면 변수를 입력할 수 없으며 실제로 솔루션이 최적이다. 객관적 행이 이제는 형태 방정식에 해당하므로 최적이라고 쉽게 볼 수 있다.

${\displaystyle z(\mathbf {x} )=z_{B}+{\텍스트{비기본 변수에 해당하는 음성 항}}}$

변수 선택 규칙을 입력하여 목표 행의 항목이 음수인 열을 선택하도록 변경함으로써 알고리즘을 변경하여 최소값이 아닌 목표 함수의 최대값을 찾도록 한다.

변수 선택에서 떠나는 중

피벗 열을 선택한 후 피벗 행의 선택은 결과적 해결책이 실현 가능하다는 요건에 의해 크게 결정된다. 첫째, 입력 변수의 값이 음수가 아닐 것임을 보장하므로 피벗 열의 양수 항목만 고려한다. 피벗 열에 양수 입력이 없는 경우 입력 변수는 음수가 아닌 값을 취할 수 있으며, 이 값을 계속 사용할 수 있다. 이 경우 객관적 기능은 아래에 제한되지 않으며 최소치가 없다.

다음으로, 피벗 행은 다른 모든 기본 변수가 양성으로 유지되도록 선택해야 한다. 계산 결과 입력 변수의 결과 값이 최소일 때 이러한 현상이 나타난다는 것을 알 수 있다. 즉, 피벗 열이 c인 경우 피벗 행 r이 선택되어 다음과 같이 된다.

${\displaystyle b_{r}/a_{rc}\,}$

a_rc > 0이 되도록 모든 r에 대한 최소값이다. 이를 최소 비율 검정이라고 한다.^[20] 최소값이 달성되는 행이 두 개 이상일 경우 낙하 변수 선택 규칙을^[22] 사용하여 결정할 수 있다.

예

선형 프로그램 고려

최소화

${\displaystyle Z=-2x-3y-4z\,}$

대상

${\displaystyle {\displaysty}3x+2y+z&\leq 10\\\2x+5y+3z&\leq 15\x,\,y,\z&\geq 0\ended}}}}$

느슨한 변수 s와 t를 추가하면 표준 테이블au로 표현된다.

${\displaystyle {\bmatrix}1&2&3&4&0&0&0&0\\0&1&1&1&1&10\0&5&3&0&1&1&15\end{bmatrix}}}}}$

여기서 5열과 6열은 기본 변수 s와 t를 나타내고 그에 상응하는 기본 실현 가능한 해결책은

${\displaystyle x=y=z=0,\,s=10,\,t=15.}$

2, 3, 4열은 피벗 열로 선택할 수 있으며, 이 예에서는 4열이 선택된다. 2행과 3행을 피벗 행으로 선택한 결과 z 값은 각각 10/1 = 10, 15/3 = 5이다. 이 중 최소값이 5이므로 3열은 피벗 행이어야 한다. 피벗 생성 수행

${\displaystyle {\bmatrix}3&#2&-11&#0&#4&#460\\0&7&1&#1&#3&#1&#3&#1&#1&#1&#15}}d{bmatrix}}}}$

이제 4열과 5열은 기본 변수 z와 s를 나타내고 그에 상응하는 기본적인 실현 가능한 해결책은

$[\displaystyle x=y=t=0,\,z=5,\,s=5]}$

다음 단계에서는 목표 행에 긍정적인 항목이 없으며, 실제로도 긍정적인 항목이 없다.

${\displaystyle Z={\frac {-60+2x+11y+4t}{3}}=-20+{\frac {2x+11y+4t}{3}}}}$

그래서 Z의 최소값은 -20이다.

초기 표준 테이블라우 찾기

일반적으로, 선형 프로그램은 표준 형태로 주어지지 않을 것이며, 등가의 표준 테이블라우를 찾아야 심플렉스 알고리즘이 시작될 수 있다. 이것은 인공 변수의 도입으로 이루어질 수 있다. ID 행렬의 열은 이러한 변수에 대한 열 벡터로 추가된다. 제약 조건 방정식의 b 값이 음수일 경우, ID 행렬 열을 추가하기 전에 방정식을 부정한다. 이는 실현 가능한 해결책이나 최적 해결책의 집합을 바꾸지 않으며, 느슨한 변수가 초기 실현 가능한 해결책이 될 수 있도록 보장한다. 새로운 탁자는 표준적인 형태지만 원래의 문제와 동등하지는 않다. 그래서 인공 변수의 합과 같은 새로운 객관적 함수가 도입되고 최소값을 찾기 위해 심플렉스 알고리즘이 적용되는데, 수정된 선형 프로그램을 1단계 문제라고 한다.^[23]

1단계 문제에 적용된 심플렉스 알고리즘은 음이 아닌 변수의 합이 되는 새로운 목표 함수의 값이 0으로 제한되기 때문에 새로운 목표 함수의 최소 값으로 종료되어야 한다. 최소값이 0일 경우, 인위적 변수는 원래의 문제와 동등한 표준적 테이블라우를 생성하는 표준적 테이블라우에서 제거될 수 있다. 그런 다음 심플렉스 알고리즘을 적용하여 솔루션을 찾을 수 있다. 이 단계를 단계 II라고 한다. 최소값이 양의 값이면 인공 변수가 모두 0인 1단계 문제에 대해 실현 가능한 해결책이 없다. 이는 원문제의 실현 가능한 영역이 비어 있어 원문제는 해결책이 없음을 시사한다.^[13][14][24]

예

선형 프로그램 고려

최소화

${\displaystyle Z=-2x-3y-4z\,}$

대상

${\displaystyle {\displaysty}3x+2y+z&=10\\2x+5y+3z&=15\x,\,y,\,z&\geq 0\ended{aigned}}$

이것은 (비 카논) 테이블라우로 표현된다.

${\displaystyle {\bmatrix}1&2&3&4&0\\0&3&1&10\0&2&5&3&15\end{bmatrix}}}}$

인공 변수 u 및 v와 목표 함수 W = u + v를 도입하여 새로운 테이블au를 제공

${\displaystyle {\displaystyle {\bmatrix}1&0&0&#1&#1&#1&#1&#1&#2&#1&#1&#1&#0&#0&#2&#1&#1&#1&#1&#1&#1&#15}}}}}}}}}}}}$

원래의 목적함수를 정의하는 방정식은 2단계를 예상하여 유지된다.

시공에 따르면 u와 v는 모두 초기 ID 매트릭스의 일부분이기 때문에 기본 변수다. 그러나 목표함수 W는 현재 u와 v가 모두 0이라고 가정한다. 목표 함수를 올바른 값으로 조정하려면 u = 10 및 v = 15에서 세 번째 및 네 번째 행을 첫 번째 행에 추가하십시오.

${\displaystyle {\bmatrix}1&0&5&7&4&0&0&25\\0&1&3&0&0&0&0&0&1&1&1&10\0&0&2&5&3&1&1&1&1&1&1&1&1&15\end{bmatrix}}}}}}}}}}}}}}}?$

5열은 피벗 열로 선택하므로 피벗 행은 4행이어야 하며 업데이트된 테이블au는

${\displaystyle {\bmatrix}3&0&7&#1&0&#4&#4&#0&#0&#2&#0&#0&#0&#0&#0&#1&#1&#0&#0&#0&#0&#0&#1&#1&#1&#15}}{bmatrix}}}}}}}}}}}}}}}$

Now select column 3 as a pivot column, for which row 3 must be the pivot row, to get

${\displaystyle {\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&-25&0&2&-10&-130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}}$

The artificial variables are now 0 and they may be dropped giving a canonical tableau equivalent to the original problem:

${\displaystyle {\begin{bmatrix}7&0&-25&0&-130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}$

This is, fortuitously, already optimal and the optimum value for the original linear program is −130/7.

Advanced topics

Implementation

The tableau form used above to describe the algorithm lends itself to an immediate implementation in which the tableau is maintained as a rectangular (m + 1)-by-(m + n + 1) array. It is straightforward to avoid storing the m explicit columns of the identity matrix that will occur within the tableau by virtue of B being a subset of the columns of [A, I]. This implementation is referred to as the "standard simplex algorithm". The storage and computation overhead is such that the standard simplex method is a prohibitively expensive approach to solving large linear programming problems.

In each simplex iteration, the only data required are the first row of the tableau, the (pivotal) column of the tableau corresponding to the entering variable and the right-hand-side. The latter can be updated using the pivotal column and the first row of the tableau can be updated using the (pivotal) row corresponding to the leaving variable. Both the pivotal column and pivotal row may be computed directly using the solutions of linear systems of equations involving the matrix B and a matrix-vector product using A. These observations motivate the "revised simplex algorithm", for which implementations are distinguished by their invertible representation of B.^[25]

In large linear-programming problems A is typically a sparse matrix and, when the resulting sparsity of B is exploited when maintaining its invertible representation, the revised simplex algorithm is much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.^{[24][25][26][27][28]}

Degeneracy: 대기 및 사이클링

모든 기본 변수의 값이 양수인 경우 피벗은 목표 값을 개선해야 한다. 항상 이 경우 기본 변수 세트가 두 번 발생하지 않으며, simplex 알고리즘은 제한된 수의 스텝 후에 종료되어야 한다. 기본 변수 중 적어도 하나 이상이 0인 기본 실현 가능한 해결책을 퇴보라고 하며, 객관적 가치가 개선되지 않는 피벗을 초래할 수 있다. 이 경우 용액에는 실제적인 변화가 없고 기본 변수 집합의 변화만 있을 뿐이다. 그러한 선회들이 연속적으로 여러 번 발생하면 개선은 없다; 대규모 산업 적용에서 퇴보하는 것이 일반적이며 그러한 「스트랙팅」이 눈에 띈다. 정지보다 더 나쁜 것은 동일한 기본 변수 집합이 두 번 발생할 가능성이며, 이 경우 심플렉스 알고리즘의 결정론적 회전 규칙이 무한 루프 또는 "주기"를 생성하게 된다. 실전에 있어서는 퇴행성이 원칙이고 시간을 지체하는 것이 일반적이지만, 실전에 있어서는 사이클링이 드물다. 실제 사이클링의 예에 대한 논의는 파드버그에서 이루어진다.^[24] Bland의 규칙은 사이클링을 방지하고 따라서 심플렉스 알고리즘이 항상 종료된다는 것을 보장한다.^[24][29][30] 또 다른 선회 알고리즘인 크리스크로스 알고리즘은 선형 프로그램에서 사이클을 하지 않는다.^[31]

자데의 법칙이나 커닝햄의 법칙과 같은 역사 기반 피벗 규칙도 특정 변수가 얼마나 자주 사용되는지를 추적하여 정지 및 사이클링 문제를 회피하고 그 다음 가장 자주 사용되지 않았던 그러한 변수를 선호하려고 한다.

효율성

심플렉스 방식은 실무에서 현저히 효율적이며 푸리에-모츠킨 제거와 같은 초기 방법보다 훨씬 개선되었다. 그러나 1972년 클리와 민티는^[32] 클라이-민티 큐브라는 예를 들어 단치히가 공식화한 심플렉스 방법의 최악의 복잡성은 기하급수적인 시간임을 보여주었다. 그 이후로, 그 방법의 거의 모든 변형에 대해, 그것이 잘 수행되지 않는 선형 프로그램의 집단이 있음을 보여주었다. 하위-우수 피벗 규칙이 알려져 있지만 다항식 시간에 변동이 있는지 여부는 공개 질문이다.^[33]

2014년에, 심플렉스 방법의 특정 변종이 NP-마이티 즉, 알고리즘의 실행 중 NP의 어떤 문제라도 다항식 오버헤드로 해결할 수 있다는 것이 증명되었다. 더욱이, 주어진 입력에 대한 알고리즘의 실행 중에 주어진 변수가 기초를 입력했는지와 주어진 문제를 해결하는 데 필요한 반복 횟수를 결정하는 것은 둘 다 NP-hard 문제들이다.^[34] 거의 동시에, 그것의 출력이 PSPACE-완전인 인공 피벗 규칙이 존재한다는 것을 보여주었다.^[35] 2015년에는 단치히의 피벗 규칙의 산출물을 계산하는 것이 PSPACE-완전하다는 것을 보여주기 위해 강화되었다.^[36]

simplex 알고리즘이 지수적으로 최악의 경우 복잡함에도 불구하고 실제적으로 효율적이라는 관측을 분석하고 정량화함으로써 다른 복잡성 척도가 개발되었다. 심플렉스 알고리즘은 다양한 확률 분포에서 다항식 시간 평균 사례 복잡성을 가지며, 랜덤 행렬에 대한 확률 분포의 선택에 따라 심플렉스 알고리즘의 정밀 평균 사례 성능을 가진다.^[37][38] "일반적인 현상"^{[citation needed]}을 연구하기 위한 또 다른 접근방식은 일반 위상에서 나온 Baire 범주 이론을 사용하며, (토폴로지적으로) "대부분" 행렬은 다항식 단계 수에서 심플렉스 알고리즘으로 해결할 수 있음을 보여준다. 심플렉스 알고리즘의 성능을 분석하는 또 다른 방법은 작은 섭동 하에서 최악의 경우 시나리오의 동작을 연구하는 것이다. 최악의 경우 시나리오는 작은 변화(구조적 안정성의 관점에서)에서도 안정적인가, 아니면 추적가능하게 되는가? 평활 분석이라고 불리는 이 연구 분야는 특히 심플렉스 방법을 연구하기 위해 도입되었다. 실제로 노이즈가 있는 입력에 대한 심플렉스 방법의 실행 시간은 변수의 수와 섭동의 크기에서 다항식이다.^[39]

기타 알고리즘

선형 프로그래밍 문제를 해결하기 위한 다른 알고리즘은 선형 프로그래밍 기사에 설명되어 있다. 또 다른 기본 교환 피벗 알고리즘은 크리스크로스 알고리즘이다.^[40][41] 내부 포인트 방법을 사용하는 선형 프로그래밍을 위한 다항식 시간 알고리즘이 있는데, 여기에는 카치얀의 타원형 알고리즘, 카르마르카의 투영 알고리즘, 경로 추종 알고리즘 등이 포함된다.^[15]

선형-수축 프로그래밍

LFP(Linear-fractal Programming, LFP)는 선형 프로그래밍(LP)의 일반화다. LP에서 객관적 함수는 선형함수인 반면, 선형-수축 프로그램의 객관적 함수는 두 개의 선형함수의 비율이다. 즉, 선형 프로그램은 분모가 어디에서나 그 가치를 갖는 상수함수인 분수-선형 프로그램이다. 선형 굴절 프로그램은 심플렉스 알고리즘의^{[42][43][44][45]} 변형이나 크리스크로스 알고리즘으로 해결할 수 있다.^[46]

참고 항목

메모들

참조

• Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547.

추가 읽기

이러한 소개는 컴퓨터 과학 및 운영 연구의 학생들을 위해 작성되었다.

• 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7 섹션 29.3: 심플렉스 알고리즘 페이지 790–804.
• 프레더릭 S. 힐리어와 제럴드 J. 리버먼: 운영 연구 소개, 제8판. 맥그로힐 ISBN 0-07-123828-X
• Rardin, Ronald L. (1997). Optimization in operations research. Prentice Hall. p. 919. ISBN 978-0-02-398415-0.

외부 링크

위키북 운영 연구에는 다음과 같은 주제의 페이지가 있다. 심플렉스 메소드

• 조지아 공과대학교 스파이로스 레벨리오티스의 선형 프로그래밍과 심플렉스 알고리즘 소개
• Greenberg, Harvey J, Klee-Minty Polytope, Simplex Method의 지수적 시간 복잡성을 보여주는 덴버의 콜로라도 대학교(1997) PDF 다운로드
• Simplex Method 예제를 포함한 Simplex Method에 대한 자습서.
• www.mathstools.com의 Mathstools Simplex 계산기
• 위스콘신-화이트워터 대학의 Thomas McFarland에 의한 표준 선형 프로그래밍 문제에 대한 Simplex 절차의 예.
• PHPSimplex: Mahlaga 대학의 Daniel Izquierdo와 Juan José Ruiz의 선형 프로그래밍 문제 해결을 위한 온라인 도구(UMA, 스페인)
• 심플렉스-m 온라인 심플렉스 해결사