Deterministic Models in Optimization

The course will introduce fundamental topics in optimization at the undergraduate level. Some specific topics to be covered are: Formulations, Linear Programming, Simplex Method, Duality, Sensitivity Analysis, Transportation, Assignment Problems, Network Optimization Problems, Integer Programs, Nonlinear Optimization, and Game Theory.

Pre-requisites: Mathematical maturity at the level of a junior undergraduate student will be assumed. Prior coursework in Linear Algebra, Calculus and familiarity with Matrices is required.

Lectures

The following is a tentative list of lectures. Subject to change. Lecture slides will be posted a day before the lecture in Canvas.
  • Week 1
    • Introduction
    • Math Modeling, Linear Programs
    • LP Modeling
  • Week 2
    • LP Modeling, Linearization Techniques
    • Linearization Techniques, LP Standard Form
    • Graphic Method for Solving LPs
  • Week 3
    • Labor day
    • Optimality Test, Simplex Method Outline
    • Simplex Method Outline
  • Week 4
    • Simplex Method Initialization
    • Simplex Method Iterations and Termination
    • Tabular Form of Simplex Method
  • Week 5
    • Shadow Prices
    • Dual Problem and Primal-Dual Connections
    • Duality Theory
  • Week 6
    • Dual Simplex Method
    • LP and Simplex in Matrix Form
    • Simplex in Matrix Form, Entries of Tabular Form, Sensitivity Analysis
  • Week 7
    • Sensitivity Analysis
    • Game Theory
    • Game Theory: 2-player 0-sum games Solution Approaches
  • Week 8
    • LP Formulation 2-player 0-sum games and Consequences
    • Review for Exam 1
    • Exam 1
  • Week 9
    • Transportation Problem
    • Transportation Simplex Method
    • Unbalanced Transportation Problem, Assignment Problem
  • Week 10
    • Hungarian Algorithm for Assignment Problem
    • Exam 1 Discussion
    • LP Solving in Excel
  • Week 11:
    • Minimum Spanning Tree Problem
    • Shortest Path Problem
    • Max Flow Problem
  • Week 12
    • Max Flow: Augmenting Path Algorithm
    • Non-Linear Optimization: Unconstrained, Convex functions
    • Non-Linear Optimization: Minimizing Convex functions, Equality Constrained Non-linear Optimization
  • Week 13
    • Inequality Constrained Non-Linear Optimization
    • Algorithms for Non-Linear Optimization
    • Integer Programming
  • Week 14: Fall Break
  • Week 15
    • Math Modeling with Integer Variables
    • IP Solving Outline
    • IP Solving: Branch & Bound
  • Week 16
    • Math Modeling with Integer Variables
    • Review
  • Week 17
    • Exam 2