Linear optimization: Sensibility analysis 1: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 00:40 Uhr

Besetzt H&S

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: ${\displaystyle 6{\frac {\$}{m^{2}}}}$      Carrots: ${\displaystyle 9{\frac {\$}{m^{2}}}}$
  

The selling prices of the products are:

• Roses: ${\displaystyle 7{\frac {\$}{m^{2}}}}$      Carrots: ${\displaystyle 11{\frac {\$}{m^{2}}}}$
  

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

Initial Tableau

Sensibility analysis

NBV-analysis

In Order to analyze the non basic variables we have to pick (in the final tableau)

For variable ${\displaystyle y_{3}}$

• 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 ${\displaystyle {\frac {30}{6}}=5}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_\text{3,min} = 720 - \min \left \{ \left | \frac{30}{6} \right |\ \right \} = 720-5 = 715

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

So we get an Interval from 715 to 780, in which the budget may vary, without having an effect on the structure of the optimal solution.

For variable ${\displaystyle y_{1}}$

We have the absolute ratios:

• ${\displaystyle {\frac {60}{1}}=60}$
• ${\displaystyle {\frac {10}{0,5}}=20}$
• Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac {30}{-1,5}= -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}{0,5} \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}{-1,5} \right |\ \right \} = 60+20 = 80

BV-analysis

In Order to analyze the basic variables we have to pick (in the final tableau)

for variable ${\displaystyle x_{1}}$

• 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{0,5}{-1,5} \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 ${\displaystyle x_{2}}$

• 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{0,5}{1} \right |\ \right \} = -2 +0,5 = - 1,5

Presentation of the Problem

Detailed solution Process with explanation

Sources