ECE337 Linear Programming

Introduction: Optimization, Problems encountered, Size of Problems, Iterative Algorithms and their Convergence. Basic Properties of Linear Programs: Introduction, Examples of Linear Program Problems, Basic Solutions, The Fundamental Theorem of Linear Programming, Relations to Convexity. Simplex Method: Pivots, Adjacent Extreme Points, Determination of Minimum Feasible Solution.Computational Procedures—Simplex Method: Artificial Variables, Variables with Upper Bounds.Matrix Form of Simplex Method, Revised Simplex Method, Duality: Dual Linear Programs, The Theorem of Duality, Relationto the Simplex Procedure,Sensitivity and Complementarity Slackness, Simplex Dual Method. Primal-Dual Algorithm, Reduction of Linear Inequalities (Redundant Equations, Null Variables, Non-external Variables, Applications).Transportation and Flow Network Problems: The Transportation Problem, Determination of a Basic Feasible Solution, Triangulation of Basis, Simplex Method for Transportation Problems, The Assignment Problem, Basic Network Concepts, Minimum Cost Flowς, Maximum Flow, Primal-Dual Transportation Algorithm, Summary. Karmakar’s Algorithm.

Students will be able to

• Understand the basic concepts of Linear Programming
• Model real life practical optimization problems of certain complexity as Linear Programming problems
• Solve practical Linear Programming as those that are produced from various applications. (E.g., economics,networks)
• Analyze the accuracy and other characteristics of the obtained solutions