338 ACTIVITY 16: - Saint Mary's College



Math 438 ACTIVITY 17: Post Optimality Analysis [Part 1 - Sensitivity Analysis]

WHY: In actual use, the coefficients and constants in linear programming problems are often estimates and/or subject to change over time. One concern is: How badly is the solution affected by errors/changes in the data of the problem (coefficients, right-hand sides of constraints, etc.). Post Optimality analysis involves techniques for to tells us when we can determine the optimal solution for an altered problem without re-solving the problem and how to determine the new solution in these cases. [Not a big deal for the problems we are doing – but most real problems involve hundreds or thousands of variables and constraints]. These techniques are particularly useful for considering “what-if...” questions about possible future changes in the situation [as in your major project].

LEARNING OBJECTIVES:

1. Learn the meaning and the source of the “ranges” for the coefficients and constants in the solution of an LP problem

2. Learn how the ranges produced by the SIMPLEX program are used to predict the consequences of changing coefficients or constants in the problem .

3. Discover how to find the new solution after changing one of the coefficients or constants in a solved LP problem.

CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.

2. Accuracy of the answers to the table & chair problem after post optimality analysis.

RESOURCES:

1. Section 3.5: Strategic Mathematics

2. Activity 16 and your results from that Activity [in particular, solution of the Furnco problem]

3. 40 minutes

PLAN

1. Look over the model

2. Use your solution to the Furnco problem [from Activity 16] to answer the Critical Thinking questions

MODEL: [Examples 3.3.4 - 3.3.6 from pp.103 - 105]

minimize x1 - 2x2 - x3

subject to x1 + x2 + x3 ≤ 5

4x1 - x2 + x3 ≤ 6

x1 + x2 ≤ 4

x1 ≥ 0, x2 ≥ 0

Standard Form:

minimize x1 - 2x2 - x3

subject to x1 + x2 + x3 + x4 = 5

4x1 - x2 + x3 + x5 = 6

x1 + x2 + x6 = 4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0

Initial Basic Variables x4, x5, x6 Initial Nonbasic Variables x1, x2, x3

Initial basic Variables x3, x4, nonbasic Variables x1, x2

We obtained the optimal solution to this problem using the SIMPLEX program in Activity 16.

The final tableau is:

SOLUTION TABLEAU

4 5 6 1 2 3

3 1.00 1.00 0.00 -1.00 0.00 0.00 1.00

5 9.00 -1.00 1.00 2.00 5.00 0.00 0.00

2 4.00 0.00 0.00 1.00 1.00 1.00 0.00

-9.0 -1.0 0.0 -1.0 -2.0 -2.0 -1.0

-1.0 0.0 -1.0 -3.0 0.0 0.0

We observed that the basis is x3 , x5, x2 [The order does matter to get the correct order of columns in B, CBT etc. It’s the order in which we take the columns to get an identity matrix in the final tableau. Likewise, the order for B-1 is the order in which we’d take columns for an identity in the initial tableau – that’s easy to get if we used SIMPLEX]

The nonbasic variables are x1, x4, x6 thus CBT = [-1 0 -2], CDT = [1 0 0],

CBTB-1D - CDT = [-3 -1, -1], XT = [0 4 1 0 9 0], z = -9, B = [pic], D =[pic], B-1 = [pic], B-1D = [pic]

Now, let us examine the effects of various changes in the problem. There are several types of changes we might consider.

The key in every one is that the final basis will not be changed by any change that does not spoil

1. the optimality conditions [ CBTB-1D - CDT negative or 0 ]

2. the non-negativity requirements [all variables ≥ 0 and all right-hand sides ≥ 0] or

3. solution steps [essentially B-1 must not change]

although there will often be a change in the optimal solution and almost always a change in the value of the optimal solution. For any such change, we can easily [without re-starting the simplex method] find the new optimal solution and new value of the objective function.

If #1 is violated but 2 and 3 are not, we do not have to restart, but can continue pivoting from the current solution.

It is easiest to look at these in groups, though we always consider making only one change at a time:

1. Objective function coefficients

