Linear optimization: Sensibility analysis 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→NBV-analysis) |
K |
||
(17 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
− | |||
− | |||
== Theory == | == Theory == | ||
=== Terminology === | === Terminology === | ||
Zeile 49: | Zeile 47: | ||
==== Simplex tableaus ==== | ==== Simplex tableaus ==== | ||
− | |||
[[Datei:Gardening_LP_tableaus.jpg]] | [[Datei:Gardening_LP_tableaus.jpg]] | ||
Zeile 55: | Zeile 52: | ||
==== NBV-analysis ==== | ==== NBV-analysis ==== | ||
In Order to analyze the non basic variables we have to pick (in the final tableau) | In Order to analyze the non basic variables we have to pick (in the final tableau) | ||
− | |||
'''For variable <math> y_1 </math>''' | '''For variable <math> y_1 </math>''' | ||
Zeile 69: | Zeile 65: | ||
<br /> | <br /> | ||
<math> y_\text{1,max} = 60 + \min \left \{ \left | \frac {30}{-\frac{3}{2}} \right |\ \right \} = 60+20 = 80 </math> <br /> | <math> y_\text{1,max} = 60 + \min \left \{ \left | \frac {30}{-\frac{3}{2}} \right |\ \right \} = 60+20 = 80 </math> <br /> | ||
− | |||
− | |||
− | |||
<br /> | <br /> | ||
Zeile 88: | Zeile 81: | ||
<br /> | <br /> | ||
− | |||
==== BV-analysis ==== | ==== BV-analysis ==== | ||
Zeile 98: | Zeile 90: | ||
* the absolute smallest negative ratio of '''OF-coefficient''' and '''the corresponding row-element''' | * the absolute smallest negative ratio of '''OF-coefficient''' and '''the corresponding row-element''' | ||
− | <math> x_\text{1,min} = -1 - \min \left \{ \left | \frac{ | + | <math> x_\text{1,min} = -1 - \min \left \{ \left | \frac{\frac{1}{2}}{-\frac{3}{2}} \right |\ \right \} = -1-\frac{1}{3} = - \frac {4}{3} </math> <br /> |
* the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | * the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | ||
Zeile 112: | Zeile 104: | ||
* the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | * the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | ||
− | <math> x_\text{2,max} = -2 + \min \left \{ \left | \frac{ | + | <math> x_\text{2,max} = -2 + \min \left \{ \left | \frac{\frac{1}{2}}{1} \right |\ \right \} = -2 +\frac{1}{2} = - \frac{3}{2} </math> <br /> |
<!-- '''for variable y_2''' | <!-- '''for variable y_2''' | ||
Zeile 122: | Zeile 114: | ||
* the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | * the absolute smallest positive ratio of '''OF-coefficient''' and '''the corresponding row-element''' | ||
− | <math> y_\text{2,max} = -2 + \min \left \{ \left | \frac{ | + | <math> y_\text{2,max} = -2 + \min \left \{ \left | \frac{\frac{1}{2}}{1} \right |\ \right \} = -2 +\frac{1}{2} = - \frac{3}{2} </math> <br /> |
--> | --> | ||
− | == | + | == Counterexample == |
− | To demonstrate, the funcionality of the sensibility analysis above and that it is correct we vary one of the | + | To demonstrate, the funcionality of the sensibility analysis above and that it is correct we vary one of the problem's constraints. <br/> |
For this example we modify <math> y_3 </math> to 781 instead of 720. | For this example we modify <math> y_3 </math> to 781 instead of 720. | ||
[[Datei:Simplex_y3(781)_all_Iterations.png]] | [[Datei:Simplex_y3(781)_all_Iterations.png]] | ||
− | Now it is obvious that the | + | Now it is obvious that the basic variables in the optimal solution have changed. Thus it is clear what is meant by structural changes of the optimal solution. |
− | In this simple example the bottlenecks are now <math> y_2 </math> and <math> y_1 </math> and not <math> y_3 </math> and <math> y_1 </math> like in the first example. | + | In this simple example the bottlenecks are now <math> y_2 </math> and <math> y_1 </math> and not <math> y_3 </math> and <math> y_1 </math> like in the first example. <br/> |
+ | The upper bound for this constraint is 780. When we choose 780 we can choose two possible pivot elements, thus it is not sure that the structure of the optimal solution will change. | ||
− | == | + | == Interpretation of the sensibility analysis == |
+ | |||
+ | By the found intervals above, you can see the following: | ||
+ | <br/> | ||
+ | |||
+ | From the interval <math> \textstyle \left [ 40 ; 80 \right ] </math> for variable <math> y_1 </math>, you can see, in which the plantable Area of carrots may vary, without having an influence on the structure of the optimal solution. | ||
+ | |||
+ | <br/> | ||
+ | |||
+ | For the variable <math> y_3 </math> the Interval <math> \textstyle \left [ 540 ; 780 \right ] </math> in which the budget may vary, without having an effect on the structure of the optimal solution. | ||
+ | |||
+ | <br /> | ||
+ | |||
+ | |||
+ | For the variable <math> x_1 </math> an Interval from <math> \textstyle \left [ 0 ; \frac{4}{3} \right ] </math> in which the Cost contribution of roses may vary, without having an effect on the structure of the optimal solution. | ||
+ | |||
+ | <br /> | ||
+ | |||
+ | For the variable <math> x_2 </math> an Interval from <math> \textstyle \left [ \frac{3}{2} ; \infty \right ] </math> in which the Cost contribution of carrots may vary, without having an effect on the structure of the optimal solution. | ||
==Sources== | ==Sources== | ||
+ | |||
+ | OR lecturescript, OR-Course on Olat | ||
+ | |||
+ | Detailed example: Own Notes of last Year's Tutorial of Produktionswirtschaft | ||
+ | |||
+ | Authors: | ||
+ | Arno Hornberg | ||
+ | Philipp Stedem |
Aktuelle Version vom 7. Juli 2013, 22:38 Uhr
Inhaltsverzeichnis
Theory
Terminology
The german term "Sensibilitätsanalyse" was derived from the original english term "sensitivity analysis" by Müller-Merbach [Operations Research] in 1992. The term sensibility analysis, that is used in this Article, is used synonymous to that.
Use
After finding an optimal solution for a linear optimization problem by the means of the simplex algorithm, one can use the sensibility analysis to see, how much the initial data may be changed, without changing the structure of the optimal solution. In other words you can see, the robustness of your optimal programm regarding the change of the objective function or constraints.
Non basic variable change
In the following section, all relations concerning dimensions of numbers are absolute values
The smallest negative and the smallest positive quotient of the optimal solution's right hand side and the corresponding column element of the optimal solution define, when added or subtracted to the right hand Side of the initial solution, the upper and lower endpoint of the interval in which the constraints may vary.
So, you can see the robustness of the optimal solution, concerning the change of the restrictions.
Basic variable change
The smallest negative and the smallest positive quotient of the optimal solution's Objective function coefficient and the corresponding row element of the optimal solution define, when subtracted or added to the coefficients of the initial objective function, the lower and upper endpoint of the interval in which the coefficients of the objective function may vary.
By the interval of basic variables, you can see the robustness of the optimal solution, concerning the change of the objective function.
Complete detailed Example
Optimization
Text
A garden center has got a bed with a developable area of 100 m².
There is a budget of $720 available to plant roses and carrots in the bed.
However, the maximal planting area of carrots shall not exceed 60m².
The planting shall maximize profit.
The costs for the seed are as following:
- Roses: Carrots:
The selling prices of the products are:
- Roses: Carrots:
Formal LP
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): OF: x _1 + 2x_2 \xrightarrow {} max! \qquad | x_1 ; x_2 \ge 0
1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2+ y_1 \le 60
2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 + x_2 + y_2 \le 100
3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6x_1 + 9x_2 + y_3 \le 720
Simplex tableaus
Sensibility analysis
NBV-analysis
In Order to analyze the non basic variables we have to pick (in the final tableau)
For variable
We have the absolute ratios:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac {30}{-\frac{3}{2}}= -20
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_\text{1,min} = 60 - \min \left \{ \left | \frac{60}{1} \right |; \left |\ \frac{10}{\frac{1}{2}} \right |\ \right \} = 60-20 = 40
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_\text{1,max} = 60 + \min \left \{ \left | \frac {30}{-\frac{3}{2}} \right |\ \right \} = 60+20 = 80
For variable
- the absolute smallest ratio of the right hand side and the coresponding negative collumn element.
Here it is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{10}{- \frac{1}{6}} = 60
- the absolutely smallest ratio of the right hand side and the corresponding positive collumn element.
Here it is
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_\text{3,min} = 720 - \min \left \{ \left | \frac{30}{\frac{1}{6}} \right |\ \right \} = 720-180 = 540
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_\text{3,max} = 720 + \min \left \{ \left | \frac {10}{-\frac{1}{6}} \right |\ \right \} = 720+60 = 780
BV-analysis
In Order to analyze the basic variables we have to pick (in the final tableau)
for variable
- the absolute smallest negative ratio of OF-coefficient and the corresponding row-element
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_\text{1,min} = -1 - \min \left \{ \left | \frac{\frac{1}{2}}{-\frac{3}{2}} \right |\ \right \} = -1-\frac{1}{3} = - \frac {4}{3}
- the absolute smallest positive ratio of OF-coefficient and the corresponding row-element
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_\text{1,max} = -1 + \min \left \{ \left | \frac{ \frac{1}{6} }{ \frac{1}{6} } \right |\ \right \} = -1 +1 = 0
for variable
- the absolute smallest negative ratio of OF-coefficient and the corresponding row-element
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_\text{2,min} = -2 - \min \left \{ \left | \frac{ \frac{1}{6}} { 0 } \right |\ \right \} = -2 -\infty = -\infty
- the absolute smallest positive ratio of OF-coefficient and the corresponding row-element
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_\text{2,max} = -2 + \min \left \{ \left | \frac{\frac{1}{2}}{1} \right |\ \right \} = -2 +\frac{1}{2} = - \frac{3}{2}
Counterexample
To demonstrate, the funcionality of the sensibility analysis above and that it is correct we vary one of the problem's constraints.
For this example we modify to 781 instead of 720.
Now it is obvious that the basic variables in the optimal solution have changed. Thus it is clear what is meant by structural changes of the optimal solution.
In this simple example the bottlenecks are now and and not and like in the first example.
The upper bound for this constraint is 780. When we choose 780 we can choose two possible pivot elements, thus it is not sure that the structure of the optimal solution will change.
Interpretation of the sensibility analysis
By the found intervals above, you can see the following:
From the interval for variable , you can see, in which the plantable Area of carrots may vary, without having an influence on the structure of the optimal solution.
For the variable the Interval in which the budget may vary, without having an effect on the structure of the optimal solution.
For the variable an Interval from in which the Cost contribution of roses may vary, without having an effect on the structure of the optimal solution.
For the variable an Interval from Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \textstyle \left [ \frac{3}{2} ; \infty \right ]
in which the Cost contribution of carrots may vary, without having an effect on the structure of the optimal solution.
Sources
OR lecturescript, OR-Course on Olat
Detailed example: Own Notes of last Year's Tutorial of Produktionswirtschaft
Authors: Arno Hornberg Philipp Stedem