개념
선형 부등식 제약 아래 선형 목적함수를 최적화. 1947년 단치히가 심플렉스 알고리즘 발명 — 2차대전 군수·운송·자원 배분의 표준 도구가 됐다.
한 호흡으로 이해하기
선형 제약이 만든 가능 영역에서 선형 목적함수를 최적화한다. 유한한 최적값이 존재하고 가능 영역에 꼭짓점이 있으면 최적 꼭짓점이 적어도 하나 존재한다. 최적해가 한 변 전체일 수도 있고, 문제가 불가능하거나 무한대로 발산할 수도 있다. 심플렉스와 내부점 방법은 자원 배분·흐름·생산 계획 등에 쓰인다.
한눈에 보기
상황 | 제약 | 목적함수 | 최적 값 |
|---|---|---|---|
공장 자원 배분 | 재료 ≤ 100, 노동 ≤ 80 | 이윤 = 5x + 3y → max | 꼭짓점 중 하나 |
혼합·배합 | 원료·영양·수요 | 비용 → min | 연속량이면 LP |
네트워크 흐름 | 용량·흐름 보존 | 비용 → min | 일부 라우팅·운송 |
전력 급전의 선형 근사 | 수요·용량 | 운영비 → min | 현실은 추가 비선형·정수 제약 |
선형 분류의 일부 변형 | 선형 제약 | 선형 손실·비용 → min | LP 가능; 표준 SVM은 보통 이차계획 |
심플렉스 알고리즘은 인접한 기저해를 따라가고, 내부점 방법은 가능 영역 안쪽을 지난다. 실제 모형의 품질은 목적함수와 제약이 현실을 얼마나 잘 담는지에도 달려 있다.
핵심 식
선형 목적함수 + 선형 제약
오늘날의 응용
항공·물류·통신 라우팅, 포트폴리오 최적화, 머신러닝 SVM.
MathVoyage 너머로
불러오는 중…