선형계획법이란?
연립일차방정식이나 연립일차부등식으로 표현할 수 있는 문제들의 값을 최소화해 구하는 과정
선형계획에는 목적함수와 제약조건, 그리고 비음조건이라는 것이 존재한다.
목적함수는 min 기호 앞에 붙여주며, 제약조건에는 s.t. 기호를 붙여준다.
(s.t. = subject to = “~에 제약되다” 라는 뜻.)
\begin{align*}
min\quad &5x_1 - 2x_2 + 3x_3 \\
s.t.\quad &x_1 + x_2 + x_3 = 10 \\
&2x_1 + 4x_2 + 5x_3 = 40
\end{align*}
최댓값과 최솟값
- 식에 써져 있는 max와 min 바꾸려면?
-
- 단, 선형계획법은 기본적으로 최솟값(min)을 구하는데 신경쓴다.
기저변수와 비기저변수
선형계획법은 선형대수의 기저를 가지고 아이디어를 전개한다.
- 기저변수 : 해에 영향을 미치는 변수들로써 값이 0이 아니다.
- 비기저변수 : 해에 영향을 미치지 않는 변수들로써 값이 0이다.
표준형 선형계획법
개요
\begin{align*}
min\;z=\;
&c_1x_1 +\cdots+ c_1x_n \\
s.t.\quad
&a_{11}\;\underline{x}_1 +
a_{12}\;\underline{x}_2 + \cdots
a_{1n}\;\underline{x}_n = b_1 \\
&a_{21}\;\underline{x}_1 +
a_{22}\;\underline{x}_2 + \cdots
a_{2n}\;\underline{x}_n = b_2 \\
&a_{31}\;\underline{x}_1 +
a_{32}\;\underline{x}_2 + \cdots
a_{3n}\;\underline{x}_n = b_3 \\
&\vdots \\
&a_{m1}\;\underline{x}_1 +
a_{m2}\;\underline{x}_2 + \cdots
a_{mn}\;\underline{x}_n = b_n \\
\\[15pt]
&x_1, \cdots, x_n \ge 0 \\
&b_1, \cdots, b_n \ge 0
\end{align*}
다음과 같은 모양을 표준형 선형계획이라고 한다.
벡터로 표기하면 다음과 같다.
\begin{align*}
min\quad & \underline{c}^{'}\underline{x} \\
s.t\quad &
A\underline{x} = \underline{b} \\
&\underline{x} \ge 0
\end{align*}
A\underline{x} = \underline{b} 를 만족하는 해가 없다. = 선형게획의 해가 없다 = feasible set is empty.
예시 1 - 변수 3개인 경우
\begin{align*}
min\quad &5x_1 - 2x_2 + 3x_3 \\
s.t.\quad &x_1 + x_2 + x_3 = 10 \\
&2x_1 + 4x_2 + 5x_3 = 40 \\
&x_1, x_2, x_3 >= 0
\end{align*}
푸는 법
- 연립방정식을 행렬로 바꾸고, 가우스 소거법을 쓰며 기저해를 찾는다.
이때 비기저변수/기저변수가 될 행을 미리 선정한다. (여기서는 1행과 2행이 기저.)
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
2 & 4 & 5 & 40\\
\end{array}
\right]
\quad
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
0 & 2 & 3 & 20\\
\end{array}
\right]
\quad
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
0 & 1 & \frac{3}{2} & 10\\
\end{array}
\right]
\underline{x} =
\begin{bmatrix}
10 \\ 10 \\ 0
\end{bmatrix}
◀ x_3가 비기저변수 일 때 기저해
이번에는 1행과 3행이 기저인 상황이다. (순서를 바꾸는 과정이 있음)
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
2 & 4 & 3 & 40\\
\end{array}
\right]
\quad
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
2 & 3 & 4 & 40\\
\end{array}
\right]
\quad
\left[
\begin{array} {rrr|r}
1 & 1 & 1 & 10\\
0 & \frac{2}{3} & 1 & \frac{20}{3}\\
\end{array}
\right]
\underline{x} =
\begin{bmatrix}
10/3 \\[2pt]
0 \\[2pt]
20/3
\end{bmatrix}
◀ x_2가 비기저변수 일 때 기저해
- 기저해는 무수히 많다. 이러한 기저해들을 가용해라고 한다.
- 가용해들의 집합을 feasible set이라고 한다.
- 가용해를 목적함수에 대입
-
\underline{x} = [10,\; 10,\; 0]^{T} 일때
5\cdot10 - 2\cdot10 + 3\cdot0 = 30
-
\underline{x} = [10/3,\; 0,\; 20/3]^{T} 일때
5\cdot10 - 2\cdot0 + 3\cdot\frac{20}{3} = (150+60)/3 = 70
- 둘 중 최솟값을 구한다. 답은 30.
선형계획법의 목표 : 목적함수가 최소화 되는 값을 구하는 것!
이때 기저에 따라 그 값이 최소가 될 수도 있고 아닐 수도 있다.
따라서 적합한 기저를 아는 것이 매우 중요하다.
예시 2 - 실생활 문제
다음 조건을 만족하는 연필, 지우개, 볼펜의 갯수는?
- 강릉 A 공장 : 연필 600원, 지우개 200원
- 광주 B 공장 : 연필 300원, 볼펜 100원
- 부산 C 공장 : 연필 1000원, 지우개 100원, 볼펜 100원
- A, B, C의 생산비용 = (800, 1000, 900)
- A의 연필 생산량 = B의 연필 생산량 = C의 연필 생산량
- A의 지우개 생산량 = C의 지우개 생산량
- B의 볼펜 생산량 = C의 볼펜 생산량
- max\quad 600x_1 + 600x_2 + 900x_4 : 목적함수
행렬로 표현하기
이를 다시 행렬로 표기하면 다음과 같다.
A =
\begin{pmatrix}
600 & 200 & 0 \\
300 & 0 & 100 \\
100 & 100 & 100
\end{pmatrix} \\[10pt]
\underline{b} =
\begin{pmatrix}
800000 \\
1000000 \\
9000000
\end{pmatrix}\\[10pt]
\underline{c} =
\begin{pmatrix}
-600 \\
-600 \\
-900
\end{pmatrix}
정규형 선형계획
앞서 이야기한 표준형 선형계획법에서, 적합한 기저를 아는 것은 매우 중요하다고 했다.
그런데 방정식 & 미지수가 무한히 많은 상황에서는 기저를 찾는 것이 매우 어렵다.
이때 만약 어떤 변수가 기저인지 미리 알아버린다면, 최적해를 좀 더 쉽게 찾을 수 있을 것이다.
- 기저가 미리 되어 버린 변수를 초기기저해라고 한다.
- 또한 초기기저해를 가진 선형계획법을 정규형 선형계획법이라고 한다.
이러한 표준형 선형계획을 푸는 방법을 심플렉스 알고리즘이라고 한다.
정규형 선형계획 만들기
표준형 선형계획을 정규형 선형계획으로 바꾸는 방법을 보자.
다음과 같이 표준형 선형계획이 주어져 있다.
\begin{array} {rrrrr}
max & 50x_1 &+60x_2 \\[5pt]
s.t.& 2x_1 &&+42 &\le300 \\[5pt]
& 20x_1 &+ 40x_2 & &\quad=2000
\end{array}\\[13pt]
x_1, x_2, x_3, x_4 \ge 0
두 가지를 하면 정규형 선형계획법으로 바꿀 수 있다.
- min을 max로 바꾼다.
- 여유변수(slack variable)을 추가한다; 여기서는 x_3, x_4
\begin{array} {rrrrr}
min & -50x_1 &-60x_2 \\[5pt]
s.t.& 2x_1 & &+x_3 &&=258 \\[5pt]
& 20x_1 &+ 40x_2 & &+x_4 &=2000
\end{array}\\[13pt]
x_1, x_2, x_3, x_4 \ge 0
태블루(tableau)
선형계획법을 그냥 방정식이나 행렬 형태로 적으면 계산 시 불편함이 있다.
따라서 다음과 같은 표를 만든다.
\begin{array}{r|rrrr|r}
& x_1 & x_2 & x_3 & x_4 \\
& -50 & -60 & 0 & 0 &
\\ \hline
x_3 & 2 & 0 & 1 & 0 & 258 \\
x_4 & 20 & 40 & 0 & 1 & 2000
\end{array}
LaTex로 쓰면 다음과 같다.
latex\begin{array}{r|rrrr|r}
& x_1 & x_2 & x_3 & x_4
\\ \hline
& -50 & -60 & 0 & 0 & \\
x_3 & 2 & 0 & 1 & 0 & 258 \\
x_4 & 20 & 40 & 0 & 1 & 2000
\end{array}
\begin{array}{r|rrrr|r}
& x_1 & x_2 & x_3 & x_4 \\
& -50 & -60 & 0 & 0 &
\\ \hline
x_3 & 2 & 0 & 1 & 0 & 258 \\
x_4 & 20 & 40 & 0 & 1 & 2000
\end{array}
hline 위의 숫자가 목적함수- 밑의 숫자가 제약조건임을 알 수 있다.
- 또 목적함수 부분이 0인 변수(x_3, x_4)가 바로 기저다.
- 해를 구하기 위해선 이 기저를 바꾸려고 시도해야 한다.
즉, 여유변수를 추가함으로써 임의로 기저를 설정하는 것이라고 생각하면 된다.
그때의 임의로 설정된 기저가 바로 초기기저해