1. 선형 계획법 (Linear Programming, LP)
ㅇ 경영과학의 가장 기본적인 모형
- 단순하면서도 응용 분야가 넓은 이상적인 모형
ㅇ 1949년경, 미 해군 소속인 George B. Dantzig이,
- 군사 자원의 최적 할당 문제를 다루면서,
- 선형 계획법 문제를 정형화시키고,
- 이의 해를 구하는 심플렉스 방법을 개발
ㅇ 목적함수, 제약조건(등식 또는 부등식)이 결정 변수의 선형 함수로 표현되는 최적화 문제
- 제약 조건 : 연립 일차 부등식 또는 연립 일차 방정식 (선형 제약 형태)
- 목적함수 : 일차식 (선형 함수 형태)
2. 선형 계획 문제의 일반 형태
※ (구성 : 1개의 선형 목적 함수와 다수의 선형 제약 조건들로써 구성됨)
ㅇ 목적 함수 : [# \text{min or max} \;\; z = c_1x+c_2x_2+\cdots+c_nx_n #]
ㅇ 제약 조건 : [# \begin{array}{Llll}
\mbox{subject to} & a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & \lesseqqgtr & b_1 \\
& a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & \lesseqqgtr & b_2 \\
& \qquad \vdots & & \vdots \\
& a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & \lesseqqgtr & b_m
\end{array} #]
ㅇ 양수 조건 : [# x_1\geq0,\; x_2\geq0,\; \cdots\; ,\; x_n\geq0 #]
ㅇ (항목별 설명)
- 목적 함수 : 최소화(min)/최대화(max)시키려는, 결정변수 벡터 {#\mathbf{x}#}의 선형 함수
- 제약 조건(식) : 결정변수 x가 만족해야 하는 연립 선형 방정식 (등식 또는 부등식 형태)
- 양수 조건 : 결정변수 벡터 {#\mathbf{x}#}의 각 원소 xi는 음수가 될 수 없음
3. 선형 계획 문제의 적용 분야 및 例)
ㅇ 적용 분야 : 교통망, 통신망, 제조업, 경제학, 경영학 등
ㅇ 적용 문제
- 운송 계획 문제 : 여러 공급지 → 여러 수요지로 물자 운송 (총 운송 비용 최소화)
- 생산 계획 문제 : 제한된 자원(노동, 원료 등) 하에서, 이익 최대화 또는 비용 최소화
- 일정 계획 문제 : 작업 순서 및 시간 배치 최적화 (예: 공장 작업 스케줄, CPU 스케줄링 등)
- 영양 문제 : 최소 비용으로 영양 기준 충족 (LP의 고전적 예제로써, Dantzig 초기 연구 주제)
- 네트워크 흐름 문제 : 최대 유량(Max Flow), 최소 비용 흐름 등 통신/물류 네트워크 핵심 모델
4. 선형 계획 문제의 주요 해법
ㅇ 심플렉스 해법 : (경계 탐색)
- George B. Dantzig이 제안한 대표적 알고리즘
- 해의 공간(가능 영역, feasible region)의 꼭짓점(vertex)들을 따라 이동하며 최적해 탐색
- 매 단계 마다 목적함수 값을 개선하는 방향으로 이동
- 유한 번의 단계 내에 최적해 도달
. 이론적으로는 지수 시간 가능하지만, 실무에서는 매우 효율적
. 직관적 (기하학적 해석 가능)
. 중소 규모 문제에서 매우 빠름
ㅇ 내부점 해법 : (내부 경로 탐색)
- 1984년 Narendra Karmarkar에 의해 실용적으로 발전
- 경계(꼭짓점)가 아닌 내부 경로를 이용
- 가능 영역의 내부(interior)를 따라 이동하면서 최적해 접근
- 다항시간(polynomial time) 알고리즘
. 대규모 문제(변수/제약 수 매우 큼)에 유리
. 현대 최적화 소프트웨어에서 핵심적으로 사용됨