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 > Sensitivitätsanalyse:

Änderung der Zielfunktionskoeffizienten

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 wird mittels Sensitivitätsanalyse gezeigt, in welchem Bereich die Zielfunktionswerte variiert werden können, ohne dass die Optimallösung des Optimierungsproblems ihre Optimalitätseigenschaft verliert, d.h. ohne dass ein zusätzlicher Basisaustausch bzw. Simplexschritt notwendig wird. Das bedeutet also, dass das Optimaltableau in der Form bestehen bleibt (Basisvariablen, Werte), wenn die Koeffizienten Zielfunktion in einem bestimmten Bereich variiert werden. Dabei gilt der Schwankungsbereich der Zielfunktionswerte nur für das Ausgangstableau. Werden also im Ausgangstableau die Zielfunktionswerte in einem bestimmten Bereich variiert (immer ein Zielfunktionswert, wobei die anderen konstant gehalten werden), so ergibt sich das gleiche Optimaltableau, wie ohne Variation der Werte. 

Merke

Für die Sensitivitätsanalyse müssen immer Ausgangstableau und Optimaltableau gegeben sein. Sollte nur das Ausgangstableau gegeben sein, so muss das Optimaltableau noch mittels Simplex bestimmt werden.

Vorgehensweise: Schwankungsbereich Zielfunktionskoeffizienten

1. Es wird zunächst das Ausgangstableau betrachtet:

Ausgangstableau Sensitivitätsanalyse
Ausgangstableau

Die Zielfunktionskoeffizienten im Ausgangstableau $c_j$ werden wie folgt definiert:

$c_1 = -400$   

$c_2 = 780$     

$c_3 = 1.250$.

Merke

Nicht vergessen. Die Zielfunktionswerte sind im Ausgangstableau mit ihren umgekehrten Vorzeichen eingetragen.

Die zu den Zielfunktionskoeffizienten zugehörigen Variablen $x_j$ sind:

$x_1$ für $c_1$,

$x_2$ für $c_2$,

$x_3$ für $c_3$.

2. Danach wird das Optimaltableau herangezogen:

Endtableau Sensitivitätsanalyse
Optimaltableau

Es wird nun geschaut, wo sich die im Ausgangstableau befindlichen Nichtbasisvariablen im Optimaltableau befinden. Im Ausgangstableau sind die Nichtbasisvariablen $x_1$, $x_2$ und $x_3$. Im Optimaltableau stellen $x_1$ und $x_3$ Basisvariablen dar, $x_2$ hingegen ist Nichtbasisvariable. Es muss nun bei der Berechnung der unterschieden werden zwischen Basisvariablen und Nichtbasisvariablen:

Basisvariablen

Ist die im Ausgangstableau befindliche Nichtbasisvariable im Optimaltableau eine Basisvariable, so muss folgende Berechnung durchgeführt werden:

Methode

$c_j^- := \{ min \{\frac{c_j^*}{a_{ij}^*} \} \; \text{mit} \; a_{ij}^* > 0 \; \text{sonst} \; \infty \}$

$c_j^+ := \{ min \{-\frac{c_j^*}{a_{ij}^*} \} \; \text{mit} \; a_{ij}^* < 0 \; \text{sonst} \; \infty \}$

mit

$c_j^*$ Zielfunktionskoeffizient im Optimaltableau

$a_{ij}^* $ Koeffizient der Zeile, wo sich $x_j$ befindet (Optimaltableau)

Nichtbasisvariablen

Ist die im Ausgangstableau befindliche Nichtbasisvariable im Optimaltableau ebenfalls eine Nichtbasisvariable, so muss folgende Berechnung durchgeführt werden:

Methode

$c_j^- = \infty$

$c_j^+ = c_j^*$

Schwankungsbereich der Zielfunktionskoeffizienten

Den Schwankungsbereich ermittelt man dann mittels folgendem Intervall:

Methode

$[c_j - c_j^- \; , \; c_j + c_j^+]$                     Intervall: Zielfunktionskoeffizienten $c_j$

Vorgehensweise

Die genaue Vorgehensweise wird im Weiteren ausführlich behandelt. Dazu sei das obige Ausgangs- und Optimaltableau gegeben.

1. Zunächst sind die Nichtbasisvariablen aus dem Ausgangstableau und die dazugehörigen Zielfunktionskoeffizienten zu bestimmen:

$c_1 = -400$   für $x_1$

$c_2 = 780$    für $x_2$

$c_3 = 1.250$   für $x_3$.

2. Danach wird geschaut wo sich die Variablen im Optimaltableau befinden. $x_1$ und $x_3$ sind Basisvariablen, $x_2$ ist eine Nichtbasisvariable. Es werden zunächst die Basisvariablen betrachtet.

  • $x_1$ = Basisvariable:

Die Berechnung wird anhand der beiden obigen Formeln durchgeführt

Methode

$c_j^- := \{ min \{\frac{c_j^*}{a_{ij}} \}^* \; \text{mit} \; a_{ij}^* > 0 \; , \; \text{sonst} \; \infty \}$

Es wird zunächst der Wert $c_1^-$ berechnet. Hierfür werden alle Koeffizienten im Optimaltableau betrachtet, die sich in der Zeile von $x_1$ befinden und größer als Null sind. Die dazugehörigen Zielfunktionswerte stehen dann unter diesen Koeffizienten. Größer als Null sind die Koeffizienten: $a_{31}^* = \frac{1}{10}$ mit $c_1^* = 10$ und $a_{32}^* = \frac{1}{2}$ mit $c_2^* = 20$. Existieren keine Werte größer als Null, so nimm $c_1^-$ den Wert $\infty$ an. Einsetzen in die Formel ergibt:

$c_1^- := min \{ \frac{10}{\frac{1}{10}} ; \frac{20}{\frac{1}{2}} \} = 40$

Danach wird $c_1^+$ berechnet.

Methode

$c_j^+ := \{ min \{-\frac{c_j^*}{a_{ij}^*} \} \; \text{mit} \; a_{ij}^* < 0 \; \text{sonst} \; \infty \}$

Hierfür werden alle Koeffizienten im Optimaltableau betrachtet, die sich in der Zeile von $x_1$ bfinden und kleiner als Null sind. Existieren keine Werte kleiner als Null, so nimmt $c_1^+$ den Wert $\infty$ an. Es existieren aber Werte kleiner als Null, und zwar $a_{33}^* = -\frac{1}{50}$ mit $c_3^* = 48$:

$c_1^+ := min \{ -\frac{48}{-\frac{1}{50}} \} = 2.400$

Der Schwankungsbereich wird ermittelt mit dem Intervall:

$[c_j - c_k^- \; , \; c_j + c_k^+]$      

mit  $c_j = c_1 = -400$ (Zielfunktionswert im Ausgangstableau für $x_1$)

Es ergibt sich ein Schwankungsbereich für $c_1 $ von:

$[-400 - 40; -400 + 2.400]$

Methode

$[-440; 2.000] \in c_1$

Der Zielfunktionswert $c_1$ darf im Ausgangstableau die Werte von -440 bis 2.000 annehmen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

  • $x_3$ = Basisvariable:

$c_3^- := min \{ \frac{10}{\frac{1}{25}} ; \frac{20}{\frac{4}{5}} ; \frac{48}{\frac{8}{250}} \} = 25$

$c_3^+ := \infty$   (Es existieren keine negativen Koeffizienten im Optimaltableau)

Der Schwankungsbereich liegt demach für $c_3$ bei:

$[1.250 - 25; 1.250 + \infty]$

Methode

$[1.225 ;  \infty] \in c_3$

Der Zielfunktionswert $c_3$ darf im Ausgangstableau die Werte ab 1.225 annehmen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

  • $x_2$ = Nichtbasisvariable:

$x_2$ stellt im Optimaltableau eine Nichtbasisvariable dar. Die Berechnung erfolgt zu:

$c_2^- = \infty$

$c_2^+ = c_2^* = 20$  $c_2^+$ nimmt den Wert an, den $c_2^*$ im Optimaltableau als Zielfunktionswert besitzt.

Der Schwankungsbereich ergibt sich zu:

$[780 - \infty; 780 + 20]$

Methode

$[-\infty ; 800] \in c_2$

Der Zielfunktionswert $c_2$ darf im Ausgangstableau die Werte bis 800 annehmen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

  • $x_4$: Schlupfvariable

Ist in dem Optimaltableau eine Schlupfvariable in der Basis gegeben, so kann man auf für diese die obigen Berechnungen anführen und einen Schwankungsbereich ermitteln:

$c_1^- := min \{ \frac{20}{10} \} = 2$

$c_1^+ := min \{ -\frac{10}{-4} \} = 2,5$

Der Schwankungsbereich ergibt sich zu (bei Schlupfvariablen ist der Zielfunktionswert $c_j$ immer Null):

$[0 - 2; 0 + 2,5]$

Methode

$[-2 ; 2,5] \in c_4$

Eine Schlupfvariable besitzt immer den Zielfunktionswert Null. Befindet sich eine Schlupfvariable im Optimaltableau aber in der Basis, so besitzt diese auch einen Schwankungsbereich. Die Schulpfvariable $x_4$ kann demnach in die Zielfunktion mit den Werten zwischen -2 und 2,5 eingehen, ohne dass die Basislösung die Optimalitätseigenschaft verliert, d.h. also ohne dass ein Basistausch erforderlich wird.

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