OR
operations research
operations research
Definition Weg gerichteter Graph
Ein Weg ist in einem gerichteten Graph eine Kette, wobei die Pfeile nur in eine Richtung zeigen
Definition Kreis & Zyklus
> in einem ungerichteten Graphen heisst eine Kette Kreis, wenn gilt io = it
> in einem gerichteten Graphen heisst ein Weg mit io = it Zyklus
was ist die Definition eines Baumes & eines Waldes
> Baum: Baum in G ist ein zusammenhängender, ungerichteter, zyklusloser Graph
> Wald: ungerichteter kreisloser Graph, seine Komponenten sind Bäume
wie funktioniert der algorithmus für azyklische Graphen und was macht er?
- beginne beim Knoten welcher kein Vorgänger hat
- wähle den nächsten Knoten indem l_v maximiert wird
- fahre so fort
- sucht den längsten Weg von einer Quelle s zu allen anderen Knoten im gerichtetem Graphen
Was ist ein Gerüst, spanning tree?
Ein Gerüst in G ist ein Baum in G, welcher alle Knoten von G umfasst
was ist die voraussetzung für den djikstra algorithmus und was sucht er?
> sucht die kürzesten Wege von Knoten s zu allen anderen Knoten im gerichtetem/ungerichtetem Graphen "one to all"
> alle Längen der Kanten sind nichtnegativ
> Zyklen sind zulässig, aber Zyklen negativer Länge dürfen nicht auftreten
> da keine negativ bewerten Kanten im Graphen vorkommen dürfen
Dijkstra Algorithmus: Aufteilung der Knoten in Teilmengen
- Menge A der Knoten, zu denen bereits kürzester Weg von der Quelle S bekannt ist
- Menge B der Knoten, zu denen Wege von s aus bekannt sind, jedoch nicht sicher ist, ob diese minimal sind
- Menge C der Knoten, zu denen noch kein Wege von s aus bekannt sind
Wie gehe ich beim Kruskal vor?
- sortiere Kanten nach aufsteigenden Gewichten
- markiere diese Kanten rot
- es dürfen keine Zyklen entstehen
- alle Orte müssen besucht werden und es muss eine verbindung zwischen den Punkten bestehen
allgemeines heuristisches Vorgehen für Optimierungsprobleme?
Eröffnungsverfahren: Bilde eine gute zulässige Lösung
Verbesserungsverfahren: Verbessere diese Tour iterativ (2-opt)
was ist die Länge eines Weges?
Die länge eines Weges ist die SUmme der Löngen seiner Kanten
voruassetzung für den
- kürzesten weg
- längsten weg
kürzesten: keine negativen Zyklen im Graphen
längsten: keine positiven Zyklen im Graphen
wie funktioniert die topologische sortierung im azyklischen Graphen?
- wähle einen Knoten v, der kein Vorgänger hat und gebe ihm die nächste Nr. (v existiert immer wenn kein Zyklen vorhanden sind)
- Entferne Knoten v (mit seinem Bogen) und fange wieder bei Schritt 1 an
wie funktioniert die nearest neigbor heuristik?
- wähle einen Startknoten
- von diesem aus zum nächsten mit der kleinsten Distanz
- fahre von diesem Knoten genau gleich fort, also zum nächsten Knoten mit der kleinsten Distanz
wie funktioniert die nearest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten mit der minimalen distanz
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie funktioniert farthest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten mit der maximalen distanz
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie funktioniert die cheapest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten j, welcher die Länge der Tour am wenigsten erhöht
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie sieht eine adjazenzmatrix in einem ungerichtetem graphen aus?
- die matrix ist symmetrisch
- ich habe da eine 1, wo es zwischen zwei Knoten einen Weg gibt
wie sieht eine inzidenzmatrix in einem ungerichteten Graphen aus?
- Liegt ein Knoten nicht an einer Kante an, dann schreiben wir in die zugehörige Zelle, einfach eine 0
- liegt ein Knoten an einer Kante, dann schreiben wird eine 1 in die Zelle
- eignet sich vor allem für viele Knoten mit wenig Kanten
Gib an:
- Knotengrade in G
- Menge der hängenden (falls deg(v) = 1) Knoten in G
- Menge isolierter (falls deg(v) = 0) Knoten in G
- Knotenmenge S, delta(S) = Menge aus S hinausführenden Kanten (Endknoten in S, aber den anderen ausserhalb von S)
- Knotenmenge S, gamma(S) = Menge der in S liegenden Kanten (beide Endknoten in S)
Knotengrade: deg(1) = 3, deg(2) = 2, deg(6) = 1, deg(5) = 0
hängender Knoten: G = {4,6,7}
isolierter Knoten: G = {5}
Knotenmenge:
- S{1,3,4} → delta(S) = {(1,2),(2,3)}, gamma(S) = {(1,3), (1,4)}
- S{6,7} → delta(S) = Ø, gamma(S) = {(6,7)}
was ist ein ungerichteter Graph?
Ein ungerichteter Graph, ist ein Paar G = (V,E) wobei V eine endlich eMengen und E eine Menge von uneordneten Paaren von Elementen aus V ist.
was ist ein gerichteter Graph?
ein gerichteter Graph ist ein Paar G = (V,E) wobei V eine endliche Menge und E eine Menge von geordneten Paaren von Elementen aus V ist.
Die Elemente von V werden als Knoten und die Elemente von E als die Bogen von G bezeichent.
wie sieht eine adjazenzmatrix eines gerichteten Graphen aus?
- es gibt da eine 1 wo es Kanten zwischen zwei Knoten hat
- die 1 setzt ich da von wo aus der Graph beginnt (also beim head)
wie sieht die inzidenzmatrix eines gerichteten graphen aus?
- eine -1 beim austritt aus einem Knoten
- eine 1 beim eintritt in eine Knoten
- zeilen = Knoten
- Spalten = Kanten
was passiert im branch & bound algorithmus?
es wird zu jedem Teilmodell die zugehörige LP-Relaxion gelöst
Was passiert bei einer Relaxierung eines Optimierungsproblems?
Die Forderung der Ganzzahligkeit wird aufgehoben
was sagt die starke dualität aus?
wenn das primale problem eine optimale Lösung besitzt, so hat auch das duale Problem eine optimale lösung
The duality gap = 0, dual and primal problem are the same
was ist das dualproblem, wenn das primalproblem unbeschränkt ist?
das zugehörige dualproblem ist unzulässig, weil das P gegen unendlich geht und wenn man es kehren würde, würde das D gegen minus gehen, was nicht funktioniert.
Was sagt die schwache dualität aus?
the duality gap is >= 0
That means the solution to the dual (minimization) problem is always greater than or equal to the solution to an associated primal problem
wie funktioniert der simplex algorithmus und nach was sucht er?
- maximierungsform * -1 rechnen
- ungleichung zu Gleichungen umformen mittels Schlupf steht <= darf sofort eingefügt werden
- wähle nichtbasisvariable mit dem kleinsten negativen koeffizienten in der Zielfunktionszeile
- pivotzeile bestimmt sich durch die Berechnung aller Quotienten der Form rechte seize dividiert durch das entsprechende Element aus der Pivotspalte. (ignoriere alle Elemente in Pivotspalte = negativ oder null sind)
- Wähle die Zeile mit dem kleinsten Quotienten Basisvariable dieser Zeile wird zur Nichtbasisvariablen
- Pivotzeile so multiplizieren, das pivotelement = 1
Er sucht im Polyeder, nach der optimalen ganzzahligen Ecke
wann ist ein LP unzulässig?
ist unzulässig, weil sich Ungleichungen widersprechen, z.B. x1 <= 1 und x1 >= 2.
In diesem Falle gibt es keine Lösung, welche alle Ungleichungen erfüllen würde, das zugehörige Polyeder ist die leere Menge
was ist ein greedy algorithmus?
- Es wird nämlich immer die aktuell beste Entscheidung getroffen, ohne auf Vorherige oder auf Auswirkungen dieser Wahl zu achten.
- oft schnelle Lösung
- kann sein, dass aus diesem Grund nicht die optimale Lösung gefunden wird
- Kruskal oder dijkstra sind greedy algorithmen
was heisst wenn ein lp unbeschränkt ist?
es gibt unendlich viele zulässige Lösungen mit beliebig hohen Zielfunktionswerten (z. B. max { x | x ≥ 0 } ).
Wie entsteht ein Steiner Baum und was sucht er?
Ein steiner Baum entsteht wenn alle obligatorischen Knoten aus N und zusätzlich (muss nicht sein) die fakultativen Knoten, also die Steiner Knoten benutzt werden um jeden obligatorischen Knoten im Baum ohne Zyklen zu erreichen.
das Problem des minimalen Steiner Baums besteht darin, unter allen möglichen Steiner Bäumen von G, einen mit minimalem Gewicht zu finden.
was gibt ein Schattenpreis an?
Ein Schattenpreis einer Restriktion gibt an, wie viel sich der Zielfunktionswert ändert, wenn die Kapazität der entsprechenden Ressource um eine Einheit erhöht wird.
Wenn das Primalproblem unbeschränkt ist, was ist dann mit dessen Dualproblem?
- unbeschränkt
- unzulässig
- optimal
dann ist dessen D unzulässig, weil das P gegen unendlich geht und wenn man es kehrt, geht das D gegen minus unendlich, was nicht zulässig ist
in einem ungerichtetem, schlichtem Graphen G=(V,E) entspricht die SUmme aller Knotengerade der doppelten Anzahl der Kanten wieso?
ich weiss e=(v,w), Kante e verbindet Knoten v und w
Knotengerade deg(v) und deg(w), werden zweimal gezählt
siehe inzidenzmatrix , doppelt so viele Kanten wie Knoten
in einem ungerichtetn, schlichten Graphen G=(V,E) ist die Anzahl Knoten mit ungeradem Grad gerade. was bedeutet das?
In jdem Graphen gibt es eine gerade Anzahl Knoten mit ungeradem Knotengrad → da Kanten immer zweimal gezählt werden, kann es gar nie eine ungerade Anzahl geben.
was macht der floyd warshall alogrithmus?
- im ungerichtetem/gerichtetem Graphen sucht er nach dem kürzesten Wegen von jedem Knoten i zu jedem Knoten j
- Zyklen sind erlaubt
- erkennt negative Zyklen
- für den längsten Weg, einfach Vorzeichen wechseln
-
- 1 / 38
-
Cartes-fiches
Definition Weg gerichteter Graph
Ein Weg ist in einem gerichteten Graph eine Kette, wobei die Pfeile nur in eine Richtung zeigen
Definition Kreis & Zyklus
> in einem ungerichteten Graphen heisst eine Kette Kreis, wenn gilt io = it
> in einem gerichteten Graphen heisst ein Weg mit io = it Zyklus
was ist die Definition eines Baumes & eines Waldes
> Baum: Baum in G ist ein zusammenhängender, ungerichteter, zyklusloser Graph
> Wald: ungerichteter kreisloser Graph, seine Komponenten sind Bäume
wie funktioniert der algorithmus für azyklische Graphen und was macht er?
- beginne beim Knoten welcher kein Vorgänger hat
- wähle den nächsten Knoten indem l_v maximiert wird
- fahre so fort
- sucht den längsten Weg von einer Quelle s zu allen anderen Knoten im gerichtetem Graphen
Was ist ein Gerüst, spanning tree?
Ein Gerüst in G ist ein Baum in G, welcher alle Knoten von G umfasst
was ist die voraussetzung für den djikstra algorithmus und was sucht er?
> sucht die kürzesten Wege von Knoten s zu allen anderen Knoten im gerichtetem/ungerichtetem Graphen "one to all"
> alle Längen der Kanten sind nichtnegativ
> Zyklen sind zulässig, aber Zyklen negativer Länge dürfen nicht auftreten
> da keine negativ bewerten Kanten im Graphen vorkommen dürfen
Dijkstra Algorithmus: Aufteilung der Knoten in Teilmengen
- Menge A der Knoten, zu denen bereits kürzester Weg von der Quelle S bekannt ist
- Menge B der Knoten, zu denen Wege von s aus bekannt sind, jedoch nicht sicher ist, ob diese minimal sind
- Menge C der Knoten, zu denen noch kein Wege von s aus bekannt sind
Wie gehe ich beim Kruskal vor?
- sortiere Kanten nach aufsteigenden Gewichten
- markiere diese Kanten rot
- es dürfen keine Zyklen entstehen
- alle Orte müssen besucht werden und es muss eine verbindung zwischen den Punkten bestehen
allgemeines heuristisches Vorgehen für Optimierungsprobleme?
Eröffnungsverfahren: Bilde eine gute zulässige Lösung
Verbesserungsverfahren: Verbessere diese Tour iterativ (2-opt)
was ist die Länge eines Weges?
Die länge eines Weges ist die SUmme der Löngen seiner Kanten
voruassetzung für den
- kürzesten weg
- längsten weg
kürzesten: keine negativen Zyklen im Graphen
längsten: keine positiven Zyklen im Graphen
wie funktioniert die topologische sortierung im azyklischen Graphen?
- wähle einen Knoten v, der kein Vorgänger hat und gebe ihm die nächste Nr. (v existiert immer wenn kein Zyklen vorhanden sind)
- Entferne Knoten v (mit seinem Bogen) und fange wieder bei Schritt 1 an
wie funktioniert die nearest neigbor heuristik?
- wähle einen Startknoten
- von diesem aus zum nächsten mit der kleinsten Distanz
- fahre von diesem Knoten genau gleich fort, also zum nächsten Knoten mit der kleinsten Distanz
wie funktioniert die nearest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten mit der minimalen distanz
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie funktioniert farthest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten mit der maximalen distanz
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie funktioniert die cheapest insertion?
- wähle 2 Knoten v und w und starte mit der Teiltour v,w,v(Wähle sie som dass d_vw minimal ist)
- wähle den einzufügenden Knoten j, welcher die Länge der Tour am wenigsten erhöht
- berechne delta(j,p,q) = d_pj + d_jq - d_pq
- Einfügestelle: j hat beste Stelle, da wo delta(j,p,q) minimal ist
wie sieht eine adjazenzmatrix in einem ungerichtetem graphen aus?
- die matrix ist symmetrisch
- ich habe da eine 1, wo es zwischen zwei Knoten einen Weg gibt
wie sieht eine inzidenzmatrix in einem ungerichteten Graphen aus?
- Liegt ein Knoten nicht an einer Kante an, dann schreiben wir in die zugehörige Zelle, einfach eine 0
- liegt ein Knoten an einer Kante, dann schreiben wird eine 1 in die Zelle
- eignet sich vor allem für viele Knoten mit wenig Kanten
Gib an:
- Knotengrade in G
- Menge der hängenden (falls deg(v) = 1) Knoten in G
- Menge isolierter (falls deg(v) = 0) Knoten in G
- Knotenmenge S, delta(S) = Menge aus S hinausführenden Kanten (Endknoten in S, aber den anderen ausserhalb von S)
- Knotenmenge S, gamma(S) = Menge der in S liegenden Kanten (beide Endknoten in S)
Knotengrade: deg(1) = 3, deg(2) = 2, deg(6) = 1, deg(5) = 0
hängender Knoten: G = {4,6,7}
isolierter Knoten: G = {5}
Knotenmenge:
- S{1,3,4} → delta(S) = {(1,2),(2,3)}, gamma(S) = {(1,3), (1,4)}
- S{6,7} → delta(S) = Ø, gamma(S) = {(6,7)}
was ist ein ungerichteter Graph?
Ein ungerichteter Graph, ist ein Paar G = (V,E) wobei V eine endlich eMengen und E eine Menge von uneordneten Paaren von Elementen aus V ist.
was ist ein gerichteter Graph?
ein gerichteter Graph ist ein Paar G = (V,E) wobei V eine endliche Menge und E eine Menge von geordneten Paaren von Elementen aus V ist.
Die Elemente von V werden als Knoten und die Elemente von E als die Bogen von G bezeichent.
wie sieht eine adjazenzmatrix eines gerichteten Graphen aus?
- es gibt da eine 1 wo es Kanten zwischen zwei Knoten hat
- die 1 setzt ich da von wo aus der Graph beginnt (also beim head)
wie sieht die inzidenzmatrix eines gerichteten graphen aus?
- eine -1 beim austritt aus einem Knoten
- eine 1 beim eintritt in eine Knoten
- zeilen = Knoten
- Spalten = Kanten
was passiert im branch & bound algorithmus?
es wird zu jedem Teilmodell die zugehörige LP-Relaxion gelöst
Was passiert bei einer Relaxierung eines Optimierungsproblems?
Die Forderung der Ganzzahligkeit wird aufgehoben
was sagt die starke dualität aus?
wenn das primale problem eine optimale Lösung besitzt, so hat auch das duale Problem eine optimale lösung
The duality gap = 0, dual and primal problem are the same
was ist das dualproblem, wenn das primalproblem unbeschränkt ist?
das zugehörige dualproblem ist unzulässig, weil das P gegen unendlich geht und wenn man es kehren würde, würde das D gegen minus gehen, was nicht funktioniert.
Was sagt die schwache dualität aus?
the duality gap is >= 0
That means the solution to the dual (minimization) problem is always greater than or equal to the solution to an associated primal problem
wie funktioniert der simplex algorithmus und nach was sucht er?
- maximierungsform * -1 rechnen
- ungleichung zu Gleichungen umformen mittels Schlupf steht <= darf sofort eingefügt werden
- wähle nichtbasisvariable mit dem kleinsten negativen koeffizienten in der Zielfunktionszeile
- pivotzeile bestimmt sich durch die Berechnung aller Quotienten der Form rechte seize dividiert durch das entsprechende Element aus der Pivotspalte. (ignoriere alle Elemente in Pivotspalte = negativ oder null sind)
- Wähle die Zeile mit dem kleinsten Quotienten Basisvariable dieser Zeile wird zur Nichtbasisvariablen
- Pivotzeile so multiplizieren, das pivotelement = 1
Er sucht im Polyeder, nach der optimalen ganzzahligen Ecke
wann ist ein LP unzulässig?
ist unzulässig, weil sich Ungleichungen widersprechen, z.B. x1 <= 1 und x1 >= 2.
In diesem Falle gibt es keine Lösung, welche alle Ungleichungen erfüllen würde, das zugehörige Polyeder ist die leere Menge
was ist ein greedy algorithmus?
- Es wird nämlich immer die aktuell beste Entscheidung getroffen, ohne auf Vorherige oder auf Auswirkungen dieser Wahl zu achten.
- oft schnelle Lösung
- kann sein, dass aus diesem Grund nicht die optimale Lösung gefunden wird
- Kruskal oder dijkstra sind greedy algorithmen
was heisst wenn ein lp unbeschränkt ist?
es gibt unendlich viele zulässige Lösungen mit beliebig hohen Zielfunktionswerten (z. B. max { x | x ≥ 0 } ).
Wie entsteht ein Steiner Baum und was sucht er?
Ein steiner Baum entsteht wenn alle obligatorischen Knoten aus N und zusätzlich (muss nicht sein) die fakultativen Knoten, also die Steiner Knoten benutzt werden um jeden obligatorischen Knoten im Baum ohne Zyklen zu erreichen.
das Problem des minimalen Steiner Baums besteht darin, unter allen möglichen Steiner Bäumen von G, einen mit minimalem Gewicht zu finden.
was gibt ein Schattenpreis an?
Ein Schattenpreis einer Restriktion gibt an, wie viel sich der Zielfunktionswert ändert, wenn die Kapazität der entsprechenden Ressource um eine Einheit erhöht wird.
Wenn das Primalproblem unbeschränkt ist, was ist dann mit dessen Dualproblem?
- unbeschränkt
- unzulässig
- optimal
dann ist dessen D unzulässig, weil das P gegen unendlich geht und wenn man es kehrt, geht das D gegen minus unendlich, was nicht zulässig ist
in einem ungerichtetem, schlichtem Graphen G=(V,E) entspricht die SUmme aller Knotengerade der doppelten Anzahl der Kanten wieso?
ich weiss e=(v,w), Kante e verbindet Knoten v und w
Knotengerade deg(v) und deg(w), werden zweimal gezählt
siehe inzidenzmatrix , doppelt so viele Kanten wie Knoten
in einem ungerichtetn, schlichten Graphen G=(V,E) ist die Anzahl Knoten mit ungeradem Grad gerade. was bedeutet das?
In jdem Graphen gibt es eine gerade Anzahl Knoten mit ungeradem Knotengrad → da Kanten immer zweimal gezählt werden, kann es gar nie eine ungerade Anzahl geben.
was macht der floyd warshall alogrithmus?
- im ungerichtetem/gerichtetem Graphen sucht er nach dem kürzesten Wegen von jedem Knoten i zu jedem Knoten j
- Zyklen sind erlaubt
- erkennt negative Zyklen
- für den längsten Weg, einfach Vorzeichen wechseln
