Suche Algorithmus für den Optimalen Pfad (Maximierungsproblem) |
| 20.11.2015, 02:48 | DS87 | Auf diesen Beitrag antworten » | ||
| Suche Algorithmus für den Optimalen Pfad (Maximierungsproblem) ich suche einen Algorithmus für die Optimierung (Maximierung) von Zuweisungen. Im wesentlichen habe ich eine zwei-dimensionale Tabelle. Dabei befinden sich in der Zeile Bestellungen und in der Spalte Dienstleister. Ich suche die Optimale Zuweisung eines Dienstleisters zu einer Bestellung. Dabei gelten die Regeln, dass eine Bestellung genau von einem Dienstleister erbracht werden kann und ein Dienstleister kann maximal eine Bestellung erbringen. Es kann sein dass ein Dienstleister keine Bestellung erbringt, genauso wie dass eine Bestellung nicht erbracht wird, wenn es das Maximum so will. Hier ist ein Beispiel für das Problem: XX| D1 D2 D3 D4 D5 B1| 80 72 10 31 00 B2| 82 22 45 91 24 B3| 11 85 00 00 12 Leider stehe ich total auf dem Schlauch welche Methode man dafür nehmen kann. In kleinen Datensätzen ist es noch recht einfach (hier ergibt das Maximum B1-D1, B2-D4, B3-D2= 256), für eine große Tabelle mit NxM Elementen wird das leider ohne einen schönen Algorithmus nichts. Leider habe ich noch nichts passendes gefunden. Sollte es keinen Algorithmus für das Optimale Maximum geben, würde es auch ein Approximationsalgorithmus tun. Leider habe ich derzeit keinen sinnvollen Ansatz 
|
||||
| 20.11.2015, 11:36 | Elvis | Auf diesen Beitrag antworten » | ||
Branch and Bound - Algorithmus. Wenn Du genug Geld hast, kaufe passende Software. Wenn nicht, werde erst reich und kaufe dann passende Software. 
Googeln nach "Software für binäre Optimierung" gibt z.B. http://www.tobias-elze.de/vortr/optimierung.pdf und das http://www.math.uni-magdeburg.de/~werner/or-skript.pdf |
||||
| 20.11.2015, 12:20 | zyko | Auf diesen Beitrag antworten » | ||
Deine Problemstellung, falls ich sie richtig verstanden habe, stellt ein "Zuordnungsproblem" dar. Dieses kann mit der "Ungarischen Methode" gelöst werden. Dabei wird aus der Zuordnungsmatrix aus jeder Spalte und Zeile genau ein einziges Element so ausgewählt, dass die Summe der gewählten Elemente minimal wird. S. dazu auch im Internet. In einem älteren "Bronstein et al." steht dazu ausführlich der Algorithmus. Die Matrix muss dabei nicht notwendigerweise quadratisch sein. |
||||
| 20.11.2015, 17:25 | DS87 | Auf diesen Beitrag antworten » | ||
Jau, jetzt wo ich die Ungarische Methode höre kommts langsam aus den Grauen Gehirnzellen wieder. 2. Semester Studium OR. Ich habe mich nochmal schlau gemacht. Danke dir 
Wiki schreibt, dass es eine Funktion ist. Anfangs sollte das für meine Zwecke reichen. Es kann aber gut sein, dass ich in einem halben Jahr auch mal eine 100x100 Matrix habe. Ein Jahr später gibt es eine noch größere Matrix. Leider habe ich noch keinen Erfahrungswert, wie schnell die Berechnung ist. Ist eine Berechnung der Matrix (natürlich macht die Arbeit die CPU) binnen weniger Minuten Problemlos möglich? Wenn nicht, gibt es eventuell auch einen alternativ-Algorithmus, der approximiert, dafür aber dafür nicht so aufwändig ist? |
||||
| 23.11.2015, 12:50 | zyko | Auf diesen Beitrag antworten » | ||
Da meine Erfahrungen mit der Ungarischen Methode 20 Jahre zurückliegen und nur bis basieren, kann ich dir leider für so große Matrizen keine aktuellen Rechenzeiten nennen. In solchen Fällen sollte man versuchen, die Gesamtproblemstellung in mehrere kleinere Teilprobleme zu zerlegen. Evtl. gelingt es auch, den Algorithmus durch Nutzung mehrerer CPUs zu beschleunigen. Viel Erfolg |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
