Skip to content
Tutorials Center
My learning

Topics

Linear Programming and Operations Research Tutorial

Learn Linear Programming and Operations Research step by step: 38 lessons in 9 chapters with examples, quizzes, diagrams and projects.

Start learning →

of lessons completed

Getting Started

  1. 1 What Is Linear Programming? Learn what linear programming is: decision variables, a linear objective, linear constraints and the feasible region, with a small production example you can run.
  2. 2 The Graphical Method Solve two-variable linear programs by drawing the feasible region, enumerating corner points and sliding the objective line, with runnable Python and a plot.
  3. 3 Solving LPs with SciPy's linprog Use scipy.optimize.linprog to solve linear programs: objective, A_ub, A_eq, bounds, maximizing, reading status, slack, duals and common input mistakes.
  4. 4 Standard Form and Slack Variables Convert any linear program to standard form with slack, surplus and split free variables, then see basic solutions, with a Python converter checked against linprog.

Modelling

  1. 5 Product Mix and Resource Allocation Learn the product mix model: define variables, build a resource matrix, add demand limits and minimum orders, and solve with linprog while reading the results.
  2. 6 Diet and Blending Problems Model the diet problem and blending (mixing) problems as minimum-cost linear programs with nutrient requirements, ratio constraints and proportion variables.
  3. 7 Transportation and Assignment Models Model the transportation problem and the assignment problem as linear programs with supply, demand and one-to-one constraints, then solve them in Python.
  4. 8 Multi-Period Planning and Inventory Models Model production planning over several periods with inventory balance equations, overtime, backorders and storage costs, solved as a linear program in Python.
  5. 9 Modelling Tricks: Absolute Values, Min-Max and Goals Make non-obvious problems linear: absolute values, minimize the maximum, maximize the minimum, goal programming and piecewise costs, with runnable Python.

Simplex Method

  1. 10 The Geometry of Linear Programs Understand why LP optima sit at vertices: convex sets, polyhedra, extreme points, basic feasible solutions, adjacency and the fundamental theorem, with Python checks.
  2. 11 The Simplex Method by Hand: Tableaux Learn the simplex method with tableaux: entering variable, ratio test, pivoting and optimality, working the bakery example step by step with Python tableaux.
  3. 12 Implementing Simplex in Python Write your own simplex solver in Python with NumPy: a tableau function with entering rules, ratio test, status codes and duals, tested against SciPy on random LPs.
  4. 13 Degeneracy, Cycling and Bland's Rule Understand degenerate vertices, stalling and cycling in the simplex method, run Beale's classic cycling example in exact fractions and fix it with Bland's rule.
  5. 14 Unbounded and Infeasible LPs Learn what unbounded and infeasible LPs mean, how simplex detects them, how to extract a ray, and how to find conflicting constraints with an elastic relaxation.
  6. 15 Two-Phase Simplex and Big-M Handle >= and = constraints in simplex with artificial variables: build a Phase 1 feasibility search, then Phase 2, compare with Big-M, and test against linprog.

Duality and Sensitivity

  1. 16 The Dual Problem Learn the dual of a linear program: the primal-dual conversion table, the economic meaning of dual variables, and a Python dual builder checked against linprog.
  2. 17 Duality Theorems and Complementary Slackness Understand weak duality, strong duality, the primal-dual outcome table and complementary slackness conditions, and verify them numerically with Python and linprog.
  3. 18 Shadow Prices and Sensitivity Analysis Learn shadow prices, reduced costs and sensitivity ranges for objective coefficients and right-hand sides, computed from the optimal basis in Python and verified by re-solving.

Integer Programming

  1. 19 Integer Programming Basics Learn what integer and mixed-integer linear programs are, why rounding an LP solution fails, what the LP relaxation bound means, and how to solve a MILP with SciPy.
  2. 20 Binary Variables and Logic Model yes/no decisions with 0-1 variables: knapsack, if-then and either-or rules, fixed charges and big-M constraints, all solved with SciPy milp.
  3. 21 Branch and Bound Understand branch and bound step by step: LP relaxations, branching on fractional variables, pruning by bound, node selection, and a from-scratch Python implementation.
  4. 22 Cutting Planes and Formulation Strength See why two correct integer models can solve very differently: LP relaxation strength, tight constraints, valid inequalities, cover cuts and Gomory cuts, with runnable examples.

Network Flows

  1. 23 Network Flow Models Learn network flow modelling: nodes, arcs, supply and demand, flow balance, minimum-cost flow, transshipment, and why network LPs always have integer solutions.
  2. 24 Shortest Paths as Flows Formulate shortest paths as minimum-cost flows, solve them with linprog, compare with Dijkstra and Bellman-Ford, and handle negative arcs, cycles and longest paths in DAGs.
  3. 25 Max Flow and Min Cut Compute maximum flow with augmenting paths and Edmonds-Karp, find the minimum cut, understand the max-flow min-cut theorem, and solve flow problems with SciPy and linprog.
  4. 26 The Transportation Problem Solve the classic transportation problem: model supplies, demands and unit costs as an LP, build starting solutions with northwest corner and least cost, and handle unbalanced cases.
  5. 27 The Assignment Problem Learn the assignment problem: the 0-1 model, why its LP is integral, the Hungarian algorithm steps, maximization and unbalanced cases, solved with SciPy linear_sum_assignment.

Scheduling and Queueing

  1. 28 Scheduling Basics and Dispatch Rules Learn scheduling vocabulary and optimal dispatch rules: SPT, EDD, weighted SPT, Moore-Hodgson and Johnson's rule for two-machine flow shops, checked with brute force in Python.
  2. 29 Critical Path Method Plan projects with the critical path method: build activity networks, run forward and backward passes, find slack and the critical path, use PERT estimates, and crash activities with LP.
  3. 30 Scheduling with MILP Model parallel-machine and single-machine scheduling as MILPs: assignment variables, makespan, disjunctive big-M ordering constraints, time-indexed ideas, compared with LPT and Smith's rule.
  4. 31 Queueing Fundamentals and the M/M/1 Queue Learn queueing theory basics: arrival and service processes, Kendall notation, utilization, Little's law and the M/M/1 formulas, verified with a simulation in Python.
  5. 32 Multi-Server Queues and Simulation Size service systems with M/M/c and Erlang C and Erlang B formulas, see the effect of service variability with M/G/1, and simulate multi-server queues with an event heap in Python.

Applications

  1. 33 Blending and Feed Mix Model blending problems as linear programs: the diet or feed mix problem, quality constraints written as weighted averages, shadow prices and a gasoline blending example in Python.
  2. 34 Multi-Period Production Planning Build production plans over several periods with inventory balance, overtime and backlog in an LP, then add setup costs for lot sizing with MILP and check it against Wagner-Whitin.
  3. 35 Finance and Data Fitting with LP Use linear programming beyond factories: least absolute deviation and minimax regression, absolute-value linearization, and minimum-CVaR portfolio optimization with scenarios, in SciPy.

Projects and Practice

  1. 36 Project: Facility Location Build a capacitated facility location model end to end: decide which warehouses to open and who they serve, solve with a MILP, verify by brute force, and run what-if scenarios.
  2. 37 Project: Staff Rostering Build a weekly staff schedule with integer programming: cover daily demand with five-day shifts, compare LP and MILP, derive demand from Erlang C queueing, and add weekend costs.
  3. 38 Practice Problem Set Eight practice problems on integer programming, transportation, max flow, assignment, scheduling, queues, blending and project planning, with runnable solutions and answers to check against.