Einführung in LP, Modellbildung, Graphische Lösung, Primaler Simplex, Dualer Simplex, ökonomische Interpretation

Question 1

LP-Umformung

Gib die Umformung eines Minimierungsproblems in ein Maximierungsproblem an.

Answer 1

vgl. Folie 76

Question 2

Wie wird die Standardform noch genannt?

Answer 2

Kanonische Form

Question 3

Wahr oder falsch?

In der Standardform kann der Koeffizient des Schlupf in der ZF jede reelle Zahl annehmen.

Answer 3

Falsch!

Die Koeffizienten der Schlupfvariablen sind in der ZF immer gleich 0 (vgl. Folie 86).

Question 4

Gib die allgemeine Form eines LPs in Matrizenschreibweise wieder.

Answer 4

vgl. Folie 88

Question 5

Definition: Konvexität von Mengen

Answer 5

vgl. Folie 89

Question 6

Definition: Konvexe Linearkombination/Echte Linearkombination

Answer 6

vgl. Folie 90

Question 7

Definition: Konvexe Polyeder

Answer 7

Die Menge aller konvexen Linearkombinationen endlich vieler Punkte wird auch das von diesen Punkten aufgespannte konvexe Polyeder genannt.

Question 8

Definition: Eckpunkt

Answer 8

Ein Punkt y heißt Eckpunkt einer konvexen Menge K, wenn er sich nicht als echte Linearkombination zweier verschiedener Punkte in K darstellen lässt.

Question 9

Satz: Schnittmenge konvexer Mengen

Answer 9

Seinen K1, …, Kr konvexe Mengen mit endlich vielen Eckpunkten. Dann ist auch die Menge K1 (schnitt) … (schnitt) Kr konvex mit endlich vielen Eckpunkten.

Question 10

Wahr oder falsch?

Der zulässige Bereich eines LP ist stets konvex.

Answer 10

Wahr!

Für jede einzelne NB gilt, dass die Menge der für das Problem zulässigen Punkte konvex ist. Der zulässige Bereich wird aus der Schnittmenge all dieser Mengen gebildet.

Question 11

Definition: Konvexität von Funktionen

Answer 11

vgl. Folie 92

Question 12

Wahr oder falsch?

Eine nach unten geöffnete Parabel ist konvex.

Answer 12

Falsch!

Eine nach oben geöffnete Parabel ist konvex.

(Merksatz: Wenn die Gerade zwischen zwei beliebigen Punkten auf der Funktion auf oder oberhalb der Funktion liegt, dann ist die Funktion konvex. vgl. Folie 92)

Question 13

Wahr oder falsch?

Eine Funktion ist konvex, wenn ihre Hessematrix positiv-semi-definit ist.

Answer 13

Wahr!

Question 14

Satz: Konvexität des zulässigen Bereichs

Answer 14

Der zulässige Bereich eines LP ist konvex mit endlich vielen Eckpunkten. (Dies kann auch bedeuten, dass der Bereich leer oder unbeschränkt ist).

Question 15

Satz: Maximum einer linearen Funktion über einer konvexen Menge

Answer 15

Sei z eine lineare Funktion, definiert über einer nicht leeren konvexen Menge mit endlich vielen Eckpunkten. Dann gilt: Wenn z nach oben beschränkt ist, so nimmt z das Maximum an mindestens einem der Eckpunkte an. Ist der zulässige Bereich eines LP unbeschränkt, so gibt es folgende Fälle:

• ZF kann unbeschränkt wachsen
• ZF ist beschränkt, nimmt Optimum in einer Ecke an

Question 16

Wie viele Lösungen kann ein LP haben?

Answer 16

0, 1, unendlich

Question 17

Definition: Aktive/Passive NB

Answer 17

Eine NB heißt in einer Basislösung bindend/aktiv, wenn die dazugehörige Schlupfvariable den Wert Null annimmt. Eine NB, die in der Basislösung keine Einschränkung darstellt, ist nicht bindend/passiv.

Question 18

Definition: Zulässige Basislösung

Answer 18

“Kandidaten” für optimale Lösungen sind die Eckpunkte des Lösungsraums. Sie werden zulässige Basislösungen genannt.

Question 19

Nenne die Voraussetzungen für die Anwendung des primalen Simplex.

Answer 19

• Starttableau
• Zulässige Basislösung
• Nicht-Negativitäts-Bedingung

Question 20

Wahr oder falsch?

Wenn in der ZF-Zeile im Tableau des primalen Simplex ganz links -z steht, dann ist der primale Simplex beendet sobald alle Werte der ZF-Zeile negativ sind.

Answer 20

Falsch!

(Merke: Egal ob in der ZF-Zeile ganz links -z oder z steht, der primale Simplex wird beendet sobald alle Werte in der ZF-Zeile positiv sind.)

Question 21

Nenne die Voraussetzungen für die Anwendung des dualen Simplex.

Answer 21

• Starttableau

- Keine zulässige Basislösung (negatives bi)

Question 22

Was versteht man unter Substitutionskoeffizienten?

Answer 22

Sie geben an, um wieviele Einheiten sich jede BV zur Zeile i erhöht (aij < 0) bzw. erniedrigt (aij > 0), wenn man die NBV zur Spalte j um eine Einheit erhöht (Gleiches gilt auch für den ZF-Wert).

vgl. Folie 145

Question 23

Was versteht man unter Schattenpreisen/Opportunitätskosten?

Answer 23

Kostenmäßige Werte jeder Einheit der Mindestanforderungen: Erhöht (senkt) man eine Anforderung (bi-Wert) um eine Einheit, verschlechtert (verbessert) sich der ZF-Wert um den angegebenen Wert.

vgl. Folie 146

Question 24

Wahr oder falsch?

Bei der 2-Phasen Methode wendet man erst den dualen Simplex an, um eine zulässige Basislösung zu finden, und danach den primalen Simplex, um eine optimale Basislösung zu finden.

Answer 24

Wahr!

Question 25

Wahr oder falsch?

In einem LP steht s. t. für “Subject to”.

Answer 25

Wahr!

Question 26

Wie formt man eine Gleichheitsbedingung in einem LP von der allgemeinen Form in die Standardform um?

Answer 26

Die Gleichheitsbedingung wird zunächst in zwei Ungleichheitsbedingungen (<= und >=) umgeformt und dann mit den bekannten Regeln in die Standardform überführt.

Question 27

Wie formt man ein xj (Element) R in einem LP von der allgemeinen Form in die Standardform um?

Answer 27

vgl. Folie 83

Question 28

Wahr oder falsch?

Die Vereinigung zweier konvexer Mengen ist konvex.

Answer 28

Falsch!

vgl. Nr. 2.4 b)

Question 29

Warum ist Konvexität für die Optimierung von LPs wichtig?

Answer 29

Weil wir ansonsten nicht sagen können, ob ein gefundenes lokales Optimum auch ein globales Optimum ist.

Question 30

Wahr oder falsch?

Der Simplex-Algorithmus in Gleichungsschreibweise ist beendet, wenn alle ZF-Koeffizienten kleiner als null sind. Dies gilt sowohl bei z als auch bei -z.

Answer 30

Wahr!

Beim Simplex-Algorithmus in Tableauschreibweise ist es genau anders herum.

Question 31

Wahr oder falsch?

Der Simplex Algorithmus kann nur auf konvexen Mengen angewendet werden.

Answer 31

Wahr!