How do you formulate a Linear Programming question involving simplex?
To implement the simplex algorithm, the inequalities must be transformed into equations using slack variables. The slack variables must then also be incuded in the non-negativity constraint.
Which constraint remains as an inequality?
The non-negativity constraint
What are slack variables?
Variables representing the amount of slack between an actual quantity and the maximum possible value of the quantity. They are added to the constraints to change them from an inequality to equations.
When can the simplex tableau method be used?
- When there are a maximum of 4 variables
- When there are a maximum of 4 constraints (in addition to the non-negativity constraints)
Explain how the simplex tableau method works:
- Any variables in a simplex tableau, that are not basic variables, have the value 0
- The simplex method always starts from a basic feasible solution, at the origin, and then progresses with each iteration to an adjacent point within the feasible region until the optimal solution is found
What is a basic feasible solution?
A solution where all the constraints are satisfied, but is a non-optimal solutions
Explain how to perform the simplex tableau method to maximise an objective function:
- Rearrange the objective function so that it is equal to a value (i.e P = 2x + 3y becomes P - 2x - 3y = 0)
- Draw the initial tableau, this should consist of the slack variables and the objective function down the left (in the basic variable column), and the variables and the slack variables along the top (with the value, θ value, and row operations columns to the right of these)
- Input your values into the initial tableau from the constraints and objective function (the θ value and row operation columns should still be empty)
- Scan the objective row (the bottom row) for the most negative number, this is your pivot column.
- For each row, divide the “value” by the corresponding term in the pivot column to calculate the θ value
- Now scan the θ values to find the smallest positive θ value, this is your pivot row
- Relabel the basic variable on this row (currently a slack variable) as the variable in the pivot column
- Perform a row operation so that the value where the pivot row and pivot column cross has a value of 1 (do this by dividing the row)
- Perform row operations on the other rows so that all the other calues in the pivot column are 0 (do this by adding are subtracting multiples of the pivot row)
- Repeat steps 4-9 until all the numbers in the objective row are non-negative
- Read off your solution by looking at the values of the basic variables (any variables that are not now in the basic variables column have a value of 0)
How do you know when you have achieved an optimal solution?
When all the numbers in the objective row are non-negative
What does it mean when all θ values are negative or 0 (i.e there are no positive θ values)?
No optimal solution can be found, this is because geometrically it relates to an unbounded region
Explain how to perform the simplex tableau method to minimise an objective function:
- Define a new objective function that is the negative of the original objective function (i.e P = 3x - y would become Q = -P = y - 3x)
- Perform the simplex tableau method to maximise this new objective function as normal.
- After you have maximised the new function, write you objective value as the negative of this value to minimise the original objective function
When do you have to use the 2-stage simplex method?
If one or more of the constraints is a greater than constraint (i.e x + 3y ≥ 10), then 2 stage simplex must be used
In two-stage simplex, how do you convert the constraints to equations?
- For any “less than” constraints (i.e x + 3y ≤ 10), you convert them into equations as you would with one-stage simplex - by adding a slack variable. For example: “x + 3y ≤ 10” would become “x + 3y + s = 10”
- For any “greater than” constraints (i.e x + 3y ≥ 10), you must subtract a slack variable (s) and add an artificial variable (a). For example: “x + 3y ≥ 10” would become “x + 3y - s + a = 10”
In two-stage simplex, why must you subtract the slack variable and add the artifical variable rather than just adding a slack variable as you would in one-stage simplex?
If you simply added a slack variable, it would mean that the slack variable must be negative to change the inequality into an equation. This is not possible as all slack variables ≥ 0. Therefore by subtracting the slack variable and adding an artificial variable, you avoid this problem
What is the two-stage simplex method for problems that include ≥ constraints?
- Use slack, surplus, and artificial variables, as necessary, to write all the constraints as equations
- Define a new objective function, I, to minimise the sum of all the artificial variables (I = -Σa)
- Substitute in the equations for the artificial variables and rearrange the equation so it is equal to a value (i.e I - x + y + s₂ = -11)
- Use the simplex method to solve this problem with I as the objective row (bottom row), but still including the original objective function (P) in the tableau (in the row above the bottom)
- If the minimum sum of the artifical values is 0 (Value column of I = 0) then the solution found is a basic feasible solution of the original problem, which is then the starting point for the second stage. Remove the new objective function row (I) and the artificial variable columns. Then use the simplex method again to solve this problem with the original objective function (P) as the objective row
- If the minimum sum of the artificial variables is not 0 (value column of I ≠ 0 when the optimal solution has been found (no negative values on bottom row)) then the original problem has no basic feasible solution
What is important to consider when calculating θ values?
You do NOT calculate θ values for an objective function (both P or I)
When do you have to use the Big-M simplex method?
It is interchangeable with the 2-stage simplex method:
If one or more of the constraints is a greater than constraint (i.e x + 3y ≥ 10), then Big-M (or 2 stage simplex) must be used
In Big-M simplex, how do you convert the constraints to equations?
Same as 2 stage simplex:
* For any “less than” constraints (i.e x + 3y ≤ 10), you convert them into equations as you would with one-stage simplex - by adding a slack variable. For example: “x + 3y ≤ 10” would become “x + 3y + s = 10”
* For any “greater than” constraints (i.e x + 3y ≥ 10), you must subtract a slack variable (s) and add an artificial variable (a). For example: “x + 3y ≥ 10” would become “x + 3y - s + a = 10”
What is the Big-M simplex method for problems that include ≥ constraints?
- Use slack, surplus, and artificial variables, as necessary, to write all the constraints as equations
- Alter your objective function, P, by minusing M times the sum of the artificial variables from the original objective function (where M is an arbitrarily larger number). For example, when the original objective function is “P = x - y + z”, the new objective function is “P = x - y + z - MΣa”
- Substitute in the equations for the artificial variables and rearrange the equation so it is equal to a value (i.e P - (1+M)x + y - z + Ms₃ = -4M)
- Use the simplex algorithm to maximise this problem as normal
What must you do if you are minimising a problem using Big-M?
- You must define the objective function Q as -P and then subtract MΣa from Q. You must never have +MΣa in your new objective function, it must be -MΣa
- Maximise Q with Big-M method as usual
- Flip the final value from positive to negative or negative to positive to minimise P
-
Decision - Graphs and Networks40
-
Decision - Algorithms17
-
Decision - Orders7
-
Decision - Critical Path Analysis19
-
Decision - Route Inspection8
-
Decision - Linear Programming7
-
Decision - Linear Programming: SIMPLEX19
-
Decision - Travelling salesman problem13
-
Decision - Other8
-
Core Pure - Roots of Polynomials12
-
Core Pure - Matrices + Linear Transformations36
-
Core Pure - Complex Numbers19
-
Core Pure - Series9
-
Core Pure - Differentiation7
