|Subject Area||Applications and Foundations of Computer Science|
|Semester||Semester 7 – Fall|
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