[Optimization] 6. Simplex

안녕하세요. 이번 포스팅부터는 LP 최적화에 꽃이라고 할 수 있는 Simplex method에 대해서 배워보도록 하겠습니다.

Simplex method 는 LP 문제를 푸는 가장 기본적인 방법입니다.

​

위와 같은 문제가 있을 때, 기본적으로 최적의 해는 꼭지점들 중에 있다고 가정할 수 있습니다.

초기 점으로 (0,0)을 선택하고, x축이나 y축을 따라, 두번 째 점으로 이동하고 계속해서 꼭지점으로 이동하면서 최적 해를 찾아야 합니다.

이 때, 어느 방향으로 먼저 가는가에 대한 알고리즘이 바로 Simplex method 라고 할 수 있습니다.

​

Simplex method를 가장 간단하게 이해하기 위해서는 예시를 보면서 배우는 것이 가장 좋다고 생각합니다.

위와 같은 문제를 풀어야합니다. 눈으로 보기에도 답이 무엇인지 직감이 안갑니다.

Simplex method의 첫 번째 단계로, 제약조건의 부등호를 등호로 바꾸어주어야 합니다.

각 식에 새로운 변수 (Slack variables)를 정해주면 위와 같이 등호로 바뀌게 됩니다.

​

이제 위 식을 아래와 같은 표로 만들어줍니다.

이 때, Z-C 에 대해서, x1 이 -12로 가장 작은 값을 가지므로, x1=0 으로 만들어야 합니다.

XB, x1 사이의 Ratio 를 구한 후, 가장 작은 값을 가지는 (S1) 을 Basic variable로 만들어 줍니다. (=0)

이제 S1이 x1으로 바뀌었고, Z가 업데이트가 되었습니다. Z는 C 의 x1의 -12를 제거하기 위해서 기존의 S1 행에 12가 곱해져서 더해진 것입니다.

다음 과정으로 똑같이 Z-C를 해주시고, 가장 작은 값인 x2를 0으로 만들어 주어야 합니다.

XB와 x2 의 Ratio를 계산하고, 가장 작은 값을 가지는 S4가 Basic variable로 설정됩니다.

이제 S4이 x2으로 바뀌었고, Z가 업데이트가 되었습니다. Z는 C 의 x2의 -9를 제거하기 위해서 기존의 S4 행에 9가 곱해져서 더해진 것입니다.

다음 과정으로 똑같이 Z-C를 해주시고, 가장 작은 값인 S1을 0으로 만들어 주어야 합니다.

XB와 S2 의 Ratio를 계산하고, 가장 작은 값을 가지는 S3가 Basic variable로 설정됩니다.

최종적으로 모든 Z-C 가 0보다 크거나 같은 값을 가지게 되면 iteration이 종료가 됩니다.

Z=17700 의 값을 가지며, x1=650, x2=1100, S1=350, S2=400, S3=0, S4=0 이 최적값이네요!!