CHAPTER 4: Post-optimality analysis Flashcards
Example: Electric power generation
The management of a coal-fired electric power generating plant is studying the plant’s operational setup in
order to comply with emission standards under air pollution control laws. For the plant in question, the
allowed maximum emission rates are:
- Maximum sulphur oxide emission: 3000 parts per million (PPM)
- Maximum particulate emission (smoke): 12 kilograms/hour (kg/hr)
Coal is brought to the plant by railroad → stockpiles → conveyor belt → pulverizer unit → combustion chamber
Coal/ Sulphur Oxides in Flue Gas / Particulate (emission/ton)
Coal A/ 1800 PPM/ 0.5 kg
Coal B/ 3800 PPM/ 1.0 kg
The conveyor loading system has a capacity of 20 tons per hour regardless of which coal is loaded.
The pulverizer unit can handle at most 16 tons of coal A per hour, whereas it can pulverize up to 24 tons of coal B per hour.
Values of the steam output: 240£per ton for A; 200£per ton for B.
Objective: What is the maximum possible output of electricity (in terms of the
total value of the steam output)?
Formulation of the LPP
x_1= coal A used (ton/hour) x_2= coal B used (ton/hour)
LPP: maximise z= 24x_! + 20x_2 (value of steam output in 10£)
subject to
0.5x1 + x2 ≤ 12 (smoke emission)
x1 + x2 ≤ 20 (loading facilities)
(1/16)x1 + (1/24)x2 ≤ 1 (pulverizer)
−1200x1 + 800x2 ≤ 0 (sulphur)
where x1, x2 ≥ 0
The solution has been found using the simplex method. The initial and final tableaux are given below. x3, x4,
x5 and x6 are slack variables.
Initial tableau Basis x1 x2 x3 x4 x5 x6 Sol z −24 −20 0 0 0 0 0 x3 1/2 1 1 0 0 0 12 x4 1 1 0 1 0 0 20 x5 1/16 1/24 0 0 1 0 1 x6 −1200 800 0 0 0 1 0
Final tableau z | 0 |0| 6 | 0| 336 | 0| 408 x2| 0 |1 | 3/2 | 0| −12 | 0| 6 x4| 0 |0| −1/2 | 1| −12 | 0| 2 x1| 1 |0| −1 |0 | 24 | 0| 12 x6| 0 |0|−2400| 0|38400| 1 |9600
The optimal solution (total value of steam output) is 408, basic vars are x_2=6 and x_4=2, x_6=9600 and x_1=12. Non-basic are x_3 and x_5, with reduced costs 6 and 336, reduced for others are 0.
*sulphur oxide emission cap in terms of PPM (unit for ratio of volumes) and assume volume of flue gas is proportional to amount coal burnt , for A its αx1 and B αx1 (same constant of proportionality)
amounts of sulphur oxides in the two types of flue gases are then 1800αx1 and 3800αx2,
respectively
Total volume is α(x1 + x2).
so constraint 1800αx1 + 3800αx2 ≤ 3000α(x1 + x2) is simplified
*for pulverizer constraint x_1/16 and x_2/24 are times needed to process x_1 tons of A and x_2 of B when operating at full capacity. Given coal is used in one hour total processing time no more than 1
Example: Electric power generation, Reading information from the tableaux
BASIC MATRIX
Find the optimal basic matrix B and its inverse B−1
Optimal basic matrix is formed by basic vars columns in final:
x2, x4, x1 and x6 columns in the INITIAL tableau
B= [ 1 0 1/2 0 ] [ 1 1 1 0 ] [1/24 0 1/16 0 ] [800 0 -1200 1]
B-1 is formed by x3, x4, x5, and x6 columns in the OPTIMAL tableau basic vars in initial
B= [ 3/2 0 -12 0 ] [ -1/2 1 -12 0 ] [ -1 0 24 0 ] [-2400 0 38400 1 ]
In general, B^−1a_j is the jth column of the optimal tableau, where aj is the jth column in the initial tableau. The solution column in the final tableau is B^−1b.
Example: Electric power generation, Reading information from the tableaux
SHADOW COSTS
Find the shadow costs for the constraints from the optimal tableau
By Proposition 3.1, the shadow cost of a constraint is the same as the optimal reduced cost of the corresponding slack variable
(x_3 is the slack var for constraint 1 so r_1 is 6 etc )
r∗_3 = 6. r∗_4 = 0. r∗_5 = 336, and r∗_6 = 0.
NOTE
reduced costs in optimal sols
- If a decision variable’s reduced cost is non-zero in the optimal solution, we may consider raising (reducing) the price (cost) of the variable, so that it would become profitable to use that variable.
- The values of the slack variables tell us how much resources are left, which can be re-allocated or reduced.
Example: Electric power generation, Reading information from the tableaux
A device is marketed to reduce the sulphur oxide content of the gases by 10 per cent. Is it worthy to install the device?
The slack of the sulphur constraint (constraint 4) is x6 = 9600. Thus the sulphur constraint is NOT
binding, which means the sulphur emission is already below the government regulated limit. Therefore, there is no need to install the device to further reduce the emission.
ie because x_6 is positive and constraint is non binding
Example: Electric power generation, Reading information from the tableaux
One can increase by 10% of the pulverizer capacity. Suppose that the hourly capital cost to
provide the extra capacity is £300. Is it worth it to install the device?
Solution. The shadow cost for the constraint is 336 units per hour.
A 10% increase in pulverizer capacity results
in 0.1 × 336 = 33.6 units of increase in the value of steam output per hour, which is £336.
Because this is larger
than the hourly capital cost £300, it is worth it to install the extra capacity
DEF 4.1 Optimality range
Consider changing the cost coefficient (c_j) of a decision variable (x_j).
The optimality range for c_j
is the set of values for c_j
in which the optimal basis remains optimal.
The optimality range is given by the condition r ≥ 0, i.e., rj ≥ 0 for all j.
e.g., changing the price of a product.
*If the basis is not changed, changing cj will change only the reduced costs in the final optimal tableau. By optimality condition, if one of the reduced costs becomes negative (for maximisation problems), then the tableau
is no longer optimal, and the basis will have to be changed
*Note that, since the basis remains unchanged, the reduced costs for the basic variables would remain zero.
] Therefore we need only check the reduced costs of the non-basic variables.
reduced cost for jth variable= cost coefficient vector of basic variables in the final tableau * B-1 * jth column vector in A ie from initial - cost coefficient of j
Optimality range:
For the electric power generation example, what is the range of values of c2
for which the optimal basis remains unchanged? c2 is the cost coefficient of x2, which is 20 in the example.
We calculate the new values of the reduced costs for the non-basic vars r_3 and r_5. The basis is still x_2, x_4 and x_6. Thus
c^T_B= [ c1,c4,c1,c6]=[c2,0,24,0]
and c3=c5=0
columns in optimal tablea are B^-1 a_j.
to calculate r_3=c^T_B B^-1 a_3-c_3 use the third column in the optimal tableau
r_3=c_2(3/2)+0+0+24x(-1)-0 ≥0 for no change in the optimal bias
c2 ≥ 16
Similarly,
r5 = c2(−12) + 24(24) − 0 ≥ 0
We find c2 ≤ 48. So 16 ≤ c2 ≤ 48, which is the optimality range for c2
NOTES optimality range
Remark. Suppose we are changing coefficient ck . There are two possibilities. First, xk
is a basic variable. Thus
we are changing cB. Since rj = c^T_B B^−1 aj − cj
so the reduced costs for all non-basic variables would be changed.
Second, xk
is non-basic. Then cB remains the same, so is the 1st term in rj
for all j. Therefore, only rk
is changed.
DEF 4.2
Feasibility range
Consider changing the resource b_j. T he range for bj in which the optimal basis remains optimal and the solution remains feasible is called the feasibility range of the resource bj (or the corresponding constraint).
*Since the basis is the same, so are the reduced costs, the basic matrix B, and the non-basic variables. But the
values of the optimal solutions xˆ_B = B^−1
b would be changed. For the solutions to remain feasible, we need
B^−1 b ≥ 0, which is the condition we use to find the feasibility range.
**The feasibility range is given by the condition B^−1 b ≥ 0.
basis| x1 x2 … xn| Solution
z |rj = cT_B B−1aj − cj| zB = cT_B xˆ_B
xB| B−1A̅ | xˆB = B−1b
Example: Electric power generation, Reading information from the tableaux
Feasibility range
Let b_1 = 12 + δ, so the perturbed resource vector is
b~ = [12 + δ, 20, 1, 0]T
We need to find B−1 b~
We have
B−1b~ =
B−1 [12, 20, 1, 0]^T + B−1[δ, 0, 0, 0]^T
The first term on the right hand side is the optimal solution in the final tableau. B−1
is given by the four
columns in the final tableau corresponding to the identity matrix in the first tableau. We want the above equation to be non-negative. Thus
[6]
[2]
[12]
[9600]
+
[ 3/2 0 −12 0] [ −1/2 1 −12 0] [ −1 0 24 0] [−2400 0 38400 −1] * [δ] [0] [0] [0] ≥ 0 ⇒
[6 + (3/2)δ] [2 − (1/2)δ] [12 − δ ] [9600 − 2400δ] ≥ 0 We find δ ≥ −4, δ ≤ 4, δ ≤ 4, δ ≤ 12.
So −4 ≤ δ ≤ 4 and the feasibility range for
b1 is 8 ≤ b1 ≤ 16.
If we do not split b1 into b1 = 12 + δ, the calculation would go as follows: B^−1 * [b_1] [20] [1] [0] = [3b_1 /2 − 12] [8 − b_1 /2] [24 − b_1] [38400 − 2400b_1] ≥ 0
from which we find b1 ≥ 8, b1 ≤ 16, b1 ≤ 24 and b1 ≤ 16. Same conclusion follows.
HOW TO ANSWER:
Example 4.7. In the above power generation problem, suppose that a newly available coal (very hard, and low
in pollutants) is contemplated. It has a smoke emission rate of 1/3 kg/ton. The pulverizer can handle 12 tons
of it per hour. The new coal has a sulphur content of 1500 PPM. Like all other coals it uses loader capacity.
Each ton of the coal can produce £350 worth of steam output. Should it be used?
*could introduce var x_7 = amount of new type to be used per hour and include in the formulation. if it should be positibe in optimal then should use coal o/w no
Adding a new decision variable
would x7 be a basic variable in the optimal solution?’ If it is basic, then it would be positive,
otherwise it is zero
If we look at the tableau, the new decision variable would add a new column to the tableau.
*we don’t need to use initial
However, the
optimal solution changes only if the new variable becomes a basic variable. Otherwise, the value for the new
variable would be zero, hence has no effect on the solution. In general, let say xk
is the new decision variable
to be introduced. To know if xk should be a basic variable or not, we need to find the reduced cost rk
for xk. If rk < 0 (in a maximisation problem), then xk should become a new basic variable; the optimal solution need to
be changed. If, on the other hand, rk > 0, then nothing is changed.
SOLUTION:
Example 4.7. In the above power generation problem, suppose that a newly available coal (very hard, and low
in pollutants) is contemplated. It has a smoke emission rate of 1/3 kg/ton. The pulverizer can handle 12 tons
of it per hour. The new coal has a sulphur content of 1500 PPM. Like all other coals it uses loader capacity.
Each ton of the coal can produce £350 worth of steam output. Should it be used?
Let x7 be the amount of the new type of coal used per hour. The cost coefficient for the coal is c7 = 35
(unit: 10£). The coefficients for the coal in the four constraints are, respectively, 1/3, 1, 1/12, and −1500 (to see
how to obtain these numbers, see the remarks on the derivation of the constraints given above).
Using the formula r_k =
c^T_B B^−1 a_k − c_k
we find
r7 = −5.
So the new coal should be used.
Note cB and B^−1 have been found in previous examples.
Another method is to use the remark following Proposition 3.1 where it was noted that the c^T_B B^−1
is the same as
the reduced costs for the slack variables, which can be found from the optimal tableau:
c^T_B B^−1 = (6, 0, 336, 0).
Thus r7 = 2 + 28 − 35 = −5.
Remark. The solution for the above example calculated only r7 which is enough to answer the question in the
example. The other coefficients for the x_7 column in the optimal tableau can be calculated using B^−1a_7. If we
need to find the new optimal solution, we would then need to calculate B^−1 a_7, and then start from the optimal tableau, and apply a further step of simplex iteration with x7 as the enter variable.
HOW TO ANSWER:
Example 4.8. Given the prospect of policy changes in response to global warming, the management of the
power plant wants to investigate the effects of a carbon emission cap on the operation of the plant. Due to the differences in purity and combustion efficiency, the two types of coal produce different amounts of CO2: 2.5
tons are produced from burning 1 tone of A, whilst 3 tons are produced from 1 ton of B. Investigate how the solution changes if CO2 emission is capped at 40 ton per hour.
Adding an additional constraint
does the original optimal solution still satisfy the
additional constraint?
If Yes: then the slack for the new constraint is > 0. No practical effects. Optimal sol cost same and new slack becomes basic var.
If No: solution to the new slack variable is < 0 ⇒ solution infeasible. We then
use dual simplex method to recover feasibility and find new optimal sol
*for new constraint add new slack var. #basic vars=#constraints s adding new constraint +1 to basic vars. so optimal basis will be changed, however optimal cost may still remain same if constraint satisfied
SOLUTION Example 4.8. Given the prospect of policy changes in response to global warming, the management of the power plant wants to investigate the effects of a carbon emission cap on the operation of the plant. Due to the differences in purity and combustion efficiency, the two types of coal produce different amounts of CO2: 2.5
tons are produced from burning 1 tone of A, whilst 3 tons are produced from 1 ton of B. Investigate how the
solution changes if CO2 emission is capped at 40 ton per hour.
check if optimal satisfies new constraint:
2.5x1 + 3x2 ≤ 40
Let x_7 be slack var, adding row and col to final optimal tableau (x_7 added as a basic var as we want to find its value and check feasibility)
x1| x2| x3| x4| x5| x6|x7|Solution z| 0 0 6 0 336 0 0 408 x2| 0 1 3/2 0 −12 0 0 6 x4| 0 0 −1/2 1 −12 0 0 2 x1| 1 0 −1 0 24 0 0 12 x6| 0 0 −2400 0 38400 1 0 9600 x7| 2.5 3 0 0 0 0 1 40
We would have obtained this tableau if we had added constraint to initial if we had ignored x_7 row during simplex calculations
Therefore, there is no need to change the other rows when we add the x7 row (apart adding a new column, which is zero except in the new
row).
The new tableau is NOT consistent, in that the columns for the basic variables are not unit vectors.
As a result,
the numbers in the solution column are not necessarily the actual solutions for the basic variables and/or the cost function. To recover consistency, we need to reduce the coefficients in the x7-row to zero in the columns
of current basic variables. We use row-operations (Gaussian-Jordan elimination):
(−2.5) × (x1-row) + (−3) × (x2-row) + x7-row
→
new x7-row
The new tableau is
x1 x2 x3 x4 x5 x6 x7 Solution z 0 0 6 0 336 0 0 408 x2 0 1 3/2 0 −12 0 0 6 x4 0 0 −1/2 1 −12 0 0 2 x1 1 0 −1 0 24 0 0 12 x6 0 0 −2400 0 38400 1 0 9600 x7 0 0 −2 0 −24 0 1 −8
consistent but sol is no longer feasible,
Dual simplex method used to retain feasability: x_7 leaves, ratios for non-basic x_3 and x_5 are -3 and -14 (for the dual simplex
method, the ratio is defined as the reduced cost over the coefficient in the pivot row, if the coefficient is negative)
hence x_3 enters, updating by row operations:
x1 x2 x3 x4 x5 x6 x7 Solution z 0 0 0 0 264 0 3 384 x2 0 1 0 0 −30 0 3/4 0 x4 0 0 0 1 −6 0 -1/4 4 x1 1 0 0 0 36 0 -1/2 16 x6 0 0 0 0 67200 1 -1200 19200 x3 0 0 1 0 12 0 −1/2 4
which is now feasible and optimal. You may find the optimal solutions from the tableau.
