Funktionsprinzip
Beim Funktionsprinzip werden Arbeitssysteme, die gleichartige Funktionen durchführen können, räumlich zu Werkstätten zusammengefasst (Werkstattproduktion)
Objektprinzip
beim Objektprinzip orientiert sich die Anordnung der Arbeitssysteme an den Arbeitsplänen der zu bearbeitenden Erzeugnisse
wie unterscheiden sich exakte Verfahren von Heuristiken
Wir bezeichnen einen Algorithmus zur Lösung eines Optimierungsproblems als exaktes Verfahren, wenn er für jede beliebige Probleminstanz garantiert eine optimale Lösung bestimmt oder korrekt feststellt, dass eine optimale Lösung nicht existiert. Der Algorithmus heißt Heuristik, wenn er lediglich auf die Bestimmung (möglichst guter) zulässiger Lösungen abzielt
wie werden Eingabe und Lösungen in Mathematischen Optimierungsmodellen (MO) repräsentiert
In einem MO wird die Eingabe durch Parameter repräsentiert
Parameter sind dabei vorgegebene und unveränderliche Symbole, die erst durch eine Probleminstanz mit konkreten Werten belegt werden
Lösungen werden durch Variablen repräsentiert
beliebiges MO, das kein LP ist
die NB x1 + x2 = 10 in zwei NB transformieren
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änktes LP vorliegt?
Der Algorithmus wählt eine Pivot-Spalte mit negativen reduzierten Kosten. Dort befinden sich ausschließlich nichtpositive Einträge.
Nehmen Sie an, Sie erlauben auch primal degenerierte LPs als Eingabe für den Simplex- Algorithmus. Wie können Sie in einem Simplextableau zu einem beliebigen LP und zu einem beliebigen Zeitpunkt der Ausführung des primalen Simplex-Algorithmus erkennen, ob die aktuell betrachtete Basislösung primal degeneriert ist?
Wenn es einen zulässigen Eckpunkt gibt, in dem mehr als n NB/NNB mit Gleichheit erfüllt sind, dann existiert eine Basislösung, in der (mindestens) eine BV den Wert Null annimmt. Wir bezeichnen eine derartige Basislösung 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äsentiert, den Wert Null aufweist.
Warum werden in Schritt 5.1 des primalen Simplex-Algorithmus Zeilen i mit nichtpositiven Einträgen nicht berücksichtigt?
Die mit einer solchen Zeile korrespondierende BV würde mit steigendem Wert der bisherigen NBV, die in die Basis aufgenommen werden soll, entweder größer werden (im Falle eines negativen Eintrags) oder gleich bleiben (im Falle einer Null). Somit ist ein (eindeutiger) Basiswechsel nicht möglich. Die NBV könnte beliebig weit erhöht werden, ohne den Wert der BV zu verringern.
Warum ist es in Schritt 1 des primalen Simplex-Algorithmus wichtig, dass das LP in Standardform und nicht mit nichtnegativen rechten Seiten vorliegt?
Würden 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
Last changed2 years ago
