8. 선형 프로그래밍 (LP, Linear Programming) — 심플렉스법

핵심 인사이트 (3줄 요약)

1. 본질: LP (Linear Programming, 선형 계획법) 는 목적 함수와 제약 조건이 모두 선형인 최적화 — 가능 영역이 볼록 다면체(Polytope)이고 최적해는 반드시 꼭짓점에 존재한다.
2. 가치: 심플렉스법 (Simplex Method) 이 실용적으로 빠르고, 내점법 (Interior Point Method) 이 이론적으로 다항식 복잡도를 보장하며, 쌍대 LP가 경제 해석과 알고리즘 분석에 활용된다.
3. 판단 포인트: LP 완화 (LP Relaxation) — 정수 계획법을 LP로 풀어 하한 경계 획득, 분기 한정법 (Branch & Bound) 과 결합해 정수 최적화의 기반이 된다.

Ⅰ. 개요 및 필요성

표준형 LP (Standard Form Linear Program):

maximize   cᵀx
subject to Ax ≤ b
           x ≥ 0

• c ∈ ℝⁿ: 목적 함수 계수 벡터
• A ∈ ℝ^{m×n}: 제약 계수 행렬
• b ∈ ℝ^m: 제약 우변 벡터
• x ∈ ℝⁿ: 결정 변수 (Decision Variables)

LP 해의 존재성

📢 섹션 요약 비유: LP의 가능 영역은 "규칙으로 만든 방"이다 — 각 제약이 벽이 되어 방을 만들고, 최적해는 항상 방의 모서리(꼭짓점)에 위치한다.

Ⅱ. 아키텍처 및 핵심 원리

2D LP 예시와 심플렉스 경로

maximize  5x₁ + 4x₂
s.t.      6x₁ + 4x₂ ≤ 24
          x₁ + 2x₂ ≤ 6
          x₁, x₂ ≥ 0

x₂
 6 ┤         C(0,3)
   │        /
 3 ┤       /  D(3,1.5)
   │      / ╱
   │     /╱
 0 └────B(4,0)──────► x₁
  O(0,0)    4

꼭짓점:  O(0,0): 목적값=0
         B(4,0): 목적값=20
         D(3,1.5): 목적값=21 ← 최적!
         C(0,3): 목적값=12

심플렉스법: O → B → D (꼭짓점을 따라 이동하며 목적값 증가).

심플렉스 알고리즘 (Simplex Method)

1. 초기 기저 가능해 (BFS) 설정 (꼭짓점)
2. 인접 꼭짓점 중 목적값 향상 방향 선택 (피벗 열 선택)
3. 비율 테스트로 피벗 행 결정 (가능성 유지)
4. 기저 교환 (Pivot)
5. 향상 가능한 인접 꼭짓점 없으면 → 최적해

복잡도:

• 최악: 지수 시간 (Klee-Minty 예시: 모든 꼭짓점 방문)
• 실용: 평균 다항식 시간 (m+n개 꼭짓점 정도 탐색)

내점법 (Interior Point Method)

바리어 함수 (Barrier Function) 를 이용해 가능 영역 내부를 통과:

min f(x) s.t. hⱼ(x) ≤ 0
→ min_{t} f(x) - (1/t)Σⱼ log(-hⱼ(x))   (Logarithmic Barrier)

t → ∞ 이면 원 문제에 수렴

카마르카 (Karmarkar) 알고리즘 (1984): 최초 다항식 시간 LP 알고리즘. 현대 내점법: O(n³·√n)이지만 실용적으로는 심플렉스와 비교하며 선택.

LP 쌍대 문제 (LP Duality)

원 문제 (Primal):

max cᵀx,   s.t. Ax ≤ b, x ≥ 0

듀얼 문제 (Dual):

min bᵀy,   s.t. Aᵀy ≥ c, y ≥ 0

강한 쌍대성 (Strong Duality): 원 문제 최적값 = 듀얼 문제 최적값

경제 해석: 듀얼 변수 y* = 자원의 잠재 가격 (Shadow Price)

📢 섹션 요약 비유: 심플렉스법은 "방 모서리 탐색기"다 — 방(가능 영역)의 한 모서리에서 시작해 목적값이 증가하는 인접 모서리로 계속 이동하다가, 더 좋은 모서리가 없으면 멈춘다.

Ⅲ. 비교 및 연결

심플렉스 vs 내점법 비교

네트워크 플로우 LP

최단 경로, 최대 플로우, 최소 비용 플로우 모두 LP로 표현 가능:

