Course Description

Linear programming, game theory, PERT, network analysis; duality theory and sensitivity analysis; applications. Computer programs written to implement several techniques. Prerequisites: CS 2010 and MATH 2220 or equivalent.

Course Syllabus

1. Examples of Optimization Problems
2. Introduction to Linear Programming
3. The Simplex Algorithm and Goal Programming
   1. Converting an LP to Standard Form
   2. Using the Simplex Method to Solve Minimization Problems
   3. Alternative Optimal Solutions
   4. Unbounded LPs
   5. The Lindo Computer Package
   6. Degeneracy and the Convergence of the Simplex Algorithm
   7. The Big M Method
   8. The Two-Phase Simplex Method
   9. Solving LPs with Spreadsheets
4. Sensitivity Analysis: An Applied Approach
   1. A Graphical Introduction to Sensitivity Analysis
   2. The Computer and Sensitivity Analysis
5. Sensitivity Analysis and Duality
   1. Finding the Dual of an LP
   2. Economic Interpretation of the Dual Problem
   3. The Dual Theorem and Its Consequences
   4. Shadow Prices
   5. Duality and Sensitivity Analysis
   6. Complementary Slackness
   7. The Dual Simplex Method
6. Transportation and Assignment Problems
   1. Formulating Transportation Problems
   2. Finding Basic Feasible Solutions for Transportation Problems
   3. The Transportation Simplex Method
   4. Sensitivity Analysis for Transportation Problems
   5. Assignment Problems
7. Network Models
   1. Shortest Path Problems
   2. Maximum Flow Problems
   3. CPM and PERT
   4. Minimum Cost Network Flow Problems
   5. Minimum Spanning Tree Problems
   6. The Network Simplex Method
8. Integer Programming:
   1. Formulating Integer Programming Problems
   2. The Branch-and-Bound Method for Solving Pure Integer Programming Problems
   3. The Branch-and-Bound Method for Solving Mixed Integer Programming Problems
   4. Solving Knapsack Problems by the Branch-and-Bound Method
9. The Revised Simplex Algorithm
10. Game Theory

Course Project