ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Lineare Programmierung > Standardform: Maximierungsproblem:

Grafische Lösung eines Maximierungsproblems

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

In diesem Abschnitt soll aufgezeigt werden, wie man ein lineares Optimierungsproblem grafisch löst. Dazu muss die Standardform

Methode

         maximiere $f(x) = c^Tx$

u.d.N.

                      $Ax \le b$

                      $x \ge 0$

gegeben sein. Die grafische Lösung ist für Optimierungsprobleme mit zwei Entscheidungsvariablen geeignet. Es wird das folgende -aus dem vorherigen Abschnitt entnommene - Maximierungsproblem betrachtet:


$f(x_1, x_2) = 30 x_1 + 40 x_2$    $\rightarrow$   max!

u.d.N.

$x_1 + x_2 \le 15 $        Maschinenrestriktion

$x_1 + 2 x_2 \le 27$     Energierestriktion

$x_1 \le 8$                   Absatzrestriktion 1

$x_2 \le 10$                 Absatzrestriktion 2


$x_1, x_2 \ge 0$


Es soll nun für dieses Optimierungsproblem die optimale Kombination aus $x_1$ und $x_2$ zur Maximierung des Deckungsbeitrages unter Berücksichtigung der Restriktionen bestimmt werden. Dabei stellen $x_1$ und $x_2$ die stündlich zu produzierende Menge in Kilogramm dar.

Für die grafische Lösung geht man nun wie folgt vor:

Methode

1. Einzeichnung aller Restriktionen (Nebenbedingungen).

2. Einzeichnung der Zielfunktion.

3. Verschiebung der Zielfunktion (parallel zu sich selbst) bis diese gerade noch innerhalb des zulässigen Bereichs liegt.

1. Einzeichnen der Restriktionen

Die Nebenbedingungen werden nacheinander in ein Koordinatensystem eingezeichnet. Die Maschinenrestriktion (in rot eingezeichnet) hat die Form:

$x_1 + x_2 \le 15 $  

Um $x_1$ einzuzeichnen, wird $x_2 = 0$ gesetzt und dann nach $x_1$ aufgelöst:

$ x_1 = 15$

Um $x_2$ einzuzeichnen wird $x_1 = 0$ gesetzt und dann nach $x_2$ aufgelöst:

$x_2 = 15$

Merke

Werden keine Einheiten von $x_2$ produziert, so können 15 Einheiten von $x_1$ produziert werden und umgekehrt.

Die beiden Punkte $x_1(15; 0)$ und $x_2(0; 15)$ werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Eissroten hinsichtlich der Maschinenrestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einer Eissorte produziert wird, desto weniger Kapazität bleibt für die andere Eissorte übrig.


Die Energierestriktion (in grün) hat die Form:

$x_1 + 2 x_2 \le 27$ 


Umstellen nach $x_1$ und $x_2$ ergibt dann jeweils (wobei die andere Variable null wird):

$x_1 = 27$

$x_2 = \frac{27}{2} = 13,5$

Werden keine Einheiten von $x_2$ produziert, so können 27 Einheiten von $x_1$ produziert werden. Werden keine Einheiten von $x_1$ produziert, so können 13,5 Einheiten von $x_2$ produziert werden.

Die beiden Punkte $x_1(27; 0)$ und $x_2(0; 13,5)$ werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Eissroten hinsichtlich der Energierestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einer Eissorte produziert wird, desto weniger Kapazität bleibt für die andere Eissorte übrig.


Die Absatzrestriktionen (in blau) haben die Form:

$x_1 \le 8$

$x_2 \le 10$

Diese beiden Punkte hingegen werden nicht miteinander verbunden, sondern stellen Geraden dar. Dies liegt daran, dass die Absatzrestriktionen der beiden Torten nicht voneinander abhängig sind und sich gegenseitig nicht begrenzen.

In der nachfolgenden Grafik sind alle Restriktionen eingezeichnet:

Grafische Lösung LP - Restriktionen


Der zulässige Bereich wird durch diese eingezeichneten Restriktionen ermittelt. In diesem Beispiel ist dieser gegeben durch die Maschinenrestriktion (rot) und durch die Absatzrestriktionen (blau). Der zulässige Bereich ist in der nachfolgenden Grafik durch die schwarzen Linien gekennzeichnet:

