| Class Number
| Date
| Topics
| Reading
| HW Assigned
| HW Due
| | 1
| 9/4
| Introduction, Administration, Examples of mathematical programs
| Chapter 1
|
|
|
| 2
| 9/6
| Formulation of LP, solving 2-d LPs graphically, extreme points,
feasible and infeasible LPs, bounded and unbounded LPs
| Chapter 3.1 - 3.3
|
|
|
| | | | | | |
| 3
| 9/11
| Examples and modelling
| Chapter 3.4 - 3.7
| HW 1
|
|
| 4
| 9/13
| Standard form, basic and non-basic variables,
basic feasible solutions, directions, beginning of simplex algorithm
| Chapter 4.1,4.2, note on BFS and theorem 1
|
|
|
| R1
|
| Review of linear algebra
| Chapter 2
|
|
|
| | | | | | |
| 5
| 9/18
| Simplex algorithm:directions, BFS existence and Representation theorems, geometry of basic solutions
| Chapter 4.2-4.4, proofs of theorems 2 and 3
| HW 2
| HW 1
|
| 6
| 9/20
| Simplex algorithm: the tableau, examples
| Chapter 4.5- 4.8
|
|
|
| R2
|
| Examples of linear programs.
| Chapter 3.8
|
|
|
| | | | | | |
| 7
| 9/25
| Simplex algorithm, degeneracy, complexity, Big M
| Chapter 4.8, 4.11, 4.12, 4.14
| HW 3
| HW 2
|
| 8
| 9/27
| degeneracy continued, multiple optimal solutions, free variables, multiperiod LP examples.
| Cycling handout,
chapter 4.8, 4.14, 3.10-3.12
|
|
|
| R3
|
| The simplex algorithm with Big-M
| Chapter 4.12
|
|
|
| | | | | | |
| 9
| 10/2
| LINDO, LPs in Excel, Duality
| Chapter 4.9, 4.10, 4.17, 6.5, files from class, mcdiet.xls
| HW 4
| HW 3
|
| 10
| 10/4
| Duality
| Chapter 6.2, 6.5, 6.7
|
|
|
| R4
|
| Multiperiod models, Duality
| Chapters 3.12, 6.5
|
|
|
| | | | | | |
| 11
| 10/9
| Midterm Review
|
|
| HW 4
|
| 12
| 10/11
| Midterm 1
|
|
|
|
| R5
|
| Midterm Review (Wed.)
|
|
|
|
| | | | | | |
| 13
| 10/16
| Sensitivity analaysis
| Chapter 6.1-6.2
| HW 5
|
|
| 14
| 10/18
| Sensitivity analysis, shadow prices
| Chapter 6.3,6.6,6.8
|
|
|
| R6
|
| Duality
|
|
|
|
| | | | | | |
| 15
| 10/23
| Duality and sensitivity analysis, Dual Simplex
| Chapter 6.8, 6.9, 6.11
| HW 6
| HW 5
|
| 16
| 10/25
| Transportation problems, transportation simplex
| Chapter 7.1-7.3
|
|
|
| R7
|
| Complementary Slackness
| Chapter 6.10
|
|
|
| | | | | | |
| 17
| 10/30
| Transportation simplex, LINGO.
| Chapter 7.3, Chapter 4:appendices B-C
| HW 7
| HW 6
|
| 18
| 11/1
| Assignment problem and Hungarian Algorithms
| Chapter 7.5
|
|
|
| R8
|
| Sensitivity Analysis in transportation problems
| Chapter 7.4
|
|
|
| | | | | | |
|
| 11/6 NO CLASS
|
|
|
|
|
| 19
| 11/8
| Network models, shortest paths
| Chapter 8.1, 8.2
| HW 8
| HW 7
|
| R9
|
| Shortest paths, Dijkstra
|
|
|
|
| | | | | | |
| 20
| 11/13
| Maximum Flow, Minimum Cuts, Duality revisited
| Chapter 8.3
|
|
|
| 21
| 11/15
| Mincost flows, Multicommodity flows
| Chapter 8.5
|
| HW 8
|
| R10
|
| Midterm review
|
|
|
|
| | | | | | |
| 22
| 11/20
| Midterm 2
|
|
|
|
| NO CLASS
| 11/22
|
|
|
|
|
| | | | | | |
| 23
| 11/27
| Minimum Cost Flows, Integer Programming, Total Unimodularity
| Chapters 8.5, 9.1
| HW 9
|
|
| 24
| 11/29
| Branch and Bound
| Chapter 9.3-9.6
|
|
|
| R11
|
| Min. Cost Flows and Integer Programming Models
| Chapters 8.5, 9.2
|
|
|
| | | | | | |
| 25
| 12/4
| Min. Cost Flows, Brance & Bound, Dynamic Prorgramming
| Chapters 8.5,9.6, 13.1-2
| HW 10 (not to be handed in)
| HW 9
|
| 26
| 12/6
| Dynamic Programming
| Chapter 13.3-6
|
|
|
| R12
|
| Branch & Bound
|
|
|
|
| | | | | | |
|
| 12/20, 1:10PM (209 Havemeyer, 233 Mud, 644 Mudd)
| Final
|
|
|
|
All readings are from Winston & Venkataraman