Decision Mathematics 2

What decision mathematics 2 covers

One of the eight optional papers of 9FM0, sat as Paper 4D. It is an Option 2 paper, so it may be taken only in a matching pair with Decision Mathematics 1. It moves goods at least cost, assigns jobs to workers, pushes flow through a network, and chooses well when the outcome is uncertain. The recurrence relations that also appear on this specification are covered in the Further Pure 2 unit.

The main ideas

• Transportation problems: balancing with a zero-cost dummy, the north-west corner method, and the cell count that detects degeneracy.
• Shadow costs and improvement indices, and the stepping-stone method with its entering cell, its loop and its exiting cell.
• Allocation by the Hungarian algorithm: row then column reduction, the minimum-lines test, augmenting, dummies and maximisation.
• Cuts in a directed network and their capacity, with multiple sources and sinks and restricted vertices split into two.
• Maximum flow by the labelling procedure, with augmenting paths that may step backwards, proved maximal by exhibiting a cut of equal capacity.
• Dynamic programming with stage and state variables, worked backwards, for total, minimax and maximin objectives.
• Two-person zero-sum games: play-safe strategies, stable solutions, dominance and mixed strategies, then decision trees and expected monetary value.

The results it turns on

an m by n transportation solution uses m + n − 1 occupied cells

the count that detects degeneracy

R + K = cost for every cell in use, and improvement index = cost − R − K

shadow costs and the stepping-stone test

maximum flow = minimum cut

the theorem a maximal flow is proved with

any part of an optimal path is itself optimal

Bellman's principle, which licenses working backwards

a game is stable when maximin = minimax, and that value is the game's

the test for a stable solution

chance nodes take the probability-weighted average, decision nodes the best available

working a decision tree back to the first decision

Where it usually goes wrong

• A cut's capacity counts only the arcs crossing towards the sink. Arcs crossing back the other way contribute nothing to it.
• An augmenting path may include a backwards step, reducing the flow along one arc in order to raise the total through the network.
• In a mixed strategy problem the optimum is the highest point of the lower boundary, which may be an end of the range rather than a crossing. An end means a pure strategy and a dominated row that was left in.
• Expected monetary value is an average over repetitions, so for a one-off decision with large stakes a utility argument may favour the safer branch.

Where to start

Transportation first, north-west corner before the stepping-stone method. Allocation is self-contained and can be taken at any point. Cuts before maximum flow, since the theorem is stated in terms of them. Dynamic programming, game theory and decision analysis are independent of the network work and make a natural final block.