- 선형계획에서의 쌍대정리에 대해 다룬다.
개요: 쌍대정리란?
원문제
\begin{align*}
\text{min} \kern{10pt} & \mathbf{c}^{\prime}\mathbf{x}
\\[15pt]
\text{s.t.} \kern{10pt} &
A\mathbf{x} = \mathbf{b},~
\mathbf{x} \ge 0
\end{align*}
쌍대문제
\begin{align*}
\text{max} \kern{10pt} & \mathbf{y}^{\prime}\mathbf{b}
\\[15pt]
\text{s.t.} \kern{10pt} &
\mathbf{y}^{\prime}A \le \mathbf{c}^{\prime}
\kern{25pt}
\end{align*}
특징
- 부등식 기호
- 비음조건이 없다.
왜 쌍대문제를 구하려고 하는가?
- 미지수가 줄어든다.
- 쌍대 문제에 해가 있다면, 원 문제에도 해가 있다.
즉, 원래 문제를 쌍대문제로 바꾸면 구하기가 더 쉬워질 수 있다.
물론 항상 그렇지는 않으나, 심플렉스 알고리즘 등에서 이를 사용한다.
쌍대문제의 3가지 정리
쌍대문제에는 3가지 속성이 존재한다.
약쌍대정리
원문제의 해는 쌍대문제의 해보다 크거나 같다.
\mathbf{c}^{\prime}\mathbf{x}
~\ge~
\mathbf{y}^{\prime}\mathbf{b}
이 부등식이 성립하는 이유는 다음과 같다.
\mathbf{c}^{\prime} = \mathbf{y}^{\prime}A
\\[10pt]
A\mathbf{x} = \mathbf{b}
\\[20pt]
\therefore~
\mathbf{c}^{\prime}\mathbf{x}
~\ge~
\mathbf{y}^{\prime}A\mathbf{x}
~=~
\mathbf{y}^{\prime}\mathbf{b}
파아카스 정리(Farkas’ lemma)
두 조건을 동시에 만족하는 벡터 x, y는 존재하지 않는다.
\begin{align}
&\mathbf{c}^{\prime}\mathbf{x}
~>~0,~A\mathbf{x}=0,~\mathbf{x}\ge0
\\[10pt]
&\mathbf{c} \le
\mathbf{y}^{\prime}A
\end{align}
1번이 성립할 경우
2번이 성립할 경우
이를 이용해 강쌍대정리를 증명한다.
강쌍대정리
원문제의 해가 쌍대문제의 해와 같다.
\mathbf{c}^{\prime}\mathbf{x}
~=~
\mathbf{y}^{\prime}\mathbf{b}
이를 증명하는 방법은 다음과 같다.