Aufgabe 3.3

Moderator: Algorithmische Modellierung

Dragon
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 18. Apr 2006 15:36
Wohnort: Darmstadt

Aufgabe 3.3

Beitrag von Dragon » 25. Aug 2008 10:44

Hallo,

ich habe folgenden ansatz für dies Aufgabe aufgestellt.

minimize c1*Fahrzeit+c2*Fahrpreis

Aus der Aufgabenstellung geht hervor das eine Fahrzeit von mehr als 30 % längerer Dauer als die schnellste Verbindung nicht mehr zulässig ist. D.h. der Fahrpreis darf höher werden die Fahrzeit dagegen nur in dieser Schranke.
Daraus schließe ich, dass ich die Fahrzeit stärkert gewichten muss als den Fahrpreis !??

Meine Überlegung war c1=1,3 und c2=1 zu setzen. Allerdings führt das nicht zu dem gewünschten Ergebnis. :(
Kann mir jemand sagen was an meiner Überlegung flasch ist und wie man die Gewichte besser wählen kann ? :? :?

Equinox
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 27. Nov 2004 14:58

Re: Aufgabe 3.3

Beitrag von Equinox » 25. Aug 2008 12:27

Ich hab's so gemacht:

Code: Alles auswählen

minimize sum(i in 1..no_of_queries) (m*min_travel_time[i]+costs[i])

subject to{
forall(i in 1..no_of_queries){
    travel_time[i] <= 1.3*min_travel_time[i];
}
[...]
Wobei m mindestens gleich dem maximalen Fahrpreis +1 und die Fahrtzeit diskret sein muss.

So stellst du sicher, dass zuerst die Fahrtzeit minimiert wird und erst dann die Kosten.

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Re: Aufgabe 3.3

Beitrag von Ultr1 » 25. Aug 2008 12:36

Hallo,

die Konstanten so zu wählen ist schon der richtige Weg. Vielleicht hilft dir mein Ansatz außerdem noch weiter:

Ich habe zunächst alle lokalen Konstrukte doppelt, aber mit veränderten Namen in den Code aufgenommeb. Einmal modelliere ich z.B. mit drives_out[i,j] den Weg für den günsttigsten Pfad, mit drives_out_for_zeit[i,j] den Weg für den zeitlich kürzesten Pfad. Die funktionsweise ist die gleiche sie beeinflussen sich aber nicht. Ich kann nun zu diesem separaten Konstrukt einfach die Kosten zu diesem zeitlich kürzesten Weg berechnen.

Das ganze muss nun aber noch die das minimize eingebat werden:

Code: Alles auswählen

minimize 1000 * besteZeit + preis;
subject to {
        zeit > 0;
	besteZeit > 0;
	besteZeit * 130 >= zeit * 100;
};
Durch den Koeffizient 1000 wird sichergestellt, dass der werd besteZeit in jedem Falle (unabhängig von den werten des ausgabeweges) berechnet wird.
Der Solver wird nun aber auch noch versuchen preis zu optimieren (sozusagen das Kleingeld). Preis wird wegen der doppelten Konstrukte ohne Abhängigkeit der Werte für den zeitlich kürzesten Weg berechnet, eben mit Ausnahme der 1.3fach-Zeitbedingung.

Ich hoffe das hilft.
Gruß
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Dragon
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 18. Apr 2006 15:36
Wohnort: Darmstadt

Re: Aufgabe 3.3

Beitrag von Dragon » 25. Aug 2008 13:09

Danke erstmal für eure Vorschläge.
Ganz schlau werd ich daraus allerdings immer noch nicht.

@equinox:
Wobei m mindestens gleich dem maximalen Fahrpreis +1 und die Fahrtzeit diskret sein muss.
Woher kennst du denn maximalen Fahrpreis und warum muss m mindestens diesen Wert +1 haben?
Außerdem verstehe ich nicht warum du m*min_travel_time +travel_cost minimierst und nicht
m*travel_time +travel_cost.


@ultra1: Auch bei deiner Lösung stellt sich mir die Frage warum wird 1000 * besteZeit + preis; minimiert und nicht
1000 * Zeit + preis; ??? :?

Ich verstehe das man die Zeit immer mehr gewichten muss als den Preis.
Soweit ich das Problem verstehe darf man auch nicht davon ausgehen das man die besteZeit von vornherein kennt,
da man dazu ein gesondertes Optimierungsproblem lösen müsste.
Man mus also eine Methode finden wie gleichzeitig Zeit und Preis minimiert werden, was mein ansatz prinzipiell auch leistet.
Müssen die 30% nicht über die Wahl der Gewichte mit eingebracht werden ???

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Re: Aufgabe 3.3

Beitrag von Ultr1 » 25. Aug 2008 13:26

Dragon hat geschrieben: @ultra1: Auch bei deiner Lösung stellt sich mir die Frage warum wird 1000 * besteZeit + preis; minimiert und nicht
1000 * Zeit + preis; ??? :?
Ich hätte meine Vriablenbelegungen besser erläutern sollen.
Dragon hat geschrieben: Soweit ich das Problem verstehe darf man auch nicht davon ausgehen das man die besteZeit von vornherein kennt,
Doch. Gneau das halb habe ich die gleichen Konstrukte nochmal unter anderen Namen verwendet.
Mit drives_out_for_zeit[i,j] lasse ich mir den zeitlich kürzesten Weg ausgeben. Ich habe für diese zeitliche Optimierung eine Variable besteZeit gewählt, die durch die Zugabschnitte aus drives_out_for_zeit[i,j] bestimmt wird. Der zeitlich kürzeste Weg ergibt sich dann in jedem Fall aus dem minimize 1000 * besteZeit.

Jetzt kannst du im Grunde genommen die ganzen Konstrukte (insbesondere drives_out_for_zeit[i,j]) wegwerfen. Das zweite Array drives_out[i,j] kommt nun ins Spiel. Es soll mir dann meine gewünscht Zugverbindung ausgeben. Hier moddeliere ich dieses Array, so dass es den kostengünstigsten Weg ausspuckt. Analog moddelliere ich für dieses Array den Wert zeit. Zusätzlich können wir aber noch eine Bedingung aufstellen. zeit darf eben nur 1.3 mal größer als besteZeit sein.

Jetzt klarer?
Gruß
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Dragon
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 18. Apr 2006 15:36
Wohnort: Darmstadt

Re: Aufgabe 3.3

Beitrag von Dragon » 25. Aug 2008 13:32

Danke für die schnelle Anwort.
Ich habe jetzt verstanden wie du das Problem modelliert hast.

Wenn man tatsächlich erst die beste Zeit berechnen darf ist sie so auch sicherlich korrekt.
Allerdings glaube ich immer noch nicht, das das überhaupt zulässig ist. :?: :shock:

Darf ich fragen woher du weißt das man das Problem so lösen darfst?

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Re: Aufgabe 3.3

Beitrag von Ultr1 » 25. Aug 2008 13:39

Dragon hat geschrieben:Darf ich fragen woher du weißt das man das Problem so lösen darfst?
Weil der Solver das richtige Ergebnis ausspuckt :twisted:
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Dragon
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 18. Apr 2006 15:36
Wohnort: Darmstadt

Re: Aufgabe 3.3

Beitrag von Dragon » 25. Aug 2008 13:44

Gut das seh ich ein.
Dann hab ich mir die Sache die ganze zeit schwerer gemacht als sie tatsächlich ist.

Antworten

Zurück zu „Algorithmische Modellierung“