최적설계 | 심플렉스법(2)

1. 인위변수

   표준화한 선형계획문제의 기저해가 음수라면, 해당 설계대안은 기저유용해가 아니므로 심플렉스법을 적용할 수 없다. 이때 음이 아닌 값을 갖는 인위변수(artificial variable)를 도입하여 심플렉스법을 적용하면 초기 기저유용해를 찾을 수 있으며, 해당 초기 기저유용해를 시작으로 심플렉스법을 적용하여 최적해를 탐색할 수 있다. 심플렉스법을 총 두 번 적용하는 것이다. 단, 첫 번째로 심플렉스법을 적용할 때에는 인위변수를 소거하기 위해 인위가격함수를 정의하고, 인위변수를 비기저변수로 만듦으로써 인위가격함수를 최솟값인 0으로 만드는 것을 목표로 한다. 인위가격함수는 인위변수의 합으로 다음과 같이 정의한다.

 

$$ \begin{align} \omega=\sum x_j \end{align}$$

 

   인위변수를 적용하여 새롭게 정의한 표준선형계획문제에 심플렉스법을 적용하기에 앞서, 인위가격함수는 반드시 제약조건을 기반으로 비기저변수만을 포함한 식으로 표현되어야 한다. 인위가격함수를 포함한 표준선형계획문제에 심플렉스법을 적용하였을 때 만약 모든 인위가격계수가 음수가 아니라면 해당 설계대안이 초기 기저유용해가 된다. 또한 이때 인위가격함수에 변수를 대입하여 그 값을 계산하면 0이 된다. 반면에, 모든 인위가격계수가 음수가 아님에도 인위목적함수의 값이 0보다 크다면 해당 선형계획문제는 유용해를 가지고 있지 않다는 것을 의미한다. 설계자는 문제의 정식화를 검토하여 너무 과다한 제약조건 혹은 부적당한 정식화가 있는지를 점검해야 한다.

 

2. 예제

선형계획문제

   다음과 같이 표준화된 선형계획문제에 심플렉스법을 적용해보자.

 

$$ \begin{align} \mathrm{minimize}~~~~f = -2x_1 - 5x_2 + 5x_3 \end{align}$$

 

$$ \begin{align} 3x_1 + 2x_2 -2x_3 + x_4 &= 12 \\\\ 2x_1 + 3x_2 - 3x_3 - x_5 &= 6 \\\\ x_i \geq 0;~~~~i = 1~~&to~~5 \end{align}$$

 

   위 표준선형계획문제를 첨가행렬(augmented matrix)로 정리하면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} 3 & 2 & -2 & 1 & 0 & 12 \\ 2 & 3 & -3 & 0 & -1 & 6 \\ -2 & -5 & 5 & 0 & 0 & f \\ \end{bmatrix} \end{align}$$

 

   위와 같은 첨가행렬에서 기저변수는 x₄, x₅에 해당하며, 비기저변수는 x₁, x₂, x₃에 해당한다. 해당 설계대안은 x₅의 해가 음수이기 때문에 유용하지 않으므로 심플렉스법을 적용할 수 없다.  인위변수 x₆을 도입하여 첫 번째 선형계획문제를 정의하면 다음과 같다.

 

$$ \begin{align} \mathrm{minimize}~~~~\omega = x_6 \end{align}$$

 

$$ \begin{align} 3x_1 + 2x_2 -2x_3 + x_4 &= 12 \\\\ 2x_1 + 3x_2 - 3x_3 - x_5 + x_6 &= 6 \\\\ -2x_1 - 5x_2 + 5x_3 &= f \\\\ x_i \geq 0;~~~~i = 1~~&to~~6 \end{align}$$

 

   첫 번째 심플렉스법을 적용하기에 앞서, 제약조건을 기반으로 인위가격함수를 비기저변수만을 포함한 식으로 표현하면 다음과 같다.

  

