Linear optimization: Upper and lower bounds 1: Unterschied zwischen den Versionen

Version vom 7. Juni 2013, 15:12 Uhr

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 ${\displaystyle {x}'_{j}}$ into new one ${\displaystyle 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.

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

By changing ${\displaystyle x_{j}}$ to ${\displaystyle {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 ${\displaystyle {x}'_{j}}$ back to ${\displaystyle x_{j}}$ for getting the right results to the processed exercise.

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

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

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

Example:

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

That is the initial situation.

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

Our next step is to replace our variables ${\displaystyle x_{1}}$,${\displaystyle x_{2}}$ by ${\displaystyle {x_{1}}'}$,${\displaystyle {x_{2}}'}$ by substracting the lower bounds variables ${\displaystyle l_{1}}$,${\displaystyle 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.

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 ${\displaystyle x_{j}}$ top the upper bound ${\displaystyle u_{j}}$ they will be replaced by their "opposing" variable ${\displaystyle {\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).

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 ${\displaystyle 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.

In Phase 0 and 0` there are

${\displaystyle 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

${\displaystyle Q_{3}=u_{s}}$