Feb 25, 2024  
2018-2019 Undergraduate Academic Catalog 
2018-2019 Undergraduate Academic Catalog [ARCHIVED CATALOG]

Add to Portfolio (opens a new window)

MA 343 - Linear Programming

3 lecture hours 0 lab hours 3 credits
Course Description
This course introduces the fundamentals of linear programming methods. Topics include formulating real-life problems (such as production planning, inventory, shortest path and assignment problems) as linear programs, the simplex algorithm, geometry of feasible regions and optimal solutions, duality theory and complementary slackness conditions. Tools relating linear and integer programs such as Gomory cuts and branch-and-bound methods will also be introduced. (prereq: MA 231 )
Course Learning Outcomes
Upon successful completion of this course, the student will be able to:
  • Formulate various real-life problems as linear and integer programs
  • Be able to solve linear programs using the simplex algorithm
  • Be able to construct the dual problem of a general linear program
  • Understand the weak and strong duality relations for linear programs
  • Verify optimal solutions using duality theory and complementary slackness conditions
  • Execute the primal-dual algorithm to solve the shortest path problem
  • Tackle integer programs using linear programming tools such as Gomory cuts and branch-and-bound methods

Prerequisites by Topic
  • College algebra including basic operations and concepts with real vectors and matrices

Course Topics
  • Linear algebra review
  • Formulation of linear and integer programs
  • Outcomes of linear programs
  • Basic feasible solutions and the simplex method
  • The 2-phase method
  • Duality theory and complementary slackness
  • Primal-dual algorithm - shortest path problem
  • Gomory cuts and branch-and-bound

Bruce O’Neill

Add to Portfolio (opens a new window)