Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Nebenbedingung in TSP: Länge von Objekten/Strecken bestimmter Art
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Nebenbedingung in TSP: Länge von Objekten/Strecken bestimmter Art
julieann
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.10.2003
Mitteilungen: 150
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-09 17:19


Ich scheine auf dem Schlauch zu stehen, da ich mich schwer tue, eine bestimmte Bedingung in meinem Optimierungsmodell unterzubringen.

Vereinfacht gesagt muss ich n Objekte in eine Reihenfolge bringen. Dazu nutze ich ein TSP.
Manche Objekte dürfen nicht hintereinander geplant werden, es gibt also keine Kante zwischen ihnen. Außerdem gibt es Dummies, welche notfalls zwischen zwei Objekten eingeplant werden können.

Ich habe derzeit also neben den Dummies und einem Start/Endknoten die Variablen "Kanten_i,j" (binär, 1, wenn Objekt j auf i folgt) sowie "Position_i" (ganzzahlig, enthält die Position des Objektes i).

Alle n Objekte haben eine bestimmte Länge.
Nun muss ich dafür Sorgen, dass vor Objekten der Sorte a (bzw. dem ersten Objekt einer "Kette" von Objekten der Sorte a) eine bestimmte Mindestlänge von Objekten der Sorte b verplant wird.
Damit tue ich mich gerade schwer bzw. komme nicht recht auf die Idee.
Kann mir hier jemand auf die Sprünge helfen?

Vielen Dank im Voraus!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 688
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-09 18:06


Hallo julieann,

was sind das denn für Dummies? Welche Sorte haben die, oder haben sie überhaupt eine?

Wie lautet die Aufgabenstellung im Originalwortlaut?

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
julieann
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.10.2003
Mitteilungen: 150
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-09 20:34


Eine Aufgabenstellung im eigentlichen Sinne gibt es nicht, das Problem entstammt "der Realität". Bevor Objekte der Sorte a durch die Anlage dürfen, müssen erst X Meter der Sorte b kommen (damit eine entsprechende Qualität gewährleistet werden kann, die bei b noch nicht erreicht werden muss).

Die Dummies sind derzeit wirkliche Dummyvariablen. Sie haben keinen Typ o.ä.
Sie stellen nur sicher, dass es immer eine Lösung gibt, falls zB bestimmte der n Objekte keine Kompatibilität/Kanten zu anderen aufweisen o.ä. (In der Realität wird dies dann sicher nochmals anders abgebildet)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 688
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-09 21:35


Könnte man irgendwas in der folgenden Art machen?

Alle Kantengewichte derjenigen Kanten, die Objekte der Klasse a untereinander verbinden, werden pauschal um 100000 erhöht, damit sie beim Suchen eines kostenminimalen Weges möglichst spät drankommen.

Zeige doch mal dein Optimierungsproblem, so richtig schön formal mit allem drum und dran.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
julieann
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.10.2003
Mitteilungen: 150
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-07-09 21:53


Morgen werde ich es in Ruhe hier formulieren, ist schon spät ;)

Wenn ich die Kantengewichte erhöhe für Kanten, die Objekte der Sorte a untereinander verbinden, sorge ich doch hauptsächlich dafür, dass diese möglichst "zerstreut" werden, also lieber andere Verbindungen zu den Objekten a gewählt bzw. diese nicht hintereinander platziert werden. Oder verstehe ich dich falsch?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 688
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-09 21:56


Ich schieße bisher lediglich ins Blaue. Ich müsste das mal möglichst handfest vor Augen haben.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
julieann
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.10.2003
Mitteilungen: 150
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-07-10 16:43


Ich habe mal versucht, das Modell aufzuschreiben:




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
julieann hat die Antworten auf ihre/seine Frage gesehen.
julieann wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 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]