Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

1818SS Operations Research (GDL-OR) > FT-Karteikarten > Flashcards

FT-Karteikarten Flashcards

1
Q

Ist eine Kante mit minimalem Gewicht im

zugehörigen minimalen Spannbaum enthalten?

A

Nein. (Begründung: Kanten mit minimalem
Gewicht könnten einen Kreis bilden. Bäume sind
Kreisfrei!)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Kann man Kruskals Algorithmus auch verwenden,

um einen maximalen Spannbaum zu berechenen?

A

Ja. Man bevorzugt Kanten mit höherem Gewicht

oder gewichtet die Kanten neu.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Nennen Sie die Definition eines Graphen

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist in einem Multigraphen erlaubt?

A

In Multigraphen sind parallele Kanten (wenn

gerichtet: in die gleiche Richtung) erlaubt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist ein endlicher Graph?

A

Ein Graph dessen Mengen der Knoten und Kanten

endlich ist.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wie nennt man einen Graphen ohne parallele

Kanten und ohne Schlinge?

A

schlichter Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Was ist ein Digraph?

A

Ein schlichter gerichteter Graph mit endlicher

Knotenmenge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist ein Zyklus?

A

Ein Zyklus ist ein geschlossener Weg. Ein Weg ist
die Folge von gerichteten Kanten, jeweils in
Pfeilrichtung.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist ein vollständiger Digraph?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Wie heißt ein ungerichteter schlichter Graph, wenn
für jedes Knotenpaar i,j eine Kante von i nach j
existiert?

A

vollständiger schlichter Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Wie heißt ein Graph, bei dem jedes Knotenpaar

durch mindestens eine Kette verbunden ist?

A

zusammenhängender Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist ein zusammenhängender, kreisfreier und

ungerichteter Graph?

A

Ein ungerichteter Baum

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was ist ein gerichteter Baum?

A

Ein gerichteter, kreisfreier Graph mit genau einem

Ausgangsknoten

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Was ist die Adjazenzmatrix?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Was ist die Inzidenzmatrix?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wann wird ein Graph als gewichteter Graph

bezeichnet?

A 
Wenn alle Kanten E eines Graph g(V,E,w) mit
Werten w(e) versehen sind.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Was muss gelten, damit ein Subgraph (V’,E’) von

einem ungerichtetem Graph ein Spannbaum ist?

A 
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Was ist das Gewicht eines Spannbaums?

A

Die Summe aller seiner Kantengewichte.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Was ist ein minimaler Spannbaum?

A

Ein Spannbaum mit dem minimalen Gewicht unter

allen Spannbäumen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Nenne zwei Beispiele für die Anwendung von

Spannbäumen!

A

1 Linienplanung für den öffentlichen
Personenverkehr
2 Kostengünstige
Anschlusskabel für Internet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Welche Bedingungen hat der Kruskal-

Algorithmus?

A

Der Graph muss endlich, ungerichtet ,

zusammenhängend und gewichtet sein.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Wozu dient der Kruskal-Algorithmus?

A

Mit dem Kruskal-Algorithmus kann man einen

minimalen oder maximalen Spannbaum finden.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Wann wird eine Kante beim Kruskal-Algorithmus
nicht in den minimalen Spannbaum mit
aufgenommen?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Wozu dient der Dijkstra-Algorithmus?

A

Mithilfe des Dijkstra-Algorithmus kann man den
kürzesten Weg von einem Knoten zu allen
anderen Knoten finden.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Ist ein Teilweg von einem kürzesten Weg selbst

immer ein kürzester Weg?

A

Ja.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Wie kann der Dijkstra-Algorithmus angepasst
werden, damit zunächst alle Kanten mit den
kleinsten Kantengewichten verwendet werden?

A

Vor der Anwendung des Dijkstra-Algorithmus ist

eine Neugewichtung der Kanten erforderlich.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Wann ist der Dijkstra-Algorithmus beendet?

A

Wenn die Menge der markierten Knoten der

Menge aller Knoten entspricht.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Wann funktioniert der Dijkstra-Algorithmus nicht?

A

Bei negativen Kantengewichten.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Was ist der entscheidende Vorteil vom Bellman-
Ford-Algorithmus gegenüber dem Dijkstra-
Algorithmus?

A

Er funktioniert auch bei negativen

Kantengewichten. Und erkennt negative Zyklen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Wie lautet das Prinzip der optimalen Substruktur?

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Was sind die Abruchkriterien des Bellman-Ford-

Algorithmus?

A

-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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Was bedeutet es, wenn beim Bellman-Ford-
Algorithmus auf der Hauptdiagonalen in der
Bewertungsmatrix negative Werte Auftreten?

A

