감소비용 (Reduced Cost)

한 줄 정의: 비기저변수를 1단위 늘릴 때 목적함숫값이 변하는 양으로, 진입변수 선택의 기준입니다.

쉽게 풀면

선형계획의 현재 해에서 0으로 놓여 있는 변수(예: 지금 안 만드는 제품)를 조금 만들기 시작하면 목적함수가 좋아질까요, 나빠질까요? 그 변화량이 감소비용입니다. 감소비용을 보면 어떤 변수를 새로 해에 넣을지, 혹은 이미 최적인지 판단할 수 있습니다.

왜 중요한가

단체법의 최적성 판정과 열생성법의 가격결정 문제는 모두 감소비용을 기준으로 돌아갑니다. 결과 해석에서는 '이 제품이 채택되려면 이익이 얼마나 올라야 하는가'를 알려 주어 관리적 시사점으로도 쓰입니다.

논문에서는 이렇게 쓰입니다

"가격결정 하위문제에서 음의 감소비용을 갖는 경로가 더 이상 발견되지 않아 열생성 절차를 종료하였다."

최소화 문제에서 감소비용이 모두 0 이상이면 최적이라는 판정을 쓴 예입니다.

조금 더 깊게 보면

변수 j의 감소비용은 c_j − z_j = c_j − c_B B⁻¹ a_j로, 원래 비용에서 현재 쌍대가격으로 평가한 자원 사용 가치를 뺀 값입니다. 교재에 따라 부호를 반대로(z_j − c_j) 정의하기도 합니다. 최소화 문제에서는 모든 감소비용이 0 이상이면 현재 기저해가 최적이고, 음수인 변수가 있으면 그 변수를 진입시켜 개선할 수 있습니다. 기저변수의 감소비용은 항상 0입니다. 열생성법에서는 수많은 열을 모두 나열하지 않고, 감소비용이 가장 작은 열을 찾는 하위문제를 풀어 새 열을 추가합니다.

주의할 점

'잠재가격'이 제약(우변)의 한계가치라면 감소비용은 변수(열)의 한계가치로, 서로 연결되어 있지만 대상이 다릅니다. 최대화·최소화 여부와 교재의 부호 정의에 따라 최적 판정 기준이 반대가 되므로 주의해야 합니다.