Week 10: Transportation, Transshipment & Assignment

This week’s big question: you have factories that can supply goods and stores that demand them, and a different cost to ship along every route. Which shipping plan meets all the demand at the lowest total cost? These are still linear programs, but they have so much structure that Solver cracks them fast.

These three models run the quiet machinery of the economy: distribution networks routing product from plants to stores, crew or shift assignment putting the right person on the right job, machine-to-task scheduling on a factory floor, even matching officials to games. All of them reduce to the same idea. Choose how much flows on each route to hit every requirement at the least total cost.

Before the week

• Read: Taylor, Introduction to Management Science (13e): Chapter 6, “Transportation, Transshipment, and Assignment Problems,” pp. 261–279 (focus: the transportation model balanced and then unbalanced, transshipment, and assignment as a special case), then Chapter 5, “Integer Programming,” pp. 208–220 (focus: why some decisions cannot be fractional, what changes when you require whole numbers, and how Solver takes an integer or binary constraint). The chapter PDFs are posted in this week’s Canvas module.
• Warm-up self-check, supply, demand, and reading a cost matrix:

Session 1: Mon, Oct 26 · The transportation model, and whole-number decisions (TBD)

🧩 Puzzle

Two plants, two stores. Plant A can ship 120 units and Plant B can ship 80 (total supply 200). Store 1 needs 100 and Store 2 needs 100 (total demand 200. The problem is balanced). Shipping costs per unit are: A→Store 1 = \$8, A→Store 2 = \$6, B→Store 1 = \$5, B→Store 2 = \$9. What shipping plan meets every store’s demand at the minimum total cost?

Build the skill 1: set up the transportation grid

A transportation model has a set of sources (each with a fixed supply), a set of destinations (each with a fixed demand), and a unit cost to ship along every source→destination route. The decision variables are the shipment quantities \(x_{ij}\), units sent from source \(i\) to destination \(j\). The objective is to minimize total cost \(\sum_{i}\sum_{j} c_{ij}\,x_{ij}\), subject to “ship out all of each supply” and “meet all of each demand.”

When total supply equals total demand the problem is balanced, and every unit shipped out arrives somewhere. Drag the slider to choose how much travels on the Plant A→Store 1 route and watch every other route adjust automatically, then hit “Least cost”:

The model, written out

The full balanced transportation model is short enough to write in three lines, and these are exactly the families of cells you will type into Solver:

One supply equality per source row (“everything Plant \(i\) ships sums to its supply \(s_i\)”), one demand equality per destination column (“everything arriving at store \(j\) sums to its demand \(d_j\)”), and shipments can’t go negative. That is the whole model, Solver just searches the \(x_{ij}\) for the cheapest combination that satisfies all the equalities at once.

Build the skill 2: one degree of freedom: trade cheap routes against expensive ones

Notice you only got to choose one number. With 2 sources and 2 destinations there are four routes, but the supply and demand constraints lock down the other three the moment you fix the first. A balanced 2×2 problem has exactly one degree of freedom. So the whole job is: push flow onto the cheap routes and starve the expensive ones, as far as the supplies and demands allow.

Here Plant B→Store 1 is the cheapest route at \$5, so we want B serving Store 1 as much as possible. Plant B only has 80 units, so it sends all 80 to Store 1; the remaining 20 of Store 1’s demand must come from Plant A. That forces the rest of the grid, and the expensive B→Store 2 route (\$9) carries nothing.

Now scale it past what you can eyeball

A 2×2 has one free number. You really can do it in your head. Real problems are not 2×2. Picture a craft brewery’s hops distribution: three farms (90, 130, 140 lbs; total 360) shipping to three breweries (110, 120, 130 lbs; total 360. Balanced), with a unit cost (\$/lb) for every route:

Now there are nine routes and four degrees of freedom. Far too many combinations to eyeball, and the cheapest cell in each row no longer wins on its own (grabbing every row’s minimum overspends some farm’s supply and starves a brewery). Type this grid into Solver with the three supply equalities and three demand equalities and it returns the optimal plan in well under a second, at a total cost of \$1,460. That is the whole reason for Solver: same skill as the 2×2 (read the matrix, write the equalities, minimize the cost sum), but now with too many routes to guess.

Build the skill 3: when the answer has to be a whole number

Look again at the plan you just built. Every shipment came out a whole number of units and nobody had to ask for it. That happens because the supplies and demands on the right-hand side are themselves whole, which pulls the optimum onto whole units by itself. The structure handed you integers for free. Now take that structure away.

A county health department wants to reach as many residents as it can with two options. A mobile clinic van costs \$60,000, needs 1 staff team, and reaches 5,000 residents a month. A walk-in kiosk costs \$40,000, needs 2 staff teams because it keeps longer hours, and reaches 4,000. There is \$240,000 to spend and 6 staff teams to assign. Counting the budget in \$10,000 units, with \(x\) vans and \(y\) kiosks:

