The Art of Linear Programming

Подписаться 29 тыс.

Просмотров 599 тыс.

50% 1

A visual-heavy introduction to Linear Programming including basic definitions, solution via the Simplex method, the principle of duality and Integer Linear Programming. #some3
More problems: slama.dev/youtube/linear-prog...
Made as my entry to SoME3: 3blue1brown.substack.com/p/so...
------------------
Timetable:
0:00 - Introduction
0:26 - Basics
3:44 - Simplex Method
11:47 - Duality
14:01 - Integer Linear Programming
17:31 - Conclusion
------------------
Source code: github.com/xiaoxiae/videos/tr...
Music (in the order it appears in the video):
► Cases to Rest by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Thannoid by Blue Dot Sessions: app.sessions.blue/browse/trac...
► ZigZag Heart by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Maisie Dreamer by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Night Light by Blue Dot Sessions: app.sessions.blue/browse/trac...
Software used:
► Manim (animation software): github.com/ManimCommunity/manim/
► Kdenlive (video cutting): kdenlive.org/en/
► ffmpeg (audio/video processing): ffmpeg.org/
► OBS (audio/video recording): obsproject.com/download
► arecord (audio recording): linux.die.net/man/1/arecord
► sox (audio processing): sox.sourceforge.net/
► Inkscape (vector image editing): inkscape.org/
► Midjourney (image generation): www.midjourney.com/app/
Social media:
► Website (for other things I'm up to): slama.dev/
► Patreon (if you'd like to support me): / ytoms
Thanks to Matěj Kripner, Martin Balko, Lucia Zhang, Václav Rozhoň (@polylog), Kateřina Sulková, Mohit Shrestha, Teo Tuicu and Tomáš Sláma (my dad, not me) for valuable feedback.
------------------
[EN] Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice
www.taylorfrancis.com/books/m...
[CZ] Přednáška Jiřího Sgalla: Lineární programování a kombinatorická optimalizace
iuuk.mff.cuni.cz/~sgall/vyuka...
[EN] George B. Dantzig (1982): Reminiscences about the origins of linear programming
apps.dtic.mil/sti/pdfs/ADA112...

Опубликовано:

14 май 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 381

@xcoder1122 10 месяцев назад

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.

@johankotze42 4 месяца назад

Your example reminds me of HP's examples in their old calculator (wire bound) manuals.

@terdragontra8900 4 месяца назад

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

@patrickchuan4550 3 месяца назад

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.

@OhsoLosoo Месяц назад

Ah another Harvest moon enthusiast

@johankotze42 10 месяцев назад

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.

@IxCIHAoX 8 месяцев назад

@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?

@greatcanadianmoose3965 7 месяцев назад

@@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!

@fabio.1 4 месяца назад

👀

@Alexander-oh8ry 10 месяцев назад

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

@YTomS 10 месяцев назад

Thanks for the kind words and the comment (you're right, the definitions were incorrect), I updated the website.

@ColinTimmins 10 месяцев назад

@@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. 😊

@socratesphilanthropy4937 10 месяцев назад

I have heard black hole . Rabbit hole? Thanks 4 the new term from an indian

@markgreen2170 9 месяцев назад

@@socratesphilanthropy4937 and now we have a new one 'bonus hole'

@mathfincoding 10 месяцев назад

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!!!!!!!

@payrimdwein9082 10 месяцев назад

just saw this after my course finished, this is good!

10 месяцев назад

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.

@jainickvishani5185 9 месяцев назад

EXACTLY, I just finished my finals last week and I see this video explaining the whole damn course 😂

@spb1179 10 месяцев назад

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.

@Ocara31 10 месяцев назад

Please, make about Non Linear Programming and also about Combinatorial Optimization. Your work is really fantastic!

@demr4921 10 месяцев назад

Damn right!

@gigantopithecus8254 4 месяца назад

what about nonconvex instaid

@juanhbiancuzzo1490 10 месяцев назад

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.

@teodorticu2628 10 месяцев назад

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!

@bejoscha 10 месяцев назад

Perfect pace, well thought of outline, clean and helpful visuals, good narration - what is not to love about this? You've gained a subscriber.

@protiumdev 10 месяцев назад

Thank you for all the work you put in these videos, I really learn a lot with them!

@VictorUn1 10 месяцев назад

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 !

@stjintje 10 месяцев назад

Wow, well explained! I struggled to get through my linear programming course for 2 years, but you make it seem so simple!

@prathameshsundaram7509 10 месяцев назад

I love how thorough your videos are! Thanks a ton.

@juan.araujonog 10 месяцев назад

I just found your channel and this is so good. You should really be proud of your work!

@ShashankEarth 7 месяцев назад

Excellently explained!!! What a great visualization video. Waiting for more videos on Simplex and Dual Simplex. Thank you so much.

@Erik_The_Viking 7 месяцев назад

Beautiful video! Well done with a simple example to show the concepts.

@sarkaholendova9080 12 дней назад

Wow, what a quality! I am blown away. The best video yet! Thank you :)

@ehsanabbasi6218 9 месяцев назад

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!

@timelygoose 6 месяцев назад

The best explanation on this topic that I've come across, thank you sir!

@victormanuel8767 9 месяцев назад

This is brilliant. You really blended theory and practical application into one cohesive whole.

@pedrocolangelo5844 10 месяцев назад

Seriously, I have not been this excited with a RU-vid 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.

@macroxela 10 месяцев назад

Check out Reducible, similar to 3blue1brown but about computer science topics. He's just as good.

@user-vx6zk5jj4e 7 месяцев назад

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.

@blllannnnk 7 месяцев назад

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!

@namesurname1869 6 месяцев назад

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.

@puneetkumarsingh1484 8 месяцев назад

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.

@user-gc6bb1tk9h 10 месяцев назад

Phenomenal video. Very well explained. This is so helpful! Simple explanation, great work sir!.

@lydianlights 10 месяцев назад

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!

@blackbriarmead1966 10 месяцев назад

satisfactorycalculator?

@lydianlights 10 месяцев назад

@@blackbriarmead1966 I made "yet another factory planner". I would post the link but RU-vid would probably eat it.

@adolfninh23 3 месяца назад

detail and down-to-earth explanation

@guitarljm 3 месяца назад

We need your next video!! Amazing stuff.

@beach_bum_dev 10 месяцев назад

Great video, instant sub. I look forward to more high quality videos such as this one

@neobrandsainclair3407 9 месяцев назад

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 :)

@felipenoleto166 Месяц назад

bro I'd pay to watch the continuation, very well explained!

@pablocasas1001 10 месяцев назад

This video is simply wonderful please keep explaining linear programming(and hopefully any convex as well)

@iFastee 10 месяцев назад

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

@DuongNguyen-dz8pb 10 месяцев назад

This is so helpful! Simple explanation, great work sir!

@samuelkhzym9442 7 месяцев назад

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 :)

