Optimierungsmethoden des Operations Research

Im folgenden Abschnitt wird ein formelmäßig einfach zu beschreibendes (und damit leicht programmierbares) Verfahrenselement vorgestellt, das grundlegend für die Lösung verschiedener Probleme ist: die Lösung linearer Gleichungssysteme und die Umrechnung der Parameterdarstellung ihrer Lösungsmengen, die Invertierung regulärer Matrizen und die Lösung linearer Optimierungsaufgaben.

Für die Menge \( M \subseteq {\mathbb{R}^n} \) und die Funktion z: \( M \to \mathbb{R} \) wird die folgende Aufgabenstellung Optimierungsproblem genannt: Falls es ein x* ε M mit dieser Eigenschaft gibt, schreiben wir und bezeichnen x* als Optimallösung der Aufgabe (2.1). Andernfalls heißt die Optimierungsaufgabe unlösbar. Für die Aufgabe (2.1) ist folgende Schreibweise üblich: M wird zulässiger Bereich, x ε M zulässiger Punkt (Vektor) und z Zielfunktion des Optimierungsproblems genannt. -

Anschauliche Erläuterungen zum Simplexverfahren blieben bisher auf solche Aufgaben beschränkt, deren zulässiger Bereich im \( {\mathbb{R}^2} \) darstellbar ist. Grundlage für die geometrische Beschreibung des zulässigen Bereichs aus 2.1 und des Ablaufs von Algorithmus (2.22) im Fall höherer Dimension sind Grundbegriffe und Aussagen aus der Geometrie konvexer Polyeder, die im folgenden Abschnitt zusammengestellt werden. M(P) erfülle dabei stets die folgende Voraussetzung: (3.1) M(P) besitze eine zulässige Basislösung.

Die Restriktionen der aus der Praxis stammenden linearen Optimierungsaufgaben bilden im allgemeinen ein System linearer Gleichungen und Ungleichungen, so daß folgende Problemstellung vorliegt: mit Aⁱ ε Mat(m_i, s); \( c,\,u = {\left( {{x_1}, \ldots, {x_s}} \right)^t}\,\varepsilon \,{\mathbb{R}^s};\,{b^i}\,\varepsilon \,{\mathbb{R}^{{{m_i}}}};\,z,\,q\,\varepsilon \,\mathbb{R} \).

Jeder linearen Optimierungsaufgabe kann eine sog. duale Aufgabe zugeordnet werden. Hinsichtlich ihrer Lösungseigenschaften bestehen zwischen beiden Aufgaben enge Beziehungen, die für eine Reihe von Problemstellungen des Operations Research von grundlegender Bedeutung sind.

Unter „revidierten“ Simplexverfahren verstehen wir Verfahren, die entstehen, wenn der normale Simplexalgorithmus so umformuliert wird, daß für die rechnerische Durchführung jedes Austauschschrittes Informationen aus den Ausgangsdaten herangezogen werden (ohne daß dabei der Verlauf des Verfahrens verändert wird). Das Ziel einer solchen Umformulierung ist mehrschichtig:

Lineare Optimierungsaufgaben der Praxis zeichnen sich häufig dadurch aus, daß ein Teil der Restriktionen eine besondere Struktur besitzt. Liegt eine Aufgabenstellung der Form vor, so wird nun unterstellt, daß die Restriktionen H¹x = d¹ in spezieller Weise strukturiert seien. Im folgenden werden sie daher spezielle Restriktionen genannt. Ihre Besonderheit kann darin bestehen, daß die Matrix H¹ z.B.

Bei Optimierungsaufgaben der Praxis sind die auftretenden Variablen häufig beschränkt. Dies führt zu Restriktionen von besonders einfacher Struktur, nämlich Die Zahlen λ_j, \( {\lambda_j},\,{\mu_j} \varepsilon \,\mathbb{R} \) werden als untere bzw. obere Grenze für x. bezeichnet. Die den folgenden Ausführungen zugrunde liegende Zielsetzung besteht darin, die explizite Aufnahme der Restriktionen (8.1) zu vermeiden. Besonders einfach ist dies zu erreichen, wenn die entsprechende Variable einseitig beschränkt ist, also einer der folgenden Fälle vorliegt: Unterwirft man die vorliegende Aufgabe einer Variablentransformation so geht jede der Bedingungen (8.2) über in eine Vorzeichenbeschränkung x′_j ≧ 0 (bzw. x′_i ≧ 0), die im Simplexverfahren bekanntlich so verarbeitet wird, daß sie keine gesonderte Zeile des Tableaus beansprucht, sondern lediglich bei der Wahl des Pivots (vgl. Algorithmus (2.22)) Berücksichtigung findet.

Bisher haben wir stets den Fall betrachtet, daß die Daten a, H, d des Problems (P) (aus Abschnitt 2.1) konstante Größen sind. Die Besonderheit der Aufgabe, die im Rahmen der parametrischen Optimierung behandelt wird, besteht in der Parameterabhängigkeit dieser Daten: es sei (P) = (P(λ)) für \( \lambda \,\varepsilon \,{\mathbb{R}^k},\,k\,\varepsilon \,\mathbb{N} \). Dabei geht es darum, für (P(λ)) je eine Optimallösung in Abhängigkeit von λ zu bestimmen.

Das Verfahren von Chatschijan arbeitet mit einer Folge von Ellipsoiden fallenden Volumens, die die möglichen Optimalpunkte einer linearen Optimierungsaufgabe sukzessive einschließen. Die Grundidee des Verfahrens wird erläutert an einem Verfahren zur Ermittlung zulässiger Punkte.

Bisher haben wir zwei verschiedene Prinzipien, eine lineare Optimierungsaufgabe zu lösen, vorgestellt:

Das Problem (P_st), das aus (P) durch Weglassen der Ganzzahligkeitsforderungen entsteht, wird das (P) zugrunde liegende stetige Problem genannt. Die zulässigen Bereiche M(P) und M(P_st) genügen offenbar der Beziehung die in nebenstehender Skizze für den Fall, daß M(P_st) ⊆ ℝ² ist und die Ganzzahligkeitsforderung x₂ ∈ ℤ lautet, veranschaulicht wird.

Ausgangspunkt sei weiterhin das in der Einleitung zu Teil IV zugrundegelegte Problem (P), mit endlichen Unter- und Obergrenzen für den Vektor x¹. Vorausgesetzt wird, daß die Aufgabe (P_st) lösbar sei. — Um das Simplexverfahren zur Lösung von (P) verwenden zu können, wurden in den bisher behandelten Schnittebenenverfahren die Ganzzahligkeitsforderungen durch zusätzliche Schnittrestriktionen ersetzt. Ihre Konstruktion erwies sich als aufwendig, weil sie von M(P_st) keinen Punkt aus M(P) wegschneiden dürfen.

Ausgangspunkt ist die folgende, wesentlich-ganzzahlige Aufgabe mit Hⁱ ∈ Mat(m_i, n), d_i ∈ ℝ^mi, i = 1, 2 λ, μ, c ∈ ℝⁿ. Ferner setzen wir λ = 0 voraus, was durch die Transformation x → x + λ erreichbar ist.