Lineare Programme

Question 1

kanonische Form LP

Answer 1

max c^T*x
Ax ≤ b
x ≥ 0

x: Entscheidungsvariable
A: Koeffizientenmatrix
b: rechte Seite
c^T: Zielfunktionskoeffizient

-> jedes LP kann in diese Form gebracht werden

Question 2

Gurobi Programm Grundstruktur

Answer 2

from gurobipy import *
 def solve (...):
   model = Model ( "Modellname" )
   model.modelSense = GRB.MINIMIZE
  # Variablen erzeugen :
   xKaufen = {}
     for speise in speisen :
       xKaufen [ speise ] = model . addVar ( obj = kosten [ speise ] , name = ( ’ x_ ’ + speise ))
   model.update()
   model.addConstr(#nebenbedingungen)
   model.optimize()
   return model

Question 3

Gurobi Variable definieren

Answer 3

xKaufen [ speise ] = model.addVar ( obj = kosten [ speise ] , name = ( ’ x_ ’ + speise ))

lb: untere Schranke der Variable, Standard: 0.0
ub: obere Schranke der Variable, Standard: GRB.INFINITY
obj: Zielfunktionskoeffizient der Variable, Standard: 0.0
name: Name der Variable

Question 4

Standardform LP

Answer 4

max c^T*x
Ax = b
x ≥ 0

x: Entscheidungsvariable
A: Koeffizientenmatrix
b: rechte Seite
c^T: Zielfunktionskoeffizient

Kann aus kanonischer Form durch Schlupfvariablen gewonnen werden.

Question 5

Schlupfvariable

Answer 5

Wandelt eine Ungleichung in eine Gleichung um:

a+b≤c <=> a+b+s=c mit s≥0

Question 6

Vorgehen Simpex Algorithmus

Answer 6

1. LP in die Standardform bringen und in Tabelle schreiben
2. Zulässige Basis: Einheitsvektoren
3. Optimalität: Einträge der obersten Zeile nicht-positiv
4. Pivotelement: Pivotspalte(Spalte mit größtem Wert in der Zielfunktion) und
   Pivotzeile(Zeile mit dem kleinsten Wert ganz rechts, nachdem dieser durch den Spaltenwert geteilt wurde,
   wenn dieser denn größer als 0 ist, Ratiotest)
5. Wir bringen unser Pivotelement auf den Wert 1 und die ganze Zeile soll ein Basisvektor werden, also nur die 1
   als Eintrag haben, also müssen elementare Zeilenoperationen angewandt werden.
6. Der Zielfunktionswert kann oben rechts abgelesen werden, muss aber negiert werden
7. Solange die oberste Zeile positiv ist, müssen die Schritte wiederholt werden

Question 7

Was ist wenn im Simplexalgorithmus beim Ratiotest nur negative Ergebnisse rauskommen?

Answer 7

Unbeschränktes LP

Question 8

entartete Ecke

Answer 8

die Basis wird durch zu viele Ecken überbestimmt

Question 9

Wann ist die Basis eines Simplextableus nicht zulässig?

Answer 9

• Falls die b-Werte (untere rechte spalte) nicht alle positiv sind.
• Falls nicht alle Basisvektoren gegeben sind
• Falls die Kostenwerte nicht null sind

Big-M:
- alle Zielfunktionswerte negativ, aber w ist noch Teil der Basis

Question 10

Basen eines Polyeders

Answer 10

• LP auf Standardform bringen
• Den Geraden die jew. Schlupfvariablen zuordnen
• Bei der Basis einer Ecke mindestens 2 von den Schlupfvariablen der beteiligten Geraden weglassen

Question 11

Wann drehen sich beim Dualisieren die Vorzeichen um und wann nicht ?

Answer 11

max->min: Umdrehen
min->max: nicht Umdrehen

nur für die 0-Bedingung!

Question 12

Wann ist die gegebene, zulässige Lösung eines LPs optimal?

Answer 12

Die Lösung erfüllt die Gleichungen des primalen und dualen LPs mit Gleichheitszeichen.

Question 13

Gegeben: x* Vektor Lösung für primales LP; gesucht y* Vektor Lösung für Duales LP

Answer 13

BSP: x=(1,0,1)-> erste und dritte gleichung des dualen lps müssen mit gleichheit erfüllt sein; Gleichungssystem aufstellen und y´s rausrechnen.
Prüfen ob y die letzte Nebenbedingung auch erfüllt