Linear optimization: Parametrical objective function 2

Theory

Parametrical objective functions is an extension of linear optimization. It handles problems where the coefficient of the objective function and / or the right sides of constraints can not be assumed to be constant, but rather may vary depending on different parameters.

Generally the parametrical objective function is searching for an optimal solution of a linear problem independent from the parameters actual value. Commonly optimization problems like parametrical problems origin from instability in decisions especially concerning given data. One way to solve such a problem is through a modified Simplex-Method which will be presented below.

Example and solution of the Problem

The origin of parametrical optimization is the sensitivity analysis. Compared to the sensitivity analysis the parametrical objective function makes a statement about large changes in the input data.

We are assuming that a company wants to maximize their profit. Therefor the companies controller put up a profit equation which needs to be maximized.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): G = qx_1 + 300x_2 - 20000

Our restrictions are:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 + 1x_2 \le 95
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1x_1 + 4x_2 \le 100
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1x_1 + 0x_2 \le 30

---

In order to put up a Simplex-Algorithm we must transfer the objectiv function:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): G - qx_1 - 300x_2 = - 20000

Also we must get rid of the inequations at our restrictions and replace them with slack variables:

$2x_{1}+1x_{2}+Ya=95$
$1x_{1}+4x_{2}+Yb=100$
$1x_{1}+0x_{2}+Yc=30$

Now we can start with our first tableau. First action ist to find the pivot element which indicates us where the capacity is limited the most. It is important to start with the second row because q equals 0 in our first tableau:

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

---

Now we need to work with the pivot element and start the regular simplex. Remember q=0:

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

Because x1 can't get below 0, q is not allowed to hurt the restrictions. Thats why it is not optimal solution. That is why we need to take a 3rd tableau.

---

After finding the pivot element on the x1 side we will transfer now to the last tableau where q is not limited.

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

Now we got the final tableau with the optimal solution. larger than or equal $q$ is a hint that the iteration is over. It is not allowed that the objectiv funktion could turn negative. The only variable in the objective function is q now.

Now we got an optimal solution of the linear problem independent from the parameters actual value.

Source

| Sensitivitätsanalyse und Parametrische Optimierung (English)

Parametrische_Optimierung, Parameter_q_als_Zielfunktionskoeffizient

Han, Kamber, Pei: Data Mining. Concepts and Techniques. Elsevier Inc 2012. ISBN 978-0-12-381479-1