Linear optimization: Sensibility analysis 4: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(Die Seite wurde neu angelegt: „==Introduction== The '''sensibility analysis''' (also sensitivity analysis) determines to what extend initial data can be changed, without changing the struct…“)
 
(→‎Optimal Solution)
 
(14 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
−
==Introduction==
+
==Theory==
  
−
The '''sensibility analysis''' (also sensitivity analysis) determines to what extend initial data can be changed, without changing the structure and characteristics (optimality, validity) of the final solution. The modification can be caused by variation of basis and non-basis variables. Because not all variables (data) can be changed at the same time, the modification has to be “ceteris paribus” (one variable changes, all other variables stay constant).  
+
The '''Sensibility Analysis''' (also: Sensitivity Analysis) can be seen as a „What if – Analysis“. The question we have in mind while doing the analysis is: „What happens to the outcome, if we change this variable?“ You have to consider that initial data has to be changed without changing the structure and characteristics (optimality, validity) of the final solution. Doing a Sensitivity Analaysis will predict you the outcome resulting from a certain change in the variables (basis or non basis?). It’s important, that this change of variables happens ceteris paribus. That means, that only one of the variables changes, while all others have to stay constant. The result of the sensibility analysis will be the range in which these variables can be changed, so that we don’t have to do further iterations to get to the optimal solution.
−
The result of the sensibility analysis will be the range in which these variables can be changed, so that we don’t have to do further iterations to get to the optimal solution.
+
  
 +
In reality it applies as a popular decision support. Analysts can do several Sensitivity Analyses and get an overview which alternative of changing variables will lead to which outcome. Based on that they are able to decide what change will bring the intended  result along.
  
−
== Change of basic variables ==
 
  
 +
 +
== Example ==
 +
We assume, that we have a company which sells two sorts of fruit-boxes (apples and pineapples). All fruits have to pass three processes. First they get washed. In the second step the fruits get cut and in the last step they get packed into boxes. The prices for apples are 5$ and for pineapples 8$.
 +
 +
Capacities of the processes and time the models need:
 +
{| class="wikitable"
 +
! Process
 +
! Apples
 +
! Pineapples
 +
! Capacity (max)
 +
|-
 +
| Washing
 +
| 1
 +
| 4
 +
| 90
 +
|-
 +
| Cutting
 +
| 2
 +
| 5
 +
| 160
 +
|-
 +
| Packing
 +
| 1
 +
| 2
 +
| 75
 +
|}
 +
 +
 +
*objecitve function: <math>5x_1 + 8x_2 \rightarrow max</math>
 +
 +
 +
 +
=== Initial Solution ===
 +
{| class="wikitable"
 +
!
 +
! <math>x_1</math> (non-basic)
 +
! <math>x_2</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| -5
 +
| -8
 +
|
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| 3
 +
| 90
 +
|-
 +
| <math>y_B</math>
 +
| 2
 +
| 5
 +
| 160
 +
|-
 +
| <math>y_C</math>
 +
| 1
 +
| 2
 +
| 75
 +
|}
 +
 +
=== Optimal Solution ===
 +
 +
{| class="wikitable"
 +
!
 +
! <math>x_2</math> (non-basic)
 +
! <math>y_C</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| 2
 +
| 5
 +
| 375
 +
|-
 +
| <math>y_B</math>
 +
| 1
 +
| -2
 +
| 10
 +
|-
 +
| <math>x_1</math>
 +
| 2
 +
| 1
 +
| 75
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| -1
 +
| 15
 +
|}
 +
 +
 +
== Detailed Solution Process ==
 +
=== Change of basic variables ===
 
Basic Variables
 variation interval for dual value in the initial solution is defined by the smallest negative and the smallest positive ratio of objective function (here: optimal solution) and the corresponding row element.
 
Basic Variables
 variation interval for dual value in the initial solution is defined by the smallest negative and the smallest positive ratio of objective function (here: optimal solution) and the corresponding row element.
  
 +
The '''positive value''' has to be '''added''' to the initial value and the '''negative value''' has to be '''subtracted''' from the initial value.
  
−
*[[Datei:05_81NBV.jpg]]
+
==== Initial Solution ====
−
**Pay attention, that the '''positive value''' has to be '''subtracted''' from the initial value. At the same time the '''negative value''' has to be '''added''' to the initial value.
+
{| class="wikitable"
 +
!
 +
! <math>x_1</math> (non-basic)
 +
! <math>x_2</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| -5
 +
| -8
 +
|
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| 3
 +
| 90
 +
|-
 +
| <math>y_B</math>
 +
| 2
 +
| 5
 +
| 160
 +
|-
 +
| <math>y_C</math>
 +
| 1
 +
| 2
 +
| 75
 +
|}
  
−
*[[Datei:05_82NBV.jpg]]
+
==== Optimal Solution ====
−
**Interpretation: In this example (Ya) the machine capacity could decrease to 150 or increase to 210, without changing the structure. The end tableau of the optimal solution will still be the same.
+
  
−
== Change of non-basic variables ==
+
{| class="wikitable"
 +
!
 +
! <math>x_2</math> (non-basic)
 +
! <math>y_C</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| 2
 +
| 5
 +
| 375
 +
|-
 +
| <math>y_B</math>
 +
| 1
 +
| -2
 +
| 10
 +
|-
 +
| <math>x_1</math>
 +
| 2
 +
| 1
 +
| 75
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| -1
 +
| 15
 +
|}
 +
 
 +
*<math>y_{B,min} = 0 - min\{|5/-2|\} = -2,5</math>
 +
*<math>y_{B,max} = 0 + min\{|2/1|\} = 2</math>
 +
 
 +
 
 +
*<math>x_{1,min} = -5 - min\{|5/1|\} = -10</math>
 +
*<math>x_{1,max} = -5 + min\{|2/2|\} = -4</math>
 +
 
 +
 
 +
*<math>y_{A,min} = 0 - min\{|5/-1|\} = -5</math>
 +
*<math>y_{A,max} = 0 + min\{|2/1|\} = 2</math>
 +
 
 +
 
 +
 
 +
*<math>y_B</math> can be varied from -2,5 to 2
 +
*<math>y_A</math> can be varied from -10 to -4
 +
*<math>x_1</math> can be varied from -5 to 2
 +
 
 +
=== Change of non-basic variables ===
  
 
The interval where the initial solution can be varied is defined by the smallest negative and smallest positive ratio of the RS (here: optimal solution) and the corresponding column element.
 
The interval where the initial solution can be varied is defined by the smallest negative and smallest positive ratio of the RS (here: optimal solution) and the corresponding column element.
  
−
*[[Datei:05_83BV.jpg]]
+
Pay attention, that the '''positive value''' has to be '''subtracted''' from the initial value, while the '''negative value''' has to be '''added''' to the initial value.
 +
 
 +
==== Initial Solution ====
 +
{| class="wikitable"
 +
!
 +
! <math>x_1</math> (non-basic)
 +
! <math>x_2</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| -5
 +
| -8
 +
|
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| 3
 +
| 90
 +
|-
 +
| <math>y_B</math>
 +
| 2
 +
| 5
 +
| 160
 +
|-
 +
| <math>y_C</math>
 +
| 1
 +
| 2
 +
| 75
 +
|}
 +
 
 +
==== Optimal Solution ====
 +
 
 +
{| class="wikitable"
 +
!
 +
! <math>x_2</math> (non-basic)
 +
! <math>y_C</math> (non-basic)
 +
! RS
 +
|-
 +
| o.f.
 +
| 2
 +
| 5
 +
| 375
 +
|-
 +
| <math>y_B</math>
 +
| 1
 +
| -2
 +
| 10
 +
|-
 +
| <math>x_1</math>
 +
| 2
 +
| 1
 +
| 75
 +
|-
 +
| <math>y_A</math>
 +
| 1
 +
| -1
 +
| 15
 +
|}
 +
 
 +
*<math>x_{2,min} = -8 - min\{|10/1, 75/2, 15/1|\} = -18</math>
 +
*<math>x_{2,max} = -8 + min\{|0|\} = -8</math>
 +
 
 +
 
 +
*<math>y_{B,min} = 160 - min\{|75/1|\} = 85</math>
 +
*<math>y_{B,max} = 160 + min\{|10/-2, 15/-1|\} = 165</math>
 +
 
 +
 
 +
 
 +
 
 +
*<math>x_2</math> can be varied from -18 to -8
 +
*<math>y_B</math> can be varied from 85 to 165
  
−
*[[Datei:05_84BV.jpg]]
 
  
  
 +
*Interpretation: In this example (<math>y_B</math>) the machine capacity (i.e.) could decrease to 85 or increase to 165, without changing the structure. The end tableau of the optimal solution will still be the same.
 +
*'''Remember''', that just one variable can be varied (ceteris paribus). The other variable(s) stay(s) constant.
  
 
== Sources==
 
== Sources==
−
* W. Domschke, A. Drexl, Einführung in Operations Research, 6th edition, 2005
+
* W. Domschke, A. Drexl, Einführung in Operations Research, 6. Auflage, 2005
 
* Prof. Dr. O. Wendt, lecture script "Operations Research", 2013
 
* Prof. Dr. O. Wendt, lecture script "Operations Research", 2013

Aktuelle Version vom 28. Juli 2013, 22:16 Uhr

Theory

The Sensibility Analysis (also: Sensitivity Analysis) can be seen as a „What if – Analysis“. The question we have in mind while doing the analysis is: „What happens to the outcome, if we change this variable?“ You have to consider that initial data has to be changed without changing the structure and characteristics (optimality, validity) of the final solution. Doing a Sensitivity Analaysis will predict you the outcome resulting from a certain change in the variables (basis or non basis?). It’s important, that this change of variables happens ceteris paribus. That means, that only one of the variables changes, while all others have to stay constant. The result of the sensibility analysis will be the range in which these variables can be changed, so that we don’t have to do further iterations to get to the optimal solution.

In reality it applies as a popular decision support. Analysts can do several Sensitivity Analyses and get an overview which alternative of changing variables will lead to which outcome. Based on that they are able to decide what change will bring the intended result along.


Example

We assume, that we have a company which sells two sorts of fruit-boxes (apples and pineapples). All fruits have to pass three processes. First they get washed. In the second step the fruits get cut and in the last step they get packed into boxes. The prices for apples are 5$ and for pineapples 8$.

Capacities of the processes and time the models need:

Process Apples Pineapples Capacity (max)
Washing 1 4 90
Cutting 2 5 160
Packing 1 2 75


  • objecitve function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5x_1 + 8x_2 \rightarrow max



Initial Solution

(non-basic) (non-basic) RS
o.f. -5 -8
1 3 90
2 5 160
1 2 75

Optimal Solution

(non-basic) (non-basic) RS
o.f. 2 5 375
1 -2 10
2 1 75
1 -1 15


Detailed Solution Process

Change of basic variables

Basic Variables
 variation interval for dual value in the initial solution is defined by the smallest negative and the smallest positive ratio of objective function (here: optimal solution) and the corresponding row element.

The positive value has to be added to the initial value and the negative value has to be subtracted from the initial value.

Initial Solution

(non-basic) (non-basic) RS
o.f. -5 -8
1 3 90
2 5 160
1 2 75

Optimal Solution

(non-basic) (non-basic) RS
o.f. 2 5 375
1 -2 10
2 1 75
1 -1 15
  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{B,min} = 0 - min\{|5/-2|\} = -2,5


  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1,min} = -5 - min\{|5/1|\} = -10
  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1,max} = -5 + min\{|2/2|\} = -4


  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{A,min} = 0 - min\{|5/-1|\} = -5


  • can be varied from -2,5 to 2
  • can be varied from -10 to -4
  • can be varied from -5 to 2