@arhamhundia3039 5 месяцев назад

Amazing video really helped me understand, thank you, please keep on making more videos.

@feeelix 10 месяцев назад

Awesome video! I believe it's only a matter of time until your channel takes off

@tunafllsh 10 месяцев назад

Good job! This summarizes the course I took on LP.

@adamdemeter6963 4 месяца назад

Quality work! Well done.

@lucareale7161 10 месяцев назад

Phenomenal video. Very well explained

@ajk7868 10 месяцев назад

You are amazing, I was hopping to find a mathematical channel like this

@AlleBalle54 7 месяцев назад

great video, perfectly explained. Looking forward to the next one :)

@aglotgaming4660 10 месяцев назад

what nice video

@TrollFunMineMafia 9 месяцев назад

i remember doing this in university and not understanding a thing, now it all makes way more sense! thank you

@polares8187 10 месяцев назад

This video was amazing. Well created 💪💪

@jackninja1 10 месяцев назад

Absolutely excellent explanation!

@benwinstanleymusic 7 месяцев назад

Incredible video, thank you so much Tom! Helps so much with my optimisation course

@azfarahsan 6 месяцев назад

WHERE WAS THIS VIDEO WHEN I WAS STUDYING LINEAR PROGRAMMING GOOD VIDEO CONGRATS 👏🏼👏🏼

