선형 프로그래밍(Linear Programming, LP)은 선형 부등식 제약 조건 하에서 선형 목적 함수를 최대화 또는 최소화하는 최적화 문제다. 산업공학, 운영 연구, 경쟁 프로그래밍에서 광범위하게 활용된다.
표준형
$$\max \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} \le \mathbf{b},; \mathbf{x} \ge 0$$
가능 해 집합(볼록 다면체)의 꼭짓점(vertex)을 이동하며 최적해를 탐색한다.
python
def simplex(c, A, b):
"""
최대화: c^T x, 제약: Ax <= b, x >= 0
반환: (최적값, 최적 x 벡터) 또는 None (불가능/무한)
"""
import numpy as np
m, n = len(A), len(c)
# 슬랙 변수 추가
tab = np.zeros((m + 1, n + m + 1))
tab[:m, :n] = A
tab[:m, n:n+m] = np.eye(m)
tab[:m, -1] = b
tab[-1, :n] = -np.array(c)
basis = list(range(n, n + m))
for _ in range(1000):
# 피벗 열: 목적 함수 행에서 가장 음수
col = np.argmin(tab[-1, :-1])
if tab[-1, col] >= -1e-9:
break # 최적
# 피벗 행: 최소 비율 테스트
ratios = []
for i in range(m):
if tab[i, col] > 1e-9:
ratios.append((tab[i, -1] / tab[i, col], i))
if not ratios:
return None # 무한
_, row = min(ratios)
# 피벗
tab[row] /= tab[row, col]
for i in range(m + 1):
if i != row:
tab[i] -= tab[i, col] * tab[row]
basis[row] = col
x = np.zeros(n + m)
for i, b_idx in enumerate(basis):
x[b_idx] = tab[i, -1]
return tab[-1, -1], x[:n]
import numpy as np
c = [5, 4]
A = [[6, 4], [1, 2], [-1, 0], [0, -1]]
b = [24, 6, 0, 0]
print(simplex(c, A, b))
LP vs 정수 프로그래밍
| 항목 | LP | IP (정수 프로그래밍) |
|---|
| 변수 | 실수 | 정수 |
| 복잡도 | 다항 시간 | NP-Hard |
| 알고리즘 | Simplex, Interior Point | Branch & Bound, 절단면 |
쌍대성 (Duality)
모든 LP 문제에는 쌍대 문제가 존재하며, 강한 쌍대성 정리(Strong Duality)에 의해 원 문제와 쌍대 문제의 최적값이 같다.
관련 개념
