16. Iterative Improvement

  Iterative Improvement은 최적의 해답을 찾는 알고리즘 중 하나이다. 기본적인 문제 풀이의 원칙은 '현재 가능한 솔루션에서 좀 더 나은 솔루션으로 개선해 나가는 것'이다. 점진적인 개선 활동을 통해 최적의 해를 찾아내는 것이 Iterative Improvement의 핵심이다.

  Iterative Improvement의 대표적인 방법은 선형 계획법(LP, Linear Programming)이다. 선형 계획법에 대해 자세히 알아보자.

1. 선형계획법 (Linear Programming)

  대학교 전공떄 계량분석론을 한번이라도 들어본 경험이 있다면 매우 쉽게 그 개념을 이해할 수 있을 것이다. 혹은 중학교때 배운 연립방정식을 배운 적이 있을 것이다. 이 두가지 문제가 일종의 선형계획법이다. 아래의 문제를 통해서 생각해보자

  EX) 어떤 카페에서 라떼와 아메리카노를 팔려고 한다. 아메리카노의 경우 물과 커피 원료로 만들어지고, 라떼의 경우 커피 원료와 우유로 만들어진다. 물의 값은 공짜에 가까워서 0원이라고 가정하고, 커피 원료와 라떼는 별도로 돈을 내야하는 상황이다. 아메리카노 한잔을 만들기 위해 커피 원료는 총 80g이 사용된다. 반면 라떼 한잔을 위해서는 커피 원료 60g과 우유 100ml가 든다고 하자. 그리고 아메리카노 한잔의 수익은 300원이고, 라뗴 한잔의 수익은 450원이다. 오늘 우리 매장에서는 커피 원료가 2Kg, 우유가 3L를 보유하고 있다. 우리가 가진 재료로 최대의 수익을 내려면 아메리카노와 라떼를 각각 몇잔씩 만들어야 하는가?

  이 문제를 분석해보자. 선형계획법 문제를 풀기 위해서 의사결정 변수를 정해야 한다. 의사결정 변수란 우리가 최종적으로 구해야 하는 해라고 생각하면 된다.

  - 의사결정변수 : X_1 (아메리카노 개수), X_2 (라뗴 개수)

  목적 함수는 우리가 최대로 하고자 하는 값이다. 우리는 수익의 극대화가 목표이므로 수익에 관한 수식이 우리가 구하려는 목적합수가 된다.

  - 목적 함수 : max (300 * X_1 + 450 * X_2)

  이 문제의 제약 조건은 총 2가지 이다. 우리가 가진 커피 원료와 우유의 양이다. 이 두가지 제약 조건에 관한 식은 아래와 같이 표현된다.

  - 제약 조건 : (커피원료) 80 * X_1 + 60 * X_2 <= 2000

  (우유)       100 * X_2 <= 3000 

  우리는 해를 구하기 위해 3가지 영역으로 구분할 수 있다. 우선 제약조건을 만족시키는 '실행 가능 영역(feasible region)'이 존재할 것이다. 하지만, 이는 최적해는 아니다. 우리가 가진 원료로 만들 수 있는 음료의 양일 뿐, 최고의 수익을 낼 수 있는 값은 아니다. 이 영역 안에 있는 해의 값을 '실행가능해 (feasible solution)' 이라고 한다. 이 실행가능해 중에서 실제로 수익을 극대화 할 수 있는 해가 '최적해 (optimal Solution)'이 된다. 최적해는 아예 없을 수도, 하나만 있을 수도, 무한대로 많을 수도 있다. 의사결정 변수가 2개이고 선형 함수 내에서는 0개, 1개, 무한대가 존재하게 된다. 선형 계획법은 도해법과 단체법으로 해결할 수 있다.

 1.1 도해법 (Graphical Solution Method)