A. Objective function coefficients of non-basic variables: A change in a coefficient of a non-basic variable will change the solution precisely when it makes some entry in CBTB-1D - CDT positive. Since we are considering the possibility of changing an entry in CD , as long as the (changed) coefficient is larger than the corresponding entry in CBTB-1D the optimal solution will not be changed. The “lower bound” given by the SIMPLEX program is this corresponding entry of CBTB-1D. As long as the coefficient of the variable stays at or above this lower bound, neither the optimal solution nor the value will be changed. A change outside the range will require further pivoting

To see the effect of changing the coefficient of x1 from 1 to -1, note that the entry of CBTB-1D under the x1 column is -2. Since -1 is not less than -2, changing the coefficient to -1 will not affect the basis - so x1 will still be non-basic, and the new coefficient will not affect either the optimal solution or the value.

If we were to change the coefficient of x1 to -4 (from 1) , this would put the coefficient below -2 and this component of the CBTB-1D - CDT vector would become positive (+2, in fact), so we would have to pivot again to obtain the optimal solution [but we could put the +2 into the bottom row of the last tableau and pivot from there]

B. Objective function coefficients of basic variables: A change in a coefficient of a basic variable will change the optimal solution if it makes some entry in CBTB-1D - CDT positive [Such a change will always change the value z of the optimal solution - the question is whether it will make our solution no longer optimal.]. We need to see what changes we can make in one entry of CB without affecting the optimality condition. There are two ways to describe the change - by the new (changed) value of the coefficient and the new (changed) optimal value of the objective function z [the solution is not changed, remember] or by the amount of change (new value minus old value) is the coefficient and in the value of the objective function z).

First approach: If the changed vector is called CB* with the new (changed) coefficient c*, the requirement is that

CB*T B-1D - CDT is still non-positive. This gives a set of linear inequalities in c* whose solution set gives the range reported by the SIMPLEX program. As long as the new coefficient c* is in this range, the basic feasible solution will not be changed - but the value of the solution will change to CB*TB-1b (from CBTB-1b).

