Lineare Optimierung

Beim Funktionsprinzip werden Arbeitssysteme, die gleichartige Funktionen durchführen können, räumlich zu Werkstätten zusammengefasst (Werkstattproduktion)

beim Objektprinzip orientiert sich die Anordnung der Arbeitssysteme an den Arbeitsplänen der zu bearbeitenden Erzeugnisse

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

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

x1 +x2 <= 10 und -x1 -x2 <= -10

Der Algorithmus wählt eine Pivot-Spalte mit negativen reduzierten Kosten. Dort befinden sich ausschließlich nichtpositive Einträge.

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.

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.

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