Skip to main content

Linear Programming - Overview

Introduction​

Overview of linear programming, the simplex method, duality, and applications to networks and game theory.

Key Concepts​

Linear Programming​

  • Standard form: minimize cᵀx subject to Ax = b, x ≥ 0
  • Feasible region
  • Basic feasible solutions
  • Optimal vertices

The Simplex Method​

  • Moving between vertices
  • Pivot operations
  • Tableau method
  • Degeneracy

Duality Theory​

  • Primal and dual problems
  • Weak and strong duality theorems
  • Complementary slackness
  • Economic interpretation

Network Models​

  • Max flow problems
  • Min cost flow
  • Assignment problems
  • Connection to graph theory

Game Theory​

  • Zero-sum games
  • Mixed strategies
  • Nash equilibrium
  • LP formulation

Applications​

  • Resource allocation
  • Supply chain optimization
  • Network routing
  • Strategic decision making

References​