Es zeigt, dass es einen negativen Zyklus gibt. Es

gibt keine Lösung.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Was versteht man unter einem linearen

Optimierungs- oder Programmierungsproblem?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Was ist der zulässige Bereich?(LP)

A

Die Menge der Punkte, die die Nebenbedingungen

erfüllen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Wozu dienen Schlupfvariablen?

A

Schlupfvariablen werden bei einer Ungleichung auf
einer Seite addiert, um die Ungleichung in eine
Gleichung umzuformen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Was ist eine zulässige Lösung in einem LP?

A 
Ein Punkt (oder Vektor) der alle
Nebenbedingungen Erfüllt.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Was ist eine zulässige Lösung in einem LP?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Wann ist eine Lösung eines LP optimal?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Wie findet man grafisch die optimale Lösung eines

LP?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Was ist bei der Verwendung einer Gleichung als
Nebenbedingung bei der Erstellung der
Standardform eines LP zubeachten?

A

Die Gleichung muss in eine „Größergleich-“ und
eine „Kleinergleich-“ Ungleichung aufgeteilt
werden.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Was sind Strukturvariablen?

A

Strukturvariablen sind keine Schlupfvariablen. Sie

sind die Variablen des Ursprünglichen Problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Wann spricht man von der Standardform eines

LP?

A

Maximierungsfunktion; Nur Gleichungen (Schlupf);
Nichtnegativitätsbedingung, alle variablen
links(auch in zf)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Was gilt bezüglich der Konvexität der

Lösungsmenge Eines LP in Standardform?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

Wieviele Eckpunkte der Lösungsmenge berührt

die optimale Zielfunktion immer?

A

mindestens Einen. Höchstens so viele wie es

Strukturvariablen gibt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Was gilt für die Menge aller optimalen Lösungen

eines LPs bezüglich Konvexität?

A

Die Menge aller optimalen Lösungen eines LPs ist
immer konvex. (Sind zwei Punkte eine optimale
Lösung, so sind es auch alle dazwischen)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Welchen Wert hat eine Nicht-Basisvariable in der

Basislösung?

A

Null

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Wann ist ein Punkt einer konvexen Menge ein

Eckpunkt?

A

Wenn er sich nicht als echte Linearkombination
zweier verschiedener Punkte der Menge darstellen
lässt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Definition für konvexe und echte

Linearkombination

A

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?

49
Q

Was gilt für die konvexe Linearkombination?

A

Linearkombination mit Skalaren größergleich Null

und in Summe 1

50
Q

Was gilt für die echte Linearkombination?

A

Linearkombination mit Skalaren echt größer Null

und in Summe 1.

51
Q

Wie sieht die allgemeine Form eines LP aus?

A

Hier 4.1.b) Lösung einfügen

52
Q

Wofür steht die Abkürzung s.t.?

A

Subjekt to (Nebenbedingungen)

53
Q

Schritte von allgemeiner zur Standardform eines

LP

A

-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)

54
Q

Wie zeigt sich die Unbeschränktheit eines LP im

primalen Simplex?

A

Es lässt sich kein Pivotelemnt finden(Alle a_ij

negativ) ??Was wenn mehrere b_i negativ??

55
Q

Was passiert im dualen simplex, wenn es keine

zulässige Lösung gibt?

A

Es lässt sich kein Pivotelemnt finden(Alle a_ij

positiv)

56
Q

Was macht man mit einer Gleichung(=) bei der

erstellung der Standardform?

A

Man teilt sie auf in eine kleiner und größer

Ungleichung

57
Q

Wann gibt es keine zulässige Lösung?

A

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)

58
Q

Was ist duale Degeneration?

A

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!

59
Q

Was ist primale Degeneration? Woran erkennt

man sie im Tableau?

A

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.

60
Q

Was besagt die MUB im Branch and Bound?

A

Auswahlstrategie für Teilproblem. Maximum Upper
Bound. Wähle Problem mit größtem
Zielfunktionswert aus der Liste.(Branch and
Bound)

61
Q

Was besagt die FIFO-Methode im Branch and

Bound Algorithmus?

A

First In First Out. Wähle Problem aus der Liste,

das zuerst eingeführt wurde.

62
Q

Was besagt die LIFO-Methode im Branch and

Bound Algorithmus?

A

Auswahlstrategie für Teilproblem. Last In First Out.
Wähle Problem aus der Liste, das zuletzt
eingeführt wurde.

63
Q

Wodurch zeichnet sich ein Rucksackproblem aus?

A

1Zielfunktion(Nutzen)+
1Nebenbedingung(Gewicht)
+Entscheidungsvariablen sind 1 oder Null

64
Q

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.

A

?Richtig?

65
Q

