線形計劃法의 심플렉스 알고리즘과 쿤-터커條件

Abstract

이 노트는 線型計劃法의 쿤-터커條件에 등장하는 선택변수， 여분변수，쌍대변수 등

모든 변수들이 심플렉스표에서 찾아지는 이유를 체계적으로 설명한다.

최적화 기법으로서의 線形計劃法은 그 뒤에 개발된 非線形計劃法 속에 포함되고 말아

이론적으로는 점점 우리의 관심의 대상에서 멀어지는 경향이 있다. 그러나 비선형계획법

의 쿤-터커조건이 선형계획법에서는 최적화의 필요충분조건이 된다는 매력적인 성질과

심플렉스 알고리즘으로 그 구체적인 최적해를 구할 수 있다는 또 하나의 매력은 선형계

획법에 대한 관심을 버리지 못하게 하고 있다.

이 노트에서는 심플렉스 알고리즘에서 사용되는 심플렉스표에 등장하는 각각의 항목들

이 쿤-터커조건과 구체적으로 어떻게 관련되는지와 원문제， 쌍대문제의 선택변수，여분변

수들이 어떤 모습으로 등장하는지에 관한 별로 알려져 있지 않은 내용을 체계적으로 정

리해 보고자 한다.