Übungsaufgabe 3.2

Moderator: Algorithmische Modellierung

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Übungsaufgabe 3.2

Beitrag von David » 19. Jul 2008 14:22

Hallo zusammen,

habe mir schon eine ganze Weile Gedanken zur Aufgabe 3.2 gemacht, aber bin zu keiner vernünftigen Lösung gekommen. Das einzige, was ich bisher habe ist die Eingabe:

Code: Alles auswählen

int+ number_of_vt = ...;		# vt = verkehrstag
int+ number_of_bhfs = ...;
int+ ic_zuschlag = ...;
int+ number_of_zugabschnitte = ...;


range vts = 1..number_of_vt;
range bhfs = 1..number_of:bhfs;
range minuten = 0..59;
range stunden = 0..23;
range boolean = 0..1;
range zugabschnitte = 1..number_of_zugabschnitte;

struct Zeit{
	minuten m;
	stunden h;
	};
	
struct Zugabschnitt{
	bhfs 	abfahrts_bhf;
	bhfs 	ankufts_bhf;
	Zeit	abfahrts_zeit;
	Zeit	ankunfts_zeit;
	int+ 	grundpreis;
	boolean	fahrrad_erlaubt;
	int+ 	id;					#erlaubt?
	};
	
struct Zug{
	{Zugabschnitt} za;
	boolean vt[vts];
	boolean ic;
	};
	
struct Anfrage{
	vts tag;
	Zeit start_zeit;
	bhfs start_bhf;
	bhfs ziel_bhf;
	boolean ic_erlaubt;
	boolean fahrradmitnahme;
	};
	
Zeit umstiegszeit[bhfs] = ...;
{Zug} zuege = ...;

Anfrage a =...;
  
Bin mir aber nicht im klaren, wie ich jetzt den Graph in OPL aufbauen kann, damit das Problem über einen Kürzeste Wege Algorithmus gelöst werden kann.
Wäre nett, wenn jemand Hilfestellungen oder seinen Code posten könnte.

Danke!


Schönen Gruß,

David

tss
Neuling
Neuling
Beiträge: 8
Registriert: 9. Apr 2008 10:40

Re: Übungsaufgabe 3.2

Beitrag von tss » 21. Jul 2008 10:23

Hallo,

also mein Ansatz beginnt ziemlich ähnlich zu deinem. Ich glaube, wir sollten uns erst in der Aufgabe 3.1 von der Idee mit dem Kürzeste-Wege-Algorithmus leiten lassen und in Aufgabe 3.2 wirklich nur das Problem modellieren - das war jedenfalls das, was ich gemacht habe. OPL macht ja ohnehin "was es will", von daher denke ich, dass es OK ist, wenn man den Ansatz mit den kürzesten Wegen mal außer Acht lässt; der gehört ja eher in die Ecke Problemlösung als -modellierung.

Gruß

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe 3.2

Beitrag von Prof. Karsten Weihe » 21. Aug 2008 15:23

David hat geschrieben: Bin mir aber nicht im klaren, wie ich jetzt den Graph in OPL aufbauen kann, damit das Problem über einen Kürzeste Wege Algorithmus gelöst werden kann.
Ich habe in der Aufgabenstellung den Hinweis zu geben, genau das nicht zu versuchen, sondern das Problem einfach wie gegeben zu modellieren.

Gruß,

KW

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Re: Übungsaufgabe 3.2

Beitrag von David » 23. Aug 2008 12:27

Prof. Karsten Weihe hat geschrieben: Ich habe in der Aufgabenstellung den Hinweis zu geben, genau das nicht zu versuchen, sondern das Problem einfach wie gegeben zu modellieren.
Ich hatte
Sie brauchen nicht den Graphen aus der Vorlesung aufzubauen, können die Aufgabe aber durchaus so lösen, wenn es Ihnen sinnvoll erscheint. In diesem Fall würde Ihnen initialize vielleicht gute Dienste leisten.
wohl nicht korrekt als Hinweis interpretiert, nicht den Graphen aus der Vorlesung aufzubauen. :wink:

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

Re: Übungsaufgabe 3.2

Beitrag von Dragon » 23. Aug 2008 14:13

Hallo,

