15. Linear Programming: LP, reductions, Simplex

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Srinivas Devadas

In this lecture, Professor Devadas introduces linear programming.

License: Creative Commons BY-NC-SA

[yusufahmed]

For my revision:
Standard form: 21:38
Duality: 31:14
Converting to standard form: 33:15
Solving max flow using LP: 40:13

[gustavo]

One of the best explanations about the fundamentals of Simplex. Thank you, Professor!

[Ludiusvox]

Thank you so much for this lecture, because I have taken Analysis of Algorithms and supposedly it was ABET accredited and I didn't miss any lectures but somehow this lecture wasn't included in my class. In my theory you guys are all working off of the public education budget from the DoE so thank you for filling in where the other teachers skip subjects in school

[henryzhu]

One of the interesting class for the whole series. No boring proof and analysis

[lilyshawn]

What a great lecture! I love that the professor handed out Frisbee to his students.

[XiaosChannel]

oh dear, never thought I'd learn how politics work here.

[bhushan]

@1:17:23 equation for slack variable x5 is wrongly written (last term should be x6 /2 instead of x1 /2)

[caio-jlqw]

Golden lecture! On top of that, a charismatic professor :)

[jwarha]

Great lecture. That board though...I wish I could clean it myself.

[guillemf]

28:34 Did he just throw a frisbee? Why are his classes so much fun?

[PedroFPardo]

I couldn't get a better solution than (x1, x2, x3) = (8, 4, 0) >> 28 How can Professor Devadas get to 30?

[gatoquantico]

How did he get the constants for getting the certificate of optimality?

[lounesbenali]

at 1:16:45 z = 27 + x2/4 - x3/2 -3x6/4 a small typo ! But Thank you !

[AvanagantiAkshathreddy]

He proved that x1+x2+x3+x4 has as a possible lower bound, but where did he prove that it is the minimum possible lower bound in the certificate of optimality??

[englishmotherfucker]

1:20 the chalk looks like the upper left quarter of a face looking towards the exit

[KundoKun]

I learned that people gift frisbees to politicians based on the message they want to hear.

[hsujerry]

How can we prove the time complexity of the simplex algorithm? The professor seems to omit the proof

[binwangcu]

I can make an unapproved claim that the optimality is smaller, but how come using cost function itself certifies the optimality?

[mustafa]

What did the professor throw, when the student answered correctly? Do anyone know?

[AIKTD]

The assumption at 4:49 would imply that you could decide to spend different amounts of money per issue per region, instead of having a global budget per issue. Now that's how real politics work!