📂최적화이론

선형계획법에서의 약한 쌍대성 정리 증명

정리

$$\begin{align*} \text{Maximize} & \sum_{j=1}^{n} c_{j} x_{j} & \text{(Primal)} \\ \text{subject to} & \sum_{j=1}^{n} a_{ij} x_{j} \le b_{i} & i = 1 ,\cdots , m \\ & x_{j} \ge 0 & j = 1, \cdots , n \end{align*}$$ $$\begin{align*} \text{Minimize} & \sum_{i=1}^{m} b_{i} y_{i} & \text{(Dual)} \\ \text{subject to} & \sum_{i=1}^{m} y_{i} a_{ij} \ge c_{j} & j = 1 ,\cdots , n \\ & y_{i} \ge 0 & i = 1, \cdots , m \end{align*}$$

주어진 선형계획문제의 프라이멀 문제와 듀얼 문제가 위와 같이 나타난다고 하자. 만약 $\left( x_{1} , \cdots , x_{n} \right)$ 가 프라이멀 문제의 가용해고, $\left( y_{1} , \cdots , y_{m} \right)$ 가 듀얼 문제의 가용해라면, 다음 부등식이 성립한다. $$\sum_{j=1}^{n} c_{j} x_{j} \le \sum_{i=1}^{m} b_{i} y_{i}$$

설명

약한 쌍대성 정리는 쉽게 말해서 위 그림처럼 프라이멀 문제와 듀얼 문제의 목적 함수값이 역전되지 않음을 보장한다.

증명 ¹

$$\begin{align*} \sum_{j} c_{j} x_{j} \le& \sum_{j} \left( \sum_{i} y_{i} a_{ij} \right) x_{j} & \because \text{Dual Constraint} \\ =& \sum_{i,j} y_{i} a_{ij} x_{j} \\ =& \sum_{i,j} x_{j} a_{ij} y_{i} \\ =& \sum_{i} \left( \sum_{j} a_{ij} x_{j} \right) y_{i} \\ \le& \sum_{i} b_{i} y_{i} & \because \text{Primal Constraint} \end{align*}$$

■

같이보기

선형계획법에서의 쌍대성

최적화를 전공할 게 아니라 한 과목으로 다룬다면 선형계획법은 심플렉스 메소드와 쌍대성 이 두가지만 배우면 모든 걸 다 배운 것이다. 물론 그 둘 뿐이라고해서 딱히 그 과정이 쉽다는 말은 아니다.

심플렉스 메소드가 구체적인 그 방법에 대해 논한다면, 쌍대성은 프라이멀 문제에 대해 듀얼 문제가 존재하고, 그 최적해가 서로 같다는 식의 다분히 이론적인―순수수학적인 논의다. 이는 다음의 쌍대성 정리들로 보장된다.

약한 쌍대성 정리

$$\sum_{j=1}^{n} c_{j} x_{j}^{\ast} \le \sum_{i=1}^{m} b_{i} y_{i}^{\ast}$$

강한 쌍대성 정리

$$\sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast}$$