RoF?: Der Kruskal-Algorithmus kann auch
verwendet werden um einen maximalen
Spannbaum zu berechnen.

A

Richtig. Man bevorzugt einfach die Kanten mit

maximalem Gewicht.

66
Q

RoF?: Ein Knoten ohne Nachfolger heißt Quelle.

A

Falsch. Er heißt Senke bzw in eine Quelle gehen

mehr Kanten hinein als hinaus.

67
Q

RoF?: Ein Spannbaum ist ein Subgraph, der

alle Knoten des Ursprungsgraphen umfasst.

A

Richtig

68
Q

RoF?: Eine Kante mit minimalem Gewicht ist
immer im zugehörigen minimalen Spannbaum
enthalten.

A

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.

69
Q

RoF?: Die Anzahl der Optimallösungen eines

linearen Programms ist immer endlich.

A

Falsch. Ein LP kann keine, unendlich viele oder

eine Lösung haben

70
Q

RoF?: Jedes LP kann als
Maximierungsproblem oder
Minimierungsproblem dargestellt werden.

A

Richtig. Man multipliziert die Zielfunktion mit -1 zur

Umformung

71
Q

Rof?: Ein Punkt Y heißt Eckpunkt einer
konvexen Menge, wenn er sich nicht als echte
Linearkombination zweier verschiedener
Punkte darstellen lässt.

A

Richtig

72
Q

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.

A

Richtig. (Komplementärer Schlupf)

73
Q

RoF?: Die Summe von Entscheidungen in der
dynamischen Optimierung nennt man
Variante.

A

Falsch. Sie heißt Politik

74
Q

Wie zeigt sich Redundanz im Tableau?

A

Im Simplex-Tableau: Positive rechte Seite mit
Zeileneinträgen ausschließlich null oder
negativ.

75
Q

Wie erkennt man, dass es sich bei einem Tableau

um eine unzulässige Lösung handelt?

A

Mindestens ein b_i ist negativ. (Achtung! Nicht

Zielfunktionsert betrachten. Kann negativ sein)

76
Q

Wie erkennt man, dass es sich bei einem Tableau

um eine zulässige Lösung handelt?

A

alle bi positiv.(Achtung! Nicht Zielfunktionswert

betrachten. Dieser kann negativ sein)

77
Q

Wie erkennt man, dass es sich bei einem Tableau

um eine Optimallösung handelt?

A

Alle Einträge in der z-Zeile(c_j) positiv(Achtung:

nicht Zielfunktionswert betrachten!)

78
Q

Wie erkennt man Unbeschränktheit in einem

Tableau?

A

Eine Spalte mit nur negativen Einträgen. Es lässt

sich kein Pivotelement finden.

79
Q

Was ist ein schlichter Graph?

A

Ein Graph ohne Schlingen und parallele Kanten.

80
Q

Was gilt für einen ungerichteten Baum?

A

Er ist kreisfrei, ungerichtet und

zusammenhängend.

81
Q

Was gilt in einem zusammenhängendem

Graphen?

A

Jedes Knotenpaar ist durch mindestens eine Kette

miteinander verbunden.

82
Q

RoF?: Ein Unbeschränktes Problem hat eine

optimale Lösung.

A

Falsch

83
Q

RoF?: Um die dynamische Optimierung anwenden
zu können, muss eine geeignete Modellierung des
Problems vorliegen.

A

Richtig

84
Q

RoF?: Bei der dynamischen Optimierung existiert
eine Anzahl von Zuständen, die gemeinsam
betrachtet werden.

A

Falsch. Die Zustände werden separat betrachtet.

85
Q

Was beeinflusst die Zielfunktion bei der

dynamischen Optimierung?

A

Die gesammte Politik (Die Summe der Entscheidungen)

86
Q

Was ist das Grundprinzip der dynamischen

Optimierung?

A

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.

87
Q

Was ist die Idee hinter der Dynamischen

Optimierung?

A

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).

88
Q

RoF?: Die dynamische Optimierung ist ein

Algorithmus.

A

Falsch. Es ist eine allgemeines Prinzip.

89
Q

RoF?: Die dynamische Optimierung beschränkt

sich auf die Rückwärtsrechnung.

A

Falsch. Es gibt Rückwärts und Vorwärtsrechnung

in der dynamischen Optimierung.

90
Q

RoF?: Die Dynamische Optimierung führt schneller

ans Ziel als die vollständige Enumeration.

A

Richtig. (Vollständige Enumeration=Alle zulässigen
Lösungen finden. Vergleich liefert Optimale
Lösung)

91
Q

Nennen Sie zwei Beispiele zur Anwendung der

dynamischen Optimierung!

A

1 Lagerhaltung

2 Kürzeste Wege

92
Q

