Linear Programming

Linear Programming이란 무엇일까? 

이름만 들어선 몬지 감조차 안온다. 이제 이것에 대해서 알아보도록 하자. 이번 포스팅은 다음 문서를 번역한 것에 불과함을 미리 말한다. 

Linear Programming.pdf

1. Introduction 

 Linear Programming(LP) 문제는 linear한 constraint를 갖는 상황에서 linear한 함수를 최대화, 혹은 최소화 하는 문제를 푸는 것을 의미한다. 여기서 constraint는 등호이거나 부등호이다. 다음의 예를 보자. 

x1과 x2가 있다. 이 때 x1+x2 = y를 최대화하려고 하고 constraint는 다음과 같다. 

 x1 >= 0

 x2 >= 0

 x1 + 2*x2 <= 4

 4*x1 + 2*x2 <= 12

 -x1 + x2  <= 1

 이 문제에서 두 개의 모르는 변수가 있고, 다섯 개의 constraint가 있다. 모든 constraint들은 부등호이고, 모두 linear하다. 먼저 처음 두 개의 constraint, x1 >= 0과 x2 >= 0 는 special하다. 이들은 non-negativity constraint라고 불리고, LP 문제에서 종종 보이곤 한다. 나머지 constraint들은 main constraint라고 불린다. 최대화(혹은 최소화)시켜야 할 것은 objective function이라고 불린다. 여기서 objective function은 x1+x2 이다. 

  이 문제에서 두 개의 변수만이 있으므로 우리는 이 문제를 모든 조건을 만족시키는(constraint set이라고 불린다) 그래프를 그린 후에 objective function의 값을 최대화 하는 점을 찾음으로서 풀 수 있다. 각 inequality constraint는 half-plane의 점으로 만족되어지고, constraint set은 이들 각 half-plane의 교차점을 의미한다. 현재 예제에서 constraint set는 Figure1에서 어둡게 칠해진 영역이다. 

 우리는 x1+x2를 최대로 하는 point (x1, x2)를 찾는데, 이 때 (x1, x2)는 constraint set 안에서 찾아야 한다. x1+x2 함수는 기울기가 -1인 직선 에선 동일한 값을 갖는다. 이 직선을 원점에서 위로 울릴 수록, 혹은 오른쪽으로 보낼 수록 그 값이 커진다. 그러므로 우리는 기울기가 -1이고, constraint set에 포함되는 직선 중에서 가장 오른쪽 혹은 위에 있는 직선을 찾으면 된다. 이는 x1+2*x2=4와 4*x1+2*x2=12가 만나는 점에서 일어나고, (x1, x2) = (8/3, 2/3)이다. objective function의 값은 (8/3)+(2/3)=10/3이다. 

 일반적으로 objective function이 linear하다면, constraint set의 조건을 만족하는 영역의 코너에서 objective function의 최대값(혹은 최소값)이 정해진다. 때때로, 최대값이 constraint set의 전 edge에서 형성되기도 하지만, 코너에서 일어나기도 한다. 

 모든 linear programming이 이렇게 쉽게 풀리는 것은 아니다. 많은 변수가 있을 수도 있고, 많은 constraint가 있을 수도 있다. 어떤 변수들은 양수로 한정될 수도 있고, 어떤 변수들은 unconstrained일 수도 있다. main constraints들 중 몇은 등호이고, 나머지는 부등호일 수 있다. 그러나, standard maximum problem, standard minimum problem이라 불리는 두 종류의 문제는 중요한 역할을 수행한다. 이러한 문제들에서 모든 변수들은 nun-negative로 한정되고, 모든 main constraint들은 부등호로 한정된다. 

 m-vector, b = (b_1, ... b_n)' 와 n-vector, c = (c_1, ..., c_n)', 와 실수로 이루어진 m*n matrix가 주어졌다.

 

The Standard Maximum Problem: 다음을 최대화하는 n-vector, x = (x_1, ..., x_n)'를 찾자. 

 이는 다음 constraints를 갖는다. 

The Standard Minimum Problem: 다음을 최소화하는 n-vector, y = (y_1, ..., y_n)'를 찾자. 

 

