쌍대 문제의 기본 개념

쌍대 단체법은 선형계획 문제의 쌍대 문제를 풀기 위한 방법이다. 먼저, 쌍대 문제의 정의를 간략히 다뤄야 쌍대 단체법의 원리를 이해할 수 있다. 선형계획 문제에서 기본적인 문제를 1차 계획 문제라 하고, 이에 대응하는 쌍대 문제는 다음과 같은 형태로 정의된다.

\min_{\mathbf{x}} \quad \mathbf{c}^\top \mathbf{x}
\text{subject to} \quad \mathbf{A} \mathbf{x} \geq \mathbf{b}, \quad \mathbf{x} \geq 0
\max_{\mathbf{y}} \quad \mathbf{b}^\top \mathbf{y}
\text{subject to} \quad \mathbf{A}^\top \mathbf{y} \leq \mathbf{c}, \quad \mathbf{y} \geq 0

이때, 원문제와 쌍대 문제는 상호 간에 밀접한 관계를 가지고 있으며, 이 둘 간의 관계를 통해 여러 중요한 성질이 도출된다. 이를 쌍대성 이론이라고 한다.

쌍대 단체법의 동작 원리

쌍대 단체법은 기본적으로 원문제와 쌍대 문제의 관계를 활용하여 해를 구하는 방법이다. 단체법(Simplex Method)이 원문제를 풀기 위한 알고리즘이라면, 쌍대 단체법은 쌍대 문제를 직접적으로 풀기 위한 알고리즘이다.

쌍대 단체법은 다음의 기본적인 과정에 따라 진행된다:

  1. 쌍대 문제로의 변환: 원문제를 먼저 쌍대 문제로 변환하여 시작한다. 원문제에서 사용되는 제약 조건과 목적 함수를 바탕으로 쌍대 문제를 형성한다. 이때, 쌍대 문제의 변수는 원문제에서의 제한 조건에 대응한다.

  2. 초기 기본 해 설정: 쌍대 단체법은 기본적으로 단체법과 유사하게 기본 해(Basic Feasible Solution)에서 시작한다. 이때, 초기 기본 해는 쌍대 문제에서 유효한 해가 되어야 한다.

  3. Pivoting: 쌍대 단체법은 단체법에서와 마찬가지로 피봇팅 과정을 거친다. 피봇팅은 현재 해가 최적해가 아니라고 판단되면, 새로운 해를 찾아가는 과정이다. 이는 쌍대 문제에서의 목적 함수가 개선될 수 있도록 변수 값을 변경하는 단계이다.

피봇팅을 하기 위해서는 최적성 조건과 가능성 조건을 검사한다. 최적성 조건은 현재 해가 최적해인지를 판별하고, 가능성 조건은 현재 해가 유효한 해인지를 확인한다.

  1. 해의 개선: 피봇팅 과정을 통해 해를 개선해 나간다. 이때, 원문제와 쌍대 문제 간의 관계를 이용하여 해를 동시적으로 구할 수 있다.

쌍대 단체법의 특징 중 하나는, 원문제와 쌍대 문제 간의 상호 관계를 활용함으로써 두 문제를 동시에 풀 수 있다는 점이다. 즉, 쌍대 문제를 풀면서 원문제의 해도 자동으로 구해지는 경우가 많다.

변수의 선택과 갱신

쌍대 단체법에서는 각 단계에서 갱신할 변수를 선택하는 것이 중요한데, 이는 블랜드의 규칙(Blan’s Rule) 또는 최소 비용 법칙(Minimum Cost Rule) 등을 사용하여 결정된다. 피봇팅 시 갱신할 변수는 다음과 같은 과정을 거쳐 선택된다:

  1. 초기 해의 최적성 검사: 현재의 해가 최적해인지 판단하기 위해 쌍대 변수의 값을 확인한다. 쌍대 해에서 가장 개선될 수 있는 변수를 선택하여 피봇팅을 진행한다.

  2. 비가능성 제거: 쌍대 단체법에서는 비가능해가 발생할 수 있다. 이를 해결하기 위해 비가능성을 제거하고 가능한 해 영역 안에서 최적화를 진행한다.

제약 조건의 역할

쌍대 단체법에서는 원문제의 제약 조건이 쌍대 문제의 해에 직접적인 영향을 미친다. 따라서 제약 조건의 변형이나 추가는 쌍대 문제의 해에 변화를 줄 수 있으며, 이 과정에서 라그랑주 승수(Lagrange Multiplier)가 사용될 수 있다.

