Optimal solution (optimization) — 최적해

최적해 — 운용 과학, 최적화 이론 및 의사결정 이론에서, 문제의 모든 제약 조건을 만족하는 허용 가능한 해(즉, 실행 가능해) 중에서 목적 함수의 극값(문제의 정식화에 따라 최댓값 또는 최솟값)을 보장하는 해를 말한다.

최적해를 탐색하는 것은 대부분의 최적화 문제를 푸는 주된 목표이다.

본질과 특성

최적해는 두 가지 핵심 특성을 가진다:

1. 실행 가능성: 모델 변수에 부과된 모든 제약 조건을 만족해야 한다. 즉, 최적해는 항상 실행 가능 영역(feasible region)에 속한다. 2. 목적 함수의 극값성: 모든 실행 가능해 중에서 최적성 기준을 형식화하는 목적 함수의 최선의(최대 또는 최소) 값을 보장한다.

모든 실행 가능해가 최적해인 것은 아니지만, 모든 최적해는 반드시 실행 가능해이어야 한다.

실행 가능 영역과의 관계

실행 가능 영역이란 문제의 제약 조건을 만족하는 모든 대안(변수 값의 집합)으로 이루어진 집합이다. 최적해는 이 영역 내에서 목적 함수가 극값에 도달하는 점(또는 점들)이다. 실행 가능 영역이 공집합이면 문제는 실행 가능해도, 따라서 최적해도 존재하지 않는다.

목적 함수와 제약 조건의 역할

• 제약 조건은 가능한 해의 집합(실행 가능 영역)을 결정한다.
• 목적 함수는 가능한 해 중 어느 것이 최선인지(최적인지)를 결정한다.

목적 함수 없이는 어느 실행 가능해가 최적인지 판별할 수 없다. 제약 조건 없이는 문제가 자명하거나 유한한 최적해를 갖지 않을 수 있다(예: 제약 조건 없이 선형 함수를 최대화하는 경우).

최적해의 유일성

최적해는 항상 유일하지는 않다. 일부 문제(예: 선형 계획법에서 목적 함수가 활성 제약 조건 중 하나에 평행한 경우)에서는 목적 함수 값이 동일한 최적해가 무한히 많이 존재할 수 있다. 그러나 최적점(또는 최적점들)에서의 목적 함수 값은 항상 유일하다(최적값이 존재하는 경우).

탐색 방법

운용 과학에서 최적해를 탐색하기 위해 모델의 유형에 따라 다양한 수학적 방법이 사용된다:

• 심플렉스법(선형 계획법)
• 경사하강법 및 기타 수치 방법(비선형 계획법)
• 분기한정법, 절단 평면법(정수 계획법)
• 동적 계획법

모델 의존성

어떤 해가 최적인지는 채택된 수학적 모델의 범위 내에서만 성립함을 이해하는 것이 중요하다. 모델이 실제 상황을 부적절하게 반영하는 경우(목적 함수가 잘못 선택되었거나, 중요한 제약 조건이나 의존 관계가 고려되지 않은 경우), 형식적으로 도출된 최적해는 실제로는 비효율적이거나 심지어 잘못된 결과를 낳을 수 있다.

다기준 문제에서의 최적성

여러 목적 함수를 가진 문제(다기준 최적화)에서는 단일 최적해라는 개념이 흔히 파레토 최적성의 개념으로 대체된다. 파레토 최적해란 하나의 목적 함수 값을 개선하기 위해 적어도 하나의 다른 목적 함수 값을 악화시키지 않고는 불가능한 실행 가능해를 말한다.

참고 문헌

• Ventzel, E. S. 운용 과학: 문제, 원리, 방법론. — 모스크바: Nauka, 1988.
• 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)

같이 보기

• 운용 과학
• 최적화
• 수학적 모델
• 목적 함수
• 제약 조건
• 실행 가능 영역
• 실행 가능해
• 기준
• 의사결정 이론
• 다기준 최적화
• 파레토 최적성
• 극값