Ck601 Chap05

예제5-1 S실업에서는 급증하는 인건비와 물류비용의 문제를 해결하기 위하여 기존에 있는 국내 공장(S1)의 생산규모를 줄이고 해외에 매달 1,000롯트를 생산할 수 있는 제2공장(S2)과 2,000롯트를 생산할 수 있는 제3공장(S3)을 설립하여 4개의 해외현지법인(D1, D2, D3, D4)으로 수출하고 있다. 이들 현지법인의 매달 평균수요는 각각 1,100롯트, 1,300롯트, 1,700롯트, 1,400롯트로서 총 5,500롯트이다. 현재는 수출책임자 임의로 해외공장의 제품을 우선적으로 공급하고 나머지는 국내 생산품으로 수요를 맞추어 주고 있다. 최근에 경영합리화를 위한 일환으로 새로운 방법으로 공급체계를 구축하고자 각 공장의 생산원가, 현지법인까지의 수송비 및 기타 부대비용을 합쳐 설정한 롯트당 수요지 도착원가는 다음과 같다.

1) 비용을 최소화하는 공급체계는 무엇이며, 비용은 얼마인가? 2) 예상되는 D2 수요의 변화가 공급방법과 비용에 어떤 영향을 미치는가?

수송문제기법의 필요성 S실업의 비용절감의 문제는 다수의 공급지(source)에서 다수의 수요지 또는 목적지(destination)로 물품이나 용역을 제공하는 조직체가 공통적으로 겪는 문제이다. 이 문제는 선형계획모형으로 구축하여 해결할 수 있다. 이러한 문제를 해결하는 데 선형계획법을 이용하지 않는 이유는 적합하지 않아서가 아니라 보다 간단한 방법인 수송문제기법으로 해를 구할 수 있기 때문이다.

수송문제의 시작과 공헌자 수송문제의 원천은 George Dantzig가 선형계획법을 개발하기에 앞서 Frank L. Hitchcock이 1941년에 발표한 “The Distribution of a Product from Several Sources to Numerous Localities”라는 연구논문이라고 하겠다. 이와는 별도로 1975년 노벨상 경제학 부문 수상자인 T. C. Koopmans가 1947년에 발표한 “Optimum Utilization of the Transportation System”의 연구논문 또한 이 분야의 발전에 크게 기여하였다. 그 후 Dantzig를 비롯하여 A. Charnes, W. Cooper, W. Vogel, E. Russel등이 수송문제의 해를 구하는 연산기법의 개발에 크게 공헌하였다.

수송문제의 LP모형 결정변수

목적함수

균형수송문제 S실업의 문제와 같이 총 공급량과 총 수요량이 같은 문제를 균형수송문제(均衡輸送問題;balanced transportation problem)라고 한다. 균형수송문제의 경우에는 다음의 수식이 성립한다. 위의 관계로 인하여 m+n개의 제약조건 중에서 (m+n-1)개의 제약조건을 충족하면 나머지 하나는 자동적으로 충족된다. 이는 m+n개의 제약조건이 선형독립관계를 유지하지 못한다는 것을 의미한다. 따라서 실질적으로 목적함수를 제약하는 제약조건의 수는 (m+n-1)개이고 나머지 하나는 중복된 제약조건이 된다.

수송문제의 해법

수송표의 작성

기본가능해의 도출 수송문제의 기본가능해(basic feasible solution of transportation problem)가 되려면 (m+n-1)개의 수송경로에 양수의 수송량이 있어야 한다 수송문제의 해법도 심플렉스법과 마찬가지로 우선 기본가능해를 먼저 찾고 이를 근거로 해를 점진적으로 개선해 나가는 반복연산과정이다. 기본가능해를 찾는 방법 지름길법(shortcut method)이라고 불리워지기도 하는 최소비용법(最少費用法;minimum-cost method) 벌과손실법(罰過損失法;penalty method or Vogel's approximation method) 북서코너법(northwest-corner method) 열 최소비용법(column minimum cost method) 행 최소비용법(row minimum cost method)

최소비용법 1) 수송표에서 수송비가 가장 작은 난을 선정한 후 공급량과 수요량을 비교하여 적은 양을 이 난에 할당하고 할당된 양을 작은 원으로 표시한다. 2) 할당한 양을 선정된 난의 공급량과 수요량에서 각각 빼어서 공급량과 수요량을 수정한다. 3) 수정한 수요량이나 공급량이 0이된 행이나 열에 있는 난은 수송량 할당대상에서 제외되어야 하므로 그 난을 ×로 표시한다. 4) 할당되지 않고, 할당대상에서 제외되지 않은 난 중에서 수송비가 가장 작은 난을 선정하여 1)부터 3)까지의 절차를 모든 난이 할당이 되거나 할당대상에서 제외될 때까지 반복하되, 수요량과 공급량은 수정된 양으로 비교하여야 한다.

벌과손실법 벌과손실법은 관련된 다른 난의 비용과의 관계를 전혀 고려하지 않고 수송표에 있는 최소비용에 우선을 두고 할당하는 최소비용법과는 달리 기회비용을 나타내는 벌과손실지수를 구하여 기회비용의 발생을 최소화하는 할당방법이다. 벌과손실법으로 기본가능해를 구하는 절차는 다음과 같다. (1) 각 행과 열의 벌과손실지수를 구한다. 각 행과 열의 벌과손실지수는 각 행과 열에 있는 가장 작은 두 수송비의 차이이다.

(2) 벌과손실지수가 가장 큰 행 또는 열을 찾아 그 행 또는 열에 있는 난 중에서 수송비가 가장 작은 난을 선정한다 (2) 벌과손실지수가 가장 큰 행 또는 열을 찾아 그 행 또는 열에 있는 난 중에서 수송비가 가장 작은 난을 선정한다. 이 난의 공급량과 수요량을 비교하여 적은 양을 그 난에 할당하고 할당량을 작은 원으로 표시한다. (3) 수송량이 할당된 난의 공급량과 수요량을 최소비용법과 같은 방법으로 수정하고 수정한 공급량 또는 수요량이 0인 행 또는 열에 있는 난을 수송량의 할당대상에서 제외하는 뜻으로 그 난에 ×로 표시한다. (4) 수송량 할당대상에서 제외되지 않은 난만으로 각 행과 열의 벌과손실지수를 구하여 할당 전의 벌과손실지수를 수정하고, 수정된 수요나 공급량이 0이된 행 또는 열의 벌과손실지수는 의미가 없으므로 지운다.

(5) 수정된 벌과손실지수를 가지고 2)부터 4)까지의 절차를 모든 난이 할당대상에서 제외될 때까지 반복한다.

최적해 결정 기본가능해를 이용하여 최적해를 찾는 데는 디딤돌법(stepping-stone method)이나 수정유통법(修正流通法; modified distribution method; MODI)이 사용된다.

디딤돌법 디딤돌법은 최적해여부를 판정하는 과정(빈난평가)과 최적해가 아닌 경우 수송량을 재할당하여 더 나은 수송방법을 찾는 과정으로 구성되어 있다.

빈난평가 (1) 평가하고자 하는 빈 난을 선택하여 그 난의 폐쇄경로(閉鎖經路; closed path or pivotal path)를 찾는다. 폐쇄경로 찾는 법 폐쇄경로를 찾기 위해서는 선택한 빈 난에서 시작하여 수평 또는 수직으로 이동하여 할당된 난을 만나면 그 방향을 바꾸어야 한다. 즉 수평으로 이동중 할당된 난을 만나면 할당된 난에서 수직으로 이동해야 하고, 수직으로 이동중 할당된 난을 만나면 수평으로 이동해야 한다. 따라서 할당된 난이 폐쇄경로의 모서리가 된다. 이동중 만나는 할당된 난에서 방향을 바꿀 수 없을 때, 즉 같은 열이나 행에 할당된 난이 없을 때는 그 할당된 난은 난의 평가과정에서 제외된다. 이러한 원칙에 따라 이동을 계속하면 결국 출발한 빈 난으로 다시 돌아오게 된다. 여기서 평가하고자 하는 빈 난과 폐쇄경로의 모서리난을 합치면 짝수가 된다.

(2) 시작한 빈 난을 포함하여 폐쇄경로의 모서리가 되는 난의 단위당 수송비에 +부호와 –부로를 교체하면서 차례대로 부여한다. (3) +와 –부호가 붙은 단위당 수송비를 모두 합한다. (4) (3)의 평가 결과 양수이면 수송비가 증가하게 되어 해를 개선하지 못하고, 0이면 총비용이 같은 다른 해가 존재함을 의미하며 음수이면 수송량의 재할당으로 해의 개선이 가능함을 나타낸다.

최소비용법에 의한 기본가능해

재할당 (1) 빈난평가 결과가 음수인 난 중에서 가장 작은 값을 가진 빈난을 선택한다. (2) 선택된 빈난을 평가하는데 사용한 폐쇄경로를 추적하여 폐쇄경로에 부여된 부호를 찾는다. (3) 공급과 수요의 균형을 유지하기 위하여 폐쇄경로에서 –부호가 부여된 난에 할당된 수송량 중에서 가장 적은 양을 선택한다. (4) 선택된 가장 적은 수송량을 폐쇄경로에서 –부호가 부여된 난에서는 빼고, +부호가 부여된 난에서는 더해준다.

복수의 최적해 빈난평가 결과 모두 음수가 아니므로 최적해임을 알 수 있다. 그러나 S2-D3 평가 결과는 0으로써 양수도 아니다. 이는 복수의 최적해(multiple optimal solutions)가 존재한다는 것을 의미한다. S2-D3의 폐쇄경로에서 -가 부여된 난은 S2-D1과 S1-D3이며 할당된 양은 두 난 모두 1,000이다. 이 양을 -가 부여된 난의 할당량에서 빼고, +가 부여된 난의 할당량에 더하면 또 다른 최적해가 도출된다.

퇴화현상 할당된 난의 수가 (m+n-1)보다 적게 되는 경우도 수송문제에서 발생하는 데 이를 수송문제의 퇴화현상(degeneracy of transportation problem)이라고 한다. 퇴화현상이 발생하면 일부 빈 난의 폐쇄경로를 찾을 수 없어 빈난평가를 할 수 없다. 이런 경우에는 필요한 수 만큼의 인위적인 할당된 난을 만들어 빈난평가를 하여야 한다.

인위적으로 할당된 난을 만들 때는 빈 난에 (epsilon)을 할당하여 만든다.