| |
Nov 23, 2024
|
|
|
|
|
MA 343 - Linear Programming3 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
Coordinator
Yu Hin (Gary) Au
Add to Portfolio (opens a new window)
|
|
Skip to Main Content
