MATH3215
Operations Research
Linear programming and the simplex method, duality and sensitivity, network flows and shortest paths, transportation problems, and integer programming by relaxation, branching and cuts.
Your progress
0/ 35 sections marked complete
Next section: Geometry, simplex, and dual certificates
Completion marks are saved in this browser.
This course in the web
In the MATH3215 notes
- Theorem cards
- 74
- Definitions
- 41
- Counterexamples
- 34
- Concept lenses
- 16
- Histories of ideas
- 0
- Proof X-rays
- 36
No concept lens from this course is recorded in the web yet.
Counts cover the 35 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 74 · Definitions 41 · Counterexamples 34 · Concept lenses 16 · Proof X-rays 36
No concept lens from this course is recorded in the web yet.
Counts cover the 35 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 2 sections
Geometry, simplex, and dual certificates
Feasible polyhedra, basic solutions, simplex dictionaries, and independently checkable dual bounds.
Theorems 2 · Definitions 1Counterexamples 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Geometry, simplex, and dual certificates
Feasible polyhedra, basic solutions, simplex dictionaries, and independently checkable dual bounds.
- 1.2
Zero-sum games as linear programs
Derive mixed-strategy guarantees and certify a game value by duality.
Chapter 2 · 3 sections
Flows, shortest paths, and certificates
Residual networks, augmenting paths, cut certificates, and distance potentials.
Theorems 8 · Definitions 4Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Flows, shortest paths, and certificates
Residual networks, augmenting paths, cut certificates, and distance potentials.
- 2.2
Bipartite matching and vertex-cover certificates
Model assignment as flow and prove a matching-cover equality.
- 2.3
Transportation plans and dual prices
Build balanced shipping models and certify minimum cost with potentials.
Chapter 3 · 4 sections
Relaxation, branching, and integrality
Integer models, valid bounds, branch and bound, cover inequalities, and unimodular network structure.
Theorems 10 · Definitions 5Counterexamples 4Lenses 1Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Relaxation, branching, and integrality
Integer models, valid bounds, branch and bound, cover inequalities, and unimodular network structure.
- 3.2
0–1 knapsack by dynamic programming
Derive a capacity recurrence, reconstruct a solution, and distinguish pseudo-polynomial time.
- 3.3
Lagrangian upper bounds for discrete decisions
Price a capacity constraint and certify an integer optimum.
- 3.4
Binary decisions and mixed-integer modeling
Construct and verify on/off, fixed-charge, disjunctive and product formulations.
Chapter 4 · 1 section
Revised simplex, Phase I, and lexicographic pivots
Basis solves, artificial-variable cleanup, an exact cycling trace, and lexicographic termination.
Theorems 2 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Revised simplex, Phase I, and lexicographic pivots
Basis solves, artificial-variable cleanup, an exact cycling trace, and lexicographic termination.
Chapter 5 · 1 section
Farkas' alternative, strong duality, and sensitivity
Closed-cone proofs of alternatives, attainment and dual multipliers, with exact parameter regions.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Farkas' alternative, strong duality, and sensitivity
Closed-cone proofs of alternatives, attainment and dual multipliers, with exact parameter regions.
Chapter 6 · 1 section
Minimum-cost flows, potentials, and assignment
Residual-cycle optimality, global price certificates, transportation exchanges, and finite assignment updates.
Theorems 2 · Definitions 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Minimum-cost flows, potentials, and assignment
Residual-cycle optimality, global price certificates, transportation exchanges, and finite assignment updates.
Chapter 7 · 1 section
Fractional cuts and finite integer search
Pure-integer tableau cuts, aggregated rounding, strength comparisons, and finite branch-and-cut assumptions.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Fractional cuts and finite integer search
Pure-integer tableau cuts, aggregated rounding, strength comparisons, and finite branch-and-cut assumptions.
Chapter 14 · 1 section
Transportation feasibility
Use cuts to determine feasible routes.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
Transportation feasibility with forbidden routes
Use residual paths and cut certificates to decide whether allowed routes can meet all balances.
Chapter 15 · 1 section
Bland's rule and finite simplex termination
Prove noncycling with fixed variable indices, a null-space cost identity, and both pivot choices; follow two zero steps before improvement.
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
Bland's rule and finite simplex termination
Prove noncycling with fixed variable indices, a null-space cost identity, and both pivot choices; follow two zero steps before improvement.
Chapter 16 · 1 section
Lower bounds, balances, and cut certificates
Transform mandatory flows correctly, prove a complete feasibility criterion, and diagnose capacitated transportation bottlenecks.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Lower bounds, balances, and cut certificates
Transform mandatory flows correctly, prove a complete feasibility criterion, and diagnose capacitated transportation bottlenecks.
Chapter 17 · 1 section
Column generation, pattern pricing, and dual certificates
Solve a large linear relaxation by generating useful patterns and certify when no omitted pattern can improve it.
Theorems 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 17.1
Column generation, pattern pricing, and dual certificates
Solve a large linear relaxation by generating useful patterns and certify when no omitted pattern can improve it.
Chapter 18 · 1 section
Cost certificates for flows with lower bounds
Use residual cycles and node prices to optimize a feasible flow with mandatory arc bounds.
Theorems 1 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 18.1
Cost certificates for flows with lower bounds
Use residual cycles and node prices to optimize a feasible flow with mandatory arc bounds.
Chapter 19 · 1 section
Basis updates and transpose solves
Derive product-form basis updates and use them in revised simplex calculations.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 19.1
Basis updates and transpose solves
Derive product-form basis updates and use them in revised simplex calculations.
Chapter 8 · 8 sections
Decision models
Demand uncertainty and marginal decisions.
Theorems 16 · Definitions 11Counterexamples 8Lenses 1Proof X-rays 8
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Single-period inventory and marginal decisions
Derive a discrete demand threshold from overage and underage costs.
- 8.2
Critical paths and scheduling slack
Derive earliest and latest activity times on an acyclic precedence network.
- 8.3
A stationary single-server queue
Derive the stable M/M/1 occupancy distribution and compare capacity choices.
- 8.4
Finite-horizon decisions under uncertainty
Derive Bellman's recursion and a time-dependent maintenance policy.
- 8.5
Robust linear constraints under uncertain coefficients
Derive worst-case constraints for independent intervals and coupled uncertainty.
- 8.6
Convex resource allocation
Derive and certify a quadratic allocation by completing the square.
- 8.7
Economic order quantity and cycle costs
Balance fixed ordering costs against average inventory in a deterministic model.
- 8.8
Multi-server queues and Little's law
Derive the stationary distribution of the M/M/c queue, compute waiting probability and mean delay, and relate queue lengths to waiting times by Little's law.
Chapter 20 · 1 section
Linear programming models for deviations and worst cases
Build and verify exact linear formulations for absolute deviations and minimax objectives.
Theorems 1 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 20.1
Linear programming models for deviations and worst cases
Build and check exact linear formulations for absolute deviations and minimax objectives.
Chapter 21 · 1 section
Dual simplex and reoptimization certificates
Dual-feasible pivots, failed-row Farkas certificates, formal anti-cycling, and cost versus requirement changes.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 21.1
Dual simplex and reoptimization certificates
Maintain dual feasibility while repairing basic values, derive the dual ratio test, and distinguish right-hand-side from cost changes.
Chapter 22 · 1 section
Objective coefficients and optimal basis ranges
Derive cost sensitivity ranges from reduced costs and interpret their limits.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 22.1
Objective coefficients and optimal basis ranges
Derive cost sensitivity ranges from reduced costs and interpret their limits.
Chapter 23 · 1 section
Transportation bases: trees, degeneracy, and prices
Use a transportation tree to calculate a shipment exchange and certify its optimum.
Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 23.1
Transportation bases: trees, degeneracy, and prices
Use a transportation tree to calculate a shipment exchange and certify its optimum.
Chapter 24 · 1 section
Bellman–Ford: shortest walks and negative cycles
Derive the edge-limited recurrence and classify finite, unreachable, and unbounded distances.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 24.1
Bellman–Ford: shortest walks and negative cycles
Derive the edge-limited recurrence and classify finite, unreachable, and unbounded distances.
Chapter 25 · 1 section
Minimum spanning trees: cuts, cycles, and Kruskal's algorithm
Build a cheapest spanning tree and justify its edges by exchange.
Theorems 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 25.1
Minimum spanning trees: cuts, cycles, and Kruskal's algorithm
Build a cheapest connected network and justify each choice by an exchange argument.
Chapter 26 · 1 section
Network simplex: tree pivots and bound flips
Follow a bounded network-simplex step using tree balances, residual capacities and node prices.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 26.1
Network simplex: tree pivots and bound flips
Follow a bounded network-simplex step using tree balances, residual capacities and node prices.
Chapter 27 · 1 section
Set covering: models, relaxations and certificates
Translate coverage decisions into an integer program and use a dual relaxation to certify bounds.
Theorems 3 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 27.1
Set covering: models, relaxations and certificates
Translate coverage decisions into an integer program and use a dual relaxation to certify bounds.