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:

Umformung in die Standardform (Maximierungsproblem)

WebinarTerminankündigung aus unserem Online-Kurs Thermodynamik:
 Am 13.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Thermodynamik) Innere Energie, Wärme, Arbeit
- Innerhalb dieses 60-minütigen Webinares wird der 1. Hauptsatz der Thermodynamik für geschlossene Systeme behandelt und auf die innere Energie, Wärme und Arbeit eingegangen.
[weitere Informationen] [Terminübersicht]

Es ist immer sinnvoll ein Optimierungsproblem in Standardform (Maximierungsproblem, kleiner/gleich Ungleichungen, Nichtnegativitätsbedingung) vorliegen zu haben. Die grafische Lösung kann in diesem Fall dann so vorgenommen werden, wie es in den vorherigen Abschnitten gezeigt wurde. Aber auch für die Aufstellung des in den folgenden Abschnitten aufgeführten Simplex-Algorithmus ist das Vorliegen der Standardform sinnvoll. In diesem Abschnitt wird ausführlich beschrieben, wie man ein Optimierungsproblem in die Standardform umformt. 

Es existieren vier mögliche Gründe für die Abweichung von der Standardform

  1. Variablen ohne Nichtnegativitätsbedingung,

  2. Gleichheitsbedingungen statt Ungleichheitsbedingungen und

  3. Größer/gleich-Ungleichungen statt Kleiner/gleich-Ungleichungen.

Es ist möglich lineare Optimierungsprobleme in denen diese Fälle auftreten durch einfache Operationen so umzuformen, dass am Ende die Standardform resultiert: 

Methode

Umformung in Standardform:

  1. Ersetzen von $x_j$, welche keiner Nichtnegativitätsbedingung unterliegt, durch $x_j^+ \ge $ und $x_j^- \ge $, wobei gilt $x_j = x_j^+ - x_j^-$.

  2. Eine Gleichung $a_{i1}x_1 + ... + a_{in} x_n = b_i$ kann durch zwei Ungleichungen ersetzt werden
    $a_{i1}x_1 + ... + a_{in} x_n \le b_i$ und $-a_{i1}x_1 - ... - a_{in} x_n \le -b_i$.

  3. Aus einer $\ge$-Ungleichung wird eine $\le$-Ungleichung durch Multiplikation der gesamten Ungleichung mit $-1$.


Im Folgenden werden die einzelnen Schritte anhand eines Beispiels ausführlich aufgezeigt.

Anwendungsbeispiel: Umformung in Standardform

Beispiel

Gegeben sei das folgende lineare Optimierungsproblem:

$f(x_1, x_2) = 5x_1 + 10 x_2 $    $\rightarrow$  max!

u.d.N

$x_1 +  x_2 = 8$

$x_1 - 2 x_2 \le 4$

$x_1 \ge 0$

Geben Sie das lineare Optimierungsproblem in Standardform an!

Mittels der oben angegeben Operationen kann nun das lineare Optimierungsproblem in die Standardform überführt werden. 


1. Aus einer Gleichung zwei Ungleichungen machen (siehe Schritt 2):

$x_1 +  x_2 \le 8$

$-x_1 -  x_2 \le -8$

2. Die Gleichung $x_1 - 2 x_2 \le 4$ ist bereits in Standardform gegeben, bleibt also bestehen.

3. Für $x_2$ ist keine Nichtnegativitätsbedingung gegeben, d.h. es müssen zwei neue Variablen eingeführt werden (siehe Schritt 1):

$x_2^+ \ge 0$  und   $x_2^- \ge 0$


Für diese Variablen gilt:

$x_2 = x_2^+ - x_2^-$

Merke

Es ist natürlich auch möglich statt der Variablen $x_2^+$ und $x_2^-$ die Variablen $x_3$ und $x_4$ oder auch $x_2$ und $x_3$ einzuführen. Dann gilt:

$x_2 = x_3 - x_4$   bzw.  $x_2 = x_2 - x_3$

und wird dann eingesetzt. 

Es muss nun überall für $x_2 = x_2^+ - x_2^-$ eingesetzt werden:

$f(x_1, x_2) = 5x_1  + 10 x_2^+ - 10x_2^- $    $\rightarrow$  max!

u.d.N

$x_1 +  x_2^+ - x_2^- \le 8$

$-x_1 -  x_2^+ + x_2^- \le -8$

$x_1 - 2 x_2^+ + 2x_2^- \le 4$

$x_1, x_2^+, x_2^- \ge 0$

Die Standardform ist nun gegeben. Das grafische Lösungsverfahren kann hier nicht angewandt werden, weil statt zwei nun drei Entscheidungsvariablen gegeben sind.

Merke

Vorschau: Zur Lösung dieses Optimierungsproblems kann der duale Simplexalgoritmus oder die Big-M-Methode angewandt werden. Der primale Simplexalgorithmus kann hier nicht angewandt werden, da negative Werte auf der rechten Seite vorhanden sind. Die hier genannten Verfahren werden in den nachfolgenden Abschnitten ausführlich erläutert.

Video: Umformung in die Standardform (Maximierungsproblem)

In diesem Abschnitt wird gezeigt, wie man ein lineares Optimierungsproblem in die Standardform (Maximierungsproblem, Kleiner/gleich-Ungleichungen, Nichtnegativitäsbedingung) überführt.

Video: Umformung in die Standardform (Maximierungsproblem)

In diesem Abschnitt wird gezeigt, wie man ein lineares Optimierungsproblem in die Standardform (Maximierungsproblem, Kleiner/gleich-Ungleichungen, Nichtnegativitäsbedingung) überführt.
Multiple-Choice
Welche Gründe für die Abweichung von der Standardform existieren?
0/0
Lösen

Hinweis:

Bitte kreuzen Sie die richtigen Aussagen an. Es können auch mehrere Aussagen richtig oder alle falsch sein. Nur wenn alle richtigen Aussagen angekreuzt und alle falschen Aussagen nicht angekreuzt wurden, ist die Aufgabe erfolgreich gelöst.

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