수송모형의 특성 수송모형의 해법 수송모형의 응용 중개수송모형 할당모형 제6장 수송모형과 할당모형 경영과학(Ⅰ) 제6장 수송모형과 할당모형 수송모형의 특성 수송모형의 해법 수송모형의 응용 중개수송모형 할당모형 secom.hanbat.ac.kr

▶ 수송모형의 특성 일반적인 심플렉스법이 아닌 고유한 해법을 사용하여 최적해 도출 수송모형(transportation model) : 공급지와 수요지 사이의 총수송비용을 최소로 하는 수송량 결정 문제 할당모형(assignment model ; 짝짓기 문제 혹은 배정문제) 공급지의 수와 수요지 수가 동일 각 공급지와 수요지의 공급량 및 수요량이 모두 1임 중개수송모형(transshipment model) : 공급지와 수요지 사이에 창고와 같은 중간 경유지가 있는 형태의 수송모형 형태상 네트워크 모형(network model)의 일종

▶ 수송모형의 특성 ◁ 수송문제의 일반적 형태 ▷ C11 X11 공급량 수요량 1 1 a1 b1 ： ： 공 급 지 수요 지 ◁ 수송문제의 일반적 형태 ▷ C11 X11 공급량 수요량 1 1 a1 b1 ： ： 공 급 지 수요 지 ai i Cij Xij j bj ： ： am m n bn Cmn Xmn

▶ 수송모형의 특성 <일반적인 선형계획모형으로의 수식화> 제약조건 (i) 각 공급지의 공급능력 제약         X11 + … + X1j  + … + X1n ≤ a1           ：        Xi1 + …  + Xij  + …  + Xin  ≤ ai        Xm1 + … + Xmj + … + Xmn ≤ am 변수 : Xij ＝ 공급지 i에서 수요지 j로 수송할 수송량 목적함수(총수송비용의 최소화) Min. Z = C11X11 + … + CijXij + … + CmnXmn

▶ 수송모형의 특성 <일반적인 선형계획모형으로의 수식화> 불균형수송모형 (unbalanced transportation model) : 균형수송문제로 바꾸어야만 수송심플렉스법 적용 가능 공급량이 더 많으면 가수요지(假需要地) 도입 수요량이 더 많으면 가공급지(假供給地) 도입 (ⅱ) 각 수요지의 수요량 제약        X11 + … + Xi1 + … + Xm1  ≥ b1           ：        X1j  + … + Xij  + … + Xmj   ≥ bj        X1n + … + Xin + … + Xmn  ≥ bn 균형수송모형(balanced transportation model) ☞ 총공급량과 총수요량이 동일

▶ 수송모형의 해법 일반적인 수송표 수요지 공급지 1 … j n 공급량 a1 ： i Xij ai m am 수요량 b1 bj bn Cij

▶ 수송모형의 해법 수송심플렉스법의 절차 3단계 : 최적해인지 검토하여 아니면 해를 개선한다 (새수송표 작성)   ☞ 해의 검토와 개선을 위한 방법 : 디딤돌법, 수정배분법 1단계 : 균형수송문제인지를 확인하고 수송표를 만든다.    ☞ 불균형수송문제이면 가공급지나 가수요지를 도입 2단계 : 초기해를 구한다.    ☞ 초기해를 구하는 방법 : 북서코너법, 최소비용법, 보겔근사법

▶ 수송모형의 해법 예제 모형 : C전자회사의 제품 수송문제 공장의 공급량 : 800, 600, 400 대리점의 수요량 : 700, 500, 400, 200 제품단위당 수송비(단위 : 천원) 대리점 공장 가 나 다 라 1 3 4 9 2 7 6 5 8

▶ 수송모형의 해법 C전자회사의 수송표 대리점 공장 가 나 다 라 공급량 1 3 X11 4 X12 9 X13 2 X14 800 7 X21 6 X22 X23 X24 600 X31 5 X32 X33 8 X34 400 수요량 700 500 200 1,800

