Benutzerin:Gabriele Hornsteiner/Gemischte Modelle

Aus Wikibooks

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: mit

Restriktionen:

  • H:
  • L:
  • A:

Wir werden nun als Hilfsvariable My3 einführen:

Zielfunktion: mit


Restriktionen:

  • H:
  • L:
  • A:

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