개정 심플렉스법

수학적 최적화에서 수정된 심플렉스 방법은 선형 프로그래밍을 위한 조지 단치히의 심플렉스 방법의 변형이다.

개정된 심플렉스 방식은 수학적으로 표준 심플렉스 방식과 동일하지만 구현에 차이가 있다.기본 변수 집합에 조정된 제약조건을 명시적으로 나타내는 표고를 유지하는 대신, 제약조건을 나타내는 행렬의 기초의 표현을 유지한다.매트릭스 지향 접근방식은 희박한 매트릭스 연산을 가능하게 하여 연산 효율을 높일 수 있다.^[1]

문제 제식

나머지 논의의 경우, 선형 프로그래밍 문제가 다음과 같은 표준 형태로 변환된 것으로 가정한다.

${\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}$

여기서 A ∈ R^m×n. 일반성을 상실하지 않고 제약 행렬 A가 전체 열 순위를 가지며 문제가 타당하다고 가정한다. 즉, Ax = b와 같은 x 0 0이 적어도 하나 있다.A가 순위결핍 상태인 경우 중복 제약이 있거나 문제가 실행 불가능할 수 있다.두 가지 상황 모두 사전 검토 단계로 처리할 수 있다.

알고리즘 설명

최적성 조건

선형 프로그래밍의 경우 Karush-Kuhn-Tucker 조건은 최적화를 위해 필요하며 충분하다.표준형식의 선형 프로그래밍 문제의 KKT 조건은 다음과 같다.

${\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}$

여기서 λ과 s는 각각 제한조건 Ax = b와 x ≥ 0과 관련된 라그랑주 승수다.^[2]모든 1 < i < n에 대해 sx_ii = 0에 해당하는 마지막 조건을 보완적 느슨함 조건이라고 한다.

때때로 선형 프로그래밍의 기본 정리라고 알려진 것에 의해 실현 가능한 폴리토프의 꼭지점 x는 후자의 열에서 선택한 A의 기초 B로 식별할 수 있다.^[a]A가 전위를 가지기 때문에 B는 비논리적이다.일반성을 상실하지 않는 한 A = [B N]이라고 가정한다.그러면 x는 다음에 의해 주어진다.

${\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}$

여기서 x_B ≥ 0. c와 s는 그에 따라 으로 분할한다.

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{정렬}}}$

보완적 느슨함 조건을 만족시키려면 s = 0으로_B 한다.그 뒤를 잇는다.

${\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}$

라는 것을 암시한다.

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{정렬}}}$

이 시점에서 s_N ≥ 0이면 KKT 조건이 충족되므로 x가 최적이다.

피벗 작업

KKT 조건을 위반할 경우 B의 기존 칼럼을 희생하여 N 열을 기본으로 도입하는 피벗 연산을 실시한다.퇴보성이 없는 경우 피벗 연산은 항상 cx의^T 엄격한 감소를 초래한다.따라서 문제가 경계가 되는 경우 정점의 수가 한정되어 있기 때문에 수정된 심플렉스 방법은 피벗 연산을 반복한 후 최적의 정점에서 종료해야 한다.^[4]

입력_q 지수로 지수 m < q ≤ n을 s < 0으로 선택한다.A, A의_q 해당 컬럼을 기본으로 옮기고, x는_q 0에서 증가하도록 허용된다.라는 것을 알 수 있다.

${\displaystyle {\frac {\partial({\boldsymbol {c}^{\mathrm {T}{\boldsymbol{x}}}}}}{\partial x_{q}}}=s_{q}}}},}}$

즉, x의_q 모든 단위가 증가하면 cx의^T -s가_q 감소한다.^[5]이후

${\displaystyle {\boldsymbol {Bx_{B}}+{\boldsymbol {A}_{q}x_{q}={\boldsymbol {b},}$

x는_B x - Δx x⁻¹_qq 0에 따라_B Δx = BAx만큼 감소해야 한다.let d = BA⁻¹_q.d ≤ 0이면 아무리 x를_q 늘려도 x_B - Δx는 음이 아닌 상태를 유지하게 된다.따라서 cx는^T 임의로 감소할 수 있으며, 따라서 문제는 무한하다.그렇지 않은 경우, 인덱스 p = argmin_1≤i≤mi {x_i/d_i d > 0}을(를) 왼쪽 인덱스로 선택하십시오.이 선택은 타당성을 유지하면서 효과적으로 x를_qp 0에서 x까지 증가시킨다.피벗 작업은 기초에서 A를_p A로_q 교체하는 것으로 마무리된다.

숫자 예제

다음과 같은 선형 프로그램을 고려하십시오.

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{정렬}}}$

내버려두다

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}$

초기에는 실현 가능한 꼭지점 x = [0 0 0 10 15]^T에 해당한다.지금 이 순간

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

입력 인덱스로 q = 3을 선택하십시오.그 다음 d = [1 3],^T 즉 x₃ 단위가 증가하면 x와₄ x가₅ 각각 1과 3으로 감소한다는 것을 의미한다.따라서 x는₃ 5로 증가하는데, 이때 x는₅ 0으로 감소하고 p = 5는 이탈지수가 된다.

피벗 작업 후

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{정렬}}}$

그에 상응하여

${\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

양의 s는_N x가 이제 최적임을 나타낸다.

실무문제

퇴보

전면 개정한 심플렉스 방식은 수학적으로 심플렉스 방식과 동일하기 때문에 피벗 연산이 cx의^T 감소를 초래하지 않고 피벗 연산의 체인으로 인해 기초가 순환되는 퇴화 현상도 겪는다.동요 또는 사전 편찬 전략을 사용하여 사이클링을 방지하고 종료를 보장할 수 있다.^[6]

기준표현황

개정된 심플렉스 방법에는 B와 관련된 두 가지 유형의 선형 시스템이 있다.

${\displaystyle {\begin{aigned}{\boldsymbol{Bz}&={\boldsymbol {y},\\\boldsymbol{B}^{\boldsymbol {T}{\boldsymbol}}}.\end{정렬}}}$

B를 리팩터링하는 대신에, 보통 LU 인자화는 각 피벗 작동 후에 직접 업데이트되며, 이 목적을 위해 Forrest-와 같은 몇 가지 전략이 존재한다.톰린과 바텔스-골루브 방법.그러나, 수치 오류뿐만 아니라 업데이트를 나타내는 데이터의 양은 시간이 지남에 따라 쌓이고 주기적인 리팩터링이 필요하게 된다.^[1][7]

참고 및 참조

메모들

참조

참고 문헌 목록