Week 4

Question 1

What is sensitivity analysis?

Answer 1

It deals with questions in the following nature:

• Is the optimal solution still optimal with new parameter values?
• Is there a range of parameters values for which the optimal solution found remains optimal?
• Does the solution found remain feasible with new parameter values?
• Is there a range of parameter values for which the optimal solution found remains feasible?

Question 2

How can we check what changes in the constraints do to our optimal result?

Answer 2

We can rewrite the simplex problem to include delta₁, delta₂, delta₃, …..

Then if we just solve the simplex problem, we can see how the optimal changes. Note this formula only holds if the constraints are still met.

Question 3

How to calculate the optimal value, using matrix algebra?

Answer 3

B^-1 b^(bar) = x_B

Question 4

How to calculate the optimal value of using a new right hand side?

Answer 4

We just compute B^-1b^(bar) = x_B, if this is feasible then we’re done, if not we need to do the dual simplex steps.

Question 5

How to do a dual simplex step?

Answer 5

1. Make the negative value the leaving variable
2. Apply the minimum ratio test, on the absolue values of the quotient obtained by divinding the reduceed objective coefficients by the coefficients in the row of the learing variable that are negative.

Question 6

How to determine the interval of one of the constraints for which the solution remains basic feasible?

Answer 6

1. Find B^-1
2. Calculate the following: B^-1 b^(bar) + B^-1 delta_i ≥ 0
3. Solve and find the interval.

Question 7

How to determine the new reduced objective coefficients, if the values left hand sides change?

Answer 7

We can calculate using the following formula:

c_B^T B^-1 A_j - c_j + d_B^T B^-1 A_j - d_j

Question 8

How to determine the new objective function with changed coefficients?

Answer 8

Let d₁, d₂, … be the changes in coefficients. Then add to the current value the transpose of the vector with the d₁, d₂, … which are in the left optimal value in the tableau, and mutliply it with the coefficients in the row for every row that is non-zero.

Question 9

When does the new formula for changed coefficients remain feasible?

Answer 9

If the values in the objective funcion remain positive.

Question 10

What to do if the solution when changing the coeficients does not remain feasible?

Answer 10

Just apply (some) simplex steps.

Question 11

What are ILP?

Answer 11

Integer Linear Problems, so they only allow integers.

Question 12

What are binary variables?

Answer 12

Variables that can only be 0 or 1.

Question 13

What is a problem with ILP problems?

Answer 13

Because only a finite number of variables exist, we need to check them all, and we cannot do it really any faster.