Return to the
List of Activities This activity is designed to help you discover how to obtain new solutions for linear programming problems without starting from the beginning when we change the constraints or objective function after solving the original problem. This ability to do post optimality analysis will be helpful when analyzing the results of your major project. It will help you answer "what-if" questions for clients you work with in your future profession.
minimize -3x1 - 2x2
subject to
2x1 + x2 <= 80
x1 + x2 <= 50
x1 >= 0, x2 >= 0
Standard Form:
minimize -3x1 - 2x2
subject to 2x1 + x2 + x3 = 80
x1 + x2 + x4 = 50
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0
Basic Variables x3, x4, Nonbasic Variables x1, x2
We obtained the optimal solution to this problem using the SIMPLEX program in Activity 15. We observed that
CB' = [-3 -2], CD' = [0 0], CB'B^(-1)D - CD' = [-1 -1], X' = [30 20 0 0], z = -130, B = | 2 1 |, D = | 1 0 |, B^(-1) = | 1 -1 | = B^(-1)D. | 1 1 | | 0 1 | |-1 2 |
Now, let us examine the ranges given in the Sensitivity Analysis section of the printout. For the non-basic variables x3, x4, there is only a lower bound on their objective function coefficients. This is because CD must be greater than CBTB-1D to maintain optimality, but CD has no upper bound. (Recall that for a BFS to be optimal we must have CB'B^(-1)D-CD' <= 0.) A change in the objective function coefficient of a non-basic variable will change the optimal solution precisely when it makes some entry in CB'B^(-1)D-CD' positive. Let's try changing the coefficient of x3 from 0 to -1. Since x3 is non-basic, we merely have to check to make sure it stays nonbasic. If it does the solution will not change. Using Procedure 3.5.2 on page 132, we note that theta = -1. Thus we subtract -1 from the bottom row entry under the x3 column in the final tableau and note that it becomes -1 - (-1) = 0.
Suppose that we want to change the coefficient of x3 to -2 (from 0). Then theta = -2 and the entry in the bottom row of the final tableau under the x3 column would become 1, so we would need to pivot again and bring x3 into the basis to obtain the optimal solution.
The ranges for coefficients of basic variables and for the right side constants have both upper and lower bounds. As long as we stay within those bounds, we can compute the new optimal solution without pivoting. For example, if we change the coefficient of x1 from -3 to -2, we apply Procedure 3.5.1 on page 131. Note that theta = 1 and it is in position 1 of CB since x1 is the first basic variable. Thus, we multiply the first row of the final tableau by 1 and add it to the bottom row, obtaining 0 -2 0 0, with the new objective function value -100. Note that we do not change the entries under the basic variables when we add theta times the kth row to the bottom row. We see that the solution x1 = 30, x2 = 20, is still optimal but the new objective function value is -2(30) - 2(20) = -100.
Suppose that we want to change the coefficient of x1 to -1 (outside the range given in the printout). Here theta = 2 and the new bottom row becomes 1 -3 0 0 with z = -70. The given solution is no longer optimal because there is a positive entry in the bottom row, so we would have pivot one more time to find the new optimal solution.
Note that we can only change the b values within their bounds. Otherwise, at least one will become negative and we will have to start the SIMPLEX method from the beginning. Let us change b1 from 80 to 90. The new column in the final tableau corresponding to the b vector will become B-1 times the new b vector: i.e. [40 10]' and the new solution is [40 10 0 0]. The new z value is CB'B^(-1)b' = -3(40) - 2(10) = -140.
Changing any other column in the initial tableau can be handled in a similar manner. If the bottom row entry becomes positive after multiplying that column by B-1, we would have to pivot again, thus changing which variables are basic.
Adding a new constraint will not change the solution if it satisfies the constraint. Otherwise, you must solve the problem from the beginning. You cannot use post optimality analysis.
PROBLEM NUMBER 1
ITERATION 1
VARIABLE COSTS
0.0000 0.0000 -30.0000 -30.0000 -100.0000 -80.0000
SOLUTION TABLEAU
5 6 1 2 3 4
5 40000.00 1.00 0.00 40.00 30.00 40.00 30.00
6 6000.00 0.00 1.00 2.00 2.00 5.00 4.00
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 30.0 30.0 100.0 80.0
ITERATION 2
SOLUTION TABLEAU
5 6 1 2 3 4
3 1000.00 0.03 0.00 1.00 0.75 1.00 0.75
6 1000.00 -0.12 1.00 -3.00 -1.75 0.00 0.25
-100000.0 -2.5 0.0 -100.0 -75.0 -100.0 -75.0
-2.5 0.0 -70.0 -45.0 0.0 5.0
ITERATION 3
SOLUTION TABLEAU
5 6 1 2 3 4
4 1333.33 0.03 0.00 1.33 1.00 1.33 1.00
6 666.67 -0.13 1.00 -3.33 -2.00 -0.33 0.00
-106666.7 -2.7 0.0 -106.7 -80.0 -106.7 -80.0
-2.7 0.0 -76.7 -50.0 -6.7 0.0
SENSITIVITY ANALYSIS
SHADOW PRICES ARE CHANGE IN OBJECTIVE FUNCTION VALUE PER UNIT CHANGE
IN THE RIGHT HAND SIDE CONSTANTS.
PENALTY COSTS ARE CHANGES IN THE OBJECTIVE FUNCTION VALUE PER UNIT INCREASE
IN THE NON-BASIC VARIABLES.
RANGES ON C(J) REPRESENTS LIMITING VALUES OF COST COEFFICIENTS THAT WILL NOT
CHANGE THE OPTIMUM SOLUTIONS.
RANGES ON B(I) REPRESENT LIMITING VALUES OF RIGHT HAND SIDE CONSTANTS THAT
WILL NOT CHANGE THE OPTIMUM BASIC VARIABLES.
NON-BASIC PENALTY
VARIABLES COST
5 2.667
1 76.667
2 50.000
3 6.667
ROW SHADOW
NUMBER PRICES
1 -2.667
2 0.000
RANGES ON NON-BASIC C(J)
VARIABLE LOWER LIMIT
5 -2.667
1 -106.667
2 -80.000
3 -106.667
RANGES ON BASIC C(J)
VARIABLE LOWER LIMIT UPPER LIMIT
6 -20.000 999999.000
4 -999999.000 -75.000
RANGES ON B(I)
I LOWER LIMIT UPPER LIMIT
1 0.000 45000.000
2 5333.333 999999.000
PROGRAM PREPARED FOR THE SAINT MARY S TIME SHARING SERVICE (1981)
BY
D.E.MILLER & A.M.AGOSTINO
CONVERTED TO C (1994) BY P.D.SMITH
Return to the
List of Activities