|
|
| Zeile 8: |
Zeile 8: |
| | | | |
| | Sources: | | Sources: |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == '''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 <math>x_{j}\geq l_{j}</math>?'''''
| |
| − |
| |
| − |
| |
| − | ''Mathematically'' you just need to transform the old variable <math>{x}'_{j}</math> into new one <math>x_{j}</math>. You consider lower bounds before translating the simplex sheet.
| |
| − |
| |
| − | <math>{\color{Red} {x}'_{j}}= x_{j}-l_{j}</math>
| |
| − |
| |
| − | Now the lower bound changes to a non-negative-constraint.
| |
| − |
| |
| − | <math>{x}'_{j}> 0</math>
| |
| − |
| |
| − |
| |
| − | By changing <math>x_{j}</math> to <math>{x}'_{j}</math> we also need to replace the right site of our simplex tableau.
| |
| − |
| |
| − | The standard linear projection looks like
| |
| − |
| |
| − | <math>y_{i}+\sum a_{ij}\cdot x_{j}= b_{i}</math>
| |
| − |
| |
| − | Our modification leads us to the following formula.
| |
| − |
| |
| − | <math>y_{i}+\sum a_{ij}\cdot ({x}'_{j}+l_{j})= b_{i}</math>
| |
| − |
| |
| − | Now we just change the composition a bit to get our standard structure of the linear projection.
| |
| − |
| |
| − | <math>y_{i}+\sum a_{ij}\cdot {x}'_{j}= b_{i}-\sum a_{ij}\cdot l_{j}</math>
| |
| − |
| |
| − |
| |
| − | It is important to replace <math>{x}'_{j}</math> back to <math>x_{j}</math> for getting the right results to the processed exercise.
| |
| − |
| |
| − | <math>x_{j}= {x}'_{j}+l_{j}</math>
| |
| − |
| |
| − |
| |
| − | ''Graphically'' you need to shift the coordination system like pictured below.
| |
| − |
| |
| − | [[Datei:OR;bounds.jpg]]
| |
| − |
| |
| − | Here you see that the whole coordination system was moved up by the respective lower bound. <math>x_{1}</math> was moved up by <math>l_{1}</math> and <math>x_{2}</math> and by <math>l_{2}</math>.
| |
| − |
| |
| − |
| |
| − | ''Example:''
| |
| − |
| |
| − | We also want to solve an example for you as you can see below.
| |
| − |
| |
| − |
| |
| − | That is the initial situation.
| |
| − |
| |
| − | [[Datei:OR;bounds2.jpg]]
| |
| − |
| |
| − | We need to produce at least 60 units of product <math>x_{1}</math> and at least 10 units of product <math>x_{2}</math>. It is pointed out in an own line. All informations are given.
| |
| − |
| |
| − | Our next step is to replace our variables <math>x_{1}</math>,<math>x_{2}</math> by <math>{x_{1}}'</math>,<math>{x_{2}}'</math> by substracting the lower bounds variables <math>l_{1}</math>,<math>l_{2}</math>. Doing this operation it is necessary to conform our right site.
| |
| − |
| |
| − | We will do this by using this formula:
| |
| − |
| |
| − | <math>b_{i}^{neu}= b_{i}-\sum a_{ij}\cdot l_{j}</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | This operation leads us to sheet two.
| |
| − |
| |
| − | [[Datei:OR;bounds3.jpg]]
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | '''''How to integrate upper bounds like <math>x_{j}\leq u_{j}</math>?'''''
| |
| − |
| |
| − |
| |
| − | "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 <math>x_{j}</math> top the upper bound <math>u_{j}</math> they will be replaced by their "opposing" variable <math>\bar{x}_{j}</math>. 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'''
| |
| − |
| |
| − | <math>b_{i}^{new}=b_{i}-a_{is}u_{s} \forall i</math> + coefficients in column s change their sign
| |
| − |
| |
| − |
| |
| − | '''Substitution of BV'''
| |
| − |
| |
| − | <math>b_{r}=u_{r^{*}}-b_{r}</math> + coefficients <math>a_{rj}</math> 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 <math>b_{i}\leq u_{i}</math> and in case substitute <math>y_{i}</math> with <math>\bar{y}_{i}</math> (before selecting r or s for pivot element)
| |
| − |
| |
| − | In Pivot column we need to transform our <math>x_{s}</math> with its oposing <math>\bar{x}_{s}</math>, if <math>x_{s}\leq u_{s}</math>
| |
| − |
| |
| − |
| |
| − | '''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.
| |
| − |
| |
| − |
| |
| − | <math>Q_{1}=min\left \{b _{i}/a_{is} \right \}</math> <math>\forall a_{is}> 0</math>
| |
| − |
| |
| − | <math>Q_{2}=min\left \{ \left (b _{i}-u_{i} \right )/a_{is} \right \}</math> <math>\forall a_{is}< 0</math>
| |
| − |
| |
| − | <math>Q_{3}=u_{s}</math>
| |
| − |
| |
| − |
| |
| − | <math>Q_{1}</math> "bottle-neck" solution becomes minimum and the simplex sheet will be solved ordinary.
| |
| − |
| |
| − | <math>Q_{2}</math> Substitution of BV of according row by its opposing variable. After that a ordinary iteration follows.
| |
| − |
| |
| − | <math>Q_{3}</math> 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.
| |
| − |
| |
| − | <math>60\leq x_{1}\leq 110</math>
| |
| − |
| |
| − | <math>10\leq x_{2}\leq 45</math>
| |
| − |
| |
| − |
| |
| − | Our sheet looks like that now:
| |
| − |
| |
| − | [[Datei:OR;bounds4.jpg]]
| |
| − |
| |
| − | 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.
| |
| − |
| |
| − | [[Datei:OR;bounds5.jpg]]
| |
| − |
| |
| − | Here the coordination system is shifted up to the new origin. At this point we also need to redifine our upper bounds.
| |
| − |
| |
| − | <math>0\leq x_{1}\leq 50</math>
| |
| − |
| |
| − | <math>0\leq x_{2}\leq 35</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | [[Datei:OR;bounds6.jpg]]
| |
| − |
| |
| − |
| |
| − | [[Datei:OR;bounds7.jpg]]
| |
| − |
| |
| − | <math>Q_{1}= min\left \{ 45,80,50 \right \}= 45</math>
| |
| − |
| |
| − | <math>Q_{2}= min\left \{ -,-,- \right \}= -</math>
| |
| − |
| |
| − | <math>Q_{3}=35</math>
| |
| − |
| |
| − | <math>\rightarrow Q_{3}= Minimum
| |
| − | \Rightarrow x'_{2}\rightarrow \bar{x}_{2}^{'}</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | <math>Q_{1}= min\left \{ 20,45,- \right \}= 20</math>
| |
| − |
| |
| − | <math>Q_{2}= min\left \{ -,-,- \right \}= -</math>
| |
| − |
| |
| − | <math>Q_{3}= 50</math>
| |
| − |
| |
| − | <math>\rightarrow Q_{1}= Minimum
| |
| − | \Rightarrow Phase 2
| |
| − | </math>
| |
| − |
| |
| − |
| |
| − | [[Datei:OR;bounds10.jpg]]
| |
| − |
| |
| − | <math>Q_{1}= min\left \{-,25,-\right \}= 25</math>
| |
| − |
| |
| − | <math>Q_{2}= min\left \{15,-,\propto \right \}= 15</math>
| |
| − |
| |
| − | <math>Q_{3}=35</math>
| |
| − |
| |
| − | <math>\rightarrow Q_{2}= Minimum
| |
| − | </math>
| |
| − | (column <math>x_{1}'</math>)
| |
| − |
| |
| − | [[Datei:OR;bounds8.jpg]]
| |
| − |
| |
| − | [[Datei:OR;bounds9.jpg]]
| |
| − |
| |
| − | all <math>c_{j}>0</math>
| |
| − |
| |
| − | <math>\Rightarrow</math> optimal solution
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | transformation of the variables:
| |
| − |
| |
| − | <math>\bar{x_{1}}'= 0 \Rightarrow x_{1}'= \bar{u_{1}}'-x_{1}'= 50-0=50</math>
| |
| − |
| |
| − | <math>\Rightarrow x_{1}= x_{1}'+l_{1}=50+60 =110</math>
| |
| − |
| |
| − | <math>\bar{x_{2}}'=15\Rightarrow x_{2}'=\bar{u_{2}}'-x_{2}'=35-15=20</math>
| |
| − |
| |
| − | <math>\Rightarrow x_{2}=x_{2}'+l_{2}=20+10=30</math>
| |