• 제약조건식을 만족시키는 영역을 그래프 상에 나타내어 해를 찾는 방법
• 변수가 3개 이상이면 표현하기 곤띾하며, 4개 이상이면 적용 불가능
• 실행가능 영역의 꼭짓점에 최적해가 존재

  도해법을 이용해 문제를 풀어보자. 우선 2가지 제약 조건에 따라 그래프를 그리게 되면 아래 영역과 동일하게 된다.

  위 사진에서 두 영역이 겹치게 되는 부분이 제약조건을 통과하게 되는 부분이다. 꼭지점 4 부분에 대해 목적 함수를 계한하면 X_1 = 2.5, X_2 = 30에서 최대 값을 가져오게 된다. 따라서 가장 많은 수익을 내고 싶다면, 아메리카노 2잔 라떼 30잔을 판매하면 된다.

  도해법에서도 알 수 있듯이 의사결정 함수가 3개라면 3차원 영역에 포현해야 하므로 표현이 매우 어려워 진다. 그리고 4개라면 4차원 영역으로 넘어가게 되므로 표현이 아예 불가능 해진다.

  도해법으로 특수한 해도 구할 수 있다. 만약 제약 조건과 목적 함수가 동일 선상에 존재하게 된다면, (위 문제에서 아메리카노의 가격이 80원 라뗴의 가격이 60이라면, 혹은 비율이 이와 같다면)해가 최적 해의 개수는 다수가된다. 혹은 라떼 한잔의 가격보다 원료 값이 비싸진다면 실행 가능영역으로 목적함수가 들어오지 않게 된다. 이런 경우 해는 존재하지 않게 된다.

 1.2 단체법 (Simplex Method)

• 의사결정변수 값 중 기본 값을 시작으로 좀 더 나은 해로 변경을 반복함으로써 최적해를 찾는 방법
• Simplex method는 optimal solution을 보장하는 것으로 알려져 있음

  실제로 선형계획법을 해결하는데 가장 많이 쓰이는 방법은 단체법이다. 예시를 통해서 단체법에 대해 알아보자. 우선 단체법 해결을 위해서 부등식으로 표현된 제약조건을 등식으로 교체해야한다. 이를 위해서 여유변수를 사용해야 한다.

목적 함수 : max (        300 * X_1 + 450 * X_2 + 0 * u + 0 * v)

제약 조건 : (커피원료)    80 * X_1 +  60 * X_2 +      u             = 2000

    (우유)                        100 * X_2 +                v   = 3000 

단체법 해결을 위해 위의 표준형 방정식으로 Simplex Table을 만든다.

  단체법에서 가장 아래 목적함수 열에 있는 숫자들이 음수에서 벗어나게 된다면 최적해가 된다. 이를 위해서 첫번 쨰로 진입 변수를 선택한다.

  진입 변수를 선택하는 방법은 목적함수 열이 음수이면서, 가장 작은 값을 선정해야 한다. 따라서 위 표에서 진입변수는 X_1이 된다.

  그 다음은 퇴출 변수를 지정해야 한다. 퇴출 변수는 진입변수 열의 제약조건식 계수에 대한 우변상수의 비율 (θ-ratio )를 구하여 양수 값 중 가장 작은 값 이다. 이렇게 지정된 퇴출 변수는 x_1 열의 u 변수가 된다.

  이 변수를 Pivot element로 하여 새로운 Simplex table을 만들게 된다. pivot element 값이 1이 되고 진입변수 열의 나머지 값들은 모두 0이 되도록 하기 위한 행 단위 연산이며, 가우스 소거법으로 계산하여 새로운 테이블을 만들게 된다.

  

  노란색으로 표현된 Pivot Element를 기준으로 두번째 Simplex Table을 만들게 된다. 해당 값을 1로 만들어야 하므로 Pivot Element의 제약 함수 식은 아래처럼 80으로 나누어 새로운 식을 만든다. ( x_1 = 1, x_2 = 3/4, u = 1/80, v = 0, value = 25 )

  두번쨰 열의 경우 이미 x_1값이 0이므로 따로 건드리지 않아도 된다.

  마지막 열의 경우 x_1 값을 0으로 만들어야 한다. 이때, 좌측의 u 변수를 x_1로 변경하게 되고, 이 값은 앞서 구한 value 값인 25와 동일할 것이다. 따라서 (300*25 = 7500) 만큼의 값을 u 변수로 채워주게 된다. u 변수의 값은  (300 / 80 = 15 / 4)로 작성한다.

  이렇게 구한 두번째 Simplex table은 아래와 같이 나온다.

 

  이제 두번째 진입변수은 x_2에 대한 식을 계산하자. Pivot Element를 1로 만들어야 하고, 해당 열의 값을 게산할 수 있다. ( x_1 = 0, x_2 = 1, u = 0, v = 1/100, value = 30 )

  그리고 위의 열의 경우 해당 변수를 0으로 만들어야 한다. 두변째 열에서 x_2의 열이 1이고, 값은 30이었으므로 이 값에 따라 x_2의 값은 30이 나오게 된다. 30을 첫번쨰 열에 대입하게 된다면 3/4 * 30 = 90/4 = 45/2가 나오게 되고, x_2 값을 0으로 만들기 위해 전체 값을 25 - (45/2)로 구한다. 따라서 값은 5/2가 된다.

