Simplex method 에서 basis 를 나간 basic variable은 바로 다음 pivot 에 들어올 수 있을까?

Q1. Simplex method 에서 특정 pivot 에서 basis 를 나간 어떤 basic variable x_j는 그 바로 다음 pivot 에서 들어올 수 있을까?

없다.

기하학적으로 생각해보자. 특정 pivot 과 그 다음 pivot 의 basis 는 adjacent basic feasible solution 이다. 즉, 하나만 빼고 모두 같은 basic variable 을 공유한다. extreme points 들이 다면체의 꼭지점들이라고 본다면 한 꼭지점에서 (BFS) iteration 이 끝나면 다른 인접한 꼭지점으로 edge를 따라 이동해서 다른 꼭지점 (adjacent BFS)에 도달하는 셈이다. 이러한 관점에서 봤을때 특정 basis 를 나간 어떤 basic variable x가 바로 다음 pivot 에서 들어온다는 말은 왔던 edge를 타고 본래의 BFS로 돌아간다는 말과 같다. simplex를 이해한 사람이라면 직관적으로 이런 일은 일어나지 않을 것이라는걸 눈치챌 수 있다. edge를 타고 왔다는 건 reduced cost 가 감소하는 방향으로 움직인다는 것인데 그걸 도로 타고 갔다는건 reduced cost 가 다시 증가하는 방향으로 움직인다는 뜻이고 모순이 생긴다.

 

Q2. 그렇다면 미래에는 들어올 수 있을까?

있다.

들어올 수 없다면 simplex method는 n 시간 안에 끝난다는 사실이 보장되어야하는데 그렇지않다.