Ιστοσελίδα Μαθήματος ΤΕΜ-231: Γραμμικός και Μη Προγραμματισμός (Linear and Non-linear Programming)

Χειμερινό Εξάμηνο 2013/14

 

Διδάσκων:  Χαρμανδάρης Ευάγγελος

email: vagelis@tem.uoc.gr

 

Ανακοινώσεις

[30/06/14]  Αποτελέσματα Τελικής Εξέτασης Ιουνίου: Τελική Βαθμολογία

 

[24/02/14]  Project Μαθήματος:

 

1) Πρόβλημα του Περιπλανώμενου Πωλητή

Ανεβλαβής Μιχάλης,  Κουτσογιαννάκης Γεώργιος, Μουτάφης Ιωάννης

 

2) Το πρόβλημα του ελάχιστου δέντρου που καλύπτει ένα γράφο

Κοκκάλα Γεωργία, Παρασκευαίδης Μάριος, Παπαχρήστου Γιώργος, Σίμου Θεοδώρα

 

3) Πρόβλημα του Περιπλανώμενου Πωλητή: Μια Αναλυτική Προσέγγιση

Φώτογλου Ιωακείμ

 

 

[23/02/14]  Αποτελέσματα Τελικής Εξέτασης: Τελική Βαθμολογία

 

 

[22/01/14]  Αποτελέσματα Προόδου: Βαθμολόγιο Προόδου

 

[20/01/14]  Προσοχή— Σας ενημερώνω ότι:

 

1) Η εξέταση των εργαστηριακών ασκήσεων θα γίνει στο εργαστήρι αυτή την εβδομάδα: Την Πέμπτη (23/01) 14:00-16:30 για την Ομάδα 1 (της Τρίτης) και Παρασκευή (24/01) 14:00-16:30 για την Ομάδα 2 (Πέμπτης).  Για την εξέταση φέρτε μαζί σας τις αναφορές (ή και τα αρχεία της MATLAB) σε κάποιο usb stick ΚΑΙ τις αναφορές εκτυπωμένες.

 

2) Επίσης λόγω  αρκετών αιτημάτων θα γίνει extra 2ωρο αυτή την Πέμπτη (23/01) 11:00-13:00 με την λύση ορισμένων  εργαστηριακών ασκήσεων.

 

3) Η Εξεταστέα Ύλη του μαθήματος είναι:

 

Α) Βιβλίο Luenberger and Ye:  Κεφάλαια 2, 3, 4 (Γ.Π.) και  7, 8, 11 (Μ.Γ.Π.)

 

Β) Βιβλίο Φακίνου και Οικονόμου: Κεφάλαια 1 (Γ.Π.), 3 (Δ.Π.) και 4 (Μ.Γ.Π.)

 

 

[12/01/14]  Σας ενημερώνω ότι παρακάτω μπορείτε να βρείτε τη 3η Σειρά Ασκήσεων του μαθήματος.

 

[09/12/13]  Σας ενημερώνω ότι παρακάτω μπορείτε να βρείτε τη 2η Σειρά Ασκήσεων του μαθήματος.

 

[23/11/13]  Σας ενημερώνω ότι τη Δευτέρα 25/11 11:00-13:00 δεν θα γίνει θεωρία αλλά θα γίνει το εργαστήριο της 2ης ομάδας που είχε αναβληθεί.

 

[22/11/13]  Σας ενημερώνω ότι παρακάτω μπορείτε να βρείτε τη 1η Σειρά Ασκήσεων του μαθήματος.

 

[20/11/13]  Σας ενημερώνω ότι παρακάτω μπορείτε να βρείτε όλα τα προγράμματα MATLAB που χρησιμοποιούμε στο εργαστήριο από το βιβλίο  «Linear programming with MATLAB», M.C. Ferris, O.L. Mangasarian, S.J. Wright, SΙΑΜ, 2007.

 

[20/11/13]  Σας ενημερώνω ότι η πρόοδος του μαθήματος θα γίνει την Πέμπτη 05/12 στην ώρα του μαθήματος, 09:00-11:00, στην αίθουσα Α203.

 