Grafische Lösung LP - zulässiger Bereich

Die Nichtnegativitätsbedingungen geht dadurch ein, dass der Bereich oberhalb der Abzisse ($x_1$-Achse) und rechts von der Ordinate ($x_2$-Achse) betrachtet wird. Der zulässige Bereich stellt ein Vieleck (=Simplex) dar.

2. Einzeichnung der Zielfunktion

Um nun das optimale Produktionsprogramm zu ermitteln, also die optimale Kombination aus $x_1$ und $x_2$ zur Maximierung des Gesamtdeckungsbeitrages, wird die Zielfunktion benötigt. Diese hat die Form:

$f(x_1, x_2) = 30 x_1 + 40 x_2$ 

Hierbei ist es egal, welchen Höchstwert (rechte Seite) man ansetzt. Es ist wichtig, dass der gewählte Wert so hoch ist, dass sich die Zielfunktion in die Grafik einzeichnen lässt und noch innerhalb des zulässigen Bereiches liegt. Außerdem sollten dabei einigermaßen gerade Werte für $x_1$ und $x_2$ resutieren. Umso genauer wird am Ende das Ergebnis. In diesem Beispiel haben wir den Höchstwert $180$ gewählt:

$30x_1 + 40 x_2 \le 180$

mit

$x_1 = 6$

$x_2 = 4,5$

3. Verschiebung der Zielfunktion
Grafisches Verfahren Maximierungsproblem optimale Lösung
Bestimmung der optimalen Lösung

Diese beiden Punkte zeichnet man nun in die Grafik ein und verbindet sie miteinander (gelbe Linie). Als nächstes nimmt man sich ein Geodreieck in die Hand und verschiebt die Gerade solange (parallel zu sich selbst) nach oben bis zu dem Punkt, welcher sich gerade noch innerhalb des zulässigen Bereiches befindet. In der Grafik ist dies der gelb eingezeichnete Punkt. 

Es werden also von $x_1 = 5 kg/std$ und von $x_2 = 10 kg/std$ produziert. Dies ergibt einen Gesamtdeckungsbeitrag in Höhe von:

$f(5, 10) = 30 \cdot 5 + 40 \cdot 10 = 550 €$

Für die Gesamtproduktionsmenge von 15 kg pro Stunde erhält das Unternehmen einen Deckungsbeitrag von 550 € pro Stunde.

Zusammenfassung

Die Maschinenrestriktion (rot) begrenzt die Produktion der Eissorten. Es können also nicht beide Eissorten bis zu ihrem Absatzmaximum ($x_1 = 8$, $x_2 = 10$) produziert werden. Es stellt sich also die Frage, welche Sorte einen besseren Beitrag für den Deckungsbeitrag leistet. Es ist ersichtlich, dass die Schokoladensorte ($x_2$) bis zu ihrem Absatzmaximum in Höhe von 10 kg/std produziert wird. Die Vanillesorte hingegen ($x_1$) wird nicht bis zu ihrem Absatzmaximum in Höhe von 5 kg/std produziert. Der Grund dafür liegt darin, dass die Schokoladensorte einen höheren Deckungsbeitrag aufweist (40 €) und zur Maximierung des Gesamtdeckungsbeitrages einen höheren Beitrag leistet als die Vanillesorte. Die Energierestiktion ist in diesem Beispiel unerheblich, da die Maschinenrestriktion die Produktion so stark begrenzt, dass die Energiekapazität nicht ausgeschöpft wird. 

Kommentare zum Thema: Grafische Lösung eines Maximierungsproblems

  • Eckehard Quast schrieb am 16.02.2016 um 11:19 Uhr
    Hallo, Ich sehe in der Grafik leider keine gestrichelte Linie und der Punkt ist leider auch nicht zu finden. Auch müsste doch bei der Berechnung des Deckungsbeitrages der Wert für x1 = 5 angenommen werden, oder? Dann würde der DB sich ergeben durch: f( 5, 10) = 30*5 + 40*10 = 550€ Stimmt das?
Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen