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

In this lesson we learn how to solve a linear programming problem using the dual simplex method.
Note: You don't need to write the dual formulation of a problem to use the dual simplex. The Dual simplex is to solve the dual of given problem without actually writing its dual formulation. Sometime solving the dual problem is more economic (time -efficient) than primal problem. Since according to the dual theorem the value of primal and dual programming are the same at the optimal solution, we prefer to solve the dual instead of the original problem.
In general, to solve a linear programming problem, assuming that RHS is greater than or equal to zero, you can solve the problem Using
1- Regular simplex when all constraints are in from of less than or equal.
2- Big M or two phase when there are equal or greater than or equal constraints.
Problems of type 2, can also be solved using dual simplex if certain conditions are true for the problem : optimality condition and infeasibility.
Two conditions to solve a problem using dual simplex:
Optimality: recall that the optimal condition is when all values in the row of Z of the simplex table are positive or zero for a max problem and when all values of z-row of the simplex table are negative or zero for a min problem
Infeasibility: It means that you have to have at least one negative in the RHS of your initial table.
So, if any the above two conditions are not true you cannot use the dual simplex to solve the problem. You might instead use the big-M or two-phase to solve the problem.

[@sxmirzaei]

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

[@odiocolombia]

Shokoufeh Mirzaei Thank you, beside you are beautiful, you are smart :)

[@ashkantaravati]

I was badly struggling with OR and was so desperate when I found these videos. You made my day. I'm in Iran, have less than a month to prepare for Master's entrance exam for Industrial Engineering, I haven't passed this course as my bachelor's degree is in computer engineering. So, خیلی ممنون، زنده بود، آرزوی موفقیت خانم دکتر!

[@sxmirzaei]

@@ashkantaravati Hi Ahskan, I am glad these videos were helpful. Hope you make it to a Masters program of your choice! Fingers crossed for you!

[@ashkantaravati]

@@sxmirzaei Thanks professor! 🤩

[@ctyc123]

Hi Shokoufeh, I know its been a long time ago, but how about max objective function?

[@kimbryanduenas]

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

[@sxmirzaei]

+Kim Bryan Duenas Thank you!

[@aleroux]

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

[@FPrimeHD1618]

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.

[@mouhamethfadalmarabyaidara4935]

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

[@BBoyXy]

Thank you so much. Compliments from Portugal!

[@babakkhajavi8545]

Really appreciate your awesome in detailed teaching. I couldn't find better than your description for dual simplex. Iranian proud of you. Many Thanks Shokoufeh Jan.

[@parthajitmazumdar5474]

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

[@MrOnizukakira]

VOUS ETES SPECTACULAIRE.... BRAVO..i barely can understand english and i understood this lesson :D thanks .

[@feyza4225]

I was so confused, now it all makes sense. Thank you very much!

[@ada4990]

It's very satisfying to watch your videos. Everything is summarized and simplified in a format that it's very easy to understand the concepts that I struggled with a lot during classes. Also, the handwriting is nice on the eyes and your voice is very soothing to the ears. Thanks for your effort, appreciated it a lot!

[@manindermanish3843]

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

[@AbhishekSingh-yc3dp]

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

[@denisbelousov9889]

You are the best teacher ever!

[@kuromimi_112]

thank u for this short yet concise explanation and i love your calm accent hehe

[@neverstopexploring9]

thanks for sharing this. keep up the good work. world needs more people like you :D

[@nesto7707]

Let me just say something... if you have this professor, you are lucky.

[@isikerhan]

Your videos helped me a lot. I appreciate it!

[@anlsevici581]

+Işık Erhan I totally agree

[@chrisjfox8715]

Thanks for the very clear video and explanation! I am a bit confused about something though [and the more I try to write out my question then the more turned around I get haha...] I see the caption clarification that you don't actually have to use the Dual formulation [despite you taking the time to show its setup] in order to perform the Dual Simplex Method. I get that using the Dual table can sometimes be the more time-efficient approach, which may be done whether the conditions necessary for the Dual Simplex Method are met or not...? I understand the conditions of being allowed to use the Dual Simplex Method (DSM), but what distinguishes the method itself from the Regular Simplex Method (RSM) using the Primal and from the RSM using the Dual...if conditions for being allowed to use the DSM are not so? Around the 3:05 mark, I believe what you're getting at is that you're using the Primal to perform the DSM to avoid the need to have to work out the Dual, but was that much work really saved here?

[@johnakudoro1543]

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

[@SagarmayBiswas]

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

[@giovannybuitron3726]

so what do you do when the objective function doesnt satisfy the requirements, eg a max function has all positive coef.?

[@gauravjoshi3566]

Thank you so much for the sensitivity analysis videos, they were really helpful.

[@petermambwe9430]

applause given good lecture...#zambian student 😊😊😊✔

[@battlegoose1831]

Thanks! your explanation is very easy to understand!

[@zahrarad2259]

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

[@javierespinoza3782]

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)

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

[@kunaldesarda1095]

