Chapter 8 수송과 할당 CONTENTS 수송문제 할당문제 경유수송문제

Overview 수송문제 할당문제 경유수송문제 Ch.8 수송과 할당

8.1 수송문제 수송문제(transportation problem) 다수의 공급지와 다수의 수요지가 존재하는 상황에서 어떤 공급지에서 어떤 수요지로 얼마만큼의 물량을 이동시키는 것이 가장 좋을지를 결정하는 문제 수송문제를 해결하기 위한 세 가지 정보 𝑠 𝑖 : 공급지 𝑖의 공급능력 𝑑 𝑗 : 수요지 𝑗의 수요량 𝑐 𝑖𝑗 : 공급지 𝑖와 수요지 𝑗를 잇는 경로 상의 단위당 수송비용(혜택, 이익 등) 최적의 기준 수송비용의 최소화, 수송혜택의 최대화 등 Ch.8 수송과 할당

8.1 (1) 수송문제 익히기 김 부장은 자동차 타이어 생산업체인 한성타이어(주)의 물류책임자이다. [그림 8-1]에서 보는 바와 같이 한성타이어는 인천, 대전, 광주에 공장(□으로 표시)을 가지고 있고, 서울, 전주, 강릉, 대구, 부산에는 지역창고(○으로 표시)가 있다. 각 공장에서 각 지역창고로 타이어를 수송하는데 있어 한성타이어는 톤(1톤=1000kg)을 측정단위로 사용하고 있다. 한 공장에서 지역창고로 선적되는 타이어 1톤에는 한성타이어가 생산한 타이어들이 표준분류방식에 의해 취합되어 들어있다. Ch.8 수송과 할당

8.1 (1) 수송문제 익히기(계속) 수송표(transportation tableau) 행: 공급지를 나타냄. 수송표의 가장 우측 열은 공급지의 공급능력 열: 수요지를 나타냄. 수송표의 가장 아래 행은 수요지의 수요량 셀(cell): 공급지와 수요지를 잇는 경로. 셀 안에는 최적의 수송량 결정이 결정되어 표시됨 셀의 작은 박스 안의 숫자: 단위당 수송비용 Ch.8 수송과 할당

8.1 (1) 수송문제 익히기(계속) 네트워크 다이어그램(network diagram) 노드(node, 마디): 공급지와 수요지 등 지역을 나타냄 아크(arc, 화살표): 공급지와 수요지를 잇는 경로(path)를 나타냄 𝑐 𝑖𝑗 : 단위당 수송비용 𝐿 𝑖𝑗 : 이동물량의 하한값 𝑈 𝑖𝑗 : 이동물량의 상한값 𝑑 𝑗 : 수요량 𝑠 𝑖 : 공급능력 (공급량) Ch.8 수송과 할당

8.1 (1) 수송문제 익히기(계속) 의사결정변수 목적함수 제약조건 <공급지 제약 조건> <수요지 제약 조건> Ch.8 수송과 할당

8.1 (1) 수송문제 익히기(계속) 완성된 수송계획모형 모든 기술계수가 1인 특수한 형태의 선형계획모형 제약조건의 우변항이 모두 정수인 경우, 의사결정변수는 정수조건 없이 비음조건만 주어도 정수해만을 갖게 됨 Ch.8 수송과 할당

