Linear Programming -- Spring 2017 -- Skiles 270, Tue, Th 1:30-3PM
Instructor: Greg Blekherman, email: greg@math.gatech.edu
Textbooks: Linear Programming by V. Chvatal
Online Resources: Course notes by Jim Burke at University of Washington.
Office Hours: Monday 2-3PM, Tuesday 3:30-4:30PM, Thursday 10-11AM in Skiles 208A.
Course Policies and Grading: All information concerning grading, homework, quizzes and exams is in the course policies page.
Calendar and Syllabus: Important dates and lecture schedule are in the course calendar. The calendar will be updated during the term. The syllabus for the course is here.
Computational Project: This is an independent project. You cannot collaborate on it. The project is due on April 20th at the beginning of class.
Part 1:
1) Take Model 11 or 20 from here. Formulate either as a linear program.
2) Use either Excel Solver or Matlab to solve the linear program and create a sensitivity report.
3) Write a brief report commenting on the nature of the solution. This report should be accompanied by the solution to the LP, the solution to the dual, and the full sensitivity report. In particular, your report should comment on the robustness of the solution indicating the most sensitive elements of the model.
Matlab is the standard language used in many optimization applications and it has many powerful solvers and packages. You can use linprog to solve linear problems in Matlab. However, it is easier to generate the sensitivity report in Excel. The guide to installing Excel Solver is here.
The report for this part of the project should be put together as follows:
Page 1: the problem statement appearing on the modeling webpage.
Page 2: your LP model typed up in Word or some other editor (mathematicians like LaTeX but there is a steep learning curve).
Page 3: the Excel spread sheet file for your model or Matlab printout of commands and output used to solve the problem.
Page 4: The solution and the sensitivity report from Excel Solver or Matlab.
Page 5-6: Your discussion of the sensitivity report as presented to a client. In particular, your discussion should address any sensitivity in the range boundaries, reduced costs, and/or shadow prices.
Part 2: Read tutorial on transportation problems here. Solve Exercises 2 and 3.
1) Write down LP formulation for both problems.
2) Solve one of the problems using either Excel Solver or Matlab.
The report for this part of the project should be put together as follows:
Page 1: your LP model for Exercise 2typed up in Word or some other editor (mathematicians like LaTeX but there is a steep learning curve).
Page 2: your LP model for Exercise 3 typed up in Word or some other editor (mathematicians like LaTeX but there is a steep learning curve).
Page 3: the Excel spread sheet file for your model or Matlab printout of commands used to solve the problem of your choice.
Page 4: The solution and dual solution from Excel Solver or Matlab.
Homework Assignments:
Homework 1: Part 1 and Part 2.
Homework 2: Part 1 and Part 2. For Part 2, ignore instructions about tableau form (we did not use it yet).
Homework 3: Do Models 3-10 here. Change the models to standard form. Extra Credit: If the problem has feasible origin, solve it using the simplex method. You may investigate how to not do it by hand.
Homework 4: The assignment is here.
Homework 5: The assignment is here.
Homework 6: The assignment is here.
Homework 7: The assignment is here.
Homework 8: Do Widgets International and Donna's Trees problems from here. You may wish to consult other problems and solutions. Extra Credit: Arty's t-shirts.
Homework 9: The assignment is here.
Homework 10: The assignment is here.
Practice Problems: Practice Problems for the Midterm Exam are here. Short solutions are here. Practice Problems for the Final Exam are here. Partial solutions to practice problems are here.