Transportation problems
Transportation Problems
Transportation problems decide how much to ship from each source to each destination.
The goal is usually to minimize total shipping cost.
Basic Structure
A transportation problem has:
- sources
- destinations
- supply at each source
- demand at each destination
- shipping cost for each route
- nonnegative shipment quantities
Decision Variables
If there are sources $i=1,\ldots,m$ and destinations $j=1,\ldots,n$, define:
\[x_{ij}=\text{quantity shipped from source }i\text{ to destination }j\]Each possible route has its own variable.
Objective Function
If shipping one unit from source $i$ to destination $j$ costs $c_{ij}$, then total cost is:
\[\sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij}\]The objective is:
\[\min \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij}\]Supply Constraints
If source $i$ can supply at most $s_i$, then:
\[\sum_{j=1}^n x_{ij}\le s_i\]for each source $i$.
If all supply must be shipped, then use equality:
\[\sum_{j=1}^n x_{ij}=s_i\]Demand Constraints
If destination $j$ must receive at least $d_j$, then:
\[\sum_{i=1}^m x_{ij}\ge d_j\]for each destination $j$.
If demand must be met exactly, then:
\[\sum_{i=1}^m x_{ij}=d_j\]Nonnegativity
Shipments cannot be negative:
\[x_{ij}\ge 0\]for all routes.
General Transportation LP
The model is:
\[\min \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij}\]subject to:
\[\sum_{j=1}^n x_{ij}\le s_i, \qquad i=1,\ldots,m\] \[\sum_{i=1}^m x_{ij}\ge d_j, \qquad j=1,\ldots,n\] \[x_{ij}\ge 0\]Example: Two Factories and Two Warehouses
A company has factories in Pomezia and Caserta.
It ships goods to warehouses in Rome and Naples.
Let:
\[x_1=\text{units shipped from Pomezia to Rome}\] \[x_2=\text{units shipped from Pomezia to Naples}\] \[x_3=\text{units shipped from Caserta to Naples}\] \[x_4=\text{units shipped from Caserta to Rome}\]Production capacities:
\[10000\]from Pomezia and:
\[8000\]from Caserta.
Demands:
\[11000\]for Rome and:
\[4600\]for Naples.
Costs:
| Route | Cost per unit |
|---|---|
| Pomezia to Rome | 10 |
| Pomezia to Naples | 30 |
| Caserta to Naples | 5 |
| Caserta to Rome | 35 |
The LP is:
\[\min 10x_1+30x_2+5x_3+35x_4\]subject to source capacities:
\[x_1+x_2\le 10000\] \[x_3+x_4\le 8000\]destination requirements:
\[x_1+x_4\ge 11000\] \[x_2+x_3\ge 4600\]and:
\[x_1,x_2,x_3,x_4\ge 0\]Route Availability
If a route is not allowed, do not create a variable for it.
Alternatively, create the variable and force it to zero:
\[x_{ij}=0\]Usually, it is cleaner to omit impossible routes.
Balanced Transportation
A transportation problem is balanced when total supply equals total demand:
\[\sum_i s_i=\sum_j d_j\]Then supply and demand constraints are often written as equalities.
Unbalanced Transportation
If supply exceeds demand, not all supply needs to be shipped.
Use:
\[\sum_j x_{ij}\le s_i\]If demand exceeds supply, the problem may be infeasible unless shortages are allowed.
Common Mistakes
Avoid these mistakes:
- defining one variable per factory instead of one variable per route
- forgetting destination demand constraints
- writing supply constraints with $\ge$
- writing demand constraints with $\le$ when demand must be satisfied
- forgetting nonnegativity
- mixing route order in the objective
Key Takeaway
A transportation LP chooses shipment quantities on routes so that supply and demand restrictions are satisfied at minimum total cost.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.