Linear programming

Class date(s): 07 January to 04 February 2015

References

Dr. Marlin has made a great, short e-book on Linear Programming. You will find reading his notes very rewarding, and a great supplement to the class lectures.

Resources

Scroll down, if necessary, to see the resources.

Date Class number Topic Slides/handouts for class Video file References and Notes
07 January 01B
• Degrees of freedom
• Terminology related to optimization
• Introductory linear programming problem
Video
12 January 02A
• More terminology related to optimization
• Continue with our introductory LP problem
• Geometric aspects of the optimum
• Moving LP problems into standard form
Video

We covered topics on page 11, 13, 14 and 17 of the notes by Marlin (see comment above).

14 January 02B
• Getting the LP problem into standard form
• Starting to understand the Simplex method to solve LPs
Video

We covered topics on page 21 to 29 of the notes by Marlin, however, I did not focus on the mathematical details; we only consider the geometric viewpoint in 4G3.

19 January 03A
• Running the simplex method to solve LPs
• Interpretation of the optimum solution
Video
21 January 03B
• Interpretation of general LP models
• Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)
Video

See page 37 and 38 in Marlin's notes for an alternative visualization of sensitivity analysis.

26 January 04A
• Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)
• The effect of $$b_i$$ changes on the RHS
• The effect of $$A$$ changes on the LHS
• The effect of $$c_i$$ changes in the objective
Video
28 January and 04 February 04B
• Recapped some concepts on sensitivity analysis
• Considered sensitivity analysis where two or more variables were varied
• Getting a general understanding of LPs
• Allocation problems
• Blending problems
VideoA and VideoB

The R-code used to draw the plot in the class handout 2B and 3A.

plot(c(0, 100), c(0, 70), type = "n", xlab = expression(x[1]), ylab = expression(x[2]), asp = 1)
abline(a=1500/10, b=-16/10, lw=7)            # Placement
abline(a=1000/12, b=-10/12, lw=5)            # Solder
abline(a=500/8, b=-4/8, lw=3)                # Inspection
abline(v=0, h=0)
title(expression("Objective: Maximize 10"~x[1]~"+ 15"~x[2]))

text(20, 55, expression("Inspection: 4"~x[1]~"+ 8"~x[2]~"+ "~x[5]~" = 500"), srt=332.5)
text(35, 57, expression("Solder: 10"~x[1]~"+ 12"~x[2]~"+ "~x[4]~" = 1000"), srt=319.5)
text(65.5, 50, expression("Placement: 16"~x[1]~"+ 10"~x[2]~"+ "~x[3]~" = 1500"), srt=301)
text(2, 30, expression("Non-negativity: "~x[1]>=~"0"), srt=90)
text(45, 2, expression("Non-negativity: "~x[2]>=~"0"), srt=0)

delta=2
text(0+delta, 0+delta, "[0]")
text(0+delta, 62.5-2*delta, "[1]")
text(62.5, 31.25-1.5*delta, "[2]")
text(87-delta, 10.9-1.0*delta, "[3]")
text(93.75-2.1*delta, 0+1.0*delta, "[4]")