심플렉스 알고리즘

표준형 선형계획법을 푸는 방법을 심플렉스 알고리즘이라고 한다.
초기기저로부터 기저를 바꾸고, 해를 구하는 데 중점을 두고 있다.
우선적으로는 손으로 풀어보자. (실제로는 코딩으로 하는 경우가 더 많다.)
- 계산이 복잡하므로 조심해야 한다.
- 보통 타블로를 작성해 푼다.
- 부등호 방향에 따라 크게 3가지 케이스가 있다.

1. 기본형 : 모든 부등호가 “≤”

\begin{array} {rrrrr} min & -50x_1 &-60x_2 & -7x_3 \\[5pt] s.t. & 2x_1 & +9x_2 && &&& \le1000 \\[5pt] & 20x_1 &+ 40x_2 & +7x_3&& && \le2000\\[5pt] & 5x_1 &+ x_2 &&&& & \le5000\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3\; \ge 0

1. 정규형 선형계획

\begin{array} {rrrrr} min & -50x_1 &-60x_2 & -7x_3 \\[5pt] s.t. & 2x_1 & +9x_2 && +x_4 &&& =1000 \\[5pt] & 20x_1 &+ 40x_2 & +7x_3&& +x_5&& =2000\\[5pt] & 5x_1 &+ x_2 &&&& +x_6 & =5000\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3,\; x_4,\; x_5,\; x_6\; \ge 0

2. 기저 고르기 & 피봇연산

목적함수 행에서 아무 음수나 고른다.
- 어떤 음수를 고르든 상관은 없으나, 계산에 유리한 방향으로 고르는 것이 좋다.
또, 그 음수 밑에서 양수를 고른다.
양수가 여러개일 때는 (양수가 속한 행의 y값) / (해당 양수) 의 비율을 봐서 작은 것을 고른다.

