Linear programming

Class date(s):	07 January 2015
Download video: Link [610 M]
Download video: Link [812 M]
Download video: Link [840 M]
Download video: Link [820 M]
Download video: Link [807 M]
Download video: Link [819 M]

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	Handout from class	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	Handout from class	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	Handout from class	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)	Handout from class	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	Handout from class	Video
28 January	04B	Recapped some concepts in sensitivity analysis Considered sensitivity analysis where two or more variables were varied Getting a general understanding of LPs Allocation problems Blending problems	Handout from class	[ Video]

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]")