Herbers Excel-Forum - das Archiv

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

Excel-Beispiele zum Thema "optimale Reihenfolge"
Tabellenblätter in umgekehrter Reihenfolge drucken Daten in umgekehrter Reihenfolge übertragen
Reihenfolge einer Zahlenreihe nach dem Zufallsprinzip variieren Änderung der Reihenfolge einer Wertereihe
Werte in zweiter Tabelle in anderer Reihenfolge darstellen