표준형 선형계획 문제

표준형 선형계획 문제는 선형계획법에서 가장 일반적으로 다루는 형태의 문제로, 다음과 같은 수학적 정의로 표현된다. 이는 목적 함수를 최소화하거나 최대화하는 동시에 일련의 선형 제약 조건을 만족시키는 문제이다.

1. 목적 함수

목표는 목적 함수를 최적화(최대화 또는 최소화)하는 것이다. 일반적으로 목적 함수는 아래와 같이 주어진다:

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

또는

$\text{minimize} \quad \mathbf{c}^\top \mathbf{x}$

여기서: - $\mathbf{c} \in \mathbb{R}^n$ 는 목적 함수의 계수 벡터. - $\mathbf{x} \in \mathbb{R}^n$ 는 결정 변수 벡터이다.

2. 제약 조건

선형 제약 조건은 다음과 같이 표현된다:

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

여기서: - $\mathbf{A} \in \mathbb{R}^{m \times n}$ 는 계수 행렬. - $\mathbf{x} \in \mathbb{R}^n$ 는 결정 변수 벡터. - $\mathbf{b} \in \mathbb{R}^m$ 는 제약 조건의 상수 벡터이다.

3. 비부정성 제약 조건

또한, 결정 변수는 비부정성(non-negativity) 제약 조건을 만족해야 한다:

$\mathbf{x} \geq 0$

이러한 비부정성 제약 조건은 표준형 문제의 필수적인 요소로, 모든 결정 변수는 0 이상이어야 한다.

4. 표준형 문제의 전체 수식

표준형 선형계획 문제는 목적 함수와 제약 조건을 모두 포함한 형태로 다음과 같이 표현된다:

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

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

혹은 동일한 문제를 최소화 형태로 표현하면:

$\text{minimize} \quad \mathbf{c}^\top \mathbf{x}$

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

5. 표준형 문제의 구성 요소

목적 함수: 결정 변수 $\mathbf{x}$ 에 대한 선형 결합으로 이루어져 있으며, 주어진 계수 $\mathbf{c}$ 에 따라 $\mathbf{x}$ 의 값을 최대화하거나 최소화하려고 한다.
제약 조건: 제약 조건은 선형 부등식으로 구성되며, 계수 행렬 $\mathbf{A}$ 와 상수 벡터 $\mathbf{b}$ 가 주어진다. 이 제약 조건에 따라 $\mathbf{x}$ 의 값이 제한된다.
비부정성 제약: 모든 결정 변수 $\mathbf{x}$ 는 음수가 될 수 없으며, 0 이상의 값을 가져야 한다.

6. 변형을 통한 표준형 변환

실제 문제는 표준형 형태로 바로 주어지지 않을 수 있다. 하지만 일반적으로는 문제를 표준형으로 변환하여 해결하는 것이 편리한다. 이를 위해, 몇 가지 변형을 적용할 수 있다.

등식 제약 조건을 부등식으로 변환:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

이런 형태의 등식 제약 조건은 표준형에 맞춰 부등식으로 바꿀 수 있다. 등식 제약 조건은 두 개의 부등식으로 나눌 수 있다:

$\mathbf{A} \mathbf{x} \leq \mathbf{b} \quad \text{and} \quad \mathbf{A} \mathbf{x} \geq \mathbf{b}$

혹은 추가적인 방법으로 슬랙 변수를 도입하여 변형할 수 있다.

최소화 문제를 최대화 문제로 변환: 최소화 문제를 최대화 문제로 바꾸려면, 목적 함수의 부호를 바꿔준다. 예를 들어,

$\text{minimize} \quad \mathbf{c}^\top \mathbf{x}$

를

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

로 변환한다.

7. 슬랙 변수 (Slack Variables)

불등식 제약 조건을 등식 제약 조건으로 변환할 때 슬랙 변수를 도입할 수 있다. 예를 들어, 다음과 같은 부등식 제약 조건:

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

을 등식으로 변환하기 위해, 슬랙 변수 $\mathbf{s} \in \mathbb{R}^m$ 를 도입하여 다음과 같이 표현할 수 있다:

$\mathbf{A} \mathbf{x} + \mathbf{s} = \mathbf{b}$

여기서 $\mathbf{s} \geq 0$ 는 부등식에서의 '남은 차이'를 나타내는 슬랙 변수이다. 슬랙 변수를 도입함으로써 부등식 제약 조건을 등식 제약 조건으로 바꿀 수 있다.

