logo

심플렉스 메소드의 브랜드 룰 📂최적화이론

심플렉스 메소드의 브랜드 룰

정리

딕셔너리: i=1,⋯ ,mi = 1 , \cdots , m 에 대해서 다음과 같은 꼴의 연립방정식을 딕셔너리dictionary라 한다. ζ=∑j=1ncjxjxn+i=bi−∑j=1naijxj \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라 한다. 이들의 인덱스를 다음과 같이 나타낸다. B:={n+1,n+2,⋯ ,n+m}N:={1,2,⋯ ,n} \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의 인덱스를 N\mathcal{N} 에서 가장 작은 것으로 선택하고, 이탈 변수leaving variable의 인덱스를 B\mathcal{B} 에서 가장 작은 것으로 선택하는 것을 브랜드 룰Brand’s rule이라 한다. 브랜드 룰에 따르면 심플렉스 메소드는 사이클에 빠지지 않는다.

설명

선형계획문제를 푸는 방법도 심플렉스 메소드 단 하나가 아니고, 심플렉스 메소드에서 딕셔너리를 업데이트하는 피벗 룰pivot rule 역시 단 하나가 아니지만 브랜드 룰이 있음으로써 심플렉스 메소드는 반드시 선형계획문제를 풀 수 있음이 보장된다는 점이 중요하다. 이 정리를 이해하게 되면 사실 선형계획법에서 가장 중요한 두가지 컨셉, 그 중에서 심플렉스 메소드는 마스터 했다고 보아도 무방하다.

증명 1

전략: 쉽지 않다. 브랜드 룰로 피벗을 하는데 사이클에 빠지는 것이 모순임을 보일 것이다.

Part 1. ζ=v+∑j=1n+mcj∗xj\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}

일반성을 잃지 않고, 사이클링이 일어난 시점부터 증명을 시작하자. 이는 어떤 k∈Nk \in \mathbb{N} 에 대해 딕셔너리가 다음과 같이 순환하는 것이다. D0,D1,⋯ ,Dk−1,D0,D1,⋯ D_{0} , D_{1} , \cdots, D_{k-1} , D_{0} , D_{1} , \cdots 이 딕셔너리 중 어떤 것에서는 기저고 어떤 것에서는 기저가 아닌 변수를 피클fickle이라 부르겠다. 이들 중 xtx_{t} 가 가장 큰 인덱스를 가진 피클이라 하고, xtx_{t} 를 이탈 변수로 가지는 딕셔너리를 DD 라 할 때, 일반성을 잃지 않고 D=D0D = D_{0} 라 뒀을 때 DD 는 ∀i∈B\forall i \in \mathcal{B} 에 대해 다음과 같이 적을 수 있다. ζ=v+∑j∈Ncjxjxn+i=bi−∑j∈Naijxj \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*} 여기서 xsx_{s} 가 진입 변수라 하면 xtx_{t} 가 이탈 변수고 아직은 t∈Bt \in \mathcal{B} 고 s∈Ns \in \mathcal{N} 이다. 이제 D∗D^{\ast} 를 D1,⋯ ,Dk−1D_{1} , \cdots, D_{k-1} 중에서 xtx_{t} 가 기저에 진입한 딕셔너리라 두고, ∀i∈B∗\forall i \in \mathcal{B}^{\ast} 에 대해 다음과 같이 적을 수 있다고 하자. ζ=v∗+∑j∈N∗cj∗xjxn+i=bi∗−∑j∈N∗aij∗xj \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*} 심플렉스 메소드가 사이클에 빠졌다는 것은 모든 D1,⋯ ,Dk−1D_{1} , \cdots, D_{k-1} 이 타락했다는 의미degenerated고, v∗=vv^{\ast} = v 이므로 목적 함수 ζ\zeta 는 j∈B∗j \in \mathcal{B}^{\ast} 에 대해 cj∗=0c_{j}^{\ast} = 0 와 같이 둠으로써 다음과 같이 적을 수 있다. ζ=v+∑j=1n+mcj∗xj \zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}

Part 2. ζ=v+csy\zeta = v + c_{s} y

방정식 폼에서 그랬던 것처럼 어떤 변수가 음수가 되는 상황은 되지 않게끔 진입변수인 xsx_{s} 가 커지고 나머지 N\mathcal{N} 에 있는 변수들은 00 으로 고정하는 상황을 생각해보자. 수식으로 적으면 xs=yxj=0,j∈N∖{s}xi=bi−aisy,i∈B \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*} 이고, 이 yy 를 증가 시키는 것이다. 목적 함수 ζ\zeta 를 이에 대해 다시 적어보면 다음을 얻는다. ζ=v+csy \zeta = v + c_{s} y

