Description

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, Relation to 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 Flows, Maximum Flow, Primal-Dual Transportation Algorithm, Summary. Karmakar’s Algorithm.

Learning Outcomes

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