8.1 (1) 수송문제 익히기(계속) 해 찾기를 이용해 구한 최적해 결과 공장 1에서 180톤 생산  지역창고 1로 120톤, 지역창고 3으로 60톤 수송 공장 2에서 280톤 생산  지역창고 2로 100톤, 지역창고 4로 80톤 , 지역창고 5로 100톤 수송 공장 3에서 150톤 생산  지역창고 3으로 100톤, 지역창고 5로 50톤 수송  총수송비용 3,780(만원) 발생. 공급능력과 수요량을 만족시키면서 수송비용을 최소화 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류 균형수송문제(balanced transportation problems) 총공급량과 총수요량이 일치하는 문제 일반적으로 수송문제에서 공급지 제약조건은 ‘≤’, 수요지 제약조건은 ‘≥’로 두는 것을 추천하나 제약조건을 모두 등호로 바꾸어도 동일한 결과를 제공 균형수송문제에서 모든 제약조건은 최적해에서 속박적 제약조건(binding constraints)이 됨 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 불균형수송문제(unbalanced transportation problems) 1. 총공급량>총수요량 ▪ 특정 공급지의 공급량은 수요지로 이동하지 않고 남게 되는 현상 발생 공급지에서 보관비용, 재고비용 등이 발생하지 않는 경우: 기존의 방법과 동일하게 해를 구하고, 어느 공급지에서 얼마만큼의 물량이 이동되지 않느냐 하는 것은 공급지 제약조건의 여유분(slack)을 보고 판단함 보관비용, 재고비용 등이 발생하는 경우: 가상의 수요지(dummy demand point)를 추가하여 불균형수송문제를 균형수송문제로 변환한 후 해를 구함 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 불균형수송문제(unbalanced transportation problems) 2. 총공급량<총수요량 ▪ 수요량이 만족되지 않으므로 기존의 모형으로는 실행 불가능한 문제가 됨 ▪ 가상의 공급지(dummy supply point) 추가하여 불균형수송문제를 균형수송문제로 변환한 후 해를 구함 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 식수공급문제 두 곳의 저수지에서 세 곳의 도시에 식수를 공급하고 있다. 각 저수지에서는 일일 200(백만)리터씩 식수를 공급할 수 있다. 각 도시에서는 식수를 일일 150(백만)리터씩은 받아야 한다. 각 도시에서 필요한 양만큼 식수를 공급받지 못할 경우에는 시민들에게 충분한 물을 공급하지 못함으로 인해서 여러 가지 민원이 제기되는 바, 이러한 불편함을 각 도시에서는 수치로 평가하였다. 즉, 충족되지 않은 식수 1(백만)리터에 대해서 식수부족비용이 발생하는데 도시 1에서는 백만리터당 2만원, 도시 2에서는 2만2천원, 도시 3에서는 2만3천원으로 추정하고 있다. 두 곳의 저수지에서 세 곳의 도시로 식수를 어떠한 방법으로 공급하는 것이 총수송비용과 식수부족 비용의 합을 최소화할 수 있는가? 각 공급지에서 각 수요지로의 단위당 수송비(단위: 천원)는 다음의 수송표에 나타나 있다. Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 총수요량이 총공급량을 50(백만)리터 초과 가상의 공급지를 추가 가상의 공급지의 공급량: 총수요량의 초과분 50(백만)리터 가상의 공급지(저수지 3)의 단위당 수송비용: 식수부족비용 가상의 공급지에서 어떤 도시로 식수가 공급된다는 말은 해당 도시에서 그만큼의 식수를 받지 못한다는 의미임 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 의사결정변수 완성된 선형계획모형 Ch.8 수송과 할당

8.1 (2) 수송문제의 종류(계속) 해 찾기 결과 저수지 1  도시 1로 100(백만)리터, 도시 2로 100(백만)리터 공급 저수지 2  도시 2로 50(백만)리터, 도시 3으로 150(빅만)리터 공급 가상의 저수지  도시 1로 50(백만)리터 공급  도시 1의 수요량 부족분  식수공급비용(수송비용+식수부족비용)은 4,050천원으로 최소화됨 Ch.8 수송과 할당

8.2 할당문제 할당문제(assignment problems) 여러 개의 작업과 여러 명의 작업자가 있는 상황에서 어떤 작업을 어떤 작업자에게 할당(1:1 할당)할 지를 결정하는 문제 모든 공급량과 모든 수요량이 1인 특수한 형태의 수송문제 의사결정변수(모형의 특이성으로 인해 이진변수로 지정하지 않아도 0 또는 1의 값만을 갖게 됨) 목적함수: 할당을 통해 얻게 되는 혜택의 최대화 제약조건 Ch.8 수송과 할당

8.2 할당문제(계속) 할당문제(assignment problems) 특수한 형태의 수송문제로 0-1 정수조건이 필요 없음 완성된 할당모형 균형할당문제: 공급지(작업자)의 수 = 수요지(작업)의 수 불균형할당문제: 공급지(작업자) 수 ≠ 수요지(작업) 수 작업자의 수 > 작업의 수: 가상의 작업 추가 작업자의 수 < 작업의 수: 가상의 작업자 추가 Ch.8 수송과 할당

