빅 M 방법 - 실험 도서관

빅 M 방법의 개요

빅 M 방법은 선형계획법에서 2단계 단체법의 대안으로 자주 사용되는 기법이다. 이 방법은 인공 변수(Artificial Variable)를 추가하여 초기 해를 찾는 데 도움을 준다. 일반적으로 선형계획 문제에서 허용 가능한 기본해를 찾기 어려운 경우 빅 M 방법을 사용한다. 이 방법에서는 매우 큰 값을 의미하는 M을 도입하여 인공 변수들을 제약식에 추가하고, 이를 최대한 빨리 제거하는 방식으로 문제를 해결한다.

인공 변수와 목적 함수의 수정

먼저, 허용 가능한 기본 해를 찾기 위해 인공 변수를 도입한다. 이러한 인공 변수는 문제의 제약식이 항상 성립하도록 보장한다. 즉, 제약식이 등식 형태로 변환될 때, 잉여 변수(surplus variable)만으로는 허용 가능한 해를 찾을 수 없는 경우에 인공 변수를 추가한다.

이때 수정된 목적 함수는 다음과 같은 형태를 갖는다:

$\text{최대화} \quad z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n - M(A_1 + A_2 + \cdots + A_m)$

여기서: - $c_1, c_2, \dots, c_n$ : 원래 목적 함수의 계수들 - $A_1, A_2, \dots, A_m$ : 인공 변수들 - $M$ : 매우 큰 값

단체표(Simplex Tableau) 구성

빅 M 방법을 사용하면 단체법에서 사용하는 표를 구성할 수 있다. 이때 인공 변수는 매우 큰 계수로 가중치를 부여받아 목적 함수에서 제거된다. 단체법 표는 다음과 같은 형태로 구성된다.

기본 변수	$x_1$	$x_2$	$\cdots$	$x_n$	$A_1$	$A_2$	$\cdots$	$A_m$	우변
$x_1$	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$	0	0	$\cdots$	0	$b_1$
$x_2$	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$	0	0	$\cdots$	0	$b_2$
$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$	$\vdots$
$A_1$	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$	1	0	$\cdots$	0	$b_m$

여기서: - $x_1, x_2, \dots, x_n$ : 결정 변수들 - $A_1, A_2, \dots, A_m$ : 인공 변수들 - $b_1, b_2, \dots, b_m$ : 우변 상수들

목적 함수의 초기 형태

인공 변수를 포함한 문제에서 초기 목적 함수는 다음과 같이 수정된다:

$\mathbf{z} = \mathbf{c}^{T} \mathbf{x} - M (\mathbf{A}^{T} \mathbf{a})$

여기서: - $\mathbf{c}$ : 원래 목적 함수의 계수 벡터 - $\mathbf{x}$ : 결정 변수 벡터 - $M$ : 매우 큰 값 - $\mathbf{A}$ : 인공 변수 벡터 - $\mathbf{a}$ : 인공 변수들의 계수 행렬

이 식은 인공 변수를 최대한 빠르게 제거하기 위해 설계되었다. 목적 함수에 큰 값을 부여하여 인공 변수를 가능하면 0으로 만들어야 한다.

빅 M 방법의 초기 단체법 표 구성

초기 단체법 표는 다음과 같이 구성된다. 인공 변수가 추가된 후에는 단체법의 기본적인 단계와 동일한 방식으로 진행된다. 그러나, 빅 M 방법에서는 인공 변수가 포함된 제약식을 처리해야 하므로, 목적 함수의 초기 형태에 큰 M이 포함되어 있다. 이때의 단체법 표는 아래와 같다.

기본 변수	$x_1$	$x_2$	$\cdots$	$x_n$	$A_1$	$A_2$	$\cdots$	$A_m$	우변
$A_1$	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$	$1$	$0$	$\cdots$	$0$	$b_1$
$A_2$	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$	$0$	$1$	$\cdots$	$0$	$b_2$
$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$	$\vdots$
$A_m$	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$	$0$	$0$	$\cdots$	$1$	$b_m$
$z$	$-c_1 + M a_{11}$	$-c_2 + M a_{12}$	$\cdots$	$-c_n + M a_{1n}$	$-M$	$-M$	$\cdots$	$-M$	$0$

여기서 중요한 점은 목적 함수에 포함된 인공 변수의 영향이다. 빅 M 방법에서는 인공 변수의 계수들이 $-M$ 으로 추가되어 있기 때문에, 이를 빠르게 제거하는 것이 단체법의 첫 번째 목표이다. 첫 번째 단계에서는 가능한 한 인공 변수의 값을 0으로 만들어야 한다.

피봇 선택

