Linear Programming
Math 472
Fall 2010

Textbook: An Introduction to Linear Programming and Game Theory, 2^nd Edition. by Paul R. Thie, John Wiley & Sons, New York, 1988.

Read this Without Tears: WHAT IS EXPECTED OF YOU, see "Teaching at the University Level" by Stephen Zucker, Notices Amer. Math. Soc. 43 (1996), p. 863.

Course Description: This course is a very elementary introduction to the theory and applications of linear programming, illustrated by many examples.

Prerequisites and Development of Contents: This course should be accessible to any student with a $C-$ in Calculus and Applied Linear Algebra. The content of this course itself should very nearly coincide with that of Thies's book, excluding most of the parts on game theory. I am not perfect. However, be sure that I will do my very best to please you and your expectations.

Readings, Problem Sets, Exams: Readings and problem sets will be from the text and my manuscript, and it will be assigned in classes and perhaps additionally published at my homepage. Exams will cover all material covered in the lectures and/or the readings. Paul Thie seems to have put a fair effort into his presentation from very practically oriented point of view, and his approach is probably quite different from what you've seen before. Thus, I really encourage you to read the book and, hopefully, additional related literature, as lectures advances.

Exam Dates:

• Midterm I: Friday, October 8, 2009 (during regular class hour)
• Midterm II: Friday, November 19, 2009 (during regular class hour)
• Final Exam: Monday, December 13, 2009, 7:50-9:50am (TBC) (written test on or oral as mutual agreement between December 10-17)

Grading Strategies - Grade Distribution:

• 25 % Homeworks & Quizzes, 50 % Midterms (25 % each exam), 25 % Final Exam
• 90 % <= A-class, 75 % <= B-class, 60 % <= C-class, 45 % <= D-class
• Your scores are recorded in my office, and evaluated according to the gradeline distribution given. A computational project may count up to 25 % (depending on your effort) by substituting the worsest part of Homeworks or one of the Midterms, based upon an agreement with the instructor, which must be indicated towards the instructor and started before November 15. This project is documented by a written document handed in immediately after the Thanksgiving break and is orally presented in an academic discussion before the final exam week. I will be the grader for all sections as well.

Course Syllabus as Postscript (Last Update: 08/19/10) - You will need an utility like ghostview to read it!

Please, note you need ghostview to read the postscript files after downloading! See http://www.cs.wisc.edu/~ghost/index.html for more software product information.

Course Syllabus as Pdf (Last Update: 08/19/10) - You will need an utility like ACROREADER (ADOBE) to read it!

Remarks for the Prerequisites and First Week:

Please, review your knowledge on linear algebra, in particular, simple vector operations in R^n, the elimination method and pivoting to treat systems of linear equations A x = b.

Remarks for the 1st Midterm Exam:

Please, review your notes and sections 1.1 - 3.4. The midterm exams are not of multiple choice. Midterm I will contain 4 problems (one word problem). The main goal is to check your capability of learnt linear programming techniques. In particular, you should be sure in linear programming formulation (LP) with constraints and objective function, transformation of word problems into mathematical (LP) forms, standard forms (SLP) of (LP), canonical forms, pivoting, convexity of region G of feasible solutions, basic feasible solutions as vertex points of G, simplex method and simplex algorithm. No books, no notes, no tables, no graphic calculators at all, no notebooks are permitted (only plain calculators, i.e. non-programmable and non-graphical ones with the standard function evaluations). I don't expect that you know all formulas, but you should be able to understand and work with them. Go over the homeworks again to have a glimpse on those problems you may expect on the midterm.

Remarks for the 2nd Midterm Exam:

Please, review your notes and sections 3.1. - 4.5. The midterm exams are not of multiple choice. Midterm II will contain 4 problems. The main goal is to check your capability of learnt techniques. In particular, you should be sure in the simplex algorithm and related aspects, artificial variables, the problem of redundancy, strategy of fastest descent, strategy of lowest local computational cost, strategy of most negative coefficients c_s, problem of cycling, the duality relation, invariance property of dual operation, transformation to dual systems and slack variables, the principles of weak and strong duality, and the complementary slackness theorem. The textbook will not allowed to be used. No extra books, no extra notes, no tables, no cheating sheets, no graphical calculators, no notebooks are permitted (only plain calculators, i.e. non-programmable and non-graphical ones with the standard function evaluations). You should be able to understand, apply and work with the formulas you have seen in the textbook or during lecture hours.

Remarks for the Final Exam:

