쌍대성 문제와 기본 정리

쌍대성 문제의 정의

선형계획법에서 쌍대성(Duality)은 주어진 최적화 문제에 대응하는 또 다른 문제를 정의하는 개념이다. 쌍대성 문제는 주어진 '원문제(Primal Problem)'에 대응하여 '쌍대 문제(Dual Problem)'를 설정하는 방식으로 이뤄진다. 일반적으로 원 문제와 쌍대 문제는 상호 관계를 가지며, 둘 다 최적해를 가질 경우 이들의 해는 일정한 연관성을 갖는다.

원 문제는 주어진 자원 하에서 이익을 최대화하는 것, 또는 비용을 최소화하는 문제로 정의된다. 쌍대 문제는 주어진 제약 조건 하에서 자원의 가격을 결정하여 비용을 최소화하는 문제로 정의된다.

원 문제(Primal Problem)는 일반적으로 다음과 같은 형태를 갖는다:

$\begin{aligned} \text{최소화} \quad & \mathbf{c}^T \mathbf{x} \\ \text{제약조건} \quad & \mathbf{A} \mathbf{x} \geq \mathbf{b}, \\ & \mathbf{x} \geq 0 \end{aligned}$

여기서: - $\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$ : 자원 벡터

쌍대 문제(Dual Problem)는 다음과 같은 형태를 갖는다:

$\begin{aligned} \text{최대화} \quad & \mathbf{b}^T \mathbf{y} \\ \text{제약조건} \quad & \mathbf{A}^T \mathbf{y} \leq \mathbf{c}, \\ & \mathbf{y} \geq 0 \end{aligned}$

여기서: - $\mathbf{y} \in \mathbb{R}^m$ : 쌍대 변수 벡터 - $\mathbf{A}^T$ : $\mathbf{A}$ 의 전치 행렬

쌍대 문제는 원 문제와의 관계를 통해 해석되며, 이 둘 사이에 다양한 정리들이 존재한다.

쌍대성 이론의 기본 정리

쌍대성 이론의 가장 중요한 기본 정리 중 하나는 강쌍대성 정리(Strong Duality Theorem)이다. 이 정리는 원 문제와 쌍대 문제 모두 최적해를 가질 때, 그들의 목적 함수 값이 동일하다는 것을 보장한다.

또 다른 중요한 정리는 약쌍대성 정리(Weak Duality Theorem)이다. 약쌍대성 정리는 원 문제의 임의의 해와 쌍대 문제의 임의의 해에 대해 쌍대 문제의 목적 함수 값이 원 문제의 목적 함수 값보다 작거나 같다는 것을 말한다.

약쌍대성 정리를 수식으로 표현하면 다음과 같다:

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

여기서 $\mathbf{x}$ 는 원 문제의 임의의 해이고, $\mathbf{y}$ 는 쌍대 문제의 임의의 해이다.

쌍대성 정리의 여러 응용과 관련하여 추가적인 정리들이 존재하지만, 쌍대성 문제의 핵심은 원 문제와 쌍대 문제의 상호 관계에서 발생한다는 것이다.

쌍대성 문제의 구성

쌍대성 문제는 원 문제의 각 제약 조건에 대응하는 쌍대 변수를 도입하여 구성된다. 이는 원 문제에서 주어진 자원이나 제약 조건의 가치를 나타내는 변수들로 해석될 수 있다. 원 문제의 제약 조건이 $\mathbf{A} \mathbf{x} \geq \mathbf{b}$ 형태로 주어졌을 때, 쌍대 문제는 다음과 같이 구성된다.

원 문제의 형식

원 문제는 다음과 같이 표준형으로 나타낼 수 있다:

$\begin{aligned} \text{최소화} \quad & \mathbf{c}^T \mathbf{x} \\ \text{제약조건} \quad & \mathbf{A} \mathbf{x} \geq \mathbf{b}, \\ & \mathbf{x} \geq 0 \end{aligned}$

쌍대 문제의 형식

쌍대 문제는 원 문제의 목적 함수와 제약 조건을 이용해 다음과 같이 변형된다:

$\begin{aligned} \text{최대화} \quad & \mathbf{b}^T \mathbf{y} \\ \text{제약조건} \quad & \mathbf{A}^T \mathbf{y} \leq \mathbf{c}, \\ & \mathbf{y} \geq 0 \end{aligned}$

쌍대 변수의 역할

쌍대 문제에서의 변수 $\mathbf{y}$ 는 원 문제의 각 제약 조건에 대한 '가격' 또는 '그림자 가격'으로 해석된다. 이는 자원이 추가될 때 목적 함수 값이 얼마나 변하는지를 나타내는 값이다.

$y_j$ 는 원 문제의 제약 조건 $j$ 에 대응하는 쌍대 변수로, 해당 제약 조건의 '그림자 가격'이다.
쌍대 문제의 목적 함수 $\mathbf{b}^T \mathbf{y}$ 는 자원의 가치를 극대화하려는 과정에서 설정된다.

약쌍대성 정리 (Weak Duality Theorem)

쌍대성 이론에서 가장 기본적인 정리인 약쌍대성 정리는, 원 문제와 쌍대 문제의 해가 존재할 때 쌍대 문제의 해는 원 문제의 해보다 크거나 같음을 보장한다. 이를 수식으로 표현하면 다음과 같다:

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

