선형 계획법 (Linear Programming)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 3분 · 896자/단어 #algorithm #math #linear-programming #optimization

정의

선형 계획법 (Linear Programming, LP) 은 선형 부등식 제약 조건 아래에서 선형 목적 함수를 최적화 (최대화/최소화) 하는 문제. 표준형:

maximize    c^T x
subject to  A x ≤ b,  x ≥ 0

변수 x ∈ ℝⁿ, 계수 c ∈ ℝⁿ, 행렬 A ∈ ℝ^{m×n}, 우변 b ∈ ℝ^m. 모든 식이 선형 (1차).

문제 상황과 동기

많은 최적화 문제가 선형 부등식 체계로 표현 가능. 최대 이익, 최소 비용, 자원 배분.
naive: 변수 공간을 격자로 샘플링. 차원이 높으면 불가능.
simplex method: 다면체의 꼭짓점을 따라 이동. 실무에서 다항 시간에 수렴.
ellipsoid / interior-point: 이론적 다항 시간 보장.

핵심 통찰: 최적해는 항상 feasible region (실행 가능 영역) 의 꼭짓점 (basic feasible solution) 에 존재.

시각화

핵심 아이디어

Feasible region {x | Ax ≤ b, x ≥ 0} 은 convex polytope (볼록 다면체). 목적 함수 c^T x 의 등고면 (hyperplane) 을 c 방향으로 밀어서 polytope 과 접하는 점이 최적해.

Basic feasible solution (BFS): n 개의 변수 중 m 개가 binding (등호). 나머지는 0. 꼭짓점.
Simplex pivot: 한 BFS 에서 인접 BFS 로 이동. 목적값이 개선되는 방향.
Degeneracy: 이동해도 목적값 변화 없음. cycling 가능 → Bland’s rule.

LP 는 항상 다음 중 하나:

최적해 존재 (bounded + feasible)
Unbounded (목적 함수를 무한히 키울 수 있음)
Infeasible (제약을 동시에 만족 못 함)

알고리즘

Simplex (tableau form):
1. 표준형으로 변환 (slack 변수 도입)
2. 초기 BFS 찾기 (Phase I: auxiliary LP)
3. while true:
   a. entering variable 선택 (most negative reduced cost)
   b. leaving variable 선택 (minimum ratio test)
   c. pivot (행 연산으로 entering 을 basic 으로)
4. unbounded / infeasible / optimal 판별

2D 시각화 슈도코드:
1. feasible polytope 의 모든 constraint 나열
2. 각 꼭짓점 = 2개 constraint 의 교차점
3. 목적 함수 c^T x 의 기울기 방향으로
   가장 먼 꼭짓점이 최적해

구현

// 기본 simplex (tableau) - 표준형 max c^T x s.t. Ax <= b, x >= 0
#include <bits/stdc++.h>
using namespace std;
using ld = double;
const ld EPS = 1e-9;
struct Simplex {
  int n, m; // n vars, m constraints (excluding x>=0)
  vector<vector<ld>> a; // tableau: rows 0..m-1, cols 0..n+m
  vector<int> basis;    // basis[i] = index of basic var for row i
  Simplex(vector<vector<ld>> A, vector<ld> b, vector<ld> c) {
      n = c.size(); m = b.size();
      a.assign(m, vector<ld>(n + m + 1, 0));
      for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) a[i][j] = A[i][j];
          a[i][n + i] = 1; // slack 변수
          a[i][n + m] = b[i];
      }
      basis.resize(m);
      for (int i = 0; i < m; i++) basis[i] = n + i; // 초기 basis = slacks
      a.emplace_back(n + m + 1, 0);
      for (int j = 0; j < n; j++) a[m][j] = -c[j]; // objective row
  }
  void pivot(int r, int c) {
      ld div = a[r][c];
      for (int j = 0; j <= n + m; j++) a[r][j] /= div;
      for (int i = 0; i <= m; i++) {
          if (i == r) continue;
          ld mul = a[i][c];
          for (int j = 0; j <= n + m; j++) a[i][j] -= mul * a[r][j];
      }
      basis[r] = c;
  }
  bool solve() {
      while (true) {
          int col = -1;
          for (int j = 0; j < n + m; j++) {
              if (a[m][j] < -EPS) { col = j; break; }
          }
          if (col == -1) break; // optimal
          int row = -1;
          ld min_ratio = 1e30;
          for (int i = 0; i < m; i++) {
              if (a[i][col] > EPS) {
                  ld r = a[i][n + m] / a[i][col];
                  if (r < min_ratio) { min_ratio = r; row = i; }
              }
          }
          if (row == -1) return false; // unbounded
          pivot(row, col);
      }
      return true;
  }
  ld get_value() { return -a[m][n + m]; }
};
int main() {
  // 예: max x + y s.t. x + 2y <= 4, 2x + y <= 5, x, y >= 0
  vector<vector<ld>> A = {{1, 2}, {2, 1}};
  vector<ld> b = {4, 5};
  vector<ld> c = {1, 1};
  Simplex lp(A, b, c);
  if (lp.solve()) {
      cout << fixed << setprecision(6) << lp.get_value() << "\n";
  } else cout << "Unbounded\n";
}

