Optim.aufgabe Städte,Ähnlichke < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:20 Mi 21.04.2010 | | Autor: | Katrin89 |
| Aufgabe 1 | Ich soll zu der Aufgabe die Funktion minf(x) und die Nebenbedingungen [mm] g_1,...,g_m, [/mm] die >=0 sind, bestimmen.
Aufgabe
a) Es seine die paarweisen Entfernungen d_(ij) zwischen den k+1 Städten [mm] S_0,S_1,...,S_k. [/mm] Gesucht ist eine Tour möglichst kurzer Gesamtlänge, die bei [mm] S_0 [/mm] beginnt, alle Städte durchläuft ud wieder zu [mm] S_0 [/mm] zurückkehrt.
|
| Aufgabe 2 | | b) Es seinen 2n Objekte [mm] O_1,...,O_(2n) [/mm] gege, deren paarweise Ähnlichkeit durch den Parameter [mm] a_(ij)=a(O_i,O_j) [/mm] gemessen wird. Die bjekte sollen in 2 Gruppen [mm] C_1 [/mm] und [mm] C_2 [/mm] mit [mm] abs(C_1)=abs(C_2)=n [/mm] aufgeteilt werden derart, dass die Objekte in den beiden Gruppen untereinander möglichst ähnlich sind. |
Idee zu 1)
min [mm] f(x)=sum(d(S_i,S_j),ij=1,k+1)
[/mm]
[mm] g_1:sum(S_j,j=1,k+1)=k+1, [/mm] aber diese NB ist >=0 und nicht <=0.
Bei der Summe von [mm] g_1 [/mm] weiß ich es nicht, weil sie eine Reihenfolge voraussetzt, oder?
[mm] S_0 [/mm] habe ich noch nicht in eine NB unterbringen können, denke, dass man vllt. ein Glied aus der Summe ziehen könnte...
Idee zu 2) leider keine :-(
Vllt. habt ihr nen Tipp?!?
Liebe Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:49 Mi 21.04.2010 | | Autor: | Katrin89 |
Komme leider auch hier nicht voran...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:08 Fr 23.04.2010 | | Autor: | max3000 |
Zu 1:
Siehe Runreiseproblem (Traveling Salesman problem). Das solltest du eigentlich bei google finden.
Ansonsten als Ansatz: Du suchst Koeffizienten [mm] x_{ij} [/mm] so, dass [mm] x_{ij}=1, [/mm] wenn man von Stadt i nach Stadt j gehen muss, ansonsten 0.
Dann ist Zielfunktion [mm] \sum_{i,j=0}^{k}x_{ij}*d_{ij}
[/mm]
Das ist jetzt die Summe aller gewählten Wege.
Nebenbedingungen sind, dass du von jeder Stadt i zu mindestens einer andere gehen musst, also
[mm] \sum_{j=0}^{k}x_{ij}>=1 [/mm] für alle [mm] j=0,\dots,k
[/mm]
Das ist nur ein Ansatz und nicht vollständig. Da muss es natürlich noch andere Nebenbedingungen geben, die du jetzt vielleicht selber finden kannst.
Für dieses Problem gibt es viele verschiedenen Modelle. Such einfach mal und dann dürftest du eigentlich schnell fündig werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:18 Sa 24.04.2010 | | Autor: | Katrin89 |
Hey, danke!
Habe eine Internetseite gefunden, die es meines Erachtens gut beschreibt. Aber ich verstehe die Bedingung (14) trotz Erklärung nicht. Kann mir das jemand erklären?
Hier ist der Link:
http://www.maphi.de/mathematik/optimierung/opt_speziell_rundreise.html
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:18 So 25.04.2010 | | Autor: | max3000 |
Dort steht ja geschrieben: "Die Bedingung (14) verhindert derartige Teilzyklen. ". Das bedeutet dass man innerhalb einer Rundreise nicht 2 mal an der selben Stadt ankommen darf. Leider ist dort nicht wirklich beschrieben, was die [mm] u_i [/mm] bedeuten und darum würd ich lieber nach einer besseren Beschreibung suchen.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 17:20 So 25.04.2010 | | Autor: | Katrin89 |
Eigentl. fand ich die Beschreibung der anderen Bedingungen und der Zielfunktion ganz passend und auf anderen Internetseiten fand ich es noch übler.
Kann man die Bed. 14 nicht umschreiben oder hast du vllt. ne gute Seite, wo ich es nachlesen könnte?
Meistens ist es viel komplexer als ich es (bis jetzt) bei meiner Aufgabe brauche.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:32 Mi 28.04.2010 | | Autor: | Katrin89 |
Hallo,
ich habe eine andere Homepage gefunden, die das Proglem besser erläutert und ich habe es verstanden. Danke.
Viele Grüße
|
|
|
|
