Linear optimization: Upper and lower bounds 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Linear Optimization) |
(→Linear Optimization) |
||
Zeile 120: | Zeile 120: | ||
<math>Q_{3}=u_{s}</math> | <math>Q_{3}=u_{s}</math> | ||
+ | |||
+ | |||
+ | <math>Q_{1}</math> "bottle-neck" solution becomes minimum |
Version vom 7. Juni 2013, 15:42 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 into new one . 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.
By changing to 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 back to for getting the right results to the processed exercise.
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. was moved up by and and by .
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 and at least 10 units of product . It is pointed out in an own line. All informations are given.
Our next step is to replace our variables , by , by substracting the lower bounds variables ,. 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 top the upper bound they will be replaced by their "opposing" variable . 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 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 with (before selecting r or s for pivot element)
In Pivot column we need to transform our with its oposing , 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.
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
"bottle-neck" solution becomes minimum