12
Oct

# How to Solve a Linear Programming Problem Using the Dual Simplex Method

Hello everyone this is Mirzaei from Cal poly
Pomona, and in this lesson we are going to learn, how to solve a linear programming problem
using the Dual Simplex method. Consider a linear programming problem as shown on the
screen. Suppose we are trying to solve this problem. We have the option of choosing two-phase
or big M to solve this problem. Another alternative to solve this problem would be using the Dual
Simplex method. In Dual Simplex method, we are trying to solve the dual of a problem
instead of the initial problem. Because, according to a theorem, we know that the value of a
primal problem and its dual programming its going to be the same at the optimal point,
and that’s why instead of solving the problem we have the option of solve it dual problem,
because both at the end converge to the same optimal solution. So, let’s look at the dual
programming of this primal problem. Before writing the dual programming of this initial
problem, we need to normalize this problem. We know that for a minimization problem the
normal condition is when all the constraints have>=. Therefore, to change this minimization
problem to a normal form I have to multiply the first three constraints by -1. If I multiply
the first three constraints by -1, and keep the last constraint as it is, I am able to
write the normalized form of this minimization problem. Now, that I have a normal minimization
problem, I am able to write the dual programming of this problem, which is a normal maximization
problem. I can start solving this problem using the Simplex method. Because all the
constraints are in form of=or=sign. So, these are the two important criteria
that we have to have for a problem before start solving it using the Dual Simplex method.
In this problem, since we have all the coefficients of the objective function positive for a minimization,
our objective function is in form of optimality. Also, we have one constraint that has a>=sign
here, and, therefore, both conditions are met to solve this problem using the Dual Simplex
method. The first thing that we need to do before starting the Dual Simplex method is
to standardize this problem. The first three constrains of this problem can be easily standardized
by adding slack variables. Because all the constraints are in form of

a more in depth explanation not too bad

• samitha elvitigala says:

Really helpful. Keep up the good work. Thanks 🙂

• alireza masoumi says:

tnx 😉 really usefull

• Lilantha Dilan says:

Thanks a lot

• Ousmane condé says:

you are awesome! you tutorials helped me raise my grades 50% more

• Veena Ali says:

thanks a lot nice explanation

• Shokoufeh Mirzaei says:

Make sure you watch 2:42 to 3:08.

• Tac says:

Hey, thanks for this lecture. But I was wondering, at 7:05 you say we divide non-zero values of row of Z by negetive values of the pivot row. What if the pivot row had -1, and 2 instead?   Because at 7:30 you say we don't consider the signs for minimum test, so we only focused on size of absolute value of Z  divided by pivot row?

In short, if pivot row was -1 and +2, we'd get the same answer because the signs don't matter when doing the minimum test?

Best,

Shawn

Gooood thanks 😘

• dobyxn says:

Thank you very much! I have one question. If we had positive values at the rhs of the last step and some values at the row of z that are positive for this min problem, then, do we continue the steps of the simplex method to reach for only negative values at the row of z?i mean, do we continue with the regular simplex?

• Mustapha Ejjayah says:

thank you  Shokoufeh Mirzaei

• Wilson Camacho says:

why didn't you just multiply your 4th constraint by -1 to make things easier?

• d1rkn says:

good job , Thank you

• Junk Square says:

How to choose the pivotal element, if minimum test gives to equal values?

• Junk Square says:

In maximization problem we won't get any -ve value in row of Z, then how to perform minimum test?

• Ehsen Hanif says:

Hello. At 1:36 when you write down the next part of the equation. Why do you write >= 3 and >=4 ? Where did you get those numbers?

• Parajuli Sunil says:

Please show change of unrestricted variable if ith constant is in equal sing"=" then its ith dual variable must be stated as unrestricted. Can you briefly explain it?

• Zecon Mann says:

thnks a lot uable me to pass pass my b.tech math exam

• Karrar Barazanchi says:

How are you ..lde problem on the subject of linear programming .. when a professor at the University gives to the student in question and there are question directly equations and the objective function etc will be resolved directly by the graph … I have a problem when the teacher gives us a question, and this question be a way of words and the student who is extracted from the two variables here lies the difficulty I hope you to help us in some way in order to know how to extract the two variables of the question (x1 and x2) .. what is the way of thinking or to extract variables from so questions (thank you)

• MAZOUZI Zakaryae says:

VOUS ETES SPECTACULAIRE…. BRAVO..i barely can understand english and i understood this lesson 😀 thanks .

• Oualid Aberyem says:

• Javier Espinoza says:

Finally, someone explained the relation Primal-Dual and Dual Simplex, ive been reading Taha's book, but is unclear. Thank You! (btw: you're cute, i added you in instagram lol)

• Martin Čičmanec says:

Thank you for the video, much appreciated.

• miro tane says:

If I continue with your solution using primary simplex method I get Z*=900 and X2 = 225 , because in Z line is -1 which can be improved by primary simplex (every variable in z must be >=0). It pass through all constraints. So what is the right solution?

