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 > Minimierungsproblem:

Zusammenfassung: Minimierungsproblem

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]

In diesem Abschnitt soll nochmals zusammegefasst werden, wie eine optimale Lösung mittels der unterschiedlichen Simplexverfahren gewonnen werden kann, wenn ein Minimierungsproblem gegeben ist. 

Wichtig

Liegt ein Minimierungsproblem vor, so kann dieses entweder in ein Maximierungsproblem dualisiert werden oder mittels Umformungsregeln in ein Maximierungsproblem ungeformt werden. 

Vorgehen ohne Dualisierung

1. Wird das Minimierungsproblem nicht dualisiert, so muss dieses mittels der Umformungsregeln in die Standardform überführt (Maximierungsproblem, Kleiner/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung. Die Umformungsregeln lauten:

  • Aus einem Minimierungsproblem wird ein Maximierungsproblem, indem die Zielfunktion mit $-1$ multipliziert wird.

  • 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^-$.

  • 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 = b_i$ und $-a_{i1}x_1 - ... - a_{in} x_n = -b_i$.

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

2. Das Maximierungsproblem wird dann in die Normalform überführt -> Einfügen von Schlupfvariablen zur Erreichung von Gleichheitsbedingungen. Die Schlupfvariablen gehen mit dem Wert Null in die Zielfunktion ein und können demnach in dieser unberücksichtigt bleiben.

  • Sind die Werte der rechten Seite alle positiv, wird der primale Simplexalgorithmus angewandt. Hier wird zunächst die Pivotspalte und dann die Pivotzeile ausgewählt. Danach erfolgt der Simplexschritt. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 

  • Sind Werte der rechten Seite negativ, wird der duale Simplexalgoithmus oder die Big-M-Methode angewandt. 

    Beim dualen Simplexalgorithmus wird zunächst die Pivotzeile und dann die Pivotspalte gewählt. Es erfolgt der Simplexschritt. Erst wenn alle Werte der rechten Seite positiv sind liegt eine zulässige Basislösung vor. Liegen dann noch negative Werte in der Zielfunktionszeile vor, muss der primale Simplexalgorithmus angewandt werden um die Optimallösung zu erhalten. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 

    Bei der Big-M-Methode wird jede Gleichheitsbedingung, die negative Werte aufweist, mit $-1$ multipliziert. Dort wo sich dann negative Schlupfvariablen ergeben, wird jeweils eine künstliche Variable $y_i$ eingefügt. Diese wird in der Zielfunktion mit $-M$ bewertet, wobei $M$ als hinreichend groß angenommen wird. Die künstlichen Variablen müssen dann aus der Zielfunktion entfernt werden, indem die Nebenbedingungen nach diesen aufgelöst und in die Zielfunktion eingesetzt werden. Danach wird der primale Simplexalgorithmus angewandt. Für die Pivotspalte wird sich dabei in der Zielfunktionszeile an $M$ orientiert, da diese als hinreichend groß angenommen werden. Sind keine negativen Werte in der Zielfunkktion erhalten liegt die optimale Lösung vor.

Vorgehen bei Dualisierung

1. Wird das Minimierungsproblem dualisiert, so muss dieses zunächst in die folgende Form überführt werden: Minimierungsproblem, Größer/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung. Danach wird die Dualsierung vorgenommen. Es liegt dann ein duales Maximierungsproblem vor. 

2. Das duale Maximierungsproblem wird dann in die Normalform überführt -> Einfügen von Schlupfvariablen zur Erreichung von Gleichheitsbedingungen. Die Schlupfvariablen gehen mit dem Wert Null in die Zielfunktion ein und können demnach in dieser unberücksichtigt bleiben.

  • Sind die Werte der rechten Seite alle positiv, wird der primale Simplexalgorithmus angewandt. Hier wird zunächst die Pivotspalte und dann die Pivotzeile ausgewählt. Danach erfolgt der Simplexschritt. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 

  • Sind Werte der rechten Seite negativ, wird der duale Simplexalgoithmus oder die Big-M-Methode angewandt. 

    Beim dualen Simplexalgorithmus wird zunächst die Pivotzeile und dann die Pivotspalte gewählt. Es erfolgt der Simplexschritt. Erst wenn alle Werte der rechten Seite positiv sind liegt eine zulässige Basislösung vor. Liegen dann noch negative Werte in der Zielfunktionszeile vor, muss der primale Simplexalgorithmus angewandt werden um die Optimallösung zu erhalten. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 

    Bei der Big-M-Methode wird jede Gleichheitsbedingung, die negative Werte aufweist, mit $-1$ multipliziert. Dort wo sich dann negative Schlupfvariablen ergeben, wird jeweils eine künstliche Variable $y_i$ eingefügt. Diese wird in der Zielfunktion mit $-M$ bewertet, wobei $M$ als hinreichend groß angenommen wird. Die künstlichen Variablen müssen dann aus der Zielfunktion entfernt werden, indem die Nebenbedingungen nach diesen aufgelöst und in die Zielfunktion eingesetzt werden. Danach wird der primale Simplexalgorithmus angewandt. Für die Pivotspalte wird sich dabei in der Zielfunktionszeile an $M$ orientiert, da diese als hinreichend groß angenommen werden. Sind keine negativen Werte in der Zielfunkktion erhalten liegt die optimale Lösung vor.

3. Die Lösung wird in diesem Fall im Optimaltableau nicht auf der rechten Seite abgelesen (wie ohne Dualsierung), sondern bei den Zielfunktionswerten. 

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