REFERAT-MenüDeutschGeographieGeschichteChemieBiographienElektronik
  EnglischEpochenFranzösischBiologieInformatikItalienisch
  KunstLateinLiteraturMathematikMusikPhilosophie
 PhysikPolitikPsychologieRechtSonstigeSpanisch
 SportTechnikWirtschaftWirtschaftskunde  

Lineare Optimierung



Theodor - Litt - Schule
Neumünster



1. Einleitung: Was ist eigentlich "lineare Optimierung"?

Die lineare Optimierung ist ein Teilgebiet der Optimierungsrechnung. Diese Rechnung ist ein Hilfsmittel zur optimalen Entscheidungsfindung bei komplizierten Problemen.

Unter einschränkenden Bedingungen wird mit Hilfe der linearen Optimierung das Minimum beziehungsweise das Maximum einer linearen Funktion ermittelt. Die zu maximierende Funktion ist dabei meistens die Gleichung für den Gewinn, die zu minimierende Funktion die Gleichung für die Kosten eines Unternehmens.

Die einschränkenden Bedingungen, die Einfluss auf das Ergebnis haben, müssen herausgefunden werden, um sie dann mit dem zu erreichenden Maximum / Minimum in Verbindung zu setzen.

2. Geschichte der "linearen Optimierung"

Die lineare Optimierung gehört zu den jüngeren Anwendungsgebieten der Mathematik. Vor einem halben Jahrhundert begann der richtige Durchbruch der linearen Optimierung mit der Simplexmethode, die von G.B. Dantzig entwickelt wurde. Die ersten Arbeiten der Linearen Optimierung wurden im Jahre 1939 von dem russischen Mathematiker Leonid W. Kantorowicz in diesem Gebiet veröffentlicht.

Besonders in den USA wurden am Ende des zweiten Weltkrieges neue Lösungsmöglichkeiten für Probleme der mathematischen Optimierung, die für den militärischen Bereich von Bedeutung waren, entwickelt.

Die Simplexmethode, mit der alle linearen Optimierungsprobleme gelöst werden können, ist bis heute das wichtigste Verfahren zur Lösung von Problemen dieser Art.

J. von Neumann und O. Morgenstern gelang es schon kurz nach Dantzig diese Methode beträchtlich weiterzuentwickeln. Seit Beginn der 50er Jahre erlebte dieser Bereich der Mathematik erneut eine rapide Aufwärtsentwicklung. Dieser große Aufschwung wirkte sich besonders günstig auf Großrechenanlagen aus, die Berechnungen nach dem Simplexverfahren in einer kurzen Zeit bewältigen konnten. Schon im Jahre 1956 konnten mit einer IBM- Maschine Probleme der linearen Optimierung mit mehr als 200 Gleichungen mit großer Genauigkeit gelöst werden. Die erste wichtige Anwendung auf wirtschaftliche Probleme erfolgte bei der Planung und Entwicklung von Erdölraffinerien.

Im Jahre 1979 entwickelte der Russe Khasian einen neuen Algorithmus, mit dem bei linearen  Optimierungsproblemen mit einer großen Anzahl von Variablen und einschränkenden Bedingungen die optimale Lösung schneller bestimmt werden konnte. Der wesentliche Vorteil dieses Verfahrens liegt darin, dass der Rechenaufwand geringer ist, als beim Simplexverfahren. Heute gehört die lineare Optimierung zu den best erforschten Gebieten der Wirtschaftsmathematik.

3. Graphisches Verfahren

 

3.1 Aufgabenstellung

Eine Unternehmung stellt zwei Produkte P1 und P2 her. Die Fertigung erfolgt auf den Maschinen M1, M2 und M3 und erfordert unterschiedliche Belegungszeiten. Die Bearbeitungsdauer (bezogen auf Minuten) und die Kapazitäten (bezogen auf Mengeneinheiten) der Maschine sind in der folgenden Tabelle angegeben.

Bearbeitungszeit

Bearbeitungszeit

Kapazität

für P1

für P2

M1

20

40

8000

M2

15

10

