쌍대성 해석 - 실험 도서관

쌍대성의 기초

선형계획법에서 쌍대성은 원문제(Primal Problem)와 쌍대문제(Dual Problem) 사이의 관계를 나타낸다. 원문제는 일반적으로 최적화하려는 목적을 가진 문제이고, 쌍대문제는 원문제의 제약 조건과 목적함수를 기반으로 파생된 문제이다.

원문제와 쌍대문제는 서로 밀접하게 연관되어 있으며, 이 관계는 여러 해석적 및 계산적 이점을 제공한다. 특히, 쌍대성 이론을 통해 강 쌍대성 정리와 약 쌍대성 정리를 도출할 수 있다. 하지만 여기서는 쌍대성 해석의 기초를 살펴보겠다.

쌍대성 문제의 형식

원문제가 다음과 같은 형태라고 가정한다.

$\text{최소화 } \mathbf{c}^\top \mathbf{x} \quad \text{제약조건} \quad \mathbf{A} \mathbf{x} \geq \mathbf{b}, \, \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{최대화 } \mathbf{b}^\top \mathbf{y} \quad \text{제약조건} \quad \mathbf{A}^\top \mathbf{y} \leq \mathbf{c}, \, \mathbf{y} \geq 0$

여기서:

$\mathbf{y} \in \mathbb{R}^m$ 은 쌍대 변수 벡터

쌍대 문제에서 나타나는 변수 $\mathbf{y}$ 는 원문제의 제약 조건에 대응하는 쌍대 변수이다.

경제적 해석

쌍대성의 경제적 해석은 원문제의 해석에 중요한 시사점을 제공한다. 쌍대 변수 $\mathbf{y}$ 는 원문제에서 제약 조건이 어느 정도로 '귀중한가'를 나타낸다. 즉, 원문제의 제약 조건에 약간의 변화가 있을 때 목적 함수 값이 얼마나 변하는지를 나타내는 그림자 가격(Shadow Price)이라고 할 수 있다.

만약 쌍대 문제에서 어떤 변수 $y_i$ 가 0이 아니라면, 이는 원문제에서 해당 제약 조건이 최적 해에 영향을 주고 있다는 뜻이다. 반대로, $y_i = 0$ 인 경우, 이는 해당 제약 조건이 실제로 최적 해를 구하는 과정에서 역할을 하지 않았음을 의미한다.

쌍대성 정리

쌍대성 이론의 핵심 정리 중 하나는 강 쌍대성 정리이다. 이 정리는 원문제와 쌍대문제 간의 최적값이 동일하다는 중요한 사실을 다룬다. 하지만 이를 이해하기 위해 먼저 약 쌍대성 정리를 살펴보아야 한다.

약 쌍대성 정리

약 쌍대성 정리는 원문제와 쌍대문제 간의 목적 함수 값에 대한 불등식을 나타낸다. 이를 수식으로 표현하면 다음과 같다.

$\mathbf{x} \text{가 원문제의 실현 가능한 해라면}, \quad \mathbf{y} \text{가 쌍대문제의 실현 가능한 해일 때,}$

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

즉, 원문제에서 얻을 수 있는 목적 함수의 값은 쌍대문제의 목적 함수 값보다 항상 크거나 같다는 것을 의미한다. 이를 통해 쌍대문제의 해는 원문제의 상계(Upper Bound)로 작용한다.

강 쌍대성 정리

강 쌍대성 정리는 다음과 같이 정의된다.

$\mathbf{x}^* \text{가 원문제의 최적해이고,} \quad \mathbf{y}^* \text{가 쌍대문제의 최적해라면},$

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

즉, 원문제와 쌍대문제의 최적해에서 목적 함수의 값은 동일하다. 이 사실은 쌍대 문제의 해석적 의미를 강화시켜 주며, 원문제의 해를 구할 때 쌍대문제를 활용할 수 있는 근거가 된다.

쌍대성 갭

쌍대성 이론에서 쌍대성 갭(Duality Gap)은 원문제와 쌍대문제 간의 목적 함수 값의 차이를 의미한다. 수식으로 표현하면:

$\text{쌍대성 갭} = \mathbf{c}^\top \mathbf{x} - \mathbf{b}^\top \mathbf{y}$

강 쌍대성 정리에 따르면, 쌍대성 갭은 최적 해에서는 항상 0이다. 즉, 원문제와 쌍대문제의 최적해가 있을 때 쌍대성 갭은 존재하지 않는다.

