Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Lineare Optimierung mit dem Simplexverfahren

1. Äquivalente Umformungen linearer Gleichungssysteme

Zusammenfassung
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.
Ernst-Peter Beisel, Manfred Mendel

2. Lineare Optimierungsaufgaben in Normalform und ihre Lösung mit dem Simplexverfahren

Zusammenfassung
Für die Menge \( M \subseteq {\mathbb{R}^n} \) und die Funktion z: \( M \to \mathbb{R} \) wird die folgende Aufgabenstellung Optimierungsproblem genannt:
$$ \left\{ \begin{gathered} Bestimme\,ein\, \times *\,\varepsilon \,M\,derart,\,da\beta \,z\left( { \times *} \right)\, \hfill \\ minimal\,ist,\,wobei\,minimal\,bedeutet:\, \hfill \\ z\left( { \times *} \right) \leqq z\left( \times \right)\,\left( {fur\,alle\, \times \varepsilon \,M} \right) \hfill \\ \end{gathered} \right\} $$
(2.1)
Falls es ein x* ε M mit dieser Eigenschaft gibt, schreiben wir
$$ z\left( {x * } \right) = \begin{array}{*{20}{c}} {Min\,z(x)} \\ {x\,\varepsilon \,M} \\ \end{array} $$
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:
$$ \left\{ {\begin{array}{*{20}{c}} {z(x) \to Min} \\ {x\,\varepsilon \,M} \\ \end{array} } \right\} $$
(2.2)
M wird zulässiger Bereich, x ε M zulässiger Punkt (Vektor) und z Zielfunktion des Optimierungsproblems genannt. -
Ernst-Peter Beisel, Manfred Mendel

3. Zur Geometrie linearer Optimierungsaufgaben

Zusammenfassung
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
$$ M = M(P) = \left\{ {x\;\varepsilon \,{\mathbb{R}^n}\left| {H\,x = d,\,x \geqq 0} \right.} \right\}\,von\,(P) $$
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.
Ernst-Peter Beisel, Manfred Mendel

4. Simplexverfahren für die allgemeine lineare Optimierungsaufgabe

Zusammenfassung
Die Restriktionen der aus der Praxis stammenden linearen Optimierungsaufgaben bilden im allgemeinen ein System linearer Gleichungen und Ungleichungen, so daß folgende Problemstellung vorliegt:
$$ \left\{ {\begin{array}{*{20}{c}} {{A^1}u = {b^1},\,{A^2}u \geqq {b^2},\,{A^3}u \leqq {b^3}} \\ {z - {c^t}u = q,\,z\,\min imal,\,u \geqq 0} \\ \end{array} } \right\} $$
(4.1)
mit Ai ε Mat(mi, 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} \).
Ernst-Peter Beisel, Manfred Mendel

5. Dualität

Zusammenfassung
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.
Ernst-Peter Beisel, Manfred Mendel

Strukturierte lineare Programmierung

6. Revidierte Simplexverfahren

Zusammenfassung
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:
i)
Durch Rückgriff auf die Ausgangsdaten sollen spezielle Strukturen der Ausgangssituation, etwa sehr viele Nullen in der Ausgangsmatrix oder eine spezielle Anordnung der Daten (z.B. Konzentrierung um die Hauptdiagonale der Matrix), die normalerweise nach wenigen Austauschschritten im laufenden Tableau verschwunden sind, nutzbringend verwendet werden.
 
ii)
Die Gesamtrechenzeiten und der Gesamtspeicherplatzbedarf sollen herabgesetzt werden.
 
iii)
Es wird größere numerische Stabilität erreicht dadurch, daß immer wieder die (numerisch unverfälschten) Ausgangsdaten für den Fortgang des Verfahrens herangezogen werden.
 
Ernst-Peter Beisel, Manfred Mendel

7. Dekomposition

Zusammenfassung
Lineare Optimierungsaufgaben der Praxis zeichnen sich häufig dadurch aus, daß ein Teil der Restriktionen eine besondere Struktur besitzt. Liegt eine Aufgabenstellung der Form
$$ \left\{ {\begin{array}{*{20}{c}} {z + {c^t}x = q} \\ {{H^1}x = {d^1}} \\ {{H^2}x = {d^2}} \\ {z\,\min imal,\,x \geqq 0} \\ \end{array} } \right\} $$
(L)
vor, so wird nun unterstellt, daß die Restriktionen H1x = d1 in spezieller Weise strukturiert seien. Im folgenden werden sie daher spezielle Restriktionen genannt. Ihre Besonderheit kann darin bestehen, daß die Matrix H1 z.B.
  • aus sehr vielen Nullen und wenigen Elementen +1 oder -1 besteht, oder
  • Blockdiagonalgestalt besitzt.
Ernst-Peter Beisel, Manfred Mendel

8. Kapazitive Simplexverfahren

