쌍대성의 개념 - 실험 도서관

쌍대성의 정의

선형계획법에서 쌍대성(Duality) 은 주어진 선형계획 문제(원문제, 또는 Primal Problem)와 이에 상응하는 새로운 문제(쌍대문제, 또는 Dual Problem) 간의 관계를 나타낸다. 원문제와 쌍대문제는 서로 밀접한 관계를 가지며, 둘 다 동일한 최적해를 가진다. 즉, 원문제의 해에서 얻을 수 있는 최적값은 쌍대문제의 해에서 얻는 최적값과 동일하다.

쌍대성 이론을 이용하면 복잡한 선형계획 문제를 간단한 쌍대 문제로 변환하여 더 쉽게 풀 수 있는 장점이 있다.

원문제와 쌍대문제의 관계

일반적인 선형계획 문제는 다음과 같은 형태를 가진다:

$\text{maximize} \quad \mathbf{c}^\top \mathbf{x}$

$\text{subject to} \quad \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서: - $\mathbf{c} \in \mathbb{R}^n$ 은 비용 벡터 - $\mathbf{x} \in \mathbb{R}^n$ 은 결정 변수 벡터 - $\mathbf{A} \in \mathbb{R}^{m \times n}$ 은 계수 행렬 - $\mathbf{b} \in \mathbb{R}^m$ 은 제약 조건의 우변 벡터

이 문제에 상응하는 쌍대문제는 다음과 같이 정의된다:

$\text{minimize} \quad \mathbf{b}^\top \mathbf{y}$

$\text{subject to} \quad \mathbf{A}^\top \mathbf{y} \geq \mathbf{c}, \quad \mathbf{y} \geq 0$

여기서: - $\mathbf{y} \in \mathbb{R}^m$ 은 쌍대 변수 벡터

쌍대문제는 원문제의 제약 조건과 목표 함수를 이중적으로 변환하여 나타낸 것이다.

쌍대성 정리

쌍대성의 중요한 결과 중 하나는 쌍대성 정리이다. 이 정리는 원문제와 쌍대문제의 최적해가 동일한 최적값을 가진다는 것을 보여준다. 이는 다음과 같은 수학적 표현으로 나타낼 수 있다:

$\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$

여기서 $\mathbf{x}^*$ 는 원문제의 최적해, $\mathbf{y}^*$ 는 쌍대문제의 최적해이다.

쌍대성 이론의 경제적 해석

쌍대성 이론은 선형계획법에서 경제적 해석을 가능하게 한다. 원문제에서 결정 변수 $\mathbf{x}$ 는 자원 할당 문제에서 자원을 배분하는 역할을 하고, 쌍대문제에서의 변수 $\mathbf{y}$ 는 자원의 가격 또는 그림자 가격(Shadow Price)을 나타낸다. 즉, 쌍대 변수 $\mathbf{y}$ 는 각 제약 조건이 자원으로 작용할 때 해당 자원의 가치(혹은 추가적인 자원 단위당 기여도)를 나타낸다.

따라서, 쌍대문제의 목적 함수는 각 제약 조건(자원)의 가격에 제약 조건의 우변 값(자원의 가용량)을 곱한 값을 최소화하는 문제로 해석할 수 있다. 이와 같은 관점에서 쌍대성은 원문제에서 자원의 최적 분배와 자원의 가격 간의 상호작용을 설명하는 수단으로 활용된다.

쌍대성 정리의 조건

쌍대성 정리가 성립하기 위한 조건은 강 쌍대성 정리와 약 쌍대성 정리로 나뉜다.

약 쌍대성 정리

약 쌍대성 정리는 다음과 같은 내용을 포함한다:

원문제의 모든 허용 가능한 해 $\mathbf{x}$ 에 대해, 쌍대문제의 모든 허용 가능한 해 $\mathbf{y}$ 에 대해서도 다음이 성립한다:

$\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}$

즉, 원문제의 목표 함수값은 쌍대문제의 목표 함수값보다 클 수 없다.