3000

M3

30

10

5400

Der Deckungsbeitrag pro ME beträgt 90 GE von P1 und 120 GE von P2.

Wie viele ME sind von P1 und von P2 herzustellen, damit der gesamte Deckungsbeitrag möglichst groß ist. Wie hoch ist dieser maximale Deckungsbeitrag?

xi  sei die Zahl der Produkte Pi

Z = 90x1 + 120x2 } Zielfunktion

20x1 + 40x2 8000            Maschine M1

15x1 + 10x2 3000            Maschine M2

30x1 + 10x2   5400            Maschine M3


x1   0

x2 0           Nichtnegativitätsbedingungen

Die Zielfunktion ist das Optimierungskriterium, welches minimal oder maximal werden soll.

In diesem Fall geht es um den Deckungsbeitrag, der maximal werden soll.

Die Nebenbedingungen sind Restriktionen (Beschränkungen), die sich in diesem Fall aus den Kapazitätsbeschränkungen der Maschinen ergeben.

Es gibt nämlich keinen Sinn negative Werte für x1 und x2 zuzulassen, denn die produzierte Menge kann nicht negativ sein. Deshalb unterliegen die Variablen x1 und x2 den Nichtnegativitätsbedingungen.

3.2 Graphische Lösung

Für Systeme mit zwei Variablen lassen sich die möglichen Lösungsmengen in einer Ebene (zweidimensional) graphisch veranschaulichen:

Für das Gleichheitszeichen wird mit jeder Nebenbedingung eine Gerade definiert, die die Ebene in zwei Halbebenen teilt.

Durch das Ungleichheitszeichen wird die Halbebene spezifiziert, in der die mögliche Lösungsmenge liegt. Im Ergebnis entsteht ein Polygon (=Vieleck).

Dazu stellt man zunächst die Nebenbedingungen nach x2 um.

20x1 + 40x2  8000               / -  20x1

            40x2  8000 - 20x1  /  :  40

                x2      200 -  0,5x1

                 x2      300 - 1,5x1

                 x2    540 - 3x1

Die Zielfunktion löst man auch nach x2 auf:

Z = 90x1 + 120x2

      

      3       Z

x2   =  - ——— + —————

      4      120  

 

Die Graphen dieser Funktionenschar sind parallele Geraden, die danach unterschieden werden können, in welchen Punkten

PZ

 
                        Z  

                    ¦0/ —————¦ sie die y- Achse schneiden.

                       120 ‡

Man konstruiert die Gerade der Zielfunktion für Z = 0.

Die Gerade wird solange parallel nach oben verschoben, bis sie an einem Eckpunkt das Polygon verlässt. Dieser Eckpunkt ist ein Optimum unseres Problems.

 

Z=0 :                      3                       0 

               x2 =  - --- x1  +   ---

4                                  120

                               3

                x2  =  - --- x1

4


PMAX  (100/150)  ist der optimale Punkt. Man erzielt den höchsten Deckungsbeitrag, wenn 100 ME von P1 und 150 ME von P2  hergestellt werden.

Berechnung des maximalen Deckungsbeitrags:

 

ZMax  = 90x 1  + 120x2

        = 90*100 + 120*150

        = 27000


Der maximale Deckungsbeitrag beträgt 27000 GE.



I    x2 200 - 0,5x1

II   x2 300 - 1,5x1

III  x2 540 - 3x1

Z = - 0,75x1            (Parallelverschiebung von Z nach Z1)



4. Die reguläre Simplexmethode

Das graphische Verfahren zur Lösung von linearen Optimierungsproblemen ist nur anwendbar bei zwei, höchstens drei Variablen. Aber schon bei drei Variablen trifft man auf erhebliche Schwierigkeiten, weil drei Variablen eine räumliche Darstellung in der Zeichenebene verlangen.

Bei n Variablen werden die Lösungsmengen von Hyperebenen im n - dimensionalen Raum begrenzt.

Es ensteht ein Polyeder (= Vielflächner).