Solve that as an ordinary LP, the way you did in Week 7, and the best corner sits at \(x = 3\), \(y = 1.5\), reaching 21,000 residents. There is no such thing as half a kiosk. Solving the problem while ignoring the whole-number requirement is called the LP relaxation, and its answer is a ceiling: the true whole-number plan can never beat it.

The obvious repair is to round. Try it below. Every dot is a whole-number plan that actually fits inside both the budget and the staffing:

Rounding up to \((3, 2)\) breaks both constraints at once: \$260,000 against a \$240,000 budget, and 7 staff teams out of 6. Rounding down to \((3, 1)\) is affordable at \$220,000 and reaches 19,000 residents, which is legal but not the best you can do. The real optimum is \((4, 0)\): four vans and no kiosks at all, spending the \$240,000 exactly and reaching 20,000 residents.

That is the whole lesson in one picture. The best whole-number plan was not next to the fractional one and it was not any rounding of it. It was a different mix. Integer programming is what you use when the decision variables have to come out whole: how many vans to buy, whether to open a site at all, which grants to fund. Taylor splits the models three ways, and the difference is only which variables carry the requirement: a total integer model where every variable is whole, a 0-1 model in which each decision is a binary variable (1 for yes, 0 for no), and a mixed-integer model where some variables are whole and others stay continuous.

In Solver the change is one line. Add a constraint on the decision cells whose relation is int, or bin for yes/no. What it costs you is speed. Solver can no longer slide along the edges of the region to a corner; it has to search among the dots, which it does by branch and bound, repeatedly solving relaxed LPs and discarding whole branches that cannot beat the best whole-number answer found so far. At this size that is instant. It is also why integer models scale worse than the transportation model you just built, whose structure hands you whole units without paying that cost at all.

In practice: real shipping problems rarely arrive this tidy

• Unbalanced totals flip the constraint type. When supply exactly equals demand, the supply and demand constraints are equalities (\(=\)). When they don’t match, Taylor’s rule is to switch the slack side’s constraints to \(\le\): if supply > demand, the supply constraints become \(\le\) (some supply stays put); if demand > supply, the demand constraints become \(\le\) (some demand goes unmet). An equivalent reformulation is to rebalance with a dummy node. Supply > demand → a dummy destination absorbs the surplus at \$0 cost; demand > supply → a dummy source “covers” the shortfall on paper (the demand it fills is really unmet). Both give the same plan; in Solver it is just the difference between an \(=\) and a \(\le\) on the relevant constraint.
• Costs aren’t always per unit. A carrier may charge per truck or per trip, or give volume discounts, then the cost is no longer a clean \(c_{ij}\) per unit and the plain transportation model needs adjusting.
• Transportation hands you whole units. Most models do not. Because the supplies and demands are whole numbers here, the optimum lands on whole units by itself, and that same network structure is why Solver dispatches even large transportation problems so quickly. When a model has no such structure, never round a fractional answer and call it done: rounding can land you outside the feasible region, and even when it stays inside it can miss the best whole-number plan, exactly as it did with the vans and kiosks. Say int or bin in the model and let Solver search.

Back to the puzzle

The minimum-cost plan ships 20 on Plant A→Store 1 (so A→Store 2 = 100, B→Store 1 = 80, B→Store 2 = 0), for a total cost of \$1,160. The lowest the slider can reach. Check it: \(20(8) + 100(6) + 80(5) + 0(9) = 160 + 600 + 400 + 0 = 1{,}160\). The intuition pays off: cheap B→Store 1 runs flat out, expensive B→Store 2 carries nothing, and Plant A quietly covers what’s left.

In-class group practice (wrap-up)

To close Session 1, find a low-cost shipping plan by hand in your group. Write your group’s names on the sheet and hand it to your TA before you leave. It counts toward participation.

• Download: Week 10 group practice (Word)

Session 2: Wed, Oct 28 · Transshipment & assignment (special cases) (TBD)

🧩 Puzzle

Two workers, two jobs. Worker 1 finishes Job A in 7 hours and Job B in 9; Worker 2 finishes Job A in 8 and Job B in 5. Each worker takes exactly one job and each job needs exactly one worker. Which assignment finishes the work in the fewest total hours?

Build the skill 1: transshipment: pass-through nodes in the middle

A transshipment model is a transportation model with intermediate nodes. Think a port, warehouse, or hub between the sources and the destinations. Goods can flow source → hub → destination instead of going direct, and a hub is neither a final source nor a final sink: whatever flows in must flow out. That is a flow-conservation constraint, and it is a real equation, not just a slogan.

