# SA305 — Linear Programming

## Sections 3031 and 5031

### Announcements

 20 Apr End-of-semester announcements: Projects. Changes to instructions posted below: Due COB Thursday 30 April E-mail your report and GMPL model/data files to me Final Exam. Tuesday 5 May at 19:30 For more information, see the "Exams" section below GMPL Exercises. Due at noon on Wednesday 6 May I will send you the status of your GMPL exercises electronically on Monday 27 April, Thursday 30 April, and Monday 4 May 26 Mar Exam 2 is on Thursday 2 April. See below for details. 10 Mar Instructions for the course project have been posted. See below for details. 3 Feb Exam 1 is on Thursday 12 February. See below for details. 8 Jan Welcome!

### Homework

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

GMPL exercises are starred*. For GMPL exercises, formulate a model on paper and write the accompanying GMPL code. Submit your GMPL code using this submission form (also linked above).

 Date Problems Solutions 21 Apr rock-paper-scissors rock-paper-scissors 16 Apr pirates*. This is the last GMPL exercise of the semester. pirates 14 Apr 9.5, 9.7, cars 9.5, 9.7, cars 9 Apr 9.1, 9.2, 9.3, 9.4 9.1, 9.2, 9.3, 9.4 7 Apr 8.11ab, 8.12ab 8.11, 8.12 26 Mar 8.1, 8.2, 8.3, 8.8 8.1, 8.2, 8.3, 8.8 24 Mar 7.14, 7.16, 7.17 7.14, 7.16, 7.17 12 Mar 7.2, 7.3, 7.4 7.2, 7.3, 7.4 10 Mar 6.14, 6.18 6.14, 6.18 3 Mar 6.1, 6.2, 6.8, 6.9 6.1, 6.2, 6.8, 6.9 24 Feb 2.6 (redo). Use symbolic input parameters. diet-part2* (updated 10 March partial model file, data file) 2.6 19 Feb 2.9 (redo), 2.10 (redo), 2.13*, 2.20, 2.22. Use symbolic input parameters. Complete part b in Lesson 14. 2.9, 2.10, 2.13, 2.20, 2.22 5 Feb, 10 Feb 2.14, 2.16. Use symbolic input parameters. 2.14, 2.16 3 Feb sets, 2.3 (redo), 2.24, diet-part1. Use symbolic input parameters. Bring your laptops to the next class. sets, 2.3, 2.24, diet-part1 29 Jan inventory, finco inventory, finco 27 Jan 2.9, 2.10* 2.9, 2.10 22 Jan 2.6, 2.11*, 2.12 2.6, 2.11, 2.12 15 Jan 2.1, 2.3* 2.1, 2.3 13 Jan 1.1abcd, 1.2. Bring your laptops to the next class. 1.1abcd, 1.2 8 Jan 1.1abcd using trial-and-error. For each optimization model, find a few feasible solutions and determine their values. Try to find the best feasible solution you can.

### Lessons

 Dates Lesson Files 23 Apr, 28 Apr 31 Review notes, solutions 21 Apr 30 LP duality and game theory notes 16 Apr 29 Maximin and minimax objectives notes 14 Apr 28 An economic interpretation of LP duality notes 14 Apr 27 Weak and strong duality notes 9 Apr 26 Bounds and the dual LP notes 7 Apr 25 Degeneracy, convergence, multiple optimal solutions notes 7 Apr 24 Finding an initial BFS notes 31 Mar 23 The simplex method — example notes, completed notes 26 Mar 22 The simplex method notes 24 Mar 21 Basic solutions in canonical form LPs notes 24 Mar 20 Linear programs in canonical form notes 12 Mar 19 Geometry and algebra of "corner points" notes 10 Mar 18 Improving search: convexity and optimality notes 3 Mar 17 Improving search: finding better solutions notes, completed notes 24 Feb 16 Introduction to algorithm design notes 24 Feb 15 Work scheduling models, revisited notes 19 Feb 14 Production process models, revisited notes, completed notes 19 Feb 13 Multiperiod models, revisited notes 5 Feb, 10 Feb 12 Blending models, revisited notes 3 Feb, 5 Feb 11 Resource allocation models, revisited notes, farmerjones.mod, farmerjones-original.dat, farmerjones-new.dat 3 Feb 10 Sets, summations, for statements notes 29 Jan 9 Multiperiod models notes 27 Jan, 29 Jan 8 Production process models notes, notes on Alvin Fine 22 Jan, 27 Jan 7 Work scheduling models notes 22 Jan 6 Blending models notes 15 Jan 5 Resource allocation models notes, thdc.mod 15 Jan 4 Solving optimization models with a computer notes, farmerjones.mod 13 Jan 3 Graphical solutions of optimization models notes, solving animation, outcomes animation 8 Jan, 13 Jan 2 Introduction to optimization modeling notes 8 Jan 1 Introduction notes

### Quizzes

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

 Date Quiz Solutions 16 Apr Quiz 11 pdf 9 Apr Quiz 10 pdf 26 Mar Quiz 9 pdf 24 Mar Quiz 8 pdf 5 Mar 10 Mar Quiz 7 pdf 26 Feb 3 Mar Quiz 6 pdf 19 Feb Quiz 5 - not really a quiz 5 Feb Quiz 4 pdf 29 Jan Quiz 3 pdf 22 Jan Quiz 2 pdf 15 Jan Quiz 1 pdf

### Exams

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

• Exam 1 (12 February)
• Information
• Last year's Exam 1 and solutions
• Solutions
• Exam 2 (2 April)
• Information
• Last year's Exam 2 and solutions. Ignore Problems 2d, 3b. Also see Problem 2 from last year's Exam 1 above.
• Solutions
• Final Exam (5 May)
• Information
• Final Exam from 2013 and solutions. Ignore Problems 6de. Also see Lesson 31 above.