▶ 수송모형의 해법 ◁ 초기해를 구하는 방법 ▷ m개의 공급지와 n개의 수요지가 있는 경우, ☞기저변수(할당되는 경로)의 수는 m+n-1 개로 유지되어야 함 북서코너법(northwest corner method) 최소비용법(least cost method) 보겔근사법(Vogel's approximation method)

▶ 수송모형의 해법 북서코너법 수송표의 왼쪽 상단부터 공급량과 수요량에 맞게 수송량 배정 북서코너법에 의한 초기해 대리점 공장 가 나 다 라 공급량 1 3 700 4 100 9 2 800 7 6 400 200 600 5 8 수요량 500 1,800 초기 수송비용 : 3×700 + … + 8×200 = 7,500(천원)

▶ 수송모형의 해법 최소비용법 여러 수송경로 중에서 가장 작은 비용을 갖는 경로부터 우선적으로 수송량을 배정 3. 1, 2를 반복하여 하나의 행이나 열이 남으면 공급량과 수요량에 맞게 나머지를 배정한다 1. 현재의 수송표에서 최소비용을 갖는 칸에 최대한의 양을 배정한다. 2. 공급량과 수요량을 수정하되, 남은 양이 0이면 그 행이나 열을 지운다. 만약 행과 열이 동시에 0이 되면 임의로 하나만 지우고, 다른 하나는 남은 양을 0으로 둔다. <배정방법>

▶ 수송모형의 해법 최소비용법에 의한 초기해 대리점 공장 가 나 다 라 공급량 1 3 300 4 9 2 200 800 7 6 400 600 5 8 수요량 700 500 1,800 총수송비용 :3×300 + … 1×400 = 4,500

▶ 수송모형의 해법 보겔근사법 상대적인 비용 (기회비용)의 개념을 도입 최선의 수송경로를 선택하지 못할 때 생기는 상대적 손실 고려 1. 각 행과 열에 대해 기회비용을 구한다. 기회비용 = 각 행, 열에 가장 작은 비용과 그 다음 작은 비용과의 차 <보겔근사법의 과정> 4. 1, 2, 3을 반복하여 하나의 행이나 열이 남게 되면 공급량과 수요량에 맞게 나머지를 배정한다. 2. 가장 큰 기회비용을 갖는 행(열)의 가장 작은 비용을 갖는 칸에 최대한 많은 양을 배정한다. 3. 공급량과 수요량을 수정하되, 남은 양이 0이면 그 행(열)을 지운다. 만약 동시에 0이 되면 하나만 지우고, 다른 하나는 0으로 둔다.

▶ 수송모형의 해법 보겔근사법의 첫 번째 수송표 대리점 공장 가 나 다 라 공급량 행기회비용 1 3 4 9 2 800 1 2 7 6 1 3 600 2 3 1 400 5 4 8 400 3(선택) 수요량 700 (300) 500 400 200 1,800 열기회비용 2 1 3 1

▶ 수송모형의 해법 보겔근사법의 두 번째 수송표 대리점 공장 가 나 다 라 공급량 행기회비용 1 3 4 9 2 800 7 6 400 600 (200) 5 8 3(선택1) 수요량 700 (300) 500 200 1,800 열기회비용 8 (선택)

▶ 수송모형의 해법 보겔근사법의 세 번째 수송표 대리점 공장 가 나 다 라 공급량 행기회비용 1 3 300 4 9 2 800 7 6 400 600 (200) 5 8 3(선택1) 수요량 700 (300) 500 200 1,800 열기회비용 4 (선택3) 8 (선택2)

▶ 수송모형의 해법 보겔근사법의 네 번째 수송표 대리점 공장 가 나 다 라 공급량 행기회비용 1 3 300 4 9 2 800 7 6 400 200 600 (200) 3(선택4) 5 8 3(선택1) 수요량 700 (300) 500 1,800 열기회비용 4 (선택3) 8 (선택2)

▶ 수송모형의 해법 보겔근사법의 의한 최종해 대리점 공장 가 나 다 라 공급량 1 3 300 4 500 9 2 800 7 6 800 7 6 400 200 600 5 8 수요량 700 1,800 총수송비용 : 3×300 + … 1×400 = 4,300

▶ 수송모형의 해법 ◁ 수정배분법 : 최적여부 검사 및 해의 개선 ▷ 수정배분법의 절차 1단계 : 최적여부 검사 ◁ 수정배분법 : 최적여부 검사 및 해의 개선 ▷ 수정배분법의 절차 1단계 : 최적여부 검사 각 공급지와 수요지의 제약식에 상응하는 쌍대변수를 각각 Ui, Vj 기저변수(수송량 배정) Xij에 대해, Ui + Vj = Cij 이용하여 Ui, Vj 계산 비기저변수(배정안된 변수)의 수정비용, Dij = Cij - (Ui + Vj) 계산 이 값들이 모두 음수가 아니어야만 최적해를 얻는다. 2단계 : 진입변수 결정 위의 Dij 값 중 가장 작은 음수(절대값이 가장 큰 음수)는 변수 선택

▶ 수송모형의 해법 3단계 : 탈락변수 결정 진입변수로부터 시작하여 기저변수들을 경유하여 제자리에 되돌아오는 폐쇄고리를 형성 폐쇄고리에 속한 변수들에 대해 출발점으로부터 교대로 수송량의 증가와 감소를 표시 감소에 해당하는 값 중 가장 작은 값을 갖는 변수를 탈락 그 값을 조정수송량으로 결정 4단계 : 해의 개선 형성된 폐쇄고리에 대해 3단계에서 정한 조정수송량을 진입변수 에서 출발하여 교대로 증가ㆍ감소시키고, 최적해가 얻어질 때까지 위 과정을 반복한다.

▶ 수송모형의 해법 C전자회사 문제의 경우 U1 = 0 → V1=3, V2= 4, V4=2 V1 = 3 → U3 = -2, V2 = 4 → U2 = 2 ⇒ V3 = -1 대리점 공장 가 나 다 라 공급량 Ui 1 3 300 4 9 (10) 2 200 800 7 (2) 6 400 (-1) 600 5 (3) (7) 8 (8) -2 수요량 700 500 1,800 Vj -1

▶ 수송모형의 해법 대리점 공장 가 나 다 라 공급량 Ui 1 3 300 4 + 9 (10) 2 - 200 800 2 7 표에서 (2, 라)칸, 즉, X24의 수정비용이 음수 → 현재의 해는 최적이 아님 이를 중심으로 폐쇄고리 형성 : X24 → X22 → X12 →X14 → X24 X22, 와 X14 의 값이 200으로 동일 → 이 값을 교대로 증감시켜 해를 개선 대리점 공장 가 나 다 라 공급량 Ui 1 3 300 4 + 9 (10) 2 - 200 800 2 7 (2) 6 - 400 3 + (-1) 600 5 (3) 4 (7) 8 (8) -2 수요량 700 500 1,800 Vj -1

▶ 수송모형의 해법 대리점 공장 가 나 다 라 공급량 Ui 1 3 300 4 500 9 (9) 2 800 7 (3) 6 (1) 수정배분법에 의해 개선된 해(최적해) 대리점 공장 가 나 다 라 공급량 Ui 1 3 300 4 500 9 (9) 2 800 7 (3) 6 (1) 400 200 600 5 (6) 8 (8) -2 수요량 700 1,800 Vj

▶ 수송모형의 해법 ◁ 불균형수송모형 ▷ 공급량이 수요량보다 많은 경우 예제 모형 : E식품회사의 청량음료 수송문제 대리점 ◁ 불균형수송모형 ▷ 공급량이 수요량보다 많은 경우 예제 모형 : E식품회사의 청량음료 수송문제 생산공장의 일간 생산량 : 700, 800, 1200(상자) 판매대리점에서 요구하는 양 : 900, 700, 400, 500(상자) 상자당 수송비(단위 : 만원) 대리점 공장 1 2 3 4 8 9 11 16 12 7 5 14 10 6

E식품회사의 초기 수송표(공급초과의 경우) ▶ 수송모형의 해법 총공급량(2,700)이 총수요량(2,500)보다 크므로 가수요지 도입 E식품회사의 초기 수송표(공급초과의 경우) 대리점 공장 1 2 3 4 가상 대리점 공급량 8 9 11 16 700 12 7 5 800 14 10 6 1,200 수요량 900 400 500 200 2,700 각 공장에서 가상대리점으로의 수송비용은 0으로 취급 만약 각 공장에서 공급하지 못한 양에 대한 보관비용이 있거나, 보관에 따른 제약이 존재한다면 수송비용은 그에 맞게 조정

▶ 수송모형의 해법 E식품회사의 문제의 최적 수송표 대리점 공장 1 2 3 4 가상 대리점 공급량 8 700 9 11 16 12 100 7 5 800 14 10 6 400 500 200 1,200 수요량 900 2,700

▶ 수송모형의 해법 E식품회사의 최적 수송계획 대리점 공 장 <수요량> <생산량> 700 1 900 100 700 2 700 800 2 100 3 400 400 1,200 (200) 3 4 500 500 총수송비용 : 3×700 + … + 8×500 = 12,700(만원) 3번 공장의 경우, 1,200상자 생산, 1, 3, 4번 대리점에 100, 400, 500 상자 공급 → 200상자는 공장에 보관

▶ 수송모형의 해법 수요량이 공급량보다 많은 경우 예제 모형 앞의 E식품회사 예제에서 대리점 3의 수요량이 900으로 증가 예제 모형   앞의 E식품회사 예제에서 대리점 3의 수요량이 900으로 증가 각 대리점에서는 필요한 양을 확보하지 못하게 될 때 상자당 9, 10, 8, 15의 부족비용이 발생하게 되는 경우 ☞ 가상공장(가공급지)을 도입하고 각 대리점의 부족비용을 수송비용으로 취급

E식품회사의 초기 수송표(수요초과의 경우) ▶ 수송모형의 해법 E식품회사의 초기 수송표(수요초과의 경우) 대리점 공장 1 2 3 4 공급량 8 9 11 16 700 12 7 5 800 14 10 6 1,200 가상공장 15 300 수요량 900 500 3,000

▶ 수송모형의 해법 E식품회사의 최적 수송표 대리점 공장 1 2 3 4 공급량 8 700 9 11 16 12 7 600 5 200 800 14 10 6 500 1,200 가상공장 100 15 300 수요량 900 3,000 1, 2번 대리점은 200, 100상자씩 제품 공급 부족 총비용은 21,300(공급부족에 따른 비용 : 9×200 + 10×100 = 2,800 총수송비용 : 8×700 + … + 7×500 = 18,500)

▶ 수송모형의 응용 예제 모형 : S섬유의 의복 생산 및 재고관리 계획(총괄생산계획) 연중생산량을 평준화 : 비수기에 수요량보다 다소 많이 생산 <분기당 생산능력 및 연간수요와 의복 1벌당 생산비용> 1사분기 2사분기 3사분기 4사분기 생산능력 9,000 8,000 예상수요 6,000 4,000 12,000 단위생산비용(만원) 10 12 ► 분기 이월시, 단위당 재고비용 = 1(만원), 연도 이월 불가 ► 연간 총생산능력=35,000, 예상총수요 =31,000 → 공급량이 수요량을 초과하는 불균형수송문제

▶ 수송모형의 응용 S섬유회사 문제의 초기 수송표 10 11 12 13 9,000 M 8,000 수요량 6,000 4,000 수요기간 생산기간 1사분기 2사분기 3사분기 4사분기 가수요 생산능력 10 11 12 13 9,000 M 8,000 수요량 6,000 4,000 12,000 35,000

▶ 수송모형의 응용 S섬유회사 문제의 최적 수송표 10 6,000 11 12 13 3,000 9,000 M 4,000 수요기간 생산기간 1사분기 2사분기 3사분기 4사분기 가수요 생산능력 10 6,000 11 12 13 3,000 9,000 M 4,000 8,000 5,000 1,000 예상수요 12,000 35,000

▶ 수송모형의 응용 S섬유회사의 최적 생산 및 재고계획 1사분기의 수요량 6,000벌은 1사분기에서 전량 생산하여 공급 2사분기는 수요량은 4,000이지만 8,000을 생산, → 4,000벌을 3사분기의 수요에 충당 3사분기에도 8,000벌을 생산 → 그 중 3,000 벌은 4사분기 수요를 위해 이월 4사분기에는 생산능력대로 9,000벌을 생산 → 3사분기의 재고량과 함께 수요 충당 총괄생산계획하에서 예상되는 총비용 : 351만원

▶ 중개수송모형 공급지와 수요지 사이에 중간경유지가 있는 수송모형 예제 모형 : R전자회사의 수송문제    예제 모형 : R전자회사의 수송문제 공장과 대리점 사이에 2곳의 창고 운영 R전자회사의 수송문제 자료(금액단위 : 천원) 중간창고 공장 3 4 공급량 1 20 30 600 2 10 400 대리점 중간창고 5 6 7 8 3 20 60 30 4 40 50 수요량 200 150 350 300

▶ 중개수송모형 네트워크 모형으로 표현한 R전자회사의 문제 공 장 대리점 <수요량> <생산량> 20 20 5 200 600 1 3 60 30 30 6 60 150 30 40 40 7 350 400 2 4 60 10 8 50 300 R전자회사의 중개수송모형

▶ 중개수송모형 ◁ 세가지방법 ▷ 일반적인 선형계획법 문제로 수식화하여 푸는 방법 보통의 수송모형으로 변환시켜 푸는 방법 ◁ 세가지방법 ▷ 일반적인 선형계획법 문제로 수식화하여 푸는 방법 중간창고에 대한 두 제약식 추가    -중간창고 3 : X13 + X23 = X35 + X36 + X37 + X38     -중간창고 4 : X14 + X24 = X45 + X46 + X47 + X48 보통의 수송모형으로 변환시켜 푸는 방법 공급지에서 수요지로 직접 수송이 이루어지는 보통의 수송모형으로 변형시킨 다음 수송심플렉스법 적용 직접 수송심플렉스법을 적용하는 방법 중간창고가 수요지로서의 역할과 공급지로서의 역할을 동시에 수행하므로 수송표의 공급지와 수요지에 모두 포함 공급량과 수요량은 총공급량 (= 총수요량) 공장에서 대리점으로 직접 수송할 수 없으므로 비용을 'M'으로 표시

▶ 중개수송모형 첫번째 방법에 의한 해 공 장 대리점 <수요량> <생산량> 200 600 5 200 1 3 350 6 50 150 150 7 350 400 400 2 4 250 8 300 R전자회사의 최적 수송계획

▶ 중개수송모형 두번째 방법 : 보통의 수송모형으로 변환시킨 그림 대리점 공 장 <수요량> <생산량> 40(창고3) 5 200 600 1 20(창고4) 50(창고3) 80(창고4) 6 150 50(창고3) 7 350 50(창고4) 400 2 60(창고3) 8 300 60(창고4) R 전자회사 문제의 변형된 수송모형

▶ 중개수송모형 변형된 R전자회사 문제의 최적 수송표 대리점 공장 5 6 7 8 공급량 1 40 200 70 50 350 80 예) 공장 1에서 대리점 5로 가는 방법 중간창고 3을 거치면 수송비용 : 20 +20 = 40 중간창고 4를 거치면 30 +40 = 70 따라서 중간창고 3을 거치는 수송경로만 고려 수송심플렉스법 적용 결과, 다음의 최적 수송표를 얻음 변형된 R전자회사 문제의 최적 수송표 대리점 공장 5 6 7 8 공급량 1 40 200 70 50 350 80 600 2 150 60 250 400 수요량 300 1,000