쌍대성 갭의 해석

쌍대성 갭이 존재하는 경우, 이는 원문제와 쌍대문제 사이에 뭔가 잘못되었음을 의미할 수 있다. 예를 들어, 제약 조건이 비실현 가능하거나, 원문제의 해가 존재하지 않을 수 있다.

쌍대성 이론의 적용

쌍대성 이론은 선형계획법 문제를 푸는 과정에서 매우 유용하다. 특히, 쌍대 문제는 원문제의 최적해를 찾는 데 도움을 주며, 제약 조건을 관리하는 데 중요한 역할을 한다. 이를 좀 더 구체적으로 살펴보면 다음과 같다.

1. 제약 조건의 역할

쌍대 변수 $\mathbf{y}$ 는 원문제의 각 제약 조건에 대한 중요한 정보를 제공한다. 원문제에서 제약 조건 $\mathbf{A} \mathbf{x} \geq \mathbf{b}$ 가 주어진다면, 이 제약 조건을 만족시키기 위한 최소한의 비용을 쌍대 변수 $\mathbf{y}$ 가 나타낸다.

만약 쌍대 변수 $y_i = 0$ 이라면, 해당 제약 조건은 원문제에서 크게 중요하지 않다는 것을 의미한다.
반면, $y_i > 0$ 인 경우, 해당 제약 조건이 원문제의 최적해를 결정하는 데 중요한 역할을 한다.

쌍대 문제는 원문제의 제약 조건을 평가하는 도구로 사용될 수 있다. 예를 들어, 제약 조건이 제거되었을 때 최적해가 어떻게 변할지를 쌍대 문제의 해석을 통해 예측할 수 있다.

2. 그림자 가격(Shadow Price)

쌍대 변수는 흔히 그림자 가격(Shadow Price)이라고 불린다. 이는 제약 조건에 대한 미분값으로, 제약 조건이 약간 변화했을 때 목적 함수 값이 얼마나 변하는지를 나타낸다. 경제적 관점에서는, 각 제약 조건에 대한 그림자 가격은 해당 자원의 가치 또는 기여도를 의미한다.

예를 들어, 다음과 같은 선형계획 문제를 고려해보자.

$\text{최소화 } \mathbf{c}^\top \mathbf{x} \quad \text{제약조건} \quad \mathbf{A} \mathbf{x} \geq \mathbf{b}, \, \mathbf{x} \geq 0$

이때, 특정 제약 조건 $\mathbf{A}_i \mathbf{x} \geq b_i$ 에 대한 쌍대 변수 $y_i$ 는 그 제약 조건이 얼마나 중요한지를 나타낸다. 만약 $y_i = 0$ 이라면, 해당 제약 조건은 최적해에 큰 영향을 미치지 않으며, 반대로 $y_i > 0$ 이라면, 그 제약 조건이 중요하게 작용하고 있음을 뜻한다.

3. 민감도 분석

쌍대성 이론은 민감도 분석에 중요한 정보를 제공한다. 민감도 분석이란, 문제의 제약 조건 또는 목적 함수 계수에 변화가 있을 때 최적해가 어떻게 변하는지를 분석하는 것이다. 쌍대 문제의 해를 통해 원문제의 최적해가 제약 조건이나 목적 함수 계수에 민감하게 반응하는지 확인할 수 있다.

이를 수학적으로 설명하자면, 제약 조건 벡터 $\mathbf{b}$ 가 약간 변동되었을 때, 쌍대 문제의 해는 다음과 같이 표현될 수 있다:

$\Delta \mathbf{c} = \mathbf{A}^\top \Delta \mathbf{y}$

이는 원문제의 목적 함수 계수 $\mathbf{c}$ 에 변동이 생겼을 때, 쌍대 변수 $\mathbf{y}$ 의 변화에 의해 나타난다는 것을 의미한다.

쌍대성의 직관적 해석

쌍대성 이론의 직관적 해석은 두 문제 간의 균형을 유지하는 과정으로 볼 수 있다. 원문제가 제공하는 비용과 자원 할당의 최적화 문제에서 쌍대 문제는 자원 사용의 효율성을 평가하는 역할을 한다. 이 두 문제는 상호 보완적이며, 쌍대 문제를 통해 원문제의 복잡한 제약 조건을 간단하게 해석할 수 있다.