쌍대 단체법에서의 피봇팅 절차

피봇팅 과정은 쌍대 단체법의 핵심 단계 중 하나로, 현재의 해를 개선하여 최적 해에 도달하는 데 사용된다. 피봇팅 절차는 크게 다음과 같은 단계로 이루어진다:

  1. 진입 변수(Entering Variable)의 선택:
  2. 진입 변수는 피봇팅 과정에서 새로운 기본 변수로 선택되는 변수이다. 쌍대 단체법에서는 쌍대 문제의 해를 개선할 수 있는 변수를 진입 변수로 선택한다.
  3. 이를 선택하기 위해 최적성 조건을 검사하며, 만약 현재의 해가 최적 해가 아니라면, 개선이 가능한 변수를 찾아 진입 변수로 선택한다.

진입 변수의 선택 기준은 아래와 같다:

c_j - \sum_{i} A_{ij} y_i > 0

이 조건을 만족하는 변수 j를 진입 변수로 선택한다.

  1. 이탈 변수(Leaving Variable)의 선택:
  2. 이탈 변수는 피봇팅 과정에서 기본 해를 유지하기 위해 기존의 기본 변수 중 하나를 제거하는 변수이다.
  3. 이탈 변수는 새로운 진입 변수로 인해 어떤 변수가 더 이상 기본 해의 일부분으로 남을 수 없을 때 선택된다.
  4. 이때 가능성 조건을 검사하여 이탈 변수를 선택한다. 가능성 조건은 현재의 해가 여전히 유효한지를 확인하는 절차이다.

이탈 변수는 아래 조건을 만족하는 변수로 선택된다:

\frac{b_i}{A_{ij}} \quad \text{where} \quad A_{ij} > 0

위 조건을 만족하는 최소의 값을 가지는 i가 이탈 변수가 된다.

  1. 피봇(Pivoting) 과정:
  2. 진입 변수와 이탈 변수가 결정되면 피봇팅을 수행하여 해를 갱신한다.
  3. 피봇팅은 Simplex Tableau에서 행렬 연산을 통해 새로운 기본 해를 구하는 과정이다. 이때, 행렬의 일부를 수정하고 나머지는 고정한 채로 행렬의 요소들을 조정한다.
  4. 구체적으로, 진입 변수와 이탈 변수가 결정된 후에는 새로운 기본 해를 계산하기 위해 행렬의 피봇을 수행한다. 이는 선형 대수학의 피봇팅과 유사한다.

피봇팅 이후, 새로운 기본 변수 집합이 생성되며, 이 과정이 반복된다.

최적성 조건과 가능성 조건

쌍대 단체법에서는 두 가지 중요한 조건, 즉 최적성 조건과 가능성 조건이 충족되어야 한다.

  1. 최적성 조건:
  2. 현재의 해가 최적해인지를 결정하는 조건이다. 만약 이 조건이 충족되지 않으면 추가적인 피봇팅이 필요하다.
  3. 최적성 조건은 다음과 같다:
c_j - \sum_{i} A_{ij} y_i \leq 0 \quad \forall j

이 조건을 만족하면 현재의 해는 최적해로 간주된다.

  1. 가능성 조건:
  2. 해가 여전히 유효한지를 검사하는 조건이다. 이 조건이 충족되지 않으면 피봇팅을 통해 비가능한 해를 제거해야 한다.
  3. 가능성 조건은 다음과 같다:
b_i - \sum_{j} A_{ij} x_j \geq 0 \quad \forall i

이 조건을 만족하면 현재의 해는 유효한 해로 간주된다.

피봇팅 과정은 최적성 조건과 가능성 조건을 충족시키기 위한 반복적인 과정이며, 최적의 해에 도달할 때까지 이 절차가 계속된다.

Simplex Tableau에서의 표현

쌍대 단체법에서 해를 나타내는 일반적인 도구는 Simplex Tableau이다. 이는 단체법에서도 사용되는 표 형식의 방식으로, 각 단계에서의 기본 해와 피봇팅 과정에서 사용된다.

\begin{array}{c|ccccc|c} & x_1 & x_2 & \cdots & x_n & \text{자유 변수} & \text{목적 함수 값} \\ \hline \text{제약 1} & a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ \text{제약 2} & a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \text{제약 m} & a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \\ \hline \text{목적 함수} & c_1 & c_2 & \cdots & c_n & z \end{array}

