Linear optimization: Sensibility analysis 5
Theory: The sensibility analysis is a post optimal calculation for linear programming problems. It describes the determination of sensibility, respectively the stability of the optimal solution in terms of modification of the initial data. We consider the changing of factors and modification should not have any effect on the essential properties of the solution. We modify only one factor by keeping the other factors constant (ceteris paribus). Relevant for the sensibility analysis are the initial solution and the final optimal solution. By changing the data of the initial solution at least one optimal tableau coefficient change. Important is the change of single data until the optimal solution isn´t optimal and feasible anymore which is given by negative elements on the right side (RS) or object function. A qualitative change is given if a basis-variable changes into a non-basic-variable and vice versa.
Mostly we analyze the changing of the objective function coefficients and the primal values.
Changes in the coefficients of a Non-Basic Variable:
First we examine the changes of the capacity of facility A. If the capacity is lower than 170 h, yA get a forced increase. The increase of yA (yA = 20/1 = 20) causes a decrease of x2 (x2 = 0). So the capacity decrease of 170 h to 150 h results x2 = 0. Before we could further decrease the capacity, x2 have to leave the base.
YA, min = 170 – min {|20/1|} = 170 – 20 = 150
An increase of capacity is therefore equivalent to negative growth of yA. In this context x1 and yC are reduced. With yA = -40 results yC = 0. This means an increase of capacity of 170 h to 210 h and facility C becomes a bottleneck facility. Before we could further increase of facility A, yA have to leave the base.
YA, max = 170 + min {|130/-1|, |120/-3|} = 170 + 40 = 210
With the sensibility analysis you can calculate possible shifting of individual restrictions between adjacent vertexes of the optimum. With the changing of capacity the optimum move between these vertexes. Formally you can say: The absolutely negative and the smallest positive ratio of right side and corresponding column element of the optimal solution offer the margin of fluctuation by the primal value in the initial solution.
For facility B you get the constraints yB = 40 (yC = 0) and yB = -20 (x2 = 0). Therefore yB = 40 results a new capacity of 110 h and for yB = 20 a capacity of 170 h.
YB, min = 150 – min {|130/2|, |120/3|} = 150 – 40 = 110
YB, max = 150 + min {|20/-1|} = 150 + 20 = 170
Changes in the coefficients of a Basic Variable
Suppose that the variable x j under consideration is a basic variable in the optimal solution s by the final simplex tableau. Now we assume that the only changes are made to the coefficients of this variable. A Changing like this can interpreted as a rotation of the profit function.
In our case we want to increase/decrease the variable x1. (with an amount of d) We change the original profit function G + 200yA + 100yB) = 13000 into G + dx1 + 200yA = 13000 But x1 is a basic variable. Thus, means that x1 mustn’t be in the profit function. The dual value of x1 is zero. So the restriction x1 – yA + 2yB = 130 must be deducted of the profit function which leads to
G + (200 +d)yA + (100 – 2d)yB = 13000 – 130d
Now the value of d is like the quotient of the coefficients of the profit function and the coefficients of the current row (in our case x1).
Target: Looking for the smallest negative (in absolute terms) and smallest positive value of d, which lead to a negative coefficient of the profit function.
This value gives the spread of variation without changing the structure of the optimal solution. (graphically: Where the vertex doesn´t change.)
Formally you can say: The absolutely smallest negative and the smallest positive ratio of objective function coefficient and according element of the row of the optimal solution offer the margin of fluctuation by the dual value in the initial solution.
In our case we get:
X 1,min = -300 - min {|200/-1|} = -300- 200 = -500
X 1,max= -300 + min {|100/2|} = -300 +50 = -250
X 2, min = -500- min {|100/-1|} = -500- 100 = -600
X 2, max = -500 + min {|200/1|} = -500 + 200 = -300
Y c, min = 0 - min {|200/-3|} = 0 66,7 = -66, 7
Y c, max = 0 + min {|100/3|} = 0 + 33, 3 = 33,3
