정수 계획법 (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\le 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\le 40$$
$$2x_1+4x_2\le 30$$
$$x_1,x_2\ge 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}\le 1$$
$$x_{B1}+x_{B2}\le 1$$
$$x_{C1}+x_{C2}\le 1$$
$$10x_{A1}+20x_{B1}+30x_{C1}\le 50$$
$$10x_{A2}+20x_{B2}+30x_{C2}\le 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. 휴리스틱 알고리즘 및 메타휴리스틱: 근사해를 찾기 위한 방법들로서 유전 알고리즘, 시뮬레이티드 어닐링 등이 있습니다.