@porschepanamera92 10 месяцев назад

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 :)

@Adityarm.08 7 месяцев назад

This was done so well! Thank you.

@CharlesWinnip 10 месяцев назад

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!

@alejrandom6592 10 месяцев назад

Wow this made me realize linear programming is a lot less boring than what school makes it look like. Great video ♡

@ojcgv21 7 месяцев назад

this is an awesome video man, congrats!

@OgsLike 7 месяцев назад

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!

@zoom8370 10 месяцев назад

Nice one! This put a smile on my face.

@bugs-hl5jf 7 месяцев назад

Really amazing explanation. Thank you.

@giovannihernandez3208 9 месяцев назад

This is amazing. I could understand what the dual is more intuitively.

@darshagarwal8307 2 месяца назад

amazing stuff, I am working on recommender systems, and this has been quite helpful! You have just gained a subscriber :)))

@gabedarrett1301 7 месяцев назад

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

@andrewcpu 9 месяцев назад

Wow, just found your channel. Love it.

@ridazouga4144 10 месяцев назад

Maaan thaaaanks for sharing this amazing content👏👏👏👏

@jackgude3969 6 месяцев назад

I really like the background music. Very cosy math video.

@ishungchan 3 месяца назад

Thank you, I'm struggling with this course at my uni. Your video helps me understand it 🙏

@TheTaekwondo1996 9 месяцев назад

Thanks a lot, the video was really helpful and the explanation was very clear

@michaelangel7907 9 месяцев назад

Great! superb graphics, clear explanations. thanks

@priyanshugoel3030 9 месяцев назад

Okay that explained slack,surplus and basic variables pretty well.

@TheLoopesMan 10 месяцев назад

Great work as usual boss

@user-hy6cp6xp9f 10 месяцев назад

I love this, thanks so much for sharing

@dylanrandle 10 месяцев назад

Great video, thank you! Please keep it up!

@newtral6303 3 месяца назад

Please bring out more videos and continuation of this series on LP, ILP & MILP.

@albertn0855 8 месяцев назад

This videos is inspiring to me as I'm considering operations research as my main field of study as an applied mathematician!

@fawwazanvilen6625 5 месяцев назад

omg you showing duality was mindblowing

@innokentiyromanchenko1450 10 месяцев назад

thanks for your videos, they are excellent

@dilu4202 7 месяцев назад

vivid video！love it！

@electra_ 10 месяцев назад

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.

@ivanperica3731 2 месяца назад

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.

@frannaglic4628 10 месяцев назад

Great video! Good work sir.

@debasiskar4662 9 месяцев назад

Waiting for many more videos of similar type.

@jorgemelendez6536 8 месяцев назад

This is a great lecture. Thanks

@FaffyWaffles 10 месяцев назад

I love this use of Manim. So High Quality! New Subscriber is me.

@nhaho1473 8 месяцев назад

Thank you for this video, it's very useful for me .

@corlaez 7 месяцев назад

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!

10 месяцев назад

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!

@mohitduggal007 10 месяцев назад

Great explanation 👍

@pierre2693 Месяц назад

Excellent video!

@WavyB1 7 месяцев назад

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!!!

@tatolela1234 10 месяцев назад

I dont usually writte comments, but in this time i had to. sincerely spectacular explanation.

@kofiboamah8242 9 месяцев назад

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

@fuuryuuSKK 10 месяцев назад

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

@samarthtandale9121 7 месяцев назад

Love this video , really ❣️💯❣️

@kreuner11 10 месяцев назад

the 3blue1brown animation system is gonna be a standard mathematical video type soon (like whitepaper styles), if not already being one

@preston7376 10 месяцев назад

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!