경영과학(Ⅰ) 제9장 네트워크모형 서 론 최단경로문제 최소걸침나무문제 최대흐름문제 secom.hanbat.ac.kr

▶ 서 론 네트워크의 구성요소와 구조 5 2 6 1 마디 2 3 2 1 1 4 1 1 4 3 3 5 2 가지 흐름 네트워크의 종류 - 단방향 네트워크(directed network) - 양방향 네트워크(undirected network) 경로(path, route) : 위 그림의 ①→③→②→④ 와 같은 연속되는 가지 고리(loop, cycle) : ①→③→②→①과 같이 처음으로 되돌아오는 경로 나무(tree) 네트워크 : 고리가 없는 네트워크

▶ 서 론 대표적인 3가지 네트워크 모형 가. 최단경로문제(shortest route problem) : 두 지점 사이의 최단경로(가장 작은 비용  또는  가장 짧은 거리나 시간에 도착할 수 있는 경로)를 찾는 문제(외판원 문제) 나. 최소걸침나무문제(minimum spanning tree problem) : 네트워크상의 모든 연결하는 방법  중에서 가장 작은 비용 또는 시간으로 연결할 수 있는 방법을 찾는 문제 (설비배치문제,  네트워크 설계문제) 다. 최대흐름문제(maximal flow problem) : 네트워크상의 한 지점에서 다른 지점으로 보낼 수 있는 최대 의 유통량을 찾는 문제(교통흐름 분석문제, 송유관 설계문제)

▶ 최단경로문제 출발지점에서 도착지점에 이르는 최단경로를 찾는 문제 예제 모형  : 출발지 ①에서 각 지점까지의 최단경로와 거리를 구하는 영업사원의 문제 13 2 6 12 5 20 6 7 14 20 출발지 1 4 4 1 10 11 30 16 15 3 5 18 영업사원 문제의 네트워크

▶ 최단경로문제 다익스트라법(Dijkstra method) : 가장 대표적인 발견적기법 1단계 처음에 출발마디를 선택하여 각 마디까지의 임시최단거리를 표시하되, 직접 연결되는 가지가 없으면 ∞로 표시한다. 2단계 선택되지 않은 마디에 대하여, 가장 작은 임시최단거리를 갖는 마디를 선택하고 연결하여 영구최단거리로 삼는다. 도착마디가 선택되면 끝내고, 아니면 3단계로 간다. 3단계 선택되지 않은 마디에 대해, 직전에 선택된 마디와 연결될 때의 거리가 기존의 임시최단거리보다 작으면 임시최단거리를 수정하여 2단계로 간다.

▶ 최단경로문제 초기 임시최단거리 ∞ 12 13 2 6 12 5 20 20 6 7 14 1 20 출발지 4 7 ∞ 1 10 11 30 16 15 3 5 18 15 ∞ - ⑤, ⑥, ⑦번 마디는 직접 연결되는 경로가 없으므로 임시최단거리를 ∞로 한다.

▶ 최단경로문제 임시최단거리중 ②번 마디의 임시최단거리가 12로 가장 작으므로 ②번 마디를 선택하여 연결하고, 각 마디의 임시최단거리를 수정 25 12 ∞ × 13 2 6 12 17 5 20 20 × 6 7 14 출발지 1 20 4 7 ∞ 1 10 11 30 16 15 3 5 18 15 ∞

▶ 최단경로문제 임시최단거리중 가장 작은 값(15)을 갖는 ③번 마디를 선택하여 연결하고, 임시최단거리 수정 25 12 ∞ × 13 2 6 12 17 5 20 × 20 6 7 14 20 45 출발지 1 4 7 1 ∞ × 10 11 30 16 15 3 5 18 15 ∞ × 33

▶ 최단경로문제 세 번째 수정된 임시최단거리 24 25 × 12 ∞ × 13 2 6 12 17 5 20 20 × 6 7 14 45 출발지 4 7 1 ∞ × 10 11 30 16 15 3 5 18 15 ∞ × × 33 27