Change of non-basic variables

The interval where the initial solution can be varied is defined by the smallest negative and smallest positive ratio of the RS (here: optimal solution) and the corresponding column element.

Pay attention, that the positive value has to be subtracted from the initial value, while the negative value has to be added to the initial value.

Initial Solution

(non-basic) (non-basic) RS
o.f. -5 -8
1 3 90
2 5 160
1 2 75

Optimal Solution

(non-basic) (non-basic) RS
o.f. 2 5 375
1 -2 10
2 1 75
1 -1 15
  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2,min} = -8 - min\{|10/1, 75/2, 15/1|\} = -18
  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2,max} = -8 + min\{|0|\} = -8


  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{B,min} = 160 - min\{|75/1|\} = 85
  • Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{B,max} = 160 + min\{|10/-2, 15/-1|\} = 165



  • can be varied from -18 to -8
  • can be varied from 85 to 165


  • Interpretation: In this example () the machine capacity (i.e.) could decrease to 85 or increase to 165, without changing the structure. The end tableau of the optimal solution will still be the same.
  • Remember, that just one variable can be varied (ceteris paribus). The other variable(s) stay(s) constant.

Sources

  • W. Domschke, A. Drexl, Einführung in Operations Research, 6. Auflage, 2005
  • Prof. Dr. O. Wendt, lecture script "Operations Research", 2013
Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Linear_optimization:_Sensibility_analysis_4&oldid=6893“