[경영학과] 2021년 2학기 경영의사결정론 기말시험 과제물(분단탐색법 알고리즘)

목차

선형계획법(LP; Linear Programming)의 특별한 경우로 정수계획법(IP; Integer Programming)을 들 수 있다. 혼합 정수계획법(Mixed Integer Programming)의 해법 중에 분단탐색법(Branch and Bound) 알고리즘에 대해 설명하시오. 알고리즘에 대한 설명 이후에 이 알고리즘의 타당성에 대해 본인의 생각을 기술하시오.


- 목 차 -

I. 서 론

II. 본 론
1. 알고리즘의 존재의 이유와 문제점
2. 분단탐색법의 타당성

III. 결 론

참고문헌


<< 함께 제공되는 참고자료 한글파일 >>
1. 분단탐색법이란.hwp
2. 분단탐색법의 절차.hwp

본문내용

Ⅰ. 서 론

경영학에서 소비자의 의사 결정을 좌지우지 하는 것은 지금 시대 흐름에 맞는 알고리즘의 유무이다. 알고리즘에 쌓인 누적된 데이터는 소비자에게 남다른 신뢰감을 주고 기업 또한 편리함이 있기에 필수적인 요소로 뽑힌다. 21세기 들어 알고리즘의 지속된 발전은 여러 시장에서 소비자 혹은 기업이 의사를 결정하는데 있어서 큰 도움을 주었다.
선형계획법은 특히 가장 획기적인 알고리즘으로 뽑혔고, Microeconomics분야에서는 소비자의 흐름, 시대 경향을 분석하는데 있어서 큰 성과를 거두었기 때문에 가장 일반적인 운용과학 기법으로 뽑힌다. 이 중에서 정수계획법은 선형 계획 모델에 대해서 최적의 값을 구하기 위하여 만들어진 선형계획모델의 2.0 버전이라고 할 수 있다.
분단탐색 방법은 목표 영역을 여러 개의 하위 그룹으로 나누고 각 집합에서 최적 결과의 최고 값과 최저 값을 결정하고 고려 범위에 포함되지 않은 하위 그룹을 삭제하고 목표 솔루션을 찾을 때까지 이 과정을 계속해서 반복하는 기법을 말한다. 영어로는 ‘Branch and Bound’라고 표기한다. branch는 알다시피 나뭇가지를 뜻하고 bound는 “묶는 것, 혹은 그러할 가능성이 큰”이란 뜻이다. 다시 말해, 나뭇가지는 여러개의 소집단을 뜻하는 것이다. 이 기법은 인수 라 불리는 것의 의 최소값을 찾는 것이라 표현할 수 있다. 여러개의 목표 가능성을 갖고 있는 재료들이 그들만의 “region”을 구성하게 되고 자연스럽게 그것은 우리가 아는 Brach가 된다. 그리고 그것은 커지고 커져 Tree를 형성하게 되고 그 안에서 최적의 값을 도출한다. Brach and Bound는 소집단을 목표영역으로 분류된 최적의 값으로 가능성이 큰 값을 대상으로 지칭한 것이다. 이것의 핵심은 값의 오류를 방지하기 위해 다른 수집한 lower bound가 다른 영역의 upper bound보다 값이 크다면 탐색하여 분류된 영역에서 제거하는 것이다. 우리는 이러한 과정을 “pruning” 이라 부르고, 이 과정은 모든 subregion에서 최소한의 minimum bound를 기록하고 유지함으로써 구현되는 것이고, lower bound의 값이 의 값보다 클때에는 계속해서 제거되기 때문에 편리함이 있다. 이상향으로 하는 것은 우리가 분류한 영역에서 변수값으로 떠오르는 것을 모두 제거하거나 해결되면 끝이난다. 그렇게 되면 모든 subregion은 함수 모든 구역의 최소값과 같은 을 갖게될 것이다. 그러나 한가지 문제로 제기되는 것은, 목표영역을 추정하여 분류하고 가감하는 이 과정을 최적의 값이 도출되기 전까지 계속해서 반복하는 것인데, 과연 이 알고리즘은 현실적일까? 혹은 현실적이라 하여도 다른 알고리즘에 비하여 어디가 더 나은 것일까? 그리고 근본적으로 알고리즘이 갖고있는 결함은 무엇일까?


- 중략 -

참고 자료

없음