Die Simplexmethode ist eine algebraische Methode, die es ermöglicht, lineare Optimierungsprobleme mit beliebig vielen Variablen einfach und übersichtlich zu lösen.

Ein Simplex ist ein Polyeder des R n (n - dimensionalen Raums) mit n + 1 Ecken.

zum Beispiel:                        R2: Dreieck                      R3: Tetraeder

 
                   


Das Simplexverfahren ist ein Iterationsverfahren (schrittweises Rechenverfahren zur Annäherung an die exakte Lösung).

Man beginnt mit einer Startnäherung (meist xi = 0) und verbessert sukzessive (allmählich eintretend) die Zielfunktion.

Das Verfahren wird an dem obigen Beispiel erläutert:

a) Durch Einführen von Schlupfvariablen (ui  0) wird das Optimierungsproblem als lineares                                 

    Gleichungssystem formuliert.

    Die Schlupfvariable füllt den noch vorhandenen "Spielraum" aus, wenn die Werte für x1

    und x2 des linken Teils der Ungleichung kleiner als der Wert des rechten Teils sind.

    Die Schlupfvariablen u1, u2 und u3 übernehmen also die Werte der jeweils noch freien

    Kapazität der Maschinen M1, M2 und M3.

    20x1 + 40x2 + u1 = 8000

    15x1 + 10x2 + u2 = 3000

    30x1 + 10x2 + u3 = 5400

 

    90x1 + 120x2 = Z

    (4 Gleichungen, 6 Unbekannte)

Basisvariable:          Variable, die nach Vorgabe von zwei Variablen berechnet wird

(u1, u2, u3)

 

Nichtbasisvariable:  frei vorgebbare Variablen (= 0)

(x1, x2)

b) Startpunkt:    x1 = x2 = 0 (Nichtbasisvariablen)

   

         Berechnen der Basisvariablen

      I   u1 = 8000 - 20x1 - 40x2

     II  u2 = 3000 - 15x1 - 10x2

    III  u3 = 5400 - 30x1 - 10x2

    IV  Z  = 90x1 + 120x2

 

    u1 = 8000

    u2 = 3000

    u3 = 5400

    Z  = 0

Bei dieser Ausgangslösung hat die Zielgröße den Wert Null; die Lösung ist im Sinne der Maximierung von Z aber eine "schlechte" Lösung.

c) Zur Verbesserung der Lösung soll nun ein Variablenaustausch erfolgen. Da x2 den größten 

    Einfluss auf die Zielfunktion hat, wird x2 in die Basis aufgenommen (x2 hat den größten

    Einfluss auf die Zielfunktion, da der Deckungsbeitrag um 120 GE steigt, wenn der Wert

    von x2 um eine ME steigt. Bei x2 steigt der Deckungsbeitrag nur um 90 GE).

    Gegen welche Variable wird x2 getauscht?

x1 = 0, u1 = 0

 
Versuch 1:     x2                  u1          :  

aus I folgt:

x2:                                   u1 = 8000 - 20x1 - 40x2                      / - 8000 + 20x1

                 u1 - 8000 + 20x1 = - 40x2                                                

                               - 8000   = - 40x2                                            / : (- 40)

                                        x2 = 200       

aus II folgt:

u2:                                   u2 = 3000 - 15x1 - 10x2

                                         u2 = 3000 - 10 * 200

                                         u2 = 1000

aus III folgt:

u3:                                    u3 = 5400 - 30x1 - 10x2

                                         u3 = 5400 - 10 * 200

                                         u3 = 3400

 

 

 

x1 = 0, u2 = 0

 
 


Versuch 2:        x2                  u2        :

aus II folgt:

x2:                                       u2 = 3000 - 15x1 - 10x2                        / - 3000 + 15x1

                     u2 - 3000 + 15x1 = - 10x2

                                       - 3000 = - 10x2                                             / : (- 10)    

                                              x2 = 300

           

aus I folgt:

u1:                                u1 = 8000 - 20x1 - 40x2

                                                                       u1 = 8000 - 40 * 300

                                   u1 = -4000                                      ( Widerspruch, da u1 < 0 !)

