Math 354: Section 7, Spring 2005 (01:640:354:07)
Linear Optimization
Tuesdays, Thursdays 7:40-9:00 PM Scott Hall 106
Official course description:
Linear programming problems, the
simplex method,
duality theory,
sensitivity analysis,
introduction to
integer programming,
the transportation problem,
network flows, and other applications.
Prerequisite: Linear Algebra, 640:250.
My information:
- Kai Medville
- Office: Hill Center 622
- Office hours: Tuesday 3:00-4:00 and Wednesdays 5:00-6:00 in Hill 622
- Course website: go to www.math.rutgers.edu/~medville and follow the link "Spring 2005: Linear Optimization (Math 354), Section 7" under "Teaching".
- Email: medville@math.rutgers.edu
Text:
Kolman and Beck, Elementary Linear Programming with Applications, 2nd ed., Academic press, 1995.Grades:
- We will have homework, quizzes, two midterm exams, and a cumulative final exam.
- Late homework and make-up quizzes will not be accepted or given without a VERY good excuse.
- The grades break down as follows:
Homework/Quizzes 20% Midterm #1 20% Midterm #2 20% Final Exam 40%
ANNOUNCEMENTS:
-
5/12: Grades have been given to Rutgers. I try to post the final grades sometime this weekend. If you need to know sooner, email me.
<\li>
- 5/05: Here are the solutions to the final review.
- 5/03: It may be useful to look at the solutions to the second midterm.
- 5/03: The review sessions are now confirmed. Wednesday May 4 6-8pm in Hill 423 and Friday May 6 1-3pm in Hill 525. Come with questions. Please take a look at the final exam review problems. I recommend you do mine AND Prof. Wilson's.
- 5/03: Professor Wilson has posted some review problems. He will be going over the problems on Saturday May 6, 2-5pm in ARC-324. You are welcome to join his session. When he says use the labeling algorithm in problem #6, pretend (for me) that he says Ford-Fulkerson algorithm.
4/26: The final exam will be given on Tuesday, May 10, 8-11 PM at Scott Hall 106. The exam is cumulative. I will allow the use of calculators. - 4/21: Vince Vatter wrote a nice introduction to graphs and the Ford-Fulkerson algorithm.
- 4/3: Here is an answer key for the midterm review. I have posted some suggested homework problems from sections 3.6, 4.1, and 4.2 to help you prepare for the exam.
- 3/31: To help you prepare for the second midterm, there is a practice exam available. An answer sheet will be forthcoming.
- 3/22: We are behind schedule. This means that the 2nd midterm will be postponed. The schedule has been adjusted to reflect this.
- 3/11: The final exam is scheduled to be administered on Tuesday, May10, 8-11pm.
- 3/8: As it turns out, the university has cancelled classes. See you Thursday.
- 3/8: You can view the fourth quiz Q4 and answer key.
- 3/8: I will not be at office hours today.
- 3/8: A short tutorial on the two-phase method can be found here. The same thing can be found in the book. There is a general tutorial on the simplex method to to be found here.
- 3/1: Class is cancelled today. I am stuck out of town. See you on Thursday. Expect a short quiz reviewing the 2-phase method on Thursday.
- 2/24: Class is cancelled today. I will be at lecture with exams for those who want them now.
- 2/17: Quiz #3 can be viewed here. The answer to (a) is x1, u, v are the basic variables and the basic solution is [ 20 , 0 , 0 , 6 , 12 , 0] transpose. The answer to part (b) is Entering: x2 and Departing: u.
- 2/11: Midterm #1 review sheet answer key.
- 2/10: Midterm #1 review sheet.
- 2/9: Two nice examples of the Simplex Method here and here.
- 2/9: You can view the first two quizzes: Q1 and Q2.
- 1/29: The homework due on Tuesday PDF.
- 1/29: A link for a good online reference to Linear Programming, http://www.isye.gatech.edu/~spyros/LP/LP.html.
- 1/27: Additional suggested homework problems listed from Chapter 0. Listed in Homework section. You should be able to solve these problems by the time of Midterm #1. The sooner the better.
- 1/27: Proposed date for Midterm #1: 2/17/2005. See full calendar below.
- 1/25: First homework assignment in PDF and LaTeX.
Homework:
| Due Date | Section | Required Problems | Suggested Problems |
|---|---|---|---|
| --- | 0.1 | 3,5,9,15 | |
| 0.2 | 1,3,9,13,15 | ||
| 0.3 | 3,5,7,11 | ||
| 0.4 | 3,5 | ||
| 0.5 | 3,5,7 | ||
| Tue 1/25 | 1.1 | 6 | 3 |
| 1.3 | 10 | 9 | |
| Tue 2/1 | 1.3 | 14 | 1,3,7,15,22,24 |
| 1.4 | 4 | 1,3,7 | |
| Tue 2/8 | 1.3 | 30 | |
| 1.5 | 6,8 | 3,7 | |
| Tue 2/15 | 2.1 | 2,4,20 | 5,7,9 |
| 2.3 | 2(a) | 3,5,7(a),9(a) | |
| Tue 3/1 | 3.1 | 2,4 | 7,9 |
| Tue 3/22 | 3.2 | 9,10 | 1,3,5,11 |
| Tue 3/29 | 3.3 | 1,2,6 | 5,11 |
| 3.4 | 2 | 8,9 | |
| Th 4/7 | 3.6 | 1,2,3 | |
| 4.1 | 1,2,5 | ||
| 4.2 | 3,4,5,7 | ||
| Tue 4/26 | 5.3 | 2,4 | |
| 5.4 | 6 | ||
| 5.5 | 2 |
Approximate Schedule:
| Lecture | Date | Sections | Topics | |
|---|---|---|---|---|
| 1 | Tue 1/18 | 1.1 | Introduction to Linear Programming | |
| 2 | Th 1/20 | 1.2-1.3 | Matrix notation, geometry of constraints | |
| 3 | Tue 1/25 | 1.3 | Review of Geometry, Convexity | |
| 4 | Th 1/27 | 1.4 | Convexity and Extreme Point Theorem | |
| 5 | Tue 2/1 | 1.4, 0.4, 0.5 | Extreme Point Theorem (cont.) and Linear Algebra Review | |
| 6 | Th 2/3 | 1.5 | Basic Solutions | |
| 7 | Tue 2/8 | 2.1 | Simplex Method, an example | |
| 8 | Th 2/10 | 2.3 | 2-Phase Method | |
| 9 | Tue 2/15 | catch-up/review | ||
| -- | Th 2/17 | Midterm #1 | ||
| 10 | Tue 2/22 | 3.1 | Duality, Intro | |
| 11 | Th 2/24 | -- | snow day | |
| 12 | Tue 3/1 | 3.2 | Duality, Part I | |
| 13 | Th 3/3 | -- | snow day | |
| 14 | Tue 3/8 | -- | snow day | |
| 15 | Th 3/10 | 3.2 | Duality, Part II | |
| 16 | Tue 3/22 | 3.3 | Computational Aspects of Duality | |
| 17 | Th 3/24 | 3.4 | Dual Simplex Method | |
| 18 | Tue 3/29 | 3.6 | Sensitivity Analysis | |
| 19 | Th 3/31 | 4.1, 4.2 | ||
| 20 | Tue 4/5 | catch-up/review | ||
| -- | Th 4/7 | Midterm #2 | ||
| 21 | Tue 4/12 | 5.3,5.4 | Intro to graph theory, Solving the Max flow problem | |
| 22 | Th 4/14 | 5.4 | Max flow/min cut. Ford Fulkerson. | |
| 23 | Tue 4/19 | 5.5 | Shortest path algorithm | |
| 24 | Th 4/21 | 5.1 | Transportation problem | |
| 25 | Tue 4/26 | 5.2 | Assignment problem | |
| 26 | Th 4/28 | catch-up/review |