This is so interesting. I am retired now, but the last 20 years of of my working life was spent managing a dynamic truck allocation system in an opencast mine. I was mostly involved in the IT/IM side, but I knew the optimization was done with the simplex algorithm. Over the years, however, I got the impression that all the graduated industrial engineers did not understand what they were working with.I'll rewatch all of this a number of times.
@johankotze42 Interesting, i always wondered how an industrial engineer would apply Operations Research in pratice. We had to calculate the simplex by hand, but i always thought i would just use some excel plugin. I'll soon graduate in industrial engineering and am curious about key skills that you dont learn in uni. If you don't mind, what would you like to see more in upcoming IEs?
@@IxCIHAoX I mean look up the excel solver... I've learnt both doing it by hand, as well as excel, though currently I'm learning GUSEK to solve these problems!
@@IxCIHAoX I am an industrial engineer working as an operations research scientist in logistics. What I'd look for in a ie grad is decent programming skills (python/java/scala/c/c++/c# I don't care which), basic knowledge in statistics, basics in data handling and visualization and most importantly knowledge in OR and that does not mean simplex. Can you model mixed integer linear problems? Can you spot weak points in your model (big-M, symmetry, ...)? Can you write your model in your programming language of choice (for example python + pulp)? And maybe know a thing or two about heuristic solution approaches (greedy, local search, tabu search, genetic algorithms....)
I took multiple operations research classes in undergrad and I'm taking math graduate classes now. I never truly understood the connection between the primal and the dual problem until now. My mind is blown. Thank you so much!!!!!!!
just saw this after my course finished, this is good!
Рік тому+1
The way I always understood it is that most problems are either seen as you taking up resources to maximize a profit or you are minimizing your wasted money by emptying out your storage space. In the example, you are either making potatoes/carrots to get a profit or you are essentially trying to use as much seeds and fertilizers as possible to have the least waste.
Took me 2 watches on separate days while thinking about it in between to fully understand the slack loosening and tightening concept. And when it clicked, it felt really beautiful and made sense! Thanks for making it so clear.
Truly impressed by this video! As an industrial engineer, it was a challenge to learn and visualize the concept of LP and SIMPLEX. What I learned in 19 minutes from this video is comparable to my 4-month university course. Now I wish you had created this video 3 years ago. Thanks!
I appreciate that you are giving the real meaning behind each step instead of just throwing some random numbers and math operations like most other creators do.
Wanted to say that besides your excellent knowledge on the subject, it’s an extremely rare and precious talent you have of teaching and presenting complex subjects in an accessible way. Your visuals, audio, pace and use of humour is exceptional. You have a multi-million dollar talent that I hope you benefit from!
My college professor was not bad, but this video is something else. Really utilising the technology to present complex topics in such an amazing way. I am aware of how complex and immensly time consuming these types of videos get, but please do continue making these.
The initial problem looks way too simple ... because it is. Of course you plant as many carrots as you can and fill the rest with potatoes. Probleme solved. To make the initial problem more complex, just add in two other factors: The amount of farmland is also limited and potatoes provide way more yield per square meter than carrots do. Yet carrots grow faster and you could sow and harvest carrots twice a season but potatoes only once. And there you have a problem you cannot solve in your head any longer, yet that is a real world problem a farmer might face.
I actually played a lot of those farm-themed diner-dash-like games that has this sort of problem. Back then, I didn't know much about how to apply linear algebra (even though I aced at all my maths subjects). I did know Excel and used it to verify hunches I had. Now that I know more, I could say that… I wish people would start with ratios and portions. Then, they know how to better do comparisons. When to do what in which order. When do we apply infinite series. When is a line a dot, a plane, or an angle. When do we use a relative scale, an informed absolute scale, or a straight-out bonkers mathematical absolute scale.
cool... it would be nice to mention that most hard problems are non-linear, non-convex, can be part of the branch of discrete decisions where it becomes computationally unscalable to use certain linear algorithms, can be multimodal (or multiobjective)... and that's where heuristic and stochastic algorithms (that have a lot of generalizations of the linear programming field) enter to even try to tackle them
As an industrial engineering student who is currently studying integer LP this video has to be the best way to get a grasp of the topic. Looking forward to you getting deeper into these concepts.
Wow, this is awesome. The knapsack problem almost feels like it could be posed in discreet probability theory: given a random variable X, find a finite subset A of X that will maximize E[A] (=sum of p_i•x_i) and the sum of the chosen values x_i do not exceed a number k. Thanks for your website!
Im impressed by your website and ran hours deep into a mathematical rabbit hole on Wikipedia. Thanks, I unexpectedly learned a lot today! But i noticed that on your website, the description of the maximum independent set problem and minimum vertex cover problem are wrong and mashed together
@@YTomSStating the fact that you had a correction to make and corrected it gets an extra sub from me. Thanks for the content. I’m now getting back into programming. 😊
I love your videos! It feels like you explain complex things in a way that really makes them easy to understand. Your content always triggers my interest and I find myself going into rabbit holes online lol. Keep it up!
This is EXACTLY what I need to learn. One problem that came up at work was how to find the intersection of N half spaces in logarithmic time, and I couldn't understand the linear programming or the simplex method to do so... Will use this vid as a starting point to get into it. Thank you!
i got confused from 5:45 the loosening and tightening, simplex method... i even got more confused with the introduction of the slack variables... I have saved this video i hope to watch it several times till i get it. Thank you very much for a great video
Seriously, I have not been this excited with a UA-cam channel since I discovered 3blue1brown, and that must be about 3 years ago. Sir, what a masterpiece it is. Thanks for sharing it with us.
I used linear programming to solve for optimal production chains in the game Satisfactory! I made an online tool and everything. To be honest I just discovered that it was a well studied class of problems and downloaded a library to do it for me, haha. I knew vaguely there was "something, something simplex method" going on under the hood but I never truly studied the algorithm. Cool to see the geometry of how it actually works!
I struggled with linear programming when I was a student, but you explained it so well that it's easier for me to understand how it works. Thank you :)
that was really fun to watch. Thanks man I haven't took a math class in a while but, I was decently good at understanding math. You have a great way of explaining things and I love it! Keep up the content made me realize how much I loved math when I was taking it back then!
I found the answer intuitively as soon as the problem was presented (which is super simple of course) but it was interesting to see (around the 9:22 mark) that my logic to arrive to that answer is exactly the Dantzig's pivot rule. Thanks for the video it is super interesting that this intuition of mine has been reinforced by this method and that it can apply to more complex inequalities and more dimensions!
Phenomenal video! We are going through the simplex method in my linear optimization class and it was very difficult to grasp the process, let alone the intuition behind it. Thank you for making it :)
this is an absolutely amazing video. It's animations are so beautiful and illustrate the essence of the method. After watching the video, I can confidently say that I have some real understanding of linear programming! Thanks a lot!
I hope you make more videos on this subject! We mentioned linear programming in school, but not much more other than "yeah you can plug in numbers to this library and it works" which was quite dissapointing... i want to know how and why it works.
It's pretty amazing that you summarized the most important upper level Industrial (& Systems) Engineering course in under 20 minutes. When are you going to dive deeper into the iceberg??
very nice video! You really did a good job at explaining this concept very much intuitively :) actually, just a little improvement: When representing quantities or numbers with images or in this case circles, as you did at 14:56, one naturally compares the given shapes by their area they take up. Thus, a twice as heavy item having twice the height is a bit misleading, since the influence of the diameter is quadratic, and it should actually have √2 times the height. I mean, look how miniscule the 2kg circle looks in comparison to the 4kg one, even though it is just half of that, it certainly doesn't look like that - because the area is actually 1/4 of the 4kg one. And, intuitively, when thinking about them as wheights, it also makes a lot of sense to say that double the area of wheight makes for double the weight. So, just a thing for the future, when representing numbers as shapes, always think about the area, not their sidemeasures. Cheers!
the fact that the Simplex method is called that, together with the similar objective and visualisation, made me remember Reducible's video on the GJK algorithm
Finally, an intuitive explanation of the simplex method! Your content matches that of 3blue1brown in terms of quality and ease of understanding! Subscribed Also, you might want to number the x1 and x2 tick marks
With only two variables (x, y) and calling the objective function z, we have: z = ax + bx , with a and b constants, we have the equation of a plane. So the minimum and the maximum of z must be in the edges of the region. I find this way a lot easier to visualize and I always used it in teaching. The maximim or minimum can be on a whole side of the poligon, not only on a vertex.
I understand this in a similar way. In 2 dimensions, you know that by moving from a point in the middle of the region you can move up, down, left or right to reach an edge. It is guaranteed moving one of these ways will maximise your function. Then, once you reach an edge, as you move up and down that edge, your variable y = mx + c, the equation of the edge. So then you can rewrite your plane as a function of just x. Your function of x will be linear so depending on the gradient you can either keep on moving up or down the line to maximise your function. Once you reach a corner you have maximised your function along that edge, now you just need to check the other edges. This same reasoning applies to higher dimensions: imagine going from a 3d region to a plane to an edge to a corner.
Great video! Just wanted to comment that most people residing in the U.S. think of a “ton” as 2000 pounds. I needed to rewind the video in your first example in order to realize that you meant a metric ton. Not a big deal, just wanted to let you know about the potential confusion. Keep up the good work!
Very nice intro to LP. I've read about slack variables, and now they make more sense. I would love to see a follow-up to N variables, which makes it less intuitive without the geometric interpretation, and a brief note on convexity. Nonconvex optimization problems require some more exotic methods :)
Currently taking an optimisations class where we spent the first half of the semester covering the simplex method and co. I don’t mean to rush you, but if you could come out with the second video covering the dual simplex method and some of the other nuances within 8 weeks time (the final exam) that’d be greatly appreciated 😅
i was waiting anxtiously. for the Brilliant AD. And was pleased that the video was just pure knowledge. Thank you. For this, here is a LIKE and SUBSCRIBE!!!
Great video! Just a few notes: Maybe keep a reminder of what it means to be a tight or loose variable on screen (being zero or not) - I forgot and had to rewind a few times to get this😅; maybe visualize taking the ratio of variable (coefficients) and the constants (or bounds) of the inequalities more explicitly, the moving squares that highlight this were a little too fast for me. Looking forward to watching your next video!
@@RoyalUA-cam_PRO As far as I understood it, the introduction of the additional slack variables s1, s2 and s3 allows us to turn the inequalities that have to be satisfied into equalities that have to be satisfied. And the values of the slack variables directly encode whether the corresponding inequality in the original formulation is satisfied 'loosely' or 'tightly'. For example, when s1=0 this means that the current candidate for a solution (x1,x2,s1,s2,s3) corresponds to a candidate of the original formulation (x1,x2) where inequality number 1 is satisfied with equality, so x1=3000 in this example. Now, this kind of interpretation only really works for the slack variables s1, s2, s3. In the method we start with (see 6:53 in the video) x1=x2=0 and also call them the tight variables, because they are zero. This sounds a bit confusing, but it should become clearer once we forget our previous interpretation of what it means for a (slack) variable to be tight. From now on it's easier to think "y is tight if and only if y=0". (The original "slack interpretation" might make sense again if we look at the dual problem... but I'm not sure.) Since we want to maximize the objective function 1.2*x1+1.7*x2, we want to get to the best solution candidate (x1,x2) such that the inequalities are satisfied and the objective is the largest. (We also use that this maximum is attained at some corner of the polygon defined by the inequalities. Otherwise the whole algorithm to move between corners wouldn't really work.) According to Dantzig's pivot rule, we now choose to 'loosen' x2. That means we want our next solution candidate (x1,x2,s1,s2,s3) to satisfy x2>0 instead of x2=0, since that is what it means for a variable to become tight. In order to get to another corner, we have to find among the (previously) loose variables that variable which limits us from taking x2 to be arbitrarily large. (We would want to make x2 arbitrarily large if possible since this would increase the value of our objective function. If it was possible to make x2 arbitrarily large, however, the whole model of the farmer's problem would be unrealistic since we can't produce infinite amounts of carrots or potatoes...) Every equality (or inequality in the original formulation) is linked to a single slack variable. We rearrange the equations to have the currently loose variables on the left hand side as function sof the chosen, to-be-tightened variable x2. Now we just increase x2 until one of the loose variables becomes zero. In our example we set x2=4000 which leads to s2=0, and so now s2 is tight and x2 loose. Since the functions corresponding to (previously) loose variables earlier are linear in x2 (or technically affinely linear), we can find a method to determine which function gets to zero faster by computing the zeros of the functions and choosing the smaller one. (We interpret this zero to be reached first if we visualize this process as going along the 'x2-axis'.) Here this leads to the zeros x2=4000 such that 0=s2=4000-x2 and x2=5000 such that s3=0=5000-0-x2. How does this relate to forming and comparing the ratios 4000/(-1)=-4000 and 5000/(-1)=-5000? If we had had different equations that needed to be satisfied where for example s2=4000-x2 and s3=5000-2*x2, we could similarly compute the zeros which would lead to x2=4000 to get s2=0=4000-x2 or x2=2500=5000/2 to get s3=0=5000-2*x2. Here we would choose s3 to be tightened based on the comparison 5000/2 < 4000/1 or equivalently 5000/(-2) > 4000/(-1). The last way of writing this inequality to see which loose variable should be tightened directly and solely uses the coefficients of the linear functions (or equations)! This allows us to write a program that can just automatically choose 'the variable which tightens first if we increase the value of x2' without thinking about the whole meaning behind that comparison of ratios! (More generally, if the equations were s2=A+B*x2 and s3=C+D*x2 we would compare either the zeros -C/D and -A/B and choose to tighten s2 if -A/B < -C/D or, equivalently, choose the maximum A/B > C/D.) So this is how these ratios appear in the algorithm. Hope I could explain my thought process sufficiently well^^'
cannot fathom why you chose “loose” and “tight” to use for your geometric analogy of the problem. It genuinely made the pivot section 10x harder to understand in a video that was otherwise very easy to follow along with.
I didn't want to use basic/non-basic, because that was something I always mixed up when learning about the algorithm. I felt like "tight/loose" would convey the meaning of 0/anything, but perhaps something like "zeroed/free" would have been better...
For the Knapsack Problem, you mentioned vectors, so I took the slope of each vector and took the best slope until the sack was almost full. Then I tried to fill the last 7 weight exactly and got 84, too
Only two minutes in, but the first problem heavily reminds me of the type of word problems I would see in the calculator section of the SAT when I was studying/taking it in high school.
Рік тому
Thank-you for this! Or should I say - děkuju? Finally someone from my country using manim and creating videos that I really enjoy watching! Keep up the great work - you have a sub from me :) Měj se!
This is so interesting. I am retired now, but the last 20 years of of my working life was spent managing a dynamic truck allocation system in an opencast mine. I was mostly involved in the IT/IM side, but I knew the optimization was done with the simplex algorithm. Over the years, however, I got the impression that all the graduated industrial engineers did not understand what they were working with.I'll rewatch all of this a number of times.
@johankotze42 Interesting, i always wondered how an industrial engineer would apply Operations Research in pratice. We had to calculate the simplex by hand, but i always thought i would just use some excel plugin. I'll soon graduate in industrial engineering and am curious about key skills that you dont learn in uni. If you don't mind, what would you like to see more in upcoming IEs?
@@IxCIHAoX I mean look up the excel solver... I've learnt both doing it by hand, as well as excel, though currently I'm learning GUSEK to solve these problems!
👀
@@IxCIHAoX I am an industrial engineer working as an operations research scientist in logistics. What I'd look for in a ie grad is decent programming skills (python/java/scala/c/c++/c# I don't care which), basic knowledge in statistics, basics in data handling and visualization and most importantly knowledge in OR and that does not mean simplex. Can you model mixed integer linear problems? Can you spot weak points in your model (big-M, symmetry, ...)? Can you write your model in your programming language of choice (for example python + pulp)? And maybe know a thing or two about heuristic solution approaches (greedy, local search, tabu search, genetic algorithms....)
I took multiple operations research classes in undergrad and I'm taking math graduate classes now. I never truly understood the connection between the primal and the dual problem until now. My mind is blown. Thank you so much!!!!!!!
just saw this after my course finished, this is good!
The way I always understood it is that most problems are either seen as you taking up resources to maximize a profit or you are minimizing your wasted money by emptying out your storage space.
In the example, you are either making potatoes/carrots to get a profit or you are essentially trying to use as much seeds and fertilizers as possible to have the least waste.
EXACTLY, I just finished my finals last week and I see this video explaining the whole damn course 😂
This topic has to be one of the most important things I’ve seen this year. So useful. That’s crazy what you could do with this.
18 mins of your video is more helpful than 4 hours at my class. Thank you so much
Took me 2 watches on separate days while thinking about it in between to fully understand the slack loosening and tightening concept. And when it clicked, it felt really beautiful and made sense! Thanks for making it so clear.
This is some 3Blue1Brown quality level of quality! I am genuinely shocked by how good this video and the explanation is! Thank you.
Easily the best video on linear programming
Your work will impact generations to come and uplift the knowledge of people who are at a disadvantage. Thanks a lot
Perfect pace, well thought of outline, clean and helpful visuals, good narration - what is not to love about this? You've gained a subscriber.
Truly impressed by this video! As an industrial engineer, it was a challenge to learn and visualize the concept of LP and SIMPLEX. What I learned in 19 minutes from this video is comparable to my 4-month university course. Now I wish you had created this video 3 years ago. Thanks!
Okay that explained slack,surplus and basic variables pretty well.
i remember doing this in university and not understanding a thing, now it all makes way more sense! thank you
I appreciate that you are giving the real meaning behind each step instead of just throwing some random numbers and math operations like most other creators do.
Please, make about Non Linear Programming and also about Combinatorial Optimization. Your work is really fantastic!
Damn right!
what about nonconvex instaid
Wanted to say that besides your excellent knowledge on the subject, it’s an extremely rare and precious talent you have of teaching and presenting complex subjects in an accessible way. Your visuals, audio, pace and use of humour is exceptional. You have a multi-million dollar talent that I hope you benefit from!
this is my first video of you that I've seen, and it's really amazing. i'm looking forward to seeing more videos in this series.
My college professor was not bad, but this video is something else. Really utilising the technology to present complex topics in such an amazing way. I am aware of how complex and immensly time consuming these types of videos get, but please do continue making these.
The initial problem looks way too simple ... because it is. Of course you plant as many carrots as you can and fill the rest with potatoes. Probleme solved. To make the initial problem more complex, just add in two other factors: The amount of farmland is also limited and potatoes provide way more yield per square meter than carrots do. Yet carrots grow faster and you could sow and harvest carrots twice a season but potatoes only once. And there you have a problem you cannot solve in your head any longer, yet that is a real world problem a farmer might face.
Your example reminds me of HP's examples in their old calculator (wire bound) manuals.
that you system described is still linear so the algorithm would still work, but it would be harder for the viewer to follow as a first example
I actually played a lot of those farm-themed diner-dash-like games that has this sort of problem. Back then, I didn't know much about how to apply linear algebra (even though I aced at all my maths subjects). I did know Excel and used it to verify hunches I had. Now that I know more, I could say that… I wish people would start with ratios and portions. Then, they know how to better do comparisons. When to do what in which order. When do we apply infinite series. When is a line a dot, a plane, or an angle. When do we use a relative scale, an informed absolute scale, or a straight-out bonkers mathematical absolute scale.
Ah another Harvest moon enthusiast
Wrong
aahhh I'm hoping there is a next video some day. It's so nice to look back at the stuff I learned at uni!
cool... it would be nice to mention that most hard problems are non-linear, non-convex, can be part of the branch of discrete decisions where it becomes computationally unscalable to use certain linear algorithms, can be multimodal (or multiobjective)... and that's where heuristic and stochastic algorithms (that have a lot of generalizations of the linear programming field) enter to even try to tackle them
That's why they are called "hard" problems. Isn't it?
I would even say not "most hard problems", but _all_ hard problems ...
As an industrial engineering student who is currently studying integer LP this video has to be the best way to get a grasp of the topic. Looking forward to you getting deeper into these concepts.
Wow, this is awesome. The knapsack problem almost feels like it could be posed in discreet probability theory: given a random variable X, find a finite subset A of X that will maximize E[A] (=sum of p_i•x_i) and the sum of the chosen values x_i do not exceed a number k.
Thanks for your website!
Wow this made me realize linear programming is a lot less boring than what school makes it look like. Great video ♡
I've just discovered your channel and when I finished the video I thought you would have more subscribers. The quality is mind-blowing, keep going !
Im impressed by your website and ran hours deep into a mathematical rabbit hole on Wikipedia. Thanks, I unexpectedly learned a lot today! But i noticed that on your website, the description of the maximum independent set problem and minimum vertex cover problem are wrong and mashed together
Thanks for the kind words and the comment (you're right, the definitions were incorrect), I updated the website.
@@YTomSStating the fact that you had a correction to make and corrected it gets an extra sub from me. Thanks for the content. I’m now getting back into programming. 😊
I have heard black hole . Rabbit hole? Thanks 4 the new term from an indian
@@socratesphilanthropy4937 and now we have a new one 'bonus hole'
WHERE WAS THIS VIDEO WHEN I WAS STUDYING LINEAR PROGRAMMING
GOOD VIDEO CONGRATS 👏🏼👏🏼
Thank you for all the work you put in these videos, I really learn a lot with them!
I love your videos! It feels like you explain complex things in a way that really makes them easy to understand. Your content always triggers my interest and I find myself going into rabbit holes online lol. Keep it up!
Excellently explained!!! What a great visualization video. Waiting for more videos on Simplex and Dual Simplex. Thank you so much.
This is EXACTLY what I need to learn. One problem that came up at work was how to find the intersection of N half spaces in logarithmic time, and I couldn't understand the linear programming or the simplex method to do so... Will use this vid as a starting point to get into it. Thank you!
What work do you do?
@@rohith9875 graphics programming for CAD systems. Basically visual tools for modelling etc.
@@preston7376 oh damn that's sounds pretty interesting
i got confused from 5:45 the loosening and tightening, simplex method... i even got more confused with the introduction of the slack variables... I have saved this video i hope to watch it several times till i get it. Thank you very much for a great video
Wow, well explained! I struggled to get through my linear programming course for 2 years, but you make it seem so simple!
Seriously, I have not been this excited with a UA-cam channel since I discovered 3blue1brown, and that must be about 3 years ago.
Sir, what a masterpiece it is. Thanks for sharing it with us.
Check out Reducible, similar to 3blue1brown but about computer science topics. He's just as good.
We need your next video!! Amazing stuff.
The best explanation on this topic that I've come across, thank you sir!
This is probably the most useful thing I’ve ever learned of since learning to breathe
I used linear programming to solve for optimal production chains in the game Satisfactory! I made an online tool and everything. To be honest I just discovered that it was a well studied class of problems and downloaded a library to do it for me, haha. I knew vaguely there was "something, something simplex method" going on under the hood but I never truly studied the algorithm. Cool to see the geometry of how it actually works!
satisfactorycalculator?
@@blackbriarmead1966 I made "yet another factory planner". I would post the link but UA-cam would probably eat it.
I struggled with linear programming when I was a student, but you explained it so well that it's easier for me to understand how it works. Thank you :)
Maths with storytelling, best video I ever watch❤
detail and down-to-earth explanation
that was really fun to watch. Thanks man I haven't took a math class in a while but, I was decently good at understanding math. You have a great way of explaining things and I love it! Keep up the content made me realize how much I loved math when I was taking it back then!
omg you showing duality was mindblowing
I really like the background music. Very cosy math video.
This is amazing. I could understand what the dual is more intuitively.
This is brilliant. You really blended theory and practical application into one cohesive whole.
bro I'd pay to watch the continuation, very well explained!
you bothered to explain the concept of duality which my university prof just didn't feel like doing. Thank you
Thank you, I'm struggling with this course at my uni. Your video helps me understand it 🙏
This videos is inspiring to me as I'm considering operations research as my main field of study as an applied mathematician!
Wow, what a quality! I am blown away. The best video yet! Thank you :)
I found the answer intuitively as soon as the problem was presented (which is super simple of course) but it was interesting to see (around the 9:22 mark) that my logic to arrive to that answer is exactly the Dantzig's pivot rule. Thanks for the video it is super interesting that this intuition of mine has been reinforced by this method and that it can apply to more complex inequalities and more dimensions!
Awesome video! I believe it's only a matter of time until your channel takes off
Beautiful video! Well done with a simple example to show the concepts.
Phenomenal video. Very well explained. This is so helpful! Simple explanation, great work sir!.
Phenomenal video! We are going through the simplex method in my linear optimization class and it was very difficult to grasp the process, let alone the intuition behind it. Thank you for making it :)
this is an absolutely amazing video. It's animations are so beautiful and illustrate the essence of the method. After watching the video, I can confidently say that I have some real understanding of linear programming! Thanks a lot!
Good job! This summarizes the course I took on LP.
I dont usually writte comments, but in this time i had to. sincerely spectacular explanation.
You are amazing, I was hopping to find a mathematical channel like this
great video, perfectly explained. Looking forward to the next one :)
Please bring out more videos and continuation of this series on LP, ILP & MILP.
I love how thorough your videos are! Thanks a ton.
I hope you make more videos on this subject! We mentioned linear programming in school, but not much more other than "yeah you can plug in numbers to this library and it works" which was quite dissapointing... i want to know how and why it works.
"Since planting a negative amount of seeds is difficult" I love it
0:16 - you clever bastard. Instant Like.
Turned out, it's actually trivial.
It's pretty amazing that you summarized the most important upper level Industrial (& Systems) Engineering course in under 20 minutes. When are you going to dive deeper into the iceberg??
I love the bot ❤ & it"s creators+intendors!
very nice video! You really did a good job at explaining this concept very much intuitively :)
actually, just a little improvement: When representing quantities or numbers with images or in this case circles, as you did at 14:56, one naturally compares the given shapes by their area they take up.
Thus, a twice as heavy item having twice the height is a bit misleading, since the influence of the diameter is quadratic, and it should actually have √2 times the height.
I mean, look how miniscule the 2kg circle looks in comparison to the 4kg one, even though it is just half of that, it certainly doesn't look like that - because the area is actually 1/4 of the 4kg one.
And, intuitively, when thinking about them as wheights, it also makes a lot of sense to say that double the area of wheight makes for double the weight.
So, just a thing for the future, when representing numbers as shapes, always think about the area, not their sidemeasures.
Cheers!
Makes total sense when you say it, didn't come to mind when making the video. Thanks, will keep in mind!
reminder that #SoME3 is ongoing, and this video definitely qualifies for it!
This actually is my submission for #SoME3 (tagged in the description), I'll also add a link to the SoME3 post 🙂.
the fact that the Simplex method is called that, together with the similar objective and visualisation, made me remember Reducible's video on the GJK algorithm
I JUST had an exam in mathematics in the modern world and Im kicking myself rn bc i didnt find this video a few hours ago
Wow, just found your channel. Love it.
I just found your channel and this is so good. You should really be proud of your work!
Finally, an intuitive explanation of the simplex method! Your content matches that of 3blue1brown in terms of quality and ease of understanding! Subscribed
Also, you might want to number the x1 and x2 tick marks
This is so helpful! Simple explanation, great work sir!
With only two variables (x, y) and calling the objective function z, we have:
z = ax + bx , with a and b constants, we have the equation of a plane.
So the minimum and the maximum of z must be in the edges of the region.
I find this way a lot easier to visualize and I always used it in teaching.
The maximim or minimum can be on a whole side of the poligon, not only on a vertex.
I understand this in a similar way. In 2 dimensions, you know that by moving from a point in the middle of the region you can move up, down, left or right to reach an edge. It is guaranteed moving one of these ways will maximise your function. Then, once you reach an edge, as you move up and down that edge, your variable y = mx + c, the equation of the edge. So then you can rewrite your plane as a function of just x. Your function of x will be linear so depending on the gradient you can either keep on moving up or down the line to maximise your function. Once you reach a corner you have maximised your function along that edge, now you just need to check the other edges. This same reasoning applies to higher dimensions: imagine going from a 3d region to a plane to an edge to a corner.
amazing stuff, I am working on recommender systems, and this has been quite helpful! You have just gained a subscriber :)))
Great video! Just wanted to comment that most people residing in the U.S. think of a “ton” as 2000 pounds. I needed to rewind the video in your first example in order to realize that you meant a metric ton. Not a big deal, just wanted to let you know about the potential confusion. Keep up the good work!
Thanks for the comment, I didn't know that a ton has multiple meanings :). Will keep it in mind for future videos!
Amazing video really helped me understand, thank you, please keep on making more videos.
Very nice intro to LP. I've read about slack variables, and now they make more sense. I would love to see a follow-up to N variables, which makes it less intuitive without the geometric interpretation, and a brief note on convexity. Nonconvex optimization problems require some more exotic methods :)
Incredible video, thank you so much Tom! Helps so much with my optimisation course
Currently taking an optimisations class where we spent the first half of the semester covering the simplex method and co. I don’t mean to rush you, but if you could come out with the second video covering the dual simplex method and some of the other nuances within 8 weeks time (the final exam) that’d be greatly appreciated 😅
I will have to watch this a few more times, I got lost with the introduction of slack variables. I appreciate the explanation, though!
This video is simply wonderful please keep explaining linear programming(and hopefully any convex as well)
i was waiting anxtiously. for the Brilliant AD. And was pleased that the video was just pure knowledge. Thank you. For this, here is a LIKE and SUBSCRIBE!!!
Absolutely excellent explanation!
Saying that planting negative seeds is "difficult" rather than "impossible" made me laugh. Great video!
I love this use of Manim. So High Quality! New Subscriber is me.
Great video!
Just a few notes: Maybe keep a reminder of what it means to be a tight or loose variable on screen (being zero or not) - I forgot and had to rewind a few times to get this😅; maybe visualize taking the ratio of variable (coefficients) and the constants (or bounds) of the inequalities more explicitly, the moving squares that highlight this were a little too fast for me.
Looking forward to watching your next video!
Yes...same issue except I still don't get it
@@RoyalUA-cam_PRO As far as I understood it, the introduction of the additional slack variables s1, s2 and s3 allows us to turn the inequalities that have to be satisfied into equalities that have to be satisfied. And the values of the slack variables directly encode whether the corresponding inequality in the original formulation is satisfied 'loosely' or 'tightly'. For example, when s1=0 this means that the current candidate for a solution (x1,x2,s1,s2,s3) corresponds to a candidate of the original formulation (x1,x2) where inequality number 1 is satisfied with equality, so x1=3000 in this example.
Now, this kind of interpretation only really works for the slack variables s1, s2, s3. In the method we start with (see 6:53 in the video) x1=x2=0 and also call them the tight variables, because they are zero. This sounds a bit confusing, but it should become clearer once we forget our previous interpretation of what it means for a (slack) variable to be tight. From now on it's easier to think "y is tight if and only if y=0". (The original "slack interpretation" might make sense again if we look at the dual problem... but I'm not sure.)
Since we want to maximize the objective function 1.2*x1+1.7*x2, we want to get to the best solution candidate (x1,x2) such that the inequalities are satisfied and the objective is the largest. (We also use that this maximum is attained at some corner of the polygon defined by the inequalities. Otherwise the whole algorithm to move between corners wouldn't really work.) According to Dantzig's pivot rule, we now choose to 'loosen' x2. That means we want our next solution candidate (x1,x2,s1,s2,s3) to satisfy x2>0 instead of x2=0, since that is what it means for a variable to become tight.
In order to get to another corner, we have to find among the (previously) loose variables that variable which limits us from taking x2 to be arbitrarily large. (We would want to make x2 arbitrarily large if possible since this would increase the value of our objective function. If it was possible to make x2 arbitrarily large, however, the whole model of the farmer's problem would be unrealistic since we can't produce infinite amounts of carrots or potatoes...) Every equality (or inequality in the original formulation) is linked to a single slack variable. We rearrange the equations to have the currently loose variables on the left hand side as function sof the chosen, to-be-tightened variable x2. Now we just increase x2 until one of the loose variables becomes zero. In our example we set x2=4000 which leads to s2=0, and so now s2 is tight and x2 loose.
Since the functions corresponding to (previously) loose variables earlier are linear in x2 (or technically affinely linear), we can find a method to determine which function gets to zero faster by computing the zeros of the functions and choosing the smaller one. (We interpret this zero to be reached first if we visualize this process as going along the 'x2-axis'.) Here this leads to the zeros x2=4000 such that 0=s2=4000-x2 and x2=5000 such that s3=0=5000-0-x2. How does this relate to forming and comparing the ratios 4000/(-1)=-4000 and 5000/(-1)=-5000? If we had had different equations that needed to be satisfied where for example s2=4000-x2 and s3=5000-2*x2, we could similarly compute the zeros which would lead to x2=4000 to get s2=0=4000-x2 or x2=2500=5000/2 to get s3=0=5000-2*x2. Here we would choose s3 to be tightened based on the comparison 5000/2 < 4000/1 or equivalently 5000/(-2) > 4000/(-1). The last way of writing this inequality to see which loose variable should be tightened directly and solely uses the coefficients of the linear functions (or equations)! This allows us to write a program that can just automatically choose 'the variable which tightens first if we increase the value of x2' without thinking about the whole meaning behind that comparison of ratios! (More generally, if the equations were s2=A+B*x2 and s3=C+D*x2 we would compare either the zeros -C/D and -A/B and choose to tighten s2 if -A/B < -C/D or, equivalently, choose the maximum A/B > C/D.) So this is how these ratios appear in the algorithm.
Hope I could explain my thought process sufficiently well^^'
cannot fathom why you chose “loose” and “tight” to use for your geometric analogy of the problem. It genuinely made the pivot section 10x harder to understand in a video that was otherwise very easy to follow along with.
I didn't want to use basic/non-basic, because that was something I always mixed up when learning about the algorithm. I felt like "tight/loose" would convey the meaning of 0/anything, but perhaps something like "zeroed/free" would have been better...
Waiting for many more videos of similar type.
For the Knapsack Problem, you mentioned vectors, so I took the slope of each vector and took the best slope until the sack was almost full. Then I tried to fill the last 7 weight exactly and got 84, too
So you just filled the bag one item at a time with the best price/weight item available each step?
@@bbjygm Yes, and then I tried to fill the last 7 weight exactly and got 84
A very nice explanation about linear programming and simplex, also I'd like to add a Turkish subtitle to this video if you accept.
You're very welcome to, subtitles in any language are a great help to others 🙂.
Great! superb graphics, clear explanations. thanks
Great work as usual boss
Only two minutes in, but the first problem heavily reminds me of the type of word problems I would see in the calculator section of the SAT when I was studying/taking it in high school.
Thank-you for this! Or should I say - děkuju?
Finally someone from my country using manim and creating videos that I really enjoy watching!
Keep up the great work - you have a sub from me :) Měj se!
the 3blue1brown animation system is gonna be a standard mathematical video type soon (like whitepaper styles), if not already being one
Maaan thaaaanks for sharing this amazing content👏👏👏👏
Nice one! This put a smile on my face.