최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예. 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 2 +x +7x +2x 25 +0x +8x 5 +5x 5 sub.to x 2 +x +x = 0, x 2 +x 25 =, x +x +x 5 = -, x x +x 5 = -, x 25 x 5 x 5 = -7, x 2 apple, x apple 0, x apple, x 25 apple 0, x apple 5, x 5 apple 5, x 5 apple 5, x ij 0. 질량보존법칙 용량제약조건
기본용어 최소비용흐름문제알고리듬 - 용량제약이없는경우 P := v v 2 v l v v l 유향네트워크의경로의에서 로갈때, 호의방향이일치할경우정방향호, 반대인경우역방향호라고하자. P c(p ) 경로의비용을다음과같이정의하자 = 정방 향호의비용합 - 역방향호의비용합 그림에서경로 P = i j k l 의비용은 - + = 0 이다.
음수회로를사용하는 최소비용흐름문제알고리듬 회로의흐름을조정하여해를개선한다. (6) q 흐름 2 비용 2 i 5 0 2 (2) p 0 s 2 j 2 2 0 l k t 2 (-5) (-)
음수회로를사용하는 최소비용흐름문제알고리듬 ( 계속 ) 예를들어회로 C = i-j-k-l-p-q 를보자. (6) q 흐름 2 비용 2 i 5 0 2 (2) p 0 s 2 j 2 2 0 l k t 2 (-5) (-)
음수회로를사용하는 최소비용흐름문제알고리듬 ( 계속 ) 현재가능흐름 x를회로 C := i j k l p q i 를따라가며다음 과같이조정해보자. 이렇게조정된흐름은각마디에서균형을유지하게된다. 또한역방향흐름이모두양수이면, 비음조건을만족하게하는 의최대값은 2 가된다 : + 0, 2 0, 2+ 0, 0, 0, 2+ 0. - 조정에의한목적함수의변화는다음과같다 : (c ij c jk + c kl c lp c pq + c qi )=2 ( 6) 위의예처럼회로의비용 c(c) 가음수인경우, -조정은목적함수를감소시킨다. 이러한회로를흐름증가음수회로혹은음수회로라고한다. 만약흐름증가음수회로에서역방향호가없다면? x ij +, x jk 2, x kl 2+, x lp, x pq, x qi 2+.
음수회로를사용하는 최소비용흐름문제알고리듬 ( 계속 ) 개선된흐름 : 개선된비용 2 x 6 =2 (6) q 흐름 비용 2 i 2 5 0 2 (2) p 0 s 2 j 0 0 l k t 2 (-5) (-)
음수회로를사용하는 최소비용흐름문제알고리듬 ( 계속 ) 음수회로와최적조건은다음과같은관계가있다 : 현재가능흐름에흐름증가음수회로가존재한다면해의개선이가능하다. 역으로, 흐름증가음수회로가더이상존재하지않으면, 현재가능흐름이최적이다. ( 증명생략 ) 따라서현재가능흐름에대한흐름증가음수회로를찾아앞서 - 조정으로해를개선시키는단계를반복하면최소비용흐름문제를푸는알고리듬이된다. 우리가배울네트워크심플렉스알고리듬은특별한형태의흐름을유지하여음수회로를신속하게찾는다.
걸침나무해 가능흐름 x 에대해다음의조건을만족하는걸침나무 T 가존재하면 x를걸침나무해또는나무해라고부른다. T (i, j) 에속하지않는호의흐름은모두 0 이다. 나무해 나무해가아닌가능흐름
걸침나무해 ( 계속 ) 최소비용흐름문제가최적해를가지면, 반드시나무해가되는최적해가존재한다. 증명 : 나무해가아닌최적흐름이있다고하자. 즉, 호의흐름크기가모두 >0인회로 C 가존재한다하자. 회로의어느방향으로 -조정을해도 >0이므로회로의비용은 0이어야한다. 이때, 회로 C 의흐름을역방향호흐름의최소값만큼 -조정하자. ( 역방향호가없으면회로의방향을반대로바꾼다.) 회로의비용이 0이기때문에, 조정된흐름도최적흐름이되고, 회로 C 에서흐름이 0인호가최소한개이상발생하기때문에회로 C는제거된다. 회로밖의흐름의변화는없다. 따라서, 전체네트워크에서볼때, 이러한과정을최대호의갯수만큼반복하기전에모든호의흐름이 0 보다큰회로를모두제거할수있다.
네트워크심플렉스알고리듬 매반복단계마다나무해를유지한다. 현재나무해에서음수회로를찾아 -조정을하여개선된나무해를얻는단계를반복한다. 현재나무해에대응하는걸침나무를 T라하자. 네트워크심플렉스알고리듬은 T 에속하지않는호를추가했을때발생하는회로만고려한다. 회로의방향은추가한호의방향으로정한다. ( 이러한음수회로가존재하지않으면현재해가최적해임을증명할수있다.) 이예에서, 세개의호 (,5), (5,2), 그리고 (,6) 에대해세개의회로가발생 C := 5 2 -, 비용 -7 C 2 := 5 2 5 -, 비용 C := 6 5 2 -, 비용 -
네트워크심플렉스알고리듬 ( 계속 ) 회로의비용을구하는체계적인방법 ) 마디를임의로하나선택하여뿌리마디로지정한다. 2) 걸침나무 T에서, 뿌리마디에서각마디 i까지의경로의비 용을 (i) 라고하자. ) 그러면호 (i, j) 가 T에추가되어만들어진회로의비용은 다음과같다 : c ij c ij + (i) (j). 뿌리마디 : C := 5 2 -, 비용 -7 C 2 := 5 2 5 -, 비용 C := 6 5 2 -, 비용 -
네트워크심플렉스알고리듬 ( 계속 ) 회로를따라 - 조정을하자. C := 6 5 2 즉, 정방향호의흐름은 만큼증가시키고역방향호의흐름은 만큼감소시킨다. 이때회로의비용이 -이므로목적함수는 - 만큼증가한다. 는역방향호의흐름크기중최소값까지증가시킬수있다. 이경우 이다. 만약역방향호가없다면?.
네트워크심플렉스알고리듬 ( 계속 ) 회로를따라 - 조정을하자. C := 6 5 2 즉, 정방향호의흐름은 만큼증가시키고역방향호의흐름은 만큼감소시킨다. 이때회로의비용이 -이므로목적함수는 - 만큼증가한다. 는역방향호의흐름크기중최소값까지증가시킬수있다. 이경우 이다. 만약역방향호가없다면? 목적함수를무한히감소시킬수있다.
새로운나무해는최적일까? 네트워크심플렉스알고리듬 ( 계속 ) -조정을하면, 역방향호중하나의흐름이 0으로감소하고, 새로추가한호의흐름의크기는 가된다. 예에서, 호 (2,) 의흐름이 0 으로, 호 (,6) 의흐름이 으로바뀌었다. 걸침나무에서 (2, ) 를제거하고, (, 6) 을추가하여새로운나무해를얻을수있다 : 이때, 나무가바뀌었기때문에 도재계산한다.
네트워크심플렉스알고리듬 ( 계속 ) 초기화 : 초기나무해를구하고, 뿌리마디를임의로선택한다. 주반복단계 : 알고리듬이종료할때까지다음을반복한다 : ) 현재나무해의 를구한다. 2) 현재걸침나무 T 에속하지않는호 (i, j) 중에서 c ij < 0 를만족하는것을선택한다. 그런호가없으면현재해는최적해이다. ) 위에서선택한호 (i, j) 를 T 에첨가했을때생기는음수회로를따라역방향호가없으면최적해는존재하지않는다. 알고리듬을종료한다. ) 역방향호흐름의최소값을구하여 -조정을하여새로운나무해를구한다. T에 (i, j) 를첨가하고흐름이 0으로감소한역방향호중임의로하나를 T에서삭제하여새로운 T 를구한다.
최소비용걸침나무문제 (Minimum Spanning Tree Problem) 입력 : 무향네트워크 G =(N,A), 각호 e 2 A의비용 c e. 출력 : 호비용의합이최소가되는걸침나무 T.
프림 (Prim) 의알고리듬 초기화 : 임의마디 r을선택하여 T ({r}, ;). 주반복단계 : T 가모든마디를포함할때까지다음을반복 : 양끝마디중에서하나만 T 의마디집합에포함된호중에서가장비용이작은호를하나선택하여 T 에첨가한다.
프림의알고리듬 ( 계속 ) 다음예를보자. 뿌리마디는 r = 로설정하였다 마디 에연결된호중최소비용호를택한다. 마디, 에연결된호중최소비용호를택한다. 각단계마다추가가능한호중에서비용이가장작은호를선택한다. 이러한성질을가진알고리듬을 greedy 알고리듬이라한다. 최소비용걸침나무문제는 greedy 알고리듬이항상최적해를구하는특성을지니고있다.
크라스칼 (Kruskal) 의알고리듬 T (;, ;) 초기화 :. 주반복단계 : 을반복 : T 가모든마디를포함할때까지다음 T 에추가했을때회로를발생시키지않는호중에 서, 비용이가장작은호를에추가한다. 또다른 greedy 알고리듬이가능할까? T
최소비용스타이너나무문제 -Minimum Steiner tree problem 입력 : 단순네트워크 G =(N,A), 각호 e 2 A의비용 c e, 마디의부분집합 M N. 출력 : 것. M을연결하는나무중에서호비용의합이최소가되는 M = {, 2,, 6, 7} 인예 최소비용걸침나무문제와다른점은마디의부분집합 M을연결한다는것이다. 최소비용걸침나무문제와유사하지만최적해를신속히구하는것이불가능한문제