Bei den prozessbezogenen Produktionstypen unterscheiden wir nach dem Organisationstyp der Produktion das Funktionsprinzip und das Objektprinzip. Erl¨autern Sie diese Prinzipien
Beim Funktionsprinzip werden Arbeitssysteme, die gleichartige Funktionen durchfuhren k ¨ ¨onnen, r¨aumlich zu Werkst¨atten zusammengefasst (Werkstattproduktion). Im Gegensatz dazu orientiert sich beim Objektprinzip die Anordnung der Arbeitssysteme an den Arbeitspl¨anen der zu bearbeitenden Erzeugnisse.
Beschreiben Sie, wie sich exakte Verfahren von Heuristiken unterscheiden
Wir bezeichnen einen Algorithmus zur L¨osung eines Optimierungsproblems als exaktes Verfahren, wenn er fur jede beliebige Probleminstanz garantiert eine optimale L ¨ ¨osung und/oder deren Zielfunktionswert bestimmt oder korrekt feststellt, dass eine optimale L¨osung nicht existiert. Der Algorithmus heißt (vereinfacht gesprochen, Details: siehe Vorlesung) Heuristik, wenn er lediglich auf die Bestimmung (m¨oglichst guter) zul¨assiger L¨osungen abzielt.
Beschreiben Sie, wie Eingabe und L¨osungen in Mathematischen Optimierungsmodellen (MO) repr¨asentiert werden.
In einem MO wird die Eingabe durch Parameter repr¨asentiert. Parameter sind dabei vorgegebene und unver¨anderliche Symbole, die erst durch eine Probleminstanz (explizit oder implizit) mit konkreten Werten belegt werden. L¨osungen werden durch Variablen repr¨asentiert, deren Dom¨anen erlaubte Wertebereiche vorgeben.
Geben Sie ein beliebiges MO an, das kein LP ist
In einem LP ist die Nebenbedingung x1 +x_2 = 10 zu berucksichtigen. Transformieren Sie diese = Nebenbedingung in zwei aquivalente ≤ Nebenbedingungen.
x1 + x2 ≤ 10 und −x1 − x2 ≤ −10
Illustrieren Sie graphisch ein beliebiges LP mit zwei Variablen, das unendlich viele optimale Lösungen hat. Kennzeichnen Sie die Menge der optimalen Lösungen eindeutig.
Illustrieren Sie graphisch ein beliebiges primal degeneriertes LP mit zwei Variablen
Woran erkennt der primale Simplex-Algorithmus, dass ein unbeschr¨anktes LP vorliegt?
) Der Algorithmus w¨ahlt eine Pivot-Spalte mit negativen reduzierten Kosten. Dort befinden sich ausschließlich nichtpositive Eintr¨age
Nehmen Sie an, Sie erlauben auch primal degenerierte LPs als Eingabe fur den Simplex- ¨ Algorithmus. Wie k¨onnen Sie in einem Simplextableau zu einem beliebigen LP und zu einem beliebigen Zeitpunkt der Ausfuhrung des primalen Simplex-Algorithmus erkennen, ob ¨ die aktuell betrachtete Basisl¨osung primal degeneriert ist?
Aus der Vorlesung wissen Sie: Wenn es einen zul¨assigen Eckpunkt gibt, in dem mehr als n NB/NNB mit Gleichheit erfullt sind, dann existiert eine Basisl ¨ ¨osung, in der (mindestens) eine BV den Wert Null annimmt. Wir bezeichnen eine derartige Basisl¨osung als primal degeneriert. Im Simplex-Algorithmus liegt dann ein Tableau vor, in dem ein Eintrag in der “RHS”-Spalte, der nicht den aktuellen Zielfunktionswert repr¨asentiert, den Wert Null aufweist.
Warum werden in Schritt 5.1 des primalen Simplex-Algorithmus (Bestimmung der Pivotzeile) Zeilen i mit nichtpositiven Eintr¨agen a ′ i,j nicht berucksichtigt?
Die mit einer solchen Zeile korrespondierende BV wurde mit steigendem Wert der bisherigen ¨ NBV xj (Schritt 2), die in die Basis aufgenommen werden soll, entweder gr¨oßer werden (im Falle eines negativen Eintrags) oder gleich bleiben (im Falle einer Null). Somit ist ein (eindeutiger) Basiswechsel nicht m¨oglich. Die NBV k¨onnte beliebig weit erh¨oht werden, ohne den Wert der BV zu verringern.
Warum ist es in Schritt 1 des primalen Simplex-Algorithmus wichtig, dass das LP in Standardform mit nichtnegativen rechten Seiten vorliegt?
Wurden negative rechte Seiten vorkommen, wäre die in Schritt 1 bestimmte Basislösung nicht zulässig, da mindestens eine BV einen negativen Wert hätte.
Zuletzt geändertvor einem Monat
