simplex method와 cycling 극복법

Simplex method 는 유한한 시간 안에 끝날까?

수학식으로 증명하는 것 말고 수식은 최대한 줄이고 말로 풀어 직관적으로 설명해보려한다. 이 글은 기본적으로 simplex method가 무엇인지 알고 있어야 이해할 수 있다.

Simplex method는 유한한 시간 안에 해를 구해내는 것을 보장할까? 결론부터 말하자면 그렇다.

non-degeneracy 를 가정했을 때

non-degeneracy 를 가정하면 쉽다. Simple method는 항상 Basic feasible solution (BFS) 이 감소하는 방향으로만 움직이니 같은 basis 로 돌아올 수가 없다. 우리는 유한한 basis 를 가지고 있으니 유한한 시간 안에 알고리즘이 끝난다.

degeneracy 가 있을 때- cycling 발생

degeneracy 가 있다는 말은 non basic variable 뿐만이 아니라 basic variable 중에서도 0인 변수가 있다는 말이다. degeneracy가 있는 BFS 에서 0의 값을 갖는 한 non basic variable 을 1로 올리는 방향으로 이동하려고 한다면 아주 조금만 움직여도 음수가 되기 때문에 basic solution은 feasible 영역에서 벗어나게 된다.

어렵게 말했는데 쉽게 말하면 BFS의 값이 조금도 변하지 않는다는 것이다. degeneracy가 없을 때에는 basis가 바뀔때마다 BFS가 무조건 작아진다는 사실을 알고 있었기 때문에 같은 basis 로 돌아오지 못한다는 사실을 알았다 (하나의 basis 값은 오직 하나의 BFS값에 대응된다). 하지만 BFS는 같은 값을 가지며 basis 만 변화하는 degeneracy 상황에서는 어쩌다 같은 basis 로 돌아오게 되는 상황이 생길 수도 있다. 처음 basis 로 돌아오게 된다면 이 현상을 두고 cycling 이 발생했다 말하고 영원히 끝나지 않을 것이다.

Cycling 극복법

이를 극복하는 방법이 Lexicographic rule과 Bland’s rule 로 알려진 pivoting rule 인데 쉽게 말하면 entering basis 과 exiting basis 를 잘 선택함으로써 극복할 수 있다는 것이다. 같은 basis 가 반복되지 않도록 룰을 정하면 된다는 사실을 눈치챘을 것이다.

비교적 간단한 Bland’s rule을 살펴보면 entering basis 를 고를때는 reduced cost $\bar{c_j}$ 가 음수인 것 중 가장 작은 $j$를 선택하고 exiting basis 를 고를때에도 가장 작은 subscription (아래 첨자로 표현, 예를들면 j)을 고르는 식으로 동점 상황을 극복한다.