Linear optimization: Sensibility analysis 3
Inhaltsverzeichnis
Theory
The sensitivity analysis is concerned with the effects and changes in the output data to the optimal solution. You can also ask this question a little differently: to what extent can size change without affecting the essential properties of the solution?
Finding the optimal solution to a linear programming model is important, but one can derive the Sensitivity Analysis important additional information from the linear model (but there are much more information that can be read from an analysis). There is a tremendous amount of sensitivity information, or information about what happens when data values are changed.
Other analysises you could only use under the condition that a constancy of the output data is given. However, such a stability of the output data does not exist in reality. That is a problem because you usually cannot modify any data simultaneously, only one size while keeping all other constant ("ceteris paribus") is changed and asked: In what area can the size in question vary, without this, the solution loses its validity?
By "valid" here are the qualitative characteristics of a solution and not understood quantitatively. A solution is qualitatively different (structural) only by another if at least one pivot operation is needed to establish admissibility and / or optimality again if it was lost in the change.
Non basis variables
The absolutely smallest negative and the smallest positive ratio from right side and the according column element of the optimal solution offer the margin of fluctutation by the primal value in the initial solution.
Basis variables
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.
Example
For the whole example we will stick with the following problem.
The initial tableau:
To get from the initial solution to the optimal one should be already clear and is not part of this wiki-entry.
The optimal tableau:
Detailed solution process with explanation
Non basic variables
At the beginning, we determine the non-basic variables of the optimal solution. In our example, it is the y_B and the y_A. For the first step we look at the value corresponding to y_B at the right side of the initial tableau, which is 150 in this case. To decide the lower limit of the range of variation, we subtract from the value of the right side of the initial tableau, 150, the minimum of the sum of the positive quotient of the value of the right side and the associated column value of the non-base variable of the optimal solution --> min (130/2; 120/3) = min (65; 40) = 40. So y_B, min = 150 - min (65; 40) = 150 - 40 = 110. For the upper limit of the range of variation we add to the value of the initial tableau of the right side, which is 150, the minimum of the sum of the negative quotient of the right side with the corresponding column value of the non-basic variables from the optimal tableau --> min (|20/-1|) = 20. So the upper limit for y_B is max = 150 + min (|20/-1|) = 150 + 20 = 170. The range for the variable y_B is 110 ≤ y_B ≤ 170.
If you do the same iterations for the second non-basic variables y_A, you will get the following solutions.
The lower limit is 170 - min (20/1) = 150 and the upper limit is 170 + min (|130/-1|; |120/-3|) = 170 + 40 = 210.
So the range for the variable y_A is 150 ≤ y_A ≤ 210.
Basis variables
At the beginning, we determine the basic variable of the optimal solution. In our example, it is x_1 and x_2. For the first step we look at the value corresponding to x_1 of the objective function coefficients of the initial solution, which is -300. To determine the lower limit of the range of variation, we subtract from the value of the objective function coefficient of the initial solution, which is -300, the minimum of the sum of the negative quotient of the value of the objective function coefficient and the associated row value of the base variable of the optimal solution --> min (|200/-1|) =200. For the upper limit of the range of variation we add to the value of the initial tableau of the objective function coefficients, which is -300, the minimum of the sum of the positive quotient of the objective function coefficients with the corresponding row value of the basic variables from the optimal tableau --> min (100/2). The upper limit for x_1 is -300 + min (100/2) = -250. The range for the variable x_1 is -500 ≤ x_1 ≤ -250.
If you do the same iterations for the second basic variables x_2, you will get the following solutions.
The lower limit is -500 - min (|100/-1|) = -600 and the upper limit is -500 + min (200/1) = -300.
So the range for the varibale x_2 is -600 ≤ x_2 ≤ -300.
Sources
1. Script Operation Research SS 2013 Prof. Dr. Oliver Wendt