[14/11/13] Το φροντιστήριο με ασκήσεις θα γίνεται πλέον ΚΑΘΕ Πέμπτη 11:00-13:00 στην αίθουσα Α208.

 

[04/11/13] Σας ενημερώνω ότι την επόμενη Πέμπτη (07/11) 11:00-13:00 θα γίνει έκτακτο φροντιστήριο με ασκήσεις στην Α208 από τη βοηθό, κ. Σοφία Χατζητόλιου.

 

[28/10/13] Μπορείτε να γραφτείτε στα εργαστήρια του μαθήματος (Matlab) στη παρακάτω διεύθυνση:

https://doodle.com/775i2wwnrhpniaxi?tmail=poll_invitecontact_participant_invitation&tlink=pollbtn

Υπάρχουν 2 δυνατότητες:

1) Τρίτη 09:00-11:00

2) Πέμπτη 15:00-17:00

Διαλέξτε μια από τις 2. Υπάρχει όριο 65 ατόμων ανά ημέρα, όσοι είναι περίπου οι διαθέσιμοι υπολογιστές.

Επαναλαμβάνω ότι οι παρουσίες στα εργαστήρια δεν είναι υποχρεωτικές. Είναι όμως μια καλή ευκαιρία να μάθετε τις μεθόδους ΓΜΠ.

 

Ύλη του Μαθήματος

Το μάθημα αυτό αποτελεί μια εισαγωγή σε προβλήματα βελτιστοποίησης γραμμικού και μη-γραμμικού προγραμματισμού (linear and non-linear programming). Κύριοι στόχοι του μαθήματος είναι:

· Η κατανόηση της βασικής θεωρίας γραμμικού και μη-γραμμικού προγραμματισμού.

· Η αναλυτική περιγραφή/εξέταση βασικών μεθόδων γραμμικού προγραμματισμού (μέθοδος simplex).

· Η μελέτη επιλεγμένων μεθόδων μη-γραμμικού προγραμματισμού για προβλήματα βελτιστοποίησης χωρίς περιορισμούς καθώς και με περιορισμούς.

· Η χρήση/εφαρμογή των παραπάνω αριθμητικών μεθόδων σε ένα εύρος διαφορετικών προβλημάτων.

 

Το μάθημα αποτελείται από τα παρακάτω κεφάλαια: Αρχικά, στην εισαγωγή θα δούμε τις βασικές έννοιες και τους στόχους των προβλημάτων βελτιστοποίησης  Επίσης θα δούμε το πρόβλημα του Γραμμικού Προγραμματισμού (ΓΠ) και το δυϊκό του με αντίστοιχα παραδείγματα. Κατόπιν θα παρουσιάσουμε μια σύντομη αναφορά στα κύρια θεωρήματα του (ΓΠ). Το επόμενο (τρίτο) κεφάλαιο αφορά το βασικό πυρήνα των μεθόδων ΓΠ. Θα δούμε αναλυτικά τη μέθοδο simplex με αντίστοιχες εφαρμογές.  Στο τέταρτο κεφάλαιο παρουσιάζονται συνοπτικά προβλήματα Δυναμικού προγραμματισμού (ΔΠ). Το πέμπτο κεφάλαιο αφορά τις βασικές μεθόδους Μη Γραμμικού Προγραμματισμού. Θα παρουσιαστούν ενδεικτικά προβλήματα χωρίς και με περιορισμούς.  Το τελευταίο κεφάλαιο αφορά μια σειρά επιλεγόμενων θεμάτων, πέραν της βασικής ύλης, όπως τη θεωρητική μελέτη σύγκλισης των αλγορίθμων, εφαρμογές σε διαφορετικές επιστήμες κλπ.

 

Βιβλιογραφία

· Linear and Non-linear Programming, 3rd edition, D.G. Luenberger and Yinyu Ye, Springer, 2008.

· Linear programming with MATLAB, M.C. Ferris, O.L. Mangasarian, S.J. Wright, SΙΑΜ, 2007.

· Linear Programming 1: Introduction, G.B. Dantzig and M. N. Thapa, Springer, 1997.

· Linear Programming 2: Theory and Extensions, G.B. Dantzig and M. N. Thapa, Springer, 1997.

