optimale Reihenfolge



Excel-Version: 8.0 (Office 97)
nach unten

Betrifft: optimale Reihenfolge
von: Norbert
Geschrieben am: 16.05.2002 - 11:27:20

Hallo,

ich habe folgendes Problem und bin fast am verzweifeln.
Ich habe eine Kreuztabelle der Form
A B C
A 0 0,5 1
B 0,5 0 2
C 1 2 0

Die Werte spiegeln Übergangszeiten wider.
Ich suche jetzt die optimale Reihenfolge (In diesem Bspl noch einfach BAC oder CAB mit 1,5 Std.)
Wie kann ich so etwas in einem Makro berechnen, daß er mir
a) die Reihenfolge in einer anderen Tabelle
und b) die Zeit ausgibt
P.S. meine richtige hat 50 Spalten und 50 Zeilen also 50! Permutationen!!!

Vielen Dank schon einmal im vorraus

Norbert


nach oben   nach unten

Re: optimale Reihenfolge
von: Martin Beck
Geschrieben am: 16.05.2002 - 17:05:56

Hallo Norbert,

das hört sich für mich wie ein Travelling Salesman Problem an, richtig?

Ohne einen ausgeklügelten Algorithmus wirst Du in Excel Schwierigkeiten bekommen.

Schau mal unter http://evonet.dcs.napier.ac.uk/evoweb/resources/flying_circus/demos/windows/demo21.html, da wird ein Programm namens Generator beschrieben, das TS Problem unter Excel lösen kann (wenn ich's richtig verstanden habe).

Gruß
Martin Beck

nach oben   nach unten

Re: optimale Reihenfolge
von: Norbert
Geschrieben am: 16.05.2002 - 18:06:57

Hallo Martin,

Stimmt Du hast recht, danke. An den travelling salesman habe ich bis jetzt noch nicht gedacht. Leider ist mir da nur ein Algorithmus bekannt, wie man das lösen kann. Eigentlich müßte Excel das Problem doch lösen können. (denke ich)
Das Problem, was hinzukommt ist, daß ich wirklich das Optimum suche. Also wenn jemand eine Makro Lösung kennt wäre das Klasse.

P.S. Das mit generator funktioniert leider nicht, da dieses Optimierungsproblem nur ein Teilproblem eines großen Makros ist. Und die Daten dann in ein anderes Programm zu überführen ist nicht möglich.

Gruß Norbert


nach oben   nach unten

Re: optimale Reihenfolge
von: Martin Beck
Geschrieben am: 16.05.2002 - 19:01:44

Hallo Norbert,

kannst Du den Algorithmus zur Lösung des TSP exakt beschreiben. Dann könnte man mal versuchen, es in Excel umzusetzen.

50! ergibt ca 3*10^64 Permutationen. Die mit brute force alle durchzurechnen, um das Optimum zu finden, dürfte Excel m.E. in die Knie zwingen.

Gruß
Martin

P.S. Hast Du mal den Solver angeschaut? Ich habe davon keine Ahnung, aber irgendwie in Erinnerung, daß er für solche Probleme möglicherweise geeignet ist.


nach oben   nach unten

Re: optimale Reihenfolge
von: Norbert
Geschrieben am: 17.05.2002 - 10:13:40

HAllo Martin,

die genau Methode, die ich meine habe ich jetzt ausführlich im Internet unter:
http://jochen.pleines.bei.t-online.de/index.htm

gefunden.
Ich denke, daß das eine gute Möglichkeit ist, daß Problem zu lösen. Wahrscheinlich ist eine Näherungslösung eher möglich als das Optimum.
Leider habe ich bis jetzt noch keine Idee, wie ich daß die auf dem Link beschriebene Methode in ein Makro übersetze.
Vielleicht hats Du ja eine Idee?

Gruß Norbert

nach oben   nach unten

Re: optimale Reihenfolge
von: Hans W. Hofmann
Geschrieben am: 18.05.2002 - 12:34:55

Hallo zusammen,

ich hab schon ein paar Recherchen zu dem Thema hinter mir.
Interesse an einer Zusammenarbeit?
http://fsing.fs.uni-sb.de/~thkle/tsp/heu.html
als Pascal-Listung vielleicht leichter nach VBA umzusetzen. Hab aber bisher noch nicht genauer hineingeschaut.


http://www-m9.mathematik.tu-muenchen.de/dm/java-applets/routenplanung/
http://matheplanet.com/matheplanet/nuke/html/links.php?op=search&query=

Lasst mal was hören, gerne auch PM

Gruß HW

 nach oben

Beiträge aus den Excel-Beispielen zum Thema "optimale Reihenfolge"