Operations Research Kurzfragen

1.: Beim Simplex-Algorithmus sind die Schattenpreise der Ressourcennutzung an den Werten der
Schlupfvariablen im Endtableau ablesbar.

2.: Die duale Simplexmethode kann als Verfahren zur Bestimmung einer zulässigen Ausgangslösung
genutzt werden.

3.: Die optimale Lösung eines primalen linearen Programms ist identisch mit der optimalen Lösung
des zugehörigen dualen Programms.

4.: Kurzzyklen erhöhen die Lösungsqualität beim Traveling Salesman Problem.

5.: Simulated Annealing führt niemals zur optimalen Lösung eines Rucksackproblems.

1.: Das Traveling Salesman Problem kann als klassisches Zuordnungsproblem formuliert werden.

2.: Der Lösungswert für ein TSP ohne Zyklusbedingungen ist eine untere Grenze für den Wert der
optimalen Lösung.

3.: Im Selektionsschritt eines Genetischen Algorithmus kann eine Lösung mehrfach als Elternteil
ausgewählt werden.

4.: Immer dann, wenn bei der Tabusuche eine unzulässige Lösung betrachtet wird, gerät das
Verfahren ins Kreisen.

5.: Transportprobleme können aufgrund ihrer Ganzzahligkeit mit dem Simplex-Algorithmus nicht
optimal gelöst werden.

1.: Bei der Durchführung des Branch & Bound Verfahrens gilt zu jedem Zeitpunkt, dass die größte
untere Schranke gleich der kleinste oberen Schranke ist.

2.: Im Separationsschritt des Branch & Bound Verfahrens wird entschieden, in welchem Teilproblem
das Verfahren fortgesetzt wird.

3.: Der Simplex-Algorithmus kann Teil des Branch & Bound Verfahrens sein.

4.: Das Branch & Bound Verfahren liefert immer eine optimale Lösung.

5.: Das Branch & Bound Verfahren kann nur zur Lösung binärer linearer Programme verwendet
werden.

1.: Eine Optimale Lösung eines linearen Programms mit reellwertigen Variablen kann in
einigen Fällen außerhalb des zulässigen Bereiches liegen.

2.: Jedes Lineare Programm kann graphisch gelöst werden.

3.: Ein Basistausch des Simplex-Algorithmus kann zur Bestimmung einer zulässigen Lösung
genutzt werden.

4.: Der duale Simplex-Algorithmus kann zur Bestimmung einer zulässigen Lösung genutzt
werden.

5.: Wenn der Zielfunktionswert des primalen Programms dem Zielfunktionswert des dualen
Programms entspricht, sind die jeweils zugehörigen Lösungen optimal.

1.: Heuristische Lösungsverfahren können nur zur Lösung NP-schwerer
Optimierungsprobleme eingesetzt werden.

2.: Ein Verbesserungsverfahren für das binäre Rucksackproblem kann ohne Festlegung einer
Nachbarschaft durchgeführt werden.

3.: Das Traveling Salesman Problem kann prinzipiell mit dem Branch & Bound Verfahren
gelöst werden.

4.: Die Lösung eines Traveling Salesman Problems mit einem Genetischen Algorithmus
erfordert zwingend die Repräsentation einer Lösung mittels Permutationscodierung.

5.: Die Tabusuche mit einer statischen Tabuliste kann mit starrer oder flexibler Listelänge
durchgeführt werden.

1.: Der Simplex-Algorithmus kann Teil des Branch & Bound Verfahrens sein.

2.: Metaheuristiken verbieten die Verschlechterung des Zielfunktionswertes um möglichst
schnell zur optimalen Lösung zu gelangen.

3.: Simulated Annealing führt niemals zur optimalen Lösung eines Traveling Salesman
Problems.

4.: Das 2opt Verfahren liefert eine Ausgangslösung für ein Traveling Salesman Problem.

5.: In einem Pfad eines Graphen können Knoten mehrfach vorkommen.

1.: Bei zwei komplementären Zielen entsteht ein Zielkonflikt.

2.: Das Traveling Salesman Problem lässt sich mit polynomiellem Aufwand lösen.

3.: In einem Euler-Netzwerk besitzt jeder Knoten einen ungeraden Knotengrad.

4.: Der 2-opt zählt zu den heuristischen Lösungsverfahren für Traveling Salesman Probleme.

5.: Nach der Dualisierung eines linearen Programms muss der duale Simplex angewendet
werden um die optimale Lösung zu finden.

1.: Für ein TSP mit N Städten gibt es (N—1)! alternative Traveling Salesman Touren.

2.: Das Erlauben von Kurzzyklen erhöht die Lösungsqualität beim Traveling Salesman
Problem.

3.: Besteht ein Baum aus n-1 Kanten so hat er n-1 Knoten.

4.: Das Verfahren des besten Nachfolgers für Traveling Salesman Probleme fällt in die Klasse
der Greedy-Verfahren.

5.: Das Netzwerkflussproblem ist ein lineares Optimierungsproblem und damit grundsätzlich
mit dem Simplex-Algorithmus lösbar.

1.: Mittels Sensitivitätsanalyse kann die Lösungsqualität bei linearen Programmierung erhöht
werden.

2.: Das Branch & Bound Verfahren kann unter Umständen zur vollständigen Enumeration
tendieren.

3.: Kein ganzzahliges lineares Programm kann mit dem Simplex-Algorithmus gelöst werden.

4.: In einem zusammenhängendem Graphen beinhaltet der spannende Baum alle Knoten.

5.: Ein lineares Programm mit 2 Nebenbedingungen kann nach einer Dualisierung meist mit
dem Kruskal-Algorithmus gelöst werden.

1.: Der Dijkstra-Algorithmus liefert eine untere Schranke für das Traveling Salesman
Problem.

2.: Das dynamische Losgrößenproblem lässt sich als kürzeste Wege Problem formulieren.

3.: In jedem zusammenhängendem Netzwerk N = (V,E) ist die Anzahl von Knoten mit
ungeradem Knotengrad gleich Null oder eine gerade positive Zahl.

4.: Heuristiken weisen meiste eine höhere Laufzeit auf als exakte Verfahren, dafür liefern sie
aber auch bessere Ergebnisse.

5.: Das Netzwerkflussproblem kann mit dem Simplex-Algorithmus gelöst werde.

Definieren Sie die Begriffe Euler-Netzwerk und Euler-Tour.