2 Stage Simplex Flashcards
When do we have to use 2 stage simplex
This is when question is not in standard form
When might it not be in standard form
This is when it says ti minimise, or if constraints are GREATER THAN EQUAL to etc
What does normal simplex algorithm assume , and thus what does stage 1 do
Normal simplex algorithm assumes 0 0 is on the feasible region. As soon as you introduce other things and it’s no longer, the first stage of simplex essentially maps it to the FIRST vertex of the desirable region
From here yiu can just use normal simplex to do sk
How to convert say x +y > 2 to standard then
We,l as it’s greater this time we need to subtract a variable. This is known as a SURPLUS VARIABLE
However if now x and y are zero, the surplus variable becomes negative, which it can’t be as its defined as positive
Thus we must add an A1, an ARTIFICAL VARIBALE to prevent this
So what new variables must we define
Always define slack, that’s ONYL FOR LESS THAN
Greater than= surplus + artifical
After defining all variables what do we do
How to form equation with A
Introduce A= the sum of all artifical variables . We want to minimise this to 0
To make an equation with A, add all the equations together which contain ADTIFICAL VARIABLES
Now replace the artifical with A
- bring ti front and you now have equation for A!
Finally how ti setup INITAL table with new equation with A
This equation becomes the first, and then put in all the other equations
You should have just one more than normal
How ti minimise A once set up INITAL table
What’s the one step that changes
When do you stop
Everything is the same except for one step
- instead of looking for most NEGATIVE to find pivot coloum, now must find MOST POSITIVE (because you want greatest decrease)
Everything else same, and you stop when NO MORE POSITIVE IN THE FIRST A EQUATION. At this point, A is minimised and should be 0, so should a1+a2 etc all be 0
Okay now you have minimised A and the artifical variables , what next
(What to eliminate, then )
Now you can eliminate some rows and columns from table
- eliminate first colours as it has A in it
- eliminate all columns with artifical as they are 0 now
- eliminate first row too as this was the A equation row
You should now have a table with first equation P equation. Simply run SIMPLEX NOW!
What have we essentially just done, why minimised artifical
Want to do so because we don’t want the, to have meaning.
The first stage if simplex from 2 stage has translated int to first vertex of the feasible region , now we can run normal simplex
IMPORTANT = WHAT TO DO IF THERE IS AN EQUALITY CONSTRAIN LIKE X +Y =80?
Why do we do this?
Convert this into two inequities :
- x+y <=80
- x+y >= 80
Now convert back
- x+y+s1=80
- x + y -s2 +a1= 80
And define surplus and artifical
2) we do this so we can attack the line from both directions and ensure we cover everything
Why wouldn’t sn online solver be able to do an LP
IF inequality not on standard form for sxample
Remmeber what else will mean you have to use 2 stage
Check if 0 0 is a so,union, if inequities exceed this then yeah 2 stage must be used
How to use variables they give to reformulate LP as one stage
Not bad, just rearrange for variables and sub in, and you’ll see you now have inequalities with 0,0 on the region and so can be solved with one stage
IMPORTANT , if inequality is x+2y >= -6, do we need to use 2 stage?
NO, as you can see ,0 0 is still in the feasible region meaning it is in standard form!
Simply multiply inequality by -1 to flip sign and now you can just use slack variables like normal
DOMT LACK
