단순 알고리즘과 극단 점
이 질문에 대한 내 약칭은 LP = 선형 프로그램, BFS = 기본 실행 가능한 솔루션, SEF = 표준 등식 형식입니다.
Simplex 알고리즘은 극단 지점에서 극단 지점으로 반복하기 때문에 (LP가 SEF에있을 때 Simplex가 BFS에서 BFS로 반복된다는 사실에 해당), 실현 가능 영역이 실현할 수없는 다면체 일 때 Simplex 알고리즘은 기하학적으로 어떻게 작동합니까? SEF (예 : 반 공백)? 실현 가능 영역에 극한 점이없는 LP가 있다고 가정합니다. 그런 다음 SEF에있는 '동등한'LP를 작성하고 대신 Simplex 알고리즘을 실행할 수 있습니다. 그러나이 새로운 다면체에는 극단적 인 점이있는 반면, 원래의 경우에는 전혀 없습니다. 나는 원래 한 LP의 극단 점이 다른 LP의 극단 점과 쌍 절적으로 대응한다고 생각했지만 분명히 그렇지 않습니다.
그렇다면 LP의 SEF 버전의 극단 점은 언제 원본의 극단 점과 쌍방향으로 일치합니까? 그리고 그러한 bijection이 유지되지 않을 때, Simplex 알고리즘이 원래 LP 측면에서 수행하는 작업을 기하학적으로 어떻게 해석해야합니까?
답변
Simplex 알고리즘은 극단 지점에서 극단 지점까지 반복합니다.
기술적으로는 아닙니다. 심플 렉스 알고리즘은 기본 에서 기본 으로 반복 됩니다 . 실행 가능한 기본 솔루션이 극한 지점에 해당하는 경우가 발생합니다. (예를 들어 이중 심플 렉스는 원시 실행 가능 영역의 극단 점이 아닌 이중 실행 가능 기본 솔루션을 반복합니다.)
다음과 같은 표준 형식의 LP를 고려하십시오. \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}LP의 실행 가능 영역은 항상 다면체입니다. 극단 점이 없으면 비어 있거나 (그리고 기본적인 실행 가능한 솔루션이 없음) 다음의 아핀 하위 공간입니다.$\mathbb{R}^{n}$. 이제 후자의 경우 는 발생할 수 없습니다. 아핀 하위 공간이$\mathbb{R}_{+}^{n}$.
이제 원래 다면체와 SEF 표현이 주어 졌을 때 원래 다면체와 SEF 표현이 주어 졌을 때 그 표현이 극단 점을 가지고 있으며 원래 다면체의 극단 점에 해당합니까? 대답은 : 예, SEF는 극단 점을 가질 것이며, 그렇지 않습니다. 원래 다면체의 극점과 항상 일치하지는 않을 수도 있습니다.
다음은 간단한 예입니다. $\mathcal{P} = \{x \in \mathbb{R}\}$, 1 차원 다면체입니다. 그 공식에는 하나의 자유 변수가 있고 제약이 없습니다.
SEF 표현을 작성하려면 $x$ 으로 $x^{+} - x^{-}$ 와 $x^{\pm} \geq 0$. 지금,$(0, 0)$ 해당 SEF의 극한 지점입니다. $x=0$, 이것은 극단적 인 지점이 아닙니다. $\mathcal{P}$.
귀하의 질문을 완전히 이해하지는 못했지만 기본 솔루션이 "극단적 요점"이라는 가정에서 혼란이 발생한 것 같습니다. 기본 (반드시 원시 또는 이중 실현 가능하지 않음) 솔루션은 행 수 제약 조건 (일부는 경계 일 수 있음)의 교차점입니다. 문제에 1 차 또는 이중 실행 가능한 솔루션이 없기 때문에 결과적으로 실행 불가능하거나 제한되지 않을 수 있습니다. 교과서 단순 알고리즘은 실제로 알고리즘을 시작하기 위해 BFS를 설정하는 데 어떤 형태의 1 단계 접근 방식이 필요하다는 사실을 간과합니다. 1 차 단계 1이 문제의 원초적 실행 불가능 함을 발견 할 수 있으며 이중 단계 1이 문제를 제한되지 않은 것으로 발견 할 수도 있습니다.
업데이트 : mtanneau의 대답은 아마도 자유 변수가있는 단일 제약 조건에 대해 똑같이 적용된다는 것입니다. 단순한 구현이 자유 변수로 직접 작동하고 0으로 묶인 두 개의 변수로 변환하지 않는다는 것을 추가하고 싶습니다. 그러나 동일한 유지, 알고리즘은 기본 솔루션을 반복하고 비 기본 자유 변수가 값을 취하는 규칙이 있습니다. 0. 또한 경계 다면체의 경우 기본 솔루션은 극단 점에 해당합니다.