1조 김국회,신재욱,정주영,이기한 류미진,박남수,김은종 Operation Research 1조 김국회,신재욱,정주영,이기한 류미진,박남수,김은종

목 차 보충문제 6.4 연습문제 9.2 네트워크 모형(이기한) 수송모형의 선형계획 모형(김국회, 정주영) 목 차 보충문제 6.4 네트워크 모형(이기한) 수송모형의 선형계획 모형(김국회, 정주영) 제약조건이 변형된 모형(신재욱, 류미진) 연습문제 9.2 다익스트라법이란? 연습문제로 본 해석(김은종, 박남수)

보충문제 6.4 E유통은 두 군데(1,2)공장에서 생산한 제품을, 세 군데(3,4,5)창고를 거쳐 네 군데(6,7,8,9)의 대리점으로 수송하고 있다. 공장1과 2는 생산능력이 1,500개와 2,000개이고, 대리점 5,6,7,8의 하루 수요량은 800, 950, 1,000, 750이라 한다. 각 창고는 제품을 무제한 수용할 수 있으며, 각 공장과 창고 그리고 창고와 대리점간의 단위당 수송비용(단위 : 천원)은 아래와 같다. 이 회사의 총 수송비용을 최소로 하는 수송계획을 수립하려고 한다.

보충문제 6.4 창고와 대리점간의 수송비용 공장과 창고간의 수송비용 창고 3 창고 4 창고 5 공장 1 26 19 20 공장 2 18 16 25 창고와 대리점간의 수송비용 대리점 6 대리점 7 대리점 8 대리점 9 창고 3 14 22 20 16 창고 4 32 17 21 28 창고 5 19 18 23 8

네트워크 모형 대리점 6 창고 3 공장 1 대리점 7 창고 4 대리점 8 공장 2 창고 5 대리점 9 창고 3 창고 4 26 19 20 공장 2 18 16 25 대리점 6 창고 3 공장 1 대리점 7 창고 4 대리점 8 공장 2 창고 5 대리점 9 대리점 6 대리점 7 대리점 8 대리점 9 창고 3 14 22 20 16 창고 4 32 17 21 28 창고 5 19 18 23 8

수송모형의 선형계획 모형 선형계획모형 변수값 : Xij 공장 i에서 창고j로 또는 창고 i에서 대리점j로 수송할 수송량 목적함수값(총수송비용의 최소화) Min.Z = 26X13 + 19X14 + 20X15 + 18X23 + 16X24 + 25X25 + 14X36 + 22X37 + 20X38 + 16X39 + 32X46 + 17X47 + 21X48 + 28X49 + 19X56 + 18X57 + 23X58 + 8X59

수송모형의 선형계획 모형 제약조건 공급능력의 제약 중간창고의 제약 수요량의 제약 비음조건 X13+X14+X15 ≤ 1500 X13 + X23 = X36 + X37 + X38 + X39 X14 + X24 = X46 + X47 + X48 + X49 X15 + X25 = X56 + X57 + X58 + X57 비음조건 Xij ≥ 0 (i=1,2 j=3,4,5,6,7,8,9)

수송모형의 선형계획 모형

수송모형의 선형계획 모형 목적함수값 각 루트별 수송량

수송모형의 선형계획 모형 800 대리점 6 800 창고 3 공장 1 대리점 7 950 750 창고 4 대리점 8 1200 공장 2 1200 1000 창고 5 750 대리점 9 750

수송모형의 선형계획 모형 거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39 36 40 28 1500      거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39   36 40 28 1500 8(선택1) 750 공장2 32 33 37 2000 1 수요량 800 950 1000 750   3500 Vj 7 3 5(선택1)

수송모형의 선형계획 모형 거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39 36 40 28 1500      거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39   36 40 28 1500 3 750 공장2 32 33 37 2000 1 800 수요량 950 1000 750   3500 Vj 7(선택2) 5(선택1)

수송모형의 선형계획 모형 거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39 36 40 28 1500      거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39   36 40 28 1500 750 공장2 32 33 37 2000 800 950 수요량 1000 750   3500 Vj 7(선택2) 3(선택3) 3 5(선택1)

수송모형의 선형계획 모형 거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39 36 40 28 1500      거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 Ui 공장1 39   36 40 28 1500 40(선택4) 750 공장2 32 33 37 2000 800 950 수요량 1000 750   3500 Vj 7(선택2) 3(선택3) 3 5(선택1)

수송모형의 선형계획 모형      거래회사 공장 대리점6 대리점7 대리점8 대리점9 공급량 공장1 39   36 40 28 1500 750 공장2 32 33 37 2000 800 950 250 수요량 1000 750   3500 최적해 32 × 800 + 33 × 950 + 37 × 250 + 40 × 750 + 28 × 750 = 117200

