Συνδυαστική Βελτιστοποίηση - Σχολή Μηχανικών Παραγωγής και Διοίκησης

(1) ΓΕΝΙΚΑ

ΣΧΟΛΗ	Μηχανικών Παραγωγής και Διοίκησης
2η ΣΧΟΛΗ
ΕΠΙΠΕΔΟ ΣΠΟΥΔΩΝ	Προπτυχιακό
ΚΩΔΙΚΟΣ ΜΑΘΗΜΑΤΟΣ	ΜΠΔ 426	ΕΞΑΜΗΝΟ ΣΠΟΥΔΩΝ	5^ο
ΑΥΤΟΤΕΛΕΙΣ ΔΙΔΑΚΤΙΚΕΣ ΔΡΑΣΤΗΡΙΟΤΗΤΕΣ	ΕΒΔΟΜΑΔΙΑΙΕΣ ΩΡΕΣ ΔΙΔΑΣΚΑΛΙΑΣ		ΠΙΣΤΩΤΙΚΕΣ ΜΟΝΑΔΕΣ
Διαλέξεις	3
Εργαστήρια	2
Σύνολο	5		5
ΤΥΠΟΣ ΜΑΘΗΜΑΤΟΣ	Γενικού υποβάθρου
ΠΡΟΑΠΑΙΤΟΥΜΕΝΑ ΜΑΘΗΜΑΤΑ
ΓΛΩΣΣΑ ΔΙΔΑΣΚΑΛΙΑΣ KAI ΕΞΕΤΑΣΕΩΝ	Ελληνικά
ΤΟ ΜΑΘΗΜΑ ΠΡΟΣΦΕΡΕΤΑΙ ΣΕ ΦΟΙΤΗΤΕΣ ERASMUS	Ναι
ΗΛΕΚΤΡΟΝΙΚΗ ΣΕΛΙΔΑ ΜΑΘΗΜΑΤΟΣ (URL)	https://www.eclass.tuc.gr/courses/MPD194/

(2) ΜΑΘΗΣΙΑΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ

Μαθησιακά Αποτελέσματα

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής/τρια θα είναι σε θέση να:

Περιγράφει Προβλήματα Συνδυαστικής Βελτιστοποίησης, όπως προβλήματα μέγιστης ροής, εύρεσης συντομότερης διαδρομής, ροής ελαχίστου κόστους, προβλήματα μεταφοράς, ανάθεσης
Εφαρμόζει μεθόδους και αλγορίθμους επίλυσης των προβλημάτων συνδυαστικής βελτιστοποίησης, όπως ο αλγόριθμος διακλάδωσης και οριοθέτησης, ο αλγόριθμος DINIC, o αλγόριθμος Kruskal, o αλγόριθμος Ford Fulkerson, ο αλγόριθμος Floyd- Warshall
Προγραμματίζει τους αλγορίθμους επίλυσης των προβλημάτων Συνδυαστικής Βελτιστοποίησης σε γλώσσες προγραμματισμού Matlab, C, C++ και Python
Αναλύει προβλήματα που εμφανίζονται στην καθημερινότητα του ως μηχανικός, όπως ο σχεδιασμός ενός αποχετευτικού δικτύου ή ενός δικτύου ύδρευσης ή ενός δικτύου μεταφορών
Χρησιμοποιεί έτοιμα πακέτα λογισμικού για την επίλυση προβλημάτων συνδυαστικής βελτιστοποίησης

Γενικές Ικανότητες

Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
Λήψη αποφάσεων
Παραγωγή νέων ερευνητικών ιδεών
Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης
Γραπτή επικοινωνία
Προφορική επικοινωνία
Πρωτοβουλία
Εναλλακτική/Καινοτόμος σκέψη
Χρήση Υπολογιστή
Επίλυση προβλημάτων
Διαχείριση αριθμητικών δεδομένων
Εργασία σε διεπιστημονικό περιβάλλον

