|
|
Dekomposition
I. Vorgehensweise: Zerlegung eines linearen Optimierungsproblems mit dünn besetzter Koeffizientenmatrix (dünn besetzte Matrix) in ein Haupt- und mehrere Teilprobleme. Man versucht (sofern möglich), das Optimierungsproblem durch Vertauschen der Reihenfolge von Restriktionen und/oder von Variablen auf die Form (unter Verwendung der Matrizenschreibweise und Vernachlässigung der NN-Restriktionen) zu bringen:
A1, A2, ..., Ap, D1, D2, ..., Dp, sind gewisse Matrizen, a10, a20, ..., ap0, x1, x2, ..., xp, b0, b1, ..., bp, gewisse Vektoren und 00, 01, 02, ..., 0p, entsprechende nur aus Nullen bestehende Vektoren.
1. Hauptproblem: Die Nichtnegativitätsrestriktionen werden nicht aufgeführt.
2. K-tes Teilproblem:
II. Lösung: Eine optimale Lösung kann dadurch bestimmt werden, indem die "kleinen" Teilprobleme unabhängig voneinander optimal gelöst werden (z. B. mit einer Simplexmethode). Daraus wird eine Lösung des gesamten Problems konstruiert, die anhand des Hauptproblems überprüft wird. Sofern erforderlich, werden geeignete Modifikationen an den Teilproblemen vorgenommen, diese erneut gelöst etc. bis eine optimale Lösung gefunden ist bzw. feststeht, daß keine derartige Lösung existiert. Durch diese Vorgehensweise wird es möglich, auch große lineare Optimierungsprobleme zu lösen, die für sich genommen die Speicherkapazität der Rechenanlage überfordern könnten.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
