formulating a problem:
- define variables
- find the constraints
- find the objective function
shade the…
unwanted region
find the optimal solution
draw an objective line and move is parallel, the last vertex to be crossed is the optimal solution.
branch and bound method
- calculate the optimised solution (not an integer, UB)
- truncate the x and y values and calculate the profit from this (LB)
- branch on the variable that was truncated the most (branch with values either side and signs to reflect this)
- solve the original problem with the new constraint from the branch
- reject the solution is the LB is less than the original truncated lower bound
- repeat the branching up to 3 times
minimise problems branch and bound
round up the non-integer value
Simplex for minimise
multiply profit by -1
for conditions:
if (expression ≥ constant) multiply through by -1
if (expression ≤ constant) leave it as it is
Setting up the simplex table
- rearrange profit so P - (expression) = 0
- write constraints each with their own slack
- write the table:
- rows and the profit+constraints
- columns are the variables, slack variables and constants (RHS)
Simplex method
- choose the most negative value in the profit row. This column is the pivot
- Complete ratio tests for constraint row:
- RHS/value in pivot column
the lowest non negative, non zero value is the pivot row - determine what you need to divide/multiply the pivot element by to make it 1. complete this operation to the whole row.
- determine row operations so the value in the pivot column is zero by adding/ subtracting multiples of the new pivot row.
- repeat
ratio test
RHS/value in pivot column
the lowest non negative, non zero value is the pivot row
pivot row
the lowest non negative, non zero value from the ratio test is the pivot row
pivot column
the most negative value in the profit row
When does simplex stop
when non of the values in the pivot row are negative
reading off results from a simplex tableu
If the column for a variable has all 0s and 1s read of the RHS value where the 1 is.
If the column has other numbers variable = 0
