Feasible region — 허용 해 영역
허용 해 영역 (ХДР) (또한 허용 해 집합, 영어 Feasible region, feasible set) — 운용 과학, 최적화 및 수학적 모델링에서 이는 문제에 부과된 모든 제약 조건을 만족하는 가능한 모든 해(변수 값의 집합)의 집합이다.
허용 해 영역은 최적 해를 탐색하는 부분 공간을 나타낸다. 이 영역 밖에 있는 모든 해는 허용 불가능한 해이다.
정의 및 형성
허용 해 영역은 문제의 각 개별 제약 조건에 의해 정의되는 집합들의 교집합으로 형성된다. 제약 조건은 다음과 같은 형태로 표현될 수 있다:
- 부등식: 변수 값 또는 그 조합에 대한 상한 또는 하한을 설정한다 (예: "자원 A의 소비량은 100단위를 초과해서는 안 된다", "생산된 제품의 수량은 50개 이상이어야 한다").
- 등식: 조건의 정확한 충족을 요구한다 (예: "총 수송량은 1000톤과 같아야 한다", "입출 흐름의 균형은 0이다").
- 변수의 부호 조건: 변수는 종종 비음수이거나, 정수이거나, 특정 이산 집합에 속해야 한다.
점(또는 변수 값의 벡터)이 허용 해 영역에 속하는 것은 그것이 이 모든 제약 조건을 동시에 만족할 때, 그리고 오직 그때에만 성립한다.
기하학적 해석
허용 해 영역은 특히 변수의 수가 적은 문제에서 명확한 기하학적 해석을 가지는 경우가 많다:
- 2차원 공간 (변수 2개): 각각의 선형 부등식 제약 조건은 반평면을 정의한다. 허용 해 영역은 이 반평면들의 교집합으로, 볼록 다각형(경우에 따라 비유계이거나 공집합일 수 있음)을 이룬다.
- 3차원 공간 (변수 3개): 각각의 선형 부등식 제약 조건은 반공간을 정의한다. 허용 해 영역은 이 반공간들의 교집합으로, 볼록 다면체(폴리헤드론)를 이룬다.
- 다차원 공간: 선형 제약 조건으로 정의되는 허용 해 영역은 볼록 다면체(폴리토프)이다.
비선형 제약 조건의 경우 허용 해 영역은 더 복잡한 형태를 가질 수 있으며 볼록하지 않을 수 있다.
최적화에서의 역할
허용 해 영역은 최적화에서 근본적인 역할을 한다:
1. 탐색 공간의 정의: 문제의 최적 해(존재하는 경우)는 항상 허용 해 영역의 내부 또는 경계에 위치한다. 최적화 알고리즘은 바로 이 영역에서 목적 함수의 극값을 탐색한다. 2. 해의 존재 여부 확인: 허용 해 영역이 공집합인 경우(즉, 제약 조건들이 서로 모순되는 경우), 문제는 허용 가능한 해를 가지지 않으며, 따라서 최적 해도 존재하지 않는다. 3. 최적 해에 대한 영향: 허용 해 영역의 형태와 크기는 목적 함수의 극값 달성 가능성과 그 극값의 크기에 직접적인 영향을 미친다.
허용 해 영역의 성질 (선형 계획법 문제에서)
모든 제약 조건과 목적 함수가 선형인 선형 계획법(LP) 문제에서 허용 해 영역은 중요한 성질을 가진다:
- 볼록성: 두 점이 허용 해 영역에 속하면, 이 두 점을 잇는 선분 전체도 허용 해 영역에 속한다. 이 성질은 최적 해(존재하고 유일한 경우)가 허용 해 영역 다면체의 꼭짓점 중 하나에 위치함을 보장한다.
- 폐집합성: 허용 해 영역은 자신의 경계를 포함한다(비엄격 부등식 ≤, ≥ 및 등식으로 인해).
허용 해 영역은 다음과 같을 수 있다:
- 유계: 유한한 크기를 가진다.
- 비유계: 하나 이상의 방향으로 무한히 뻗어 있다.
- 공집합: 단 하나의 점도 포함하지 않는다.
참고 문헌
- Ventzel E. S. 운용 과학: 과제, 원리, 방법론. — 모스크바: Nauka, 1988.
- Akof R., Sasieni M. 운용 과학의 기초. — 모스크바: Mir, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
참조
- 운용 과학
- 최적화
- 수학적 모델
- 제약 조건
- 허용 해
- 최적 해
- 목적 함수
- 선형 계획법
- 볼록 집합