SA305 — Linear Programming

• Mar 27  Exam 2 is on Friday April 5. See below for more information.
• Mar 5  Here is a corrected version of Example 6.21 in Rader.
• Feb 22  Information on the project is now available; see below. The first project milestone – preliminary problem statement – is due on March 8.
• Feb 8  Exam 1 is on Friday February 15. See below for more information.

• Syllabus
• Course policy statement
• GUSEK
• MathProg Manual

Note: Now that the semester is over, I have taken down the homework solutions.

Starred problems should be submitted on Google Drive. [instructions]

Files and solutions available only within USNA.

• Jan 9: 1.1abcd [solutions]
• Jan 11: 1.2 [solutions]
• Jan 14: 2.1, 2.3* [solutions, code for 2.3, output for 2.3]
• Jan 16: redo 2.3*, 2.6 [solutions]
• Jan 18: 2.11*, 2.12 [solutions, code for 2.11, output for 2.11]
• Jan 23: 2.9 [solutions]
• Jan 25: 2.10* [solutions, code, output]
• Jan 28: 2.20, 2.22 [solutions]
• Feb 1: Finish Problem 3 in Lesson 11. [code], the diet problem [solution]
• Feb 4: 2.13*, 2.14. Use symbolic input parameters. [solutions] Your MathProg code must be in 2 files: (1) a model file with symbolic input parameters, and (2) a data file with set elements and numeric values for the symbolic input parameters [.mod for 2.13, .dat for 2.13, output for 2.13].
• Feb 6: redo 2.6 using symbolic input parameters, 2.7, 2.8 (the last 2 are quite challenging - give them a try) [solutions]
• Feb 8: the McDonald's diet problem* [.mod file, .dat file]
• Feb 11: redo 2.20, 2.22 with symbolic parameters [solutions], 2.16, 2.24 with symbolic parameters [solutions]
• Feb 20: finish Example 1 in Lesson 16
• Feb 22: 6.1, 6.2, 6.8, 6.9 [solutions]
• Feb 25: 6.14, 6.18 [solutions]
• Mar 1: 7.2, 7.3 [solutions]
• Mar 4: 7.4 [solutions]
• Mar 6: 7.14 [solutions]
• Mar 8: 7.16, 7.17 [solutions]
• Mar 20: 8.1, 8.2. See p. 279 for an explanation of Dantzig's rule. [solutions]
• Mar 22: 8.3, 8.8 [solutions for 8.3]
• Mar 25: 8.7
• Mar 27: 8.11ab, 8.12a
• Mar 29: 9.1, 9.2 [solutions]
• Apr 1: 9.3, 9.4 [solutions]
• Apr 10: Finish Example 2 in Lesson 32. [solutions]
• Apr 12: In Lesson 33, verify that Player R's LP and Player C's LP form a primal-dual pair.
• Apr 17: Consider the network given in Figure 2.5 of Rader on page 83. Suppose the numbers next to the arcs are lengths. Formulate an optimization model that finds the shortest path from Hillbilly to Beverly Hills. [solutions]
• Apr 19: the summer rental problem [solutions]

• 1. Introduction (Jan 8)
• 2. An illustrative example (Jan 9)
• 3. Sensitivity analysis, MathProg/GUSEK, classification of optimization models (Jan 11)
• 4. Resource allocation models (Jan 14)
• 5. Work scheduling models (Jan 16) [filled notes]
• 6. Blending models (Jan 18)
• 7. Production process models (Jan 23)
• 8. Production process models, cont. (Jan 25) [additional notes]
• 9. Multiperiod models (Jan 28)
• 10. Sets, summations, for statements (Jan 30)
• 11. Resource allocation models, revisited (Feb 1) [farmerjones.mod, farmerjones-original.dat]
• 12. Blending models, revisited (Feb 4) [filled notes, .mod file, .dat file]
• 13. Work scheduling models, revisited (Feb 6) [.mod file, .dat file]
• 14. Production process models, revisited (Feb 8)
• 15. Multiperiod models, revisited (Feb 11) [filled notes]
• 16. Introduction to algorithm design (Feb 20)
• 17. Improving search: finding better solutions (Feb 22)
• 18. Improving search: convexity and optimality (Feb 25)
• 19. Improving search: review (Feb 27) [solutions]
• 20. Geometry and algebra of corner points (Mar 1)
• 21. Geometry and algebra of corner points, cont. (Mar 4)
• 22. Linear programs in canonical form (Mar 6)
• 23. Basic solutions in canonical form LPs (Mar 8)
• 24+25. The simplex method (Mar 18, Mar 20)
• 26. The simplex method – review (Mar 22) [solutions]
• 27. Degeneracy, convergence, multiple optimal solutions (Mar 25)
• 28. Finding an initial BFS (Mar 27)
• 29. Bounds and the dual LP (Mar 29)
• 30. Weak and strong duality (Apr 1)
• 31. Duality, maximin objectives (Apr 8)
• 32. Maximin and minimax objectives (Apr 10)
• 33. LP duality and game theory (Apr 12)
• 34. An economic interpretation of LP duality (Apr 15)
• 35. Introduction to networks and the shortest path problem (Apr 17)
• 36. The shortest path problem, cont. (Apr 19)
• 37. The shortest path interdiction problem (Apr 22)
• 38. Review (Apr 24, Apr 26) [solutions]

Note: Now that the semester is over, I have taken down the quiz solutions.

• 1. Jan 16 [solutions]
• 2. Jan 23 [solutions]
• 3. Jan 30 [solutions]
• 4. Feb 6 [solutions]
• 5. Feb 20 - not really a quiz
• 6. Feb 27 - see Lesson 19
• 7. Mar 6 [solutions]
• 8. Mar 27 [solutions]
• 9. Apr 10 [solutions]
• 10. Apr 17 [solutions]

Note: Now that the semester is over, I have taken down the sample exams and solutions.

• Exam 1 (Feb 15)
• Information
• Exam from last year [solutions] - Ignore problems 4, 5ii, 5iv
• Exam 2 (Apr 5)
• Information
• Exam from last year [solutions] - Problem 1 and the bonus problem are very challenging. Ignore problems 3a, 4a.
• Final Exam (May 7)
• Information

• Information