이는 쌍대 문제의 목적 함수 값이 원 문제의 목적 함수 값에 대한 하한임을 의미하며, 최적해가 아닐 때도 적용된다. 즉, 원 문제의 임의의 해 $\mathbf{x}$ 와 쌍대 문제의 임의의 해 $\mathbf{y}$ 에 대해 항상 이 관계가 성립한다.

약쌍대성 정리의 증명은 라그랑주 승수법을 통해 수행될 수 있으며, 이 증명을 통해 원 문제와 쌍대 문제의 구조적 관계를 명확히 할 수 있다.

강쌍대성 정리 (Strong Duality Theorem)

강쌍대성 정리는 원 문제와 쌍대 문제 모두에서 최적해가 존재할 때, 두 문제의 최적 목적 함수 값이 동일하다는 것을 보장하는 정리이다. 수식으로 표현하면 다음과 같다:

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

여기서 $\mathbf{x}^*$ 는 원 문제의 최적해이고, $\mathbf{y}^*$ 는 쌍대 문제의 최적해이다. 강쌍대성 정리는 선형계획법에서 매우 중요한 성질로, 최적해의 존재를 보장하고 두 문제의 해가 일치한다는 것을 의미한다.

강쌍대성 정리는 단체법(Simplex Method)을 통해서도 설명될 수 있으며, 최적해가 존재하는 경우에만 성립한다. 이때 최적해는 원 문제와 쌍대 문제의 해가 동시에 만족하는 해임을 보장한다.

보완성 조건 (Complementary Slackness Conditions)

쌍대성 문제와 원 문제의 최적해 사이에는 보완성 조건(Complementary Slackness)이 성립한다. 이 조건은 원 문제의 제약 조건과 쌍대 문제의 제약 조건 사이의 관계를 규명한다. 보완성 조건을 통해 최적해를 찾는 데 중요한 정보를 제공하며, 이 조건은 다음과 같이 정의된다.

$y_j ( \mathbf{A} \mathbf{x} - \mathbf{b} )_j = 0 \quad \text{for all} \quad j$

$x_i ( \mathbf{c} - \mathbf{A}^T \mathbf{y} )_i = 0 \quad \text{for all} \quad i$

즉, 원 문제에서 제약 조건이 엄격히 만족하지 않는 경우 (즉, $( \mathbf{A} \mathbf{x} - \mathbf{b} )_j > 0$ ) 쌍대 변수 $y_j$ 는 0이 되어야 하며, 쌍대 문제에서 제약 조건이 엄격히 만족하지 않는 경우 (즉, $( \mathbf{c} - \mathbf{A}^T \mathbf{y} )_i > 0$ ) 원 문제의 변수 $x_i$ 는 0이 되어야 한다. 이는 각각의 제약 조건이 최적해에서 어떤 역할을 하는지 규명하는 데 중요한 역할을 한다.

보완성 조건을 더 자세히 살펴보면 다음과 같다:

만약 $y_j > 0$ 이면, 이는 원 문제의 제약 조건이 정확히 포화 상태에서 만족한다는 것을 의미하며, $( \mathbf{A} \mathbf{x} - \mathbf{b} )_j = 0$ 가 성립해야 한다.
반대로 $x_i > 0$ 이면, 쌍대 문제의 대응 제약 조건이 정확히 포화 상태에서 만족하며, $( \mathbf{c} - \mathbf{A}^T \mathbf{y} )_i = 0$ 가 성립해야 한다.

보완성 조건은 원 문제와 쌍대 문제 사이의 상관관계를 구체화하며, 두 문제의 최적해를 찾는 데 중요한 역할을 한다. 이를 통해 쌍대성 이론의 핵심 개념을 이해할 수 있다.

쌍대성 이론의 해석

쌍대성 문제는 원 문제의 해석을 더욱 풍부하게 만드는 중요한 도구이다. 원 문제에서 우리는 자원의 사용을 최소화하려고 하며, 쌍대 문제는 주어진 자원의 가치를 최대화하려는 문제로 해석된다. 이를 통해 원 문제와 쌍대 문제 사이의 상호 작용을 다음과 같이 해석할 수 있다:

자원 할당의 최적화: 원 문제는 자원을 얼마나 효율적으로 사용할 것인지를 다루며, 쌍대 문제는 그 자원의 가격을 결정한다.
가격과 최적성: 쌍대 문제의 변수 $\mathbf{y}$ 는 자원의 가격으로 해석될 수 있으며, 이는 원 문제에서의 자원의 희소성에 대한 정보를 제공한다.
최적해의 일치: 강쌍대성 정리에 따르면, 원 문제와 쌍대 문제 모두 최적해가 존재할 때, 그 해는 서로 일치한다. 이는 두 문제의 목적 함수 값이 동일함을 의미한다.

쌍대성 이론을 통해 우리는 자원의 효율적인 할당과 가격 결정을 동시에 고려할 수 있게 되며, 최적화 문제를 더욱 심도 있게 이해할 수 있다. 또한 이론적인 연구뿐만 아니라 실질적인 문제 해결에서도 쌍대성 이론은 중요한 역할을 한다.

쌍대성 문제와 관련된 추가적인 분석과 응용은 이후 장에서 다루어질 수 있다.