Here is an explanation of the simplex algorithm, including details on how to convert to standard form and a short discussion of the algorithm's time complexity.
this is legitimately gold, i've had no idea about simplex, circulated through 4 or 5 video, all of them assumed I had some knowledge prior to watching the video so I could not understand anything at all from them. But this one right here... This is perfect ! thank you
at 8:07 the column S2, third row, the number should be 10/3, not 15/4. Also, you didn't mention artificial variables, two phase simplex and duality at all. With that being said, very good video, I'd give you a 9/10
Yes, I got that too. I think there was a mistake with -1/3 on the S2 above that 15/4, because S2 on the second row should be just 1/3, not -1/3. Thank you for your comment and thanks to author for his explanation.
Great explanation! Question though: Once we reach intersection at B ( 4:35 ) you mention that we have TWO options. Keep b=0, or keep s2=0. I'm not sure I understand how come we have two options, since if we chose b-0, then the objective would decrease no?
Yeah, I think you're always strictly improving on the solution, so surely you could always rule-out the vertex that you just came from. For 2D problems that'd mean doing a circuit till you're at the max.
Perhaps it was my linear computation classes from 1981 kicking in but didn't everyone know the answer the minute it was asked? I started to wonder why he was presenting such an obvious solution and kept waiting for the trick that I may have originally missed which, of course, doesn't exists.
I came here to understand the reasons behind the matrix manipulation better, but when the video reached that part, it kind of stopped explaining (why things are done) and settled for narrating (what is being done, which I already know) so I didn't find it as helpful as I had hoped.
At 9:15, Case where x is negative, I think you need to add one more constraint x_1< x_2 and need to include them in the objective function as well. Great explanation btw.
*S* represents the amount that you would need to add to the smaller amount (lhs) to make it equal to the larger amount (rhs). So *S1* and *S2* should be strictly non-negative.
Read and watched several explanations about the Simplex but this video is the best. It starts with the overall idea and gets deeper and deeper, which helps the understanding quite a lot.
Might be either dumb or too late.. but why not only sell standard chairs? As I am understanding it, you are essentially loosing profit with every “luxury” chair you sell.. if you spent the 1000 hours on 100 “standard” chairs (costing 10 hours each) you would make $1000 at $10 each. If you made a single “luxury” one and the rest “standard”, you would make $980. If you made two “luxury” chairs and the rest “standard”, you would make $960.. i.e. you are loosing $20 for every chair. It costs you twice in labor to profit for every luxury chair, compared to a one to one cost in labor to profit for standard chairs. What the hell am I missing?
@@24mrdanny this smallest ratio allows us to keep the constraints on variables. on a graph it corresponds to moving along the edge until u encounter the first constraint.
So, this vid is amazingly concise; but I got me some questions: 1) How do you choose the first vertex? In this case it's "obvious" that (0,0) is a vertex, but I have a problem with over 100k decision variables and if I set them all to zero then I'll be outside the solution region. 2) How to handle constraints that don't form a boundary? Imagine the same as above, but with the added constraint *x
1 - This is the purpose of the slack variables. If the right side vector b is positive, you can always start with x=0 ans s=b. Some problems do not have postive b, and then indeed it is another problem. It is called the 'first phase' of simplex algorithm. You have to start with what we call a "basic feasible solution"
2 It seems the process of changing the base was not explained, but in simplex if you start with a bfs vertex, you always get another bfs (improved) vertex. When you change the point you test how far can you move it in a given direction, and then your redundant constraint would never show up. Since some constraints add nothing to the problem, some solvers can do a preprocessing and remove it just to make the matrix smaller .
@@julianocamargo6674 Thanks for your explanations! I wish I could give an intelligent response, but I haven't touched simplex since I first wrote this comment. I'm sure I'll come back to it and read your comments again. Thanks. =)
you did not explain why at 6:40 you take the constants in the last column and divide them by their corresponding values in the first column. This video does not explain the simplex method, it simply describes it.
You are producing 20 of each chair, which use 3m2, so in total you use 120m2 (40*3m2) which is the maximum allowed by the problem, so no unused material. The same for the hours, the full 1000 hours were used (20*40+20*10).
So concise... Someone give this guy a Nobel Prize
this is legitimately gold, i've had no idea about simplex, circulated through 4 or 5 video, all of them assumed I had some knowledge prior to watching the video so I could not understand anything at all from them. But this one right here... This is perfect ! thank you
You just summed up my 1.5hour lecture in a 10min video.
I have spent hours understanding linear programming and simplex but this dude explained it better than anyone in 10 mins
Except for the last few seconds, which gave me horrible flashbacks, this is more or less the perfect explanation. Thanks a lot!
at 8:07
the column S2, third row, the number should be 10/3, not 15/4.
Also, you didn't mention artificial variables, two phase simplex and duality at all.
With that being said, very good video, I'd give you a 9/10
Yes, I got that too. I think there was a mistake with -1/3 on the S2 above that 15/4, because S2 on the second row should be just 1/3, not -1/3. Thank you for your comment and thanks to author for his explanation.
I don't usually comment in RUclips videos. But this video right here should be appreciated. Man, you're awesome!
you mean, Complex Explained
Old yet still the best
Simple and clear explanation. Thank you for making this video
Great video, you should make a comeback
Holy cow dude! This was VERY well explained. Inspiring.
This is the most straightforward video explanation of Simplex...Very much appreciated. Thanks!
Thank you, that was a brilliant explanation.
So concise yet so perfect. And so intuitive and elementary too.
I searched a lot and I've been confused totally but you explained very good:)
Great explanation! Question though:
Once we reach intersection at B ( 4:35 ) you mention that we have TWO options. Keep b=0, or keep s2=0.
I'm not sure I understand how come we have two options, since if we chose b-0, then the objective would decrease no?
Yeah, I think you're always strictly improving on the solution, so surely you could always rule-out the vertex that you just came from. For 2D problems that'd mean doing a circuit till you're at the max.
🤓
I am a computery guy.
Perhaps it was my linear computation classes from 1981 kicking in but didn't everyone know the answer the minute it was asked? I started to wonder why he was presenting such an obvious solution and kept waiting for the trick that I may have originally missed which, of course, doesn't exists.
I came here to understand the reasons behind the matrix manipulation better, but when the video reached that part, it kind of stopped explaining (why things are done) and settled for narrating (what is being done, which I already know) so I didn't find it as helpful as I had hoped.
The irony is Simple is not actually "Simple"!! (The big table thing, Oh God 🤯)
Am I the only one wondering how at 8:05 he managed to get 15/4 for the 5-(5*(-1/3))? That would be 10/3 if I'm not mistaken...
Michael Duffy you are correct, but fortunately here that doesn’t matter. Thanks for pointing out the mistake :)
At 8:08 shouldn’t the 4th value for the last row be 10/3 instead of 15/4?
5 + ( - 5 / 3 )
Amazing explanation. Not nearly enough subscribers.
Now I have an idea about what I am to do and not feel forced to memorize the steps
The only excellent video explains the simplex algorithm very clearly! Many thanks.
Really nice explanation, clear and to the point.
his voice fits being the main vocal of a rock band i swear to god.
My guy, you just saved my ass , my professor could never
thank you! you made simplex simple lol
OMG
This opened the doors of my thoughts.
At 9:15, Case where x is negative, I think you need to add one more constraint x_1< x_2 and need to include them in the objective function as well.
Great explanation btw.
Very beautifully explained.
Thank you for sparing many hours of torture for many!!
@ 2.25 timestamp--did you mean s1
*S* represents the amount that you would need to add to the smaller amount (lhs) to make it equal to the larger amount (rhs). So *S1* and *S2* should be strictly non-negative.
👌
Read and watched several explanations about the Simplex but this video is the best.
It starts with the overall idea and gets deeper and deeper, which helps the understanding quite a lot.
very clear. amazing. wow
YOU R A GENIUS ! THANKS A LOT.
awesome explanation 🎉
Might be either dumb or too late.. but why not only sell standard chairs? As I am understanding it, you are essentially loosing profit with every “luxury” chair you sell.. if you spent the 1000 hours on 100 “standard” chairs (costing 10 hours each) you would make $1000 at $10 each. If you made a single “luxury” one and the rest “standard”, you would make $980. If you made two “luxury” chairs and the rest “standard”, you would make $960.. i.e. you are loosing $20 for every chair.
It costs you twice in labor to profit for every luxury chair, compared to a one to one cost in labor to profit for standard chairs.
What the hell am I missing?
you can only make a maximumof 40 chairs due to the m3 of wood available.
@@nils3989 Ohhhh thats the detail I overlooked. Thank you for pointing it out.
i dont like the drawings
concise and accurate explanation.Great video and thanks a lot
your presentation style is really outstanding!!
Egg
i likz your accent
LEGEND! You can die in peace knowing that your legacy will forever save future undergrad students days before their final exam
Thank you louis
Beautifully explained
thank you
Great Explanation, finally a video which gives some intuition
Thank you!!
welcome to 2021.
Thanks so much for simplifying it so much, textbooks make it way more harder. I hope you keep making more videos
well said 👏
tysm
Best demonstration around. And would be hard to beat. Thanks.
Thanks a lot
Thank you❤
I can't believe this is the only video on your channel, it's so informative and you explained it very well!
That's a great explanation! Thanks for the video
what a legend
s1 and s2 aren't supposed to be great or equal to zero? why do you s1 and s1 are less than zero while drawing the graph?
good video
Perfection
why do we want the smallest ratio at 6:58?
I am wondering this as well...
@@24mrdanny this smallest ratio allows us to keep the constraints on variables. on a graph it corresponds to moving along the edge until u encounter the first constraint.
man you re a life saver , also that scene from dhis is pure gold, bless you
"A quick sanity check" always gets me 😂
all the trickery with divisions still not explained.
Dude you are wonderful - really wish you'll somehow monetize your explanation skills.
Such a great help! Really appreciate your work!!
Very well presented, and the jump cuts help understand things better
I would love to see more videos from him, a very nice way of explaining and visualising the concept
Thanks for this great video!
Very helpful, thank you!
Simplex explained Simply. Thaks a lot
best explanation i've seen so far.
thanks man. very helpful!!
I wish you are my instructor, thank you so much for this short and concise video
That intro sound sounds familiar.... dont hug me I'm scared.
Steven :)
best explanation of simplex ever!
This is awesome! Please do more
Thank you so much! =)
Man,
you are the best
Excellent!
Wow, that was great.
So, this vid is amazingly concise; but I got me some questions:
1) How do you choose the first vertex? In this case it's "obvious" that (0,0) is a vertex, but I have a problem with over 100k decision variables and if I set them all to zero then I'll be outside the solution region.
2) How to handle constraints that don't form a boundary? Imagine the same as above, but with the added constraint *x
1 - This is the purpose of the slack variables. If the right side vector b is positive, you can always start with x=0 ans s=b.
Some problems do not have postive b, and then indeed it is another problem. It is called the 'first phase' of simplex algorithm. You have to start with what we call a "basic feasible solution"
2 It seems the process of changing the base was not explained, but in simplex if you start with a bfs vertex, you always get another bfs (improved) vertex. When you change the point you test how far can you move it in a given direction, and then your redundant constraint would never show up. Since some constraints add nothing to the problem, some solvers can do a preprocessing and remove it just to make the matrix smaller .
@@julianocamargo6674 Thanks for your explanations! I wish I could give an intelligent response, but I haven't touched simplex since I first wrote this comment. I'm sure I'll come back to it and read your comments again. Thanks. =)
i love this.
vivid example
you did not explain why at 6:40 you take the constants in the last column and divide them by their corresponding values in the first column. This video does not explain the simplex method, it simply describes it.
from the drawing, how can i know if there is unused material or hours ?
You are producing 20 of each chair, which use 3m2, so in total you use 120m2 (40*3m2) which is the maximum allowed by the problem, so no unused material. The same for the hours, the full 1000 hours were used (20*40+20*10).
great
You sound like name explain
thank you!
awesome!
9:57 what dafuq ahahah
I am experiencing mathgasm. So elaborately put. Awesome video
good explanation
thanks for the straightforward explanation
I don't know why your channel isn't popular! Great explanation for people who don't have prior knowledge to such algorithm. Thanks!
Perfect man! Love that you implemented theory as well!