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. 선형 계획 문제의 해법
ㅇ 심플렉스 해법, 내부점 해법 등
4. 선형 계획 문제의 적용 분야 및 例)
ㅇ 적용 분야 : 교통망, 통신망, 제조업, 경제학, 경영학 등
ㅇ 적용 문제 : 운송 계획 문제, 생산 계획 문제, 일정 계획 문제, 영양 문제 등