15. Linear Programming: LP, reductions, Simplex
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Srinivas Devadas
In this lecture, Professor Devadas introduces linear programming.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
One of the best explanations about the fundamentals of Simplex. Thank you, Professor!
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
simplex method/big m method are fundamental part of operations research course
Simplex algo: 58:38
Not all heroes wear capes
At 16 min.. what is that / 111 ?? I dnt get it
@@biswajeetsethi7689 it's a fraction.
Thanks
Blessyou
What a great lecture! I love that the professor handed out Frisbee to his students.
How did he get the constants for getting the certificate of optimality?
One of the interesting class for the whole series. No boring proof and analysis
Golden lecture! On top of that, a charismatic professor :)
I can make an unapproved claim that the optimality is smaller, but how come using cost function itself certifies the optimality?
Can someone timestamp when he starts talking about Simplex please?
39:45 - Expressing Max-Flow as LP
This dude is rolling of a bean rn
never mind, I had my speed on 1.25
can you add timestamp please
Simplex algorithm at 59:53
How can we prove the time complexity of the simplex algorithm? The professor seems to omit the proof
1:20 the chalk looks like the upper left quarter of a face looking towards the exit
Is there restriction on the number of decision variables and constraints used in an LPP?
no
@1:17:23 equation for slack variable x5 is wrongly written (last term should be x6 /2 instead of x1 /2)
correct
prof was high af
Good lecture.
This is great
What did the professor throw, when the student answered correctly? Do anyone know?
It's a frisbee.
oh dear, never thought I'd learn how politics work here.
Xiao'sChannel amazing, isn't it?
unbelievable! how they decide what to say to let people vote to them
He proved that x1+x2+x3+x4 has 3100000/111 as a possible lower bound, but where did he prove that it is the minimum possible lower bound in the certificate of optimality??
I couldn't get a better solution than (x1, x2, x3) = (8, 4, 0) >> 28 How can Professor Devadas get to 30?
I get the same answer as you using a different method.
I think that z is equal to 27 + x2/4 - x3/2 -3x6/4 instead of 27 + x2/4 +x3/2 -3x6/4
But despite that I still find like you (8, 4, 0) >> 28
I enjoy learning algorithms here... nice work...
At 16 min.. what is that / 111 ?? I dnt get it
@@biswajeetsethi7689 I don't understand either
When introducing general form of LP, shouldn't the objective function be x*c transpose? Since c is also a vector which means that it's a column matrix...
Yes! But C is generally considered as a matrix os 1 line and n columns, avoiding the transpose.
You can, but what he wrote is valid because he wrote the coefficients as a column vector and multiplied them with the dot product. Which is equivalent to matrix multiplication with the transpose
33:11 Converting LP problem to standart form
at 1:16:45 z = 27 + x2/4 - x3/2 -3x6/4 a small typo ! But Thank you !
Great lecture. That board though...I wish I could clean it myself.
hahha +1
lol
how relevant to current events.
yeah
LP is super relevant - since many systems are linear, but LP is also very useful as part of the algorithm for IP (integer programming) which is used for scheduling algorithms
Can anybody tell me how did 140/222 come out?
I don't know also
sir multiplied some coefficients to all three constraints equations....and then added all three equations
Do you till want to know?
For the limitation equations, dollar spent per issue times number of people gained or lost per issue gives dollars, but the right hand side constant shows number of people. there's a type mismach. I got lost. I mean 50000 $, 100000 $ or 25000$ could be, but they are not dollars, they are number of people, 50000 people, 100000 people, 25000 people, but the x1, x2, x3, x4 are dollars/issue.
the coefficient: -2,5,3,etc. are votes/dollar. So -2*X1 means votes/dollar*dollars/issue=votes/issue. Therefore, the constraint is how many total votes for each issue. Here it also assumes each people has one vote. People=Vote
What are the space and time complexity of the simplex algo? how to find that?
It's exponential in time, you can find it in the notes here: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec15.pdf
It should be noted that the time complexity of the simplex algorithm is only exponential in the worst case. For practical problems, the simplex algorithm is quite efficient running in cubic time.
mention @2:10 and 1:02:10
why we are equating money spent on each issue to the population of that demography ?
That also bothered me. I think that X1 through X4 are simply dollar and the coefficients associated are in Vote/Dollar. For exemple Urban/Gun control coefficient is +8 meaning that the more money you spend the more vote you get until you have a majority. 8*X1 = the vote you get by spending X1 DOLLARS in urban ad campaign on gun control.
the coefficient: -2,5,3,etc. are votes/dollar. So -2*X1 means votes/dollar*dollars/issue=votes/issue. Therefore, the constraint is how many total votes for each issue. Here it also assumes each people has one vote. People=Vote
Lucky for him the optimal solution had x3 = 0, because otherwise x1 + x2 + x3 + x4 would be strictly greater than 3100000/111!
28:34 Did he just throw a frisbee? Why are his classes so much fun?
I guess you are new here lol. Yeah, he throws a frisbee to the students who answers questions
1:04:53 simplex derive
28:08 Haha that was funny!
I didn´t undestand what happened! Can you explain please? Thanks. :)
He said, she has her head down. Then proceeds to throw the Frisbee at the student.
Explain an easy way .
I learned that people gift frisbees to politicians based on the message they want to hear.
Is this person Indian??
Yes
Yup
how come Xi --> Xi' - Xi''?
because any real number Xi can be represented as the difference of two non-negative numbers Xi' and Xi''.
@@junzhai1715 Xi' usually implies the first derivative on Xi.... and Xi'' usually implies the second derivative of Xi....?
@@IceTurf oh no. sry. They are just two different variables. You can treat them as Yi and Zi if you want. Nothing to do with derivative.
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!
Sy bsc mumbai university lecture
My #1 take away from this lecture: How does politics work? "You buy elections!"
Just use a Neural Network!
this is MIT yet I'm doing this in 10th grade fml
lol and i doing it now hahah in second year engineering
Even I was in 10th 5 years back, didnt even cared to watch anything other than cartoons
Am I the only 8th grader that watches this kind of stuff cuz its interesting?