ui ’ 0

 
                                                                   

x1 = 0, u3 = 0

 


Versuch 3: :        x2                  u3        :

aus III folgt:

x2:                                     u3 = 5400 - 30x1 - 10x2                            / -5400 + 30x1

                  u3 - 5400 + 30x1 = -10x2

                                   -5400 = -10x2                                                       / :(-10)

                                         x2 = 540

 

aus II folgt:

u2:                               u2 = 3000 - 15x1 - 10x2

                                    u2 = 3000 - 10 * 540

                                    u2 = - 2400                                      ( Widerspruch, da u2 < 0 !)

ui ’ 0

 
 


                       

Die erste Gleichung stellt den Engpass dar, denn die "engste" Einschränkung wird durch die erste Maschine verursacht. Dort ist x2 nur 200. Deshalb wird x2 gegen u1 getauscht.

Die neuen Nichtbasisvariablen heißen x1 und u1.

d) Umschreiben auf die neuen Basisvariablen:

     I                                  u1 = 8000 - 20x1 - 40x2                  / - 8000 + 20x1

                 u1 - 8000 + 20x1 = - 40x2                                      / : (- 40)

                                                         

                                                          u1

                                          x2 = - ---- + 200 - 0,5x1

                                                          40                                     

                                                                u1

       II        u2 = 3000 - 15x1 - 10 (- ---- + 200 - 0,5x1)

                                                                40

                                                   1u1

                   u2 = 3000 - 15x1 - --- - 2000 + 5x1

                                                    4

                                                     1

                   u2 = 1000 - 10x1 - ---

                                                     4

                                                      u1

                    u2 = 1000 - 10x1 - ---

                                                       4

       




       III          u3 = 5400 - 30x1 - 10x2

                                                              u1

                      u3 = 5400 - 30x1 - 10(- --   + 200 - 0,5x1)

                                                              40

                                                        u1

                       u3 = 5400 - 30x1 + -- - 2000 + 5x1

                                                        4

                                                       u1

                       u3 = 3400 - 25x1 + --

                                                        4

                                                    u1

          IV        Z = 90x1 + 120(- --   + 200 - 0,5x1)

                                                     40

                       Z = 90x1 - 3u1 + 24000 - 60x1

                       Z = 30x1 - 3u1 + 24000

                       Nichtbasisvariable, also x1 und u1 sind 0 !

                       Z = 30 * 0 - 3 * 0 + 24000

                       Z =24000

 

Die Variable x1 in die Basis aufzunehmen vergrößert Z.

Für den Engpass folgt aus der Gleichung I:

x1 = 400, aus Gleichung II x1 = 100 und aus Gleichung III x1 = 136. Den Engpass stellt somit die zweite Gleichung dar. Deshalb wird x1 gegen u2 getauscht.

e)     Umschreiben auf die neuen Basisvariablen

                                                                              u1

II                                       u2 = 1000 - 10x1 - ---

                                                                               4

                                                                     u1

                               u2 - 1000 = - 10x1 - ---

                                                                      4

                                        u1

                 u2 - 1000 + --- = - 10x1

                                        4

               u2                      u1

        - --- + 100 - --- = x1

10                                     40

x1 in I, III und IV einsetzen

            

I                     u1                                u2                      u1

       x2 =  - --- + 200 - 0,5 (- --- + 100 - --- )

                      40                               10                     40

                      u1

       x2 = - --- + 200 + 0,05u2 - 50 + 0,0125 u1

                      40

                      u1

        x2 = - --- + 200 + 0,05u2 - 50 + 0,0125u1

                      40

         x2 = - 0,0125u1 + 150 + 0,05u2

                                                  

 III                                   u2                       u1                u1

         u3 = 3400 - 25(- --- + 100 - --- ) + ---

                                        10                      40               4

         

          u3 = 3400 + 2,5u2 - 2500 + 0,625u1 + 0,25u1

           

           u3 = 900 + 2,5u2 + 0,875u1

IV                                u2                      u1

               Z =   30( - --- + 100 - ---) - 3u1 + 24000

