Benutzerin:Gabriele Hornsteiner/Gemischte Modelle

Im Standardmodell des Simplexalgorithmus wird die Zielfunktion maximiert und es sind Höchstbeschränkungen vorgegeben. Bisweile wird man aber auch an einer Minimierung der Zielfunktion interessiert, seien es Kosten oder die Wegstrecke bei einem Transportproblem.

Es können Mindestbeschränkungen vorliegen oder es ist gewünscht, dass eine Gleichung exaktes Erfülltsein der Beschränkung erfordert.

Betrachten wir unser Politurbeispiel.

Es sei nun erwünscht, dass genau 25 Dosen des Bodepflegemittels verkauft werden. Die Grafik zeigt, dass alle realisierbaren Produktionsprogramme auf der Geraden x2=25 liegen, und zwar in dem Abschnitt zwischen den Wertepaaren (0;25) und (3,75;25). In diesem speziellen Beispiel wird klar, dass das Wertepaar (3,75;25) die Zielfunktion maxmiert, da x2 immer konstant 25 ist.

Wie implementiert man nun so etwas im Simplexmodell? Es soll das Standardmodell angestrebt werden.

Wir gehen aus von

Zielfunktion: $Z\rightarrow max$ mit $Z-5\cdot x_{1}-4\cdot x_{2}=0.$

Restriktionen:

• H: $4\cdot x_{1}+5\cdot x_{2}+y_{1}=140$
• L: $2\cdot x_{1}+1\cdot x_{2}+y_{2}=40$
• A: $x_{2}=25.$

Wir werden nun als Hilfsvariable My3 einführen:

Zielfunktion: $Z\rightarrow max$ mit $Z=5\cdot x_{1}+4\cdot x_{2}-My_{3}.$

Restriktionen:

• H: $4\cdot x_{1}+5\cdot x_{2}+y_{1}=140$
• L: $2\cdot x_{1}+1\cdot x_{2}+y_{2}=40$
• A: $x_{2}+y_{3}=25.$

M wird als sehr groß gewählt, so dass die Zielfunktion viel einbüßt, wenn y3 nicht allzuklein ist. Man nennt dieses M "Big-M", hie und da etwas konservativer auch "großes M".

Es ergäbe sich nun im Tableau zunächst

         x1   x2  y1  y2  y3   Z |  b
H |y1|    4    5   1   0   0   0 | 140       
L |y2|    2    1   0   1   0   0 |  40  
A |y3|    0   25   0   0   1   0 |  25     
---------------------------------------- 
Z |      -5   -4   0   0   M   1 |   0

Das entspricht allerdings nicht den Anforderungen an eine Anfangslösung, wenn die Basisvariablen haben in der Zielfunktionszeile eine Null, was hier wegen M nicht erfüllt ist. Man wird nun also zunächst mit Hilfe elementarer Zeilenoperationen das M aus dieser Zeile entfernen:

Zneu = Z - M*A

also

    Z |  -5   -4     0   0   M   1 |   0
-(M*A)|   0   25M    0   0   M   0 |  25M 
---------------------------------------- 
 =Zneu|   0   -25M-4 0   0   0   0 |  -25M 

         x1   x2  y1  y2  y3   Z |  b
H |y1|    4    5   1   0   0   0 | 140       
L |y2|    2    1   0   1   0   0 |  40  
A |y3|    0   25   0   0   1   0 |  25     
---------------------------------------- 
Z |      -5   -4   0   0   M   1 |   0

         x1   x2  y1  y2  y3   Z |  b
H |y1|    4    5   1   0   0   0 | 140       
L |y2|    2    1   0   1   0   0 |  40  
A |y3|    0   25   0   0   1   0 |  25     
---------------------------------------- 
Z |      -5   -4   0   0   M   1 |   0