Lineare Optimierung

Question 1

Was versteht man unter einem LP?

Answer 1

= Lineares Optimierungs- oder Programmierungsproblem

—> Maximierung oder Minimierung einer linearen Zielfunktion unter Beachtung von linearen Nebenbed./Restriktionen

Question 2

• beschreiben die Anzahl eines Optimierungsgegenstands (z.B. Endprodukte oder Konsumgüter)
• von Anfang an Teil der Zielfunktion und der Nebenbedingung

Was ist gemeint?

Answer 2

Strukturvariable

Question 3

• werden der allg. Form eines LPs bei der Transformation in die Standardform hinzugefügt
  —> jede NB bekommt eine eigene Schlupfvariable
• Hilfsvariablen: Geben an, wie viel Kapazität einer Nb nicht ausgeschöpft wird
• haben keinen Einfluss auf die Zielfunktion

Was gemeint?

Answer 3

Schlupfvariablen

Question 4

Was ist die Standardform?

Answer 4

• einheitliche Form von LP‘s
• notwendig für Anwendung von Lösungsalgorithmus (—> Simplex Algorithmus)
• jedes LP kann von der allg. Form in die Standardform transformiert werden

Question 5

Bei der Standardform muss die Optimierungsrichtung max sein!

Wahr/Falsch?

Answer 5

Wahr

—> Term umstellen falls min

Question 6

Nebenbedingungen müssen in der Standardform mit Gleichheit (=) erfüllt werden.

Wahr/Falsch?

Answer 6

Wahr

Question 7

Wann werden Schlupfvariablen eingesetzt?

Answer 7

Bei der Transformation von Ungleichheitsbedingungen in Gleichgewichtsbedingungen

(Bei aufstellen der Nb in Standardform)

Question 8

Bei der Standardform ist als Definitionsbereich nur die Nichtnegativitätsbedingung zulässig.

Wahr/Falsch?

Answer 8

Wahr

Question 9

Auf linker und rechter Seite von Gleichungen/Ungleichungen müssen Einheiten die selben sein.
(Zur Kontrolle)

(Nur lesen)

Answer 9

…

Question 10

Welche besonderen Fälle gibt es bei der Umwandlung in die Standardform? (3)

Answer 10

• „min ZF“ in eine „max ZF“ umwandeln
  Bsp.: min z = x1+x2
  —> max -z = -x1 - x2
  —> max -z + x1 +x2 = 0
• „=„-NB in Standardform umwandeln
  —> aus einer „=„-NB werden zunächst zwei neue NB (<= und >=), die wir dann noch umformen müssen
  —> umformen dann mit dem allg. Vorgehen zur Transformation von NB umformen ( umstellen zu <= -Nb und Schlupfvariabel)
• „x Element von R“ - Def.Bereich in Standardform umwandeln
  Bsp.: x3 Element von R
  —> x3‘ >= 0 und x3‘‘ >= 0
  —> Substituiere x3 mit x3‘ - x3‘‘
  —> funktioniert, weil jede reelle Zahl durch die Differenz von zwei positiven Zahlen dargestellt werden kann
  —> x3 kann in der Ausgangssituation(Element von R) auch einen neg. Wert haben
  —> einen neg. erzeugen wir mit zwei positiven Werten, indem wir so substituieren, dass x3‘‘ einen größeren Wert hat als x3‘
  —> somit erzeugen wir einen negativen Wert obwohl unser Definitionsbereich >= 0 ist!

Question 11

Eine endliche Anzahl größer 1 an optimalen Basislösungen kann existieren.

Wahr/Falsch?

Answer 11

FALSCH

—> kann NCHT existieren!

Question 12

Es ist möglich, dass keine optimale Basislösung gefunden werden kann.

Wahr/Falsch?

Answer 12

Wahr

Question 13

Wann erhalten wir unendlich viele optimale Basislösungen?

Answer 13

Wenn die Zielfunktion auf dem Lösungsraum im Optimum in mehr als einem Punkt aufliegt.

Question 14

Wie nennt man die Eckpunkte des Lösungsraums?

Answer 14

zulässige Basislösung

—> bilden die Menge der Kandidaten für die optimale Basislösung

Question 15

Was versteht man unter dem Primalproblem?

Answer 15

Ausgangsproblem (LP), wird aus dem Zusammenhang direkt abgelesen

Question 16

Was versteht man unter dem Dualproblem?

Answer 16

Umgewandeltes Ausgangsproblem

—> duale und Primate Probleme stehen in einem Verhältnis zueinander und können unter Anwendung bestimmter Regeln ineinander umgewandelt werden

Question 17

1) Für was eignet sich der Primale Simplex?
2) Was ist die Voraussetzung dafür?
3) Was ist sein Ergebnis?

Answer 17

1) Lösungsverfahren / Optimierungsverfahren für LP
2) Voraussetzung: eine zulässige Basislösung ist bekannt
3) Ergebnis: ein optimales Ergebnis (sofern dieses existiert)

Question 18

Was bewirkt der Duale Simplex?

Answer 18

Findet eine beliebige zulässige Basislösung

Question 19

Erkläre die 2-Phasen-Methode: ??

Answer 19

1.Phase:
Eine zulässige Basislösung wird durch den Dualen Simplex gefunden.

2.Phase:
Durch die anschließende Verwendung des Primalen Simplex kann die optimale Lösung ermittelt werden

Question 20

Was liegt vor, wenn im Optimaltableau ein Eintrag der rechten Seite(bi) den Wert 0 erhält.

Answer 20

Primale Degeneration

besondere Form der Redundanz

Question 21

Was liegt vor, wenn im Optimaltableau ein Zielfunktionskoeffizient für eine Nicht-Basis-Variable den Wert 0 erhält?

Answer 21

Duale Degeneration

Question 22

Stellen sie die Beziehungen zwischen primalem und dualem Problem durch gerichtete Pfeile dar?

Schema: 
Primales Problem...(links)
Duales Problem...(rechts) 
\_\_\_\_\_\_\_
...besitzt eine optimale Basislösung     

…besitzt eine optimale Basislösung
_______
…hat keine zulässige Lösung

…ist unbeschränkt
_______
…ist unbeschränkt

…hat keine zulässige Lösung
_______
…hat keine zulässige Lösung

…ist unbeschränkt oder hat keine zulässige Lösung
_______
…ist unbeschränkt oder hat keine zulässige Lösung

…hat keine zulässige Lösung
_______

Answer 22

...besitzt eine optimale Basislösung     
<=>
...besitzt eine optimale Basislösung 
\_\_\_\_\_\_\_
...hat keine zulässige Lösung 

…hat keine zulässige Lösung
_______
…hat keine zulässige Lösung
—>
…ist unbeschränkt oder hat keine zulässige Lösung
_______
…ist unbeschränkt oder hat keine zulässige Lösung