$$ \begin{align} \omega &= x_6 \\\\ &= 6 - 2x_1 - 3x_2 + 3x_3 + x_5 \\\\ \omega - 6 &= - 2x_1 - 3x_2 + 3x_3 + x_5 \end{align}$$

 

   이제 위 선형계획문제를 첨가행렬로 정리하면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} 3 & 2 & -2 & 1 & 0 & 0 & 12 \\ 2 & 3 & -3 & 0 & -1 & 1 & 6 \\ -2 & -5 & 5 & 0 & 0 & 0 & f \\ -2 & -3 & 3 & 0 & 1 & 0 & \omega-6 \\ \end{bmatrix} \end{align}$$

 

  현재 기저변수인 인위변수를 비기저변수로 만들기 위해 심플렉스법을 적용하자. 비기저변수 x₂의 임의가격계수가 음수이면서 절댓값이 가장 크고, 기저해를 해당비기저변수의 계수로 나누었을 때 기저변수 x₆의 값이 음수가 아니면서 가장 작으므로, 기저변수 x₆과 비기저변수 x₂를 교환하여 첨가행렬을 다시 나타내면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} \frac{5}{3} & 0 & 0 & 1 & \frac{2}{3} & -\frac{2}{3} & 8 \\ \frac{2}{3} & 1 & -1 & 0 & -\frac{1}{3} & \frac{1}{3} & 2 \\ \frac{4}{3} & 0 & 0 & 0 & -\frac{5}{3} & \frac{5}{3} & f+10 \\ 0 & 0 & 0 & 0 & 0 & 1 & \omega \\ \end{bmatrix} \end{align}$$

 

   위 첨가행렬에서 모든 비기저변수의 인위가격계수가 음수가 아니므로 해당 설계대안이 초기 기저유용해에 해당한다. 또한 모든 인위변수가 비기저변수가 되었고, 이를 인위가격함수에 대입하였을 때 0이 되므로 첫 번째  심플렉스법이 종료된 것을 확인할 수 있다. 이제 인위변수와 인위가격함수를 제거하여 첨가행렬을 다시 나타내면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} \frac{5}{3} & 0 & 0 & 1 & \frac{2}{3} & 8 \\ \frac{2}{3} & 1 & -1 & 0 & -\frac{1}{3} & 2 \\ \frac{4}{3} & 0 & 0 & 0 & -\frac{5}{3} & f+10 \\ \end{bmatrix} \end{align}$$

 

   위 첨가행렬에서 비기저변수 x₅의 환산가격계수가 음수이므로 해당 기저유용해는 최적점이 아니다. 비기저변수 x5의 환산가격계수가 음수이면서 절댓값이 가장 크고, 기저해를 해당 비기저변수의 계수로 나누었을 때 기저변수 x₄의 값이 음수가 아니면서 가장 작으므로, 기저변수 x₄와 비기저변수 x₅를 교환하여 첨가행렬을 다시 나타내면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} \frac{5}{2} & 0 & 0 & \frac{3}{2} & 1 & 12 \\ \frac{3}{2} & 1 & -1 & \frac{1}{2} & 0 & 6 \\ \frac{11}{2} & 0 & 0 & \frac{5}{2} & 0 & f+30 \\ \end{bmatrix} \end{align}$$

 

   위 첨가행렬에서 모든 비기저변수의 환산가격계수가 음수가 아니므로 해당 기저유용해가 최적점에 해당한다. 해당 기저유용해에서 가격함수의 값을 계산하면 다음과 같다.

 

$$ \begin{align} \frac{11}{2}x_1+\frac{5}{2}x_4 &= f + 30~~~~\left( x_1=0,~x_3=0,~x_4=0 \right) \\\\ 0 &= f + 30 \\\\ \therefore~f &= -30 \end{align}$$

 

 

 

 

 

[함께 읽으면 좋은 페이지]

 

최적설계 | 선형계획법

최적설계 | 파이썬 기반 선형계획문제 알고리즘 scipy.optimize.linprog

 

 

 

 

 

참고문헌

- Arora, J. S. (2016). Introduction to optimum design. Elsevier.