[경영과학] 최적해 사후 분석

OR에서 문제의 시나리오가 바뀔 경우 최적해를 다시 찾아야 하는 경우가 있는데, 이를 효율적으로 해결하는 것은 매우 중요한 과제이다. 시나리오가 바뀐다는 것은 다음을 의미할 수 있다.

• 제품 생산량당 얻는 단위 이득의 변화
• 허용된 자원의 양의 한계치가 변화

이 때 문제를 처음부터 다시 풀 수도 있겠지만, 그러기보다는 이전 문제의 최적해와 바뀐 문제의 최적해가 서로 멀리 떨어져 있지 않을 것이라 가정하고 접근하는 재최적화 방법을 쓰는 것이 일반적이다.

 

아래와 같은 예제가 있다고 하자. 각 결정변수는 제품 1,2를 각각 얼마나 생산할 지를 나타내는 변수이고, 목적함수의 계수는 제품 1, 2의 단위 생산량 당 이득으로 생각할 수 있다. 각각의 제약식은 제품1, 2를 생산하는데 드는 자원1,2,3에 대한 제약으로, 계수는 자원 $i$를 생산하는 데 드는 제품 $j$당 소모량이고, 우변 상수는 각 자원$i$에 대한 사용 한계이다.

 

$$\begin{aligned} \text{Maximize} \quad & Z = 5x_1 + 2x_2 \\ \text{Subject to} \quad  & x_1 + 2x_2 \leq 12 \\ & x_1 + x_2 \leq 8 \\ & 3x_1 + x_2 \leq 18 \\ & x_1 \geq 0,\; x_2 \geq 0 \end{aligned}$$

출처 : 지오지브라

 

목적함수의 계수 변화

목적함수의 계수가 변화하는 것은 제품 생산량 당 이득의 변화가 생긴다는 의미이다. 위 예제에서 현재 최적해는 $(x_1, x_2) = (5,3)$이다. 이때 제품 1의 생산량 당 얻을 수 있는 이익 변화한다고 하자. 이는 $x_1$의 목적함수의 계수가 변한다는 것과 동치이며, 현재해가 여전히 최적해로 유지되도록 하는 계수의 범위를 생각해보자.

 

현재해 (5,3)은 두번째 제약식 (자원 2)와 세번째 제약식 (자원 3)의 교점에서 나온다. 목적함수에서 $x_1$의 계수가 변한다는 것은 목적함수의 기울기가 변한다는 의미와 같다. 현재 목적함수의 기울기는 $x_1, x_2$ 평면 상에 나타내보면 $-\frac{5}{2}$이다. 최적해가 유지되려면 이 기울기가 자원 2에 해당하는 기울기인 -1과 자원 3에 해당하는 기울기인 -3사이에 있어야 함을 알 수 있다. 따라서, $x_1$의 계수가 $\Delta$만큼 변한다고 했을 때

$$-3 \leq -\frac{5 + \Delta}{2} \leq -1$$

이고, 이를 풀면 $-3 \leq \Delta \leq 1$이라는 결론을 얻을 수 있고, $2 \leq x_1 \leq 6$인 범위 내에서는 현재 최적해가 유지됨을 알 수 있다.

 

제약식의 우변 상수 변화

제약식의 우변 상수는 자원의 사용량 한계를 의미한다. 이번에는 자원 2의 사용 한계를 변화시켜 보겠다. 두번째 제약식의 우변상수가 $\delta$만큼 변한다고 할 때, 최적기저가 유지되기 위한 $\delta$의 범위를 구해보겠다.

 

현재해는 제약식 2와 3의 교점에서 생성되고, 두 직선의 교점에서 최적해가 나오도록 유지하면 된다. 따라서 제약식 2의 경계가 (6,0)과 (4.8, 3.6) 사이에서 형성되면 되고,

$$6 \leq (8 + \delta) \leq 8.4$$

이므로 $-2 \leq \delta \leq 0.4$로 구해진다.

 

자원의 잠재가격

잠재가격이란, 자원 $i$를 1만큼 더 사용할 수 있을 때, (즉 사용 한계량이 1 증가할 때) 최대이익의 변화량을 의미한다. 자원 3의 잠재가격을 구해보자.

 

자원 3의 우변상수 18을 19로 변경하면 최적해가 (5,3)에서 (5.5, 2.5)로 바뀌므로 이를 목적함수에 대입하면, 최적값이 31에서 32.5로 변화하므로 자원 3의 잠재가격은 1.5이다.

 

 

이와 같은 사후 분석을 민감도 분석이라고 한다. 오늘은 제품이 2개이고 자원이 3종류인 비교적 간단한 문제에 적용하였지만, 보다 더 복잡한 문제에 대한 민감도 분석도 현실에서는 중요한 과제 중 하나이다. 더 복잡한 민감도 분석에 대한 일반화는 심플렉스 테이블을 이용해서도 가능한데, 이는 추후 포스팅에서 다루도록 하겠다.