Linear Programming

Course Objective

This is the first course in mathematical programming and covers models and methods of linear programming and its extensions. The emphasis is on the theory and algorithms. This is the first in a series of courses in optimization techniques and models. The follow-up courses cover quadratic programming, general nonlinear programming, network flows and integer programming, etc.

Office Hours

EC 4504
972-883-2032

TAs

TBA

Text

Linear Programming, by Katta G. Murty, J. Wiley, 1983

Linear programming and its Extensions, by G.B. Dantzig, Princeton University Press, 1963.

Prerequisites

OPRE 6201; or consent of the instructor.

Grading Scheme

Homework and two exams

Course Outline

Introduction
- Definition
- Formulations of well known and cook book problems
Algorithms
- Linear Algebra
- Linear Independence
- The Simplex Algorithm and Two Phases of the Simplex Method
- Simplex Algorithm in Matrix Form
- Revised Simplex Method
  - Explicit Inverse
  - Product Form
  - Column Generation
- Finiteness of the Simplex Method and Methods for Resolving Degeneracy
  - Inductive Method
  - Lexicography and Perturbation
  - Bland's Rule
  - Other Rules
- Sensitivity Analysis and Parametric Programming
- Bounded Variables and Separable Programming
Algebra: Theory and Algorithms
- Duality Theory
- Algorithms Based on Duality
  - Dual Simplex
  - Self Dual
  - Primal Dual
- Linear Inequality Theory and Theorems of the Alternative
- Fourier Elimination
Geometry
- Convexity
- Adjacent Vertex Methods and Fractional Programming
  - Charnes-Cooper
  - Isbell-Marlowe
  - Martos-Charnes
  - Dinkelbach-Jagannathan
Extensions
- Separable Convex Programs
- Convex Quadratic Programs and Linear Complementarity
Special Linear Programs
- Network Problems and Total Unimodularity
- Large LP
  - Decomposition Principle
  - Generalized Upper Bounding

Assignments

Click here to go back ...