Transportation and assignment models are special cases of linear programming with highly structured algorithms. This page explains how these algorithms work with diagrams and numerical examples.

1. Transportation Problem Structure

        D1   D2   D3   (Demand)
S1      4    6    8     20
S2      5    3    7     30
S3      6    4    5     25
       15   25   35

Goal: minimize total shipping cost.

2. Initial Solution Methods

2.1 Northwest Corner Rule

Allocate top-left first, then move right/down.

Example

S1→D1 = 15
S1→D2 = 5
S2→D2 = 20
S2→D3 = 10
S3→D3 = 25

3. Vogel’s Approximation Method (VAM)

Compute penalties for each row/column, allocate where penalty is highest.

Example Penalty Table

Row penalties: S1=2, S2=2, S3=1
Column penalties: D1=1, D2=1, D3=2

Highest penalty = 2 → allocate to lowest cost in that row/column.

4. Optimality Check Using MODI (u–v Method)

Compute potentials \(u_i, v_j\) and reduced costs: \[ c_{ij}’ = c_{ij} – (u_i + v_j) \] If all reduced costs ≥ 0 → optimal.

5. Assignment Problem Structure

        J1   J2   J3   J4
W1      9    2    7    8
W2      6    4    3    7
W3      5    8    1    8
W4      7    6    9    4

Goal: assign each worker to exactly one job at minimum cost.

6. Hungarian Algorithm

Step 1: Row reduction

Subtract row minimums.

Step 2: Column reduction

Subtract column minimums.

Step 3: Cover zeros with minimum number of lines

0 0 5 6
2 0 0 4
4 7 0 7
3 2 5 0

Step 4: Assign zeros

Final assignment example:

• W1 → J2
• W2 → J3
• W3 → J1
• W4 → J4