Mathematik: Lösen von Linearen Optimierungsproblemen mit Java
Released by matroid on Di. 07. April 2020 21:44:30 [Statistics]
Written by Delastelle - 586 x read [Outline] Printable version Printer-friendly version -  Choose language   
Software

\(\begingroup\) Im Rahmen meiner Diplomarbeit habe ich im Jahr 2001 C/C++ Programme von Robert J.Vanderbei zur Linearen Optimierung in Java implementiert. Kern sind 2 LP-Löser - ein Simplexartiges Verfahren und ein Innere-Punkt-Verfahren. Damit kann man schnell kleine, mittlere und auch große Optimierungsprobleme lösen.

Kurzbeschreibung der 2 Algorithmen

Die Aufgabe: (LP) max c^T x unter den Nebenbedingungen: A x <= b. (A) Primal Duales Simplexverfahren mit Eta-Matrizen
Parameter:
(B) Innere Punkt Verfahren
Parameter:
Hinweis: die Variablennamen sind genauso gewählt wie im Buch "Linear Programming: Foundations and Extentions" von Robert J.Vanderbei. Die 2 Programme basieren auf den Programmen von Vanderbei.

3 kleine Beispiele

Die Beispiele (1) bis (3) sind lineare Optimierungsprobleme (LP). Sie werden beispielsweise mit dem Simplexverfahren gelöst. (1) Max. F(x,y) = 4x+3y x+3y <= 9 -x+2y >= 2 x, y >= 0 Bild Der zulässige Bereich ist nichtleer. Es gibt eine Lösung. Die Lösung ist x = 2,4 und y = 2,2. Die Zielfunktion beträgt dort 16,2. Eingabe des Problems in Java: \sourceon Java ... double[] temp_a = { 1.0, 1.0, 3.0,-2.0}; int[] temp_ka = { 0, 2, 4}; int[] temp_ia = { 0, 1, 0, 1}; double[] temp_b = { 9.0, -2.0}; double[] temp_c = { 4.0, 3.0}; ... \sourceoff mit a, b und c wie im Problem und ka als Index, wo neue Spalten beginnen und ia als Index, welche Einträge von A belegt sind (sparse Matrix möglich - "dünnbesetzte" Matrix) \sourceon Eingabeaufforderung javac BMp100_01.java java BMp100_01 ... Simplex - Bsp 1 Zustand 0 Zeit = 5 ... m = 2 ,n = 2 ,nz = 6 ------------------------------------------------------------- | Primal | | Iter | Obj Value | mu | nonz(L) nonz(U) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 16.200000000000003 -0.9207566691902651 Zustand = 0 ... javac BMp150_01.java java BMp150_01 ... Intpt - Bsp 1 Solver Zustand 0 Zeit = 8 ... m = 2 ,n = 2 ,nz = 4 ------------------------------------------------------------------ | Primal | Dual | Iter | Obj Value Infeas | Obj Value Infeas | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 17 16.199999843427648 3.804202212770035E-16 16.200000118721363 5.041339799397728E-16 Status = 0 (optimal) \sourceoff (2) Max. F(x,y) = x-y 2x-y <= 0 x+2y <= 1 2x+y >= 2 x,y >= 0 Bild Der zulässige Bereich ist leer. Es gibt keine Lösung da die Nebenbedingungen widersprüchlich sind. \sourceon Eingabeaufforderung java BMp100_02 ... Simplex - Bsp 2 Zustand 2 Zeit = 9 ... m = 3 ,n = 2 ,nz = 9 ------------------------------------------------------------- | Primal | | Iter | Obj Value | mu | nonz(L) nonz(U) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 -0.5 0.22360679774997896 Zustand = 2 (zulässiger Bereich leer) ... java BMp150_02 ... Intpt - Bsp 2 Solver Zustand 5 Zeit = 8 ... m = 3 ,n = 2 ,nz = 6 ------------------------------------------------------------------ | Primal | Dual | Iter | Obj Value Infeas | Obj Value Infeas | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 50 -0.5 1.5 -86046.14760834308 1.4551915228366852E-11 Status = 5 \sourceoff Bemerkung: die maximale Iterationszahl für das Innere-Punkt-Verfahren war hier auf 50 gestellt. Nach dieser Iterationszahl gibt es keine Lösung. (3) Max. F(x,y) = 2x+y -x+y <= 1 x+3y >= 6 x,y >= 0 Bild Der zulässige Bereich ist nichtleer. Allerdings ist die Funktion nicht nach oben beschränkt. \sourceon Eingabeaufforderung java BMp100_03 ... Simplex - Bsp 3 Zustand 1 Zeit = 7 ... m = 2 ,n = 2 ,nz = 6 ------------------------------------------------------------- | Primal | | Iter | Obj Value | mu | nonz(L) nonz(U) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 12.0 1.414213562373095 Zustand = 1 (Problem unbeschränkt) ... java BMp150_03 ... Intpt - Bsp 3 Solver Zustand 2 Zeit = 14 ... m = 2 ,n = 2 ,nz = 4 ------------------------------------------------------------------ | Primal | Dual | Iter | Obj Value Infeas | Obj Value Infeas | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 30 171264.29138321796 7.275957614183426E-12 -7.531285776700655E-17 2.23606797749979 Status = 2 (PRIMAL INFEASIBLE [unreliable]) ... \sourceoff