min  Σ_{(i,j)∈E} cᵢⱼ xᵢⱼ
s.t. Σⱼ xᵢⱼ - Σⱼ xⱼᵢ = bᵢ  ∀i  (유량 보존)
     0 ≤ xᵢⱼ ≤ uᵢⱼ            ∀(i,j) (용량 제약)

네트워크 LP의 계수 행렬 A는 완전 단모듈 (Totally Unimodular) → LP 해가 자동으로 정수!

LP 완화와 정수 계획법

IP (정수 계획법):      LP 완화 (LP Relaxation):
min cᵀx                min cᵀx
s.t. Ax ≤ b            s.t. Ax ≤ b
     x ∈ {0,1}ⁿ              0 ≤ x ≤ 1  (정수 제약 완화)

LP 완화 목적값 ≤ IP 최적값 (하한 경계)
LP 해가 정수 → IP 최적해 발견!
LP 해가 비정수 → 분기 한정법 적용

📢 섹션 요약 비유: LP 완화는 "일단 분수도 허용"이다 — 정수만 허용하는 어려운 문제를 분수도 허용하는 쉬운 LP로 먼저 풀어 하한 경계를 얻는다.

Ⅳ. 실무 적용 및 기술사 판단

생산 계획 LP

공장에서 제품 A, B를 생산. 자원: 원자재 100kg, 노동력 80시간

max  5xA + 4xB   (이익 최대화)
s.t. 2xA + xB  ≤ 100   (원자재)
     xA  + 2xB ≤ 80    (노동력)
     xA, xB ≥ 0

꼭짓점 평가 → 최적 생산량 결정
듀얼 변수 → 원자재/노동력 단위당 잠재 가치

LP 솔버 도구

기술사 판단 포인트

1. "LP의 최적해는 왜 항상 꼭짓점에?" → 목적 함수가 선형 → 기울기 방향으로 가면 반드시 가능 영역 경계(꼭짓점)에서 최적
2. "심플렉스 최악 경우는?" → 지수 시간 (Klee-Minty 예시), 실용적으로는 빠름
3. "LP 쌍대의 Shadow Price 의미는?" → 해당 제약을 1단위 완화할 때 목적 함수 증가량

📢 섹션 요약 비유: LP 솔버의 Shadow Price는 "자원의 경매 가격"이다 — 제약 자원(노동력, 원자재) 한 단위를 추가로 구입할 때 얼마까지 낼 의향이 있는지를 수치로 보여준다.

Ⅴ. 기대효과 및 결론

LP는 20세기 가장 영향력 있는 최적화 기법 중 하나 — 항공 스케줄링, 물류 최적화, 금융 포트폴리오, 전력망 운영의 핵심이다.

실용적 활용 현황:

• 항공사 운항 스케줄 최적화: LP + 정수 계획법
• 구글 광고 입찰: LP 기반 실시간 최적화
• 전력망 경제 급전: LP 매 5분 실행
• 물류 라우팅: LP + 네트워크 플로우

딥러닝 시대에도 LP는 해석 가능하고 전역 최적이 보장되므로 규제 요구사항이 있는 산업(금융, 의료)에서 여전히 핵심이다.

📢 섹션 요약 비유: LP는 "완벽한 레시피가 있는 요리"다 — 재료(자원)와 요구(제약)가 모두 선형이라면, 심플렉스 요리사가 반드시 최적 레시피(전역 최적)를 찾아낸다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[선형 계획법 (LP, Linear Programming) — 목적함수 + 제약조건]
    │
    ▼
[심플렉스 법 (Simplex Method) — 꼭짓점 탐색]
    │
    ▼
[내점법 (Interior Point Method) — 다항 시간 알고리즘]
    │
    ▼
[정수 계획법 (ILP) / 분기 한정법 (Branch & Bound)]
    │
    ▼
[SVM / 포트폴리오 최적화 — 산업 응용]

LP 최적화 이론이 단순 선형 문제에서 정수 계획과 머신러닝 응용으로 확장된 흐름이다.

👶 어린이를 위한 3줄 비유 설명

1. LP는 "규칙 있는 자원 배분": 한정된 재료(자원)로 가장 맛있는 요리(이익)를 만드는 수학 레시피.
2. 심플렉스는 "방 모서리 탐색": 방(가능 영역) 안에 서서 목적값이 가장 높은 모서리로 한 발씩 이동한다.
3. Shadow Price는 "자원 가격표": 원자재 1kg을 더 쓸 수 있다면 이익이 얼마나 늘지를 숫자로 알려준다.