Transportation and Assignment Problem
Study Notes
Transportation Models
Definition: A linear programming model to minimize the cost of transporting a
homogeneous commodity from origins (e.g., factories) to destinations (e.g., retail stores).
Objective: Identify a distribution plan that minimizes transportation costs while meeting
supply and demand constraints.
Characteristics
Limited supply at origins (factories) and known demand at destinations (warehouses,
stores).
Constant shipping costs per unit from each origin to each destination.
No shipments between sources or destinations.
Supply and demand quantities are integers.
Goal: Minimize total shipping cost while satisfying all demands.
Assumptions
Goods are homogeneous, allowing any origin to supply any destination.
Transportation costs are a direct linear function of the quantity shipped.
Total supply equals total demand.
Formulation
Inputs:
o Supply capacity of each origin.
o Demand quantity of each destination.
o Unit transportation cost for each origin-destination route.
Solution: Assign quantities to routes (cells in a table) from zero to the minimum of row
supply or column demand.
Methods for Initial Feasible Solution
1. Northwest-Corner Method (NCM):
o Start at the upper-left (northwest) cell.
o Allocate the maximum possible units (minimum of row supply or column
demand).
o Move to the next cell in the row or column until all supply/demand is allocated.
o Advantage: Simple and systematic.
o Drawback: Ignores transportation costs.
o Example (ABC Company):
Farms A (100), B (200), C (200); Projects 1 (50), 2 (150), 3 (300).
Costs: A→1: $4, A→2: $2, A→3: $8; B→1: $5, B→2: $1, B→3: $9;
C→1: $7, C→2: $6, C→3: $3.
Allocation: A→1: 50, A→2: 50, B→2: 100, B→3: 100, C→3: 200.
Total cost: 50×4 + 50×2 + 100×1 + 100×9 + 200×3 = $1900.
2. Least Cost Method (LCM):
o Allocate to the cell with the lowest unit cost.
o Assign the maximum possible units (minimum of row supply or column demand).
o Cross out exhausted rows/columns and repeat until all allocations are made.
o Example (ABC Company):
Allocation: A→1: 50, A→3: 50, B→2: 150, B→3: 50, C→3: 200.
Total cost: 50×4 + 50×8 + 150×1 + 50×9 + 200×3 = $1800.
3. Vogel’s Approximation Method (VAM):
o Calculate penalty costs (difference between the lowest and next-lowest cost in
each row/column).
o Allocate to the cell with the lowest cost in the row/column with the highest
penalty.
o Block exhausted cells and repeat until all allocations are made.
o Example:
Supply: 1 (150), 2 (175), 3 (275); Demand: A (200), B (100), C (300).
Costs: 1→A: 6, 1→B: 8, 1→C: 10; 2→A: 7, 2→B: 11, 2→C: 11; 3→A:
4, 3→B: 5, 3→C: 12.
Total cost: 150×10 + 175×7 + 25×4 + 100×5 + 150×12 = $5125.
Evaluating Optimality
1. Stepping-Stone Method:
o Trace closed paths for each empty cell, using only horizontal/vertical moves.
o Start with a "+" in the empty cell, alternate "+" and "−" signs in occupied cells.
o Calculate cost change by shifting one unit to the empty cell.
o Shift the maximum possible units to the cell with the most negative cost change.
o Example: Shift 25 units, new cost = 25×6 + 125×10 + 175×11 + 175×4 + 100×5
= $4525.
2. Modified Distribution Method (MODI):
o Compute row (ui) and column (vj) values for occupied cells using ui + vj = cij.
o Calculate cost change for empty cells: kij = cij − ui − vj.
o Allocate to the empty cell with the most negative kij, recompute ui and vj, and
repeat until all kij ≥ 0.
o Example: Initial cost = $4450, optimal cost = $4525 (multiple optimal solutions).
Special Issues
Alternate Optimal Solutions: Multiple solutions with the same minimum cost.
Degeneracy: Fewer occupied cells than rows + columns − 1.
Unacceptable Routes: Prohibit certain routes due to external factors.
Unequal Supply and Demand: Add a dummy row/column with zero costs to balance.
Assignment Problems
Definition: A special case of transportation problems where the number of sources equals
destinations, aiming to assign tasks to
