선형계획법 > Reduced Cost(수정비용)

Reduced Cost는 선형계획법에서 최적해에 대한 민감도를 나태는 수치입니다. 현재 최적해에 포함되어 있지 않은 변수가 추가되어 한 단위 변화할때 목적함수 값이 어떻게 변화하는 지를 나타냅니다. 다시 말해, 현재 해가 최적인 상황에서 특정 변수를 해에 포함시키는 것이 이득인지 손해인지를 알려주는 값이라고 생각하시면 됩니다.

직관적으로는 현재는 최적해로 포함되어 있지 않은 변수를 포함시켰을 때 지불해야하는 비용이라고 이해하시면 편할 것 같습니다. 따라서 현재 최적해에 이미 포함되어 있는 변수들의 Reduced Cost는 0입니다. 

Reduced Cost의 해석은 다음과 같습니다.

기본해(Basic Solution): 현재 최적해에서 0이 아닌 값을 가지는 변수들
비기본해(Non-basic Solution): 현재 최적해에서 0의 값을 가지는 변수들

Reduced Cost가 0인 경우: 해당 변수가 최적해에 포함되어 있음을 의미(-> Basic Solution)
Reduced Cost가 0이 아닌 경우: 해당 변수를 증가시키면 목적함수 값이 변화함을 의미(-> Non-basic Solution)

예시를 통해 한번 살펴보겠습니다.

위와 같은 문제가 있다고 했을 때 해당 최적화 문제를 해결하면 최적해는 x1=40, x2=10, x3=0이 됩니다. 이때 x3를 강제로 한단위 넣으면 목적함수가 어떻게 변할지를 보는 것이 Reduced Cost입니다. Reduced Cost를 확인하는 코드는 아래와 같습니다.

from ortools.linear_solver import pywraplp


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

## define decision variables
x_1 = solver.NumVar(0, solver.infinity(), 'x_1')  # 제품 A 생산량
x_2 = solver.NumVar(0, solver.infinity(), 'x_2')  # 제품 B 생산량
x_3 = solver.NumVar(0, solver.infinity(), 'x_3')  # 제품 C 생산량


## define constraints
# 원자재 제약
constraint1 = solver.Add(2*x_1 + 4*x_2 + 4*x_3 <= 120)  # 원자재 1 제약
constraint2 = solver.Add(x_1 + 2*x_2 + 3*x_3 <= 100)    # 원자재 2 제약

# 생산능력 제약
constraint3 = solver.Add(x_1 <= 40)  # 제품 A 최대 생산량
constraint4 = solver.Add(x_2 <= 30)  # 제품 B 최대 생산량
constraint5 = solver.Add(x_3 <= 20)  # 제품 C 최대 생산량


## defince objective function
solver.Maximize(8*x_1 + 4*x_2 + 1*x_3)  # 이익 최대화

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

if status == pywraplp.Solver.OPTIMAL:
    
    print("최적해")
    print('목적함수 값 =', solver.Objective().Value())
    print('제품 A 생산량 (x_1) =', round(x_1.solution_value(), 0))
    print('제품 B 생산량 (x_2) =', round(x_2.solution_value(), 0))
    print('제품 C 생산량 (x_3) =', round(x_3.solution_value(), 0))
    
    
    print("\nShadow Price(잠재가격)")
    print('원자재 1 제약 =', round(constraint1.dual_value(), 0))
    print('원자재 2 제약 =', round(constraint2.dual_value(), 0))
    print('제품 A 생산능력 제약 =', round(constraint3.dual_value(), 0))
    print('제품 B 생산능력 제약 =', round(constraint4.dual_value(), 0))
    print('제품 C 생산능력 제약 =', round(constraint5.dual_value(), 0))
    
    print("\nReduced Cost")
    print('제품 A의 Reduced Cost =', round(x_1.reduced_cost(), 0))
    print('제품 B의 Reduced Cost =', round(x_2.reduced_cost(), 0))
    print('제품 C의 Reduced Cost =', round(x_3.reduced_cost(), 0))

else:
    print('The problem does not have an optimal solution.')
    
    """
    최적해
목적함수 값 = 360.0
제품 A 생산량 (x_1) = 40.0
제품 B 생산량 (x_2) = 10.0
제품 C 생산량 (x_3) = 0.0

Shadow Price(잠재가격)
원자재 1 제약 = 1.0
원자재 2 제약 = -0.0
제품 A 생산능력 제약 = 6.0
제품 B 생산능력 제약 = 0.0
제품 C 생산능력 제약 = 0.0

Reduced Cost
제품 A의 Reduced Cost = 0.0
제품 B의 Reduced Cost = 0.0
제품 C의 Reduced Cost = -3.0
"""

 

기존에 해에 포함되어 있던 x1, x2는 Reduced Cost가 0, x3는 -3임을 알 수 있습니다. 즉 x3를 강제로 한단위 넣는다면 목적함수가 -3만큼 감소함을 나타냅니다. (제약조건1에 의해 x2가 한단위 줄어들고 x3가 한단위 늘어나야 하기 때문)