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 over 11 years ago