이는 다음 constraints를 갖는다. 

 

 여기서 주의할 점은 main constraints는 standard maximum problem은 <=로 나타내고, standard minimum problem은 >=로 나타낸다. 설명을 위한 예제는 standard maximum problem에 대한 것이다. 

 우리는 이제 네 개의 일반적인 linear programming problem의 예제를 설명할 것이다. 각 문제들은 extensively studied 되었다.

 Example 1. The Diet Problem. m개의 서로 다른 음식, F_1, ..., F_m이 있고, 이들이 건강에 필수적인 n개의 영양소, N_1, ..., N_n,를 제공한다. c_j가 하루에 최소 필요 영양분, N_j, 라고 하자. b_i를 F_i의 unit 가격이라고 하자. a_ij 는 음식 F_i에 포함된 영양소 N_j의 양이라고 하자. 이 경우 우리는 필요한 영양소를 최소 가격으로 제공하는 방법을 찾고자 한다. 

 y_i는 하루에 소비하는 음식 F_i의 야이라고 하자. 그러면 하루에 소비되는 가격은 다음과 같다. 

 

 이런 식단에 포함된 영양소 N_j는 다음과 같다. 

  j = 1, ...,n 에 대해서, 우리는 하루 최소 필수 영양소를 맞추지 못하면 그러한 식단은 고려하지 않는다, 즉 다음 constraint를 갖는다. 

 물론 우리는 음의 음식을 사지 않기 때문에 자동으로 다음의 constraints를 갖게 된다. 

 즉 우리의 문제는 다음과 같이 된다. (1)을 최소화 하되, (2)와 (3)에 subject되어야 한다. 이것은 정확히 standard minimum problem이다. 

Example 2. The Transportation Problem. I개의 상품 생산소, P_1, ..., P_I가 있다고 하자. 이들은 특정 상품을 생산하고, 상품이 배송되야 하는 J개의 시장, M_1, ..., M_J가 있다고 하자. P_i은 각각 s_i개의 상품을 가질 수 있고, 시장 M_j는 물량 r_j 만큼의 물량을 받아야만 한다. b_ij는 P_i에서 M_j로 단위 물량을 옮기는데 드는 비용을 의미한다. 우리가 풀고자 하는 것은 최소 배송 비용으로 시장 수요를 맞추려는 건다. 

 y_ij는 P_i에서 M_j로 배송되는 물량이라고 하면 전체 배송 비용은 다음과 같다. 

 

 특정 Port P_i에서 가질 수 있는 상품의 수는 최대 s_i이므로 다음의 constraint를 갖는다. 

 각 시장 M_j의 최소 물량은 r_j이므로 마음의 constraint를 갖고, 

 모든 물량은 0보다 커야 한다. 

 우리의 문제는 (4)를 최소화 하되, (5), (6), (7)을 constraint를 갖게 된다. 

 이 문제를 standard minimum problem 문제에 적용하자. y의 수는 I*J이기 때문에 m = I*J이다. 하지만 n은 무엇인가? n는 main constraint의 수이다. n = I + J 이지만, 어떤 constraint는 >=를 갖고, 다른 것은 <=를 갖는다. standard minimum problem에서는 모든 constraint는 >=를 갖는다. 이를 위해서는 (5) constraint를 -1을 곱해서 얻을 수 있다. 

 이제 우리의 문제는 (4)를 최소화 하되, (5'), (6), (7)를 constraint로 갖는다. 

Example 3. - 생략 - 

Example 4. - 생략 -  

Terminology

 - 최대화 되거나 최소화될 함수는 objective function이라고 불린다. 

 - 만약 standard maximum problem에서는 x, standard minimum problem에서는 y는  corresponding constraint를 만족할 때 feasible하다고 한다. 

 - feasible vector의 모음을 constraint set이라고 한다. 

 - constraint set이 비지 않았을 때 LP는 feasible이라고 하고, 그렇지 않을 경우 infeasible이라고 한다. 

 - ... 후략...

2. Duality.

 모든 LP는 긴밀히 연결된 dual linear program이 존재한다. 우리는 먼저 standard program에 대한 duality에 대해서 먼저 기술하겠다. Section 1과 같이 c와 x는 n-vector이고, b와 y는 m-vector이고, A는 m*n matrix이다. 우리는 m가 n은 모두 1보다 크거나 같다고 가정한다. 

Definition. 어떤 standard maximum problem이 있을 때, 

 이 문제의 dual은 standard minimum problem으로 주어지고, 다음과 같다. 

 이전 section에서 살펴본 예제를 보자: 이 문제는 x_1+x_2를 최대화 하는 x_1과 x_2를 찾는 것이고, constraint는 x_1과 x_2는 모두 0보다 크고, 다음의 constraint를 갖는 것이었다. 

 이 standard maximum problem의 dual은 standard minimum problem이 된다: 4*y_1_12*y_2+y_3를 최소화하는 y_1과 y_2와 y_3를 찾는 문제이고 이 때 constraint는 y_1, y_2, y_3 모두 0보다 크고, 다음의 constraint를 갖는다.  

 만약 standard minimum problem (2)가 standard maximum problem으로 바뀐다면(A, b, c를 모두 -1을 곱해서), 이것의 dual은 정의에 의해 ...(1)과 정확히 같아진다. 그러므로 (1)과 (2)는 dual이라고 불릴 수 있다. 

 general standard maximum problem과 dual standard minimum problem은 동시에 나타내 질 수 있다. 

 우리의 예제로 표현해 보면 다음과 같다. 

 standard problem 사이의 관계와 dual은 다음 theorem과 이것의 corollaries로 나타내진다. 

 ... 나머진 내일 하자. -_-;