▶ 중개수송모형 세번째 방법 : 직접 수송심플렉스법을 적용한 결과 R전자회사 문제의 최적 수송표 수요지 공급지 중간 창고3 창고4 대리점5 대리점6 대리점7 대리점8 공급량 공장1 20 600 30 M 공장2 10 400 중간창고3 200 60 350 50 1,000 중간창고4 40 150 250 수요량 300 3,000

▶ 할당모형 전형적인 할당모형의 예 작업자와 작업 또는 기계의 할당 문제 판매원과 판매지역의 배정 연구부서와 연구과제의 배정 문제 할당모형 고유의 해법 : 헝가리법(Hungarian method)   예제 모형 : S기업의 연구과제 배정문제 한 연구소에서 하나의 과제만을 수행해야 함 연구과제별 연구비신청액(단위 : 천만원) 연구과제 연구소 A B C D 가 1 4 6 3 나 9 7 10 다 5 11 라 8

▶ 할당모형 헝가리법의 절차 4단계 : 직선의 수와 행(열)의 수가 같으면 최적할당을 시작 ► 하나의 0을 포함하는 행(열)이 있으면 그 칸에 우선적으로 배정 ► 나머지 행(열)에 대해서는 두 칸이 동시에 배정되지 않도록 할당 1단계 : 각 행과 열에 대하여 기회비용표를 작성한다. ☞기회비용 = 각 칸의 비용과 그 행(열)의 가장 작은 비용과의 차이 2단계 : 각 행(열)에 대해 기회비용의 값이 0인 칸을 모두 지울 수 있는 최소 직선 수와 행(열)의 수를 비교 → 그 수가 같으면 4단계로 3단계 : 직선의 수가 행(열)의 수보다 작으면 기회비용표를 수정 ► 직선으로 지워지지 않은 칸들의 값 중 최소값을 찾음 ► 직선이 지나지 않는 칸은 그 값을 빼주고, 직선의 교차점에는 더해준 다음 2단계로 돌아간다.

