Lineare Programme Flashcards Preview

Operations Research > Lineare Programme > Flashcards

Flashcards in Lineare Programme Deck (13):
1

kanonische Form LP

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

2

Gurobi Programm Grundstruktur

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

3

Gurobi Variable definieren

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

4

Standardform LP

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.

5

Schlupfvariable

Wandelt eine Ungleichung in eine Gleichung um:

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

6

Vorgehen Simpex Algorithmus

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

7

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

Unbeschränktes LP

8

entartete Ecke

die Basis wird durch zu viele Ecken überbestimmt

9

Wann ist die Basis eines Simplextableus nicht zulässig?

- 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

10

Basen eines Polyeders

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

11

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

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

nur für die 0-Bedingung!

12

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

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

13

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

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