Skip to content

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.

22 chapters · 35 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    Geometry, simplex, and dual certificates

    Feasible polyhedra, basic solutions, simplex dictionaries, and independently checkable dual bounds.

  2. 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

  1. 2.1

    Flows, shortest paths, and certificates

    Residual networks, augmenting paths, cut certificates, and distance potentials.

  2. 2.2

    Bipartite matching and vertex-cover certificates

    Model assignment as flow and prove a matching-cover equality.

  3. 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

  1. 3.1

    Relaxation, branching, and integrality

    Integer models, valid bounds, branch and bound, cover inequalities, and unimodular network structure.

  2. 3.2

    0–1 knapsack by dynamic programming

    Derive a capacity recurrence, reconstruct a solution, and distinguish pseudo-polynomial time.

  3. 3.3

    Lagrangian upper bounds for discrete decisions

    Price a capacity constraint and certify an integer optimum.

  4. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 8.1

    Single-period inventory and marginal decisions

    Derive a discrete demand threshold from overage and underage costs.

  2. 8.2

    Critical paths and scheduling slack

    Derive earliest and latest activity times on an acyclic precedence network.

  3. 8.3

    A stationary single-server queue

    Derive the stable M/M/1 occupancy distribution and compare capacity choices.

  4. 8.4

    Finite-horizon decisions under uncertainty

    Derive Bellman's recursion and a time-dependent maintenance policy.

  5. 8.5

    Robust linear constraints under uncertain coefficients

    Derive worst-case constraints for independent intervals and coupled uncertainty.

  6. 8.6

    Convex resource allocation

    Derive and certify a quadratic allocation by completing the square.

  7. 8.7

    Economic order quantity and cycle costs

    Balance fixed ordering costs against average inventory in a deterministic model.

  8. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 27.1

    Set covering: models, relaxations and certificates

    Translate coverage decisions into an integer program and use a dual relaxation to certify bounds.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details