24. Linear Programming and Two-Person Games

MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018
Instructor: Gilbert Strang
View the complete course: ocw.mit.edu/18...
KZbin Playlist: • MIT 18.065 Matrix Meth...
This lecture focuses on several topics that are specific parts of optimization. These include linear programming (LP), the max-flow min-cut theorem, two-person zero-sum games, and duality.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@EranM]

People like Gilbert Strang should get to go back in time so we can have them forever in our society.

[@georgesadler7830]

Professor Strang ,this is a really useful lecture that starts with classical topics in mathematics. Linear Programming and Two- Persons Games are large topics in applied mathematics.

[@shankarshrestha4764]

I Love Gilbert Strang

[@archibaldgoldking]

these are new things in math , im very excited to see this

[@JoyTheDataScientist]

Wow, watching the expected payout be equal for both x and y was exhilarating. Fantastic lecture

[@carlosv.ramirezibanez3305]

Woooow explica bastante bien, es muy claro y lo hace interesante, muchas gracias

[@fatihamasyali]

40:09 zeros sum games: No lawyers involed :)

[@childybless]

Thank you so much, best explanations and always interesting to follow

[@brainstormingsharing1309]

Absolutely well done and definitely keep it up!!! 👍👍👍👍👍

[@gwonchanyoon7748]

Life is beautiful like this math!

[@JulieIsMe824]

Really useful lecture!

[@neoneo1503]

simplex method 11:00

[@edufer111]

The 2 players could be called Xavier and Yasmin, so X is for Xavier and Y is for Yasmin :-)

[@user-rn6ff8fq5n]

I can not understand the pay off matrix game. Pleasr explain.

[@mohamedf8859]

53:33 He speaks facts here

[@keithmaliko4511]

9:37 he is suggesting points that will maximize the problem?

[@Maxwaehrens]

If you just put the cut across the three final lines (5, 1 and 8) you also end up with 14. However, is there any reason why you would choose one or the other?

[@assafv1]

You need to calculate the flow value for all possible cuts and take the minimum. This minimum can be achieved at more the one cut.

[@Catloverassam]

What is the restriction on the number of decision variables and constraints in an lpp ?

[@juliettemly44]

Great lecture, thanks a lot ! Just a little question : at 41:00, isn't the saddle point supposed to be a minimum for x in its row and a maximum for y in its column ? Or maybe the opposite works too ? But if there were 2 saddle points in a matrix, then they would be equal... I'm a little confused.

[@andrewwatson6473]

A saddle point in this case is a state in which both x and y cannot improve their outcome by changing just their moves. From X’s perspective they cannot do better by picking row 2, while y remains at column 2, because 8>2. From Y’s perspective they cannot do better, while x remains at row 1, because 2

[@shauryagoyal8770]

legend

[@somerandomguy8361]

36:50 It is not p and lp, it is p(polynomial) and np(not polynomial). I think he misspoke about it.

[@ky8920]

np:nondeterministic polynomial*

[@naterojas9272]

When he speaks I'm able to download mathematical facts just by watching 👽

[@iwonakozlowska6134]

"three person game" !

[@alexgold4965]

Too bad not technical enough

[@planktonfun1]

Its really sad that old people are still working they should be retiring but can't because of the economy :(

[@childybless]

I don't think he is doing this because of money

[@planktonfun1]

@@childybless why does he do it then, he looks like he's suffering and just wants some rest

[@childybless]

@@planktonfun1 whaaat, he looks like he enjoys giving the lecture? My grandpa also thaught lectures way beyond his retirement age, he loved doing it.

[@planktonfun1]

@@childybless dude, the guy is shaking, probably has parkinsons already, he's not happy.

[@childybless]

@@planktonfun1 I think we will never know unless we ask him