(a) Bei den prozessbezogenen Produktionstypen unterscheiden wir nach dem Organisationstyp
der Produktion das Funktionsprinzip und das Objektprinzip. Erläutern Sie diese Prinzi-
pien.
Beim Funktionsprinzip werden Arbeitssysteme, die gleichartige Funktionen durchführen können,
räumlich zu Werkstätten zusammengefasst (Werkstattproduktion). - Gliederung nach Tätigkeiten - schweißerei, Montage
Im Gegensatz dazu orientiert sich beim Objektprinzip die Anordnung der Arbeitssysteme an den Arbeitsplänen der
zu bearbeitenden Erzeugnisse. - Gliederung nach Produkten - Auto a, Auto B, Auto C
Beschreiben sie wie sich exakte Verfahren von heuristiken unterscheiden.
Wir bezeichnen einen Algorithmus zur L¨ osung eines Optimierungsproblems als exaktes Verfahren, wenn er f¨ ur 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 vorge-
gebene und unver¨ anderliche Symbole, die erst durch eine Probleminstanz (explizit oder im-
plizit) 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 + x2 = 10 zu berücksichtigen.
Transformieren Sie diese = Nebenbedingung in zwei ¨ aquivalente ≤Nebenbedingungen.
(f) Illustrieren Sie graphisch ein beliebiges LP mit zwei Variablen, das unendlich viele opti-
male Lösungen hat. Kennzeichnen Sie die Menge der optimalen Lösungen eindeutig.
(g) Illustrieren Sie graphisch ein beliebiges primal degeneriertes LP mit zwei Variablen.
Normal - zwei geraden schneiden sich -> ein Eckpunkt
Degeneriert - drei oder mehr schneiden sich in einem Punkt
NB 3 ist im Eckpunkt degeneriert / unnötig
(h) Woran erkennt der primale Simplex-Algorithmus, dass ein unbeschränktes LP (Lineares Programm) vorliegt?
Unbeschränkt heißt bei Maximierungsproblemen das der zielfunktionswert beliebig groß werden kann ohne eine nebenbedingung zu verletzen
(Minimierung genau so nur umgekehrt)
(h) 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?
Aus der Vorlesung wissen Sie:
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ösungen 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.
(j) Warum werden in Schritt 5.1 des primalen Simplex-Algorithmus (Bestimmung der Pivotzeile) Zeilen i mit nichtpositiven Einträgen a′
i,j nicht berücksichtigt?
Die mit einer solchen Zeile korrespondierende BV würde mit steigendem Wert der bisherigen NBV xj (Schritt 2),
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.
(k) Warum ist es in Schritt 1 des primalen Simplex-Algorithmus wichtig, dass das LP in Standardform mit nichtnegativen rechten Seiten vorliegt?
(k) 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 changed8 days ago