이 변형을 적용한 후, 표준형 선형계획 문제는 다음과 같은 형태를 갖는다:

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

$\text{subject \ to} \quad \mathbf{A} \mathbf{x} + \mathbf{s} = \mathbf{b}, \quad \mathbf{x} \geq 0, \quad \mathbf{s} \geq 0$

8. 표준형 문제의 기하학적 해석

선형계획법에서 표준형 문제를 기하학적으로 해석하면, 가능한 해집합(feasible region)은 제약 조건을 만족하는 모든 $\mathbf{x}$ 의 집합으로 정의된다. 이 해집합은 다면체(polytopes)로 표현되며, 목적 함수는 이 다면체 위에서 최적 해를 찾게 된다.

선형계획법에서는 일반적으로 해집합의 꼭짓점에서 최적 해가 존재하며, 단체법(SIMPLEX Method)을 이용해 이를 찾는 과정이 진행된다.

이를 이해하기 위해 다면체의 예를 들면, 2차원에서의 경우 $\mathbf{x}$ 는 평면 상의 점으로, 해집합은 다각형이 된다. 이 다각형의 꼭짓점에서 최적 해가 구해지는 방식이다. 아래는 이를 시각화한 간단한 예이다:

graph LR; A((A)) --> B((B)); B --> C((C)); C --> D((D)); D --> A; A --> C; B --> D;

9. 최적 해의 존재 조건

표준형 선형계획 문제에서 최적 해가 존재하려면 다음 조건을 만족해야 한다:

가능한 해집합이 비어 있지 않음: 제약 조건을 만족하는 해가 하나 이상 존재해야 한다.
목적 함수가 유한: 목적 함수가 발산하지 않고 유한한 값에서 최적 해를 갖는다.

만약 해집합이 비어 있거나, 목적 함수가 무한으로 발산하는 경우(예: 제약 조건 없이 값이 계속 커지거나 작아지는 경우), 최적 해는 존재하지 않는다.

10. 선형계획 문제의 기본 성질

선형계획 문제의 기본적인 성질 중 하나는 해집합이 볼록(convex)하다는 것이다. 이 말은 해집합 내에서 두 점을 잇는 선분이 해집합 내에 그대로 포함된다는 의미이다. 이를 통해 최적 해는 해집합의 꼭짓점에서 발생한다는 중요한 특성이 도출된다.

1. 볼록성

선형계획 문제에서 제약 조건은 선형 부등식으로 주어지므로, 이 제약 조건들에 의해 정의된 해집합은 다면체(Polytope)이다. 이러한 다면체는 항상 볼록한다.

즉, 해집합 $\mathcal{F}$ 가 다음과 같은 성질을 만족한다면 볼록이라고 할 수 있다: - 임의의 $\mathbf{x}_1, \mathbf{x}_2 \in \mathcal{F}$ 에 대해, $\lambda \in [0,1]$ 에 대해 $\lambda \mathbf{x}_1 + (1 - \lambda) \mathbf{x}_2 \in \mathcal{F}$ .

이는 $\mathcal{F}$ 내에 있는 두 점을 잇는 선분도 $\mathcal{F}$ 내에 존재한다는 것을 의미한다.

2. 꼭짓점 해

볼록성에 의해, 최적 해는 항상 해집합의 경계에서 발생한다. 특히, 선형계획 문제의 경우에는 꼭짓점에서 최적 해가 발생하는 것이 일반적이다. 이 특성을 이용해, 단체법(SIMPLEX Method)과 같은 알고리즘은 해집합의 꼭짓점을 탐색하는 방식으로 최적 해를 찾는다.

11. 표준형 문제의 해집합

표준형 선형계획 문제의 해집합은 다음과 같은 선형 부등식으로 정의된 다면체이다:

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

이 다면체는 결정 변수 $\mathbf{x}$ 가 차지할 수 있는 모든 가능한 값을 포함하며, 그 경계는 제약 조건 $\mathbf{A} \mathbf{x} \leq \mathbf{b}$ 와 비부정성 조건 $\mathbf{x} \geq 0$ 에 의해 정의된다.

해집합의 기하학적 표현

아래는 2차원 해집합의 예이다. 각 제약 조건은 선형 부등식으로 표현되며, 그 교차점이 가능한 해집합을 나타낸다.