단체법에서처럼 빅 M 방법에서도 피봇을 선택하여 해를 반복적으로 개선한다. 피봇 선택 과정은 단체법에서 사용하는 기준과 동일하지만, 빅 M 방법에서는 인공 변수가 포함되어 있으므로 이에 따른 추가적인 고려가 필요하다. 피봇을 선택할 때는 두 가지 사항을 고려한다.

목적 함수 계수 중 가장 큰 양수 항목 선택: 이는 최적화 문제에서 비용을 최소화하거나 최대화하는 데 도움을 준다.
가장 작은 양수 비율 선택: 피봇 열에서 우변 값과 해당 열의 양의 계수 간의 비율을 계산하여 가장 작은 값을 선택한다.

이 과정을 거치면서 인공 변수를 제거하고, 나머지 결정 변수들에 대해 최적해를 구할 수 있게 된다.

단체법 표의 반복

각 반복 단계에서, 단체법 표를 수정하고 새로운 피봇을 선택한다. 각 단계는 다음과 같은 과정을 따른다:

피봇을 선택하여 새로운 기본 변수로 전환한다.
단체법 표를 수정한다.
목적 함수와 제약식에서 인공 변수의 영향을 제거한다.

매 반복마다 새로운 단체법 표를 작성하며, 최종적으로 인공 변수가 모두 제거되고, 원래의 선형계획 문제에 대한 최적해를 얻게 된다.

다음은 단체법 표의 반복을 나타내는 Mermaid 흐름도이다.

graph TD A[초기 단체법 표] --> B{피봇 선택} B --> C[단체법 표 수정] C --> D{인공 변수 제거?} D -- 예 --> E[최적해 도출] D -- 아니오 --> B

이 과정을 통해 최적해에 도달할 때까지 반복한다.

인공 변수 제거와 최적화 과정

빅 M 방법에서 가장 중요한 목표는 인공 변수를 빠르게 제거하여 원래의 결정 변수만 남기고 최적화를 진행하는 것이다. 인공 변수는 실제 문제의 해에 포함되지 않으며, 인공 변수가 0이 되는 순간부터 원래 선형 계획 문제의 해로 이어질 수 있다.

따라서 각 반복 단계에서 인공 변수의 값을 가능한 한 빨리 0으로 만들기 위해 피봇을 선택하고 단체법 표를 수정한다. 피봇 선택 시, 인공 변수의 열에서 가능한 피봇 요소를 선택하여 해당 행의 기본 변수를 인공 변수 대신 결정 변수로 바꾸게 된다.

목적 함수의 갱신

각 단계에서 목적 함수는 피봇 선택에 따라 계속 갱신된다. 갱신된 목적 함수는 다음과 같이 표현된다:

$\mathbf{z} = \mathbf{c}^{T} \mathbf{x} - M (\mathbf{A}^{T} \mathbf{a})$

여기서: - $\mathbf{c}^{T} \mathbf{x}$ : 원래 결정 변수들로 이루어진 부분 - $M (\mathbf{A}^{T} \mathbf{a})$ : 인공 변수들을 포함하는 항목으로, 이 부분을 0으로 만드는 것이 목표이다.

단체법의 기본 과정과 동일하게, 목적 함수가 최대화 혹은 최소화되는 방향으로 계속 갱신되며, 인공 변수의 계수가 모두 0이 되는 시점에서 인공 변수가 완전히 제거된다.

종료 조건

빅 M 방법의 종료 조건은 단체법의 종료 조건과 유사한다. 목적 함수에 포함된 모든 계수가 음수일 경우, 더 이상 개선할 수 없는 최적 상태에 도달했다고 판단하고 알고리즘을 종료한다. 인공 변수의 계수가 모두 0이 되었을 때 원래의 선형계획 문제로 전환하여 최종 최적해를 구할 수 있다.

종료 조건의 요약:

목적 함수의 모든 계수가 음수(최대화 문제의 경우) 또는 양수(최소화 문제의 경우)일 때 알고리즘 종료
인공 변수들이 모두 제거되고, 원래의 결정 변수들로만 이루어진 해를 얻을 수 있는 상태가 되었을 때 최적해 도출

빅 M 방법의 한계

빅 M 방법은 인공 변수와 매우 큰 상수 $M$ 을 도입하여 문제를 해결하는 방식이다. 그러나 이 방법은 몇 가지 한계를 가질 수 있다: - 매우 큰 상수 $M$ 의 선택이 문제에 영향을 미칠 수 있으며, 실제로 너무 큰 값을 사용하면 수치적 불안정성을 초래할 수 있다. - 인공 변수를 도입하면서 추가적인 계산이 필요하므로, 문제의 크기나 복잡도에 따라 계산 효율이 떨어질 수 있다.

이러한 한계점에도 불구하고 빅 M 방법은 초기 해를 찾기 어려운 선형 계획 문제에서 유용한 해결 방법으로 널리 사용된다.