Week 4 - Simplex method, Sensitivity analysis in LP

Question 1

In the simplex method, should we leave only basic or nonbasic variables in the objective function?

Answer 1

Nonbasic variables

Question 2

Bland’s rule

Answer 2

• prevents simplex from cycling
• choose the variable with the SMALLEST INDEX to ENTER, then the variable with the smallest index to exit

Question 3

For the starting solution in simplex, what to do if we cannot set the original variables to 0 (nonbasic)?

Answer 3

1. Add another variable per equation
   eg. s1 for constraint 1, s2 for constraint 2, s3 for constraint 3 etc.
2. Ignore the original objective function
   eg. instead of maximise 3x1 + 2x2, now MINIMISE s1 + s2 + s3
3. The original problem has a feasible solution where all s=0
   » so if we solve the modified LP to get a feasible solution where all s=0, we solve also the original LP
4. To solve the modified LP, minimise the sum of the s’s (as detailed in step 2)

*let all “s>=0” when we first write out

Question 4

In sensitivity analysis, what does the size & sign of a dual value tell us?

Answer 4

yi = 𝛿(optimum value) / 𝛿(RHS of effective constraint)
yi = the RATE OF CHANGE of the OBJECTIVE FUNCTION VALUE

Question 5

Sensitivity analysis - What happens to the optimal dual solution y* if the RHS of an INEFFECTIVE constraint changes?

Answer 5

y* remains feasible.
As long as the EFFECTIVE CONSTRAINTS of the optimal primal solution don’t change, the optimality conditions {y*} remain satisfied.

Question 6

Ineffective constraints
2x1 + x2 <= b1
How small can b1 be?

For effective constraints: sub in coordinates into the constraint to calculate the RHS values, eg. -6 <= b5 <= 4

Answer 6

1. Sub in x* = (1.2, 3.6) into the objective function to get =6
2. Optimal solution x* does not change as long as b1 is within the range 6 <= b1 < +∞

Question 7

Changes in an objective function coefficient
Ranges for Non-basic variables - eg. for a MAXimisation LP problem, what to do? (see notes for workings)

Ranges for Basic variables: optimal contour rotates counter-clockwise/clockwise around x* until PARALLEL to…
eg. -24 <= c1 <= 8/3

Answer 7

x* remains optimal as long as y* remains feasible for the dual
1. Sub in the y* solution into the dual constraint, then
eg. -∞ <= c2 <= 4

Question 8

Sensitivity analysis - 100% rule

Answer 8

You can COMBINE several changes of the SAME TYPE,
ie. objective coefficients or RHS coefficients but not both, if the CHANGES to each - as a FRACTION of what is ALLOWED - sum to < 1

Thus, the objective value change = the sum of the changes