Part 3.

Part 1의 ζ=v+∑j=1n+mcj∗xj\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j} 를 yy 에 대해 다시 적어보면 ζ=v+cs∗y+∑i∈Bci∗(bi−aisy) \zeta = v + c_{s}^{\ast} y + \sum_{i \in \mathcal{B}} c_{i}^{\ast} \left( b_{i} - a_{is} y \right) 이고 좌변을 Part 2의 ζ=v+csy\zeta = v + c_{s} y 로 대입하면 (cs−cs∗+∑i∈Bci∗ais)y=∑i∈Bci∗bi \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} 를 얻는다. 이 방정식은 우변이 무엇이든 모든 yy 에 대해 항상 성립하는데, 이에 따라 괄호 안이 다음과 같이 항상 00 임을 알 수 있다. cs−cs∗+∑i∈Bci∗ais=0 \begin{equation} c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} = 0 \end{equation} 다시 말해, 진입 변수가 xsx_{s} 면 cs>0 \begin{equation} c_{s} > 0 \end{equation} 임을 알 수 있다. 한편 xtx_{t} 는 가장 인덱스가 큰 피클이고, xsx_{s} 도 피클이었으므로 s<ts < t 다. D∗D^{\ast} 의 진입 변수는 xtx_{t} 라 했으니 xsx_{s} 는 진입 변수가 아니고, cs∗≤0 \begin{equation} c_{s}^{\ast} \le 0 \end{equation}

이다. (1),(2),(3)(1), (2), (3) 에 따라 ∑i∈Bci∗ais<0 \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} < 0 이고, 다음을 만족하는 r∈Br \in \mathcal{B} 가 존재해야한다. cr∗ars<0 c_{r}^{\ast} a_{rs} < 0 결과적으로 cr∗≠0c_{r}^{\ast} \ne 0 이고 r∈N∗r \in \mathcal{N}^{\ast} 이므로 xrx_{r} 은 피클이고 r≤tr \le t 다.

Part 4. r<tr < t

우리는 심플렉스 메소드를 상정하고 있으므로 다음 두가지를 이야기할 수 있다.

  • xtx_{t} 가 D∗D^{\ast} 의 진입 변수이므로 ct∗>0c_{t}^{\ast} > 0 이다.
  • xtx_{t} 가 DD 의 이탈 변수이므로 ats>0a_{ts} > 0 이다.

따라서 ct∗ats>0c_{t}^{\ast} a_{ts} > 0 인데, cr∗ars<0c_{r}^{\ast} a_{rs} < 0 이므로 r≠tr \ne t, 즉 r<tr < t 까지 장담할 수 있다.

Part 5.

r<tr < t 면 cr∗≤0c_{r}^{\ast} \le 0 이어야 하는데, 만약 그렇지 않고 cr∗>0c_{r}^{\ast} > 0 이었다면 Part 3에 따라 rr 이 D∗D^{\ast} 에 대한 진입변수여야 했을 것이기 때문이다. 이와 Part 3의 cr∗ars<0c_{r}^{\ast} a_{rs} < 0에 따라, ars>0 \begin{equation} a_{rs} > 0 \end{equation} 이다. 한편 딕셔너리들이 사이클에 빠졌다는 것은 모두 사실상 같은 해solution로 표현된다는 것이고 이에 따라 모든 피클 변수들은 그 딕셔너리에서 00 임을 알 수 있고, 그 중에서도 특히 xr=0x_{r} = 0 다. 그러나 DD 에서 xrx_{r} 은 기저변수basic variable이므로, br=0 \begin{equation} b_{r} = 0 \end{equation} 이다. (4)(4), (5)(5) 에 따라 xrx_{r} 는 DD 에서 이탈 변수의 후보 중 하나고, Part 4에서 r<tr < t 이므로 브랜드 룰에 따랐다면 xtx_{t} 대신 진작에 선택(이탈)되었어야 했다. 이 모순에 따라 브랜드 룰을 사용했는데도 딕셔너리가 사이클에 빠져있다는 전제가 거짓임을 알 수 있다.

■

같이보기

선형계획법의 기본정리

이 정리는 선형계획법의 기본정리 증명에 사용된다.

  1. Vanderbei. (2020). Linear Programming(5th Edition): p34~36. ↩︎