▶ 할당모형 S기업 문제에 대한 기회비용표 연구과제 연구소 A B C D 가 3 2 나 다 1 4 라 3 2 나 다 1 4 라 헝가리법의 2단계 적용 결과 연구과제 연구소 A B C D 가 3 2 나 다 1 4 라 0을 지우는 최소직선의 수가 3개로 행(열)의 수 4보다 작음

▶ 할당모형 헝가리법의 3단계 적용 결과 연구과제 연구소 A B C D 가 2 1 나 3 다 라 4 S기업문제의 최적할당 결과 2 1 나 3 다 라 4 최소 직선의 수가 4개이므로 최적할당을 시작 첫 번째 행과 4번째 열이 하나의 0만을 포함하고 있으므로 우선 배정 S기업문제의 최적할당 결과 연구과제 연구소 A B C D 가 2 1 나 3 다 라 4

▶ 할당모형 ◁ 할당모형의 두가지 특수한 경우 ▷ S기업의 최적 배정정책  :  -연구과제 A - 가 연구소     -연구과제 B - 다 연구소     -연구과제 C - 나 연구소     -연구과제 D - 라 연구소 연구비 총지출액은 21(천만원)이지만 기회비용은 0이다. ◁ 할당모형의 두가지 특수한 경우 ▷ 두 집단의 크기가 다른 경우(불균형할당모형) ► 수가 적은 쪽에 가상의 개체를 도입하여 균형할당모형으로 만듬 ► 최적할당정책을 구하여 가상의 개체와 짝이 된 개체는 실제로는 아무 것도 할당되지 않는 것으로 처리 두 집단의 어느 특정한 조합은 짝이 될 수 없는 경우 ► 수송모형에서 차단경로를 설정한 것과 같은 경우 ► 해당 칸의 비용을 임의의 큰 수 'M' 으로 할당하여 해를 구함

경영과학(Ⅰ) 제6장 수송모형과 할당모형 수고하셨습니다…