Feb 01, 2023  
2021-2022 Undergraduate Academic Catalog 
2021-2022 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 2314  or 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
  • Solve linear programs using the simplex algorithm
  • 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

Edward Griggs

Add to Portfolio (opens a new window)