[경영과학] 심플렉스 방법 3 - 다른 형태의 문제

비표준형 모형

지금까지 우리는 표준형 (기능제약식이 모두 $\leq$ 이며, 모든 변수가 비음이며 목적함수는 최대화) 이라는 가정 하에서 심플렉스 방법을 적용하였다. 이번 포스팅에서는 이러한 표준형이 아닌 모형 (기능제약식이 등식이거나 $\geq$ 형태인 경우)를 다룰 것이다.

 

기능 제약식이 (= 또는 $\geq$형태)인 경우의 문제는 초기해를 찾는 것에서 발생한다. 표준형태에서는 여유변수를 초기 기저변수로 잡으면 각 변수의 값이 비음이 되므로 초기해가 편리하게 찾아졌다. 그러나 비표준 형태에서는 여유변수를 두어도 비음을 만족시키지 못할 가능성이 있으므로 추가적인 접근법을 도입해야 한다. 그 접근법을 인공변수라고 한다.

 

빅 $M$ 방법 

등호 제약식 문제

$$\begin{align*}
\text{Maximize} \quad & z = 3x_1 + 5x_2 \\
\text{Subject to} \quad & x_1 \leq 4 \\
                       & 2x_2 \leq 12 \\
                       & 3x_1 + 2x_2 = 18 \\
                       & x_1 \geq 0, \quad x_2 \geq 0
\end{align*}$$

 

위 모형에서 세번째 방정식인 $ 3x_1 + 2x_2 = 18$은 등호 제약식이므로 초기 기저변수로 사용할 수 있는 여유변수를 갖지 못한다. 따라서 이 방정식에는 인공변수를 도입하여 마치 여유변수를 사용하는 것처럼 만든다.

$$3x_1 + 2x_2 + \overline{x_5} = 18$$

 

그리고 목적함수를 다음과 같이 이용하여 $\overline{x_5} \geq 0$이 되는 경우에 대해 아주 강한 페널티를 부여한다.

$$Z = 3x_1 + 5x_2 - M\overline{x_5}$$

 

이때 $M$은 매우 큰 양수를 나타내는 기호이다. 이 방법의 목적은 인공변수 $\overline{x_5}$을 0으로 만드는 것이며, 빅 $M$ 방법이라고 불린다

 

그러면 위 문제는 다음과 같은 확장형 모형으로 변형된다.

$$\begin{align*}
& Z - 3x_1 - 5x_2 \quad \quad \quad \quad \;\;+ M\overline{x_5} = 0 \\
& \quad \quad \;\;x_1  \quad \quad \quad + x_3 \quad \quad \quad \quad \quad \; = 4 \\
& \quad \quad \quad \quad \;\; 2x_2 \quad \quad \quad + x_4 \quad \quad \;\;\;= 12 \\
& \quad \quad 3x_1 + 2x_2 \quad \quad \quad \quad \quad \;\;\; + \overline{x_5} = 18 \\
\end{align*}$$

 

이를 심플렉스 테이블에 나타내면 아래와 같다. 매우 큰 양수 $M = 100$을 사용하였다.

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0			$Z$	(0)	1	-3	-5	0	0	100	0
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	3	2	0	0	1	18

 

그러나 이 코기형태는 기저변수 중 하나인 $\overline{x_5}$가 0이 아닌 계수를 가지고 있으므로 가우스 소거법을 바로 사용하기에 적절한 형태가 아니다. 따라서 처음 해야 할 작업은 이 계수를 0으로 만드는 피봇팅 작업이다. 피보팅 작업을 완료한 테이블은 아래와 같다.

 

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0' (피봇팅)			$Z$	(0)	1	-303	-205	0	0	0	-1800
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	3	2	0	0	1	18

 

이제 피봇팅이 완료되었으니 심플렉스 방법을 적용하면 된다. 최소 음수 진입조건을 사용하면 $x_1$이 진입변수가 되고, 최소비율법에 의해 $x_3$가 탈락변수가 된다. 최적해가 나올때까지 계속 적용해나가면 된다.

 

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
1			$Z$	(0)	1	0	-205	303	0	0	-588
			$x_1$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	0	2	-3	0	1	6

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
2			$Z$	(0)	1	0	0	$-\frac{9}{2}$	0	$\frac{205}{2}$	27
			$x_1$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	0	3	1	-1	6
			$x_2$	(3)	0	0	1	$-\frac{3}{2}$	0	$\frac{1}{2}$	3

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
3			$Z$	(0)	1	0	0	0	$\frac{3}{2}$	101	36
			$x_1$	(1)	0	1	0	0	$-\frac{1}{3}$	$\frac{1}{3}$	2
			$x_3$	(2)	0	0	0	1	$\frac{1}{3}$	$-\frac{1}{3}$	2
			$x_2$	(3)	0	0	1	0	$\frac{1}{2}$	1	6

 

