할당 문제 솔버

헝가리안 알고리즘으로 할당 문제 해결. 헝가리안 알고리즘(Kuhn-Munkres)을 구현하여 작업자와 작업 간의 최적 1:1 할당을 찾고, O(n3) 시간 복잡도로 총 비용을 최소화하거나 최대화합니다.

헝가리안 알고리즘(Kuhn-Munkres)을 구현하여 작업자와 작업 간의 최적 1:1 할당을 찾고, O(n3) 시간 복잡도로 총 비용을 최소화하거나 최대화합니다.

할당 문제란 무엇인가요?

할당 문제는 기본적인 조합 최적화 문제입니다: n명의 에이전트와 n개의 작업에 비용 행렬 C가 주어졌을 때, 총 비용을 최소화하는 일대일 할당을 찾습니다. 인력 스케줄링, 작업장 배치, 차량 라우팅에서 발생합니다.

헝가리안 알고리즘(Kuhn-Munkres 방법, 1955)은 O(n³) 시간에 할당 문제를 해결합니다. 행과 열 감산을 통해 비용 행렬을 반복적으로 축소한 다음 이분 그래프에서 증가 경로를 통해 최적 할당을 찾습니다.

직사각형 행렬의 경우 비용이 0인 더미 행 또는 열을 추가하여 행렬을 정사각형으로 만듭니다. 할당되지 않은 에이전트나 작업은 별도로 보고됩니다.

Formula: 최소화 Σ C[i][σ(i)] (모든 i에 대해) 제약: σ는 순열(일대일 대응) 헝가리안 단계: 1. 행 최솟값 빼기 2. 열 최솟값 빼기 3. 최소 개수의 선으로 0 덮기 4. 행렬 조정 후 최적이 될 때까지 반복

계산 예시

비용 행렬: [[9,2,7],[6,4,3],[5,8,1]]. 행 축소 → [[7,0,5],[3,1,0],[4,7,0]]. 열 축소 → [[4,0,5],[0,1,0],[1,7,0]]. 0인 칸으로 에이전트마다 작업 하나씩 배정: 에이전트 1→작업 2(비용 2), 에이전트 2→작업 1(비용 6), 에이전트 3→작업 3(비용 1). 총 비용 = 9 — 눈에 띄는 에이전트 2→작업 3, 에이전트 3→작업 1 조합(10)보다 낮습니다.

이 계산기를 사용해야 할 때

피해야 할 일반적인 실수

결과 해석 방법

관련 표준 및 참고자료

자주 묻는 질문

할당 문제에서 최대화를 할 수 있나요?

예. 최대화하려면 모든 비용을 음수로 바꾸거나 각 항목을 행렬 최대값에서 뺀 다음 결과 최소화 문제를 풀면 됩니다. 최적 할당은 동일하며 목적 함수의 부호만 변경됩니다.

작업자와 작업의 수가 같지 않으면 어떻게 하나요?

알고리즘은 비용이 0인 더미 행 또는 열로 작은 차원을 채웁니다. 풀이 후 더미 항목에 대한 할당은 미할당 작업자 또는 작업을 나타냅니다.

할당 문제에서 작업자 숙련도나 가용성 같은 실무 제약도 다룰 수 있나요?

기본 정식화에서는 직접 다루지 못합니다. 다만 불가능한 할당의 비용을 매우 큰 수(예: 999999)로 설정하면 알고리즘이 해당 할당을 선택하지 못하게 막을 수 있습니다. 복잡한 제약 조건에는 정수 선형계획 솔버 사용을 고려하세요.