8.2 (1) 균형할당문제 쏠로결혼정보 <사단법인>쏠로결혼정보는 농촌총각과 도시처녀를 짝 지워주는 일을 하는 공익단체이다. 오늘 이 결혼정보에서는 농촌에서 올라온 4명의 총각(홍길동, 임꺽정, 일지매, 변강쇠)과 서울의 한 회사에 근무하는 4명의 처녀(성춘향, 심청이, 황진이, 어우동)를 매치시켜 주려고 한다. <표 8-4>에 나타난 수치는 각 남녀의 신상명세서를 컴퓨터가 입력하여 나타낸 ‘행복도’이다. 행복도는 1에서 9까지 척도로 측정되는 데 큰 숫자일수록 둘이 매치되었을 경우 훗날 결혼 가능성이 많음을 의미한다. 예를 들면, 홍길동과 심청이와의 행복도는 4이며, 일지매와 황진이의 행복도는 6이다. 규정에 의하면 한 총각이 두 처녀 이상과 매치될 수 없으며, 그 역도 마찬가지이다. 쏠로결혼정보는 전체의 행복도를 극대화시키기 위한 총각과 처녀의 매치 방안을 마련하고자 한다. 쏠로결혼정보는 경영과학 지식이 있는 여러분의 도움을 필요로 하고 있다. Ch.8 수송과 할당

8.2 (1) 균형할당문제(계속) 의사결정변수(총각을 공급지, 처녀를 수요지로 가정) 목적함수(전체 행복도의 극대화) 제약조건 <공급지 제약 조건> <수요지 제약 조건> Ch.8 수송과 할당

8.2 (1) 균형할당문제(계속) 완성된 할당모형 Ch.8 수송과 할당

8.2 (1) 균형할당문제(계속) 해 찾기 결과 (총각 1, 처녀 3), (총각 2, 처녀 1), (총각 3, 처녀 2), (총각 4, 처녀 4)로 매치 전체 행복도는 31로 최대화 Ch.8 수송과 할당

8.2 (2) 불균형할당문제 서경회계법인 회계법인에서 흔히 발생하는 문제는 어떻게 하면 인력을 효율적으로 이용하느냐이다. 특히 대부분의 기업들이 연말결산을 시작하려는 시점에서 회계법인은 효율적인 고객관리 일정을 반드시 수립해야 한다. 다음의 예에서 우리는 작업시간의 최소화를 꾀하면서 주어진 회계업무를 성공적으로 수행하게끔 공인회계사들을 고객에게 할당하는 문제를 다루고자 한다. 서경회계법인은 세 곳의 고객으로부터 결산작업을 요청받았다. 서경회계법인은 소속 회계사들의 작업일정을 검토한 후에 홍길동, 임꺽정, 장보고, 박문수 등 4명의 회계사를 요청받은 결산작업에 투입할 수 있다고 판단하였다. 하지만 이 4명의 회계사도 작업이 밀려있는 관계로 각 회계사는 기껏해야 한 고객만을 상대할 수 있다. 4명의 회계사는 경험과 능력에 개인차가 있어 업무처리시간에도 차이가 존재한다. 과거의 업무처리시간을 근거로 하여 서경회계법인은 <표 8-5>와 같이 고객이 요청한 업무에 대한 4명 회계사의 작업시간을 추정하였다. Ch.8 수송과 할당

8.2 (2) 불균형할당문제(계속) 의사결정변수 여기서 고객 4는 가상의 고객 완성된 할당모형 Ch.8 수송과 할당

8.2 (2) 불균형할당문제(계속) 해 찾기 결과 (회계사 1, 고객 1), (회계사 2, 고객 3), (회계사 3, 가상의 고객), (회계사 4, 고객 2)로 할당, 총작업시간 580시간으로 최소화 회계사 3에게는 고객이 할당되지 않음 Ch.8 수송과 할당

8.2 (2) 불균형할당문제(계속) 서경회계법인문제(불균형할당문제) 회계사가 고객을 할당 받지 못할 때 발생하는 벌칙비용이 없으므로 균형할당문제로 전환하지 않고도 동일한 해를 구할 수 있음 대안적 할당모형 Ch.8 수송과 할당

8.2 (2) 불균형할당문제(계속) 대안적 최적해 찾기 결과 공급지 제약조건의 여유분이 1인 회계사가 고객을 할당 받지 못함을 의미 [그림 8-6]의 최적해 결과와 동일하게 회계사 3에게 고객이 할당되지 않음 Ch.8 수송과 할당

8.3 경유수송문제 경유수송문제(transshipment problems) 공급지와 수요지 사이에 경유지가 존재하는 수송문제 어떤 공급지에서 어떤 경유지를 거쳐 어떤 수요지로 얼마만큼의 물량을 이동시키는 것이 가장 좋은가? 경유지(transshipment points): 물량이 잠시 머무는 곳 예: 세관의 보세창고 경유지에서는 일반적으로 생산이나 소비가 일어나지 않음 특정 경유지로 유입된 물량의 합 = 해당 경유지에서 유출되는 물량의 합 Ch.8 수송과 할당

8.3 경유수송문제(계속) 경유수송문제의 의사결정변수는? 𝑿 𝒊𝒌𝒋 : 공급지 𝒊에서 경유지 𝒌를 거쳐 수요지 𝒋로 이동하는 물량? 잘못된 의사결정변수 다수의 공급지에서 특정 경유지로 들어온 물량이 다시 다수의 수요지로 분산 이동되어야 함을 간과함 올바른 의사결정변수 Ch.8 수송과 할당

8.3 경유수송문제(계속) 경유수송문제의 목적함수 및 제약조건 목적함수, 공급지 제약조건, 수요지 제약조건은 수송문제와 동일함 경유지 𝒊의 제약조건 이동되는 제품이 식품이나 생명체일 경우의 경유지 제약조건 식품: 이동 기간 동안 상하여 제품의 20%가 가치 상실하는 경우 생명체: 이동 기간 동안 번식하여 개체수가 20% 늘어나는 경우 Ch.8 수송과 할당

8.3 경유수송문제(계속) M 전자회사의 경유수송문제 미국 전역에 판매망을 갖춘 M전자는 주문자 상표부착 방식(OEM: original equipment manufacturing)으로 TV를 해외에 주문하여 미국 시장에 판매하는 회사이다. M전자는 세 곳의 해외 제조업체로부터 납품을 받아 네 곳의 미국 도시에 판매를 하고 있다. 해외 제조업체들은 M사의 제품명세서에 따라 TV를 제조하고 M사의 상표를 부착한 다음 M사로 TV를 납품한다. [그림 8-10]은 생산지에서 수요지까지의 제품흐름을 네트워크 다이어그램으로 표현하고 있다. 제품의 흐름을 설명하면 다음과 같다. •M전자회사는 도쿄, 타이페이, 그리고 홍콩에 있는 제조업체로부터 TV를 납품받는다. •M 전자회사는 시애틀과 LA에 있는 선박회사와 TV 운송계약을 맺는다. 운송 단위는 콘 테이너로 콘테이너 한 대에는 1000대의 TV가 선적된다. 선박 회사는 콘테이너를 생산 지에서 시애틀과 LA에 있는 하역창고로 해상 운송한다. •콘테이너가 하역되어 통관절차를 마치면 이것은 트럭으로 M전자회사의 TV 판매거점 인 시카고, 뉴욕, 애틀란타, 그리고 달라스로 육상 운송된다. Ch.8 수송과 할당

8.3 경유수송문제(계속) 이 회사의 물류책임자인 피터 박은 향후 1사분기 동안 각 판매거점의 수요를 만족시키면서 수송비용을 최소화하는 가장 효율적인 운송계획을 수립하고자 한다. 향후 1사분기동안 공급지의 생산량, 해상 및 육상 운송비용, 선적량의 상한선과 하한선, 판매거점의 수요량 등의 자료가 <표 8-6>에 요약되어 있다. <표 8-6>의 선적량 정보에서 ‘~’는 상한선이나 하한선이 없음을 나타낸다. 주어진 정보를 이용하여 총수송비용을 최소화할 수 있는 물류 방안을 제시하라. Ch.8 수송과 할당

8.3 경유수송문제(계속) Ch.8 수송과 할당

8.3 경유수송문제(계속) 의사결정변수 목적함수 Ch.8 수송과 할당

8.3 경유수송문제(계속) 제약조건 <공급지 제약 조건> <수요지 제약 조건> <경유지 제약 조건> <선적량 상한선/하한선 제약 조건> Ch.8 수송과 할당

8.3 경유수송문제(계속) 완성된 선형계획모형 Ch.8 수송과 할당

8.3 경유수송문제(계속) 최적해 결과 <공급지  경유지> 공급지 1  경유지 1로 20개, 경유지 2로 5개 콘테이너 수송 공급지 2  경유지 1로 17개, 경유지 2로 12개 콘테이너 수송 공급지 3  경유지 1로 7, 경유지 2로 9개 콘테이너 수송 Ch.8 수송과 할당

8.3 경유수송문제(계속) 최적해 결과 <경유지  수요지> 경유지 1  수요지 1로 8개, 수요지 2로 23개, 수요지 3으로 8개, 수요지 4로 5개 수송 경유지 2  수요지 1로 11개, 수요지 2로 1개, 수요지 3으로 9개, 수요지 4로 5개 수송 ▪ 총수송비용은 201만4천달러로 최소화됨 Ch.8 수송과 할당