größere Probleme

Die folgenden Probleme dieses Abschnitts werden in meiner Diplomarbeit beschrieben. (4) ein Transportproblem Zu lösen (minimieren) ist ein Transportproblem. Siehe auch: de.wikipedia.org/wiki/Transportproblem (5) ein Zuordnungsproblem 12x12 Eine nxn Matrix ist mit (ganzzahligen) Werten gefüllt. Nun wird eine Belegung (Zuordnung) gesucht, für die die Summe der Einträge minimal wird. Dabei darf in jeder Zeile und Spalte nur jeweils 1 Eintrag verwendet werden. Es ist also aus den n! möglichen Zuordnungen die optimale zu finden.
siehe auch: de.wikipedia.org/wiki/Zuordnungsproblem (6) ein Zuordnungsproblem 50x50 Die Belegung der 50x50 Matrix wir mit zufälligen ganzzahligen Werten aus [0,499] gewählt. (7) ein Zuordnungsproblem 500x500 Die Belegung der 50x50 Matrix wir mit zufälligen ganzzahligen Werten aus [2,499] gewählt. Die Werte auf der Diagonalen sind alle 1. Dies führt dazu, dass man die Lösung nachvollziehen kann. (7b) aktuell lösbare Zuordnungsprobleme des Typs (7) Innere Punkte Dimension 162 \sourceon Eingabeaufforderung java -Xmx1580m BMp150_07 162 \sourceoff REM 30 Iterationen, ff = -162.00030800252458, Zeit = 244 Sekunden (neuer Laptop ca.4 GHz) Dieser spezielle Typ Zuordnungsproblem mit Lösung auf der Diagonalen kann bis Dimension 162 mit dem Innere-Punkt-Verfahren gelöst werden. Simplextyp Dimension 2900 \sourceon Eingabeaufforderung java -Xmx1580m BMp100_07 2900 \sourceoff REM 2900 Iter, ff = -2900, Zeit = 79 Sekunden (neuer Laptop ca.4 GHz) Dieser spezielle Typ Zuordnungsproblem mit Lösung auf der Diagonalen kann bis Dimension 2900 mit dem Simplexverfahren gelöst werden. (8) Ausgleichsproblem 1
Der maximale Abstand von einer Ausgleichsgeraden soll minimiert werden. (9) Ausgleichsproblem 2 Messwerte wie bei (8). Jetzt soll die Summe der Abstände von einer Ausgleichsgeraden minimiert werden. (10) Instandsetzungsproblem Ein einfaches Instandsetzungsproblem. Enthalten sind: ein Anfangswert, mehrere Zeitintervalle, ein Verschleiß pro Intervall, die Wertsteigerung durch Wartung, eine Obergrenze für Wartungsarbeiten, ein Produktionserlös proportional zum Zeitwert der Anlage, ein Faktor zum Verkaufswert. (11) Netzwerkproblem Gegeben sei folgendes Maximalstromproblem: Für einen bestimmten Zeitabschnitt soll der Einsatz von Arbeitskräften geplant werden. Dabei soll die Summe aus Anzahl der nichtbeschäftigten Arbeiter und Anzahl der zusätzlich benötigten Arbeiter minimiert werden.

