헝가리법은 헝가리 수학자 쾨니히(konig)에 의해서 고안된 할당문제 … | [서울시 연구사 경영과학] 15년 1회차 기출문제 상세 페이지
1[서울시 연구사 경영과학] 15년 1회차
헝가리법은 헝가리 수학자 쾨니히(konig)에 의해서 고안된 할당문제 풀이법이다. 할당문제의 특수한 경우를 풀기 위하여 응용한 방법들을 설명한 것으로 옳은 것을 모두 고른 것은?㉠ 행과 열의 수가 일치하지 않을 경우, 가상행(dummy row)이나 가상열(dummy column)을 도입한다. 이때 가상행과 가상열의 단위당 비용은 가상의 큰 값 M을 사용한다.
㉡ 최대화 할당문제에 활용하고자 한다면, 할당 이익표에서 가장 큰 값을 각 칸의 숫자에서 차감하여 최대화문제를 최소화문제로 만들고, 최소화문제의 헝가리 기법을 사용하면 된다.
㉢ 경우에 따라서는 할당을 하지 말아야 하는 경우도 발생하는데, 이때는 최대화문제에서 가상의 큰 값 M을 할당하여 최적해를 구한다.
㉣ 할당문제의 최적해를 구할 때, 최적할당의 가능성을 분석하기 위하여 총기회비용표에서 0의 값을 갖는 칸을 찾아서 최소한의 직선을 사용하여 지우는데, 0의 값이 여러 개 존재하는 경우, 여러 개의 최적할당이 존재한다.
1
㉠, ㉡
2
㉡, ㉢
3
㉡, ㉣
4
㉠, ㉣
해설
옳은 설명은 최대화 문제의 변환(㉡)과 복수 최적할당(㉣)에 관한 진술이다.
㉡은 이익표의 최댓값에서 각 칸을 빼 기회손실표로 바꾸면 최소화 헝가리법을 그대로 쓸 수 있다는 내용이다. ㉣은 0인 칸으로 만들 수 있는 완전 할당 조합이 여럿이면 대안 최적해가 존재한다는 내용이다.
- ㉠: 가상행·가상열의 비용은 큰 값 M이 아니라 0을 쓴다.
- ㉢: 할당 금지 칸은 최소화(비용) 표에 큰 값 M을 넣어 배제한다. 최대화 문제에 큰 값 M을 넣으면 오히려 그 칸이 선택된다.
오류나 개정된 내용이 보이면 알려주세요