everything.study
MATH 3801

Linear Programming

0.5 credit · Undergraduate

Systems of linear inequalities, formulation of linear programming problems, geometric method, the simplex method, duality theory, complementary slackness, sensitivity analysis, branch-and-bound method and cutting plane method for integer linear programming, applications and extensions.

2022

Topics

  • Graphing Systems of Inequalities
  • Fourier Motzkin Elimination
  • Fundamental Theorem of Linear Programing
  • Duality
  • Complementary Slackness
  • Convex Sets and Extreme Points
  • Linear Programs in Standard Form
  • Simplex Method
  • Auxiliary Linear Programs and Two-Phase Method
  • Bland’s Rule
  • Simplex Tableau Method
  • Sensitivity Analysis
  • Dual Simplex Method
  • Dual Simplex Tableau Method
  • Directed Graphs and Network Flows
  • Network Simplex Method
  • Auxiliary Networks and Finding Initial Feasible Trees
  • Knapsack Problem
  • Method of Branch and Bound for Integer Programming Problems
  • Method of Cutting Plane for Integer Programming Problems

Readings

  • As a reference textbook, you can use Linear Programming – An Introduction with Applications (Second Edition) by Alan Sultan. This is not a mandatory textbook, and all
  • Course Overview: Systems of linear inequalities, formulation of linear programming problems, geometric method, the simplex method, duality theory, complementary slackness, sensitivity

Prerequisites & course information

Precludes additional credit for ECON 4004 , SYSC 3200 . Prerequisite(s): MATH 2152 or MATH 2107 , or permission of the School. Lectures three hours a week and one hour tutorial.

Sources