weitere Probleme

Die folgenden Probleme kommen nicht in meiner Diplomarbeit vor. Sie sind nur zur Ergänzung. (12) Klee-Minty 2x2 Die Klee-Minty Probleme stellen sich als Probleme dar, mit denen das klassische Simplexverfahren Schwierigkeiten hat - eine hohe Iterationszahl kann eintreten. (13) Klee-Minty 3x3 x_1 <= 5 4 x_1 + x_2 <= 25 8 x_1 + 4 x_2 + x_3 <= 125 4 x_1 + 2 x_2 + x_3 -> max (14) Klee-Minty 5x5 (15) Klee-Minty 7x7 (16) Klee-Minty 10x10 Der Simplexsolver löst die Probleme (12) bis (16) gut, der Innere-Punkt-Solver löst die Probleme (12) bis (15) gut, hat bei (16) Schwierigkeiten. (17) ein kleines LP-Problem
x_1+x_2 <=6 x_1 <= 4 x_2 <= 4 x_1+x_2 -> max Problemeingabe: \sourceon Java double[] temp_a = { 1.0, 1.0, 0.0, 1.0, 0.0, 1.0}; int[] temp_ka = { 0, 3, 6}; int[] temp_ia = { 0, 1, 2, 0, 1, 2}; double[] temp_b = { 6.0, 4.0, 4.0}; double[] temp_c = { 1.0, 1.0}; \sourceoff Ergebnis: x* = [4; 2] (Simplexsolver) Der Simplexsolver beendet die Durchführung an einer optimalen Ecke. x* = [3; 3] (Innere-Punkt-Solver) Der Innere-Punkt-Solver beendet die Durchführung in der Mitte einer optimalen Kante (= zwischen 2 Ecken). Parameter: delta = 0.02; R = 0.85 (Innere-Punkt-Solver) Hinweis: wie immer "nonzeros" groß genug gewählt.

Abschluß

Die Java-Files zum Lösen der 17 Beispiele finden sich in meinem Notizbuch. Des weiteren eine Fassung meiner Diplomarbeit. BMp100-Files beinhalten Probleme die mit dem Simplexsolver gelöst werden. BMp150-Files beinhalten Probleme die mit dem Innere-Punkt-Solver gelöst werden. fav.php?uname=Delastelle Fragen zum Thema können im Forum (oder hier) gestellt werden. Viele Grüße Ronald
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Optimierung :: Software :: Lineare Optimierung :
Lösen von Linearen Optimierungsproblemen mit Java [von Delastelle]  
Im Rahmen meiner Diplomarbeit habe ich im Jahr 2001 C/C++ Programme von Robert J.Vanderbei zur Linearen Optimierung in Java implementiert. Kern sind 2 LP-Löser - ein Simplexartiges Verfahren und ein Innere-Punkt-Verfahren. Damit kann man schnell kleine, mittlere und auch große Optimierungsproblem
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 586
 
Aufrufstatistik des Artikels
Insgesamt 139 externe Seitenaufrufe zwischen 2020.05 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://duckduckgo.com10.7%0.7 %
https://google.de8964%64 %
https://google.com4028.8%28.8 %
https://www.bing.com53.6%3.6 %
https://www.ecosia.org32.2%2.2 %
https://www.startpage.com10.7%0.7 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.10.15 18:53https://duckduckgo.com/
2021.10.14 16:10https://google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 130 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (58x)https://google.de/
2020-2021 (38x)https://google.com/
2020-2021 (18x)https://google.de
202104-04 (12x)https://google.de/url?sa=t
202102-06 (4x)https://www.bing.com/

[Top of page]

"Mathematik: Lösen von Linearen Optimierungsproblemen mit Java" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]