Skip to content

Full index

Linear functions, polyhedra and linear programming problems

  1. Linear functions
    • 1.1 Linear functions
  2. Half-spaces and polyhedra
    • 2.1 Half-spaces and supporting hyperplanes
    • 2.2 Polyhedra
  3. Linear optimization problems
    • 3.1 Linear Programming problems
    • 3.2 Examples and properties of linear optimization problems
  4. Linear Programming problems
    • 4.1 Canonical maximization form
    • 4.2 Standard maximization form
  5. Possible outcomes and equivalent formulations
    • 5.1 The two reference forms
    • 5.2 Infeasible and unbounded LP problems
    • 5.3 Equivalent reformulations

The simplex algorithm

  1. Simplex algorithm
    • 6.1 The standard form of an LP problem in canonical max form
    • 6.2 Basis of the LP problem in standard form and dictionaries
    • 6.3 Pivoting operations
    • 6.4 High-level pseudo-code of the simplex algorithm
  2. Optimality conditions and pivot rules
    • 7.1 Sufficient conditions for optimality
    • 7.2 Necessary conditions for optimality
    • 7.3 Pivot rules
  3. Phase 0 of the simplex algorithm
    • 8.1 The simplex auxiliary problem
    • 8.2 Solving the simplex auxiliary problem
    • 8.3 From the Phase \(0\) to the simplex algorithm
    • 8.4 Detecting infeasible LP problems
    • 8.5 Pseudo-code of the simplex algorithm with the Phase \(0\)
    • 8.6 The Fundamental Theorem of Linear Programming

Duality and the dual simplex

  1. Duality theory
    • 9.1 Dual problem of an LP problem in canonical max form
    • 9.2 Primal and dual problems: possible outcomes
    • 9.3 Complementary Slackness
    • 9.4 Dual problem of a generic LP problem
  2. Dual Simplex algorithm
    • 10.1 Pair of primal and dual problems
    • 10.2 Primal and dual feasible bases
    • 10.3 Finding an initial dual basic feasible solution
    • 10.4 Dual pivoting operations
    • 10.5 Pseudo-code of the dual simplex algorithm
    • 10.6 Solving the dual problem with the simplex algorithm

Matrix methods, sensitivity and geometry

  1. Revised simplex algorithm
    • 11.1 Pivoting operations with two systems of linear equations
    • 11.2 Pseudo-code of the revised simplex algorithm
  2. Revised dual simplex algorithm
    • 12.1 Pivoting operations with two systems of linear equations
    • 12.2 Updating the reduced costs
    • 12.3 Pseudo-code of the revised dual simplex algorithm
    • 12.4 Execution of the revised dual simplex algorithm
  3. The primal-dual method
    • 13.1 The reference pair of primal and dual problems
    • 13.2 The restricted primal problem
    • 13.3 The dual step
    • 13.4 Pseudo-code of the primal-dual method
    • 13.5 Execution of the primal-dual method
    • 13.6 Comparison with the simplex algorithms
  4. Sensitivity analysis
    • 14.1 Optimal bases and their two conditions
    • 14.2 Changes in the objective-function vector
    • 14.3 Changes in the right-hand-side vector
    • 14.4 Adding a new variable
    • 14.5 Adding a new constraint
    • 14.6 Summary
  5. The geometry of Linear Programming
    • 15.1 The dimension of a polyhedron
    • 15.2 Faces, facets and vertices
    • 15.3 Basic feasible solutions and vertices
    • 15.4 The Fundamental Theorem, geometrically
    • 15.5 Summary

Modelling

  1. Linear Programming modeling techniques
    • 16.1 From a problem description to an LP model
    • 16.2 Production planning
    • 16.3 Blending
    • 16.4 Transportation
    • 16.5 Multi-period planning
    • 16.6 Linearization techniques
    • 16.7 What cannot be modeled with Linear Programming