다면체의 정의

다면체(Polyhedron)는 선형 계획법에서 매우 중요한 개념으로, 여러 개의 선형 부등식으로 정의된 다차원 공간의 부분 집합을 의미한다. 즉, 주어진 선형 제약 조건에 의해 정의되는 영역이 다면체로 나타난다. 다면체는 기본적으로 유한한 개수의 평면에 의해 경계가 형성되며, 선형 계획 문제의 해를 찾는 데 중요한 역할을 한다.

다음과 같은 선형 부등식들의 집합이 있다고 가정해 보자:

\mathbf{A} \mathbf{x} \leq \mathbf{b}

여기서, - \mathbf{A}는 m \times n 크기의 계수 행렬, - \mathbf{x}는 n-차원 벡터 (변수), - \mathbf{b}는 m-차원 벡터 (상수)이다.

이때, 위의 선형 부등식들은 n-차원 공간에서 다면체의 경계를 형성하게 된다. 각 부등식은 n-차원 공간에서 하나의 초평면(Hyperplane)을 정의하며, 다면체는 이 초평면들에 의해 둘러싸인 공간이다.

가능 영역

가능 영역(Feasible Region)은 주어진 선형 제약 조건을 만족하는 모든 해들의 집합이다. 선형 계획 문제에서는 이러한 가능 영역 내에서 목적 함수(Objective Function)를 최적화하는 해를 찾게 된다. 가능 영역은 다면체와 동일한 개념으로 이해할 수 있으며, 주어진 제약 조건들이 교차하는 부분이 된다.

가능 영역은 다음과 같은 조건을 만족하는 해 \mathbf{x}들의 집합으로 정의된다:

\mathbf{x} \in \mathbb{R}^n \quad \text{such that} \quad \mathbf{A} \mathbf{x} \leq \mathbf{b}

이때, \mathbf{x}는 가능한 모든 해를 나타내며, 이 해가 가능 영역 내에 속하려면 모든 제약 조건을 만족해야 한다.

예시

2차원 공간에서 두 개의 제약 조건이 주어졌을 때, 이 조건들이 가능 영역을 어떻게 정의하는지 시각적으로 설명할 수 있다. 두 제약 조건이 다음과 같다고 가정해 봅시다:

\begin{aligned} x_1 + x_2 &\leq 4 \\ x_1 - x_2 &\leq 1 \end{aligned}

이 경우, 각각의 부등식은 2차원 평면에서 직선으로 표현되며, 두 직선의 교차점에 의해 경계가 정의된다.

graph TD; A1(x_1 + x_2 = 4); A2(x_1 - x_2 = 1); A1 --> FeasibleRegion; A2 --> FeasibleRegion; FeasibleRegion(가능 영역)

가능 영역의 특성

선형 계획 문제에서 가능 영역은 항상 볼록(Convex)한다. 즉, 두 임의의 점 \mathbf{x}_1, \mathbf{x}_2가 가능 영역에 속할 때, 이 두 점을 연결하는 선분 상의 모든 점 역시 가능 영역에 속하게 된다. 이 성질은 선형 계획 문제의 중요한 특성 중 하나로, 문제의 해를 찾는 데 있어서 단체법(Simplex Method)과 같은 알고리즘의 기초가 된다.

볼록성을 수식으로 표현하면 다음과 같다:

\mathbf{x}_1, \mathbf{x}_2 \in \text{가능 영역} \Rightarrow \forall \lambda \in [0,1], \lambda \mathbf{x}_1 + (1 - \lambda) \mathbf{x}_2 \in \text{가능 영역}

이 식은 \mathbf{x}_1과 \mathbf{x}_2 사이의 모든 점이 가능 영역 내에 있음을 의미한다.

극점과 기본 해

가능 영역의 중요한 성질 중 하나는 그 경계에 위치한 점들이 선형 계획 문제의 최적 해가 될 가능성이 높다는 점이다. 가능 영역의 경계에 위치한 점들을 극점(Extreme Point)이라고 한다. 선형 계획 문제의 해는 종종 이러한 극점에서 나타나게 된다.