Welche Entscheidungsmöglichkeiten betrachtet
man bei der typischen Modellierung des
Lagerhaltungsproblems zur Anwendung der
dynamischen Optimierung?

A

Man betrachtet, wie viele Waren man im Lager

halten kann.

93
Q

Wozu dient der Yen-Algorithmus?

A

Der Yen-Algorithmus findet die nächst längeren

Wege zum kürzesten weg.

94
Q

RoF?: Der Yen-Algorithmus liefert nur

schleifenfreie Ergebnisse.

A

Richtig

95
Q

RoF?: Ein Modell ist ein vereinfachtes,

zweckorientiertes Abbild eines realen Systems.

A

Richtig

96
Q

RoF?: Das Testen einer optimalen Lösung eines
linearen Programms bzgl. einer Veränderung der
Variablen bezeichnet man als Sensitivitäts- oder
Sensibilitätsanalyse.

A

Falsch. Man testet bzgl. der

Eingabedaten(Koeffizienten vor den Bedingungen)

97
Q

Wozu dient die Sensitivitätsanalyse?

A

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.

98
Q

Welche Annahmen benötigt die

Sensitivitätsanalyse?

A

LP (Maximierung, Strukturvariablen ,

Schlupfvariablen); Es liegt keine Degeneration vor

99
Q

RoF?: Es gibt immer so viele Nichtbasisvariablen
in einer Lösung eines LP, wie es Strukturvariablen
gibt.

A

Richtig

100
Q

Was ist ein relaxiertes Problem?

A

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.

101
Q

RoF?: Die Lösung eines relaxierten Problems
steht in einem trivialen Zusammenhang mit der
Lösung des Ausgangsproblems.

A

Falsch. Nicht-trivialer Zusammenhang

102
Q

Was ist der Zielerreichungsgrad?

A

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

103
Q

Findet der Yen-Algorithmus bei Schleifen

Anwendung?

A

Nein. (Begründung: Kanten mit minimalem
Gewicht könnten einen Kreis bilden. Bäume sind
Kreisfrei!)

104
Q

Wie heißt eine Lösung, die für jede Zielsetzung

optimal ist?

A

Perfekte Lösung

105
Q

Wie berechnet man den Zielerreichungsgrad?

A

Man teilt den Zielfunktionswert einer Lösung durch

den optimalen Zielfunktionswert.

106
Q

Welche Probleme gibt es bei der Lösung

multikriterieller LPs mit Zieldominanz?

A

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.

107
Q

Wie funktioniert die Lexikographische Ordnung

von Zielen?

A

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.

108
Q

RoF?: Der Zielerreichungsgrad des wichtigsten
Ziels ist bei der erfolgreichen Lösung mit
Lexikographischen Ordnung immer 1.

A

Richtig

109
Q

Wie funktioniert die Zieldominanz?

A

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)

110
Q

Was macht man bei der Zielgewichtung?

A

Bei der Zielgewichtung werden die verschiedenen
Ziele gewichtet. Sie werden mit Skalaren
versehen, die zwischen Null und eins sind und in
Summe eins.

111
Q

RoF?: Abstandsfunktionen sind häufig nicht-linear.
So werden Abweichungen schwächer bestraft, je
höher ihr Wert ist.

A

Falsch. So werden Abweichungen stärker bestraft.

112
Q

Beispiel für Fixkosten im LP

A

x_1≤BIG*Y_1

113
Q

Wenn Tische produziert werden, dann mindestens

25

A

x_1≤BIG*Y_1

25-x_1≤BIG(1-Y_1)

114
Q

Entweder x_1≤10 oder x_1≥20 im LP?

A

10-x_1≤BIG*Y_1

20-x_1≤BIG(1-Y_1)

115
Q

Wenn x_2+x_3>30 dann x_1≥50 im LP?

A

-30+x_2+x_3≤BIG*(Y_1)

50-x_1≤BIG(1-Y_1)

116
Q

Was ist die Grundidee des Add-Algorithmus?

A

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.

117
Q

RoF?: Der Add-Algorithmus findet beim

Warehouse Location Problem die beste Lösung.

A

Falsch. Der heuristische Algorithmus findet nur

eine gute Lösung. Nicht zwingend die Beste.

118
Q

Wie lässt sich am schnellsten herausfinden,
welches Ziel von welchem Lager beliefert wird?
(Warehouse Location Problem/Add-Algorithmus)

A

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.

119
Q

Wie lassen sich bei mit Add gelößtem Warehouse

Location Problem die Gesamtkosten bestimmen?

A

Kosten für das als erstes Eröffnete Lager
abzüglich der Ersparnis der später eröffneten
Lager.

1818SS Operations Research (GDL-OR) (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions