정수계획 문제를 푸는 기본 원리

분단탐색법은 정수계획 문제의 최적해를 찾는 대표적인 알고리즘이에요. 문제를 나누고 한계를 정하고 가능성 없는 가지를 걷어내는 과정을 정리했어요.

먼저 변수가 많은 정수계획 문제를 도해로 풀기 어려운 이유를 살펴봐요.

다음으로 선형계획 해를 바탕으로 문제를 나누는 분단하기를 알아봐요.

이어서 한계 정하기와 검토하기가 어떻게 이어지는지 확인해요.

마지막은 가지치기와 되돌아가기를 포함한 네 가지 구성요소와 정수계획의 특징이에요. 개념과 사례가 어떤 순서로 이어지는지 먼저 훑어보면 뒤의 설명이 훨씬 쉬워져요. 단계 이름만 외우기보다 각 항목이 왜 필요한지 함께 살펴보세요.

요약과 비교표, 용어 카드, 질문으로 핵심을 점검해 보세요. 처음 읽는 분도 흐름을 따라가기 쉽도록 핵심만 추려 정리했어요. 필요한 부분만 골라 읽어도 이해에 문제가 없어요. 문단마다 핵심 개념이 어떻게 이어지는지 차례대로 따라가 보면 전체 구성이 한눈에 들어와요. 복습할 때도 도움이 돼요.

Ad

문제를 나누고 한계를 정하는 과정

정수계획 모형을 효율적으로 해결하기 위해서 여러 가지 방법들이 제안되어 왔으나 현재까지 가장 효과적이면서 믿을 수 있다고 입증된 방법은 분단탐색법이다.

대부분의 상용 정수계획코드는 이러한 방법을 선택하고 있다.

분단탐색법은 처음에 문제를 선형계획법으로 풀고 만약 선형계획해가 정수여야 되는 변수에 정수값을 주면 되지만 아니라면 소수값을 반올림하는 등 전부 가능한 방법을 모색한다.

최적해를 포함할 가능성이 존재하는 하부집합들과 최적해를 포괄할 가능성이 없어서 더 이상은 조사할 필요가 없는 하부적인 집합들을 나누는 데에는 여러 가지 법칙이 사용된다.

각각의 하부집합에서 최상해 값의 상한은 정수 제한을 해제한 선형적인 계획문제의 해에 의해서 정해진다.

어느 때에든 정수 제한을 해제한 선형계획문제의 해가 이것이 정수해가 되면 하부적인 집합의 최상해가 구해진 것이며 이러한 때에 하부집하의 하한이 정해진다.

전부 가능한 하부집합의 정수가능해 중에서 최상의 것이 최적해가 되는 것이다.

반면에 정수 계획법에서 최적해가 꼭 실행영역의 외곽 부분 꼭지점에 존재하게 되는 것이 아니고 최적해를 계산해주는 심플렉스 방법과 동일한 체계적인 절차가 없이 몇 가지의 탐색적인 절차들에 의존하여서 수행한다.

분단 탐색은 해의 집합을 늘어놓아가면서 최적해의 가능성을 검토하고 아예 가능성이 없는 집합은 고려할 대상에서 제외시켜 검토영역을 계속적으로 좁혀 나감으로써 최적인 정수해를 모색하는 방법이다.

해의 집합을 늘어놓기 때문에 부분적 열거법이라고도 볼 수 있으며, 다른 해법에 비해서 개념상으로나 계산상으로 제일 우수한 방법으로 알려져 있다.

알고리즘에 대한 설명 이후에 이 알고리즘의 타당성에 대해 본인의 생각을 기술 1.

분단탐색법 알고리즘 정수계획모형에서 변수를 3개 이상 포함하는 정수계획모형은 단순하게 도해적인 방법으로만 해결할 수 없으므로 다른 해결의 과정이 이용되어야만 한다.

새로운 두 개의 부분적인 문제를 만들어가는 과정이고 이것의 기본적 개념은 의사결정 나무에 기초를 두고 있다.…

가지치기와 되돌아가기 정리

분단탐색법의 단계와 구성요소

  • 정수계획 모형은 변수가 셋 이상이면 도해로 풀기 어려워 분단탐색법을 쓰며 대부분의 상용 정수계획 코드가 이 방법을 택한다.
  • 분단탐색법은 선형계획으로 먼저 풀고 정수가 아니면 가능해 집합을 나누어 상한과 하한으로 가능성 없는 집합을 제외해 간다.
  • 구성요소는 분단하기와 한계 정하기와 가지치기와 되돌아가기이며 정수가능해를 모두 비교해야 해서 선형계획보다 복잡하다.

