[Optimization] 7. Dual model

안녕하세요. 이번 포스티에서는 Dual model에 대해서 배워보도록 하겠습니다.

Dual model은 복잡한 LP 모델을 보다 간단한 모델로 변환하는 방법입니다.

​

Primal problem은 아직 변환하기 전의 기존 문제로 정의됩니다.

Dual problem은 변환된 문제입니다.

Dual variable은 다음과 같은 변환을 따릅니다.

Primal problem이 min 혹은 max에 따라 부등호의 방향이 달라지며, 제약 조건의 부등호에 의해서도 결정됩니다.

위와 같은 문제를 Dual problem으로 변환해보겠습니다.

Dual variable의 부등호는 위와 같이 정의됩니다.

Dual problem 은 위와 같습니다.

​

Dual problem 전환 과정을 쉽게 정리해보면 위와 같은 식입니다.