여기서, 각 행은 제약 조건을 나타내며, 열은 각 변수의 계수와 제약 조건의 상수 부분을 나타낸다. 또한, 마지막 행은 목적 함수를 나타내며, z는 현재의 목적 함수 값이다.

이 Simplex Tableau는 각 피봇팅 단계에서 갱신되며, 쌍대 단체법이 진행될 때마다 변경된 해를 시각적으로 표현할 수 있다.

퇴행 문제와 쌍대 단체법

쌍대 단체법에서도 단체법과 마찬가지로 퇴행(Degeneracy) 현상이 발생할 수 있다. 퇴행이란 현재의 기본 해가 여러 기본 변수로 표현될 수 있어, 여러 단계에 걸쳐 피봇팅을 수행하더라도 목적 함수 값이 개선되지 않는 경우를 의미한다.

퇴행 문제는 두 가지 유형으로 나뉜다:

  1. 원문제에서의 퇴행:
  2. 원문제에서 퇴행이 발생하는 경우, 기본 해에서 기본 변수 중 일부가 0인 상황이 된다. 이는 기본 해가 극점에 위치하지만 여러 가능한 경로 중 하나만 선택되는 상황을 초래한다.

  3. 이 경우, 쌍대 단체법은 퇴행하는 상태에서 계속해서 피봇팅을 수행하게 되며, 계산이 효율적이지 않거나 무한 루프에 빠질 수 있다.

  4. 쌍대 문제에서의 퇴행:

  5. 쌍대 문제에서도 퇴행이 발생할 수 있다. 이는 쌍대 문제에서 여러 극점이 동일한 목적 함수 값을 가질 때 나타난다.
  6. 쌍대 문제에서 퇴행이 발생하는 경우, 쌍대 단체법은 피봇팅을 거듭하더라도 목적 함수 값의 개선이 일어나지 않는 현상을 겪습니다.

퇴행 해결 방법