정수계획 문제와 분단탐색법의 원리

  • 정수계획모형에서 변수가 세 개 이상이면 도해적인 방법만으로는 풀 수 없어 다른 해결 과정이 필요하다.
  • 정수계획 모형을 푸는 여러 방법 중 지금까지 가장 효과적이고 믿을 만하다고 입증된 방법이 분단탐색법이다.
  • 대부분의 상용 정수계획 코드가 분단탐색법을 선택하고 있다.
  • 먼저 문제를 선형계획법으로 풀어 보고 정수여야 하는 변수가 정수값이면 그대로 쓰고 아니면 가능한 방법을 찾는다.
  • 가능해의 집합을 작은 하부 집합으로 나누는 것을 분단하기라고 한다.
  • 각 하부 집합의 최상해 상한은 정수 제한을 풀어 놓은 선형계획 문제의 해로 정해진다.
  • 그 해가 정수해가 되면 하부 집합의 최상해가 구해진 것이며 이때 하한이 정해진다.
  • 가능한 하부 집합의 정수가능해 중에서 가장 좋은 것이 최적해가 된다.

세 단계와 네 가지 구성요소

  • 심플렉스 방법은 근접한 꼭지점을 따라 움직이며 더 나은 값을 찾지만 정수계획의 최적해는 꼭지점에 있지 않을 수 있다.
  • 그래서 정수계획은 체계적인 절차 대신 몇 가지 탐색적 절차에 의존한다.
  • 분단탐색법은 문제 나누기와 한계 정하기와 검토하기의 세 단계로 나눌 수 있다.
  • 문제 나누기는 완화된 선형계획 문제의 영역을 정수가 아닌 변수를 기준으로 서로 겹치지 않는 두 영역으로 나눈다.
  • 한계 정하기는 나뉜 두 문제의 해를 구해 원래 문제가 가질 수 있는 값의 한계를 정하는 단계이다.
  • 검토하기는 한계값이 정해진 각 문제가 최적해가 될 가능성이 있는지 살피고 가능성이 없으면 대상에서 제외한다.
  • 구성요소는 분단하기와 한계 정하기와 가지치기와 되돌아가기이며 하위 문제의 해가 상한에 못 미치면 가지치기를 하고 다른 하위 문제로 되돌아간다.
  • 정수계획모형은 의사결정 변수가 정수일 때만 의미가 있거나 활동을 할지 말지 정할 때 쓰이며 정수가능해를 모두 비교해야 해서 선형계획보다 복잡하고 오래 걸린다.
Ad

분단탐색법의 세 단계

단계하는 일핵심
문제 나누기완화된 문제의 영역을 둘로 나눔정수가 아닌 변수를 기준으로 분할
한계 정하기나뉜 문제의 해로 값의 한계를 정함상한과 하한을 확인
검토하기최적해 가능성을 검토가능성 없는 문제는 제외
반복정수 조건이 충족될 때까지 되풀이가지치기와 되돌아가기 포함

핵심 개념

  • 분단탐색법 — 가능해 집합을 나누고 상한과 하한으로 가능성 없는 부분을 제외해 가며 최적의 정수해를 찾는 방법이다.
  • 정수계획법 — 결정변수가 정수여야 한다는 조건이 붙은 선형계획 문제를 푸는 방법이다.
  • 가지치기 — 하위 문제의 해가 상한에 못 미칠 때 더 나누지 않고 포기해 시간을 아끼는 과정이다.
  • 되돌아가기 — 가지치기 뒤에 다른 하위 문제로 돌아가 분단하기를 이어 가는 과정이다.

자주 묻는 질문

  • Q. 분단탐색법은 왜 쓰나요?
    A. 변수가 많은 정수계획 문제는 도해로 풀 수 없고 분단탐색법이 가장 효과적이고 믿을 만하다고 입증된 방법이라 상용 코드에서 많이 쓴다.
  • Q. 분단탐색법은 어떤 단계로 이루어지나요?
    A. 문제 나누기와 한계 정하기와 검토하기의 세 단계로 나뉘며 이를 반복해 정수제약을 만족하는 최적해를 찾는다.
  • Q. 정수계획이 선형계획보다 복잡한 이유는 무엇인가요?
    A. 정수가능해가 띄엄띄엄 있어서 후보 정수해를 모두 열거하고 비교하여 최적해를 찾아야 하기 때문이다.

정리

분단탐색법은 문제를 나누고 한계를 정하고 가능성 없는 가지를 제외하며 정수제약을 만족하는 최적해를 찾는 방법이며 정수계획은 선형계획보다 복잡하고 시간이 많이 걸린다고 정리한다.

Advertisements

이 글이 도움이 됐다면 친구에게 공유해 주세요

필요한 친구에게 한 번에 보내 보세요. 공유는 큰 힘이 돼요.

네이버 블로그 스레드
이 자료 전체가 필요하신가요?총

환불규정

디지털 파일은 결제 후 즉시 제공되므로 환불이 제한됩니다.
◆환불 불가
- 단순 변심 / 일부 사용 후 환불 요청 / 구매 후 7일 경과
◆ 예외
- 파일 오류 / 다운로드 및 작동 불가 /
◆ 환불요청방식 : 상단의 고객센터 1:1 문의요청