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 > Sonderfälle bei Optimierungsmodellen:

Beispiel: Minimierungsproblem ohne optimal Lösung

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 wird ein Minimierungsproblem aufgezeigt, für welches zwar eine zulässige, jedoch keine optimale Lösung voliegt.

Gegeben sei das folgende Minimierungsproblem:

$f(x_1, x_2, x_3) = 5x_1 + 8x_2 - x_3$   $\rightarrow$  min!

u.d.N.

$4x_1 + 2x_2 + x_3 \ge 30$

$6x_1 + 4x_2 + x_3 \ge 40$

$           x_2           \ge 12$

$x_1, x_2, x_3$

Beispiel

Das Problem soll mit und ohne Dualisierung gelöst werden.

Lösung ohne Dualsierung

Das Problem wird mittels der Umformungsregeln in ein duales Maximierungsproblem umgeformt. Dabei muss das Minimierungsproblem die folgende Form aufweisen (Größer/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung). Da dies bereits der Fall ist, können als nächstes die Umformungsregeln angewandt werden:

$f(x_1, x_2, x_3) = -5x_1 - 8x_2 + x_3$   $\rightarrow$  max!

u.d.N.

$-4x_1 - 2x_2 - x_3 \le -30$

$-6x_1 - 4x_2 - x_3 \le -40$

$           -x_2         \le -12$

$x_1, x_2, x_3$

Es liegen negative Werte auf der rechten Seite vor. Es wird der duale Simplexalgorithmus (alternativ: Big-M-Methode) angewandt. Das Problem wird in die Normalform überführt:

$f(x_1, x_2, x_3) = -5x_1 - 8x_2 + x_3$   $\rightarrow$  max!

u.d.N.

$-4x_1 - 2x_2 - x_3  + x_4                      = -30$

$-6x_1 - 4x_2 - x_3           + x_5             = -40$

$           -x_2                             + x_6   = -12$

$x_1, x_2, x_3$

Das Problem wird als nächstes in das Ausgangstableau eingetragen und der duale Simplexalgorithmus angewandt. Nach 3. Iterationsschritten, ist die zulässige Basislösung erreicht (alle Werte der rechten Seite sind positiv):

Minimierungsproblem - dualer Simplex

Um eine optimale Lösung zu erhalten, muss als nächstes der primale Simplexalgorithmus angewandt werden. Hier muss zunächst die Pivotspalte (kleinster negativer Wert) ausgewählt werden. Diese liegt bei $-1$. Die Pivtozeile wird dann ausgewählt, indem die Werte der rechten Seite durch die Werte der Pivotspalte geteilt werden, wobei die Werte der Pivotspalte größer als Null sein müssen. Dies ist hier nicht gegeben. Demnach existiert zwar eine zulässige Basislösung, jedoch keine optimale Lösung. Das Verfahren wird hier abgebrochen (siehe Abschnitt: Sonderfälle bei Optimierungsmodellen). 

Vorgehen mit Dualsisierung

Die Dualsierung muss hier nicht weiter betrachtet werden, denn für das duale Problem existiert keine zulässige Basislösung (siehe Abschnitt Sonderfälle bei Optimierungsmodellen). 

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