Zusammenfassung
Bei Optimierungsaufgaben der Praxis sind die auftretenden Variablen häufig beschränkt. Dies führt zu Restriktionen von besonders einfacher Struktur, nämlich
$$ {\lambda_j} \leqq {x_j} \leqq {\mu_j} $$
(8.1)
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:
$$ {\lambda_j} \leqq {x_j} < \infty \quad oder\quad - \infty < {x_j} \leqq {\mu_i} $$
(8.2)
Unterwirft man die vorliegende Aufgabe einer Variablentransformation
$$ x_j^i = {x_j} - {\lambda_j}\,bzw.\,x_j^i = {\mu_i} - {x_i} $$
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.
Ernst-Peter Beisel, Manfred Mendel

9. Parametrische Optimierung und Sensitivitätsanalyse

Zusammenfassung
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.
Ernst-Peter Beisel, Manfred Mendel

Polynomiale Verfahren der linearen Optimierung

10. Die Ellipsoid-Methode von Chatschijan

Zusammenfassung
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.
Ernst-Peter Beisel, Manfred Mendel

11. Die Projektionsmethode von Karmarkar

Zusammenfassung
Bisher haben wir zwei verschiedene Prinzipien, eine lineare Optimierungsaufgabe zu lösen, vorgestellt:
1)
Annäherung über die Kanten des zulässigen Bereiches an einen Optimalpunkt (Simplexverfahren);
 
2)
„Einkreisen“ des zulässigen Bereichs über immer enger gezogene Ellipsoïde, deren Zentren sich einer Optimallösung nähern (Chatschijan-Verfahren).
 
Ernst-Peter Beisel, Manfred Mendel

Ganzzahlige lineare Optimierung

Frontmatter

12. Ein duales Schnittebenenverfahren nach Gomory

Zusammenfassung
Das Problem (Pst), das aus (P) durch Weglassen der Ganzzahligkeitsforderungen entsteht, wird das (P) zugrunde liegende stetige Problem genannt. Die zulässigen Bereiche M(P) und M(Pst) genügen offenbar der Beziehung
$$ M(P) = M\left( {{P_{{st}}}} \right) \cap \left( {{Z^{{{n_1}}}} \times {\mathbb{R}^{{{n_2}}}}} \right) $$
die in nebenstehender Skizze für den Fall, daß M(Pst) ⊆ ℝ2 ist und die Ganzzahligkeitsforderung x2 ∈ ℤ lautet, veranschaulicht wird.
Ernst-Peter Beisel, Manfred Mendel

13. Direkte Schnittebenenverfahren

Zusammenfassung
Das im letzten Abschnitt beschriebene Verfahren nach Gomory ist empfindlich gegenüber Rundungsfehlern, was besonders bei Aufgaben großer Dimension ins Gewicht fällt. Dieser Mangel tritt dann nicht auf, wenn jede erzeugte Zwischenlösung bereits die Ganzzahligkeitsforderungen erfüllt. Solche Verfahren wollen wir direkte Schnittebenenverfahren nennen. Im folgenden sollen zwei Verfahren dieser Art besprochen werden.
Ernst-Peter Beisel, Manfred Mendel

14. Die Branch-and-Bound-Verfahren von Dakin und Land and Doig

Zusammenfassung
Ausgangspunkt sei weiterhin das in der Einleitung zu Teil IV zugrundegelegte Problem (P), mit endlichen Unter- und Obergrenzen für den Vektor x1. Vorausgesetzt wird, daß die Aufgabe (Pst) 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(Pst) keinen Punkt aus M(P) wegschneiden dürfen.
Ernst-Peter Beisel, Manfred Mendel

15. Additive Balas-Verfahren

Zusammenfassung
Ausgangspunkt ist die folgende, wesentlich-ganzzahlige Aufgabe
$$ \left\{ {\begin{array}{*{20}{c}} {z = {c^t}x + q \to Max} \\ {{H^1}x \leqq {d^1}} \\ {{H^2}x = {d^2}} \\ {\lambda \leqq x \leqq \mu, \,x\,\varepsilon \,\mathbb{Z}} \\ \end{array} } \right\} $$
(P)
mit Hi ∈ Mat(mi, n), di ∈ ℝmi, i = 1, 2 λ, μ, c ∈ ℝn. Ferner setzen wir λ = 0 voraus, was durch die Transformation x → x + λ erreichbar ist.
Ernst-Peter Beisel, Manfred Mendel

16. Verschärfung durch Schrankentabellen

Zusammenfassung
Bei der Durchführung eines Branch- and — Bound-Verfahrens ist es günstig, möglichst schnell eine (P)-zulässige Lösung zu erreichen. Der zugehörige Zielwert wirkt dann als untere Schranke: Alle Knoten, deren Zielwert kleiner/gleich einer solchen Schranke sind, können bei der Suche nach einer (P)-optimalen Lösung ausgeschlossen werden. -
Ernst-Peter Beisel, Manfred Mendel

Backmatter

Weitere Informationen