· Εισαγωγή στην Επιχειρησιακή Έρευνα, Φακίνος και Οικονόμου, Αθήνα 2003.

 

 

Διδασκαλία  - Αξιολόγηση

Για τις διδακτικές ανάγκες του μαθήματος θα χρησιμοποιηθούν οι σημειώσεις.  Η αξιολόγηση θα βασιστεί κατά κύριο λόγο στη συμμετοχή, σε σειρές ασκήσεων, σε μια ενδιάμεση πρόοδος και στο τελικό διαγώνισμα. Θα δοθούν 3 σειρές εργαστηριακών ασκήσεων οι οποίες είναι υποχρεωτικές. Στις εργαστηριακές ασκήσεις θα γίνεται μελέτη των υπολογιστικών μεθόδων Γραμμικού και Μη Προγραμματισμού και των εφαρμογών τους με τη χρήση υπολογιστικών προγραμμάτων (π.χ MATLAB, C++, Fortran90). Πιο συγκεκριμένα ο βαθμός θα προκύπτει ως εξής: Σειρές ασκήσεων (20%) +  Τελική Εξέταση (80%). Η ενδιάμεση πρόοδος θα μετράει μόνο θετικά 20%. Επίσης θα υπάρχει η δυνατότητα για project. Η βάση είναι 50%.

 

Ηλεκτρονική Λίστα Αλληλογραφίας

Ενημέρωση σχετικά με το μάθημα (για τις σειρές ασκήσεων, ημερομηνίες εξετάσεων, κ.τ.λ.) γίνεται από την ηλεκτρονική λίστα αλληλογραφίας. Για να γραφτείτε στην ηλεκτρονική λίστα αλληλογραφίας του μαθήματος στείλτε email με κενό θέμα και περιεχόμενο subscribe em231-list στην διεύθυνση majordomo@tem.uoc.gr. Στην συνέχεια θα σας σταλεί ένα email στο οποίο θα χρειαστεί να απαντήσετε χρησιμοποιώντας κάποιο συγκεκριμένο μήνυμα για επιβεβαίωση. Για να εγγραφείτε στην λίστα πρέπει να χρησιμοποιήσετε την ηλεκτρονική διεύθυνση που σας παρέχεται από το Πανεπιστήμιο Κρήτης (για παράδειγμα username@tem.uoc.gr ή username@math.uoc.gr).

 

Σημειώσεις του Μαθήματος (English)

· Πρόγραμμα Διδασκαλίας — Ημερολόγιο του Μαθήματος

 

Σειρές Ασκήσεων

· Σειρά Ασκήσεων 1

· Σειρά Ασκήσεων 2

· Σειρά Ασκήσεων 3

 

Παραδείγματα Προγραμμάτων (MATLAB)

· MATLAB Introduction 1

· MATLAB Introduction Taylor

· Προγράμματα από το βιβλίο «Linear Programming with MATLAB» των .C. Ferris, O.L. Mangasarian, S.J. Wright, SΙΑΜ, 2007.

 

A more detailed introduction in MATLAB

· MATLAB Primer (by K. Sigmon)

· An Introduction to MATLAB (by D. Griffiths, Univ. of Dundee)

· Numerical Computing with MATLAB (by C. Moler,  Society for Industrial and Applied Mathematics, 2004)

 

Δημοσιεύσεις — Άρθρα

· 20th Century Top algorithms (SIAM News 2000)

 

Σύνδεσμοι στο Διαδίκτυο

· Linear Programming and Duality (MIT: Open Courseware)

· Transportation Theory

 

Ενδεικτικά Θέματα για Project

1)  Το πρόβλημα της ελάχιστης διαδρομής

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

·     Shortest Path Problem

·    An introduction to convexity, polyhedral theory and combinatorial optimization. (Κεφάλαιο 4.2)

2)  Το πρόβλημα του περιπλανώμενου πωλητή

Παρουσίαση του προβλήματος περιπλανώμενου πωλητή, και αναλυτική παρουσίασή του σε μορφή Γ.Π.. Δείτε επίσης:

·    A Linear Programming formulation of the Traveling Salesman Problem.(by M. Diaby)

3)  Το πρόβλημα του ελάχιστου δέντρου που καλύπτει ένα γράφο