Operations Research

Systems and Matrices ended with an objective and four inequalities already written down. This course is about writing them. It asks three questions in the same order — what do I decide, what do I want, what stops me — and answers them four times over on the model families that cover most of applied optimisation; then it shows which non-linear-looking requirements are secretly linear, converts everything to the one form the simplex method eats, and replaces the drawn corner with an algebraic object that survives ten variables. It ends with the single theorem that will later let an algorithm stop.

“Systems and Matrices” declined the simplex algorithm by name. This is it. Each step is a Gauss–Jordan pivot, the entering variable is chosen by a rate and the leaving one by a ratio that keeps every variable non-negative, and the method stops on the licence “Convexity, and Why a Local Optimum Is Global” gave it. Everything is exact, which is what makes the two famous pathologies — a tableau that returns to itself after six pivots, and a cube that forces 2ⁿ - 1 of them — reproducible on your screen rather than described in a footnote.

Every linear programme carries a second one whose variables are prices, and the simplex method has been solving both of them the whole time. That single fact is a tool: a final tableau will price a resource, bound the change that price survives, price a column that is not in the model yet, and reject a new constraint without a re-solve. The course ends where duality stops being bookkeeping — a Pareto front traced by one parameter, and a zero-sum game whose minimax theorem is strong duality with different nouns.

Draw a network, write the node equations, and the simplex method solves it. What makes this a course rather than a worked example is that the same matrix — one column per arc, a plus one at the tail and a minus one at the head — is every problem on it: change the supplies and a minimum-cost flow becomes a shortest path, a maximum flow, a transportation plan or an assignment. That matrix is totally unimodular, so every corner of every one of those programmes is whole on whole data, with no integrality constraint and no rounding; and the specialised methods that came before the simplex — potentials on a tableau, augmenting paths, the Hungarian reductions — turn out to be the dual programme, worked by hand.

Algebra’s “Systems of Inequalities and Linear Programming” closes by saying that rounding an optimal corner is not guaranteed to give the best whole-number answer — and that this is a different subject. This is the subject. Binary variables turn logic into inequalities; a big-M links a fixed cost to a decision and charges you for being careless about its size; and because integer problems are hard in the precise sense Discrete Mathematics gave the word, the tools that remain are bounds — from a relaxation, from a cut, from a search tree — and the certificate you finish with is a gap of zero, or an honest number.

This is the course on this path with no matrix in it. Five jobs on one machine have 120 orders and six reasonable objectives, and the order that wins on one of them is beaten on the others by a different order each time — so the first thing here is that a schedule is not good, it is good at something. The rules that follow are all proved the same way and none of them needs calculus: take two jobs standing next to each other, swap them, and compute the exact quantity the swap moved. That one subtraction gives shortest-processing-time, Smith’s ratio and earliest-due-date, and it is honest about the two places it does not reach. Then the machine count goes up: two in series still has an exact rule, m in parallel has a heuristic with a bound proved from two lower bounds, and a shop where each job has its own route has neither — one binary choice per shared machine, and some combinations of those choices describe no schedule at all.

Every method so far on this path has been a way of solving one big object. This course takes the opposite view: a decision made once is a decision made in a state, the state carries into the next decision, and the whole sequence collapses into a table you can fill in one pass from the end. The recursion is four lines and it is exact — these are not approximations and nothing here converges. But it is exact about the state you wrote down, and a state that leaves something out gives a table whose every entry is right and whose answer is wrong, with no symptom on the page. That is this path’s hazard at its sharpest, so every lab here computes its answer a second time by enumerating every path, every split, every order pattern, every policy, every strategy and every accept-set, and shows the two numbers side by side. Two of the lessons exist because the second number disagrees with something a reader would otherwise have assumed.

This is the course where the answer is a formula, which makes it the course where the formula most needs taking apart. The economic order quantity is √(2KD/h) and it arrives here from a quadratic inequality whose two roots collide — the same discriminant Algebra uses, applied to a budget — so that existence, uniqueness and optimality come out of one argument with no calculus in it. The claim that the cost curve is flat either side of the optimum is then computed rather than repeated: ordering t times the best quantity costs (t + 1/t)/2 times the minimum, an expression containing none of the data, so “within one per cent” is 13.2% below to 15.2% above in every warehouse there has ever been. After that the assumptions come off one at a time — a price that depends on the order, a run that takes time, a shortage that was planned, and finally a demand that is a random variable rather than a rate.

Everything on this course comes out of one matrix or one equation, and the point of it is a distinction that is easy to state and easy to lose: a steady state is the solution of a linear system, not the limit of anything. On one matrix here the system has exactly one answer and the powers never converge at all — they return to the identity every third step, for ever — so the two ideas can be seen coming apart rather than argued about. The second half turns the same machinery on queues. Cut the chain between two states, balance the crossings, and M/M/1, several servers, a finite waiting room and a customer who declines to join are four readings of one equation rather than four formulas; the closed forms are borrowed from the System Design path so that two Subjects cannot disagree about the same model. Every figure is an exact fraction except one, which is named.

Every other course on this path ends in a proof: a tableau is optimal, a corner is whole, a sequence is best by an exchange argument, a steady state is the solution of a linear system. This one ends in an interval. Simulation is the method of last resort, and what makes it a method rather than a guess is the discipline around the number it produces — a stream whose period has been certified, an estimator whose bias has been computed rather than hoped away, a guarantee that assumes nothing about the distribution, and a variance reduction measured against the honest comparison instead of the flattering one. The hazard the whole path warns about bites hardest here, because the output now carries sampling noise on top of it: a simulation of the wrong model is wrong in a way that more runs make look more convincing.