Business Mathematics and Statistics · Ch 10 — Operations Research (Transportation Problem, Assignment Problems, Decision Theory)

The Assignment Problem — Meaning and Structure

An assignment problem arises whenever exactly $n$ 'workers' (people, machines, vehicles) must be matched one-to-one with exactly $n$ 'jobs' (tasks, routes, territories), so that every worker gets exactly one job and every job goes to exactly one worker, at minimum total cost (or maximum total profit).

Assignment as a special case of the transportation problem

An assignment problem is a transportation problem in which:

the number of sources equals the number of destinations ( $m=n$ , a square cost matrix), and
every supply and every demand equals exactly 1 (each worker supplies one unit of capacity; each job demands exactly one).

Because every $a_i=1$ and every $b_j=1$ , a transportation method could technically be used — but it is inefficient here, since it would treat integer 0/1 allocations as ordinary continuous shipments. The Hungarian Method, studied next, is a specialised algorithm built exactly for this one-to-one, all-or-nothing structure, and reaches the optimal assignment far faster.

	Transportation Problem	Assignment Problem
Supplies/demands	Any positive quantities $a_i,b_j$	Always exactly 1 for every row and column
Matrix shape	$m$ sources $\times$ $n$ destinations; $m$ need not equal $n$	Always square, $n\times n$
A cell's allocation	Any quantity from 0 up to the row/column limit	Either 0 (not assigned) or 1 (assigned)
Solution method	NWC / LCM / VAM, then MODI or Stepping-Stone	Hungarian Method
Typical use	Shipping goods from factories to warehouses	Assigning workers to jobs, machines to orders, salesmen to territories

The cost/profit table …

Definition 1Assignment Problem

A special transportation problem with a square cost matrix in which every source supplies exactly 1 unit and every destination demands exactly 1 unit — equivalent to matching $n$ workers to $n$ jobs one-to-one at mini …

Start your 14-day free trial to unlock the full solution →

← Previous · 5Testing the IBFS for Optimality Next · 7 →The Hungarian Method