경영의사결정론 ) 혼합 정수계획법(Mixed Integer Programming)의 해법 중에 분단탐색법(Branch and Bound) 알고리즘에 대해 설명하시오. (2)

목차

1. 서론

2. 본론
2.1. 선형계획법과 정수계획법
2.2. 혼합 정수계획법의 해법과 분단탐색법 알고리즘
2.3. 분단탐색법 알고리즘은 타당한가

3. 결론

4. 참고문헌

본문내용

1. 서론
여러 문제 해결과정에서, 다양한 방법들 중 가장 적절한 것을 찾아내는 것을 최적화라고 할 수 있는데, 이러한 방법에 대해 연구하는 이론들을 최적화이론이라고 부를 수 있다.

2. 본론
2.1. 선형계획법과 정수계획법
선형계획법이란 선형계획의 문제를 해결하는 방법을 의미하는데, 기하학적 방법과 대수적인 방법으로 나뉜다. 선형계획법의 기하학적 방법은, 좌표평면에 여러 조건들을 제시하여 목적함수의 최댓값과 최솟값을 찾는 방법으로, 말 그대로 기하학적 도형을 이용한다. 반면에 단체법은 변수가 4개 이상이어서 기하학적인 방법을 사용할 수 없을 때 이용하는 것으로, 일반적이고 효과적인 방법으로 해당 값들을 찾게 된다.
선형계획법에는 정수계획법이 있는데, 선형계획법에서 세우는 여러 가정들 중에서 변수가 정수값만을 가져야 하는 경우에 사용되는 방법이 정수계획법이다.

참고자료

· Nemhauser, G. L. & Wolsey, L. A. (1988). Integer and combinational optimization. Whiley. ISBN 978-0-471-82819-8.
· Little, J. C., Murty, K. G., Sweeney, D. W. & Karel, C. (1963). An algorithm for the traveling salesman problem. Operations Research. 11 (6): 972-989.