AI를 위한 필수 수학

429

Chapter 10 -

운용 과학

직원에게 업무 할당, 업무 시간대 할당, 구직자에게 가능한 일자리 할당과 같은 다양한 할당 문

제와 모든 종류의 유통망에 응용이 가능할 만큼 매우 중요하다.

NOTE

할당 문제

할당 문제

assignment

problem

는 매칭 문제

matching

problem

라고도 한다. 배정받는 사람의 수는 작업 수와 같아야 하며,

각 배정자는 하나의 작업만 배정받을 수 있고 각 작업은 한 명의 배정자만 수행할 수 있다. 작업

i

를 할당자

j

에게 할당하는 데는 비용이 발생하며 목표는 총 비용을 최소화하면서 작업과 할당자 간의 매칭을 만들어내

는 것이다. 이러한 문제의 그래프는 이분 그래프

bipartite

graph

라는 특수한 유형이다. 이러한 그래프는 두 부분으

로 나눌 수 있으며 모든 엣지가 첫 번째 부분인 한 노드에서 두 번째 부분인 다른 노드로 이동한다. 모든 가

중치가 동일한 할당 문제는 이분 그래프에서의 최대 흐름 문제와 같다. 가상의 슈퍼 출발지와 또 다른 가상

의 슈퍼 목적지를 할당하고 선형 최적화와 쌍대성인 최대 유량 문제를 해결하는 것과 같은 방식으로 문제를

풀 수 있다. 이러한 문제들을 해결하기 위한 효율적인 알고리즘이 많이 있다.

10.5.6

프로젝트 설계를 위한 주공정 방법

주공정 방법

critical

path

method ...