강 쌍대성 정리

강 쌍대성 정리는 원문제와 쌍대문제 모두 최적해가 존재할 때 성립한다. 이 경우, 원문제의 최적해와 쌍대문제의 최적해는 같은 최적값을 가진다. 이는 다음과 같이 표현된다:

$\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$

즉, 최적 상태에서는 원문제와 쌍대문제의 목표 함수값이 동일해지며, 이는 두 문제 간의 밀접한 관계를 의미한다.

쌍대성 이론의 수학적 유도

쌍대 문제는 원문제의 제약 조건을 기반으로 도출되며, 그 과정은 라그랑지 승수법을 통해 이해할 수 있다. 라그랑지 승수법을 사용하여 원문제의 제약을 추가하여 이를 해결하는데, 이때 승수 $\mathbf{y}$ 는 제약 조건에 대한 그림자 가격 역할을 하며, 쌍대 문제의 변수로 등장한다.

원문제는 다음과 같다:

$\text{maximize} \quad \mathbf{c}^\top \mathbf{x}$

$\text{subject to} \quad \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$

이 문제의 라그랑지 함수를 도입하면, 이를 다음과 같이 나타낼 수 있다:

$L(\mathbf{x}, \mathbf{y}) = \mathbf{c}^\top \mathbf{x} - \mathbf{y}^\top (\mathbf{A} \mathbf{x} - \mathbf{b})$

여기서 $\mathbf{y} \geq 0$ 는 제약 조건에 대한 라그랑지 승수로, 쌍대문제의 변수 역할을 한다. 이 함수는 원문제의 목적 함수와 제약 조건의 결합으로 이루어져 있으며, 쌍대 문제는 이 라그랑지 함수의 최소화를 구하는 과정에서 도출된다.

쌍대 문제 도출 과정

라그랑지 함수의 최소화:

주어진 $\mathbf{y}$ 에 대해, 라그랑지 함수를 $\mathbf{x}$ 에 대해 최대화하는 값을 찾는다. 이는 다음과 같은 형태로 표현된다:

$\mathbf{x} \in \arg\max_{\mathbf{x} \geq 0} \left( \mathbf{c}^\top \mathbf{x} - \mathbf{y}^\top (\mathbf{A} \mathbf{x} - \mathbf{b}) \right)$

쌍대 문제의 목적 함수 유도:

라그랑지 함수를 최적화한 결과를 바탕으로, 쌍대 문제의 목적 함수는 다음과 같이 주어진다:

$\text{minimize} \quad \mathbf{b}^\top \mathbf{y}$

이는 각 제약 조건이 자원으로서의 기여도를 평가하는 과정이다.

쌍대 문제의 제약 조건 도출:

라그랑지 함수를 $\mathbf{x}$ 에 대해 최적화할 때의 조건에서 다음과 같은 쌍대 문제의 제약 조건이 도출된다:

$\mathbf{A}^\top \mathbf{y} \geq \mathbf{c}, \quad \mathbf{y} \geq 0$

이 과정을 통해, 원문제에서 제약 조건으로 주어졌던 불평등 관계가 쌍대 문제에서는 목표 함수의 최소화 문제로 전환되고, 이로부터 쌍대 문제의 구조가 도출된다.

경제적 해석의 확장

쌍대성 이론에서, 원문제와 쌍대문제는 자원 할당의 최적화 문제를 서로 다른 방식으로 표현한다. 예를 들어, 원문제는 자원을 효과적으로 배분하는 문제를 나타내고, 쌍대문제는 해당 자원에 대한 그림자 가격을 최적화하는 문제로 해석할 수 있다.

이를 통해 자원의 기회비용 또는 한계 비용을 평가할 수 있으며, 이러한 정보는 의사결정 과정에서 매우 중요한 역할을 한다. 특히, 제한된 자원 하에서 어떤 자원이 더 큰 가치를 제공하는지 판단할 때 쌍대성 이론은 유용한 도구로 작용한다.