graph TD; A((가능한 해집합)); A --- B[제약 조건 1]; A --- C[제약 조건 2]; A --- D[제약 조건 3]; B --> E[경계선]; C --> E; D --> E;

각 제약 조건에 의해 정의된 영역이 교차하는 부분이 해집합으로 나타나며, 이 교차점(꼭짓점)에서 최적 해가 발생한다.

12. 기본 해(Basic Solution)와 기본 가능 해(Basic Feasible Solution)

선형계획 문제의 해를 구할 때, 기본 해(Basic Solution)와 기본 가능 해(Basic Feasible Solution, BFS)가 중요한 역할을 한다.

기본 해: 변수의 개수가 $n$ , 제약 조건의 개수가 $m$ 일 때, 해집합 내에서 $n - m$ 개의 변수에 대해 $0$ 을 부여하여 나머지 $m$ 개의 변수를 결정하는 방식이다.
기본 가능 해: 기본 해 중에서 모든 변수가 비부정성 제약 조건을 만족하는 해를 기본 가능 해라고 한다.

기본 가능 해는 선형계획 문제에서 최적 해가 될 수 있는 후보들 중 하나이다.

13. 기본 해(Basic Solution) 구하기

기본 해를 구하는 방법은 다음과 같다. 주어진 제약 조건 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 에서, $n - m$ 개의 변수를 0으로 두고, 나머지 $m$ 개의 변수를 구하는 방식이다. 이를 통해 해집합에서 가능한 꼭짓점 해를 얻을 수 있다.

단계별 과정

기본 변수와 비기본 변수의 설정:
$\mathbf{x}$ 벡터에서 일부 변수를 기본 변수(basic variables)로 선택하고, 나머지 변수를 비기본 변수(non-basic variables)로 설정한다.
$n - m$ 개의 비기본 변수를 $0$ 으로 설정한다.
기본 변수 값 계산:
$\mathbf{A} \mathbf{x} = \mathbf{b}$ 식을 이용해 남은 $m$ 개의 기본 변수 값을 계산한다.

이 과정을 통해 얻은 해는 기본 해가 되며, 모든 기본 해가 기본 가능 해(BFS)가 되는 것은 아니다. 기본 가능 해는 반드시 $\mathbf{x} \geq 0$ 조건을 만족해야 한다.

14. 기본 가능 해(Basic Feasible Solution, BFS)

기본 해 중에서 비부정성 제약 조건을 만족하는 해를 기본 가능 해(BFS)라고 한다. 즉, 기본 변수들이 모두 0 이상일 때 해당 해는 BFS가 된다.

예시

다음은 기본 가능 해를 구하는 간단한 예이다.

제약 조건이 다음과 같이 주어진다고 가정한다:

$\mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서 $\mathbf{A}$ 는 $3 \times 5$ 행렬이고, $\mathbf{x}$ 는 5차원의 벡터이다. 이 경우, $2$ 개의 비기본 변수를 $0$ 으로 설정하고, 나머지 $3$ 개의 기본 변수 값을 계산한다. 이 계산을 통해 얻은 해가 비부정성 조건을 만족한다면, 이 해는 BFS가 된다.

15. 표준형 선형계획 문제에서 BFS의 중요성

표준형 선형계획 문제에서 BFS는 최적 해를 찾는 과정에서 매우 중요한 역할을 한다. 선형계획 문제는 다면체의 꼭짓점에서 최적 해가 발생하므로, BFS는 이러한 꼭짓점을 표현하는 방법 중 하나이다.

단체법(SIMPLEX Method)과 같은 알고리즘은 BFS를 바탕으로 다면체의 꼭짓점을 탐색하며, 최적 해를 찾는다. 이를 통해, BFS는 선형계획 문제의 해를 구하는 출발점으로 사용될 수 있다.

16. BFS와 최적 해

최적 해는 반드시 BFS 중 하나일 필요는 없지만, BFS는 최적 해가 될 수 있는 유력한 후보들이다. 이는 다면체의 꼭짓점에서 최적 해가 발생하는 성질을 바탕으로 한 것이며, BFS는 그러한 꼭짓점에서 해를 제공하는 역할을 한다.

17. 예제: 표준형 문제의 기본 해 구하기

다음은 간단한 표준형 선형계획 문제의 예이다.

$\text{maximize} \quad 3x_1 + 2x_2$

$\text{subject to} \quad \begin{aligned} x_1 + x_2 &\leq 4 \\ 2x_1 + x_2 &\leq 6 \\ x_1, x_2 &\geq 0 \end{aligned}$

