COURSE TOPICS OUTLINE - C &O 350

• Major Topics
  • Sub-topics
    • Resources for the different topics are included.

• Introduction to LP ( Chapter 1)
  • Linear Programming Applications
    diet and production problems
    • The Diet Problem: An Application of Linear Programming, a description, software, etc... (from the Optimization Technology Center).
  • LP Models
    different constraints (equality, inequality), maximize or minimize, free variables
  • Geometry
    feasible set, determination of optimal solutions
  • Definitions
    linear function, linear constraints, linear equation, linear inequality, linear program (LP), standard form, objective function, non-negativity constraints, feasible solution, feasible set, convex set, extreme point, optimal solution, optimal value, infeasible LP, unbounded LP. decision variables, slack variables.
  • Related Resources:
    • FAQ (frequently asked questions) on linear programming
    • Systems Analysis laboratory, with lots of applications and modelling; and applied problems.
    • Optimization Technology Center, contains library, technology, guide. Solves problems on line. See their optimization tree It introduces the different subfields of optimization and includes outlines of the major algorithms in each area, with pointers to software packages where appropriate.
• How the Simplex Method Works ( Chapter 2)
  • Dictionaries
    Basic Solutions and Basic Feasible Solutions (BFS)
    Though dictionaries are used, the linear algebra is emphasized.
  • Tableau
    The dictionary is used for deciding which variable enters the basis; while the tableau is used to do the pivoting.
    • LPs in Equality Form
  • Equivalent Forms
    link to linear algebra
  • Phase I
    finding an initial BFS for an LP in equality form
  • Definitions
    decision variables, slack variables, dictionary, BFS, tableau, ratios, pivoting, pivot element.
• Pitfalls ( Chapter 3)
  • Initialization
    finding an initial BFS
  • Degeneracy and Cycling
    Bland's Rule, Lexicographic Rule, Theorems on termination
  • Fundamental Theorem of LP (in standard form)
• Duality ( Chapter 5)
  • Derivation Using Bounds
  • Strong and Weak Duality
  • Complementary Slackness
  • Economic Significance
• Revised Simplex Method ( Chapter 7 (pgs 97-105))
  • Economic Interpretation
• General LP Problems ( Chapter 8 (NO upper and lower bounds on the variables)
  • The Two-Phase Method
  • Getting Rid of Artificial Variables
  • The Fundamental Theorem of LP for General LPs
• General LP Problems: Duality and Infeasibility ( Chapter 9 )
  • Farkas' Lemma
• Sensitivity Analysis ( Chapter 10 )
  • The coefficient of a nonbasic variable in the objective function is changed.
  • The coefficient of a basic variable in the objective function is changed.
  • A new variable is added.
  • A component of the right hand side b is changed.
  • A new constraint is added.
    • sensitivity analysis notes
• Integer Programming
  • Gomory's cutting plane method notes