심플렉스 알고리즘
심플렉스 알고리즘은 선형 제약식과 선형 목적 함수가 정의된 최적화 문제를 다면체의 기저해 사이에서 이동하며 푼다 선형 계획법 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다...
| 분류 | 알고리즘 · 선형 계획법 |
|---|---|
| 주요 목적 | 선형 제약식과 선형 목적 함수가 정의된 최적화 문제를 다면체의 기저해 사이에서 이동하며 푼다 |
| 핵심 방법 | 현재 기저에서 비기저 변수를 진입시키고 비율 검사로 이탈 변수를 정해 피벗 연산을 반복한다 |
| 복잡도 | 최악에는 지수적 피벗 횟수가 가능하지만 실제 많은 문제에서 효율적이다 |
| 적용 조건 | 최소화·최대화 목적과 선형 제약, 변수의 부호 조건이 명확해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
심플렉스 알고리즘은 선형 제약식과 선형 목적 함수가 정의된 최적화 문제를 다면체의 기저해 사이에서 이동하며 푼다 선형 계획법 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 현재 기저에서 비기저 변수를 진입시키고 비율 검사로 이탈 변수를 정해 피벗 연산을 반복한다. 목적 함수가 개선되는 방향을 선택하며 최적성·비유계성·실행 불가능성을 판정하는 절차가 필요하다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 최악에는 지수적 피벗 횟수가 가능하지만 실제 많은 문제에서 효율적이다 실제 구현에는 최소화·최대화 목적과 선형 제약, 변수의 부호 조건이 명확해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 1947년 George Dantzig가 개발했다. 선형 최적화·산업 운영 연구·자원 배분에 사용하며 내부점 방법과 다른 계산 경로를 가진다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]