The main 4 topics of the final exam are convexity and its consequences (convex functions, convex sets in R^n, main proposition, convexity of set of feasible solutions, set b.f.s. = set of vertex points, convex functions on convex domains attain their extremes at vertex points), the simplex algorithm (SLPs, CFs, thms 1-3 from sec 3.4, redundancy, two phases, several strategies MMNC, MLLCE, MFD, MAD), duality (invariance, weak, strong, complementary slackness) and sensitivity analysis (matrix representation from sec. 5.2, perturbation of initial data and its effects on the optimal solution, dual simplex algorithm). The final can be taken as written test (2hr's) or as oral presentation (1hr). The final exam is planned to be an oral one, however this is a free option to choose. You can have up to one hour to demonstrate in an academic discussion that you are capable of the presented course material. You start with reporting on basic facts and topics of your choice out of the 4 main topics related to the linear programming problem. You may also prepare a presentation of more sophisticated topics from linear and nonlinear programming if you wish to do so. It will be supposed that you use the blackboard and / or sheets of empty paper during this discussion. The final exam and the total grade will be determined immediately after that discussion too, unless there are further requirements to complete your course work (which I hope not). Please, contact me before the last week of teaching to set an exam time and date with me. The exam will take place with high probability in my office Neckers 265 during the last week and / or the exam week, based on our mutual agreement with class participants. Of course, if you still insist on then there will be a written final exam, but I honestly hope not. Don't have any serious fears towards the oral final exam. Mostly, we enjoy, both you and the instructor, because it aims to help you to improve your capacity in oral presentations.

Current Course Outline (Last Update: 08/19/10):

Week 1 : Introduction, 1.1.-1.4
Week 2 : 2.1.-2.3
Week 3 : 2.3.-2.6
Week 4 : 3.1.-3.2
Week 5 : 3.2.-3.3
Week 6 : 3.3.-3.4
Week 7 : 3.5, Exam I
Week 8 : Discussion on Exam I, 3.6.-3.7.
Week 9 : 3.7.-3.9.
Week 10: 4.1.-4.3.
Week 11: 4.3.-4.4.
Week 12: 4.4.-4.5., 5.1.
Week 13: 5.1.-5.3., Exam II
Week 14: Thanksgiving Break
Week 15: Discussion on Exam II, 5.3.-5.5.
Week 16: 5.5.-5.7., 8.4

Remarks for Homeworks, Quizzes and Recitations:

The homeworks and quizzes are assigned in classes and are due by the next Monday thereafter. The recitation discussion takes place every Wednesday during class hours. The homework is meant to strengthen your knowledge in related areas touched in lectures. A couple of random quizzes may occur if the participation drops down significantly. Thus, your active participation is required! The homeworks and quizzes play an essential role in forming your grade according to the presented grade distribution.

Homeworks (Last update: 08/18/10):

Week 14: 4.4.: no. 1, 2, 3a, 3b (consequences of weak and strong duality theorems) due on Friday, November 19

Week 13: 4.3.: no. 1, 3a, 4a (work with duality) due on Monday, November 15

Week 12: 4.2.: no. 1d, 1e, 2a, 2d (transformation to dual systems) due on Monday, November 8

Week 11: 3.7.: no. 3f, 3g (treatment of redundant systems) due on Monday, Nov 1

Week 10: 3.6.: no. 1a, 1b (on simplex tableau and artificial variables) due on Monday, Oct 25

Week 9: 3.5.: no. 2, 3 (on simplex tableau) due on Monday, Oct 18

Week 8: 3.4.: no. 2a, 2d, 2f, 7 (on simplex algorithm) due on Monday, Oct 11

Week 7: 3.3.: no. 3 (on simplex algorithm) due on Monday, Oct 4

Week 6: 3.2.: no. 6 (on solution concepts) due on Monday, September 27

Week 5: 3.1.: no. 3c,3f,3g,3h (on standard forms) due on Monday, September 20

Week 4: 2.3.: no. 14 and 2.4.: no 5 (on modelling) due on Monday, September 13

Week 3: 2.2.: no. 11, 14 (p. 17, on modelling) due on Friday, Sep 10

Further Readings : (optional)

• Bazaraa, M.S. and Jarvis, J.J.: Linear Programming and Network Flows, Wiley, New York, 1977.

• Bellman, R.: Dynamic Programming, Princeton University Press, Princeton (NJ), 1957.

• Charnes, A., Cooper, W.W. and Henderson, A.: An Introduction to Linear Programming, Wiley, New York, 1953.

• Dantzig, George B.: Linear Programming and Extensions, Princeton Landmarks in Mathematics, 11th printing, Princeton University Press, Princeton (NJ), 1998.

• Dantzig, George B. and Thapa, Mukund N.: Linear Programming 1: Introduction, Springer Series in Operations Research, New York, 1997.

• Nash, Stephen G. and Sofer, Ariela: Linear and Nonlinear Programming, McGraw-Hill, New York, 1996. (Our First Recommendation).

• Riley, V. and Gass, J.I.: Linear Programming and Associated Techniques, The John Hopkins Press, Baltimore, 1958 (a comprehensive bibliography in linear, nonlinear and dynamic programming).

• Schrijver, A.: Theory of Linear and Integer Programming, Wiley, New York, 1998.

• Simonnard, M.: Linear Programming, Prentice Hall, Englewood Cliffs (NJ), 1966.

• Thompson, G.E.: Linear Programming - An Elementary Introduction, Macmillan, New York, 1971.

• Yudin, D.B. and Gol'shtein, E.G.: Linear Programming, Israel Program for Scientific Translations, Jerusalem, 1965.

• Zionts, S.: Linear and Integer Programming, Prentice Hall, Englewood Cliffs (NJ), 1974.

Original Papers for the Birth of Linear Programming & Simplex Method: