제 6 장 네트워크 모형 (Network Model)

네트워크 표현 (고속도로의 예) 서울 대구 부산 광주 대전 원주 울산 16 35 9 15 22 14 19 17 8 25 12

네트워크 정의 (정의) 네트워크 여러 개의 node들과 이들을 연결하는 arc들로 구성 (정의) 네트워크 node들 사이에 사람이나 물건들이 arc를 따라 이동 (예) 고속도로망, 전화망, 철도망, TV 네트워크 네트워크 모형은 최근 들어 경영과학 분석기법으로 아주 많이 사용 수많은 실세계 시스템들이 네트워크 형태로 모형화하여 풀 수 있기 때문 여러 개의 node들과 이들을 연결하는 arc들로 구성

대표적인 네트워크 문제 유형 최소비용 네트워크 흐름 문제 (Minimal Cost Network Flow Problem) 최단경로문제 (Shortest Path Problem) 최대흐름문제 (Maximal Flow Problem)

네트워크 구성요소 (예) 고속도로망 네트워크는 노드(Node)와 아크(Arc)로 구성 노드 : 도시 또는 도로의 교차지점 아크 : 각 도시들을 연결하는 도로 노드 : 원으로 표현 아크 : 노드들을 연결하는 선으로 표현 - directed arc (방향이 있는 아크) : 한쪽 방향으로 이동 - undirected arc (방향이 없는 아크) : 양방향으로 이동 네트워크는 노드(Node)와 아크(Arc)로 구성되는 다이어그램으로 표현된다. Directed arc는 선분으로 표시되고, 양방향으로의 물동량의 흐름이 가능한 아크를 뜻한다. Undirected arc는 화살표로 표시되고, 화살표 방향으로만 물동량의 흐름이 가능한 아크를 뜻한다.

네트워크 모형의 수식화 입력 데이터 cij : 노드 i 에서 노드 j 로의 단위당 수송비 uij : arc (i, j) 의 흐름 용량 bi : 노드 i 의 공급량 또는 수요량 결정변수 xij : 노드 i 에서 노드 j 로의 수송량 기본적인 제약조건 - 흐름 보존 법칙(Flow Conservation Rule)

(예제 6-1) 노드 1, 2, 3은 공급지 노드, 노드 5, 6, 7은 수요지 노드 (예제 6-1) 노드 1, 2, 3은 공급지 노드, 노드 5, 6, 7은 수요지 노드 1 4 6 7 3 2 5 40 30 20 -15 -30 -35 생성 흡수 통과

흐름 보존 법칙 (Flow Conservation Rule) (공급지 노드) : 생성 노드에서 나가는 양의 합 ≤ 공급량+노드로 들어오는 양의 합 (수요지 노드) : 흡수 노드로 들어오는 양의 합-노드에서 나가는 양의 합 ≥ 수요량 (경유지 노드) : 통과 노드로 들어오는 양의 합 = 노드에서 나가는 양의 합 공급지 노드의 경우 그 노드에서 공급할 수 있는 양은 그 노드가 자체로 공급가능한 양과 그 노드로 들어오는 양의 합만큼 최대한 공급할 수 있다. 수요지 노드의 경우 그 노드로 들어오는 양의 합에서 그 노드로부터 나가는 양의 합을 뺀 양이 수요량보다 커야 한다.

제약조건 순흐름(net flow) = (노드에서 나가는 양의 총합) - (노드로 들어오는 양의 총합) 제약조건(흐름보존법칙) (공급지 노드) 순흐름 ≤ 공급량 (수요지 노드) 순흐름 ≤ - 수요량 (경유지 노드) 순흐름 = 0

균형 문제(balanced problem) 총공급량의 합 = 총 수요량의 합 부등호 " ≤ " 대신에 등호 "="을 사용해도 됨. (공급지 노드) 순흐름 = 공급량 (수요지 노드) 순흐름 = - 수요량 (경유지 노드) 순흐름 = 0

기타의 경우 네트워크의 각 아크를 따라 흘려보낼 수 있는 양에 제한이 주어지는 경우, 아래의 제약조건식을 추가 0 ≤ xij ≤ uij

6.4 최소비용 네트워크 흐름 문제 수요지 노드들이 요구하는 양을 공급지 노드들로부터 수송하고자 할 때, 전체 수송비가 최소가 되도록 하는 수송방법을 찾는 문제 공급지 노드로부터 최종 수요지 노드에 수송하는 양은 다른 공급지 노드나 수요지 노드 또는 경유지 노드들을 경유하여 수송하는 것이 가능 수송문제와 유사

수송문제와의 차이점 수송문제 최소비용 네트워크흐름문제 경유지 노드가 없다. 공급지 노드에서 수요지 노드로의 직접 수송만 가능 경유지 노드가 있다. 공급지 노드에서 수요지 노드로의 직접 수송뿐만 아니라, 다른 공급지 노드나 경유지 노드를 경유하여 수요지 노드로 수송하는 것도 가능

(예제 6-1) 1 4 6 7 3 2 5 40 30 20 -15 -30 -35

수학적 모형 Min z = 4x12+3x14+4x24+5x26+2x31+2x34 (결정변수) xij : 노드 i 에서 노드 j 로의 수송량 결정변수 개수 = 아크 개수 (12개) (목적함수) Min z = 4x12+3x14+4x24+5x26+2x31+2x34 +7x37+5x45+3x46+4x47+ x65+2x76 (제약조건식) 7개 노드 각각에 대해 흐름보존법칙에 관한 제약조건식이 하나씩 대응 제약조건식 개수 = 7개 (비음제약조건 제외)

제약조건식 (노드 1) x12 + x14 - x31 ≤ 40 (노드 2) x24 + x26 - x12 ≤ 30

엑셀 입력 모형 행렬 입력 방식 아크-노드 입력 방식 7 x 7 행렬표 작성 (아크 표)와 (노드 표) 작성 실제 사용된 아크와 노드만으로 입력모형 구성 행렬입력방식에 비해서 훨씬 간단

행렬 입력 방식 행렬 입력 방식 : 7×7 행렬표 작성 ① 입력 데이터 단위당 수송비 : 셀 범위 C3:I9 행렬 입력 방식 : 7×7 행렬표 작성 ① 입력 데이터 단위당 수송비 : 셀 범위 C3:I9 아크가 존재하지 않는 곳 : 임의의 큰 수송비 할당 공급량/수요량 : 셀 범위 C22:I22 - 수요지 노드 : 수요량에 ??부호를 붙여 입력 - 경유지 노드 : 0의 값을 입력(4번 노드) ② 변경할 셀 : 셀 범위 C12:I18 ③ 셀 범위 J12:J18 : 각 노드에서 나가는 양의 총합을 계산 J12 : =SUM(C12:I12), J12를 J13에서 J18까지 복사 ④ 셀 범위 C19:I19 : 각 노드로 들어오는 양의 총합을 계산 C19 : =SUM(C12:C18), C19를 D19에서 I19까지 복사 ⑤ 셀 범위 J12:J18에 있는 각 노드에서 나가는 양의 총합을 셀 범위 C20:I20에 전치. (전치 방법) 1) 셀 범위 C20:I20을 블럭 잡은 상태에서 =TRANSPOSE(J12:J18)을 입력한다. 2) [Ctrl] 키와 [Shift]키를 동시에 누른 상태에서 [Enter]키를 누른다. ⑥ 셀 범위 C21:I21 : (각 노드에서 나가는 양의 총합 - 들어오는 양의 총합)을 계산 ⑦ 목표 셀 : 셀 C24 (총수송비) C24 : =SUMPRODUCT(C3:I9,C12:I18)

아크 - 노드 입력 방식 H7 : =SUMIF($C$7:$C$18,G7,$B$7:$B$18) 아크 표 12개의 아크가 각각 하나씩 행에 대응(모두 12개의 행) B7:B18 : 변경할 셀(각 아크를 따라 수송하는 수송량) C7:D18 : 12개 아크의 시작 노드와 끝 노드를 나타내도록 노드 번호를 입력 E7:E18 : 단위당 수송비 노드 표 7개의 노드가 각각 하나씩 행에 대응(모두 7개의 행) G7:G13 : 노드 번호 I7:I13 : 공급량/수요량 (공급량은 +, 수요량은 - 로 표시, 경유지 노드의 경우엔 0) H7:H13 : 각 노드의 순흐름(net flow) 계산 H7 : =SUMIF($C$7:$C$18,G7,$B$7:$B$18)-SUMIF($D$7:$D$18,G7,$B$7:$B$18) H7을 H8에서 H13까지 복사 목표 셀 : B20 (총수송비) B20 : =SUMPRODUCT(E7:E18,B7:B18) H7 : =SUMIF($C$7:$C$18,G7,$B$7:$B$18) - SUMIF($D$7:$D$18,G7,$B$7:$B$18)

6.5 최단경로문제(Shortest Path Problem) 출발지 노드에서 출발하여 목적지 노드에 도착하기까지 주행하는데 소요되는 총시간(또는 총거리)의 합이 최소가 되는 경로를 찾는 문제 (예) 서울에서 출발하여 부산에 도착하기까지는 여러 경로를 따라 갈 수가 있는데, 이 중에서 가장 짧은 경로를 찾는 문제

