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)에 중복 없이 하나씩 할당하려고 한다. <보기>의 비용표를 따를 때, 총 처리비용의 최솟값은?
작업\기계ABCD
116181517
214131112
312131614
416141518
1
52
2
53
3
54
4
55
해설

헝가리안 방법으로 구한 최소 총비용은 53이다.

행 감소: 각 행 최솟값 15, 11, 12, 14를 뺀다.
열 감소: D열 최솟값 1을 추가로 뺀다.
감소량 합: 15+11+12+14+1=5315+11+12+14+1=53

0 위치로 작업1-C(15), 작업2-D(12), 작업3-A(12), 작업4-B(14)를 중복 없이 할당할 수 있어 15+12+12+14=5315+12+12+14=53이 최적이다.

  • 52: 행 최솟값만 더한 값으로, 작업1과 작업2가 모두 C에 몰려 실행 불가능하다.
  • 54: 작업1-D, 작업2-C로 바꾼 할당의 비용으로 최솟값보다 크다.
  • 55: 최적 할당보다 비용이 큰 다른 할당의 값이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[서울시 연구사 산업공학개론] 25년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요서울시 연구사 산업공학개론 기출문제 암기장 전체 보기