
분단탐색법은 정수계획 문제의 최적해를 찾는 대표적인 알고리즘이에요. 문제를 나누고 한계를 정하고 가능성 없는 가지를 걷어내는 과정을 정리했어요.
먼저 변수가 많은 정수계획 문제를 도해로 풀기 어려운 이유를 살펴봐요.
다음으로 선형계획 해를 바탕으로 문제를 나누는 분단하기를 알아봐요.
이어서 한계 정하기와 검토하기가 어떻게 이어지는지 확인해요.
마지막은 가지치기와 되돌아가기를 포함한 네 가지 구성요소와 정수계획의 특징이에요. 개념과 사례가 어떤 순서로 이어지는지 먼저 훑어보면 뒤의 설명이 훨씬 쉬워져요. 단계 이름만 외우기보다 각 항목이 왜 필요한지 함께 살펴보세요.
요약과 비교표, 용어 카드, 질문으로 핵심을 점검해 보세요. 처음 읽는 분도 흐름을 따라가기 쉽도록 핵심만 추려 정리했어요. 필요한 부분만 골라 읽어도 이해에 문제가 없어요. 문단마다 핵심 개념이 어떻게 이어지는지 차례대로 따라가 보면 전체 구성이 한눈에 들어와요. 복습할 때도 도움이 돼요.
정수계획 모형을 효율적으로 해결하기 위해서 여러 가지 방법들이 제안되어 왔으나 현재까지 가장 효과적이면서 믿을 수 있다고 입증된 방법은 분단탐색법이다.
대부분의 상용 정수계획코드는 이러한 방법을 선택하고 있다.
분단탐색법은 처음에 문제를 선형계획법으로 풀고 만약 선형계획해가 정수여야 되는 변수에 정수값을 주면 되지만 아니라면 소수값을 반올림하는 등 전부 가능한 방법을 모색한다.
최적해를 포함할 가능성이 존재하는 하부집합들과 최적해를 포괄할 가능성이 없어서 더 이상은 조사할 필요가 없는 하부적인 집합들을 나누는 데에는 여러 가지 법칙이 사용된다.
각각의 하부집합에서 최상해 값의 상한은 정수 제한을 해제한 선형적인 계획문제의 해에 의해서 정해진다.
어느 때에든 정수 제한을 해제한 선형계획문제의 해가 이것이 정수해가 되면 하부적인 집합의 최상해가 구해진 것이며 이러한 때에 하부집하의 하한이 정해진다.
전부 가능한 하부집합의 정수가능해 중에서 최상의 것이 최적해가 되는 것이다.
반면에 정수 계획법에서 최적해가 꼭 실행영역의 외곽 부분 꼭지점에 존재하게 되는 것이 아니고 최적해를 계산해주는 심플렉스 방법과 동일한 체계적인 절차가 없이 몇 가지의 탐색적인 절차들에 의존하여서 수행한다.
분단 탐색은 해의 집합을 늘어놓아가면서 최적해의 가능성을 검토하고 아예 가능성이 없는 집합은 고려할 대상에서 제외시켜 검토영역을 계속적으로 좁혀 나감으로써 최적인 정수해를 모색하는 방법이다.
해의 집합을 늘어놓기 때문에 부분적 열거법이라고도 볼 수 있으며, 다른 해법에 비해서 개념상으로나 계산상으로 제일 우수한 방법으로 알려져 있다.
알고리즘에 대한 설명 이후에 이 알고리즘의 타당성에 대해 본인의 생각을 기술 1.
분단탐색법 알고리즘 정수계획모형에서 변수를 3개 이상 포함하는 정수계획모형은 단순하게 도해적인 방법으로만 해결할 수 없으므로 다른 해결의 과정이 이용되어야만 한다.
새로운 두 개의 부분적인 문제를 만들어가는 과정이고 이것의 기본적 개념은 의사결정 나무에 기초를 두고 있다.…
| 단계 | 하는 일 | 핵심 |
|---|---|---|
| 문제 나누기 | 완화된 문제의 영역을 둘로 나눔 | 정수가 아닌 변수를 기준으로 분할 |
| 한계 정하기 | 나뉜 문제의 해로 값의 한계를 정함 | 상한과 하한을 확인 |
| 검토하기 | 최적해 가능성을 검토 | 가능성 없는 문제는 제외 |
| 반복 | 정수 조건이 충족될 때까지 되풀이 | 가지치기와 되돌아가기 포함 |
분단탐색법은 문제를 나누고 한계를 정하고 가능성 없는 가지를 제외하며 정수제약을 만족하는 최적해를 찾는 방법이며 정수계획은 선형계획보다 복잡하고 시간이 많이 걸린다고 정리한다.
환불규정