반복 3에서 인공변수인 $x_5$가 비기저변수가 되면서 값이 0이 되고, 남은 비기저변수들 모두 계수가 양수이므로 최적해가 찾아졌고, 이 해가 유일한 최적해임을 알 수 있다.

 

$\geq$ 형식을 갖는 제약식 문제

인공변수 기술이 $\geq$ 형식을 갖는 제약식 문제에서 어떻게 적용되는지를 살펴보자. 다음과 같은 예제를 보자.

$$\begin{align*}
\text{Minimize} \quad & z = 0.4x_1 + 0.5x_2 \\
\text{Subject to} \quad & 0.3x_1 + 0.1x_2 \leq 27 \\
                       & 0.5x_1 + 0.5x_2 = 6 \\
                       & 0.6x_1 + 0.4x_2 \geq 6 \\
                       & x_1 \geq 0, \quad x_2 \geq 0
\end{align*}$$

 

이 문제에서 세번째 제약식을 다루는 방법부터 알아보도록 한다. 방법은 잉여변수와 인공변수를 동시에 사용하는 것이다.

$$ 0.6x_1 + 0.4x_2 - x_5 + \overline{x_6} = 6 \quad (x_5 \geq 0, \overline{x_6} \geq 0)$$

 

여기서 좌변이 우변보다 넘치는 잉여량을 빼주면 부등식이 동등한 등식으로 바뀌므로 $x_5$는 잉여변수라 부른다. 그 이후는 위에서 등식 제약식을 다룬 것처럼 인공변수가 더해진다. 이를 적용한 확장형 모형은 다음과 같다.

$$\begin{align*}
& Z - 0.4x_1 - 0.5x_2 \hspace{1cm} - M\overline{x_4} \hspace{0.4cm} - M\overline{x_6} = 0 \\
& \quad \;\;\;\;0.3x_1 + 0.1x_2 + x_3 \hspace{3.4cm} = 27 \\
& \quad \;\;\;\;0.5x_1 + 0.5x_2 \hspace{1.15cm} + \overline{x_4} \hspace{2.25cm} = 6 \\
& \quad \;\;\;\;0.6x_1 + 0.4x_2 \hspace{2.2cm} - x_5 + \hspace{0.15cm} \overline{x_6} = 6
\end{align*}$$

 

$Z$를 최소화하고 있기 때문에 목적함수에서 인공변수의 계수가 $-M$임에 주의하자.

 

2-국면 방법

인공변수를 갖는 다른 문제들은 실제 문제의 첫 가능해를 찾은 후에도 최적해를 찾기 위해서는 추가적인 반복이 필요할 수도 있다. 그러므로 빅 $M$ 방법은 2개의 국면을 가진다. 첫번째 국면에서는 실제 문제의 초기해를 얻기 위해 모든 인공변수가 0이 되도록 만든다. 두 번째 국면에서는 모든 인공변수는 0으로 유지되면서, 심플렉스 방법은 실제 문제를 위한 일련의 가능해들을 거쳐 최적해에 이른다. 이를 2-국면 방법이라 하며, 이 방법은 $M$을 도입하지 않는다.

 

Big M 방법:  $\quad \text{Minimize} \quad Z = 0.4x_1 + 0.5x_2 + M\overline{x_4} + M\overline{x_6}$

2-국면 방법:
        국면 1: $\quad \text{Minimize} \quad Z = \overline{x_4} + \overline{x_6}$ 
        국면 2: $\quad \text{Minimize} \quad Z = 0.4x_1 + 0.5x_2$

 

국면 1과 국면 2에 대해 각각 모형화 하면 다음과 같다

[국면 1]

\begin{align*}
\text{Minimize} \quad & Z = \overline{x_4} + \overline{x_6} \\
\text{Subject to} \quad 
& 0.3x_1 + 0.1x_2 + x_3 = 27 \\
& 0.5x_1 + 0.5x_2 + \overline{x_4} = 6 \\
& 0.6x_1 + 0.4x_2 - x_5 + \overline{x_6} = 6 \\
& x_1, x_2, x_3, \overline{x_4}, x_5, \overline{x_6} \geq 0
\end{align*}

 

