iconEuler Examples

Optimierung - Beispiele

Wir rechnen einige Beispiele für Optimierung mit dem
Simplex-Algorithmus und mit der Hand (unterstützt durch Euler) durch.

Das erste Beispiel besteht aus Kapazitätsbeschränkungen für eine
Landwirt, der zwei Feldfrüchte anbauen möchte. Er hat 1000ha Fläche
und 4500 Arbeitsstunden zur Verfügung. Das ergibt für ihn die
Beschränkungen

Optimierung - Beispiele

Maximieren will er den Gewinn

Optimierung - Beispiele

Dazu geben wir alles in Matrixform ein.
>A=[1,1;4,5]
                  1                   1 
                  4                   5 
>b=[1000,4500]'
               1000 
               4500 
>c=[5,6]
[ 5  6 ]
Euler kann bei zwei Variablen die Menge der zuläsigen Punkte als
Polygon berechnen. Die Nebenbedingung hat dabei die Form

Optimierung - Beispiele

>x=feasibleArea(A,b);
>plot2d(x[1],x[2],filled=true,style="/");
Wir starten nun den Simplexalgorithmus, der ohne weitere Angaben das
Problem

Optimierung - Beispiele

Optimierung - Beispiele

löst. Wir setzen das Flag für Maximierung. Das Flag für check erspart
uns, den Ergebniscode zu überprüfen.
>v=simplex(A,b,c,>max,>check)
                500 
                500 
Nun plotten wir den optimalen Punkt und die Niveaulinie der
Zielfunktion.
>function map f(x,y) := c.[x;y]
>plot2d("f",niveau=c.v,>add);
>plot2d(v[1],v[2],points=true,style="ow",>add); insimg;

Optimierung - Beispiele

Der Wert der Zielfunktion ist 5500.
>c.v
[ 5500 ]
Das duale Problem lautet

Optimierung - Beispiele

Optimierung - Beispiele

Man kann das so deuten, dass der Landwirt sein gesamtes Land und seine
gesamte Arbeitskraft zu Preisen p1 bzw. p2 möglichst günstig anbietet,
so dass es auf jeden Fall für ihn günstiger wird, als wenn er alles
selbst vermarkten würde.

Wir lösen es, wobei wir durch den vierten Parameter eq=1 die
Ungleichungen als >= kennzeichnen.

>p=simplex(A',c',b',eq=1,>min,>check)
                  1 
                  1 
>b'.p
[ 5500 ]
Ändert man die Zielfunktion ein wenig ab, so ergibt sich ein Minimum,
das die Ressourcen nicht voll ausschöpft.
>c=[5,7];
>x=feasibleArea(A,b); ...
>plot2d(x[1],x[2],filled=true,style="/"); ...
>v=simplex(A,b,c,>max,>check), ...
                  0 
                900 
>plot2d("f",niveau=c.v,>add); ...
>plot2d(v[1],v[2],points=true,style="ow",>add); insimg;

Optimierung - Beispiele

Im dualen Problem erkennt man, dass der Landwirt den Preis so
festsetzt, dass die erste Feldfrucht nicht abgerufen wird, da er daran
mehr verdienen würde als durch eigene Disposition.
>p=simplex(A',c',b',eq=1,>min,>check); A'.p-c'
                0.6 
                  0 

Ein Transportproblem

Wir lösen das Transportproblem, bei dem aus zwei Lagern zwei
Produktionsstätten beliefert werden sollen. Die Menge, die dabei von
Lager i nach Ort j geschickt werden, nennen wir c(i,j). Die Kosten
seien

Optimierung - Beispiele

Die zur Verfüngung stehenden Mengen und die benötigten Mengen ergeben
Restriktionen

Optimierung - Beispiele

Optimierung - Beispiele


Optimierung - Beispiele

>shortformat;
Die Spalten der Matrix entsprechen den Variablen

Optimierung - Beispiele

>A=[1,1,0,0;0,0,1,1;1,0,1,0;0,1,0,1]
          1           1           0           0 
          0           0           1           1 
          1           0           1           0 
          0           1           0           1 
>b=[1000,800,1200,600]'
       1000 
        800 
       1200 
        600 
Die Ungleichungen sind zweimal <= und einmal >=.
>eq=[-1,-1,1,1]'
         -1 
         -1 
          1 
          1 
>c=[2,3,4,2]
[ 2  3  4  2 ]
Es ergibt sich die Lösung, die auch in Klammern im obigen Bild
angedeutet ist.
>x=simplex(A,b,c,eq=eq,>min,>check)
       1000 
          0 
        200 
        600 
Das duale Problem hat auch hier eine Deutung.

Statt die Lieferung selbst zu machen, verkaufen wir die Ware in den
Lagern zu Preisen p1, p2 und kaufen sie wieder zu Preisen q1, q2 ein,
wo sie gebraucht wird. Die Differenz der Verkaufspreise darf nicht
größer als die Transportkosten sein, also etwa

Optimierung - Beispiele

Die Preise gestalten wir so, dass der Vertragsnehmer möglichst viel
Gewinn macht.

Der Einfachheit halber schreiben wir alles in Form von <=. Das geht
durch Multiplikation von A und b mit -eq.
>p=simplex(-(eq*A)',c',-(eq*b)',>max,>check)
          2 
          4 
          0 
          2 
Wir erhalten dasselbe Optimum.
>-(eq*b)'.p, c.x
[ 4000 ]
[ 4000 ]

Examples Homepage