Math Models of OR, Fall 2021.
MATP4700.
Contents of this page:
Course basics 
Grades 
Homeworks 
Exams 
Project 
Notes 
Homework solutions 
Handouts 
Other resources
Scores on Exam 1:
98
94
92
89
89
88
88
87
86
86
85
84
83
83
82
81
80
79
79
79
77
76
73
73
73
70
69
69
69
68
67
65
65
64
64
62
62
61
58
58
58
56
54
54
49
47
42
40
28

Exam 1 will be in class on Tuesday, October 5.
Old exams are on LMS. The topics covered will be similar, coming from the
first 9 lectures, but the format may be somewhat different:
it will probably be constructed so that it is easier to grade.
You can bring one 8.5x11 sheet of paper with handwritten notes
(no scanning or photocopying!) You can write on both sides.
 Solutions to Exam 1:
Version A,
Version B,
Version C.

Exam 2 will be on Tuesday, November 9.

Exam 3 will be on Friday, December 10.
These are typed pdf files.
The notes are available on
LMS
and
Box.
Section numbers given in parentheses correspond to those used
in the text by Mike Kupferschmid available on LMS (draft of August 12, 2020);
coverage and emphasis is somewhat different, but the text is good for at
least background reading.
Formulating linear optimization problems
 Lecture 1
 Introduction: 01A_intro
(0.1, 1.1, 1.2)
 Some examples: 01B_more_examples
(1.3)
 Some contemporary applications of optimization
(not covered in 2020):
01C_optimization_applications
 Links to the
lecture.
 Lecture 2

Two models from the text (1.1, 1.3).
 Standard form: 02A_standardform
(2.1,2.9)
 Handling minmax and absolute values: 02B_maxmin
(1.5)
 Simplex tableaus: 02C_tableaus
(2.2)
 Links to the
lecture.
Solving linear optimization problems
 Lecture 3
 Pivoting: 03A_pivoting
(2.3)
 Choosing the pivot element: 03B_choosingpivot
(2.4)
 Optimal and unbounded forms: 03C_optimalform
(2.5)
 Solving a linear optimization problem: 03D_solvingLOP
(2.6)
 Links to the
lecture.
 Lecture 4
 Some definitions: 04A_definitions
 The method of artificial variables: 04B_artificial
(2.8)
 Possible outcomes for the method of artificial variables: 04C_artificial_cases
(2.8)
 Links to the
lecture.
 Lecture 5
 Degeneracy: 05A_degeneracy
(4.5)
 An example of cycling: 05B_egcycling
(4.5)
 More on geometry of linear optimization problems: 05C_geometry
(3.1,3.2,3.3)
 Links to the
lecture.
 Lecture 6
 Revised simplex: 06A_revisedsimplex
(4.2)
 An example of revised simplex: 06B_revisedsimplexexample
(4.2)
 Links to the
lecture.
 Lecture 7
 Equivalence of extreme points and basic feasible solutions:
07A_bfsextreme
 Multiple optimal solutions: 07B_multipleoptima
(3.4)
 Links to the
lecture.
 Lecture 8
 Convexity: 08A_convexity
(3.5)
 Handling upper bounds: 08B_upperbounds
 The KleeMinty cube: 09A_kleeminty
 Links to the
lecture.
 Lecture 9
 Implementing simplex: 09B_simplex
(4.1,4.4)
 Introduction to AMPL: 09C_ampl. You don't need to look at AMPL until after
Exam 1.
 Links to the
lecture.
 Lecture 10
Duality in linear optimization
 Lecture 11
 Motivations for the dual problem: 11A_duality_motivation
 Relations between primal and dual problems: 12A_dualityrelations
(5.1)
 Constructing a dual problem: 12B_dual_construction
(5.2)
 Links to the
lecture.
 Lecture 12
 Strong duality: 12C_strongduality
(5.1)
 Complementary slackness: 13B_complementaryslackness
(5.1.5)
 Links to the
lecture.
 Lecture 13
 Economic interpretation of dual variables: 13A_shadowprices
(5.1.4)
 Constructing dual solutions using complementary slackness: 13C_dualcs
 The dual simplex algorithm: 14A_dualsimplex
(5.3)
 Links to the
lecture.
 Lecture 14
 Sensitivity analysis: 14C_sensitivityanalysis
(5.4)
 Links to the
lecture.
 Lecture 15
 Theorems of the alternative: 15A_farkas
(Exercise 5.5.29)
 Dual simplex and simplex applied to the dual: 14B_dualsimplexindual
(5.3.2)
 Exploiting complementary slackness: 13D_f94cs
 Links to the
lecture.
Problems on networks
 Lecture 16
 The transportation problem: 15B_transportation
(5.2.2, 6.1)
 Applying simplex to the transportation problem: 16A_trans_simplex
(6.1)
 Solving a transportation problem: 16B_trans_solve
(6.1)
 The assignment problem and variants of transportation problems: 16C_assignment
(6.2, 6.5.3)
 Links to the
lecture.
 Lecture 17
 Minimum cost flows on general networks: 17A_genneral_networks
(6.3, 6.4)
 Network simplex: 17B_networksimplex
(6.5)
 Information about AMPL.
 The NEOS Server:
state of the art solvers for numerical optimization.
You can submit your optimization problems written in AMPL
(or other modelling languages)
to this cloud solver.
 The NEOS
optimization guide.

Fourer, Gay, and Kernighan; AMPL: A Modeling Language for Mathematical Programming. The
Scientific Press, Second Edition, 2002. This is the handbook for AMPL and is used for the project.
Available online at http://ampl.com/resources/theamplbook/

Ferris, Mangasarian, and Wright: Linear Programming with MATLAB. SIAM, 2007. Electronic
resource available via the library.

Lee, A First Course in Linear Optimization, Reex Press, 2013–16, available online at
https://github.com/jon77lee/JLee_LinearOptimizationBook/blob/master/LPBook2.95.pdf
 Myths
and counterexamples in optimization. This site shows that you have
to be careful about your assumptions when you state some things that are
"obvious" in linear programming.
 A list of operations research sites.
 RIOT:
Baseball Playoff Races. This site uses linear programming
to determine when a baseball team is eliminated from contention.
John Mitchell's homepage.