Picture two coffee importers feeding Port Hub A, which then forwards to roasters. If Importer 1 sends 50 bags and Importer 2 sends 30 bags into the hub, conservation says:

The compact check is \(\text{inflow}=\text{outflow}\) at a pure transfer node.

The 80 bags that arrive must leave, the hub stores nothing on net. And the routing is flexible: goods can go source → hub → destination, hub → hub (one port forwarding to another), or even source → destination directly, skipping the hub. A hub is an option, not a forced detour. Why have hubs at all? Consolidation: pooling many small shipments at a hub can make the per-leg cost low enough that hub routing beats shipping direct, which is exactly why distribution networks are built around them. Solver handles all of this with the same minimize-cost setup, just more nodes and one flow-balance equation at each hub.

Build the skill 2: assignment: a transportation problem where everything equals 1

An assignment model is the cleanest special case: every source has supply 1 and every destination has demand 1. You’re not splitting shipments. You’re matching each worker to exactly one job (or each machine to one task, each crew to one route). Formally each xᵢⱼ ∈ {0, 1} (\(1\) if worker \(i\) does job \(j\), else \(0\)), and the constraints are simply

One worker per row, one job per column. Notice Solver returns clean 0s and 1s here without being told to, the same free integrality you met on Monday: the network structure does it, not an int constraint. Slide the free route and hit “Least cost”, at \(x = 1\) the optimal matching locks in:

Why you cannot eyeball the big ones

Two workers give just 2 possible matchings, easy. But scale it up. Four food-truck crews must be sent to four festival lots, and you want to minimize total drive-time (minutes). Here is the time matrix:

The tempting move is to grab the single smallest cell (Crew 1 → Lot 2 at 10 min) and fill in around it. Do that greedily and you are forced into Crew 2 → Lot 3 (12), Crew 4 → Lot 1 (28), Crew 3 → Lot 4 (30), for a total of 80 minutes. But the true optimum never uses that shiny 10-minute cell at all: Crew 1 → Lot 4 (12), Crew 2 → Lot 1 (14), Crew 3 → Lot 2 (12), Crew 4 → Lot 3 (12) = 50 minutes, a third faster. Eyeballing fails because the cheapest individual choice can poison the rest of the grid. With four crews there are \(4! = 24\) matchings to weigh; bump it to ten crews and ten lots and there are \(10! = 3{,}628{,}800\), about 3.6 million. Nobody checks 3.6 million by hand. You need the model and Solver.

In practice: small grids are deceiving; the model is what scales

• The greedy “grab the cheapest cell” rule is wrong. As the 4×4 above shows, the smallest single entry can trap you into an expensive total. Assignment optimizes the whole matching at once, which is why you let Solver do it instead of picking cells by hand.
• Make it square first. Assignment assumes equal numbers of workers and jobs. More jobs than workers? Add a dummy worker (with large or zero “do-nothing” costs) so the model stays balanced. The unfilled job just gets the dummy. (This is the assignment version of the dummy-source / dummy-destination rule from Session 1.)
• The costs encode your real goal. Put hours in the grid and you minimize time; put dollars and you minimize money; put a “happiness” penalty and you can model preferences. The math doesn’t care, so make sure the numbers you feed it mean what you intend.

Back to the puzzle

Matching Worker 1 → Job A and Worker 2 → Job B takes \(7 + 5 = \textbf{12}\) hours. The only other option, the cross assignment (Worker 1 → Job B, Worker 2 → Job A), takes \(9 + 8 = 17\) hours, so 12 hours is optimal, exactly where the slider’s “Least cost” button lands. Same minimize-cost idea as Session 1, special case where every supply and demand equals 1.

After-class check

Questions spanning the transportation model, balancing with a dummy source/sink, transshipment hubs, and assignment as a 1-to-1 special case. Retry freely; nothing is submitted.

Weekly take-home (graded: submit on Canvas)

Everything for the take-home lives in one Excel workbook, and it builds all three of this week’s models with the same Solver pattern. The first brief is a book distributor whose depot stock is counted in pallets while its zones order in cases, and once you convert them, supply and demand do not balance, so you have to repair the model before it will solve at all. The second is a library sending three auditors to three branches: try the obvious shortcut of giving each auditor their own fastest branch and watch it collide, then build the 0/1 grid properly. The third is a food-bank cross-dock, where you write the flow-balance condition yourself and then solve the network three ways (direct only, through the dock only, and with both available) to see which wins and which pantry stays direct. Solver fills the shipment grids; the conversions, the formulas and the repair are yours. Three short responses plus the required AI-use disclosure go on the Free responses sheet. Upload the completed .xlsx on Canvas. That one file is your entire submission.