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 > Simlpex-Algorithmus: Einführung > Primales Simlpexverfahren:

Beispiel: Maximierungsproblem / grafische Lösung

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 ein gegebenes Maximierungsproblem zunächst grafisch gelöst werden. Im folgenden Abschnitt wird dasselbe Problem dann mittels Simplexverfahren gelöst.

Anwendungsbeispiel: Produktionsprogrammplanung

Ein Unternehmen produziert zwei Produkte $x_1$ und $x_2$ mit einem Gewinn von $g_1 = 250 €$ und $g_2 = 450 €$. Zur Produktion der beiden Produkte stehen zwei Maschinen zur Verfügung: $A$ und $B$. Einige Montagearbeiter $M$ sind dafür zuständig die Teile am Ende so zusammenzusetzen, dass die beiden Produkte entstehen. In der folgenden Tabelle sind die dazugeghörigen Daten aufgelistet:

Artikel Kapazität pro Tag
1 2
Maschine A 4 3 24 h
Maschine B 2 4 24 h
Montagearbeiter M 4 5 32 h
Gewinn pro Stück       250    450     

Im mittleren Bereich der Tabelle stehen die Stundenzahlen, die für die Produktion eines Produktes benötigt werden. So werden zum Beispiel zur Produktion von Produkt 1 4 Stunden auf Maschine A, 2 Stunden auf Maschine B und 4 Stunden zur Montage benötigt.

Ziel des Unternehmens ist es, seinen Gewinn zu maximieren. Es handelt sich in diesem Fall also um ein Maximierungsproblem mit der Form:

$f(x_1, x_2) = z = 250x_1 + 450 x_2$    $ \rightarrow$   max!

u.d.N.

$4x_1 + 3x_2                      \le 24$

$2x_1 + 4x_2                      \le 24$

$4x_1 + 5x_2                      \le 32$

$x_1, x_2  \ge 0$

Die Nichtnegativitätsbedingung muss hier eingeführt werden, da keine negativen Produkte hergestellt werden können. Das Maximierungsproblem wird zunächst grafisch gelöst.

grafische Lösung

Um die Restriktionen einzeichnen zu können, müssen die Schnittpunkte der einzelnen Gleichungen mit den Koordinatenachsen bestimmt werden. Die Koordinatenachsen spiegeln die zwei Produkte wieder. Für die Gleichung 

$4x_1 + 3x_2                      \le 24$

ergibt sich der Schnittpunkt mit der $x_1$-Achse durch Nullsetzen von $x_2$ und der Schnittpunkt mit der $x_2$-Achse durch Nullsetzen von $x_1$:

$x_1 = \frac{24}{4} = 6$

$x_2 = \frac{24}{3} = 8$.

Werden keine Einheiten von $x_2$ produziert, so können 6 Einheiten von $x_1$ produziert werden. Werden keine Einheiten von $x_1$ produziert, so können 8 Einheiten von $x_2$ produziert werden.

Die beiden Punkte $P_1(6; 0)$ und $P_2(0; 8)$ werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Produkte hinsichtlich der Maschinenrestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einem Produkt produziert wird, desto weniger Kapazität bleibt für das andere Produkt übrig.

Entsprechend wird auch mit den anderen beiden Restriktionen verfahren:

Beispiel Maximierungsproblem grafische Lösung

In der obigen Grafik ist das Koordinatensystem mit den eingezeichneten Restriktionen zu sehen. Dabei nennt man den Bereich, der von den Restriktionen eingeschlossen wird zulässigen Bereich. Alle Lösungen innerhalb dieses Bereichs sind zulässig. Es soll aber die optimale Lösung unter den zulässigen Lösungen gefunden werden.

Beispiel Maximierungsproblem grafische Lösung zulässiger Bereich

In dem nächsten Schritt wird nun die Zielfunktion benötigt. Für diese wird auf der rechten Seite ein fiktiver Gesamtgewinn angesetzt, so dass die Neigung der Gewinnfunktion in die Grafik eingezeichnet werden kann.

$z = 250x_1 + 450 x_2 $

Sinnvoll ist es einen Wert zu wählen, so dass die Division mit den beiden Werten $250$ und $450$ ganze Zahlen bzw. Zahlen mit nur einer Nachkommastelle ergeben (umso genauer kann die Zielfunktionsgerade eingezeichnet werden). Außerdem sollte die Zielfunktionsgerade noch im zulässigen Bereich liegen. Wir wählen hier also nun einen bliebigen Gesamtgewinn aus:

$z = 250 x_1 + 450 x_2  = 900$

Der Schnittpunkt mit der $x_1$-Achse ergibt sich durch Nullsetzen von $x_2$ und der Schnittpunkt mit der $x_2$-Achse durch Nullsetzen von $x_1$:

$x_1 = 3,6$

$x_2 = 2$.

Beispiel Maximierungsproblem grafische Lösung

Die gestrichelte Linie stellt die Zielfunktionsgerade dar. Diese muss nun solange parallel zu sich selbst verschoben werden (Geodreieck verwenden), bis diese gerade noch den zulässigen Bereich berührt. Der letzte Berührungspunkt der Zielfunktionsgeraden mit dem zulässigen Bereich stellt die optimale Lösung dar.

Beispiel Maximierungsproblem grafische Lösung

In der obigen Grafik wurde die Zielfunktionsgerade nun solange verschoben (parallel zu sich selbst), bis sie gerade noch im zulässigen Bereich liegt. Der Punkt (grau) ist dabei der Punkt, der gerade noch im zulässigen Bereich liegt und damit die optimale Lösung:

$x_1 = 1,3$ und 

$x_2 = 5,3$.

Das bedeutet also, dass von $x_1 = 1$ Menge produziert und von $x_2 = 5$ Mengen produziert werden, damit der Gewinn für das Unternehmen am Größten ausfällt unter Berücksichtigung der gegebenen Kapazitäten. Da nur ganze Produkte hergestellt werden können, muss in jedem Fall immer abgerundet werden.

Der Gewinn des Unternehmens beträgt dann:

$z = 250 \cdot 1 + 450 \cdot 5  = 2.710 €$.

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