최단경로문제의 예 3 1번 노드에서 10번 노드까지 가장 짧은 경로를 찾는 문제 12 1 6 10 9 4 2 8 5 7 11 1번 노드로부터 10번 노드까지 가는 최단 경로를 찾는 문제 → 1번 노드로부터 10번 노드로 물건 한 단위를 최소의 비용으로 수송하는 최소비용 네트워크 흐름문제로 간주 공급지 노드 : 출발지 노드(1번 노드), 공급량=1 수요지 노드 : 목적지 노드(10번 노드), 수요량=1 경유지 노드 : 나머지 모든 노드들(2,3,...,9) 노드 : 10개 → 제약조건식이 대응 아크 : 16개 → 결정변수가 대응 xij : 아크 (i, j)가 최단경로의 아크로 선택되면 1, 그렇지 않으면 0인 이진 변수 1번 노드에서 10번 노드까지 가장 짧은 경로를 찾는 문제

(예제 6-2)

수학적 모형 1번 노드로부터 7번 노드까지 가는 최단경로를 찾는 문제는 1번 노드로부터 7번 노드까지 물건 1 단위를 최소비용으로 수송하는 최소비용 네트워크 흐름문제로 간주할 수 있다. 1번 노드 (출발지 노드) 1단위를 공급할 수 있는 공급지 노드 7번 노드 (목적지 노드) 1단위를 필요로 하는 수요지 노드 2~6번 노드 : 경유지 노드

수학적 모형 (결정변수) xij : 아크 (i, j)가 최단경로의 아크로 선택되면 1, 아니면 0인 이진 변수

수학적 모형 Min z = 16 x12 + 9 x13 + 35 x14 + 12 x24 + 25 x25 + 15 x34 + 22 x36 + 14 x45 + 17 x46 + 19 x47 + 8 x57 + 14 x67 s.t. x12 + x13 + x14 = 1 x24 + x25 - x12 = 0 x34 + x36 - x13 = 0 x45 + x46 + x47 - x14 - x24 - x34 = 0 x57 - x25 - x45 = 0 x67 - x36 - x46 = 0 -x47 - x57 - x67 = -1 xij ≥ 0

엑셀입력모형(최단경로문제) 목표 셀 : E18 변경할 셀 : B5:B16 E5:E16 : 12개의 고속도로 구간별 거리 입력 I5:I11 : 노드의 공급량 또는 수요량 입력 1번 노드 : 출발 도시이므로 공급량이 1인 공급지 노드에 해당 7번 노드 : 목적지 노드이므로 수요량이 1인 수요지 노드에 해당 2번 ~ 6번 노드 : 모두 경유지 노드로 간주하여 0의 값을 입력 C5:D16 : 고속도로 구간 12개의 시작 노드와 끝 노드를 표시 B5:B16 : 각 구간이 선택되느냐의 여부를 나타냄.(변경할 셀에 해당) 변경할 셀의 초기값으로 모두 0을 입력 H5:H11 : 각 노드의 순흐름(net flow)을 계산 H5 : =SUMIF($C$5:$C$16,G5,$B$5:$B$16) -SUMIF($D$5:$D$16,G5,$B$5:$B$16) H5를 H6에서 H11까지 복사 E18 : 목표 셀 (1번 노드에서 7번 노드까지의 총주행거리를 나타냄.) E18 : =SUMPRODUCT(E5:E16,B5:B16) 목표 셀 : E18 변경할 셀 : B5:B16 제한 조건 : B5:B16 ≥ 0, H5:H11 ≤ I5:I11

최적해(최단경로문제) 1번 도시로부터 7번 도시까지의 최단경로 : 1→ 3 → 4 → 7 총 주행거리 : 43 E5:E16 : 12개의 고속도로 구간별 거리 입력 I5:I11 : 노드의 공급량 또는 수요량 입력 1번 노드 : 출발 도시이므로 공급량이 1인 공급지 노드에 해당 7번 노드 : 목적지 노드이므로 수요량이 1인 수요지 노드에 해당 2번 ~ 6번 노드 : 모두 경유지 노드로 간주하여 0의 값을 입력 C5:D16 : 고속도로 구간 12개의 시작 노드와 끝 노드를 표시 B5:B16 : 각 구간이 선택되느냐의 여부를 나타냄.(변경할 셀에 해당) 변경할 셀의 초기값으로 모두 0을 입력 H5:H11 : 각 노드의 순흐름(net flow)을 계산 H5 : =SUMIF($C$5:$C$16,G5,$B$5:$B$16) -SUMIF($D$5:$D$16,G5,$B$5:$B$16) H5를 H6에서 H11까지 복사 E18 : 목표 셀 (1번 노드에서 7번 노드까지의 총주행거리를 나타냄.) E18 : =SUMPRODUCT(E5:E16,B5:B16) 목표 셀 : E18 변경할 셀 : B5:B16 제한 조건 : B5:B16 ≥ 0, H5:H11 ≤ I5:I11 1번 도시로부터 7번 도시까지의 최단경로 : 1→ 3 → 4 → 7 총 주행거리 : 43

