Simplex Algorithm Explanation (How to Solve a Linear Program)

This is a quick explanation of Dantzig’s Simplex Algorithm, which is used to solve Linear Programs (i.e. find optimal solutions/max value).

Topic Covered:
• What is the Simplex Algorithm?
• Why do we use it? What is it for?
• Converting Linear Program (LP) to Standard Form (with example)
• Converting Standard Form to Slack Form (with example)
• Algorithm Explanation
• Example of Simplex Algorithm
• Complexity (runtime) of Simplex Algorithm (i.e. efficiency)

[joshdominguez]

Ngl had me in the first half. The first had goos and his explanations were clear...The second guy was just like my prof who just reads off the slides.

[somtirthamukhopadhyay]

The best lecture available we don't need a table to solve simplex!!

[garp]

First off, thanks for the video. You clearly articulate how you utilize the simplex algorithm.

Now, could you make a video to explain why we must use each rule (I.e why apply 1, 2, 3, ...)? That would help tremendously! Again, thank you!

[Lunatic]

Its really confusing how you went from Z = ax + yb and S = c - (ax + by) to this reverse way, where your slack variables are called d, e, f and your previous x and y became a and b.

For the future i would recommend staying with one style of named variables and not switch it around, because it makes following what you do way harder than it should be.

[samiazaman]

At 5:54, the answer should be a 6-tuple (instead of 5); is missing a 0, I believe..

[leechen]

Great explanation. Pivot 2 "Switch roles of b and f?"

[svily]

I can read the books myself... :D Expected a bit more oversight. But it's apparently a tricky subject. I read an article about auto-tuning PID controllers, and a guy in the comments suggested some climbing simplex algorithm... so been reading / watching for a good explanations. I have a book, but it's basically an old "Basics of mathematical cybernetics" ... something like this, thing, it's unapproachable.

[mirmd.asifhossain]

2:37 To apply rule 4 the quation 2 should be -x' + x'' + z' - z'' <= -6 . Since we need to multiply by -1 in both side. Please tell me if I am correct.

[ethanzhang]

At 5:59 I think there is a typo. Current solution should be(9, 0, 0, 0, 21, 6).

[MrsSMouse]

such a simple and neat explanation! thanks!

[zy]

So Simplex method is essentially checking all the corner points of the polygons. But, graphically, why would the negative sign indicates a better solution?

[MathsOwl]

in the basic solution part of the video, when Z = 0 + 6a + 5b + 4c, I we want to maximise that solution, and it has a positive coefficient that we select.
What if that was a minimise problem and all the coefficients turned negative as instructed in the first half of the video?
then we couldnt select any variable because all thier coefficients would be positive.
Please disambiguate.

[rishikaley]

At 2:44, shouldn't we include z`-z``<=0 also?

[ArkoSarkar]

Can anyone explain how x is a non negative constraint here in the initial step?

[shreyassingh]

bitch went from x, y, z to a, b, c and I died

[pierrestober]

Setting all non-basic variables to 0 doesn't always yield a basic solution. It is only the case if the vector b is positive in the standard form Ax<=b.

[kishoregupta]

hey there is a mistake at time point 6.02 in ur video there are 6(i.e. a, b, c, d, e, f) variable in ur method that time but while writing the best solution u have only taken 5

[c.d.premkumar]

Isn't there any video that explains how the solution is obtained. All the videos show only a mechanical routine without explanation.

[Phuongo-hhjj]

I think this video has a major mistake, when you convert minimize function to maximize by multiply it with -1, in some case you will come up with objective function with all negative non-basic variable so you can't choose any variable to pivoting.

[jiatongyu]

I'm so stressed that the variables are a, b, c... instead of subscripts form LMAO