본문에 앞서 주의할 점
제가 어떤 개념에 대해 이해할 때는 저만의 언어로 해석해서 이해하는 부분이 많아서 기존과 용어가 다르기 때문에 이해하기 힘들 수 있습니다. 교육의 목적이 아니라 정리의 목적이 강한 점 양해 부탁드립니다. 혹시라도 논리상의 모순이 존재한다면 지적해주시면 감사하겠습니다.
Linear Programming (LP)
Linear Programming은 n개의 변수가 있고, m개의 선형 조건들이 있을 때, 각 변수들에 m개의 선형 조건을 만족하는 적절한 값을 대입해서 목표 함수를 최대화(Maximize)하는 문제입니다.
저는 Applied Finite Mathematics (Sekhon and Bloom)(link)를 보고 공부하였습니다.
위 문제는 n이 2일때는 중학 수학에서 배우지만, 3, 4, 5차원 등등 쭉쭉 올라갈수록 손으로 풀기에는 + 직관적으로 풀기에는 벅차다는 생각이 듭니다.
LP의 standard form에 대해 생각해보면 다음과 같습니다.
maximize Z = f(x_1, x_2, ... , x_n)
s.t.
g_1(x_1,x_2,...,x_n) <= r_1
g_2(x_1,x_2,...,x_n) <= r_2
...
g_m(x_1,x_2,...,x_n) <= r_m
x_1,x_2,...,x_n >= 0
f(x_1, x_2, ... , x_n) = f_1*x_1 + f_2*x_2 + ... + f_n * x_n
g_i(x_1, x_2, ... , x_n) = g_i_1*x_1 + g_i_2*x_2 + ... + g_i_n * x_n
임의의 LP 문제는 위 standard form으로 변환이 가능합니다.
- i번째 부등식의 방향이 반대(>=) 인 경우
g_i(x_1, x_2,...,x_n) <= r_i인 상태라면 양변에 -1을 곱하면
-g_i(x_1, x_2, ... , x_n) >= r_i로 표현이 가능합니다. - i번째 식이 부등식이 아닌 등호(=)인 경우
g_i(x_1, x_2,...,x_n) = r_i인 상태라면
g_i(x_1, x_2,...,x_n) >= r_i
g_i(x_1, x_2,...,x_n) <= r_i
위 두 식을 동시에 만족하는 것과 같게 됩니다. - x_i <= 0을 만족해야 하는 경우
모든 식 g에 대해 x_i의 계수에 -1을 곱하면 x_i>=0이 됩니다. (x_i를 -x_i로 치환)
Simplex Method
Simplex Method는 탐욕법 (greedy method)에 기반을 두고 있습니다.
최악의 경우 지수승의 시간복잡도를 갖게 되지만, 해당 데이터를 만들기 위해서는 지수꼴의 정수를 다뤄야 하기 때문에 경험적인 시간복잡도는 N^2M이 된다고 합니다.
Simplex Method를 이용해 LP를 푸는 과정은 다음과 같습니다.(link)
1. LP문제를 standard form으로 변환합니다
2. 각 부등식을 양의 값을 갖는 변수 y_i를 추가해 g_i(x_1, x_2, ..., x_n) + y_i = r_i꼴로 변환합니다.
그리고 최대화 해야 하는 식인 Z = f(x_1, x_2, ..., x_n)에서 f를 이항해 -f(x_1, x_2, ..., x_n) + Z = 0꼴로 표현해둡니다.
3. 해당 m개의 등식들을 (m+1) x (n+m+2) 행렬로 표현합니다.
column은 x_1, x_2, ..., x_n, y1, y2, ... y_m, Z, r로 표현이 되고, i번째 row는 i번째 등식을 표현합니다.
맨 마지막 row는 objective function (f)를 표현해줍니다.
4. 그리디하게 맨 마지막 row에서 음수이면서 가장 작은 값을 갖는 column p를 pivot column으로 선택해줍니다.
5. 위 m개의 row에 대해 r / p가 최소인 row를 구합니다.
6. 해당 row에 대해 p를 1로 만들도록 등식에 p에 있는 값을 나눕니다.
7. 가우스 소거법처럼 실행합니다. 그 후 4번 로직으로 돌아갑니다. 만약 그런 해가 없으면 최적해를 찾은 겁니다.
8. (m+1, n+m+2)에 있는 값이 해가 됩니다.
최악의 경우 반복을 지수 스케일로 할 수 있지만, 그렇게 많은 반복을 하기 위해서는 데이터에 지수 스케일의 정수가 필요하기 때문에 그럴일 없다 볼 수 있습니다.
two-phase simplex method
초기 상태가 feasible area에 존재하면 단순 simplex method를 이용해서 해를 구할 수 있습니다. (ex. 모든 변수에 부등호 방향이 <= 같은 상태)
하지만, 그렇지 않은 경우 simplex를 이용해 해를 구할 수 없습니다.
따라서 위 기술한 simplex를 돌리기 전 초기 상태를 적절히 배치하기 위해 simplex를 한번 더 돌려 줍니다.
Duality
duality는 기존 LP standard 문제가 objective function을 maximize하는 문제였다면,
해당 문제와 동치인 objective function을 minimize문제를 구하는 방법입니다.
- 작성중 -
MCMF
LP 중에서 N이 2로 제한된 문제의 경우 이분그래프로 모델링할 수 있는 가능성이 있어서 Simplex를 이용하지 않고, mcmf를 이용한 풀이가 있는지도 고민을 해봐야 합니다.
- 작성중 -
http://www.maths.qmul.ac.uk/~ffischer/teaching/opt/notes/notes8.pdf