AI를 위한 필수 수학

451

Chapter 10 -

운용 과학

단체법을 사용하여 원문제를 풀 때 자동으로 쌍대 문제의 최적 비용(원문제의 최적 비용과 동

일)을 얻는다. 또한 원문제의 최종 태블로를 통해 쌍대 문제의 해 (최적화 변수 )를 확인할 수

있다. 최적화된 쌍대 변수는 원문제에 대한 해당 제약이 구속 조건

binding

일 경우에만

0

이 아니

다. 최적 쌍대 변수는 제약 조건에 관련된

그림자 가격

shadow

price

(라그랑주 승수)이므로 이 개념

은 직관적으로 명확해야 한다. 이 그림자 가격은 제한된 자원(구속 조건 )에 할당된 값으로 해

석할 수 있으며, 이때 해당 자원의 가치는 원문제의 목적 함수 값과 같게 된다. 최적 쌍대 변수

는 단체법의 최적 조건을 만족한다. 이는 단체법의 최종 태블로에서 기저 변수의 환산 비용이

반드시

0

이 되어야 하고, 최적 쌍대 변수가 최적 해에 연관된 그림자 가격이 되어야 함을 의미

한다.

또 다른 해석 방법으로는 쌍대 단체법을 쌍대 문제를 해결하는 변형된 단체법으로 생각하는 것

이다. 이때 쌍대 문제를 명시적으로 작성하지 않고 최대화하기 위해 단체법을 적용한다.

더욱이 단체법은 원문제의 일련의 기저 실행 가능 해를 생성한다 (이는 다면체의 꼭짓점에 해

당한다 ). 쌍대 실행 가능 해가 발견되는 즉시 해당 방법은 종료된다. 반면에 쌍대 단체법은 ...