극점은 다음과 같이 정의된다:

\mathbf{x} \text{가 극점이라면, } \mathbf{x} = \lambda \mathbf{x}_1 + (1 - \lambda) \mathbf{x}_2 \text{일 때, } \lambda = 0 \text{ 또는 } \lambda = 1

즉, 극점은 가능 영역 내에서 두 다른 점들의 선형 결합으로 나타날 수 없는 점이다.

기본 해(Basic Solution)는 선형 제약 조건을 만족하는 해 중에서, n개의 제약 조건이 성립하는 점이다. 이러한 기본 해는 보통 가능 영역의 극점과 일치하며, 단체법과 같은 알고리즘에서 해를 찾는 데 중요한 역할을 한다.

가능 영역의 차원

가능 영역의 차원(Dimension)은 선형 제약 조건에 의해 결정되며, 제약 조건이 많을수록 가능 영역의 차원은 줄어든다. 예를 들어, n-차원 공간에서 m개의 선형 제약 조건이 주어진다면, 이 제약 조건들 중에서 서로 독립적인 조건의 개수에 따라 가능 영역의 차원이 결정된다.

이와 같은 차원의 감소는 제약 조건들이 추가될 때 각 초평면이 전체 공간에서 부분 공간을 분할하기 때문에 발생한다.

선형 계획 문제에서의 가능 영역

선형 계획 문제에서 목적 함수는 일반적으로 다음과 같이 정의된다:

\text{maximize (or minimize) } z = \mathbf{c}^\top \mathbf{x}

여기서, - \mathbf{c}는 목적 함수의 계수 벡터, - \mathbf{x}는 결정 변수 벡터, - z는 목적 함수 값이다.

가능 영역 내에서 목적 함수 z를 최적화하는 해는 보통 가능 영역의 경계, 특히 극점에서 발생하게 된다. 이는 선형 계획법에서 목적 함수가 볼록 다면체의 경계에서 최적화된다는 점과 관련이 있다.

가능 영역의 시각화

가능 영역을 시각적으로 나타내는 것이 도움이 될 때가 많다. 2차원 또는 3차원 문제에서 가능 영역을 시각화하면 각 제약 조건이 형성하는 초평면(또는 평면)과 그 교차로 이루어진 다면체를 명확하게 볼 수 있다.

예를 들어, 다음과 같은 선형 제약 조건을 가진 2차원 선형 계획 문제를 생각해봅시다:

\begin{aligned} x_1 + x_2 &\leq 4 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}

이 경우, 가능 영역은 다음과 같이 표현된다:

graph TD; A1(x_1 + x_2 = 4); A2(x_1 = 0); A3(x_2 = 0); A1 --> FeasibleRegion; A2 --> FeasibleRegion; A3 --> FeasibleRegion; FeasibleRegion(가능 영역)

이 예시에서 가능 영역은 x_1-축, x_2-축, 그리고 직선 x_1 + x_2 = 4에 의해 정의된 삼각형 모양의 영역이다. 이 가능 영역 내에서 목적 함수를 최적화하는 해는 보통 이 삼각형의 꼭짓점, 즉 극점에서 발생한다.

가능 영역의 경계

가능 영역의 경계(Boundary)는 가능 영역을 정의하는 선형 제약 조건들로부터 형성된다. 경계는 가능한 해들의 상한 또는 하한을 나타내며, 선형 계획 문제에서 경계에 있는 점이 최적 해가 될 가능성이 매우 크다.

일반적으로, 가능 영역의 경계는 초평면들의 교차점으로 구성되며, 각 초평면은 한 개의 선형 부등식에 해당한다. 즉, 가능 영역은 여러 선형 제약 조건에 의해 형성된 다면체이며, 이 다면체의 경계에서 해가 구해진다.