[국면 2]

\begin{align*}
\text{Minimize} \quad & Z = 0.4x_1 + 0.5x_2 \\
\text{Subject to} \quad 
& 0.3x_1 + 0.1x_2 + x_3 = 27 \\
& 0.5x_1 + 0.5x_2  = 6 \\
& 0.6x_1 + 0.4x_2 - x_5  = 6 \\
& x_1, x_2, x_3, x_5 \geq 0
\end{align*}

 

다음은 2-국면 방법의 심플렉스 테이블이다.

[국면 1]

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
0			$Z$	(0)	-1	0	0	0	-1	0	-1	0
			$x_3$	(1)	0	0.3	0.1	1	0	0	0	2.7
			$x_4$	(2)	0	0.5	0.5	0	1	0	0	6
			$x_6$	(3)	0	0.6	0.4	0	0	-1	1	6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
0'			$Z$	(0)	-1	-1.1	-0.9	0	0	1	0	-12
			$x_3$	(1)	0	0.3	0.1	1	0	0	0	2.7
			$x_4$	(2)	0	0.5	0.5	0	1	0	0	6
			$x_6$	(3)	0	0.6	0.4	0	0	-1	1	6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
1			$Z$	(0)	-1	0	$-\frac{16}{30}$	$\frac{11}{3}$	0	1	0	-2.1
			$x_1$	(1)	0	1	$\frac{1}{3}$	$\frac{10}{3}$	0	0	0	9
			$x_4$	(2)	0	0	$\frac{1}{3}$	$-\frac{5}{3}$	1	0	0	1.5
			$x_6$	(3)	0	0	0.2	-2	0	-1	1	0.6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
2			$Z$	(0)	-1	0	0	$-\frac{5}{3}$	0	$-\frac{5}{3}$	$\frac{8}{3}$	-0.5
			$x_1$	(1)	0	1	0	$\frac{20}{3}$	0	$\frac{5}{3}$	$-\frac{5}{3}$	28
			$x_4$	(2)	0	0	0	$-\frac{5}{3}$	1	$\frac{5}{3}$	$-\frac{5}{3}$	0.5
			$x_2$	(3)	0	0	1	-10	0	-1	1	3

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
3			$Z$	(0)	-1	0	0	0	1	0	1	0
			$x_1$	(1)	0	1	0	0	-4	-5	5	6
			$x_3$	(2)	0	0	0	1	$\frac{3}{5}$	1	-1	0.3
			$x_2$	(3)	0	0	1	0	6	5	5	6

 

이제 인공변수들이 모두 0의 값을 가지게 되었으므로 (비기저변수) 국면 1은 종료되었다. 이제 국면 2에서는 인공변수를 제외하고 국면 1에서의 해를 초기해로 사용하여 심플렉스 방법을 적용한다.

 

[국면 2]

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$
국면 1 마지막 표			$Z$	(0)	-1	0	0	0	1	0	1	0
			$x_1$	(1)	0	1	0	0	-4	-5	5	6
			$x_3$	(2)	0	0	0	1	$\frac{3}{5}$	1	-1	0.3
			$x_2$	(3)	0	0	1	0	6	5	5	6

 

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$		$x_5$
인공변수 제거			$Z$	(0)	-1	0	0	0		0		0
			$x_1$	(1)	0	1	0	0		-5		6
			$x_3$	(2)	0	0	0	1		1		0.3
			$x_2$	(3)	0	0	1	0		5		6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$		$x_5$
국면 2 목적함수			$Z$	(0)	-1	0.4	0.5	0		0		0
			$x_1$	(1)	0	1	0	0		-5		6
			$x_3$	(2)	0	0	0	1		1		0.3
			$x_2$	(3)	0	0	1	0		5		6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$		$x_5$
0(피봇팅)			$Z$	(0)	-1	0	0	0		0		-5.4
			$x_1$	(1)	0	1	0	0		-5		6
			$x_3$	(2)	0	0	0	1		1		0.3
			$x_2$	(3)	0	0	1	0		5		6

반복			기저변수	방정식	계수							우변
					Z	$x_1$	$x_2$	$x_3$		$x_5$
1			$Z$	(0)	-1	0	0	0.5		0		-5.25
			$x_1$	(1)	0	1	0	0		0		7.5
			$x_5$	(2)	0	0	0	1		1		0.3
			$x_2$	(3)	0	0	1	-5		0		4.5

 

이로써 인공변수와 잉여변수가 모두 비기저변수화 되었고 최적해가 구해졌다.