#6 Anwendungen zur Linearen Optimierung

Question 1

Nordwesteckenregel

Answer 1

• Ausfüllen des Tableaus von oben links nach rechts Zeile für Zeile.
• immer versuchen den kompletten Bedarf zu decken

T   B1 B2 B3 B4   a
A1                         6
A2                        8
A3                        2
b   ....

Question 2

Minimalkostenregel

Answer 2

• Erfüllung der Bedarfsstellen nach den Transportkosten. Beginnen bei den niedrigsten Transportkosten und dann aufsteigend

T   B1 B2 B3 B4   a
A1                         6
A2                        8
A3                        2
b   ....

Question 3

Lineares Optimierungsproblem aus Transportproblem aufstellen

Answer 3

Kosten minimieren:

Miniere f c11x11 + c12x12 + c13x13….

c11 = Transportkosten von erster Abgabestelle zur ersten Bedarfsstelle 
x11 = gesuchte Menge die von erster Abgabestelle zu erste Bedarfsstelle transport wird

Nebenbedingungen:

a1= x12 + x11 + x13 (Es darf nur so viel abstransportiert werden, wie auch in der Abgabestelle vorhanden ist)
a2= ....

b1 = x12 + x21 (Es muss genau so viel geliefert werden, wie auch in der Bedarfsstelle benötigt wird

Question 4

MODI Verfahren

Answer 4

Siehe Blatt

Question 5

Zuordnungsprobleme

Answer 5

….sind Transportprobleme, bei denen an jeder Abgabestelle genau eine Mengeneinheit verfügbar ist und an jeder Bedarfsstelle genau eine Mengeneinheit benötigt wird.

• für eine Zuordnungsproblem mit n Objekten gibt es N! (Vakultät) zulässige Lösungen
  N! = 3! = 123
• die Einträge jeder Zeile und Spalte dürfen reduziert werden

Question 6

Ungarische Methode

Answer 6

(1) Reduktion der Ausgangsmatrix
a) Zeilenweise Reduktion -> minus Zeilenminimum
b) Spaltenweise Reduktion -> minus Spaltenminimum

(2) Versuchen Nullen so auszuwählen, dass pro Zeile und pro Spalte nur eine Null vorhanden ist.
- möglich -> optimale Lösung gefunden
- nicht möglich -> Schritt 3

(3) Anzahl minimaler Deckungslinien bestimmen
(Anzahl der Deckungslinien ungleich Anzahl der gesuchten Variablen)

(4) Minimum der nicht von einer Decklinie betroffenen Zahlen finden

(5) Matrix wird transformiert
Zahlen ohne Deckungslinie = - Minimum aus (4)
Zahlen mit Deckungslinie = bleiben gleich
Zahlen mit zwei Deckungslinien = + Minimum aus (4)

(6) Schritt 2 und 3 Wiederholen. Pro Spalte und Zeile muss nun eine Null vorhanden sein und es Muss Deckungslinien = Variablen heißen (Satz von König ­Egerváry)