제약조건이 변형된 모형 대리점 9의 수량이 750에서 1200으로 늘어나고, 각 대리점에서의 단위당 부족비용이 15일 때, 최적 수송계획을 말하라 공장 1 공장 2 대리점 6 대리점 7 대리점 8 대리점 9 공장 0 (가상공장) 대리점 6 대리점 7 대리점 8 대리점 9 공장 1 39 36 40 28 공장 2 32 33 37 공장 0 15

제약조건이 변형된 모형 선형계획모형 변수값 : Xij 공장 i에서 대리점j로 수송할 수송량 목적함수 값 Min.Z = 39X16 + 36X17 + 40X18 + 28X19 + 32X26 + 33X27 + 37X28 + 33X29 + 15X06 + 15X07 + 15X08 + 15X09

제약조건이 변형된 모형 제약조건 공급능력의 제약 대리점에서 물량의 부족비용 수요량의 제약 비음조건 X16 + X17 + X18 + X19 ≤ 1500 X26 + X27 + X28 + X29 ≤ 2000 대리점에서 물량의 부족비용 X06 + X07 + X08 + X09 ≤ 450 수요량의 제약 X16 + X26 + X06 ≥ 800 X17 + X27 + X07 ≥ 950 X18 + X28 + X08 ≥ 1000 X19 + X29 + X09 ≥ 1200 비음조건 Xij ≥ 0 (i=0,1,2 j=6,7,8,9)

제약조건이 변형된 모형

제약조건이 변형된 모형 목적함수값 각 루트별 수송량

제약조건이 변형된 모형 대리점 6 800 공장 1 300 대리점 7 650 공장 2 550 대리점 8 450 공장 0 (가상공장) 450 대리점 9 1200

제약조건이 변형된 모형 대리점 공장 6 7 8 9 공장1 39 36 40 28 (1500) 300 300 1200 공장2 32   공장1 39 36 40 28 (1500) 300 300 1200 공장2 32 33 37 (2000)  (1650) 700 350 950 가상공장0 15 450 (800) 350 (1000) 300 3,950

제약조건이 변형된 모형 대리점 공장 6 7 8 9 Ui 공장1 39 36 40 28 1500 (4) (0) 300 1200   Ui 공장1 39 36 40 28 1500 (4) (0) 300 1200 공장2 32 + 33 37 - 2000 -3 350 950 700 (8) 가상공장0 15 450 -20 (-1) (-5) (7) 800 1000 3,950 Vi 35

제약조건이 변형된 모형 대리점 공장 6 7 8 9   Ui 공장1 39 36 40 28 1500 (4) (0) 300 1200 공장2 32 33 37 2000 -3 800 950 250 (8) 가상공장0 15 450 -25 (5) (6) (12) 1000 3,950 Vi 35 최적해 40X300 + 28X1200 + 32X800 + 33X950 + 37X250 + 15X450 = 118550

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

연습문제 9.2 아래 네트워크는 8개 도시간의 이동시간을 나타내는 것이다. 다음 각 경우에 대한 최단경로를 구하여라 3 6 5 4 6 3 2 2 1 5 1 8 2 5 1 7 2 3 1 6 6 2 7 4 5 8

시작점 1번에서 가장 작은 임시최단거리인 2번 도시로 이동 연습문제로 본 풀이과정 2 ∞ 3 4 6 ∞ 3 2 2 1 5 1 8 2 5 1 7 2 3 ∞ 1 6 6 2 7 4 5 8 ∞ 1 ∞ 시작점 1번에서 가장 작은 임시최단거리인 2번 도시로 이동

시작점 2번에서 가장 작은 임시최단거리인 3번 도시로 이동 연습문제로 본 해석 2 ∞ 3 4 6 3 3 2 2 1 5 1 8 2 5 1 7 2 3 ∞ 1 6 6 2 7 4 5 8 ∞ 1 6 시작점 2번에서 가장 작은 임시최단거리인 3번 도시로 이동

시작점 3번에서 가장 작은 임시최단거리인 5번 도시로 이동 연습문제로 본 해석 2 6 3 4 6 3 3 2 2 1 5 1 8 2 5 1 7 2 3 ∞ 1 6 6 2 7 4 5 8 ∞ 1 4 시작점 3번에서 가장 작은 임시최단거리인 5번 도시로 이동

시작점 5번에서 가장 작은 임시최단거리인 6번 도시로 이동 연습문제로 본 해석 2 6 3 4 6 3 3 2 2 1 5 1 8 2 5 1 7 2 3 ∞ 1 6 6 2 7 4 5 8 10 1 ∞ 시작점 5번에서 가장 작은 임시최단거리인 6번 도시로 이동

연습문제로 본 해석 3 6 5 1 8 2 7 4 1 – 2 – 3 – 5 – 6 번 도시를 거쳐 8번도시에 도착 2 6 4 3 11 1 ∞ 1 – 2 – 3 – 5 – 6 번 도시를 거쳐 8번도시에 도착

Thanks to Listening 정신없고 혼란스러워도 같이 할 친구가 있다면 그거 하나만으로도 만족한다.