비용과 선택 변수
작업자 i를 작업 j에 배정하는 비용을 cij, 배정하면 1이고 아니면 0인 변수를 xij라 하자. 목적은 모든 cijxij의 합을 최소화하는 것이다. 두 집합의 크기가 같은 완전 할당에서는 각 작업자와 각 작업이 정확히 한 번씩 선택된다. 비용 행렬의 각 행에서 작은 값을 독립적으로 고르는 문제가 아니라 같은 열을 중복 선택할 수 없다는 제약이 함께 있다.
가장 싼 연결부터 고르면
작업자 A의 작업 1,2 비용이 각각 1,2이고 작업자 B의 비용은 1,100이라고 하자. A에게 가장 싼 작업 1을 먼저 주면 B는 작업 2를 맡아 총비용이 101이 된다. A를 작업 2, B를 작업 1에 배정하면 총비용은 3이다. 먼저 고른 연결이 개별적으로 싸더라도 전체 비용의 최솟값을 만들지는 않을 수 있다.
직사각형과 미할당
두 집합의 크기가 다르면 기본적인 직사각형 할당에서 더 큰 집합의 일부 원소는 짝이 없을 수 있다. 일대일 완전 할당과 최대 몇 개까지 선택할지 자유로운 문제는 구분해야 한다. 미할당에 비용을 주고 싶다면 그 규칙을 별도로 모형화해야 한다. 단순히 비용이 크다는 이유만으로 기본 알고리즘이 임의의 연결을 생략한다고 가정해서는 안 된다.
모형의 범위
하나의 작업자가 여러 작업을 맡거나 작업 사이에 순서와 시간이 생기는 경우에는 추가 제약이 필요하다. 점수 합을 최대화하는 구성도 가능하지만 최소 비용과 목적의 부호를 구분해야 한다. 최적해는 입력한 비용에 대한 결과이므로 그 비용이 실제 선호나 위험을 올바르게 반영하는지도 검토한다. 같은 총비용의 서로 다른 최적 할당이 존재할 수도 있다.