퇴행 문제를 해결하기 위한 대표적인 방법 중 하나는 블랜드의 규칙(Blan's Rule)을 사용하는 것이다. 블랜드의 규칙은 피봇팅할 변수를 선택하는 과정에서 무한 루프를 방지하고 퇴행 문제를 최소화하는 방법으로 다음과 같은 규칙을 따른다:

이 방법을 사용하면 퇴행 상태에서 무한히 반복되는 것을 막고, 알고리즘이 수렴하도록 돕는다.

쌍대 단체법의 종료 조건

쌍대 단체법은 아래의 종료 조건을 충족할 때까지 피봇팅을 반복한다:

  1. 최적성 조건 충족:
  2. 피봇팅을 반복한 후, 더 이상 최적성 조건을 위반하는 변수가 없을 때 알고리즘은 종료된다. 최적성 조건은 앞서 정의한 바와 같이, 모든 변수에 대해 아래 식이 만족되어야 한다:
c_j - \sum_{i} A_{ij} y_i \leq 0 \quad \forall j

이 조건이 충족되면 더 이상 개선할 수 있는 해가 없으며, 현재 해가 최적 해로 판단된다.

  1. 가능성 조건 충족:
  2. 가능성 조건이 충족되면 해가 유효한 해로 판단되며, 알고리즘은 종료된다. 즉, 해가 제약 조건을 만족하면서 목적 함수 값이 최적일 때 종료된다. 가능성 조건은 아래와 같이 나타낸다:
b_i - \sum_{j} A_{ij} x_j \geq 0 \quad \forall i
  1. 해의 수렴:
  2. 쌍대 단체법은 피봇팅을 반복하는 과정에서 목표 해에 점점 더 가까워지며, 최종적으로 수렴하는 해에 도달한다. 이 수렴 상태는 최적성 조건과 가능성 조건이 동시에 충족되는 경우이다.

쌍대 단체법의 응용

쌍대 단체법은 주로 다음과 같은 상황에서 활용된다:

다이어그램을 통한 절차 표현

쌍대 단체법의 절차를 시각적으로 이해하기 위해 다이어그램을 사용할 수 있다. 아래는 쌍대 단체법의 피봇팅 과정을 시각적으로 표현한 예시이다:

graph TD A[쌍대 문제 정의] --> B[초기 기본 해 설정] B --> C[최적성 조건 검사] C -->|조건 만족| D[최적 해 도출] C -->|조건 미충족| E[피봇팅] E --> F[이탈 변수 선택] F --> G[진입 변수 선택] G --> H[해 갱신] H --> C

이 다이어그램은 쌍대 단체법이 최적성 조건을 만족할 때까지 반복되는 과정을 시각적으로 나타낸다. 최적성 조건이 만족되면 최적 해가 도출되며, 그렇지 않으면 피봇팅을 계속하여 해를 개선한다.

퇴행 문제와 쌍대 단체법

쌍대 단체법에서도 단체법과 마찬가지로 퇴행(Degeneracy) 현상이 발생할 수 있다. 퇴행이란 현재의 기본 해가 여러 기본 변수로 표현될 수 있어, 여러 단계에 걸쳐 피봇팅을 수행하더라도 목적 함수 값이 개선되지 않는 경우를 의미한다.

퇴행 문제는 두 가지 유형으로 나뉜다:

  1. 원문제에서의 퇴행:
  2. 원문제에서 퇴행이 발생하는 경우, 기본 해에서 기본 변수 중 일부가 0인 상황이 된다. 이는 기본 해가 극점에 위치하지만 여러 가능한 경로 중 하나만 선택되는 상황을 초래한다.

  3. 이 경우, 쌍대 단체법은 퇴행하는 상태에서 계속해서 피봇팅을 수행하게 되며, 계산이 효율적이지 않거나 무한 루프에 빠질 수 있다.

  4. 쌍대 문제에서의 퇴행:

  5. 쌍대 문제에서도 퇴행이 발생할 수 있다. 이는 쌍대 문제에서 여러 극점이 동일한 목적 함수 값을 가질 때 나타난다.
  6. 쌍대 문제에서 퇴행이 발생하는 경우, 쌍대 단체법은 피봇팅을 거듭하더라도 목적 함수 값의 개선이 일어나지 않는 현상을 겪습니다.

퇴행 해결 방법

퇴행 문제를 해결하기 위한 대표적인 방법 중 하나는 블랜드의 규칙(Blan's Rule)을 사용하는 것이다. 블랜드의 규칙은 피봇팅할 변수를 선택하는 과정에서 무한 루프를 방지하고 퇴행 문제를 최소화하는 방법으로 다음과 같은 규칙을 따른다:

이 방법을 사용하면 퇴행 상태에서 무한히 반복되는 것을 막고, 알고리즘이 수렴하도록 돕는다.

쌍대 단체법의 종료 조건

쌍대 단체법은 아래의 종료 조건을 충족할 때까지 피봇팅을 반복한다:

  1. 최적성 조건 충족:
  2. 피봇팅을 반복한 후, 더 이상 최적성 조건을 위반하는 변수가 없을 때 알고리즘은 종료된다. 최적성 조건은 앞서 정의한 바와 같이, 모든 변수에 대해 아래 식이 만족되어야 한다:
c_j - \sum_{i} A_{ij} y_i \leq 0 \quad \forall j

이 조건이 충족되면 더 이상 개선할 수 있는 해가 없으며, 현재 해가 최적 해로 판단된다.

  1. 가능성 조건 충족:
  2. 가능성 조건이 충족되면 해가 유효한 해로 판단되며, 알고리즘은 종료된다. 즉, 해가 제약 조건을 만족하면서 목적 함수 값이 최적일 때 종료된다. 가능성 조건은 아래와 같이 나타낸다:
b_i - \sum_{j} A_{ij} x_j \geq 0 \quad \forall i
  1. 해의 수렴:
  2. 쌍대 단체법은 피봇팅을 반복하는 과정에서 목표 해에 점점 더 가까워지며, 최종적으로 수렴하는 해에 도달한다. 이 수렴 상태는 최적성 조건과 가능성 조건이 동시에 충족되는 경우이다.

쌍대 단체법의 응용

쌍대 단체법은 주로 다음과 같은 상황에서 활용된다:

다이어그램을 통한 절차 표현

쌍대 단체법의 절차를 시각적으로 이해하기 위해 다이어그램을 사용할 수 있다. 아래는 쌍대 단체법의 피봇팅 과정을 시각적으로 표현한 예시이다:

graph TD A[쌍대 문제 정의] --> B[초기 기본 해 설정] B --> C[최적성 조건 검사] C -->|조건 만족| D[최적 해 도출] C -->|조건 미충족| E[피봇팅] E --> F[이탈 변수 선택] F --> G[진입 변수 선택] G --> H[해 갱신] H --> C

이 다이어그램은 쌍대 단체법이 최적성 조건을 만족할 때까지 반복되는 과정을 시각적으로 나타낸다. 최적성 조건이 만족되면 최적 해가 도출되며, 그렇지 않으면 피봇팅을 계속하여 해를 개선한다.