쌍대성이론 (Duality Theory)
한 줄 정의: 하나의 최적화 문제(주문제)에 대응해, 그 해의 성질을 다른 각도에서 분석할 수 있는 쌍(쌍대문제)이 존재한다는 것을 다루는 이론입니다.
쉽게 풀면
어떤 최적화 문제를 "얼마나 이익을 최대화할 수 있는가"로 볼 수도 있지만, 같은 문제를 뒤집어 "자원 하나를 추가로 얻으면 이익이 얼마나 늘어나는가"라는 관점에서도 볼 수 있습니다. 쌍대성이론은 이 두 관점이 사실은 같은 문제를 다른 방식으로 표현한 것이며, 서로 긴밀하게 연결되어 있다는 것을 설명합니다. 원래 문제를 주문제, 뒤집은 문제를 쌍대문제라고 부릅니다. 이 둘을 함께 보면 원래 문제만으로는 알기 어려운 정보를 얻을 수 있습니다.
왜 중요한가
쌍대성이론은 자원의 한계가치(그림자가격)를 계산할 수 있게 해주어, 어떤 자원을 늘리는 것이 가장 이익이 되는지 같은 경영 의사결정에 직접적인 통찰을 제공합니다. 또한 최적해 검증이나 알고리즘 설계에서도 이론적 기반으로 폭넓게 활용됩니다.
논문에서는 이렇게 쓰입니다
"쌍대성이론(Duality Theory)에 근거하여 각 제약조건의 그림자가격(shadow price)을 산출하였다."
제약을 하나 완화했을 때 목적함수가 얼마나 개선되는지를 쌍대이론을 통해 계산했다는 의미입니다.
"주문제와 쌍대문제의 목적함수 값이 최적해에서 일치함을 강쌍대성(strong duality)을 통해 확인하였다."
일정 조건 아래에서 주문제와 쌍대문제의 최적값이 동일하다는 성질을 활용해 결과를 검증했다는 뜻입니다.
조금 더 깊게 보면
쌍대성에는 주문제의 목적값이 쌍대문제의 목적값보다 항상 작거나 같다는 약쌍대성(weak duality)과, 특정 조건 하에서 두 값이 정확히 일치하는 강쌍대성이 있습니다. 선형계획법에서는 일반적으로 강쌍대성이 성립하는 것으로 알려져 있으며, 이는 최적해를 검증하는 유용한 도구로 쓰입니다.
주의할 점
비선형계획법이나 정수계획법에서는 강쌍대성이 항상 성립하지는 않으며, 이 경우 주문제와 쌍대문제의 최적값 사이에 차이(duality gap)가 존재할 수 있습니다.