\begin{array} {r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\ & 5 & \textcolor{red}{-6} & -7 & 0 & 0 & 0 & 0 \\ \hline x_4 & 2 & \textcolor{blue}{9} & 0 & 1 & 0 & 0 & \textcolor{orange}{1000} \\ x_5 & 1 & -6 & 7 & 0 & 1 & 0 & 2000 \\ x_6 & 5 & \textcolor{blue}{1} & 0 & 0 & 0 & 1 & \textcolor{orange}{5000} \end{array}

여기서는 1000/9인 $x_4$ 가 5000/1인 $x_6$ 보다 작다.
따라서 바뀔 기저변수로 $x_4$ 를 고른다.

\begin{array} {r|rrrrrr|r} & x_1 & \textcolor{magenta}{x_2} & x_3 & x_4 & x_5 & x_6 & \\ & 5 & \textcolor{red}{-6} & -7 & 0 & 0 & 0 & 0 \\ \hline \textcolor{green}{x_4} & 2 & \textcolor{blue}{9} & 0 & 1 & 0 & 0 & 1000 \\ x_5 & 1 & -6 & 7 & 0 & 1 & 0 & 2000 \\ x_6 & 5 & 1 & 0 & 0 & 0 & 1 & 5000 \end{array}

$\textcolor{magenta}{x_2}$ 가 새로운 기저변수가 되고, 기존 $\textcolor{green}{x_4}$ 는 비기저변수가 된다.
이후 피봇연산을 실시한다.
- 이때 양수 부분이 1이 되도록 만들고,
- 열의 나머지는 전부 0이 되게 한다.

3. 기저 고르기 & 피봇연산

목적함수 행에서 아무 음수나 고른다.
그 음수 밑에서 양수를 고른다.

\begin{array} {r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & 14/3 & 0 & \textcolor{red}{-7} & 2/3 & 0 & 0 & 2000/3 \\[3pt] \hline x_2 & 2/9 & 1 & 0 & 1/9 & 0 & 0 & 1000/9 \\[3pt] x_5 & 7/3 & 0 & \textcolor{blue}{7} & 2/3 & 1 & 0 & 8000/9 \\[3pt] x_6 & 43/9 & 0 & 0 & -1/9 & 0 & 1 & 44000/9 \end{array}

피봇연산 실시.

4. 기저 확인해보기

목적함수 행에서 아무 음수나 고른다.
음수가 없는 경우, 그때의 x값들이 최적해다.

\begin{array} {r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & 3/26 & 0 & 0 & 4/3 & 1 & 0 & 10000/3 \\[3pt] \hline x_2 & 2/7 & 1 & 0 & 1/9 & 0 & 0 & 1000/9 \\[3pt] x_3 & 1/3 & 0 & 1 & 2/21 & 1/7 & 0 & 8000/21 \\[3pt] x_6 & 43/9 & 0 & 0 & -1/9 & 0 & 1 & 44000/9 \end{array}

5. 최적해 확인해보기

\underline{x} = \begin{bmatrix} 0 & \frac{1000}{9} & \frac{8000}{21} & 0 & 0 & \frac{44000}{9} \end{bmatrix}^{T} ~,~ z = \textstyle\frac{-10000}{3}

2. 불능형 : 부등호 하나만 ‘≥’

\begin{array} {rrrrr} min & x_1 & +x_2 & -x_3 \\[5pt] s.t. & x_1 & +x_2 & -x_3& \le&5000 \\[5pt] & 2x_1 &+ x_2 & +x_3& \le&6000\\[5pt] & x_1 &+ 2x_2 & -x_3& \textcolor{red}{\ge}&6000\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3,\; \ge 0

이 경우 부등호 방향을 바꾸면 다음과 같다.

\begin{array} {rrrrr} min & x_1 & +x_2 & -x_3 \\[5pt] s.t. & x_1 & +x_2 & -x_3 &\le&5000\\[5pt] & 2x_1 &+ x_2 & +x_3 &\le&6000\\[5pt] & -x_1 &- 2x_2 & +x_3 &\le& \textcolor{red}{-6000}\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3,\; \ge 0

잉여변수

다시 이를 정규형 선형계획으로 바꾸면 다음과 같다.

부등호 방향이 반대인 경우 ‘-’를 붙이면서 추가변수를 넣어야 한다.

이때, ‘-’를 붙여서 넣은 변수를 잉여변수라고 한다.

\begin{array} {rrrrr} min & x_1 & +x_2 & -x_3 \\[5pt] s.t. & x_1 & +x_2 & -x_3& +x_4 &&& =5000 \\[5pt] & 2x_1 &+ x_2 & +x_3&& +x_5 && =6000\\[5pt] & x_1 & +2x_2 & -x_3&&& \textcolor{red}{-x_6} & =6000\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3,\; \ge 0

\begin{array}{r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & 1 & 1 & -1 & 0 & 0 & 0 & 0 \\[3pt] \hline x_4 & 1 & 1 & -1 & \textcolor{red}{1} & 0 & 0 & 5000\\ x_5 & 2 & 1 & 1 & 0 & \textcolor{red}{1} & 0 & 6000\\ &-1 & 1 & 0 & 0 & 0 &\textcolor{red}{-1} & -6000\\ \end{array}

그러나 잉여변수를 넣어도 기저가 되지는 않는다.
- 모양을 보면 단위행렬이 나오지 않는다. 기저로써 실격!
\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{bmatrix}
- 또한 X값들을 벡터로 모아서 보면 비음조건에 위배됨을 알 수 있다.
\underline{x} = \begin{bmatrix} 0 & 0 & 0 & 5000 & 6000 & -6000 \end{bmatrix}

이 경우 목적함수의 최적해를 전혀 구할 수 없다.

계속 태블루를 풀어도 x값들 중 꼭 하나는 음수가 나온다.

기저를 꼼수로 잡되, 아까와 달리 목적함수 행 중 양수를 고르자.

우선 $x_1$ 을 기저로 잡아보자.

\begin{array}{r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & 1 & 1 & -1 & 0 & 0 & 0 & 0 \\[3pt] \hline x_4 & 1 & 1 & -1 & 1 & 0 & 0 & 5000\\ x_5 & 2 & 1 & 1 & 0 & 1 & 0 & 6000\\ &\textcolor{red}{1} & 2 & -1 & 0 & 0 &-1 & 6000\\ \end{array}

문제는…이 상태에서 피봇연산을 해도 여전히 비음조건을 만족하지 못함.

\begin{array}{r|rrrrrr|r} & x_6 & x_2 & x_3 & x_4 & x_5 & x_1 & \\[3pt] & 0 & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\[3pt] \hline x_4 & 0 & 1 & -1 & 1 & 0 & 1 & -1000\\ x_5 & 0 & 1 & 1 & 0 & 1 & 2 & -6000\\ x_1 & 1 & 2 & -1 & 0 & 0 & -1 & 6000\\ \end{array}

다시 처음으로 돌아와서, 이번에는 $x_2$ 를 억지로 기저로 잡아보자.

\begin{array}{r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & 1 & 1 & -1 & 0 & 0 & 0 & 0 \\[3pt] \hline x_4 & 1 & 1 & -1 & 1 & 0 & 0 & 5000\\ x_5 & 2 & 1 & 1 & 0 & 1 & 0 & 6000\\ &1 & \textcolor{red}{2} & -1 & 0 & 0 &-1 & 6000\\ \end{array}

여전히 비음조건에 위해. 전혀 나아질 기미가 안보인다.

\begin{array}{r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \\[3pt] & \cdots & 0 & \cdots & \cdots & \cdots & \cdots & \cdots \\[3pt] \hline x_4 & 0 & 0 & 0 & 1 & 0 & 1 & -1000\\ x_5 &3/2 & 0 &3/2 & 0 & 1 & 1/2 & 3000\\ &1/2 & 1 &-1/2 & 0 & 0 & -1/2 & 3000\\ \end{array}

즉, 초기기저해를 찾을 수 없으므로 문제의 해가 존재하지 않는다.

3. 인공형 : 부등호 모두가 ‘≥’

\begin{array} {rrrrr} min & 4x_1 & +12x_2 & +x_3 \\[5pt] s.t. & x_1 & +4x_2 & -x_3& \ge1 \\[5pt] & 2x_1 &+ 2x_2 & +x_3& \ge1\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; x_3,\; \ge 0

전부 부등호 방향이 “≥”
잉여변수를 넣어야 한다.

\begin{array} {rrrrr} min & 4x_1 & +12x_2 & +x_3 \\[5pt] s.t. & x_1 & +4x_2 & -x_3& -x_4 &&& = 1 \\[5pt] & 2x_1 &+ 2x_2 & +x_3&& -x_5&& = 1\\[5pt] \end{array}\\[13pt] x_1,\; \cdots,\; x_5,\; \ge 0

\begin{array} {rrrrr|r} 4 & 12 & 1 & 0 & 0 & 0 \\ \hline 1 & 4 & -1 & -1 & 0 & 1 \\ 2 & 2 & 1 & 0 & -1 & 1 \end{array}

이를 태블루로 바꿔보자.

문제는 이 경우 초기기저를 전혀 찾을 수 없다는 것이다.

인공변수

따라서 인공변수를 넣고, 목적함수도 바꾼다.

\begin{array} {rrrrr} min & x_6 & +x_7 \\[5pt] s.t. & x_1 & +4x_2 & -x_3& -x_4 && +x_6& &=1 \\[5pt] & 2x_1 &+ 2x_2 & +x_3&& -x_5 && +x_7 &=1\\[5pt] \end{array}\\[13pt] x_1,\; x_2,\; , \cdots, x_7\; \ge 0

태블루로 바꾸면 다음과 같다.

\begin{array} {c|rrrrrrr|r} &x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \text{우변} \\ \hline &0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline x_6 & 1 & 4 & -1 & -1 & -0 & 1 & 0 & 1 \\ x_7 & 2 & 2 & 1 & 0 & -1 & 0 & 1 & 1 \\ \end{array}

목적함수 수정하기

기저를 넣어도 그 기저의 목적함수 행 부분이 0이 아니다.

\begin{array} {c|rrrrrrr|r} &x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \text{우변} \\ \hline &0 & 0 & 0 & 0 & 0 & \textcolor{red}{1} & \textcolor{red}{1} & 0 \\ \hline x_6 & 1 & 4 & -1 & -1 & -0 & 1 & 0 & 1 \\ x_7 & 2 & 2 & 1 & 0 & -1 & 0 & 1 & 1 \\ \end{array}

그래서 제약식 행들을 합친 후 목적함수 행에서 뺀다.

이후 계속 피봇연산 반복.

\def\arraystretch{1.3} \begin{array} {c|rrrrrrr|r} &x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \text{우변} \\ \hline &0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ & \textcolor{red}{-3} & -6 & 0 & 1 & 1 & 0 & 0 & -2 \\ \hline x_6 & 1 & 4 & -1 & -1 & -0 & 1 & 0 & 1 \\ x_7 & \textcolor{red}{2} & 2 & 1 & 0 & -1 & 0 & 1 & 1 \\ \end{array}

\def\arraystretch{1.5} \begin{array} {c|rrrrrrr|r} &x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \text{우변} \\ &0 & -3 & \frac{3}{2} & 1 & \textcolor{red}{-\frac{1}{2}} & 0 & \frac{3}{2} & -\frac{1}{2} \\ \hline x_6 & 0 & 3 & -\frac{3}{2} & 0 & \textcolor{red}{\frac{1}{2}} & 1 & \frac{1}{2} & \frac{1}{2} \\ x_1 & 1 & 1 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{2} \end{array}

\def\arraystretch{1.5} \begin{array} {c|rrrrrrr|r} &x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \text{우변} \\ &0 & 0 & 0 & 1 & 0 & 1 & 2 & 0 \\ \hline x_5 & \textcolor{blue}{0} & 6 & -3 & 0 & 1 & 2 & \textcolor{blue}{1} & 1 \\ x_1 & \textcolor{blue}{1} & 4 & -1 & 0 & 0 & 1 & \textcolor{blue}{0} & 1 \\ \end{array}

원래의 기저인 $x_5$ 와 $x_1$ 을 찾는데 성공.

원래 연산으로

\begin{array} {rrrrr|r} 4 & 12 & 1 & 0 & 0 & 0 \\ \hline 1 & 4 & -1 & -1 & 0 & 1 \\ 2 & 2 & 1 & 0 & -1 & 1 \end{array}

원래 연산에서는 기저를 찾을 수 없었다.
그러나 지금은 기저를 찾은 상태이므로 바로 피봇연산을 해주면 된다.

이제 피봇연산을 돌려주며 해를 찾는다.

\def\arraystretch{1.5} \begin{array} {r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 \\ & 0 & 12 & 1 & 0 & 0 & 0 \\ \hline x_1 & 1 & 4 & -1 & -1 & 0 & 1\\ x_5 & 0 & 2 & 1 & 0 & 1 & 1\\ \end{array}

우선 기저 부분의 목적수 행 중 일부가 0이 아니다.

따라서, 행/열 모두 기저변수인 부분을 고르고, 해당 부분을 0으로 만든다.

\def\arraystretch{1.5} \begin{array} {r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 \\ & 4 & 12 & 1 & 0 & 0 &0 \\ \hline x_1 & \textcolor{red}{1} & 4 & -1 & -1 & 0 & 1\\ x_5 & 2 & 2 & 1 & 0 & -1 & 1\\ \end{array}

우선 행과 열이 모두 $x_1$ 인 부분을 바꾼다.

\def\arraystretch{1.5} \begin{array} {r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 \\ & 0 & -4 & 5 & 4 & 0 & -4 \\ \hline x_1 & 1 & 4 & -1 & -1 & 0 & 1\\ x_5 & 0 & 2 & 1 & 0 & \textcolor{red}{-1} & 1\\ \end{array}

또 행과 열이 모두 $x_5$ 인 부분을 바꾼다.

\def\arraystretch{1.5} \begin{array} {r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 \\ & 0 & -4 & 5 & 4 & 0 & -4 \\ \hline x_1 & 1 & 4 & -1 & -1 & 0 & 1\\ x_5 & 2 & 2 & 1 & 0 & 1 & 1\\ \end{array}

인제 완성되었다.

이 상태에서 이제 피봇연산을 시행한다.

\def\arraystretch{1.5} \begin{array} {r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 \\ & 0 & 0 & 7 & \frac{8}{3} & \frac{2}{3} & -\frac{10}{3} \\ \hline x_1 & 1 & 0 & 1 & \frac{1}{3} & \frac{8}{3} & \frac{1}{3} \\ x_5 & 0 & 1 & -\frac{1}{2} & -\frac{1}{3} & \frac{1}{6} & \frac{1}{6} \\ \end{array}

더 이상 목적함수 행에 음수가 없다.

즉, 최종적인 결과는 다음과 같다.

$\underline{x} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 \end{bmatrix},\quad z = \frac{10}{3}$

정리하기

추가변수 정리

여유변수 : 부등호가 “≤”일 때
잉여변수 : 부등호가 “≥”일 때
인공변수 : 잉여변수로도 전혀 찾을 수 없을 때

판단 기준

부등호가 모두 “≤”
- 그냥 여유변수 넣어서 피봇연산
부등호 중 하나가 “≤”
- 잉여변수
- 해가 아예 없다.
부등호가 모두 “≥”
- 잉여변수, 인공변수 모두 넣고 진짜 기저 찾기
- 잉여변수만 넣은 상황에서 행, 열 모두 기저변수인 애들 고르기
- 피봇연산해서 기저변수 열의 목적함수 행을 전부 0으로.
- 피봇연산 반복