해 공간과 기하학적 해석

해 공간의 정의

선형계획법에서 해 공간은 주어진 제약 조건을 만족하는 모든 가능한 해들의 집합을 의미한다. 수학적으로, 선형계획 문제는 다음과 같은 형태를 가진다.

$\text{maximize } \mathbf{c}^\top \mathbf{x}$

$\text{subject to } \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}$

여기서: - $\mathbf{c}$ 는 목적 함수의 계수 벡터, - $\mathbf{x}$ 는 결정 변수 벡터, - $\mathbf{A}$ 는 제약 조건 행렬, - $\mathbf{b}$ 는 제약 조건의 우변 벡터이다.

위 제약 조건을 만족하는 모든 $\mathbf{x}$ 의 집합이 바로 해 공간이다.

해 공간의 기하학적 의미

기하학적으로 해 공간은 n차원 공간에서 다면체(Polyhedron)로 표현된다. 각 제약 조건은 해 공간을 정의하는 경계를 형성하며, 이 경계는 평면, 직선, 또는 점으로 나타날 수 있다. 제약 조건들이 모두 성립하는 교집합이 해 공간을 구성하는 다면체가 된다.

이를 2차원 공간에서 예로 들면, 아래와 같은 두 가지 제약 조건이 있다고 가정하자:

$x_1 + x_2 \leq 4$

$x_1 \geq 0, \quad x_2 \geq 0$

이 제약 조건들은 $x_1$ - $x_2$ 평면에서 해 공간을 다음과 같이 형성한다:

graph TD A([0,0]) -- x1 axis --> B([4,0]) A -- x2 axis --> C([0,4]) B -- constraint --> D([4,0]) C -- constraint --> D([0,4])

극점(Vertex)과 기본 해(Basic Solution)

기하학적으로 해 공간의 경계에서 만나는 점들을 극점(Vertices)이라고 한다. 극점은 일반적으로 선형계획법에서 잠재적인 최적해로 간주된다. 이러한 극점은 주어진 제약 조건 하에서 가능한 기본 해(Basic Solution)를 나타내며, 극점에서의 목적 함수 값이 최적해가 될 가능성이 높다.

$\mathbf{A} \mathbf{x} = \mathbf{b}$ 형태의 등식 제약 조건을 포함하는 선형계획 문제에서, 기본 해는 $\mathbf{x}$ 의 성분 중 일부를 0으로 놓고, 남은 변수를 풀어서 구한다.

이때 기본 해는 다음과 같은 성질을 가진다: - 기본 해는 해 공간의 극점에 위치한다. - 최적해는 항상 극점 중 하나에서 발생한다.

해 공간의 차원과 경계

선형계획 문제에서 해 공간의 차원은 결정 변수의 수와 제약 조건의 수에 따라 결정된다. 예를 들어, 3차원 공간에서 2개의 제약 조건이 주어진다면, 해 공간은 평면으로 나타난다. 제약 조건이 증가할수록 해 공간은 더 복잡한 다면체 형태를 가지게 된다. 다만, 모든 제약 조건이 독립적이지 않다면 해 공간의 차원이 감소할 수 있다.

해 공간을 구성하는 경계들은 각각의 제약 조건이 성립하는 영역을 나타낸다. 예를 들어, $x_1 + x_2 = 4$ 라는 경계는 해 공간에서 하나의 직선으로 표현될 수 있다.

기저 해와 기저 변수

선형계획법에서 기저 해(Basic Solution)는 제약 조건을 만족하는 해 중에서 일부 변수를 0으로 두고, 나머지 변수를 풀어서 얻는 해를 의미한다. 이를 위해서 기본 해는 기저 변수(Basic Variables)와 비기저 변수(Non-Basic Variables)로 나누어진다. 기저 변수는 해가 0이 아닌 변수이고, 비기저 변수는 0인 변수이다.

기저 해를 구하는 일반적인 방법은 다음과 같다: 1. 비기저 변수의 값을 0으로 설정한다. 2. 남은 기저 변수를 사용하여 등식 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 를 풀어 기저 해를 구한다.

이때 기저 해가 실수 해를 가지면 유효한 기저 해가 되고, 음수 값이 포함되면 유효하지 않은 기저 해가 된다.

기저 해의 예시

단순한 예시로, 다음과 같은 두 개의 제약 조건이 주어진다고 가정하자:

$x_1 + 2x_2 = 6$

$3x_1 + x_2 = 9$

$x_1 \geq 0, \quad x_2 \geq 0$

비기저 변수 $x_2 = 0$ 으로 설정하면:

$x_1 = 6$

$3x_1 = 9 \quad \Rightarrow \quad x_1 = 3$

따라서 기저 해는 $(x_1, x_2) = (3, 0)$ 가 된다.

극점과 기저 해의 관계

