Difficulty: Intermediate

Prerequisites: Basic understanding of linear programming (LP) concepts, Excel Solver or equivalent LP software, introductory microeconomics.

Big Picture

Transportation planning sits at the intersection of operations research and managerial economics. Firms with multiple production sites and multiple destination markets face a core logistics question: how do you route shipments from sources to destinations so that every destination gets what it needs, no source ships more than it has, and the total freight bill is as low as possible? This is one of the oldest and most widely taught applications of linear programming. If you have covered LP basics (objective functions, constraints, feasibility), this lab applies those tools to a concrete supply-chain problem.

TL;DR

A transportation LP model minimises total shipping cost by deciding how many units to send from each source to each destination, subject to supply limits and demand requirements. The Answer Report tells you which constraints are tight (binding) and which have slack. The Sensitivity Report reveals shadow prices, which show how total cost would change if a supply or demand constraint shifted by one unit.

Key Terms and Definitions

Linear programming (LP)

A mathematical optimisation method for finding the best outcome (maximum profit or minimum cost) given a set of linear constraints. In simple terms, it is a structured way to make the best decision when you have limited resources and competing demands.

Objective function

The formula you are trying to minimise or maximise. In a transportation problem, this is total shipping cost: the sum of (units shipped on each route multiplied by that route's per-unit cost). Think of it as the single number you want to push as low (or as high) as possible.

Decision variables

The quantities the solver is free to choose. Here, each decision variable represents the number of units shipped from a particular source to a particular destination. Think of them as the blanks the model fills in.

Constraints

Conditions that the solution must satisfy. In transportation LP there are two families: supply constraints (you cannot ship more than a source has) and demand constraints (each destination must receive at least what it requires).

Binding constraint

A constraint that is exactly met in the optimal solution, with zero slack. If a supply constraint is binding, that source is fully used up. Think of it as a limit you have hit exactly.

Non-binding constraint

A constraint that is not fully used. It has slack, meaning there is leftover capacity. In this lab, Bremen's supply constraint is non-binding because 20 carloads remain unshipped.

Slack

The difference between the available amount and the amount actually used. A binding constraint has zero slack; a non-binding one has positive slack.

Shadow price (dual value)

The amount by which the objective function (total cost) would change if the right-hand side of a constraint increased by one unit, all else equal. A positive shadow price on a demand constraint means fulfilling one more unit of demand at that destination would raise total cost by that amount. Think of it as the marginal cost of relaxing a constraint by one unit.

Allowable increase / allowable decrease

The range over which a constraint's right-hand side can change before the shadow price itself changes. Within this range, the shadow price gives an accurate prediction of cost change.

Sensitivity report

A Solver output that lists shadow prices and allowable ranges for every constraint, plus reduced costs and allowable ranges for every decision variable. It answers "what if" questions without re-running the model.

Transportation model

A special class of LP where the goal is to ship goods from a set of sources to a set of destinations at minimum total cost, subject to supply and demand constraints.

Core Content: Setting up the Transportation LP Model

The problem has three sources (Hamburg, Bremen, Rotterdam) shipping goods to four destinations (Munich, Berlin, Hannover, Dresden). Each source has a fixed supply of carloads, and each destination has a fixed demand.

Supply (carloads available):

• Hamburg: 300

• Bremen: 400

• Rotterdam: 340

• Total supply: 1,040

Demand (carloads required):

• Munich: 320

• Berlin: 340

• Hannover: 280

• Dresden: 80

• Total demand: 1,020

Total supply (1,040) exceeds total demand (1,020) by 20 carloads. This means the model has excess capacity, and at least one supply constraint will be non-binding.

Unit transportation costs (cost per carload):

The solver chooses how many carloads to send along each of the 12 possible routes (3 sources x 4 destinations) to minimise total cost while meeting all supply and demand constraints.

Core Content: Reading the Answer Report

The optimal solution ships units as follows:

Minimum total transportation cost: $136,300

What the Answer Report tells you:

• Status column: Shows "Binding" or "Not Binding" for each constraint.

• Slack column: Shows the unused portion of each constraint.

Results from this problem:

• All four demand constraints (Munich, Berlin, Hannover, Dresden) are binding with zero slack. Every destination received exactly what it needed.

• Hamburg's supply constraint is binding (all 300 carloads shipped).

• Rotterdam's supply constraint is binding (all 340 carloads shipped).

• Bremen's supply constraint is not binding, with a slack of 20. Bremen had 400 carloads available but shipped only 380. Those 20 surplus carloads sit idle because shipping them anywhere would raise total cost.

The key takeaway: when supply exceeds demand, the solver leaves the cheapest-to-idle source with leftover stock. Bremen's surplus exists because, at the given costs, it is cheaper to leave those 20 units unshipped than to route them to any destination.

Core Content: Reading the Sensitivity Report

The Sensitivity Report provides shadow prices and allowable ranges for each constraint.

Demand-side shadow prices ("In Shipments"):

Each shadow price represents the marginal cost of satisfying one additional unit of demand at that destination. Munich has the highest shadow price (195), meaning it is the most expensive destination to serve on the margin.

Supply-side shadow prices ("Out Shipments"):

How to interpret the supply-side shadow prices:

• Hamburg (-20): If Hamburg's supply increased by one carload, total cost would fall by $20. The negative sign means extra supply at Hamburg is valuable because it displaces costlier shipping from elsewhere.

• Bremen (0): Bremen already has surplus capacity. Adding another carload of supply there changes nothing, because the extra unit would just sit idle.

• Rotterdam (-15): An extra carload at Rotterdam would reduce total cost by $15.

The allowable increase and decrease columns tell you the range over which these shadow prices remain valid. For Bremen, the allowable increase is effectively infinite (1E+30), confirming that no amount of additional supply at Bremen would change the cost, since it is already not fully used.

Core Content: Effect of a Cost Decrease on the Optimal Solution

In the second scenario, the per-unit cost of shipping from Rotterdam to Berlin drops from 150 to 100, and from Rotterdam to Dresden drops from 190 to 127 (each reduced by roughly one-third).

Revised optimal shipments:

Revised minimum total cost: $135,060 (a saving of $1,240 compared to the original $136,300).

What changed and why:

• Rotterdam now ships 40 carloads to Berlin and 80 to Dresden. In the original solution it shipped nothing to either city, because those routes were too expensive relative to alternatives.

• Bremen shifts 100 carloads to Munich (previously zero) and stops shipping to Berlin and Dresden, because Rotterdam now handles those routes more cheaply.

• Bremen still has 20 surplus carloads. The binding/not-binding status of constraints is unchanged.

Revised shadow prices (selected changes):

• Hamburg's shadow price moves from -20 to -15. The cost reduction at Rotterdam made Hamburg's extra capacity slightly less valuable.

• Rotterdam's shadow price moves from -15 to -35. Rotterdam is now considerably more valuable on the margin because its cheaper routes to Berlin and Dresden mean additional Rotterdam supply would save more.

• The demand-side shadow prices for Munich (215, up from 195) and Dresden (162, down from 170) shift to reflect the new cost structure.

Formulas and Model Structure

Objective function (minimise total cost):

\min Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} \, x_{ij}

