APM 261F: Plan of Lectures (Fall, 1999)

1. Elementary introduction in linear programming (1.1-1.4)
• Operation research: phases and typical problems
• Classification and examples of linear programming problems
• Transformations of LP problems, slack variables
• Feasible region and optimal solutions, classification of solutions
• Geometric solution of a LP problem and the requirement space
2. Review of linear algebra and convex analysis (2.1-2.7)
• Vectors, linear independence and basis
• Matrices, elementary row and column operations
• Solving a linear system by Gauss--Jordan reduction
• Inverse and rank of matrices, classification of solutions of linear systems
• Convex set, extreme points, hyperplanes and halfspaces, directions
• Polyhedral sets, calculating extreme points, directions and extreme directions
• Representation theorem for polyhedral sets
3. The simplex method and modifications (3.1-3.8,4.1-4.2,4.6,5.1)
• Extreme points and basic feasible solutions of a LP problem
• The extreme point theorem and optimal solutions of a LP problem
• Geometric and algebraic motivations of the simplex method
• Transformation of a LP problem to the simplex form
• Steps of the simplex method, termination due to optimality and unboundedness
• Unique and alternative optimal solutions
• The simplex method in tableau format
• Artificial variables and the two-phase method
• Degeneracy, cycling, and stalling, rules that prevent cycling
• The revised simplex method, computation of the basis inverse
4. Duality and sensitivity analysis (6.1-6.4,6.7-6.8)
• Formulation of the dual LP problems
• The duality theorems and primal-dual relationships
• Complementary slackness, solving a primal problem through the dual problem
• Economic interpretation of duality
• The dual simplex method, identification of dual variables from a primal tableau
• Sensitivity analysis: variations of parameters, adding a new constraint
5. Complexity and polynomial algorithms (8.1-8.5)
• Polynomial and exponential complexity of algorithms
• Complexity of the simplex algorithm
• Karmarkar's projective algorithm
• Converting a general problem into the Karmarkar's form
• Sliding objective function method
6. Minimal cost network flows (9.1-9.7)
• Networks and oriented graphs, tree and forest graphs
• Formulation of the minimal cost problem as a LP problem
• Simplex method for network flow problems
• Finding an initial solution for network flow problems
7. The transportation problems and integer programming (10.1-10.6)
• Formulation of the transportation problem as a LP problem
• The transportation algorithm, finding an initial solution
• Integer programming: cutting planes method, branch and bound method