📂최적화이론

선형계획법의 기본정리 증명

정리

방정식 폼의 선형계획문제에 대해, 다음 셋 중 하나는 참이다.

• (1): 만약 최적해가 존재하지 않는다면, 애초에 문제 자체가 비가용^infeasible이거나 언바운드^unbounded된 것이다.
• (2): 만약 가용해가 존재한다면, 가용기저해도 존재한다.
• (3): 만약 최적해가 존재한다면, 최적기저해도 존재한다.

증명

전략: 기본정리^{fundamental theorem}라는 이름이 붙어있는만큼 선형계획법 그 자체의 가능성을 논하고 있다. 약식 증명을 제외하고는 다른 보조정리들을 모아놓은 것이다. 약식 증명이라고 하는 것도 너무 직관에 의존하고 수학다운 논법이 아니라서 그렇지 알고리즘적으로 접근했을 때 아주 틀린 말들은 아니다. (1)~(3)은 Vanderbei와 Matousek가 적절하게 섞여있다. 증명을 이해하기 위해서는 최소한 심플렉스 메소드가 왜 반드시 성공하는지, 즉 브랜드 룰은 이해하고 있어야한다.

약식 ¹

페이즈 1에서 문제가 비가용인지 알아내거나 기저가용해를 만들어낼 수 있고, 페이즈 2에서 문제가 언바운드인지 알아내거나 브랜드 룰를 사용하는 심플렉스 메소드를 통해 최적기저해를 찾을 수 있다.

(1) ²

방정식 폼에서 최적해의 존재성: $$\begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix}$$ 행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 방정식 폼으로 나타난다고 하자. 만약 적어도 하나의 가용해가 존재하며, 가용해의 집합에서 $\mathbf{c}^{T} \mathbf{x}$ 가 위로 유계^{bounded Above}면 최적해가 존재한다.

위 보조정리의 대우명제에 따라, 최적해가 존재하지 않는다면 가용해의 집합이 공집합이거나 목적 함수가 언바운드다.

(2) ^{3 4}

기저가용해의 유일성: 선형계획문제가 방정식 폼으로 나타난다고 할 때, 그 기저가용해는 기저 $B$ 에 따라 유일하게 결정된다.

위 보조정리는 정확히는 기저가용해의 유일성을 보이는 것이지만, 증명 과정 속에서 사실 그 존재성도 보이고 있다.

브랜드 룰: 선형계획법의 심플렉스 메소드에서 진입 변수^{entering variable}의 인덱스를 $\mathcal{N}$ 에서 가장 작은 것으로 선택하고, 이탈 변수^{leaving variable}의 인덱스를 $\mathcal{B}$ 에서 가장 작은 것으로 선택하는 것을 브랜드 룰^{Brand’s rule}이라 한다. 브랜드 룰에 따르면 심플렉스 메소드는 사이클에 빠지지 않는다.

사이클링: 만약 심플렉스 메소드가 끝나지 않는다면, 딕셔너리가 사이클에 빠진 것이다.

브랜드 룰에 따라 하나의 가용해가 존재한다면, 심플렉스 메소드를 통해 사이클링을 일으키지 않고 다른 가용기저해를 찾을 수 있다.

(3) ⁵

최적기저가용해의 존재성: 선형계획문제가 방정식 폼으로 나타난다고 하자. 만약 최적해가 존재한다면, 최적기저가용해도 존재한다.

위 보조정리의 의미를 세밀하게 따져보자면, 최적해가 존재할 때 그 중 하나는 기저가용해여야한다는 것이다.

■