ich habe die Implementierung auch ungefähr so angefangen wie du.
Allerdings habe ich schwierigkeiten die Bedingungen aufzustellen.
Wie kann man denn mit Sets in OPL umgehen? Ich suche etwas wie in dieser Menge existiert ein Element,
dass diese Eigenschaften hat.

Danke

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

Re: Übungsaufgabe 3.2

Beitrag von Ultr1 » 24. Aug 2008 11:28

Ich werde von der aktuellen 6.0 Version von ILOG OPL reden:

Sets als Decision Variable (dvar) sind garnicht möglich. Ich habe es so gemacht: Als Input fordere ich ein beliebig großes Set von Zugabschnitten. Ein Zuabschnitt ist ein tuple, welches alle Informationen diesbezgl. beinhaltet. Die Größe dieses Eingabe-Sets erhälst du durch den Befehl card(some_set). Vergesse nicht using CP; zu Beginn der mod Datei zu setzen. Da Sets in der Ausgabe nicht möglich sind, gebe ich einfach eine boolean-Bitmatrix der eben genannten Größe aus, welche dann auf die Zugabschnitte hinweist, welche für die Fahrt genutzt werden sollen.

Nun musst du noch die verschiedenen Bedingungen modellieren. Du musst modellieren wann ein kürzester Pfad ensteht. Außerdem musst du weitere Bedingungen für das umsteigen etc aufstellen. Da Zykel ausgeschlossen sind, weißt du sicher welcher Zug an welchem Bahnhof wann ankommt. Ich würde auch empfehlen nicht den Ansatz mit den IC Kanten aus der Vorlesung zu wählen, indem man einen zweiten Graph baut. Du iterierst einfach über den gesamten Pfad und kannst leicht feststellen, ob irgendwo ein IC-Abschnitt dabei war.

Ich hoffe das hilft weiter, 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: Übungsaufgabe 3.2

Beitrag von Dragon » 24. Aug 2008 12:16

Hallo,

also das hilft mir jetzt nur wenig weiter. Ich möchte ja auf Elemente der Sets zugreifen.
Muss man die Aufgabe überhaupt mit "richtigen" Sets modellieren oder kann man auch Felder verwenden wie in
der Lösung oben?

Vielleicht kannst du einfach mal deine Lösung posten?

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

Re: Übungsaufgabe 3.2

Beitrag von Ultr1 » 24. Aug 2008 12:27

Auf Inhalte von Sets, kannst du mit dem Befehl item(some_set,index) zugreifen. Viele Befehle habe ich mir durch den Klick auf Hilfe -> Inhalt der Hilfetexte erarbeitet.

Ich poste hier einfach mal meinen Vorschlag

Code: Alles auswählen

using CP;

 int number_of_verkehrstage = ...;
 int number_of_stations = ...;
 int number_of_requests = ...;
 
 range verkehrstage = 1..number_of_verkehrstage;
 range stations = 1..number_of_stations;
 range requests = 1..number_of_requests;
 range bool = 0..1;
 
 int umstiegszeit[stations] = ...;
 int ic_zuschlag_cost = ...;
 
  tuple anfrage {
 	int startbf;
 	int zielbf;
 	int starttime;
 	int ic_allowed;
 	int bike_wanted;
 	int tag;
 }
 
 tuple drive {
 	int trainnr;
 	int startbf;
 	int starttime;
 	int zielbf;
 	int zieltime;
 	int grundpreis;
 	int bike;
 	int ic_kante;
 	int fahrtage[verkehrstage]; // boolean matrix an welchen tag es ist
 }

// als eingabe wird eine menge von stationsübergängen gegeben. ausgabe ist eine matrix welche wir davon benutzen
 {drive} drives_in = ...;
 int number_of_drives = card(drives_in);
 range drives = 0..(number_of_drives-1);
 dvar int drives_out[requests,drives] in bool;
 
 {anfrage} request = ...;
 
 int ic_used;
 