Second approach: As noted in the text [p 131], changing the coefficient of (basic variable) xk by an amount ( adds ( times the row of the final tableau corresponding to xk (except the basic columns) to the bottom row of the final tableau (including the last entry - which gives the value of the objective function). A change outside the range will require further pivoting [from the modified tableau]. The "allowable increase" and "allowable decrease" reported by the Excel sensitivity analysis are the maximum changes in ( that do not change the optimal solution [but the value of z will change]

For example, to find the range for the coefficient of x2 we use the fact that that the new coefficient c2 must satisfy

[-1 0 c2] B-1D - CDT≤ [0 0 0] - or [c2 -4 1 + c2] - [1 0 0] ≤ [0 0 0] - which gives c2 ≤ -1 [the range given by SIMPLEX - the "-999999.000" is the computer's equivalent of negative infinity].

If we wish to consider changing the coefficient of x2 from -2 (as given) to -1, this is a change of ( = 1 in the coefficient of x2 and will change the bottom row in the tableau from [ -9 -1 0 -1 -3 0 0] to [ -9 -1 0 -1 -3 0 0] + (1)[4 0 skip 1 1 skip skip] = [-5 -1 0 0 -2 0 0] - we still have the same optimal solution (for the changed problem) but the value of z now is -5 instead of -9 [an amount (( * x2.=(1) *(4) is added to the value of z]

If we change the coefficient of x2 to 1 (outside the range given in the printout) we would have a change of θ = 3 and the new bottom row would be [ -9 -1 0 -1 -3 0 0] + (3)[4 0 skip 1 1 skip skip] = [3 -1 0 2 0 0 0] - with the positive entry in the x2 position, we this would not be an optimal solution (for the new problem) - we would have to pivot again to find the optimal solution of this new problem.

2. Constraints

A. Right-hand side constants in constraints (the vector b): The key feature here is that the values of the variables must be non-negative. Any change that keeps B-1b non-negative will not change the basis but will change the values – of the variables (the solution) and of the objective.

A change outside the allowable range requires re-solving the problem from the beginning [since our last tableau no longer gives a basic feasible solution to start from]

To obtain the range for bk , we replace the original value with a variable - giving a vector b* - and solve the system of inequalities B-1b* ≥ 0 [Thus obtaining the ranges given in SIMPLEX]. If we change a value in b (within the ranges) the new optimal values of the basic variables [same variables, in the same order] are given by B-1b* and the new value of the objective function is given by CBTB-1b*.

For example, the constant in the first constraint is 5. To find the range on this constant within which the basis will not change, we solve the inequality B-1[b1 6 4]T ≥ 0 which gives b1 - 4 ≥ 0 , 6 ≥ 0, and -b1 + 14 ≥0 so our range is 4 ≤ b1 ≤ 14 [the range given by SIMPLEX].

If we change b1 to 12, then our basis is still { x3 , x5, x2} but the values come from B-1[12 6 4]T = [8 2 4]T and the objective function value from CBTB-1[12 6 4]T = [pic]= -16 so the optimal solution of the new problem is x1 = 0, x2 = 4 x3= 8 x4=0 x5= 2 x6= 0, and the value of the objective is -16. [It is worth noticing that we eased the constraint (≤ 12 is easier to accomplish than ≤ 5) and this allowed us to improve the objective function value (from -9 to -16) - this linkage is what we expect]

[We will see a simpler way to predict the change in the objective function value using the concept of shadow prices - but we still need to know the allowed range for the changes]

B. Coefficients of non-basic variables in constraints (a value - or even a whole column - in D): [Note: Any change in any constraint coefficient of a basic variable will require re-solving the problem from the start because changes in B change B-1 which determines the solution structure].

The key requirement is that CBTB-1D - CDT must still be non - positive with the new coefficient. If we change one or several coefficients in the column corresponding to (non-basic) variable xk we change the number in CBTB-1D- CDT corresponding to xk . If this new value CBTB-1D*k- CDTk is still non-positive, then the optimal solution and value are not changed - if it becomes positive, we must pivot again (from the modified last tableau).

For example, if we change the coefficient of x4 in the first constraint from 1 to 2, this changes the x4 (second) column of D from [1 0 0]T to [2 0 0]T and B-1D becomes [pic] (Notice that only the second column changes) CBTB-1D- CDT becomes [-2 -2 -1] - [1 0 0] = [-3 -2 -1] [Notice only the second entry changes] The solution we have is optimal for this new problem as well - so the value is also unchanged [same solution, same objective function, so same value].

3. Added constraints(a new row in the tableau): This is simple - if the optimal solution satisfies the added constraint, the optimal solution is not changed. Otherwise, the problem must be re-solved from the beginning [since we don't have a basic feasible solution to start from]

4. Added decision variables (a whole new column in the tableau): If CBTB-1Dk- CDTk is non-positive for this new column, our optimal solution and value are unchanged (the new variable is not basic and does not affect the solution). If this number is positive, we must add the column B-1Dk to our current tableau, with CBTB-1Dk- CDTk in the bottom row, and continue pivoting

CRITICAL THINKING QUESTIONS:

1. When does changing the coefficients of the objective function cause a change in the values xi of the optimal solution vector? How can you predict that this will happen from the ranges (printed by SIMPLEX) on the basic and nonbasic coefficients?

2. What is the optimal solution to the Furnco problem? Using information from the last (optimal solution) tableau and the initial setup, write B, D, CB, CD, B-1, B-1D and CBTB-1D- CDT.

3. Suppose that Furnco wishes to increase the selling price of an unfinished table to $100 per unit (but expects demand to be the same). What will this mean as far as the optimal solution is concerned? What will happen to the profit?

4. Suppose that Furnco wishes to increase the selling price of a finished chair to $120. What will this mean as far as the optimal solution is concerned? What will happen to the profit?

5. What will be the effect on Furnco's planning if the number of hours of skilled labor decreases to 3000 hours ? What will be the effect on the profit ? [Can we tell without re-solving?

6. What will be the effect on Furnco's planning and profit if a new process allows changing an unfinished table to a finished table with only two and a half hours of additional work? [Can we say without re-solving?]

7. Suppose we needed to add a constraint 3x1 + 2x4 - 3x6 ≥ 500, to the Furnco problem. Is the solution we obtained from the SIMPLEX program still optimal?

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download