정수 계획법 (Integer Programming)

정수 계획법 (Integer Programming)

정수 계획법(Integer Programming, IP)은 자원 배분, 일정 계획, 네트워크 설계, 생산 계획 등 다양한 실세계 문제를 해결하는 데 사용되는 강력한 최적화 기법입니다. 정수 계획법은 의사결정 변수가 정수로 제한되는 최적화 문제를 다루며, 이러한 문제는 일반적으로 NP-난해(NP-hard) 문제로 분류됩니다.

기본 개념

정수 계획법의 주요 구성 요소는 다음과 같습니다:

1. 의사결정변수(Decision Variables): 문제의 결정을 나타내는 변수로서 정수 값을 가집니다.
2. 목적함수(Objective Function): 최적화하고자 하는 대상입니다. 최대화하거나 최소화할 수 있습니다.
3. 제약조건(Constraints): 의사결정변수가 만족해야 하는 조건들입니다. 이는 등식 또는 부등식 형태로 주어집니다.

정수 계획법의 공식화

일반적인 정수 계획법 문제는 다음과 같이 공식화할 수 있습니다:

$$ \text{Maximize or Minimize } ; c^T x $$
$$ \text{subject to } ; Ax \leq b $$
$$ x \in \mathbb{Z}^n $$

여기서 $ x $는 정수 변수 벡터, $ c $는 계수 벡터, $ A $는 계수 행렬, $ b $는 상수 벡터입니다.

문제 유형

정수 계획법은 문제의 성격에 따라 다음과 같이 분류할 수 있습니다:

1. 순수 정수 계획법(Pure Integer Programming): 모든 변수들이 정수인 경우.
2. 혼합 정수 계획법(Mixed Integer Programming, MIP): 일부 변수만 정수로 제한되는 경우.
3. 0-1 정수 계획법(Binary Integer Programming): 변수들이 0 또는 1의 값을 가지는 경우.

예제: 공장 생산 계획 문제

구체적인 예제를 통해 정수 계획법의 적용을 살펴보겠습니다. 두 가지 제품을 생산하는 공장을 고려해 봅시다. 각 제품의 생산 비용, 시간, 이익, 그리고 제한된 자원이 주어져 있습니다. 목표는 이익을 최대화하는 것입니다.

데이터 설정:

• 제품 1: 한 단위 생산에 3시간, 이익 40
• 제품 2: 한 단위 생산에 5시간, 이익 70
• 총 가용 시간: 40시간
• 총 가용 재료: 30단위

문제 공식화:

$$ \text{Maximize } ; 40x_1 + 70x_2 $$
$$ \text{subject to} $$
$$ 3x_1 + 5x_2 \leq 40 $$
$$ 2x_1 + 4x_2 \leq 30 $$
$$ x_1, x_2 \geq 1 $$
$$ x_1, x_2 \in \mathbb{Z} $$

여기서 $$ x_1 $$과 $$ x_2 $$는 각각 제품 1과 제품 2의 생산 수량을 나타냅니다.

고급 예제: 이중 배낭 문제

더 복잡한 문제로 "이중 배낭 문제(Double Knapsack Problem)"를 살펴보겠습니다. 두 개의 배낭이 있고, 각 배낭에는 최대 용량이 있습니다. 여러 개의 아이템이 있으며, 각 아이템은 특정한 무게와 가치를 가집니다. 목표는 두 배낭에 아이템들을 배치하여 총 가치를 최대화하는 것입니다.

데이터 설정:

• 3개의 아이템: $ A, B, C $
• 아이템의 가치: $ v = [60, 100, 120] $
• 아이템의 무게: $ w = [10, 20, 30] $
• 배낭의 최대 용량: $ W = [50, 50] $

문제 공식화:

$$ \text{Maximize } ; 60x_{A1} + 60x_{A2} + 100x_{B1} + 100x_{B2} + 120x_{C1} + 120x_{C2} $$
$$ \text{subject to} $$
$$ x_{A1} + x_{A2} \leq 1 $$
$$ x_{B1} + x_{B2} \leq 1 $$
$$ x_{C1} + x_{C2} \leq 1 $$
$$ 10x_{A1} + 20x_{B1} + 30x_{C1} \leq 50 $$
$$ 10x_{A2} + 20x_{B2} + 30x_{C2} \leq 50 $$
$$ x_{A1}, x_{A2}, x_{B1}, x_{B2}, x_{C1}, x_{C2} \in {0, 1} $$

해결 방법

정수 계획 문제는 다양한 알고리즘을 통해 해결할 수 있습니다:

1. 분지 한계법(Branch and Bound): 문제를 작은 하위 문제로 나누어 해결하는 방법.
2. 분할 평면법(Cutting Plane Method): 연속 최적화 문제에서 불가능한 부분을 잘라내어 해결하는 방법.
3. 휴리스틱 알고리즘 및 메타휴리스틱: 근사해를 찾기 위한 방법들로서 유전 알고리즘, 시뮬레이티드 어닐링 등이 있습니다.