minimize (sum(i in requests, j in drives) drives_out[i,j] * item(drives_in,j).grundpreis) + ic_used * ic_zuschlag_cost;
subject to {

	// sobald ein ic genutzt wurde wird ic_used zu 1
	forall (i in requests)
		ic_used == max(j in drives) drives_out[i,j] * item(drives_in,j).ic_kante;

	// es muss eine verbindung von start zu ziel bestehen
	
	// die anzahl der abgehenden kanten vom start muss 1 sein
	forall (i in requests)
		sum(j in drives) drives_out[i,j] * (item(drives_in,j).startbf == item(request,i-1).startbf) == 1;
			// i-1 weil sets ab 0 durchnummeriert sind....
			
			
	// die anzahl der eingehenden kanten des ziel ist 1
	forall (i in requests)
		sum(j in drives) drives_out[i,j] * (item(drives_in,j).zielbf == item(request,i-1).zielbf) == 1;
	
	// zum start führt keine kante
	forall (i in requests)
		sum(j in drives) drives_out[i,j] * (item(drives_in,j).zielbf == item(request,i-1).startbf) == 0;
	
	// vom ziel geht keine kante ab
	forall (i in requests)
		sum(j in drives) drives_out[i,j] * (item(drives_in,j).startbf == item(request,i-1).zielbf) == 0;
	
	// von jedem bf wird nur eine oder keine ausgehende kante genutzt
	forall (i in requests, j in stations)
		sum (k in drives) drives_out[i,k] * (item(drives_in,k).startbf == j) <= 1;
		
	// ist der bahnhof nicht start und ziel so ist #inedges == #outedges
	forall (l in requests)
		forall ( i in stations)
			i != item(request,l-1).startbf && i != item(request,l-1).zielbf =>
				sum (j in drives) drives_out[l,j] * (item(drives_in,j).startbf == i)
					== sum (k in drives) drives_out[l,k] * (item(drives_in,k).zielbf == i);
				
	// wird der zug gewechselt, muss die umsteigezeit eingehalten werden
	forall (i in requests,j in drives, k in drives)
		drives_out[i,j] == 1 && drives_out[i,k] == 1 && item(drives_in,j).zielbf == item(drives_in,k).startbf
			=> item(drives_in,k).starttime - item(drives_in,j).zieltime  >= umstiegszeit[item(drives_in,j).zielbf];
			
	// ist fahhradmitnahme gewünscht dürfen nur entsprechende züge genommen werden
	forall (i in requests)
		forall (j in drives)
			item(request,i-1).bike_wanted == 1 && item(drives_in,j).bike == 0 => drives_out[i,j] == 0;	
		
	// sind ICs unerwünscht dürfen diese züge nicht genutzt werden
	forall (i in requests)
		forall (j in drives)
			item(request,i-1).ic_allowed == 0 && item(drives_in,j).ic_kante == 1 => drives_out[i,j] == 0;	
		
	// es dürfen nur zugabschnitte genommen werden, die auch am gewünschten tag fahren
	forall (i in requests)
		forall (j in drives, k in verkehrstage)
			item(request,i-1).tag == k && item(drives_in,j).fahrtage[k] == 0 => drives_out[i,j] == 0;	
};
.dat-file:

Code: Alles auswählen

number_of_verkehrstage = 7;
number_of_stations = 4;
number_of_requests = 3;
umstiegszeit = [ 3,2,1,5];
ic_zuschlag_cost = 9;

// int trainnr; int startbf; int starttime; int zielbf;	int zieltime; int grundpreis;int bike;int fahrtage[verkehrstage];
drives_in = {
	<1,1,0,2,1,1,1,0,[1,1,1,1,1,1,0]>,
	<1,2,1,3,2,3,0,0,[0,1,1,1,1,1,1]>,
	
	<2,1,4,3,5,4,1,1,[1,1,1,1,1,1,1]>,
	<2,3,7,4,9,1,1,0,[1,1,1,1,1,1,1]>,
	
	<3,2,3,3,6,1,1,0,[1,1,1,1,1,1,0]>
};

// int startbf;int zielbf;int starttime;int ic_allowed;int bike_wanted;int tag
request = {
	<1,4,0,1,1,3>,
	<2,4,1,1,1,2>,
	<1,4,0,1,1,5>
};


// zugrundeliegender graph:
/*                            /
       st2                   /   line 1
      / |\
    1/  | \3				|
    /   |  \				| line 3
   /    |   \
st1     |1   st4
   *    |   *               *
    *   |  *               *   line 2
    4*  |  *1
      * |*
       st3
 */
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Antworten

Zurück zu „Algorithmische Modellierung“