Linear optimization: Sensibility analysis 2

1 Basic concept

The sensitivity analysis is a method for checking the optimal solution of linear programming models (simplex), where the reactions of the final result to changes of the objective function coefficients are considered. It will examine the range in which the objective function coefficients cj may change without a variable replacement is required. It is important to distinguish whether it is basic variables or non-basic variables.

2 Theory

Based on the inital solution and the optimal solution the non-basic- and basic variables will be examined.

2.1 Non-basic variables

There for the absolutely smallest negative (min-) and smallest positive(min+) ratio of right side and the corresponding columnvalue of the optimal solution will be detected, which indicate the range of variation. To this end, the upper and lower limits of the interval have to be determined. The min+ has to be subtract from the right side of the initial solution to detect the lower limit of the interval.The sum of the min- has to be add to the right side of the initial solution to detect the upper limit of the interval. These arise from the following formulas:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): LB = RS_I - min_+ (RS_O/a_j)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): UB = RS_I + \mid min_- (RS_O/a_j) \mid

2.2 Basic variables

To the absolutely smallest negative and smallest positive ratio of the objective function coefficient and the corresponding row value of the optimal solution is determined, which indicate the range of variation.To this end, the upper and lower limits of the intervalhave to be determined.Thesum of the min- has to be subtract from the objective function coefficient of the initial solution to detect the lower limit of the interval.The min+ has to be addto the objective function coefficient of the initial solution to detect the upper limit of the interval. These arise from the following formulas:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): LB = Z_I - \mid min_-(Z_o/a_j)\mid

$UB=Z_{I}+min_{+}(Z_{o}/a_{j})$ 

3 Notes on the example

To illustrate the procedure, let us consider the following example.In this example, we will waive the presentation of the calculation of the optimum solution, because it should already be clear.

These are the inital- and the optimal solution we are going to work with.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

3.1 Non-basic variables

First, we look at the names of the non-basic variables of the optimal solution. In our example, we have y3 and x2. We start with y3. In the next step we look at the value corresponding to y3in the right side of the starting solution (75). To determine the lower limit of the range of variation, we subtract from the value of the right side of the initial solution (75) 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 75/1). So y3, min = 75-min (75/1) = 75-75 = 0 For the upper limit of the range of variation we add to the value of the initial solution of the right side (75) 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 solution (Min 10/-2; 15/-1). So y3, max = 75 + (min 10/-2; 15/-1) = 75+5 = 80. It follows 0 ≤y3≤80 The same iterations are applied to the second non-basic variables. X2, min= 0 – min 75/2 ; 10/1 ; 15/1 =0-10 =-10 , and x2, max = 0+ min () = 0 . It follows -10 ≤ x2≤ 0

3.2 Basic variables

First, we look at the names of the basic variable of the optimal solution. In our example, we have x1, y1 and y2. We start with x1. In the next step we look at the value corresponding to x1of the objective function coefficients of the initial solution (-5). To determine the lower limit of the range of variation, we subtract from the value of the objective function coefficient of the initial solution(-5) 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 20/1). So x1, min = -5- min () = -5 For the upper limit of the range of variation we add to the value of the initial solution of the objective function coefficients (-5) 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 solution (Min 5/1; 2/2). So x1, max = -5 + (min 5/1; 2/2) = -5+1 = -4. It follows -5 ≤x1≤-4 The same iterations are applied to the other basic variables y1 and y2. It follows -5 ≤ y1≤ 2 and -2,5 ≤ Y2 ≤ 2