(3) ΠΕΡΙΕΧΟΜΕΝΟ ΜΑΘΗΜΑΤΟΣ

Μαθηματικά πρότυπα και εφαρμογές της Συνδυαστικής Βελτιστοποίησης. Διαφορές μεταξύ ακέραιου και Γραμμικού Προγραμματισμού. Γραφήματα και δίκτυα. Δομές δεδομένων για δίκτυα και γραφήματα. Ανίχνευση γραφημάτων. Βέλτιστες διαδρομές και διακριτός Δυναμικός Προγραμματισμός. Τανύοντα δένδρα και αλγόριθμοι απληστίας. Προβλήματα ροών. Περιπλοκότητα αλγορίθμων και προβλημάτων. Γραμμική και Λαγκρανζιανή χαλάρωση. Μέθοδος Branch-and-Bound. Μέθοδος Τοπικής Ανίχνευσης. Ευρεστικοί Αλγόριθμοι. Αλγόριθμοι προσέγγισης. Μετα-ευρεστικοί Αλγόριθμοι.

Εργαστήρια: Για την καλύτερη κατανόηση του μαθήματος, οι φοιτητές καλούνται να εκπονήσουν τρεις εργαστηριακές ασκήσεις σε γλώσσα Προγραμματισμού C ή Matlab, υλοποιώντας αλγόριθμους επίλυσης προβλημάτων Συνδυαστικής Βελτιστοποίησης.

(4) ΔΙΔΑΚΤΙΚΕΣ KAI ΜΑΘΗΣΙΑΚΕΣ ΜΕΘΟΔΟΙ – ΑΞΙΟΛΟΓΗΣΗ

ΤΡΟΠΟΣ ΠΑΡΑΔΟΣΗΣ

Με φυσική παρουσία

ΧΡΗΣΗ ΤΕΧΝΟΛΟΓΙΩΝ ΠΛΗΡΟΦΟΡΙΑΣ ΚΑΙ ΕΠΙΚΟΙΝΩΝΙΩΝ
Στη διδασκαλία:	Σημειώσεις και παρουσιάσεις των διαλέξεων του μαθήματος στο e-class
Στην εργαστηριακή εκπαίδευση:	Σημειώσεις και παρουσιάσεις των εργαστηριακών διαλέξεων στο e-class Εκμάθηση γλωσσών προγραμματισμού και χρήση τους για δημιουργία προγραμμάτων στο αντικείμενο του μαθήματος
Στην επικοινωνία με τους φοιτητές:	e-mail και eclass . Επίλυση αποριών μέσω τηλεδιάσκεψης

ΟΡΓΑΝΩΣΗ ΔΙΔΑΣΚΑΛΙΑΣ
Διαλέξεις	39 ώρες
Εργαστήρια	26 ώρες
Εκπόνηση Εργαστηριακών Ασκήσεων	21 ώρες
Αυτοτελής μελέτη	39 ώρες
Σύνολο	125 ώρες

Διδακτέα Ύλη ανά Εβδομάδα (13 εβδομάδες) :

Α) Διαλέξεις

1) Εισαγωγή στη Θεωρία Γραφημάτων
2) Αλγοριθμική Πολυπλοκότητα
3) Ταξινόμηση Προβλημάτων και Δομές Δεδομένων
4) Ανίχνευση Γραφημάτων
5) Ο Αλγόριθμος Διακλάδωσης και Οριοθέτησης
6) Ο Αλγόριθμος Οπισθοϊχνηλασίας
7) Δυναμικός Προγραμματισμός
8) Το πρόβλημα της Μέγιστης Ροής
9) Το πρόβλημα Εύρεσης της Συντομότερης Διαδρομής
10) Το πρόβλημα του Ζευγνύοντος Δέντρου, Μητροειδή Προβλήματα και Αλγόριθμοι Απληστίας
11) Το πρόβλημα Ροής Ελαχίστου Κόστους
12) Το πρόβλημα μεταφοράς και το πρόβλημα του Πλανώδιου Πωλητή
13) Το πρόβλημα ανάθεσης και προβλήματα ταιριάσματος

