Live-Forum - Die aktuellen Beiträge
Anzeige
Archiv - Navigation
120to124
Aktuelles Verzeichnis
Verzeichnis Index
Übersicht Verzeichnisse
Vorheriger Thread
Rückwärts Blättern
Nächster Thread
Vorwärts blättern
Anzeige
HERBERS
Excel-Forum (Archiv)
20+ Jahre Excel-Kompetenz: Von Anwendern, für Anwender
120to124
120to124
Aktuelles Verzeichnis
Verzeichnis Index
Verzeichnis Index
Übersicht Verzeichnisse
Inhaltsverzeichnis

optimale Reihenfolge

optimale Reihenfolge
16.05.2002 11:27:20
Norbert
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

5
Beiträge zum Forumthread
Beiträge zu diesem Forumthread

Betreff
Datum
Anwender
Anzeige
Re: optimale Reihenfolge
16.05.2002 17:05:56
Martin Beck
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

Re: optimale Reihenfolge
16.05.2002 18:06:57
Norbert
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

Anzeige
Re: optimale Reihenfolge
16.05.2002 19:01:44
Martin Beck
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.

Re: optimale Reihenfolge
17.05.2002 10:13:40
Norbert
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

Anzeige
Re: optimale Reihenfolge
18.05.2002 12:34:55
Hans W. Hofmann
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

Beliebteste Forumthreads (12 Monate)

Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige
Anzeige
Anzeige