Where c_ij is the per-unit cost of shipping from source i to destination j, and x_ij is the number of units shipped on that route.

Supply constraints (one per source):

\sum_{j=1}^{n} x_{ij} \leq S_i \quad \text{for each source } i

The total shipped out of source i must not exceed its supply S_i.

Demand constraints (one per destination):

\sum_{i=1}^{m} x_{ij} \geq D_j \quad \text{for each destination } j

The total shipped into destination j must meet or exceed its demand D_j.

Non-negativity:

x_{ij} \geq 0 \quad \text{for all } i, j

You cannot ship a negative number of carloads.

Real-World Applications

Transportation LP models are used by logistics companies, manufacturers, and retailers to route goods from warehouses to stores, from factories to distribution centres, or from ports to inland markets. Any firm with multiple supply points and multiple demand points faces exactly this problem. Airlines use similar models for crew scheduling, and agricultural cooperatives use them to decide which grain elevators ship to which export terminals.

Common Misconceptions

• "A shadow price of zero means the constraint does not matter." It means an extra unit of that resource would not change the objective value right now, but the constraint is still part of the model. Bremen's zero shadow price reflects its current surplus, not irrelevance.

• "Non-binding means the constraint can be removed." Non-binding means there is slack in the current solution. If costs or demands changed, that constraint might become binding. You still need it in the model.

