FT-Karteikarten Flashcards
Ist eine Kante mit minimalem Gewicht im
zugehörigen minimalen Spannbaum enthalten?
Nein. (Begründung: Kanten mit minimalem
Gewicht könnten einen Kreis bilden. Bäume sind
Kreisfrei!)
Kann man Kruskals Algorithmus auch verwenden,
um einen maximalen Spannbaum zu berechenen?
Ja. Man bevorzugt Kanten mit höherem Gewicht
oder gewichtet die Kanten neu.
Nennen Sie die Definition eines Graphen
Ein Graph g(V,E) ist eine Menge von Punkten V,
die eventuell durch Kanten E miteinander
verbunden sind, wobei es nicht auf die Form
ankommt.
Was ist in einem Multigraphen erlaubt?
In Multigraphen sind parallele Kanten (wenn
gerichtet: in die gleiche Richtung) erlaubt.
Was ist ein endlicher Graph?
Ein Graph dessen Mengen der Knoten und Kanten
endlich ist.
Wie nennt man einen Graphen ohne parallele
Kanten und ohne Schlinge?
schlichter Graph
Was ist ein Digraph?
Ein schlichter gerichteter Graph mit endlicher
Knotenmenge
Was ist ein Zyklus?
Ein Zyklus ist ein geschlossener Weg. Ein Weg ist
die Folge von gerichteten Kanten, jeweils in
Pfeilrichtung.
Was ist ein vollständiger Digraph?
Ein vollständiger Digraph ist ein Digraph, in dem
für jedes Knotenpaar i,j ein Pfeil von i nach j und
ein Pfeil von j nach i vorhanden ist.
Wie heißt ein ungerichteter schlichter Graph, wenn
für jedes Knotenpaar i,j eine Kante von i nach j
existiert?
vollständiger schlichter Graph
Wie heißt ein Graph, bei dem jedes Knotenpaar
durch mindestens eine Kette verbunden ist?
zusammenhängender Graph
Was ist ein zusammenhängender, kreisfreier und
ungerichteter Graph?
Ein ungerichteter Baum
Was ist ein gerichteter Baum?
Ein gerichteter, kreisfreier Graph mit genau einem
Ausgangsknoten
Was ist die Adjazenzmatrix?
Die Adjazenzmatrix A(g)=a_ij drückt aus, welche
Knoten i und j im Graph verbunden sind. Es ist
eine [nxn]-Matrix mit den binären Elementen 0 und
1. 1 wenn eine Kante e(i,j) existiert und 0 in allen
anderen Fällen. Für ungerichtete Graphen ist die
Adjazenzmatrix symmetrisch. (nxn; 0 und 1; für
ungerichtete symmetrisch)
Was ist die Inzidenzmatrix?
Die Inzidenzmatrix H(g) = h_ij drückt aus, welche
Kanten e_j mit Knoten i verbunden sind. [nxm]-
Matrix wobei n die Anzahl der Knoten und m die
Anzahl der Kanten ist. Sie enthält die folgenden
Elemente: 1 wenn i der Startpunkt von e_j ist, -1
wenn i der Endpunkt von e_j ist(nur in gerichteten
Graphen) und 0 in allen anderen Fällen( wenn i
nicht Start- oder Endpunkt von e_j ist).
Wann wird ein Graph als gewichteter Graph
bezeichnet?
Wenn alle Kanten E eines Graph g(V,E,w) mit Werten w(e) versehen sind.
Was muss gelten, damit ein Subgraph (V’,E’) von
einem ungerichtetem Graph ein Spannbaum ist?
1. Der Subgraph muss alle Knoten des Graphen umfassen V'=V 2. Der Subgraph ist ein Baum, und damit 3. ist der Subgraph zusammenhängend und Kreisfrei
Was ist das Gewicht eines Spannbaums?
Die Summe aller seiner Kantengewichte.
Was ist ein minimaler Spannbaum?
Ein Spannbaum mit dem minimalen Gewicht unter
allen Spannbäumen.
Nenne zwei Beispiele für die Anwendung von
Spannbäumen!
1 Linienplanung für den öffentlichen
Personenverkehr
2 Kostengünstige
Anschlusskabel für Internet
Welche Bedingungen hat der Kruskal-
Algorithmus?
Der Graph muss endlich, ungerichtet ,
zusammenhängend und gewichtet sein.
Wozu dient der Kruskal-Algorithmus?
Mit dem Kruskal-Algorithmus kann man einen
minimalen oder maximalen Spannbaum finden.
Wann wird eine Kante beim Kruskal-Algorithmus
nicht in den minimalen Spannbaum mit
aufgenommen?
Wenn die Auswahl der Kante einen Kreis bilden
würde, oder wenn sich die ein Spannbaum bilden
lässt, der nur Kanten mit niedrigerem
Kantengewicht enthält.
Wozu dient der Dijkstra-Algorithmus?
Mithilfe des Dijkstra-Algorithmus kann man den
kürzesten Weg von einem Knoten zu allen
anderen Knoten finden.
Ist ein Teilweg von einem kürzesten Weg selbst
immer ein kürzester Weg?
Ja.
Wie kann der Dijkstra-Algorithmus angepasst
werden, damit zunächst alle Kanten mit den
kleinsten Kantengewichten verwendet werden?
Vor der Anwendung des Dijkstra-Algorithmus ist
eine Neugewichtung der Kanten erforderlich.
Wann ist der Dijkstra-Algorithmus beendet?
Wenn die Menge der markierten Knoten der
Menge aller Knoten entspricht.
Wann funktioniert der Dijkstra-Algorithmus nicht?
Bei negativen Kantengewichten.
Was ist der entscheidende Vorteil vom Bellman-
Ford-Algorithmus gegenüber dem Dijkstra-
Algorithmus?
Er funktioniert auch bei negativen
Kantengewichten. Und erkennt negative Zyklen.
Wie lautet das Prinzip der optimalen Substruktur?
Ein kürzester Weg zwischen zwei beliebigen
Knoten i und j in einem Graphen setzt sich immer
aus kürzesten Teilwegen zusammen. Bemerkung:
Dies gilt nur bei Graphen ohne negativen Zyklus!
Was sind die Abruchkriterien des Bellman-Ford-
Algorithmus?
-Treten auf der Hauptdiagonalen negative Einträge
auf, kann der Algorithmus abgebrochen werden,
da dies ein Hinweis auf einen negativen Zyklus ist.
-Verändern sich die Einträge der
U-Matrix von einer Iteration zu nächsten nicht, so
kann der Algorithmus abgebrochen werden, da
bereits eine optimale Lösung vorliegt.
-Der
Algorithmus muss maximal |V|-1 Mal durchlaufen
werden, danach noch ein weiters Mal zum Test auf
einen negativen Zyklus. (|V|=Anzahl der Knoten)
Was bedeutet es, wenn beim Bellman-Ford-
Algorithmus auf der Hauptdiagonalen in der
Bewertungsmatrix negative Werte Auftreten?
Es zeigt, dass es einen negativen Zyklus gibt. Es
gibt keine Lösung.
Was versteht man unter einem linearen
Optimierungs- oder Programmierungsproblem?
Unter einem linearen Optimierungs- oder
Programmierungsproblem(LP) versteht man die
Aufgabe, eine lineare (Ziel-)Funktion unter der
Beachtung von linearen Nebenbedingungen
(=Restriktionen) zu maximieren (oder minimieren).
Was ist der zulässige Bereich?(LP)
Die Menge der Punkte, die die Nebenbedingungen
erfüllen.
Wozu dienen Schlupfvariablen?
Schlupfvariablen werden bei einer Ungleichung auf
einer Seite addiert, um die Ungleichung in eine
Gleichung umzuformen.
Was ist eine zulässige Lösung in einem LP?
Ein Punkt (oder Vektor) der alle Nebenbedingungen Erfüllt.
Was ist eine zulässige Lösung in einem LP?
Eine Lösung, die die Nichtnegativitätsbedingung
erfüllt. Eine Lösung ist ein Punkt (oder Vektor) der
alle Nebenbedingungen Erfüllt.
Im Tableau sind alle b_i positiv
Wann ist eine Lösung eines LP optimal?
Eine Lösung eines LP ist optimal, wenn es keine
Lösung gibt, die bei einem Maximierungsproblem
einen größeren(Minimierungsproblem kleineren)
Funktionswert erzielt.
Im Tableau erkennt man eine Optimallösung an
den positiven Einträgen in der z-Zeile(nicht
Zielfunktionswert betrachten).
Wie findet man grafisch die optimale Lösung eines
LP?
Zunächst zeichnet man die Nebenbedingungen in
ein Koordinatensystem (Tipp:Achsenabschnitte).
Die Nebenbedingungen spannen die
Lösungsmenge auf. Daraufhin zeichnet man die
Zielfunktion mit einem beliebigen aber festen
Zielfunktionswert ein. Jetzt verschiebt man die
Zielfunktion parallel soweit nach
oben(Maximierung) oder unten(Minimierung), bis
sie den Lösungsraum gerade noch berührt. Die
Punkte, die sich sowohl auf der verschobenen
Zielfunktion, alsauch in der Lösungsmenge
befinden sind die optimale Lösungsmenge.
Was ist bei der Verwendung einer Gleichung als
Nebenbedingung bei der Erstellung der
Standardform eines LP zubeachten?
Die Gleichung muss in eine „Größergleich-“ und
eine „Kleinergleich-“ Ungleichung aufgeteilt
werden.
Was sind Strukturvariablen?
Strukturvariablen sind keine Schlupfvariablen. Sie
sind die Variablen des Ursprünglichen Problems.
Wann spricht man von der Standardform eines
LP?
Maximierungsfunktion; Nur Gleichungen (Schlupf);
Nichtnegativitätsbedingung, alle variablen
links(auch in zf)
Was gilt bezüglich der Konvexität der
Lösungsmenge Eines LP in Standardform?
Die Menge der hinsichtlich jeder einzelnen der
Nebenbedingungen zulässigen Lösungen ist
Konvex. Die Menge X aller zulässigen Lösungen
des Problems ist als Durchschnitt konvexer
Mengen ebenfalls konvex mit endlich vielen
Eckpunkten.
Wieviele Eckpunkte der Lösungsmenge berührt
die optimale Zielfunktion immer?
mindestens Einen. Höchstens so viele wie es
Strukturvariablen gibt.
Was gilt für die Menge aller optimalen Lösungen
eines LPs bezüglich Konvexität?
Die Menge aller optimalen Lösungen eines LPs ist
immer konvex. (Sind zwei Punkte eine optimale
Lösung, so sind es auch alle dazwischen)
Welchen Wert hat eine Nicht-Basisvariable in der
Basislösung?
Null
Wann ist ein Punkt einer konvexen Menge ein
Eckpunkt?
Wenn er sich nicht als echte Linearkombination
zweier verschiedener Punkte der Menge darstellen
lässt.
Definition für konvexe und echte
Linearkombination
Seien x1, …, xk Punkte in Rn und seien λ1 ≥
0, …, λk ≥ 0 mit λ1 + …+ λk = 1. Dann heißt y =
λ1x1 + …+ λkxk konvexe Linearkombination von
x1, …, xk. Gilt für alle Koeffizienten λ1 > 0, …, λk
> 0, so heißt y echte Linearkombination. ?
Echte Linearkombination Skalare auch in
Summe 1?
Was gilt für die konvexe Linearkombination?
Linearkombination mit Skalaren größergleich Null
und in Summe 1
Was gilt für die echte Linearkombination?
Linearkombination mit Skalaren echt größer Null
und in Summe 1.
Wie sieht die allgemeine Form eines LP aus?
Hier 4.1.b) Lösung einfügen
Wofür steht die Abkürzung s.t.?
Subjekt to (Nebenbedingungen)
Schritte von allgemeiner zur Standardform eines
LP
-Alle Strukturvariablen auf die linke Seite(auch zf)
-Gleichung zu zwei Ungleichungen
-Größergleich zu kleinergleich umformen(Mal -1)
-Variablen, die kleiner Null sein dürfen
Aufteilen(x_j=x_j-x_j`)
-Ungleichung zu Gleichung
umformen(Schlupfvariablen)
Wie zeigt sich die Unbeschränktheit eines LP im
primalen Simplex?
Es lässt sich kein Pivotelemnt finden(Alle a_ij
negativ) ??Was wenn mehrere b_i negativ??
Was passiert im dualen simplex, wenn es keine
zulässige Lösung gibt?
Es lässt sich kein Pivotelemnt finden(Alle a_ij
positiv)
Was macht man mit einer Gleichung(=) bei der
erstellung der Standardform?
Man teilt sie auf in eine kleiner und größer
Ungleichung
Wann gibt es keine zulässige Lösung?
Die Nebenbedingungen sind nich t
widerspruchsfrei. Die Lösungsmenge ist die leere
Menge. Im dualen Simplex lässt sich kein
Pivotelement finden(Zeileneinträge größer Null)
Was ist duale Degeneration?
Bei dualer Degeneration gibt es mehrere optimale
Lösungen. Man erkennt duale Degeneration, wenn
im Optimaltableau ein Eintrag in der Spalte einer
Nichtbasisvariable in der Zielfunktionszeile Null ist.
Eine Aufnahme der Nichtbasisvariable in die Basis
würde den Zielfunktionswert nicht verändern!
Was ist primale Degeneration? Woran erkennt
man sie im Tableau?
Primale Degeneration liegt vor, wenn im
Optimaltableau ein Eintrag der rechten Seite Null
ist. Es ist eine spezielle Form der Redundanz, bei
der sich in der Optimallösung mehr
Nebenbedingungen schneiden als es
Strukturvariablen gibt.
Was besagt die MUB im Branch and Bound?
Auswahlstrategie für Teilproblem. Maximum Upper
Bound. Wähle Problem mit größtem
Zielfunktionswert aus der Liste.(Branch and
Bound)
Was besagt die FIFO-Methode im Branch and
Bound Algorithmus?
First In First Out. Wähle Problem aus der Liste,
das zuerst eingeführt wurde.
Was besagt die LIFO-Methode im Branch and
Bound Algorithmus?
Auswahlstrategie für Teilproblem. Last In First Out.
Wähle Problem aus der Liste, das zuletzt
eingeführt wurde.
Wodurch zeichnet sich ein Rucksackproblem aus?
1Zielfunktion(Nutzen)+
1Nebenbedingung(Gewicht)
+Entscheidungsvariablen sind 1 oder Null
RoF?: Beim Branch-and-Bound-Verfahren
wird zunächst ein relaxiertes Problem gelöst,
das einen kleineren Zulässigkeitsbereich als
das ursprüngliche Problem aufweist.
?Richtig?
RoF?: Der Kruskal-Algorithmus kann auch
verwendet werden um einen maximalen
Spannbaum zu berechnen.
Richtig. Man bevorzugt einfach die Kanten mit
maximalem Gewicht.
RoF?: Ein Knoten ohne Nachfolger heißt Quelle.
Falsch. Er heißt Senke bzw in eine Quelle gehen
mehr Kanten hinein als hinaus.
RoF?: Ein Spannbaum ist ein Subgraph, der
alle Knoten des Ursprungsgraphen umfasst.
Richtig
RoF?: Eine Kante mit minimalem Gewicht ist
immer im zugehörigen minimalen Spannbaum
enthalten.
Falsch. (Kreisbildung)Gegenbeispiel. Ein Graph in
dem alle Kanten das selbe Gewicht haben besitzt
nur Kanten mit minimalem Gewicht. Es sind jedoch
nicht alle enthalten, wenn es mindestens so viele
Kanten wie Knoten gibt.
RoF?: Die Anzahl der Optimallösungen eines
linearen Programms ist immer endlich.
Falsch. Ein LP kann keine, unendlich viele oder
eine Lösung haben
RoF?: Jedes LP kann als
Maximierungsproblem oder
Minimierungsproblem dargestellt werden.
Richtig. Man multipliziert die Zielfunktion mit -1 zur
Umformung
Rof?: Ein Punkt Y heißt Eckpunkt einer
konvexen Menge, wenn er sich nicht als echte
Linearkombination zweier verschiedener
Punkte darstellen lässt.
Richtig
Rof?: Ist im dualen Optimum der Wert der
Variablen, die der i-ten Nebenbedingung des
Primalproblems entspricht positiv, so bindet
diese
Nebenbedingung im Optimum scharf.
Richtig. (Komplementärer Schlupf)
RoF?: Die Summe von Entscheidungen in der
dynamischen Optimierung nennt man
Variante.
Falsch. Sie heißt Politik
Wie zeigt sich Redundanz im Tableau?
Im Simplex-Tableau: Positive rechte Seite mit
Zeileneinträgen ausschließlich null oder
negativ.
Wie erkennt man, dass es sich bei einem Tableau
um eine unzulässige Lösung handelt?
Mindestens ein b_i ist negativ. (Achtung! Nicht
Zielfunktionsert betrachten. Kann negativ sein)
Wie erkennt man, dass es sich bei einem Tableau
um eine zulässige Lösung handelt?
alle bi positiv.(Achtung! Nicht Zielfunktionswert
betrachten. Dieser kann negativ sein)
Wie erkennt man, dass es sich bei einem Tableau
um eine Optimallösung handelt?
Alle Einträge in der z-Zeile(c_j) positiv(Achtung:
nicht Zielfunktionswert betrachten!)
Wie erkennt man Unbeschränktheit in einem
Tableau?
Eine Spalte mit nur negativen Einträgen. Es lässt
sich kein Pivotelement finden.
Was ist ein schlichter Graph?
Ein Graph ohne Schlingen und parallele Kanten.
Was gilt für einen ungerichteten Baum?
Er ist kreisfrei, ungerichtet und
zusammenhängend.
Was gilt in einem zusammenhängendem
Graphen?
Jedes Knotenpaar ist durch mindestens eine Kette
miteinander verbunden.
RoF?: Ein Unbeschränktes Problem hat eine
optimale Lösung.
Falsch
RoF?: Um die dynamische Optimierung anwenden
zu können, muss eine geeignete Modellierung des
Problems vorliegen.
Richtig
RoF?: Bei der dynamischen Optimierung existiert
eine Anzahl von Zuständen, die gemeinsam
betrachtet werden.
Falsch. Die Zustände werden separat betrachtet.
Was beeinflusst die Zielfunktion bei der
dynamischen Optimierung?
Die gesammte Politik (Die Summe der Entscheidungen)
Was ist das Grundprinzip der dynamischen
Optimierung?
Die Optimalität der Entscheidung auf einer Stufe
hängt nicht von den vorhergehenden
Entscheidung ab. Eine optimale Politik bedeutet:
Die Folge der Entscheidungen ab einer Stufe bis
zur letzten Stufe ist optimal bezüglich des auf
dieser Stufe beobachteten Zustandes.
Was ist die Idee hinter der Dynamischen
Optimierung?
Optimalitätsprinzip von Bellman. Die Optimierung
beginnt auf der letzten Stufe und setzt sich
rückwärts fort(Rückwertsrechnung). Sind alle
Stufen abgearbeitet sucht man ausgehend von der
ersten Stufe die optimale
Politik(Vorwärtsrechnung).
RoF?: Die dynamische Optimierung ist ein
Algorithmus.
Falsch. Es ist eine allgemeines Prinzip.
RoF?: Die dynamische Optimierung beschränkt
sich auf die Rückwärtsrechnung.
Falsch. Es gibt Rückwärts und Vorwärtsrechnung
in der dynamischen Optimierung.
RoF?: Die Dynamische Optimierung führt schneller
ans Ziel als die vollständige Enumeration.
Richtig. (Vollständige Enumeration=Alle zulässigen
Lösungen finden. Vergleich liefert Optimale
Lösung)
Nennen Sie zwei Beispiele zur Anwendung der
dynamischen Optimierung!
1 Lagerhaltung
2 Kürzeste Wege
Welche Entscheidungsmöglichkeiten betrachtet
man bei der typischen Modellierung des
Lagerhaltungsproblems zur Anwendung der
dynamischen Optimierung?
Man betrachtet, wie viele Waren man im Lager
halten kann.
Wozu dient der Yen-Algorithmus?
Der Yen-Algorithmus findet die nächst längeren
Wege zum kürzesten weg.
RoF?: Der Yen-Algorithmus liefert nur
schleifenfreie Ergebnisse.
Richtig
RoF?: Ein Modell ist ein vereinfachtes,
zweckorientiertes Abbild eines realen Systems.
Richtig
RoF?: Das Testen einer optimalen Lösung eines
linearen Programms bzgl. einer Veränderung der
Variablen bezeichnet man als Sensitivitäts- oder
Sensibilitätsanalyse.
Falsch. Man testet bzgl. der
Eingabedaten(Koeffizienten vor den Bedingungen)
Wozu dient die Sensitivitätsanalyse?
Mit der Sensitivitätsanalyse lässt sich mit
verhältnismäßig geringem Aufwand ein Eindruck
der Stabilität der Lösung gewinnen. Sie zeigt
einem, wie sich die Koeffizienten der Zielfunktion
und Nebenbedingungen einzeln verändern dürfen
und die optimale Lösung die optimale Lösung
bleibt.
Welche Annahmen benötigt die
Sensitivitätsanalyse?
LP (Maximierung, Strukturvariablen ,
Schlupfvariablen); Es liegt keine Degeneration vor
RoF?: Es gibt immer so viele Nichtbasisvariablen
in einer Lösung eines LP, wie es Strukturvariablen
gibt.
Richtig
Was ist ein relaxiertes Problem?
Ein relaxiertes Problem ist ein einfacheres
Problem, dessen Lösungsmenge alle Lösungen
des Ursprungsproblems enthält. Ferner steht die
Lösung des relaxierten Problems in einem nichttrivialen
Zusammenhang der Lösung des
Ausgangsproblems.
RoF?: Die Lösung eines relaxierten Problems
steht in einem trivialen Zusammenhang mit der
Lösung des Ausgangsproblems.
Falsch. Nicht-trivialer Zusammenhang
Was ist der Zielerreichungsgrad?
Der Zielerreichungsgrad ist eine relative Größe für
die Abweichung des Zielfunktionswertes einer
Lösung von dem Zielfunktionswert der optimalen
Lösung. Er berechnet sich als Quotienten von dem
Zielfunktionswert einer Lösung durch den
optimalen Zielfunktionswert
Findet der Yen-Algorithmus bei Schleifen
Anwendung?
Nein. (Begründung: Kanten mit minimalem
Gewicht könnten einen Kreis bilden. Bäume sind
Kreisfrei!)
Wie heißt eine Lösung, die für jede Zielsetzung
optimal ist?
Perfekte Lösung
Wie berechnet man den Zielerreichungsgrad?
Man teilt den Zielfunktionswert einer Lösung durch
den optimalen Zielfunktionswert.
Welche Probleme gibt es bei der Lösung
multikriterieller LPs mit Zieldominanz?
Hinzukommende Schranken beschneiden
möglicherweise den Zielerreichungsgrad des
Hauptziels zu sehr. Möglicherweise gibt es durch
die zusätzlichen Schranken sogar keine zulässige
Lösung mehr.
Wie funktioniert die Lexikographische Ordnung
von Zielen?
Ziele werden nach ihrer Wichtigkeit geordnet. Man
optimiert zunächst nach dem wichtigsten Ziel.
Danach wird der Lösungsraum auf die nach dem
wichtigsten Ziel optimale Lösung beschränkt. Jetzt
wird das zweitwichtigste Ziel unter dem neuen
Lösungsraum optimiert und die jetzt optimale
Lösung beschränkt den Lösungsraum weiter und
so fort.
RoF?: Der Zielerreichungsgrad des wichtigsten
Ziels ist bei der erfolgreichen Lösung mit
Lexikographischen Ordnung immer 1.
Richtig
Wie funktioniert die Zieldominanz?
Man erklärt ein Ziel zum Dominanten Ziel, nach
dem optimiert wird. Die anderen Ziele werden als
Nebenbedingungnen übernommen. Die nicht
dominanten Ziele werden mit einer Schranke
versehen. Zu maximierende Zielfunktionen
müssen größer einer schranke(größergleich) sein.
Zu minimierende kleiner als eine
Schranke(kleinergleich)
Was macht man bei der Zielgewichtung?
Bei der Zielgewichtung werden die verschiedenen
Ziele gewichtet. Sie werden mit Skalaren
versehen, die zwischen Null und eins sind und in
Summe eins.
RoF?: Abstandsfunktionen sind häufig nicht-linear.
So werden Abweichungen schwächer bestraft, je
höher ihr Wert ist.
Falsch. So werden Abweichungen stärker bestraft.
Beispiel für Fixkosten im LP
x_1≤BIG*Y_1
Wenn Tische produziert werden, dann mindestens
25
x_1≤BIG*Y_1
25-x_1≤BIG(1-Y_1)
Entweder x_1≤10 oder x_1≥20 im LP?
10-x_1≤BIG*Y_1
20-x_1≤BIG(1-Y_1)
Wenn x_2+x_3>30 dann x_1≥50 im LP?
-30+x_2+x_3≤BIG*(Y_1)
50-x_1≤BIG(1-Y_1)
Was ist die Grundidee des Add-Algorithmus?
Beginne mit null Standorten, füge nun sukzessive
Standorte, die die Kostenjeweils senken, hinzu, bis
sich durch Hinzunahme eines iteren Standortes
die Kosten nicht mehr senken lassen. Schließe
Standorte, die keine weitere Kostenersparnis
bewirken.
RoF?: Der Add-Algorithmus findet beim
Warehouse Location Problem die beste Lösung.
Falsch. Der heuristische Algorithmus findet nur
eine gute Lösung. Nicht zwingend die Beste.
Wie lässt sich am schnellsten herausfinden,
welches Ziel von welchem Lager beliefert wird?
(Warehouse Location Problem/Add-Algorithmus)
Man betrachtet zunächst das zuletzt eröffnete
Lager. Es beliefert alle Ziele, bei denen die
Eröffnung des Lagers eine Ersparnis gebracht hat.
Dies führt man der Reihe nach bis zum zuerst
eröffneten Lager fort. Bereits ausgewählte Ziele
stehen nicht weiter zur Verfügung.
Wie lassen sich bei mit Add gelößtem Warehouse
Location Problem die Gesamtkosten bestimmen?
Kosten für das als erstes Eröffnete Lager
abzüglich der Ersparnis der später eröffneten
Lager.
