Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 38 ยท Modelling

Transportation and Assignment Models

Model the transportation problem and the assignment problem as linear programs with supply, demand and one-to-one constraints, then solve them in Python.

Shipping goods from warehouses to stores and matching workers to jobs look like different problems, but both fit a pattern: a cost matrix and flows between two groups of nodes. These are the oldest and most useful LP structures in logistics. This lesson formulates both as ordinary linear programs; they also have special fast algorithms that you will meet in the network-flow chapters.

The transportation problem

There are m sources (factories, warehouses) with supplies s_i and n destinations (stores, customers) with demands d_j. Shipping one unit from i to j costs c_ij. Choose the quantity x_ij shipped on each route to minimize total shipping cost.

TEXT
minimize    sum_i sum_j c_ij x_ij
subject to  sum_j x_ij <= s_i      (cannot ship more than supply)
            sum_i x_ij >= d_j      (every demand must be met)
            x_ij >= 0

When total supply equals total demand the problem is balanced and both constraint groups become equalities. If supply exceeds demand, use the inequalities above. If demand exceeds supply, no plan meets all demand; the model is infeasible unless you add a penalty or an "unmet demand" variable.

A small instance: three warehouses with supplies 40, 60 and 50, and four stores with demands 30, 25, 45 and 50 (total 150 on both sides).

Cost Store 1 Store 2 Store 3 Store 4
Warehouse A 8 6 10 9
Warehouse B 9 12 13 7
Warehouse C 14 9 16 5

The trick is to flatten the 2D grid of variables x_ij into one vector, remembering index k = i*n + j. NumPy kron or loops make the constraint matrices short.

Python Solve a transportation problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A famous property: when supplies and demands are integers, a vertex solution of a transportation LP is automatically integer. You never get "12.4 trucks" here, because the constraint matrix is totally unimodular. We return to this in the integer programming chapter.

Unbalanced problems

Total supply 150, total demand 120? Inequalities <= on supply handle that. If demand exceeds supply, add a dummy source with enough supply to cover the gap and very high costs, or give every demand an unmet variable with a penalty. Whatever is shipped from the dummy is demand that is not really served.

Python Unbalanced: demand exceeds supply

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The penalty makes the optimizer choose which store goes short in the cheapest way.

The assignment problem

In an assignment problem you have n workers and n jobs, a cost c_ij for worker i doing job j, and you must give each worker exactly one job and each job exactly one worker. It is a transportation problem where every supply and demand equals 1.

TEXT
minimize    sum c_ij x_ij
subject to  sum_j x_ij = 1   for every worker i
            sum_i x_ij = 1   for every job j
            x_ij >= 0

The natural variables are binary (x_ij is 1 if worker i takes job j), but the LP relaxation x_ij >= 0 already returns a solution of 0s and 1s because of total unimodularity.

Python Assign workers to jobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

linear_sum_assignment uses the Hungarian-style algorithm; it is much faster than a generic LP for large matrices but solves exactly the same problem.

Variations

  • More jobs than workers. Relax "every job once" to "at most once" and keep "every worker exactly once" (or the reverse).
  • Maximize benefit. Negate the matrix (or pass maximize=True to linear_sum_assignment).
  • Forbidden pairings. Set the cost to a huge value, or better, remove the variable.
  • Capacity. If a worker can do up to k jobs, change the right-hand side from 1 to k; you are back to a general transportation problem.
flowchart LR
  A["Warehouse A (40)"] -->|"x_A1 ... x_A4"| S1["Store 1 (30)"]
  A --> S2["Store 2 (25)"]
  B["Warehouse B (60)"] --> S2
  B --> S3["Store 3 (45)"]
  C["Warehouse C (50)"] --> S3
  C --> S4["Store 4 (50)"]

Sources on the left, destinations on the right; each arrow carries a decision variable and a unit cost.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a balanced transportation problem, total supply and total demand are

    Balanced means supply equals demand, so every constraint can be an equality.
  2. 2. How do you handle demand exceeding supply?

    The dummy source absorbs the shortage and the penalty decides which demand goes unserved.
  3. 3. The assignment problem is a transportation problem where

    Each worker supplies exactly one unit of work and each job demands exactly one worker.
  4. 4. Why does the LP relaxation of the assignment problem yield 0/1 solutions?

    Total unimodularity means every vertex of the polytope has integer coordinates when the right-hand sides are integers.

Summary

  • Transportation: ship from sources to destinations at minimum cost with supply and demand constraints.
  • Flatten the x_ij grid into a vector and build row-sum and column-sum constraints.
  • Unbalanced problems use inequalities or a dummy source with a penalty.
  • Assignment is the special case with all supplies and demands equal to 1.
  • Integer data give integer vertices, so LP solves these problems exactly.

Next: Multi-Period Planning and Inventory Models