• "A negative shadow price on a supply constraint means you are losing money." A negative shadow price on a supply (less-than-or-equal) constraint means additional supply at that source would reduce total cost. It is a good thing, not a loss.

• "Changing one cost coefficient always changes the optimal routes." Small cost changes may fall within the allowable range, leaving the optimal basis (and the shipment pattern) unchanged. Only when a change exceeds the allowable range does the solution structure shift.

Why It Matters / Exam Flags

• ⚠️ You will likely be asked to interpret binding vs. non-binding constraints and explain what slack means in context.

• ⚠️ Shadow price interpretation is heavily tested. Know the sign convention: for a "less than or equal" supply constraint, a negative shadow price means more supply would lower cost.

• ⚠️ Expect a question where a cost coefficient changes and you must explain how the optimal solution and total cost shift, as in the Rotterdam cost-decrease scenario.

• ⚠️ The relationship between total supply and total demand (and why surplus appears at a particular source) is a common short-answer topic.

Quick Self-Test

1. True or false: In this problem, total supply equals total demand. (False. Supply is 1,040 and demand is 1,020.)

1. Fill in the blank: A constraint with zero slack is called a ______ constraint. (Binding.)

1. True or false: Bremen's shadow price of zero means Bremen could be removed from the model without changing the optimal cost. (False. It means one more unit of supply at Bremen would not change total cost, but Bremen still ships 380 carloads in the optimal solution.)

1. Fill in the blank: The shadow price on Munich's demand constraint is 195, which means satisfying one additional carload of demand at Munich would increase total cost by $______. (195.)

1. True or false: When Rotterdam's costs to Berlin and Dresden dropped, the total minimum cost increased. (False. It decreased from $136,300 to $135,060.)

Practice Q&A

Q: Why does Bremen have 20 carloads of surplus in the optimal solution?

A: Total supply (1,040) exceeds total demand (1,020) by 20 carloads. The solver leaves the surplus at Bremen because, given the cost structure, it is cheaper to leave those units idle at Bremen than to ship them anywhere.

Q: What does a shadow price of 195 on Munich's demand constraint mean?

A: If Munich's demand increased by one carload (from 320 to 321), total transportation cost would rise by $195. This is the marginal cost of serving one more unit of demand at Munich, within the allowable range.

Q: Rotterdam's supply constraint has a shadow price of -15. What does the negative sign indicate?

A: A negative shadow price on a supply (upper-bound) constraint means additional supply at that source would reduce total cost. One more carload available at Rotterdam would lower the total bill by $15, because Rotterdam could displace a more expensive shipment from another source.

Q: After the cost decrease on Rotterdam's routes to Berlin and Dresden, the optimal shipment pattern changes. Explain one specific change.

A: Rotterdam now ships 40 carloads to Berlin and 80 to Dresden (previously zero to both). The cost reductions made those routes competitive, so the solver reroutes volume through Rotterdam and away from Bremen on those corridors.

Q: The allowable increase on Berlin's demand constraint is 20. What happens if Berlin's demand rises by 25?

A: A 25-unit increase exceeds the allowable range (20). The shadow price of 140 accurately predicts cost changes only within the range. Beyond 20 additional units, the basis changes, shadow prices shift, and you would need to re-solve the model to find the new cost.

Connections to Other Topics

This material connects directly to LP fundamentals covered earlier in the course. The transportation model is a special case of the general LP framework, so everything you learned about feasibility, optimality, and duality applies here. Shadow prices are the transportation-specific version of dual variables from LP theory. If the course covers production planning or resource allocation later, those problems use the same solver mechanics with different constraint structures.

Related Terms / Search Tags

Transportation problem, transportation LP, linear programming, supply constraints, demand constraints, shadow price, dual value, binding constraint, non-binding constraint, slack variable, sensitivity analysis, allowable increase, allowable decrease, reduced cost, Excel Solver, cost minimisation, shipping optimisation, operations research, APEC 3002, managerial economics, supply chain optimisation, network flow, assignment problem