기저 해는 기하학적으로 해 공간의 극점에 해당하며, 최적해는 항상 이 극점 중 하나에 위치한다. 이 관계를 더 명확히 하기 위해, 단체법(Simplex Method)는 해 공간의 극점들을 순차적으로 탐색하여 최적해를 찾는 과정으로 이해할 수 있다.

다면체의 기하학적 구조와 극점 탐색

다면체는 선형계획 문제의 제약 조건으로 인해 형성되는 해 공간으로, 그 꼭짓점이 기저 해에 해당한다. 각 기저 해는 다면체의 한 극점에 해당하며, 기저 변수의 값을 조정함으로써 다른 극점으로 이동할 수 있다. 이때, 극점에서의 목적 함수 값이 이전보다 크면 해당 해는 더 나은 해로 간주된다.

이 과정을 수학적으로 설명하면, $\mathbf{x}$ 의 값이 $\mathbf{A}\mathbf{x} \leq \mathbf{b}$ 를 만족하는 경우, 다음과 같은 형태로 나타난다:

$\mathbf{x}_{B} = \mathbf{A}_{B}^{-1}\mathbf{b}$

여기서: - $\mathbf{A}_{B}$ 는 기저 변수에 해당하는 제약 조건 행렬, - $\mathbf{x}_{B}$ 는 기저 변수 벡터이다.

이와 같이, 극점에 위치한 기저 해는 제약 조건을 만족하는 해들 중 하나이며, 이 기저 해를 이동하는 과정을 통해 최적해를 탐색하게 된다.

기하학적 해석의 시각적 표현

기하학적으로 해 공간은 n차원 공간에서 다면체로 표현되며, 각 제약 조건은 이 다면체의 경계를 형성한다. 간단한 2차원 선형계획 문제의 경우, 해 공간을 $x_1$ - $x_2$ 좌표 평면에서 시각적으로 표현할 수 있다.

예를 들어, 다음과 같은 제약 조건을 가진 문제를 생각해보자:

$x_1 + 2x_2 \leq 8$

$x_1 \geq 0, \quad x_2 \geq 0$

$x_1 + x_2 \leq 6$

이 제약 조건들은 $x_1$ - $x_2$ 평면에서 다각형 형태의 해 공간을 형성한다. 이러한 문제는 다음과 같이 시각화할 수 있다:

graph TD A([0,0]) -- Constraint 1 --> B([4,2]) B -- Constraint 2 --> C([0,6]) C -- Constraint 3 --> A([0,0])

이러한 시각적 표현을 통해 해 공간의 극점들을 명확히 볼 수 있으며, 각 극점은 기저 해에 해당한다.

극점의 탐색 방법

단체법(Simplex Method)에서, 최적해는 이 극점들 중 하나에서 결정되므로, 기저 해에서 출발하여 인접한 극점을 탐색하는 방법을 사용한다. 이 과정에서, 목적 함수의 값을 비교하여 더 나은 방향으로 이동한다.

극점 탐색 과정은 다음과 같이 정리할 수 있다: 1. 초기 기저 해에서 시작하여 해당 극점의 목적 함수 값을 계산한다. 2. 인접한 극점으로 이동하는 변수를 결정하고, 새로운 기저 해를 구한다. 3. 새로운 극점에서의 목적 함수 값이 이전보다 나아졌다면 해당 극점으로 이동한다. 4. 이 과정을 반복하여 최적해에 도달한다.

이때, 인접한 극점으로 이동하는 과정은 기저 변수와 비기저 변수를 교환하면서 이루어진다. 구체적으로, 교환 과정은 다음 수식을 통해 설명된다:

$\mathbf{x}_B = \mathbf{A}_B^{-1} \mathbf{b}$

여기서 $\mathbf{A}_B^{-1}$ 는 기저 행렬의 역행렬이며, 이 역행렬을 통해 새로운 기저 해를 구할 수 있다.

해 공간의 특징

해 공간의 기하학적 특징을 요약하면 다음과 같다: - 다면체(Polyhedron): 해 공간은 다차원의 다면체로 표현되며, 제약 조건이 해 공간의 경계를 형성한다. - 극점(Vertices): 해 공간의 경계에서 교차하는 점들로, 이들 점은 기저 해에 해당한다. - 인접 극점(Adjacent Vertices): 기저 해에서 한 개의 비기저 변수를 기저 변수로 교환할 때 도달할 수 있는 극점이다. - 기저 해(Basic Solution): 제약 조건을 만족하는 해 중에서 기저 변수로 이루어진 해로, 다면체의 극점에 위치한다.

기하학적으로 해석된 선형계획법에서, 극점과 해 공간의 경계는 최적해를 찾는 중요한 요소로 작용한다. 특히, 극점에서의 목적 함수 값이 최적해를 제공할 가능성이 높기 때문에, 단체법은 이를 활용하여 최적화를 수행한다.