Β) Εργαστήρια

1) Εισαγωγή στις γλώσσες προγραμματισμού που χρειάζονται στο εργαστήριο (Matlab, C, C++, Python)
2) Εισαγωγή στις γλώσσες προγραμματισμού που χρειάζονται στο εργαστήριο Matlab, C, C++, Python (2ο μάθημα)
3) Παρουσίαση παραδειγμάτων θεωρίας γραφημάτων με χρήση γλώσσας προγραμματισμού
4) Ο αλγόριθμος DFS και BFS με χρήση γλώσσας προγραμματισμού. Παρουσίαση και ανάλυση της πρώτης εργαστηριακής άσκησης
5) Αλγόριθμος διακλάδωσης και οριοθέτησης με χρήση γλώσσας προγραμματισμού.
6) Αλγόριθμος οπισθοιχνηλασίας με χρήση γλώσσας προγραμματισμού.
7) Αλγόριθμος δυναμικού προγραμματισμού με χρήση γλώσσας προγραμματισμού. Παρουσίαση και ανάλυση της δεύτερης εργαστηριακής άσκησης
8) Αλγόριθμοι Ford-Fulkerson και Dinic με χρήση γλώσσας προγραμματισμού.
9) Αλγόριθμοι Dijkstra και Belman-Ford με χρήση γλώσσας προγραμματισμού.
10) Αλγόριθμοι Kruskal, Prim και Solin Boruvska με χρήση γλώσσας προγραμματισμού. Παρουσίαση και ανάλυση της τρίτης εργαστηριακής άσκησης
11) Επανάληψη και επίλυση αποριών (1ο μάθημα)
12) Επανάληψη και επίλυση αποριών (2ο μάθημα)
13) Εξέταση εργαστηριακών ασκήσεων

(5) ΑΞΙΟΛΟΓΗΣΗ ΦΟΙΤΗΤΩΝ

Αθροιστική/Συμπερασματική (για βαθμό φοιτητή) Αξιολόγηση
Γραπτή Τελική Εξέταση	70%	(Ερωτήσεις επίλυσης προβλημάτων)
Ασκήσεις Εργαστηρίου	30%	(Προφορική Εξέταση)
		(Διόρθωση Παραδομένης Εργασίας)

(6) ΣΥΝΙΣΤΩΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ

Διδασκόμενα Βιβλία

Συνδυαστική Βελτιστοποίηση (2016). Ιωάννης Μαρινακης, Αθανάσιος Μυγδαλας, ISBN: 978-960-578-022-7, ΕΚΔΟΣΕΙΣ ΝΕΩΝ ΤΕΧΝΟΛΟΓΙΩΝ ΙΔΙΩΤΙΚΗ ΚΕΦΑΛΑΙΟΥΧΙΚΗ ΕΤΑΙΡΕΙΑ
Αλγόριθμοι (2017) Μποζάνης Παναγιώτης, ISBN: 978-960-418-667-9, ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε.
Μαθηματικά και Θεωρία Γραφημάτων για Μηχανικούς (2016) Αλεξίου Δήμητρα, ISBN: 978-960-418-649-5, ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε.

Προτεινόμενη Ξένη Βιβλιογραφία:

Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice-Hall, New Jersey.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.
Martello, S. and Toth, P. (1990). Knapsack Problems, John Wiley, New York.
Schrijver, A. (1984). Linear and Integer Programming, John Wiley, New York.

Συναφή Περιοδικά:

European Journal of Operational Research
Computers and Operations Research
Applied Soft Computing
Mathematical Programming
Operations Research

Πολυτεχνείο Κρήτης

Χρήσιμα

Επικοινωνία