Linear optimization: Upper and lower bounds 1

Linear Optimization

Linear Optimization is a mathematical method for improving your outcome by using restrictions.

Normally you add contraints to your Simplex system. The Problem is that you will get a great simplex tableau and to many iteration steps. Therefore we will show a way to consider upper and lower bounds much easier by modifying the standard simplex sheet.

How to integrate lower bounds like Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\geq l_{j} ?

Mathematically you just need to transform the old variable ${x}'_{j}$ into new one $x_{j}$. You consider lower bounds before translating the simplex sheet.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): {\color{Red} {x}'_{j}}= x_{j}-l_{j}

Now the lower bound changes to a non-negative-constraint.

${x}'_{j}>0$

By changing $x_{j}$ to ${x}'_{j}$ we also need to replace the right site of our simplex tableau.

The standard linear projection looks like

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{i}+\sum a_{ij}\cdot x_{j}= b_{i}

Our modification leads us to the following formula.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{i}+\sum a_{ij}\cdot ({x}'_{j}+l_{j})= b_{i}

Now we just change the composition a bit to get our standard structure of the linear projection.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{i}+\sum a_{ij}\cdot {x}'_{j}= b_{i}-\sum a_{ij}\cdot l_{j}

It is important to replace ${x}'_{j}$ back to $x_{j}$ for getting the right results to the processed exercise.

$x_{j}={x}'_{j}+l_{j}$

Graphically you need to shift the coordination system like pictured below.

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

Here you see that the whole coordination system was moved up by the respective lower bound. $x_{1}$ was moved up by $l_{1}$ and $x_{2}$ and by $l_{2}$.

Example:

We also want to solve an example for you as you can see below.

That is the initial situation.

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

We need to produce at least 60 units of product $x_{1}$ and at least 10 units of product $x_{2}$. It is pointed out in an own line. All informations are given.

Our next step is to replace our variables $x_{1}$,$x_{2}$ by ${x_{1}}'$,${x_{2}}'$ by substracting the lower bounds variables $l_{1}$,$l_{2}$. Doing this operation it is necessary to conform our right site.

We will do this by using this formula:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{i}^{neu}= b_{i}-\sum a_{ij}\cdot l_{j}

This operation leads us to sheet two.

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

How to integrate upper bounds like Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\leq u_{j} ?

"Mathematically" you consider upper bounds during translating the simplex sheet. Together with the permissible solution the nnc defines a corridor region which is restricted by two parallel straight lines. Just when the variable $x_{j}$ top the upper bound $u_{j}$ they will be replaced by their "opposing" variable ${\bar {x}}_{j}$. This transformation happens during the solving process of our simplex algorithm dynamically. Moreover we also need to substitute our right site. Here we need to differ between NBV (Non-Basic-Variable) and BV (Basic-Variable).

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

Substitution of NBV

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{i}^{new}=b_{i}-a_{is}u_{s} \forall i

+ coefficients in column s change their sign

Substitution of BV

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{r}=u_{r^{*}}-b_{r}

+ coefficients $a_{rj}$ of row change their sign

While keeping this upper bounds in the pivotation process we have to apply a couple of modification for our simplex algorithm.

Phase 0 and 0`

There are basically no transformations.

Phase 1

Here we need to look at each row, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{i}\leq u_{i}

and in case substitute $y_{i}$ with ${\bar {y}}_{i}$ (before selecting r or s for pivot element)

In Pivot column we need to transform our $x_{s}$ with its oposing ${\bar {x}}_{s}$, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{s}\leq u_{s}

Phase 2

Selection of pivot column s is unchanged.

But the selection of our pivot row becomes a little bit complicated here. We need to do a calculation of three quantities and dicide which of those is the minimum.

$Q_{1}=min\left\{b_{i}/a_{is}\right\}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall a_{is}> 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{2}=min\left \{ \left (b _{i}-u_{i} \right )/a_{is} \right \}

    Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall a_{is}<  0

$Q_{3}=u_{s}$

$Q_{1}$ "bottle-neck" solution becomes minimum and the simplex sheet will be solved ordinary.

$Q_{2}$ Substitution of BV of according row by its opposing variable. After that a ordinary iteration follows.

$Q_{3}$ Substitution of NBV of the Pivot column. No simplex solution will follow.

Example:

At this point of our Wiki we will return to our example to show you how upper bound problems will be solved. For this we take our last exercise with small modifications. We will invent upper bounds.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 60\leq x_{1}\leq 110

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 10\leq x_{2}\leq 45

Our sheet looks like that now:

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

First we will transform our basic sheet by solving the lower bound problem as explained a chapter before. This leads us to the following sheet.

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

Here the coordination system is shifted up to the new origin. At this point we also need to redifine our upper bounds.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq x_{1}\leq 50

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq x_{2}\leq 35

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

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

$Q_{1}=min\left\{45,80,50\right\}=45$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{2}= min\left \{ -,-,- \right \}= -

$Q_{3}=35$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow Q_{3}= Minimum \Rightarrow x'_{2}\rightarrow \bar{x}_{2}^{'}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{1}= min\left \{ 20,45,- \right \}= 20

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{2}= min\left \{ -,-,- \right \}= -

$Q_{3}=50$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow Q_{1}= Minimum \Rightarrow Phase 2

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{1}= min\left \{-,25,-\right \}= 25

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q_{2}= min\left \{15,-,\propto \right \}= 15

$Q_{3}=35$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow Q_{2}= Minimum

(column $x_{1}'$)

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

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

all $c_{j}>0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

optimal solution

transformation of the variables:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bar{x_{1}}'= 0 \Rightarrow x_{1}'= \bar{u_{1}}'-x_{1}'= 50-0=50

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow x_{1}= x_{1}'+l_{1}=50+60 =110

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bar{x_{2}}'=15\Rightarrow x_{2}'=\bar{u_{2}}'-x_{2}'=35-15=20

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow x_{2}=x_{2}'+l_{2}=20+10=30