Folie SE II
Transcrição
Folie SE II
Fakultät Wirtschafts- und Sozialwissenschaften Professur für BWL, insbes. Wirtschaftsinformatik Holstenhofweg 85 22043 Hamburg SEII 16.05.09 Softwareentwicklung: Frühjahrstrimester 2009 Projektarbeit Organisatorisches Problemstellungen SELibrary Organisatorisches (Fortsetzung) Jens Czogalla [email protected] http://ifi.hsu-hh.de Organisatorisches Organisatorisches Zielgruppe: Studiengang BWL-Bachelor, 6. Trimester Formales Ziel der Vorlesung: Abschlussklausur Projektarbeit Umfang: 109 Stunden (Workload gem. Modulhandbuch) 1-2 Organisatorisches Organisatorisches Materialien: http://hsu-hh.de/ifi Grundlagen Windows Forms (Auswahl): Webcasts (Bernd Marquardt): http://www.microsoft.com/germany/msdn/webcasts/serien/MSDNWCS-0712-01.mspx Online-Buch http://openbook.galileocomputing.de/visual_csharp/ Online-Hilfe: http://msdn.microsoft.com/de-de/default.aspx 1-3 Problemstellungen Übersicht Travelling Salesman Problem Vehicle Routing Problem SUDOKU 1-4 Travelling Salesman Problem Problemstellung Gesucht ist die kürzeste Tour (Rundreise) durch m Städte. Jede Stadt soll genau einmal besucht werden. (vgl. GdWI Folie 4-36/37) Anzahl der Städte m Distanzmatrix C = (cij), i, j {1,...,m}, i ≠ j NP-schweres Optimierungsproblem (vgl. GdWI Folie 4-39) Sehr viele Variationen der Problemstellung möglich 1-5 Travelling Salesman Problem Beispiel 3 5 1 4 1 1 2 2 3 4 5 2,0 4,2 2,2 2,2 3,2 2,2 3,6 2,2 4,1 2 2,0 3 4,2 3,2 4 2,2 2,2 2,2 5 2,2 3,6 4,1 2,0 2,0 Tourenplanung in der Logistik Design/Produktion von Leiterplatten Methoden der Bioinformatik (DNA-Sequenzierung) 1-6 Travelling Salesman Problem Weitere Beispiele 7.397 Punkte auf PLA (1994) 15.112 Städte in Deutschland (2001) [Quelle: http://www.tsp.gatech.edu] 1-7 Travelling Salesman Problem Lösungsverfahren Heuristiken Nearest Neighbor (Nächster Nachbar) Spanning Tree Insertion ... Meta-Heuristiken Iterated Local Search (Iterative Lokale Suche) Simulated Annealing ... 1-8 Travelling Salesman Problem Quellen (kleine Auswahl) Bücher: Domschke, Logistik: Rundreisen und Touren. Oldenbourg Verlag, München, 1997. Grünert und Irnich, Optimierung im Transport. Band II: Wege und Touren. Shaker Verlag, Aachen, 2005. Hußmann und Lutz-Westphal (Hrsg.) Kombinatorische Optimierung erleben. Vieweg Verlag, Wiesbaden, 2007. (Volltextzugang Campus: http://springerlink.com/content/x35k73) Web: Algorithmus der Woche: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php Englischsprachige TSP-Seite: http://www.tsp.gatech.edu//index.html Visualisierung von TSP-Heuristiken:http://bjornson.inhb.de/?p=26 TSP-Spiel:http://www.tsp.gatech.edu/games/tspOnePlayer.html 1-9 Vehicle Routing Problem Problemstellung Gesucht ist die kürzeste Gesamtstrecke (Touren) bei der (alle) Kunden aus Depots beliefert werden. Jeder Kunde ist genau einmal zu besuchen. Ladekapazitäten der (identischen) Fahrzeuge sind einzuhalten. (Verallgemeinertes Travelling Salesman Problem) Capacitated Vehicle Routing Problem (CVRP) 1 Depot (Index 0) n Kunden mit Bedarf bi (darf nicht gesplittet werden) M identische Fahrzeuge mit Kapazität cap Distanzmatrix C = (cij), i, j {0,...,n}, i ≠ j Minimierung der insgesamt zurückgelegten Entfernung NP-schweres Optimierungsproblem 1-10 Vehicle Routing Problem Beispiel 3 1 5 4 1 1 2 2 D 1 2 D D 1 2 3 4 5 1,4 3,2 5,7 3,6 3,0 2,0 4,2 2,2 2,2 3,2 2,2 3,6 2,2 4,1 1 1,4 2 3,2 2,0 3 5,7 4,2 3,2 4 3,6 2,2 2,2 2,2 5 3,0 2,2 3,6 4,1 2,0 2,0 3 1-11 Vehicle Routing Problem Lösungsverfahren Heuristiken Sweep Petal Saving ... Meta-Heuristiken Iterated Local Search (Iterative Lokale Suche) (Simulated Annealing) ... 1-12 Vehicle Routing Problem Quellen (kleine Auswahl) Bücher: Domschke, Logistik: Rundreisen und Touren. Oldenbourg Verlag, München, 1997. Grünert und Irnich, Optimierung im Transport. Band II: Wege und Touren. Shaker Verlag, Aachen, 2005. Web: Visualisierung Route Planning: http://www.dna-evolutions.com/dnaappletsample.html 1-13 SUDOKU Problemstellung Ein 9x9 Gitter ist so zu füllen, dass jede Ziffer in einer Spalte, in einer Zeile und in einem Block genau einmal vorkommt. 1 9 2 6 6 7 6 3 3 5 9 1 8 9 7 8 7 6 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-14 SUDOKU Lösungsmöglichkeit 2 6 5 1 2 3 1 2 3 4 5 6 4 5 6 1 9 7 1 2 3 1 2 3 6 3 4 5 6 7 8 9 9 3 5 9 1 8 7 8 9 7 8 9 1 2 3 6 6 7 8 9 7 8 9 4 5 6 4 5 6 2 9 7 8 7 6 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-15 SUDOKU Lösungsmöglichkeit 2 6 5 Block 1 2 3 1 2 3 4 5 6 4 5 6 1 9 7 1 2 3 1 2 3 6 3 4 5 6 7 8 9 9 3 5 9 1 8 7 8 9 7 8 9 1 2 3 6 6 7 8 9 7 8 9 4 5 6 4 5 6 2 9 7 8 7 6 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-16 SUDOKU Lösungsmöglichkeit 2 6 5 Zeile 1 2 3 1 2 3 4 5 6 4 5 6 1 9 7 1 2 3 1 2 3 6 3 4 5 6 7 8 9 9 3 5 9 1 8 7 8 9 7 8 9 1 2 3 6 6 7 8 9 7 8 9 4 5 6 4 5 6 2 9 7 8 7 6 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-17 SUDOKU Lösungsmöglichkeit 2 6 5 Spalte 1 2 3 1 2 3 4 5 6 4 5 6 1 9 7 1 2 3 1 2 3 6 3 4 5 6 7 8 9 9 3 5 9 1 8 7 8 9 7 8 9 1 2 3 6 6 7 8 9 7 8 9 4 5 6 4 5 6 2 9 7 8 7 6 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-18 SUDOKU Lösungsmöglichkeit 2 6 5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 1 9 7 1 6 3 2 7 6 1 5 9 1 8 6 3 9 7 8 7 6 9 6 8 4 8 6 3 2 8 2 5 1 1 4 6 3 8 9 1-19 SUDOKU Quellen (kleine Auswahl) Web: SUDOKU-Lobby: http://www.sudoku-lobby.de/ Mathematische Basteleien: http://www.mathematische-basteleien.de/sudoku.htm Sudoku lösen: http://arbeitsblaetter.stangl-taller.at/GEDAECHTNIS/Sudoku.shtml 1-20 SELibrary Klassendiagramm 1-21 SELibrary Verwendung 1-22 SELibrary Verwendung using SELibrary; ... class TSP : BaseTSP { } 1-23 SELibrary Verwendung TSP tsp = new TSP(); string file = @“C:\a280.tsp“; bool isLoaded = tsp.Load(file); // foreach-Schleife über alle Städte foreach (Depot city in tsp) … // Zugriff auf einzelne Stadt tsp[1].X … 1-24 Organisatorisches Organisatorisches Gruppenarbeit in 2er/3er Teams Termine: Aufgabenvergabe 1. Zwischenbesprechung Erläuterung Aufgabenstellung Lösungsansatz (Klassendesign) 2. Zwischenbesprechung Offene Fragen Abgabe der Projektarbeit und Präsentation 1-25 Organisatorisches Erwartungen Objektorientiertes Design Implementierung der geforderten Algorithmen Grafische Visualisierung der Lösung (für Fortgeschrittene) Projektarbeit (schriftliche Ausarbeitung) & Präsentation 1-26 Organisatorisches Projekte Travelling Salesman Problem Nearest Neighbor (Nächster Nachbar) Heuristik und Verbesserung der Tour durch Simulated Annealing (2-opt Nachbarschaft) (Cheapest) Insertion (Einfüge) Heuristik und Verbesserung der Tour durch Iterated Local Search (2-opt Nachbarschaft) Patching Heuristik Vehicle Routing Problem Sweep Heuristik Savings Heuristik SUDOKU Lösungsverfahren gem. Folien 15-19 1-27