Operations Research Kurzfragen

Question	Answer
1.: Beim Simplex-Algorithmus sind die Schattenpreise der Ressourcennutzung an den Werten der Schlupfvariablen im Endtableau ablesbar.	1.: NEIN, die Zielfunktions-Koeffizienten sind die Schattenpreise (Kap. 2, Folie 47)
2.: Die duale Simplexmethode kann als Verfahren zur Bestimmung einer zulässigen Ausgangslösung genutzt werden.	2.: JA (Kap. 4, Folie 12)
3.: Die optimale Lösung eines primalen linearen Programms ist identisch mit der optimalen Lösung des zugehörigen dualen Programms.	3.: JA (Kap. 4, Folie 21 ff.)
4.: Kurzzyklen erhöhen die Lösungsqualität beim Traveling Salesman Problem.	4.: NEIN, wenn Kurzzyklen existieren, ist es keine gültige TSP-Lösung mehr (Kap. 9, Folie 9)
5.: Simulated Annealing führt niemals zur optimalen Lösung eines Rucksackproblems.	5.: JA (irrelevant, nicht behandelt!)
1.: Das Traveling Salesman Problem kann als klassisches Zuordnungsproblem formuliert werden.	1.: JA (Kap. 9, Folie 8)
2.: Der Lösungswert für ein TSP ohne Zyklusbedingungen ist eine untere Grenze für den Wert der optimalen Lösung.	2.: JA (Kap. 9, Folie 13)
3.: Im Selektionsschritt eines Genetischen Algorithmus kann eine Lösung mehrfach als Elternteil ausgewählt werden.	3.: JA (Vgl. Kap. 11, Folie 33)
4.: Immer dann, wenn bei der Tabusuche eine unzulässige Lösung betrachtet wird, gerät das Verfahren ins Kreisen.	4.: NEIN, nur Strafkosten (Kap. 11, Folie 12 ff.)
5.: Transportprobleme können aufgrund ihrer Ganzzahligkeit mit dem Simplex-Algorithmus nicht optimal gelöst werden.	5.: NEIN, bei unimodularer Matrix ist es möglich. (Kap. 5, Folie 7)
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.	1.: NEIN, nur im Optimum (Kap. 5, Folie 11)
2.: Im Separationsschritt des Branch & Bound Verfahrens wird entschieden, in welchem Teilproblem das Verfahren fortgesetzt wird.	2.: NEIN, das ist die Auslotung (Kap. 5, Folie 12)
3.: Der Simplex-Algorithmus kann Teil des Branch & Bound Verfahrens sein.	3.: JA (Vgl. Tutorium #3 vom 05.12.12)
4.: Das Branch & Bound Verfahren liefert immer eine optimale Lösung.	4.: JA (Vgl. Kap. 5, Folie 10 ff.)
5.: Das Branch & Bound Verfahren kann nur zur Lösung binärer linearer Programme verwendet werden.	5.: NEIN, auch für andere Probleme (Kap. 5, Folie 32)
1.: Eine Optimale Lösung eines linearen Programms mit reellwertigen Variablen kann in einigen Fällen außerhalb des zulässigen Bereiches liegen.	1.: NEIN, dann wäre sie nicht durchführbar  nicht optimal (?)
2.: Jedes Lineare Programm kann graphisch gelöst werden.	2.: NEIN, bei mehr als 2 Strukturvariablen (theoretisch 3  3D) nicht mehr möglich (?)
3.: Ein Basistausch des Simplex-Algorithmus kann zur Bestimmung einer zulässigen Lösung genutzt werden.	3.: JA (Kap. 2, Folie 15)
4.: Der duale Simplex-Algorithmus kann zur Bestimmung einer zulässigen Lösung genutzt werden.	4.: JA (Vgl. Kap. 4, Folie 12)
5.: Wenn der Zielfunktionswert des primalen Programms dem Zielfunktionswert des dualen Programms entspricht, sind die jeweils zugehörigen Lösungen optimal.	5.: JA (Vgl. Kap. 4, Folie 28) (?)
1.: Heuristische Lösungsverfahren können nur zur Lösung NP-schwerer Optimierungsprobleme eingesetzt werden.	1.: NEIN, auch zur Lösung von P-Problemen (Kap.10, Folie 6)
2.: Ein Verbesserungsverfahren für das binäre Rucksackproblem kann ohne Festlegung einer Nachbarschaft durchgeführt werden.	2.: NEIN, Verbesserungsverfahren = Untersuchen der Nachbarschaft (Kap. 10, Folie 50)
3.: Das Traveling Salesman Problem kann prinzipiell mit dem Branch & Bound Verfahren gelöst werden.	3.: JA (Kap. 5, Folie 32)
4.: Die Lösung eines Traveling Salesman Problems mit einem Genetischen Algorithmus erfordert zwingend die Repräsentation einer Lösung mittels Permutationscodierung.	4.: NEIN, auch andere Möglichkeiten (Kap. 11, Folie 23)
5.: Die Tabusuche mit einer statischen Tabuliste kann mit starrer oder flexibler Listelänge durchgeführt werden.	5.: JA (kap. 11, Folie 13)
1.: Der Simplex-Algorithmus kann Teil des Branch & Bound Verfahrens sein.	1.: JA (Vgl. Tutorium #3 vom 05.12.12)
2.: Metaheuristiken verbieten die Verschlechterung des Zielfunktionswertes um möglichst schnell zur optimalen Lösung zu gelangen.	2.: NEIN, genau das macht METAheuristiken aus (Vgl. Kap. 11, Folie 11 ff.)
3.: Simulated Annealing führt niemals zur optimalen Lösung eines Traveling Salesman Problems.	3.: JA (irrelevant, nicht behandelt!)
4.: Das 2opt Verfahren liefert eine Ausgangslösung für ein Traveling Salesman Problem.	4.: NEIN, dort beginnt es (Kap. 10, Folie 52)
5.: In einem Pfad eines Graphen können Knoten mehrfach vorkommen.	5.: JA (Kap. 7, Folie 10)
1.: Bei zwei komplementären Zielen entsteht ein Zielkonflikt.	1.: NEIN, bei konkurrierenden der Fall (Kap. 3, Folie 30)
2.: Das Traveling Salesman Problem lässt sich mit polynomiellem Aufwand lösen.	2.: Nein (Kap. 9, Folie 5)
3.: In einem Euler-Netzwerk besitzt jeder Knoten einen ungeraden Knotengrad.	3.: NEIN, geraden Knotengrad (Kap. 8, Folie 19)
4.: Der 2-opt zählt zu den heuristischen Lösungsverfahren für Traveling Salesman Probleme.	4.: NEIN, lediglich Verbesserung und nicht Lösung (Kap. 10, Folie 52)
5.: Nach der Dualisierung eines linearen Programms muss der duale Simplex angewendet werden um die optimale Lösung zu finden.	5.: JA (Kap. 4, Folie 27)
1.: Für ein TSP mit N Städten gibt es (N—1)! alternative Traveling Salesman Touren.	1.: JA (kap. 9, Folie 5)
2.: Das Erlauben von Kurzzyklen erhöht die Lösungsqualität beim Traveling Salesman Problem.	2.: NEIN, wenn Kurzzyklen existieren, ist es keine gültige TSP-Lösung mehr (Kap. 9, Folie 9)
3.: Besteht ein Baum aus n-1 Kanten so hat er n-1 Knoten.	3.: NEIN, er hätte n Knoten (Definition: n Knoten = n-1 Kanten) (Kap. 7, Folie 15)
4.: Das Verfahren des besten Nachfolgers für Traveling Salesman Probleme fällt in die Klasse der Greedy-Verfahren.	4.: JA (Kap. 10, Folie 13)
5.: Das Netzwerkflussproblem ist ein lineares Optimierungsproblem und damit grundsätzlich mit dem Simplex-Algorithmus lösbar.	5.: JA (Kap. 8, Folie 7)
1.: Mittels Sensitivitätsanalyse kann die Lösungsqualität bei linearen Programmierung erhöht werden.	1.: NEIN, nur in welchem Bereich sich die opt. Lösung nicht ändert (Kap. 3, Folie 4)
2.: Das Branch & Bound Verfahren kann unter Umständen zur vollständigen Enumeration tendieren.	2.: JA (Kap. 5, Folie 32)
3.: Kein ganzzahliges lineares Programm kann mit dem Simplex-Algorithmus gelöst werden.	3.: NEIN, bei unimodularer Matrix ist es möglich. (Kap. 5, Folie 7)
4.: In einem zusammenhängendem Graphen beinhaltet der spannende Baum alle Knoten.	4.: JA (Kap. 7, Folie 15) (Vgl. auch Wikipedia „Spannbaum“)
5.: Ein lineares Programm mit 2 Nebenbedingungen kann nach einer Dualisierung meist mit dem Kruskal-Algorithmus gelöst werden.	5.: NEIN, der Kruskal-Alg. ist ein „Greedy-Alg.“ zur Graphentheorie (Kap. 7, Folie 19 ff.) (?)
1.: Der Dijkstra-Algorithmus liefert eine untere Schranke für das Traveling Salesman Problem.	1.: NEIN, Kruskal-Alg. würde „Untere Schranke“ liefern. Dijkstra gibt lediglich Entfernung zwischen den einzelnen Knoten an (Kap. 7, Folie 24 ff.) (?)
2.: Das dynamische Losgrößenproblem lässt sich als kürzeste Wege Problem formulieren.	2.: JA (kap. 7, Folie 36)
3.: In jedem zusammenhängendem Netzwerk N = (V,E) ist die Anzahl von Knoten mit ungeradem Knotengrad gleich Null oder eine gerade positive Zahl.	3.: JA (Kap. 8, Folie 21)
4.: Heuristiken weisen meiste eine höhere Laufzeit auf als exakte Verfahren, dafür liefern sie aber auch bessere Ergebnisse.	4.: NEIN, Heuristiken = „Pi mal Daumen“, dafür schneller (Kap. 10, Folie 7)
5.: Das Netzwerkflussproblem kann mit dem Simplex-Algorithmus gelöst werde.	5.: JA (Kap. 8, Folie 7)
Definieren Sie die Begriffe Euler-Netzwerk und Euler-Tour.	EN: Zusammengehöriges Netzwerks, in dem jeder Knoten einen geraden Knotengrad von mindestens zwei hat. ET: Ein Zyklus in einem EN, bei dem jede Kante genau einmal durchlaufen wird.

Next up

Operations Research Kurzfragen

Description

Resource summary

Similar

	Created by Robin Ga almost 10 years ago

	Copied by Thuyen Yen Huynh over 7 years ago