Z회사는 4개의 작업(1, 2, 3, 4)을 4개의 기계(A, B, C… | [서울시 연구사 산업공학개론] 25년 1회차 기출문제 상세 페이지
1[서울시 연구사 산업공학개론] 25년 1회차
Z회사는 4개의 작업(1, 2, 3, 4)을 4개의 기계(A, B, C, D)에 중복 없이 하나씩 할당하려고 한다. <보기>의 비용표를 따를 때, 총 처리비용의 최솟값은?
작업\기계 A B C D 1 16 18 15 17 2 14 13 11 12 3 12 13 16 14 4 16 14 15 18
1
52
2
53
3
54
4
55
해설
헝가리안 방법으로 구한 최소 총비용은 53이다.
행 감소: 각 행 최솟값 15, 11, 12, 14를 뺀다.
열 감소: D열 최솟값 1을 추가로 뺀다.
감소량 합:0 위치로 작업1-C(15), 작업2-D(12), 작업3-A(12), 작업4-B(14)를 중복 없이 할당할 수 있어 이 최적이다.
- 52: 행 최솟값만 더한 값으로, 작업1과 작업2가 모두 C에 몰려 실행 불가능하다.
- 54: 작업1-D, 작업2-C로 바꾼 할당의 비용으로 최솟값보다 크다.
- 55: 최적 할당보다 비용이 큰 다른 할당의 값이다.
오류나 개정된 내용이 보이면 알려주세요