심플렉스 메소드의 브랜드 룰
정리
딕셔너리: $i = 1 , \cdots , m$ 에 대해서 다음과 같은 꼴의 연립방정식을 딕셔너리dictionary라 한다. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$ $\zeta$ 를 제외한 좌변의 변수들을 기저변수basic variable, 우변의 변수들을 비기저변수nonbasic variable라 한다. 이들의 인덱스를 다음과 같이 나타낸다. $$ \begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*} $$
선형계획법의 심플렉스 메소드에서 진입 변수entering variable의 인덱스를 $\mathcal{N}$ 에서 가장 작은 것으로 선택하고, 이탈 변수leaving variable의 인덱스를 $\mathcal{B}$ 에서 가장 작은 것으로 선택하는 것을 브랜드 룰Brand’s rule이라 한다. 브랜드 룰에 따르면 심플렉스 메소드는 사이클에 빠지지 않는다.
설명
선형계획문제를 푸는 방법도 심플렉스 메소드 단 하나가 아니고, 심플렉스 메소드에서 딕셔너리를 업데이트하는 피벗 룰pivot rule 역시 단 하나가 아니지만 브랜드 룰이 있음으로써 심플렉스 메소드는 반드시 선형계획문제를 풀 수 있음이 보장된다는 점이 중요하다. 이 정리를 이해하게 되면 사실 선형계획법에서 가장 중요한 두가지 컨셉, 그 중에서 심플렉스 메소드는 마스터 했다고 보아도 무방하다.
증명 1
전략: 쉽지 않다. 브랜드 룰로 피벗을 하는데 사이클에 빠지는 것이 모순임을 보일 것이다.
Part 1. $\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$
일반성을 잃지 않고, 사이클링이 일어난 시점부터 증명을 시작하자. 이는 어떤 $k \in \mathbb{N}$ 에 대해 딕셔너리가 다음과 같이 순환하는 것이다. $$ D_{0} , D_{1} , \cdots, D_{k-1} , D_{0} , D_{1} , \cdots $$ 이 딕셔너리 중 어떤 것에서는 기저고 어떤 것에서는 기저가 아닌 변수를 피클fickle이라 부르겠다. 이들 중 $x_{t}$ 가 가장 큰 인덱스를 가진 피클이라 하고, $x_{t}$ 를 이탈 변수로 가지는 딕셔너리를 $D$ 라 할 때, 일반성을 잃지 않고 $D = D_{0}$ 라 뒀을 때 $D$ 는 $\forall i \in \mathcal{B}$ 에 대해 다음과 같이 적을 수 있다. $$ \begin{align*} \zeta &=& v &+& \sum_{j \in \mathcal{N}} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j \in \mathcal{N}} a_{ij} x_{j} \end{align*} $$ 여기서 $x_{s}$ 가 진입 변수라 하면 $x_{t}$ 가 이탈 변수고 아직은 $t \in \mathcal{B}$ 고 $s \in \mathcal{N}$ 이다. 이제 $D^{\ast}$ 를 $D_{1} , \cdots, D_{k-1}$ 중에서 $x_{t}$ 가 기저에 진입한 딕셔너리라 두고, $\forall i \in \mathcal{B}^{\ast}$ 에 대해 다음과 같이 적을 수 있다고 하자. $$ \begin{align*} \zeta &=& v^{\ast} &+& \sum_{j \in \mathcal{N}^{\ast}} c_{j}^{\ast} x_{j} \\ x_{n+i} &=& b_{i}^{\ast} &-& \sum_{j \in \mathcal{N}^{\ast}} a_{ij}^{\ast} x_{j} \end{align*} $$ 심플렉스 메소드가 사이클에 빠졌다는 것은 모든 $D_{1} , \cdots, D_{k-1}$ 이 타락했다는 의미degenerated고, $v^{\ast} = v$ 이므로 목적 함수 $\zeta$ 는 $j \in \mathcal{B}^{\ast}$ 에 대해 $c_{j}^{\ast} = 0$ 와 같이 둠으로써 다음과 같이 적을 수 있다. $$ \zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j} $$
Part 2. $\zeta = v + c_{s} y$
방정식 폼에서 그랬던 것처럼 어떤 변수가 음수가 되는 상황은 되지 않게끔 진입변수인 $x_{s}$ 가 커지고 나머지 $\mathcal{N}$ 에 있는 변수들은 $0$ 으로 고정하는 상황을 생각해보자. 수식으로 적으면 $$ \begin{align*} x_{s} =& y \\ x_{j} =& 0 & , j \in \mathcal{N} \setminus \left\{ s \right\} \\ x_{i} =& b_{i} - a_{is} y & , i \in \mathcal{B} \end{align*} $$ 이고, 이 $y$ 를 증가 시키는 것이다. 목적 함수 $\zeta$ 를 이에 대해 다시 적어보면 다음을 얻는다. $$ \zeta = v + c_{s} y $$
Part 3.
Part 1의 $\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$ 를 $y$ 에 대해 다시 적어보면 $$ \zeta = v + c_{s}^{\ast} y + \sum_{i \in \mathcal{B}} c_{i}^{\ast} \left( b_{i} - a_{is} y \right) $$ 이고 좌변을 Part 2의 $\zeta = v + c_{s} y$ 로 대입하면 $$ \left( c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} \right) y = \sum_{i \in \mathcal{B}} c_{i}^{\ast} b_{i} $$ 를 얻는다. 이 방정식은 우변이 무엇이든 모든 $y$ 에 대해 항상 성립하는데, 이에 따라 괄호 안이 다음과 같이 항상 $0$ 임을 알 수 있다. $$ \begin{equation} c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} = 0 \end{equation} $$ 다시 말해, 진입 변수가 $x_{s}$ 면 $$ \begin{equation} c_{s} > 0 \end{equation} $$ 임을 알 수 있다. 한편 $x_{t}$ 는 가장 인덱스가 큰 피클이고, $x_{s}$ 도 피클이었으므로 $s < t$ 다. $D^{\ast}$ 의 진입 변수는 $x_{t}$ 라 했으니 $x_{s}$ 는 진입 변수가 아니고, $$ \begin{equation} c_{s}^{\ast} \le 0 \end{equation} $$
이다. $(1), (2), (3)$ 에 따라 $$ \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} < 0 $$ 이고, 다음을 만족하는 $r \in \mathcal{B}$ 가 존재해야한다. $$ c_{r}^{\ast} a_{rs} < 0 $$ 결과적으로 $c_{r}^{\ast} \ne 0$ 이고 $r \in \mathcal{N}^{\ast}$ 이므로 $x_{r}$ 은 피클이고 $r \le t$ 다.
Part 4. $r < t$
우리는 심플렉스 메소드를 상정하고 있으므로 다음 두가지를 이야기할 수 있다.
- $x_{t}$ 가 $D^{\ast}$ 의 진입 변수이므로 $c_{t}^{\ast} > 0$ 이다.
- $x_{t}$ 가 $D$ 의 이탈 변수이므로 $a_{ts} > 0$ 이다.
따라서 $c_{t}^{\ast} a_{ts} > 0$ 인데, $c_{r}^{\ast} a_{rs} < 0$ 이므로 $r \ne t$, 즉 $r < t$ 까지 장담할 수 있다.
Part 5.
$r < t$ 면 $c_{r}^{\ast} \le 0$ 이어야 하는데, 만약 그렇지 않고 $c_{r}^{\ast} > 0$ 이었다면 Part 3에 따라 $r$ 이 $D^{\ast}$ 에 대한 진입변수여야 했을 것이기 때문이다. 이와 Part 3의 $c_{r}^{\ast} a_{rs} < 0$에 따라, $$ \begin{equation} a_{rs} > 0 \end{equation} $$ 이다. 한편 딕셔너리들이 사이클에 빠졌다는 것은 모두 사실상 같은 해solution로 표현된다는 것이고 이에 따라 모든 피클 변수들은 그 딕셔너리에서 $0$ 임을 알 수 있고, 그 중에서도 특히 $x_{r} = 0$ 다. 그러나 $D$ 에서 $x_{r}$ 은 기저변수basic variable이므로, $$ \begin{equation} b_{r} = 0 \end{equation} $$ 이다. $(4)$, $(5)$ 에 따라 $x_{r}$ 는 $D$ 에서 이탈 변수의 후보 중 하나고, Part 4에서 $r < t$ 이므로 브랜드 룰에 따랐다면 $x_{t}$ 대신 진작에 선택(이탈)되었어야 했다. 이 모순에 따라 브랜드 룰을 사용했는데도 딕셔너리가 사이클에 빠져있다는 전제가 거짓임을 알 수 있다.
■
같이보기
선형계획법의 기본정리
이 정리는 선형계획법의 기본정리 증명에 사용된다.
Vanderbei. (2020). Linear Programming(5th Edition): p34~36. ↩︎