( x_1 = 1, x_2 = 0, u = 1/80, v = 0, value = 5/2 )

  마지막 변에서 위 값을 이용해 해를 구한다. (5/2, 30, 0, 0)이 4개의 정보를 활용해 마지막 목적 함수의 계수 값을 구한다면, 아래와 같이 나오게 된다.

  

  Simplex Method를 활용해 앞서 구한 도해법과 같은 방식의 해를 구할 수 있다. 최고 수익은 14250원이 되고, 아메리카노의 개수는 2개 라뗴의 개수는 30개로 동일한 값이 계산된다.

  Simplex Method는 그래프를 그리기 어랴운 경우 단순한 수식만으로 문제를 해결할 수 있으므로 매우 유용하다. 기본 적인 개념은 한쪽 변수에서의 해를 구하고 그 다음 변수의 해를 구하는 매우 단순한 방법이다. 문제를 단순히 이해하기에는 직관적일 수 있겠으나, 막상 변수를 선정하고 Pivot Element를 통해 계산해야하는 횟수가 매우 많다는 단점이 존재한다. 두 방법 각각 모두 장단점이 존재한다고 볼 수 있다.

2. Shortest-Augmenting-Path Algorithm

  Shortest-Augmenting-Path 알고리즘은 BFS를 이용하여 최소 간선수를 갖는 증가 경로(augmenting path)를 선택하기위한 방법이다. 알고리즘에 대해 자세히 알아보기 위해 아래의 네트워크 문제를 풀어보자.

  S로부터 T로 도달해야하는 네트워크가 존재를하고, 각 간선의 용랑은 위와 같다. Iterative Improvement에서는 S로부터 T까지의 경로를 선택하고, 해당 경로의 간선 중 최소값을 선택해 그 만큼 모든 경로에 용량을 선택하게 된다. 그리고 해당 경로는 BFS로 선택한다.

Queue 1 2 3 4 5

여기서 1에서 2로 가는 경로는 없기 때문에 3번으로 이동하게 되고, 4와 5 순서대로 이동하는 첫 번째 루트가 완성된다.

Route : S -> 1 -> 3 -> 4 -> 5 -> T

이 중 최소 경로는 3번에서 4번으로가는 용량 1의 간선이다. 따라서 해당 루트의 간선들에 1씩 Flow를 추가 시킨다. 그 다음 루트는 BFS에 의해 연속적으로 선택하게 된다.

Route : S -> 1 ->3 -> 5 -> T

  이번 루트에서는 최소 값이 1에서 3번으로 가는 간선이다. 앞선 루트에서 이미 1의 Flow를 채웠기 떄문에 총 5만큼의 Flow를 추가한다. 따라서 위 값을 반영하면 위와 같이 된다.

Route : S -> 1 -> 4 -> 5 -> T

Route : S -> 2 -> 5 -> T

  이렇게 최종적인 네트워크 플로우가 만들어지고, 최대 플로우는 13이 된다. 

시간 복잡도는 O(VE^2)가 된다.