Sensitivitätsanalyse, Sonderfälle, Multikriterielle Optimierung Flashcards
LP - Sonderfälle: Unbeschränktheit
Zeichne ein Bsp.
Wie erkennbar?
Wann erkennbar?
Gib die wichtigen Anmerkungen wieder.
vgl. Aufzeichnungen
LP - Sonderfälle: Unzulässigkeit
Zeichne ein Bsp.
Wie erkennbar?
Wann erkennbar?
Gib die wichtigen Anmerkungen wieder.
vgl. Aufzeichnungen
LP - Sonderfälle: Redundanz
Zeichne ein Bsp.
Wie erkennbar?
Wann erkennbar?
Gib die wichtigen Anmerkungen wieder.
vgl. Aufzeichnungen
LP - Sonderfälle: Primale Degeneration
Zeichne ein Bsp.
Wie erkennbar?
Wann erkennbar?
Gib die wichtigen Anmerkungen wieder.
vgl. Aufzeichnungen
n = Anzahl der Strukturvariablen
LP - Sonderfälle: Duale Degeneration
Zeichne ein Bsp.
Wie erkennbar?
Wann erkennbar?
Gib die wichtigen Anmerkungen wieder.
vgl. Aufzeichnungen
Definition: Sensitivitätsanalyse
Das Testen einer optimalen Lösung eines linearen Programms bzgl. einer Veränderung der Eingabedaten bezeichnet man als Sensitivitäts- oder Sensibilitätsanalyse.
Was versteht man unter einer qualitativen Änderung im Zusammenhang mit der Sensitivitätsanalyse?
Eine qualitative Änderung liegt dann vor, wenn sich die Struktur von BV und NBV ändert, d. h. eine bisherige NBV BV wird und umgekehrt.
Innerhalb (Außerhalb) der durch die Sensitivitätsanalyse bestimmten Intervalle ist eine Änderung quantitativ (qualitativ).
Sensitivitätsanalyse: Änderung der ZF-Koeffizienten
In welchem Bereich/Intervall kann der ZF-Koeffizient ck der Variable xk variieren, ohne dass die optimale Basislösung ihre Optimalität verliert, d. h. ein Basistausch notwendig wird?
[ck - ck-, ck + ck+]
Sensitivitätsanalyse: Änderung von Ressourcenbeschränkungen
In welchem Bereich/Intervall kann die rechte Seite bk der k-ten NB variieren, ohne dass die optimale Basislösung ihre Optimalität verliert, d. h. ein Basistausch notwendig wird?
[bk - bk-, bk + bk+]
Wahr oder falsch?
Primale und duale Degeneration können gleichzeitig auftreten.
Wahr!
Bsp.: S. 19; Nr. 2.30
Wahr oder falsch?
Wenn primale und duale Degeneration gleichzeitig auftreten, kann die ZF parallel zur redundanten NB liegen.
Falsch!
Bei gleichzeitigem Vorliegen von primaler und dualer Degeneration ist zu beachten, dass die Zielfunktion nicht parallel zu der redundanten NB sein darf, da dann nur ein optimaler Punkt vorliegen würde, und damit das Problem nicht dual degeneriert wäre
(vgl. Bsp.: S. 19; Nr. 2.30)
Wahr oder falsch?
Wenn duale Degeneration vorliegt gibt es mehrere optimale Basislösungen, aber mit dem gleichen optimalen ZF-Wert.
Wahr!
Multikriterielle Optimierung - In welchem Zusammenhang können verschiedene Ziele zueinander sein?
komplementär
konkurrierend/konträr
neutral
Definition: Zielerreichnungsgrad
Sei zi* der optimale ZF-Wert eines zu maximierenden Ziels i und zi(x) der ZF-Wert einer Lösung x, dann heißt der Quotient (zi-zi(x))/zi der mit x zu realisierende Zielerreichnungsgrad (ZEG).
Definition: Perfekte Lösung
Eine zu jeder Zielsetzung optimalen Lösung eines multikriteriellen Optimierungsproblems heißt perfekte Lösung des Problems.
Welche Ansätze für die Lösung von Zielkonflikten bei multikriterieller Optimierung kennst du?
Lexikographische Ordnung von Zielen
Zieldominanz
Zielgewichtung
Berücksichtigung von Abstandsfunktionen
Beschreibe das Vorgehen bei Lexikographischer Ordnung von Zielen
Ziele werden nach Wichtigkeit sortiert
1) Löse das Problem ausschließlich bezüglich des wichtigsten Ziels.
2) Löse das Problem ausschließlich bezüglich des zweit wichtigsten Ziels, wobei nur die Menge der optimalen Lösungen aus Schritt 1) der zulässige Bereich ist.
3) Löse das Problem ausschließlich bezüglich des dritt wichtigsten Ziels, wobei nur die Menge der optimalen Lösungen aus Schritt 2) der zulässige Bereich ist.
…
Wahr oder falsch?
Lexikographische Ordnung - “Untergeordnete” Ziele werden nur dann berücksichtigt, wenn für “übergeordnete” Ziele parametrische Lösungen vorliegen.
Wahr!
Beschreibe das Vorgehen bei Zieldominanz
Eines der Ziele wird als Hauptziel deklariert und als ZF berücksichtigt.
Alle anderen Ziele werden zu Nebenziele erklärt und als NB in das Problem aufgenommen:
- Für zu maximierende ZF: F(x) >= u
- Für zu minimierende ZF: F(x) <= o
Welche Probleme können bei Zieldominanz auftreten?
Durch hinzukommende untere (bzw. obere) Schranken der Nebenziele wird der ZEG des Hauptziels möglicherweise zu sehr beschnitten.
Weiterhin ist es möglich, dass durch diese Schranken die Menge der zulässigen Lösungen sogar zur leeren Menge wird.
Beschreibe das Vorgehen bei Zielgewichtung
- Die einzelnen Ziele werden mit l1, … lt bewertet.
- Dabei gilt 0<= lt <= 1 und l1 + … + lt = 1.
- Die neue ZF lautet: zl = l1z1 + … + ltzt
Wahr oder falsch?
Multikriterielle Optimierung - Bei der Methode der Zielgewichtung ist es möglich das der neue ZF-Wert zl keine Aussage mehr hat.
Wahr!
Beschreibe das Vorgehen bei Berücksichtigung von Abstandsfunktionen.
- Zunächst wird für jedes Ziel gesondert der optimale ZF-Wert zi* berechnet
- Danach wird eine Lösung des gesamten Problems gesucht, welche den “Abstand” zwischen den zi* und den durch x gegebenen ZF-Werten minimiert
- Die einzelnen Abstände können je nach Bedeutung der einzelnen Ziele gewichtet werden (s. Zielgewichtung, gleiche Regeln)
In OR1 gilt: Annahme einer linearen Funktion: min zA = lambda1(z1* - z1) + … + lambda2(zt* - zt)
(vgl. Folie 241)
Wahr oder falsch?
Für p = 1 entspricht das Vorgehen bei Berücksichtigung von Abstandsfunktion dem Vorgehen der Zieldominanz.
Falsch!
Für p = 1 entspricht das Vorgehen bei Berücksichtigung von Abstandsfunktion dem Vorgehen der Zielgewichtung.
Zeichne den Sonderfall, in dem primale und duale Degeneration gleichzeitig auftreten.
vgl. Aufzeichnungen
Welche Annahmen müssen bei der Sensitivitätsanalyse getroffen werden?
Lineare Problem
Maximierung
Keine Degeneration
Sensitivitätsanalyse: ZF-Koeffizient ck
Wie erhält man ck- und ck+ bei einer NBV?
ck (NBV)
ck- = unendlich
ck+ = ck*
Sensitivitätsanalyse: ZF-Koeffizient ck
Wie erhält man ck- und ck+ bei einer BV?
ck (BV)
ck-: Sind alle akj* mit (j=!k) neg. (<= 0)?
Ja: ck- = unendlich
Nein: ck- = min (cj/akj) mit (j=!k) für pos. akj*
ck+: Sind alle akj* mit (j=!k) pos. (>= 0)?
Ja: ck+ = unendlich
Nein: min (-cj/akj) mit (j=!k) für neg. akj*
Sensitivitätsanalyse: Ressourcenbeschränkung bk
Wie erhält man bk- und bk+ bei einer NBV als Schlupf?
bk (NBV)
bk-: Sind alle aiq* neg. (<=0)?
Ja: bk- = unendlich
Nein: bk- = min (bi/aiq) für pos. aiq*
bk+: Sind alle aiq* pos. (>=0)?
Ja: bk+ = unendlich
Nein: bk+ = min (-bi/aiq) für neg. aiq*
Sensitivitätsanalyse: Ressourcenbeschränkung bk
Wie erhält man bk- und bk+ bei einer BV als Schlupf?
bk (BV)
bk- = xq bk+ = unendlich