6.6 최대흐름문제(Maximal Flow Problem) 출발지 노드로부터 목적지 노드까지 단위시간동안 최대한 물량을 수송하기 위해 각 아크를 따라 수송하는 양을 결정하는 문제 (예) 송유관, 가스관, 송수관 출발지 노드와 목적지 노드가 각 한 개씩 존재, 이들 사이에 다수의 경유지 노드들 존재 아크들에는 단위시간동안 물량이 흐를 수 있는 양에 제한 : 아크 흐름 용량(Flow Capacity)

(예제 6-3) 1 4 7 6 3 2 5

수학적 모형 (결정변수) xij : 노드 i 에서 노드 j 로 한 시간동안 수송하 f : 한 시간동안 인천에 수송되는 원유의 양 (목적함수) Max z = f (제약조건식) 흐름보존법칙 : 7개 노드 각각에 대해 제약조건식이 하나씩 대응 아크의 용량 제약

제약조건식 (흐름보존법칙) (아크용량제약) x12 + x13 = f x12 ≤ 6, x13 ≤ 7 (흐름보존법칙) (아크용량제약) x12 + x13 = f x12 ≤ 6, x13 ≤ 7 x24 + x25 - x12 = 0 x24 ≤ 3, x25 ≤ 4 x34 + x36 - x13 = 0 x34 ≤ 3, x36 ≤ 4 x45 + x46 - x24 - x34 = 0 x45 ≤ 3, x46 ≤ 1 x57 - x25 - x45 = 0 x57 ≤ 5, x67 ≤ 6 x67 - x36 - x46 = 0 (비음 제약) -x57 - x67 = -f xij ≥ 0 , f ≥ 0

엑셀 입력 모형(최대흐름문제) ① 아크 표와 노드 표 작성 아크 표 : 10개의 행으로 구성 셀 범위 C6:D15 : 10개 아크의 시작 노드와 끝 노드를 표시 셀 범위 E6:E15 : 각 아크의 흐름 용량에 대한 상한값을 입력 노드 표 : 7개의 행으로 구성 셀 범위 I6:I12 : 노드의 공급량 또는 수요량을 입력 - I6 : =B16 (1번 노드는 공급지 노드이므로 공급량이 f 임.) - I12 : =­B16 (7번 노드는 수요지 노드이므로 수요량이 f 임.) - I7:I11 : 모두 경유지 노드이므로 0을 입력 셀 범위 H6:H12 : 각 노드의 순흐름(net flow)을 계산 H6 : =SUMIF($C$6:$C$15,G6,$B$6:$B$15)-SUMIF($D$6:$D$15,G6,$B$6:$B$15) H6를 H7에서 H12까지 복사 ② 변경할 셀 셀 범위 B6:B15 : 단위 시간동안 각 아크를 따라 흐르는 양 셀 B16 : 목적지 노드 7번에 단위 시간동안 수송하는 양으로 f 값에 해당 변경할 셀의 초기값으로 모두 0을 입력한다. ③ 목표 셀 : 셀 B16 - B16은 변경할 셀이면서, 동시에 목표 셀이 된다. ④ 제한 조건 : B6:B16>= 0 (비음 제약) H6:H12<= I6:I12 (흐름보존법칙 제약) B6:B15 <= E6:E15 (아크의 흐름용량 제약)

최적해(최대흐름문제) 1번 노드에서 7번 노드까지 최대 흐름량 =10 목표 셀 : E18 변경할 셀 : B5:B16 E5:E16 : 12개의 고속도로 구간별 거리 입력 I5:I11 : 노드의 공급량 또는 수요량 입력 1번 노드 : 출발 도시이므로 공급량이 1인 공급지 노드에 해당 7번 노드 : 목적지 노드이므로 수요량이 1인 수요지 노드에 해당 2번 ~ 6번 노드 : 모두 경유지 노드로 간주하여 0의 값을 입력 C5:D16 : 고속도로 구간 12개의 시작 노드와 끝 노드를 표시 B5:B16 : 각 구간이 선택되느냐의 여부를 나타냄.(변경할 셀에 해당) 변경할 셀의 초기값으로 모두 0을 입력 H5:H11 : 각 노드의 순흐름(net flow)을 계산 H5 : =SUMIF($C$5:$C$16,G5,$B$5:$B$16) -SUMIF($D$5:$D$16,G5,$B$5:$B$16) H5를 H6에서 H11까지 복사 E18 : 목표 셀 (1번 노드에서 7번 노드까지의 총주행거리를 나타냄.) E18 : =SUMPRODUCT(E5:E16,B5:B16) 목표 셀 : E18 변경할 셀 : B5:B16 제한 조건 : B5:B16 ≥ 0, H5:H11 ≤ I5:I11 1번 노드에서 7번 노드까지 최대 흐름량 =10