이 문제를 풀기 위해 먼저 기본 해를 구해야 한다. 제약 조건을 등식으로 만들고, 슬랙 변수를 도입한다:

$\begin{aligned} x_1 + x_2 + s_1 &= 4 \\ 2x_1 + x_2 + s_2 &= 6 \\ x_1, x_2, s_1, s_2 &\geq 0 \end{aligned}$

여기서 $s_1, s_2$ 는 슬랙 변수이다. 이제 $x_1, x_2, s_1, s_2$ 중 두 변수를 기본 변수로 설정하고, 나머지 변수를 비기본 변수로 설정하여 해를 구할 수 있다.

18. 표준형 문제의 예제 풀이

위의 표준형 문제에 대해 기본 해를 구하는 과정을 계속해 보자.

1. 초기 기본 변수 설정

우리는 $x_1$ 과 $x_2$ 를 비기본 변수로 설정하고, $s_1$ 과 $s_2$ 를 기본 변수로 선택할 수 있다. 따라서 $x_1 = 0$ , $x_2 = 0$ 로 설정한 후, 나머지 기본 변수 $s_1$ 과 $s_2$ 를 계산한다:

$s_1 = 4 - (x_1 + x_2) = 4 - (0 + 0) = 4$

$s_2 = 6 - (2x_1 + x_2) = 6 - (2 \cdot 0 + 0) = 6$

따라서 첫 번째 기본 해는 다음과 같다:

$(x_1, x_2, s_1, s_2) = (0, 0, 4, 6)$

이 해는 비부정성 조건을 만족하므로, 기본 가능 해(BFS)이다.

2. 다른 기본 변수 설정

다음으로, $x_1$ 을 기본 변수로 선택하고, $s_1$ 을 비기본 변수로 설정할 수 있다. 이 경우 $s_1 = 0$ 으로 설정하고, $x_2$ 와 $s_2$ 를 계산한다.

먼저 $s_1 = 0$ 을 제약 조건에 대입하여 계산하면:

$x_1 + x_2 + s_1 = 4 \quad \Rightarrow \quad x_1 + x_2 = 4$

$2x_1 + x_2 + s_2 = 6 \quad \Rightarrow \quad 2x_1 + x_2 + s_2 = 6$

이 식들을 풀면, $x_2$ 와 $s_2$ 의 값을 구할 수 있다. $x_2$ 를 제거하기 위해 두 번째 식에서 첫 번째 식을 빼면:

$(2x_1 + x_2) - (x_1 + x_2) = 6 - 4$

$x_1 = 2$

이제 $x_1 = 2$ 를 첫 번째 제약 조건에 대입하면:

$2 + x_2 = 4 \quad \Rightarrow \quad x_2 = 2$

마지막으로 $s_2$ 는:

$2x_1 + x_2 + s_2 = 6 \quad \Rightarrow \quad 2(2) + 2 + s_2 = 6 \quad \Rightarrow \quad s_2 = 0$

따라서 두 번째 기본 해는:

$(x_1, x_2, s_1, s_2) = (2, 2, 0, 0)$

이 해 역시 비부정성 조건을 만족하므로 BFS이다.

3. 또 다른 기본 변수 설정

이번에는 $x_2$ 를 기본 변수로 선택하고, $s_2$ 를 비기본 변수로 설정한다. $s_2 = 0$ 을 설정하고, 나머지 변수를 계산한다.

첫 번째 제약 조건에서:

$x_1 + x_2 + s_1 = 4 \quad \Rightarrow \quad x_1 + x_2 = 4$

두 번째 제약 조건에서:

$2x_1 + x_2 + s_2 = 6 \quad \Rightarrow \quad 2x_1 + x_2 = 6$

이 식들을 풀면: 첫 번째 식에서 $x_2 = 4 - x_1$ 이고, 이를 두 번째 식에 대입하면:

$2x_1 + (4 - x_1) = 6 \quad \Rightarrow \quad 2x_1 + 4 - x_1 = 6 \quad \Rightarrow \quad x_1 = 2$

따라서 $x_2 = 2$ 가 된다.

이때, $s_1 = 0$ , $s_2 = 0$ 이며, $x_1 = 2$ , $x_2 = 2$ 가 되므로, 세 번째 기본 해는:

$(x_1, x_2, s_1, s_2) = (2, 2, 0, 0)$

이 역시 BFS이다.