Inhaltsverzeichnis
Gegeben sei das folgende Ausgangsproblem
u.d.N.
(1)
(2)
(3)
Obere Schranke
Die obere globale Schranke liegt in diesem Fall bei einem Zielfunktionswert von
Untere Schranke
Die untere Schranke ist der optimale Zielfunktionswert des angepassten Problems. Das bedeutet also, dass das obige ganzzahlige Problem zunächst mittels Simplexalgorithmus (oder grafisch) gelöst wird, indem die Ganzzahligkeitsbedingung aufgehoben wird. Es soll im folgenden gezeigt werden, wie man die optimale Lösung mittels Simplexalgorithmus erhält. Hierzu benötigt man die Standardform:
u.d.N.
(1)
(2)
(3)
Nachdem nun die Standardform gegeben ist wird das Problem in die Normalform überführt (Einfügen von Schlupfvariablen):
u.d.N.
(1)
(2)
(3)
Da die Werte der rechten Seite negative Werte aufweisen, muss hier also zunächst der duale Simplexalgorithmus angewandt werden um eine zulässige Lösung zu erhalten. Es müssen insgesamt 3 Simplexschritte mittels dualen Simplex durchgeführt werden, bis eine zulässige Ausgangslösung resultiert:
Da alle Werte der rechten Seite positiv sind, liegt eine zulässige Ausgangslösung vor. Der primale Simplexalgorithmus muss hier nicht angewandt werden, da bereits alle Werte in der Zielfunktionszeile positiv sind. Es liegt also gleichzeitig auch die optimale Lösung vor.
Die optimale Lösung des angepassten Problems
Diese ermittelte optimale Lösung ist nicht ganzzahlig, deswegen für das obige Ausgangsproblem
Die weitere Vorgehensweise erfolgt im nächsten Abschnitt.
Weitere interessante Inhalte zum Thema
-
Zusammenfassung: Minimierungsproblem
Vielleicht ist für Sie auch das Thema Zusammenfassung: Minimierungsproblem (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.
-
Branch-and-Bound am Minimierungsproblem
Vielleicht ist für Sie auch das Thema Branch-and-Bound am Minimierungsproblem (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.