# Simplex (tableau form) - 단순 구현
import sys
EPS = 1e-9
class Simplex:
  def __init__(self, A, b, c):
      self.n = len(c)   # original variables
      self.m = len(b)   # constraints
      self.a = [row[:] + [0]*self.m + [b[i]]
                for i, row in enumerate(A)]
      # slack variables
      for i in range(self.m):
          self.a[i][self.n + i] = 1
      self.basis = list(range(self.n, self.n + self.m))
      # objective row
      obj = [-c[j] for j in range(self.n)] + [0]*self.m + [0]
      self.a.append(obj)
  def pivot(self, r, c):
      div = self.a[r][c]
      self.a[r] = [v / div for v in self.a[r]]
      for i in range(self.m + 1):
          if i == r: continue
          mul = self.a[i][c]
          self.a[i] = [self.a[i][j] - mul * self.a[r][j]
                       for j in range(self.n + self.m + 1)]
      self.basis[r] = c
  def solve(self):
      while True:
          col = next((j for j in range(self.n + self.m)
                      if self.a[self.m][j] < -EPS), None)
          if col is None: break
          row = None
          min_r = float("inf")
          for i in range(self.m):
              if self.a[i][col] > EPS:
                  r = self.a[i][self.n + self.m] / self.a[i][col]
                  if r < min_r: min_r, row = r, i
          if row is None: return False
          self.pivot(row, col)
      return True
  def value(self):
      return -self.a[self.m][self.n + self.m]

A = [[1, 2], [2, 1]]
b = [4, 5]
c = [1, 1]
lp = Simplex(A, b, c)
print(lp.solve())
print(f"{lp.value():.6f}")

결과

1
3.000000

복잡도

항목	값
시간 (Simplex, 평균)	O(m · n²) 실제 (practical)
시간 (Simplex, 최악)	지수 (Klee-Minty 예제)
시간 (Interior Point)	O(n^3.5 · L) 다항 시간
공간	O(m · n) (tableau)

L = 입력 비트 수. LP 는 P 문제 (ellipsoid method, 1979). Simplex 는 exponential 이지만 실무에서 가장 빠름.

변형 / 활용

형태	설명
정수 계획법 (ILP)	x ∈ ℤⁿ. NP-hard. LP relaxation 으로 근사.
2단계 Simplex	Phase I (초기 BFS) + Phase II (최적화).
Dual Simplex	dual 문제에서 직접 pivot. primal 이 infeasible 할 때 유리.
Network Simplex	유량/최단 경로 문제에 특화된 Simplex.
LP relaxation	ILP 의 정수 조건을 실수로 완화.

대표 PS 활용: 최대 유량은 LP 의 special case. Min-cost flow 도 LP.

함정

1. 수치 안정성

Tableau pivot 시 분모가 0에 가까우면 폭발. EPS=1e-9 이상의 tolerance 필수. 고정밀도가 필요한 경우 Fraction 타입 고려.

2. Cycling

Degenerate BFS 에서 같은 tableau 순환 가능. Bland’s rule (가장 작은 인덱스의 변수 선택) 으로 방지.

3. Unbounded 처리

col 은 있지만 row 를 찾지 못하면 unbounded. 목적 함수가 무한히 커질 수 있음.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 812	Milk Scheduling	-	kokoa-lab
BOJ 1294	문자열 장식	-	kokoa-lab
BOJ 1060	좋은 수	-	kokoa-lab
BOJ 2280	파일 합치기	-	kokoa-lab

참고

이 글의 용어 (3개)

네트워크 유량 (Network Flow)algorithm: 정의 네트워크 유량 (Network Flow) 은 방향 그래프 G = (V, E) 에서 각 간선 (u, v) 의 용량 (capacity) c(u, v) 가 주어질 때, 소스 s …
쌍대성 (Duality)algorithm: 정의 쌍대성 (Duality) 은 하나의 최적화 문제 (Primal) 에 항상 대응되는 또 다른 최적화 문제 (Dual) 가 존재한다는 원리. LP 에서 Primal-Dual 쌍…
최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF)algorithm: 정의 최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF) 은 각 간선에 용량(capacity)과 단위 비용(cost)이 주어질 때, 최대 유량을 달성하는 여러 방…

이 개념을 다룬 위키 페이지 (1)

wiki쌍대성 (Duality)