10                                     40

               Z = - 3u2 + 3000 - 0,75u1 - 3u1 + 24000

                Z = - 3u2 - 3,75u1 + 27000

Die Nichtbasisvariablen u1 und u2 sind Null, daraus folgt Z = 27000.

Das ist die optimale Lösung, weil ein Austauschen der Basisvariablen x1, x2 und u3 gegen die Nichtbasisvariablen u1 und u2 keine Steigerung der Werte der Zielgröße nachsichzieht.

Denn nimmt man u1 oder u2 als Basisvariablen, dann ginge der Deckungsbeitrag zurück.

Der Deckungsbeitrag ist also mit 27000 GE maximal, wenn 100 ME von P1 und 150 ME von P2 hergestellt werden.

Die  dritte Maschine hat dann noch eine freie Kapazität von 900 bezogen auf ME, die Maschinen M1 und M2 sind ausgelastet.

5. Simplex - Tableau:

 

Der oben beschriebene Lösungsweg lässt sich mit Hilfe des Simplex - Tableaus übersichtlicher darstellen.

Für das bekannte Beispiel gilt das folgende Tableau:

BV*

x1

x2

u1

u2

u3

Abs. Glied

Engpass

u1

20

40

1

0

0

8000

200

u2

15

10

0

1

0

3000

300

u3

30

10

0

0

1

5400

540

Z

90

120

0

0

0

0

x2

0,5

1

0,025

0

0

200

400

u2



10

0

-0,25

1

0

1000

100

u3

25

0

-0,25

0

1

3400

136

Z

30

0

-3

0

0

-24000

x2

0

1

0,0375

-0,05

0

150

x1

1

0

-0,025

0,1

0

100

u3

0

0

0,375

-2,5

1

900

Z

0

0

-2,25

-3

0

-27000

*) Basisvariable

x2 = 150         (150 ME von P2)

x1 = 100         (100 ME von P1)

u3 = 900         (die dritte Maschine hat noch eine freie Kapazität von 900 bezogen auf ME, die

                        Maschinen M1 und M2 sind ausgelastet)

Z = 27000     (max. Deckungsbeitrag)

 

 

 

5.1 Rechenregeln:

ü     Die Pivot- Spalte ist die Spalte, in der die Variable mit dem größten Einfluss auf Z steht.

ü     Die Pivot- Zeile wird durch den Engpass bestimmt:

Dazu nimmt man alle positiven Koeffizienten der Pivot- Spalte und teilt die absoluten Glieder durch die Koeffizienten. Der kleinste Wert bestimmt den Engpass. Negative

      Koeffizienten und Nullen bleiben unberücksichtigt; kann kein Engpass bestimmt werden,           

      so ist das Optimierungsproblem nicht lösbar.

                                       neu                                                                                                                                                                                                           alt

ü     Um die neue Zeile Zi  zu berechnen, dividiere man alle Elemente der Schlüsselzeile Zi

durch  das Pivot - Element.

Das Pivot- Element ist das Element in der Pivot- Spalte und der Pivot- Zeile.

ü     Alle anderen Koeffizienten berechnet man nach der Vorschrift:

  

  neu                      alt             alt               neu

a i  j   = a i  j  -  Si   *  Zj

Zeile

 


Spalte

S = Pivot- Spalte

    neu

Z = aus Pivot- Zeile hervorgegangene Zeile

Beispiele:

      neu

a21   = 15 - 10 * 0,5 = 10

      neu

a22    = 10 - 10 * 1   = 0

       neu

      a23           = 0 - 10 * 0,025 = - 0,25

neu

a24      = 1 - 10 * 0 = 1

Quellenangaben - Literaturverzeichnis

Ø     Taschenbuch Mathematischer Formeln

H.- J. Bartsch

Fachbuchverlag Leipzig, 1998

Ø     Lineare Algebra, Wirtschaft

Cornelsen, 1998

·       www.maphi.de

·       www.mathekiste.de

 










Haupt | Fügen Sie Referat | Kontakt | Impressum | Datenschutz







Neu artikel