선형계획법 사후분석 - Shadow price(잠재가격)

기존에 정리했던 선형계획법을 조금 더 확장하여, Shadow price(잠재가격)이 무엇인지 정리해보겠습니다. Shadow Price는 Dual Variable이라고도 불리며 쉽게 말해 제약조건이 완화 된다면 목적함수가 어떻게 변할지를 나타내는 수치라고 이해하면 편할 것 같습니다.

예를 들어 지난번 포스팅에서 해결했던 문제(https://direction-f.tistory.com/104)를 가지고 와본다면 아래와 같습니다.

결과적으로 위의 문제를 최적화를 해보면 군인 장난감(x1)은 20개 기차 장난감(x2)은 60개를 생산하는 것이 주어진 제약조건에서 최적화된 값이었습니다.

그렇다면 제약조건이 바뀌게 된다면 목적함수는 어떻게 바뀌게 될까요? 이를 나타내는 개념이 Shadow Price입니다. 즉 생산시간제약이 100이 아니라 101이면 어떻게 될지, 포장시간제약이 80이 아니라 90이 되면 어떻게 될지를 사후적으로 살펴보는 것입니다.

즉즉 Shaodw Price의 의미를 정리해 보면 주어진 자원의 가치가 무엇이야?에 대한 답을 찾는 것입니다.

---------------------------------------- ---------------------------------------- ----------------------------------------

[참고]

Shadow Price는 Dual Variable(쌍대변수)라고 불리기도 합니다. Dual Variable은 원래의 선형계획법문제의 쌍대문제로 나오는 해(solution)입니다.

기존의 문제는 주어진 제약조건에서 최대의 이익을 찾는 문제였습니다. 이 문제를 다르게 생각해보면 주어진 이익을 맞추기 위해 주어진 자원을 최소화하는 문제가 됩니다. 즉  군인 장난감(x1)은 20개 기차 장난감(x2)은 60개를 생산하기 위해 주어진 자원을 최소로 하는 문제로 볼수 있습니다. 따라서 위의 문제는 아래와 같은 쌍대문제로 바꿀 수 있습니다. 

즉 Dual Variable은 주어진 자원의 한계적 가치를 다루는 것입니다. (Shadow price가 나타내는 것과 동일합니다.)

(원문제를 쌍대문제로 바꾸는 것은 자세히 다루지는 않겠지만 간단히 설명하면, 제약조건 하나가 y로 대표되며 기존 최적화식의 계수들이 제약조건으로 되고 기존문제의 제약조건이 쌍대문제 최적화식의 계수가 됩니다. 이는 제약조건1에 y1을 곱하고, 제약조건3에 y3를 곱해서 기존문제의 부등식을 조합해보면 조금은 더 직관적으로 쌍대문제 변환을 이해할 수 있습니다.)

https://www.princeton.edu/~aaa/Public/Teaching/ORF363_COS323/F14/ORF363_COS323_F14_Lec12.pdf

---------------------------------------- ---------------------------------------- ----------------------------------------

 

다시 일전에 사용했던 예제를 통해서 한번 살펴보겠습니다.

 

from ortools.linear_solver import pywraplp
## from ortools.init import pywrapinit


## define solver
solver = pywraplp.Solver.CreateSolver('GLOP')

## define decision variable
x_1 = solver.NumVar(0, solver.infinity(), 'x_1')
x_2 = solver.NumVar(0, solver.infinity(), 'x_2')


## define constraints
constraint1 = solver.Add(2*x_1+x_2 <= 100)
constraint2 = solver.Add(x_1+x_2 <= 80)
constraint3 = solver.Add(x_1 <= 40)


## defince objective function
solver.Maximize(3*x_1 + 2*x_2)

## invoke the solver
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    
    print("최적해")
    print('Objective value =', solver.Objective().Value())
    print('x_1 =', round(x_1.solution_value(),0))
    print('x_2 =', round(x_2.solution_value(),0))
    
    
    print("shadow price(잠재가격)")
    print('생산시간제약 =', round(constraint1.dual_value(),0))
    print('포장시간제약 =', round(constraint2.dual_value(),0))
    print('생산수량제약 =', round(constraint3.dual_value(),0))
    

else:
    print('The problem does not have an optimal solution.')

최적해를 도출하는것 추가적으로 Shadow Price를 도출하는 코드를 추가했습니다. 결과를 살펴보면

최적해
Objective value = 180.0
x_1 = 20.0
x_2 = 60.0

shadow price(잠재가격)
생산시간제약 = 1.0
포장시간제약 = 1.0
생산수량제약 = 0.0

즉 기존 최적해는 군인 장난감(x1)은 20개, 기차 장난감(x2)은 60개를 생산하는 것인데 만약 생산시간제약이 한단위 늘어나면 목적함수는 181이 된다는 것을 뜻하게 됩니다.

즉 2x1+x2 <= 101이 되면, x1은 21개, x2는 59개를 생산할수 있게되어 목적함수값이 181이 됩니다. 

이제 역으로 원문제를 쌍대문제로 변경하여 해결해보겠습니다.

## define solver
solver = pywraplp.Solver.CreateSolver('GLOP')

## define decision variable
y_1 = solver.NumVar(0, solver.infinity(), 'y_1')
y_2 = solver.NumVar(0, solver.infinity(), 'y_2')
y_3 = solver.NumVar(0, solver.infinity(), 'y_3')


## define constraints
constraint1 = solver.Add(2 * y_1 + y_2 + y_3 >= 3) 
constraint2 = solver.Add(y_1 + y_2 >= 2)



## defince objective function
solver.Minimize(100 * y_1 + 80 * y_2 + 40 * y_3)

## invoke the solver
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    
    print("최적해")
    print('Objective value =', solver.Objective().Value())
    print('y_1 =', round(y_1.solution_value(),0))
    print('y_2 =', round(y_2.solution_value(),0))
    print('y_3 =', round(y_3.solution_value(),0))   
    

    

else:
    print('The problem does not have an optimal solution.')

위 코드의 결과를 보면 

Objective value = 180.0
y_1 = 1.0
y_2 = 1.0
y_3 = 0.0

위에서 도출한 shadow price와 동일한 값을 나타냄을 확인할 수 있습니다.

다시한번 정리하면 Shadow Price와 Dual variable은 주어진 자원이 변경되면 어떻게 의사결정이 달라질 수 있을지에 대해서 살펴보는 것이라고 보면 좋을 것 같습니다.