• miro tane says:

What should I do, when instead of x1+2×2>=150 I have x1+2×2=150. Should I replace constraint containing = with 2 constraints containing >= and <=? If yes, how exactly?

• Peng Ren says:

thanks.

• Marco Fidalgo says:

Thank you so much. Compliments from Portugal!

• Kim Bryan Duenas says:

If I could upvote this video a thousand times I would.

• Sagarmay Biswas says:

Thank you ma'm. You nailed it in just 10 minutes. Helped me a lot for my exam

• Işık Erhan says:

Your videos helped me a lot. I appreciate it!

• Carlos Felipe Oliveros says:

• BlankSabbath0410 says:

thank you very much!

• Pedro Lopes says:

thank you very much. you helped me a lot

• FPrimeHD says:

Great explanation, I definitely appreciate the work you put into this! Linear Programming is hands down the easiest math explained in the most complicated way lol.

nice video

• Tonmoy Chakraborty says:

Thanx a lot 🙂

• Soumyabrata Bhattacharjee says:

thanks Shokoufeh

• Unimedia says:

What does the W at 1 minute 50 second stands for? Please respond soon.

• Denis Belousov says:

You are the best teacher ever!

• Michael Gonzalez says:

I was deeply confused until I realized you just threw everything you explained away 3 minutes in.

• sathya chowdary says:

How to solve if we have an equality constraint???

• Richard Gruss says:

Thank you! Your explanations are very clear.

• Letícia Cardoso says:

Thank you, helped me so much !

• OMARWOTH JONATHAN says:

hi after converting the problem to maximization why didn't you solve it using simplex method

• OMARWOTH JONATHAN says:

How are you ? In simplex method how do you go about a problem when a variable enters the basis in one table then leaves the basis after in the next problem.

• harshanakelasha Withana pathirana says:

Good content. .. but for the love of he god please speak louder .. no hurry just take a breath and speak loudly. ..otherwise sleepy

• Mitch Rubiano says:

This video is MVP

• TechNation says:

hope i pass tommorow.

• ERHAN FINDIK says:

Thank you very much for this example. It was very clear 🙂

• Nathan Stuckey says:

Hi there!
First of all, thank you ever so much for your clear explanations, they really help!
I'm confused however; in another video ( https://www.youtube.com/watch?v=BctoW-x8cPI ) the method is applied to a maximisation problem with an objective function with all POSITIVE coefficients…and this contravenes the criteria pointed out in this video. Could you possibly shed some light on what's going on here? 🙂 Is the other video simply wrong or is there something I haven't understood correctly? 😀

• Niharika Saini says:

Thank you so much !!

• Ved Shankar says:

Could you explain how the dual problem is solved using matrices. I didn't quite understand the notation such as z=Cx

• Hanif Aulia says:

Thanks! your explanation is very easy to understand!

• Armandt le Roux says:

The amount of times I have rather watched this video than work through all the theory is uncountable – thank you for the great video 🙂

• Abhishek Singh says:

The best video out there for understanding Dual Simplex Method… Great work

Great explanation! Thank you!

• Aayush Taneja says:

What changes do we make for maximization problem?

• Kubilay Yazoğlu says:

Thank you very much, I have a question.
What would we do if in the new table there was no negative RHS but there is a one positive coefficient in the row of Z?

• maninder manish says:

ur voice is soo sweet i think i can never forget this dual simplex

• barnesdouglass says:

Beautiful, smart, and stunning
Explained extremely well, hopefully I do well on my quiz !

• PARTHAJIT MAZUMDAR says:

Was confused before watching this video as to what the heck has dual of an LPP got to do with the Dual Simplex method…This video made it clear the start itself..Too good 🙂

عاشقتم با این توضیح دادنتتتت 😍😍😍😍

• mouhameth fadal maraby Aidara says:

Flawless explanation. I appreciated the prelusion you made by first explaining the usefulness of this method before getting through the different steps of this lesson

• Bharathi Kiruba says:

It was easy to Understand Mam

• Jabro Jacob says:

What if we had only one inequality in the prime? the dual objective function would fall short of y2, y3, and y4.. I faced such a thing while trying to apply it on a simple Set Cover problem.

• achini jayawardane says:

this was very helpful 😉 thanks!!

• Oussama gacem says:

5:05' when you standard the problem, why did you kept the min on the objectif function?
isn't min(Z)=-max(-Z)?

• Tu Xu says:

Very clear. Thanks.

• John Akudoro says:

I have learnt a lot from this video….Many thanks!

• Raptors for the Win says:

Thank you 🙂 Needed this for my exam

• Behnam Ebrahimi says:

👌👌👌👍👍👍👏👏

• kocakOFarc says:

thank you so much your videos helped me a lot 🙂

• Davide Paolillo says:

if i get a negative rhs for z what should i do ?

• Hussein Hamza says:

thanks a lot !!!

• yo gmgm says:

OMG!! You're the best.. Thanks a ton