[경영과학] 선형계획법 (Linear Programming)

선형계획법이란?

선형계획법이란 경영과학 문제를 수학적으로 표현한 모형 중 목적함수와 제약조건식이 모두 선형식으로 정의되는 문제를 뜻한다. 여기서 관계식이 모두 선형적이라는 것은 변수 관계가 비례 혹은 반비례 관계가 있음을 나타낸다. 

 

수학적 모형	선형계획법 모형
변수(결정할 내용)	변수(결정할 내용)
상수(주어진 값)	상수(주어진 값)
수학적 관계식	목적함수: 선형식으로 표현된 이익최대화 및 최소화
	제약조건식: 선형식으로 표현된 수요만족, 자원의 한계
	비음조건: 변수가 0 이상이다

 

Notations 

• 자원
• 활동
• $Z$ : 활동 수준에 따라 목적 함수가 갖는 값
• $x_j$ : $j$번째 활동의 수준
• $c_j$ : $j$번째 활동의 수준이 1 증가할 때 $Z$가 증가하는 정도, 즉 $x_j$의 계수
• $b_i$ : 사용 가능한 자원 $i$의 상한
• $a_{ij}$ : $j$번째 활동 1 단위가 소비하는 $i$ 자원의 양
• 결정변수
• 매개변수  

 

표준형

$$\begin{align*} \text{maximize}\quad & Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \\ \text{subject to}\quad & a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \\ & a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \\ & \vdots \\ & a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \\ & x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0 \end{align*}$$

 

$$\begin{align*} \text{minimize}\quad & Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \\ \text{subject to}\quad & a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \geq b_1 \\ & a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \geq b_2 \\ & \vdots \\ & a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \geq b_m \\ & x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0 \end{align*}$$

 

 

다음과 같은 경영과학 문제를 살펴보자.

 

다음과 같이 결정변수를 설정할 수 있다.

• $Z$ : 총 이익 최대화
• 결정변수 $x_j$ : 제품 $j$의 생산 배치 수 $(j = 1,2)$ 

문제의 조건들에 따라 목적함수와 제약식을 세워보면

$$\begin{align*} \text{max} \quad & Z = 3x_1 + 5x_2 \\ \text{s.t.} \quad & x_1 \leq 4 \\ & x_2 \leq 12 \\ & 3x_1 + 2x_2 \leq 18 \\ & x_1 \geq 0, \; x_2 \geq 0 \end{align*}$$

 

과 같이 세울 수 있고, 이를 그래프를 이용해서 풀어보면

 

그림처럼 목적함수 직선이 (2,6)을 지날 때 $Z$가 최대가 됨을 확인할 수 있다.

 

이 때, 그래프 상에서 어둡게 칠해진 부분이 제약조건들을 모두 만족하는 영역이며, 이 안의 해들을 '가능해' 라고 부른다.  이 수많은 가능해들 중 목적함수가 최대 또는 최소가 되도록 하는 해를 '최적해'라고 부르며, 이 때 목적함수가 취하게 되는 값을 '최적값'이라고 부른다. 

 

위의 예시에서는 유일한 최적해를 갖지만 상황에 따라서 최적해가 여러 개가 있을 수도 있고, 최적해를 갖지 못할 수도 있다.

1. 최적해가 여러 개인 경우:
   • 목적함수 식이 가능해 영역 중 한 개 이상의 점에서 최대가 될 때
   • 목적함수 식이 제약조건 식 중 하나랑 평행할 때 
2. 최적해가 없는 경우:
   • 가능해가 없는 경우
   • 무한 최적값을 갖는 경우