Mam great explanation, it has really helped me. I have a doubt after making the tabulae if the question is of maximization type do we still to minimum test or we take the maximum of the ratios and key column?

[@richardgruss8171]

Thank you! Your explanations are very clear.

[@TheMichaelg1280]

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

[@sxmirzaei]

that's why you are not supposed to fast forward the video!

[@ManuelSilva-lv6un]

Lol, the same thing happened to me.

[@kocakOFarc]

thank you so much your videos helped me a lot :)

[@apprentice5271]

Are the elements in the z row, the reduced costs? If yes, in order to have the optimality for a minimization problem should be greater or equal than 0 not negative.

[@felixmd1993]

THANKS YOU A LOT!! please upload more videos!! you're great

[@erhanfindik2320]

Thank you very much for this example. It was very clear :)

[@ghozlanelane7741]

Great explanation thank you teacher

[@ctyc123]

I love you, thanks!!!

[@sdaniel123]

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

[@sxmirzaei]

if your pivot row had -1 and 2 , then you only had one option to perform the min test, and you would do the test on the column that has the negative value (-1). "we don't consider the signs for the minimum test" applies when you are solving for a max problem where all the values are positive in the row of z (to have the optimality condition), then when you perform the test you are dividing the positive values of the z-row by negative values of the pivot row, and you get some negative values, but to find the min value, you don't consider the signs and just find the min absolute values to define the entering decision variable. does it answer your question?

[@marcellacella8293]

Do we need to consider the negative sign when we need to find the ratio in maximum problem?

[@bharathikiruba]

It was easy to Understand Mam

[@maryamhadi81]

Thanks so much this was such a big help

[@arjunvardhan8134]

Good explanation of the method but idk how you get the solution to the dual by the end?

[@IhsaanMuhiyadheen]

Great explanation! Thank you!

[@oualab8945]

really helpful thank you !

[@mathsandstatswithsajidrehm374]

One Question Plz, if the Coefficients in MAX objective function are negative ( or at least one) then can it be solved as you told coefficients in objective function should be Postive. Ans plz today...

[@Aquaeflavie81]

thank you very much. you helped me a lot

[@jellaoud9712]

At 7:30 shouldn’t you pick the first column x_1, because 1/3 is smaller than 2/4 ?

[@tuxu1598]

Very clear. Thanks.

[@achinijayawardane7402]

this was very helpful ;) thanks!!

[@leticiacardoso8844]

Thank you, helped me so much !

[@samithadon]

Really helpful. Keep up the good work. Thanks :)

[@ved.shankar]

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

[@oussamagacem4479]

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

[@vnknovn]

I don't really get why do we need to add artifitial variables sometimes: wouldn't it be enough by multiplying by -1 the adequate constraints?

[@piyumirangima2364]

Thank you madam ❤️

[@sethayieko7432]

Hello, why does the last constraint not negative in normal min.

[@arsalanyaghoubi6351]

sorry professor;why didn't you continue this process(finding pivots and elimination)till all Z values turn >= 0?

[@nukebarbarbarian3735]

Thank you

[@thotty6156]

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

[@Kafkaesque-kc1mi]

At 6:11, how do we know that having a negative RHS value makes it infeasible? I'm thinking -x1 - 2x2 + s4 = -150 should have some solution, buy I might be missing something obvious.

[@FcBarcelonaKid]

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

[@SunilparajuliKenshin]

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?

[@lilanthadilan5809]

Thanks a lot

[@ehsenhanif8808]

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?

[@sxmirzaei]

Ehsen Hanif please note that each constraint in the dual problem is associated with a decision variable in the primal problem. Thus, the RHS of the dual problem is the coefficient of the decision variables in the objective function of the primal problem. hope that helps!

[@soumyabrata111]

thanks Shokoufeh

[@alirezamasoumi2472]

tnx ;) really usefull

[@stellaarcher2062]

Thank you so much !!

[@BlankSabbath0410]

thank you very much!

[@d1rkn]

good job , Thank you

[@Centnl287NAve]

This video is MVP

[@husseinshafeeqhamza-1640]

thanks a lot !!!

[@HandsomeMaq]

hope i pass tommorow.

[@A7MeDG0L0L]

pass ?

[@androiduser3991]

RIP :(

[@androiduser3991]

our friend passed away.

Thank you for the video, much appreciated.

[@dobyxn]

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?

[@shokoufehmirzaei9759]

to be able to solve a problem using the dual simplex, the optimality condition which is the non-positive (non-negative) values in the z-row for a min (max) problem will be maintained thought the simplex. to solve what you explained just a regular simplex method is required and usually you don't run to this condition in the dual simplex if in the fist place you started it with an optimal table.

[@mustaphaejjayah520]

***** Hi, I have one QUT Please . if we have the all values RHS negative ,which one take ? the "MAX" or the "MIN" .

[@sxmirzaei]

Mustapha Ejjayah pick the most negative value. e.g. among -2, -3 and -5 , you pick the row associated with -5.

[@mustaphaejjayah520]

Shokoufeh Mirzaei Thanks

[@mustaphaejjayah520]

Shokoufeh Mirzaei I have another QUT please . how to deduce an optimal solution of thé primal,in your Method Dual Simplex ?? ?

[@yandhi4202]

Thank you :) Needed this for my exam

