Simolex Flashcards
What is the simplex algorithm and why use?
We saw cases weee you have 2D problems tryna maximise minimus, and we have been using GRAPHICAL METHOD so far
However with 3d this is long for sure, and 4 variables or 5 this is IMPOSSIBLE
Simplex method is an algorithm thst can allow us to do it and find an answer, getting an answer for max inisng or mini Ming
What goes on in simplex then
So basically you have your feasibility region, simplex start from 0,0 and decides in which direction to go to will be one that improves the condition the most . It then goes there
- it then stops at the vertex between intersections, and then decides if this is the optimal solution. It tells this by seeing if any change makes more negative etc
- if not it goes to next and checks and tests
- f8 ally once found that’s your answer
Basiclaly manipulating simultaneous, easier to use table method
How to do
1) re write everyhting in standard form and equations, define new variable
- must write each inequality as equation using slack variables
- define objective function as equation for profit etc
- bring all over to left hand side ti make standard form
Define s1 and s2 are slack vsrbibles
2) after forming table, identify first PIVOT
- look for most negative value in the Objective function
= this becomes pivot coloumn - in coloumn now divide RHS by each thing
- looking for the SMALLEST VALUE
= this becomes PIVOT
3) adjustment
- Make the value in pivot 1 and perform this calculation to rest of coloumn by dividing
- now must make other values in pivot coloumn 0 using simultaneous equations
4) check for negative value in top , which means?
Now after adjustment if there still is a negative value in the objective function, it means further adjustment CAN BE DONE , so must iterate algorithm all over again
5) pretend there is no negative value, now what
You have reached destination.
- look for the NON BASIC variables (coloumn that dint have one 1 and rest 0)
- these non basic take value 0!
And now look for basic (coloumn with one 1 and rest 0)
- this occurs when other 2 are 0, so the value for these variables is the RHS
- same for P
== you now have a value for x and y which maximises equation and value for P too!
What’s going on basically
- starts from 0 0 and needs to pick a direction that will improve the solution THE FASTEST
- thus it must pick the side with greatest gradient (THIS IS WHY WE CHOOSE THE MOST NEGATIVE OPTION)
- now there will be two intersections with lines and you want to test the one that occurs first!
- thus we need the value for this, and can find by using intercepts, and ( THIS IS WHY WE DECIDE RHS BY THAT VALUE TO FIND THE INTERCEPTS, AND WHICH EVER IS SMALLEST WE PICK AS PIVOT)
- next we basically simultaneously solve to find values of vertex
- now we check for improvement. If there is still negativity in p equation it means there is scope for coeefeicntd to improve.
- at the same time it might become worse, we can only be sure if these become 0
- perform another iteration to do som find new soltuion
We stop when no more negativity in top, thus this is the optimal solution
Interpreting a tableau
Remember that basic is 0 and 1, non basic something else
2) can’t be improved when no more negative. If there IS A NEGARIVE, then say that this still needs to be improved, and the solution may contain a value for slack
- if there is a value for slack, try interpret this. It may mean not all the resources have been used
- IMPORTSNT ti not try and deduce how much was left behind as we adjusted before low-key skew up the numbers
Must know how simplex works
Remember goes from vertex to vertex ti find optimal solution
2) ratio test ensure it does so in a way to improve soltuijn quickest
3) setting s1 and s2 or whatever to 0 is possible because if the way we can rewrite and equation as s1= 0 etc
What does a degenerate objective function mean
There may be MORE THAN ONE WAY to obtain optimal solution
If there are 2 1s in a row, what do you interpret as
Interpret as x+y= final thing, not both final thing , as it’s an equation