▶ 최단경로문제 네 번째 수정된 임시최단거리 24 25 × 12 ∞ × 13 2 6 12 17 5 20 20 × 7 44 6 14 45 × 출발지 1 20 4 7 1 ∞ × 10 11 30 16 15 3 5 18 15 ∞ × 33 × 27

▶ 최단경로문제 다섯 번째 수정된 임시최단거리 24 25 × 12 ∞ × 13 2 6 12 17 43 5 20 20 × 7 44 × 6 14 20 45 × 출발지 1 4 7 1 ∞ × 10 11 30 16 15 3 5 18 15 ∞ × 33 × 27

▶ 최단경로문제 최종적으로 얻어진 각 지점까지의 최단경로와 최단거리 24 25 × 12 ∞ × 13 2 6 12 17 43 5 최종적으로 얻어진 각 지점까지의 최단경로와 최단거리   24 25 × 12 ∞ × 13 2 6 12 17 43 5 20 × 20 6 7 × 44 14 1 20 45 7 × 출발지 4 1 ∞ × 10 11 30 16 15 3 5 18 15 ∞ × 33 × 27

▶ 최단경로문제 각 지점까지의 최단경로와 거리 지점 최단경로 거리 2 1 – 2 12 3 1 – 3 15 4 1 – 2 – 4 17 5 1 – 2 – 4 – 5 27 6 1 – 2 – 4 – 6 24 7 1 – 2 – 4 – 5 – 7 43

▶ 최소걸침나무문제 네트워크상의 모든 마디를 연결하되, 연결된 총 길이를 최소로 하는 문제 - 수송시스템이나 컴퓨터 네트워크의 설계에 주로 이용 예제 모형 : 6개 지역에 분산되어 있는 컴퓨터를 네트워크로 연결하는 문제 5 2 5 8 3 3 7 3 1 7 6 7 4 4 5 6 8 6 5 컴퓨터 네트워크

▶ 최소걸침나무문제 그리디 해법(greedy algorithm) - 최소걸침나무문제의 대표적 발견적기법 1단계 임의의 마디에서 출발하여, 그 마디와 가장 가까운 마디를 선택하고 연결한다. 2단계 선택되지 않은 마디들에 중에서, 선택된 마디들과의 거리가 가장 짧은 마디를 선택하고 이를 연결한다. 모든 마디가 선택될 때 까지 이를 반복한다.

▶ 최소걸침나무문제 첫 번째 연결 : 1번 마디에서 출발, 가장 가까운 마디가 3번이므로 선택하여 연결 5 2 5 3 3 8 7 7 3 6 7 4 4 5 6 8 6 5

▶ 최소걸침나무문제 두 번째 연결 : 선택된 마디 ①, ③번에서 가장 가까운 거리에 있는 선택되지 않은 마디가 ⑤번이므로 선택하고 이를 ③번 마디와 연결 5 2 5 3 8 1 3 7 7 3 6 7 4 4 5 6 8 6 5

▶ 최소걸침나무문제 세 번째 연결 : 선택된 마디 ①, ③, ⑤번에서 아직 선택되지 않은 ②, ④, ⑥번 마디로 연결되는 경로중 가장 작은 거리를 갖는 마디 ②를 선택 5 2 5 3 8 1 3 7 7 3 6 7 4 4 5 6 8 6 5

▶ 최소걸침나무문제 네 번째, 다섯 번째 연결 : 마찬가지 방법으로 ⑥번, ④번 마디 선택 5 2 5 3 8 1 3 7 7 3 네 번째, 다섯 번째 연결 : 마찬가지 방법으로 ⑥번, ④번 마디 선택 5 2 5 3 8 1 3 7 7 3 6 7 4 4 5 6 8 6 5

▶ 최소걸침나무문제 최종적으로 연결된 네트워크 : 총 거리는 3 + 3 + 4 + 5 + 6 = 21 2 3 3 1 3 4 4 n개의 마디가 주어지면 항상 n-1개의 가지로 연결되는 해를 갖는다. 최적 연결은 시작하는 마디가 어느 마디인가에 관계가 없다.  

