선형계획법이란?
선형계획법이란 경영과학 문제를 수학적으로 표현한 모형 중 목적함수와 제약조건식이 모두 선형식으로 정의되는 문제를 뜻한다. 여기서 관계식이 모두 선형적이라는 것은 변수 관계가 비례 혹은 반비례 관계가 있음을 나타낸다.
수학적 모형 | 선형계획법 모형 |
변수(결정할 내용) | 변수(결정할 내용) |
상수(주어진 값) | 상수(주어진 값) |
수학적 관계식 | 목적함수: 선형식으로 표현된 이익최대화 및 최소화 |
제약조건식: 선형식으로 표현된 수요만족, 자원의 한계 | |
비음조건: 변수가 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$가 최대가 됨을 확인할 수 있다.
이 때, 그래프 상에서 어둡게 칠해진 부분이 제약조건들을 모두 만족하는 영역이며, 이 안의 해들을 '가능해' 라고 부른다. 이 수많은 가능해들 중 목적함수가 최대 또는 최소가 되도록 하는 해를 '최적해'라고 부르며, 이 때 목적함수가 취하게 되는 값을 '최적값'이라고 부른다.
위의 예시에서는 유일한 최적해를 갖지만 상황에 따라서 최적해가 여러 개가 있을 수도 있고, 최적해를 갖지 못할 수도 있다.
- 최적해가 여러 개인 경우:
- 목적함수 식이 가능해 영역 중 한 개 이상의 점에서 최대가 될 때
- 목적함수 식이 제약조건 식 중 하나랑 평행할 때
- 최적해가 없는 경우:
- 가능해가 없는 경우
- 무한 최적값을 갖는 경우
'산업공학 > 경영과학' 카테고리의 다른 글
[경영과학] 최적해 사후 분석 (0) | 2025.04.13 |
---|---|
[경영과학] 심플렉스 방법 3 - 다른 형태의 문제 (0) | 2025.04.13 |
[경영과학] 심플렉스 방법 2 (0) | 2024.10.03 |
[경영과학] 심플렉스 방법 1 (1) | 2024.10.03 |
[경영과학] OR 모형 접근 방법의 개관 (0) | 2024.03.08 |