[@naifsadoun7314]

Gooood thanks 😘

[@vnknovn]

1:42 Where did that w came from?

[@mirotane1152]

What should I do, when instead of x1+2x2>=150 I have x1+2x2=150. Should I replace constraint containing = with 2 constraints containing >= and

[@sxmirzaei]

+miro tane Exactly! if you have a constraint which has = sign, you break it to two constraints with >= and & =150 and x1+2x2

[@francobalducchi539]

+Shokoufeh Mirzaei l l l

[@francobalducchi539]

+Shokoufeh Mirzaei l l l

[@mirotane1152]

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?

[@sxmirzaei]

+miro tane if you solving the primary problem using the big-m or two-phase method you should get the same answer 300. the reason you got 900 is that you solved the primal problem with a max objective function rather than min. to solve the primal problem you don't need to multiply the objective function with a negative value. you just solve what you have.

[@mirotane1152]

+Shokoufeh Mirzaei thank you so much I didnt see it :D

[@pren5948]

thanks.

[@karrarbarazanchi666]

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)

[@sxmirzaei]

+Karrar Barazanchi Hi Karrar. that is called formulation of a linear programming problem. I have not created any videos for those type of problems yet. But I will sometime in the future. for now I would suggest you practice as much as you can using examples of your text book.

[@tonmoychakraborty5470]

Thanx a lot :)

[@mustaphaejjayah520]

thank you Shokoufeh Mirzaei

[@shivani5386]

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

[@sxmirzaei]

In the dual programming the objective function is usually shown by w (instead of z)

[@shivani5386]

+Shokoufeh Mirzaei thanks

[@hemapanta3610]

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

[@sxmirzaei]

Junk Square when you run to this situation you can choose either one. However, it is a sign that you have a degenerate solution, meaning that one of your basic variables in the next table will be zero, and you will get stuck in a loop. one rule of thumb to get rid of degeneracy is to pick the decision variable with a lower index. For example, if the tie happens between x1 and x2, choose x1. this way hopefully you will get rid of degreanate solution fatser. Read more here: ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut07.pdf

[@aayushtaneja]

What changes do we make for maximization problem?

[@sxmirzaei]

If you have a max problem and all coefficients are negative (e.g. Z=-2x1- 3x2-4x3) then nothing in your solution method change. Solve it as explained in the video.

[@omarwothjonathan9722]

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.

[@sxmirzaei]

please watch my video for the simplex method.

[@omarwothjonathan9722]

Hi I did watch but it was based on that situation where a variable enters the basis in one table then leaves in the next basis. Take for instance x1 enters the basis in the table then after in the next table x1 leaves the basis

[@randomadventuresforfun3901]

a more in depth explanation not too bad

[@sathyachowdary1379]

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

[@sxmirzaei]

change the equality to two inequalities. e.g. x1+x2=1 can be written as x1+x2>=1 and x1+x2

[@ThePositiev3x]

Is it a mistake if we write no slack variables and just rearrange the equation just like we did with the objective function?

[@hemapanta3610]

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

[@sxmirzaei]

Junk Square in that case you already have an optimum table, if the RHS>=0.

[@ThePositiev3x]

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?

[@sxmirzaei]

If there is no optimality condition in the row of Z (mix of + and - signs), or no positive in the RHS you cannot solve it using other simplex methods. You might want to consider watching simplex method video.

[@ghozlanelane7741]

When R3 was calculated, you used the old row of R4 and not in Row 2 and 1 and in z you used the old R4

[@ahf733]

Allah (God) bless you Very good explanation

[@omarwothjonathan9722]

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

[@sxmirzaei]

you dont convert the problem to a max problem to solve it using the dual simplex. you use the primal for solving the dual without actually writing the dual problem.

[@omarwothjonathan9722]

Thank you understood

[@davidepaolillo1021]

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

[@sxmirzaei]

It is fine! Z can be negative! For exmaple, if your objective function is Z=-4x1 +X2 and your X1=10 and X2=5, then Z=-35. So it is ok to have a negative Z, as long as your variables are positive.

[@ajinkyakapadi7232]

nice video

[@fireworkguy8220]

1st steps are not explained

[@chkndelux]

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

[@sxmirzaei]

Wilson Camacho if you watch the video to the end, that is actually what we did . The first couple of minutes is to explain the underlying concept of the dual simplex.

[@chkndelux]

Shokoufeh Mirzaei Ok. Do you have a video to solve this algebraically ?

[@sxmirzaei]

Wilson Camacho kzbin.info/www/bejne/jZ-XZqOreJVreqM

[@Veenaali786]

thanks a lot nice explanation

[@sepehrsepy6470]

دلام