▶ 최대흐름문제 각 가지에 흐를 수 있는 용량이 한정되어 있을 때 흘려 보낼 수 있는 최대의 유통량을 구하는 문제 흐름의 예 : 원유, 식수, 가스 등의 유동체나 교통량, 정보량, 통신량 등 예제 모형  : T 지역의 식수공급 문제 3 1 4 1 5 3 2 5 2 4 6 수원지 S 3 T 1 수요지 3 4 3 3 4 2 4 2 5 2 1 식수공급 네트워크

▶ 최대흐름문제 최대흐름문제의 발견적기법 1단계 공급지에서 수요지로 양의 용량을 갖는 경로를 선택한다. 이러한 경로를 선택할 수 없으면, 현재의 흐름량이 최대이다. 2단계 선택한 경로에 포함된 가지의 용량중 최소값을 그 경로의 흐름량으로 배정한다. 3단계 각 가지의 용량에 대해, 위에서 결정된 흐름량을 순방향으로는 빼주고 역방향으로는 더해준 다음 1단계로 간다.

▶ 최대흐름문제 첫 번째 배정 - 양의 흐름용량을 갖는 경로 선택 (S→①→④→T 경로) - 각 가지의 용량이 5, 3, 5이므로 3을 배정 - 흐름량 3을 순방향의 용량에서는 빼주고 역방향의 용량에는 더해준다. 3 1 4 3 1 2 3 2 2 2 3 4 6 S 3 T 3 1 3 3 4 3 3 4 2 4 2 5 2 1 첫 번째 배정 후의 용량 변화

▶ 최대흐름문제 두 번째 배정 : 경로 S→③→T를 선택, 흐름량 min{6, 3} = 3을 배정 3 1 4 3 1 2 3 2 2 2 3 4 3 3 S 3 T 3 1 3 3 4 3 3 4 2 4 2 5 2 1 두 번째 배정 후의 용량 변화

▶ 최대흐름문제 세 번째 배정 : S→②→⑤→T 경로에 2 배정 3 1 4 3 1 2 3 2 2 2 3 4 3 3 S 3 T 2 1 2 3 2 2 3 3 4 2 2 2 5 2 3

▶ 최대흐름문제 네 번째 배정 : S→①→②→③→④→T 경로에 2 배정 3 1 4 5 1 2 3 2 5 2 3 3 S 3 T 2 1 2 3 2 2 5 2 3 4 2 2 5 2 3

▶ 최대흐름문제 다섯 번째 배정 : S→③→⑤→T 경로에 2 배정 3 1 4 5 1 2 3 2 5 2 1 5 S 3 T 2 1 2 3 4 2 5 2 1 4 2 2 5 2 3

▶ 최대흐름문제 최종 배정 결과 3 1 4 5 5 2 S 3 T 12 5 1 12 3 2 수원지 수요지 2 4 2 2 2 5 2

▶ 최대흐름문제 수원지에서 공급할 수 있는 용량은 5 + 6 + 4 = 15이나, 중간경유지의 공급용량에 한계가 있기 때문에 최대흐름량은 12가 된다. 경로 선택의 차이에 따라 각 가지에 흐르는 양도 달라질 수도 있으나, 각 경로에 배정되는 양은 서로 다르더라도 네트워크의 최대흐름은 12로 변하지 않는다. 최소절단-최대흐름 정리(minimal cut- maximal flow theorem) : 네트워크상의 최대흐름은 네트워크를 절단하는 경로들의 집합 중 용량의 합이 최소인 값과 같다. : 이 문제에서 최대흐름량 12는 수원지와 수요지를 절단하는 경로의 집합 중 최소의 순방향 흐름량을 갖는 {④→T, ③→T, ⑤→T}의 순방향 용량의 합(5 + 3 + 4 = 12)이다.

경영과학(Ⅰ) 제9장 네트워크모형 수 고 했 어 요 !!! secom.hanbat.ac.kr