MYE009/ΠΛΕ047 : Γραμμικός Προγραμματισμός Ακαδημαϊκό Έτος 2016 -- 2017

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Γενικές Πληροφορίες

Διδάσκων:	Σπύρος Κοντογιάννης
Email -- URL -- Voice:	--  http://www.cse.uoi.gr/~kontog/  --  (26510) 08812
URL Μαθήματος:	www.cse.uoi.gr/~kontog/courses/LinProg/
Ώρες Διαλέξεων:	Κάθε Τετάρτη 17:00--20:00
Χώρος Διαλέξεων:	Αίθουσα Ι2 (στο Ισόγειο του Κτιρίου Πληροφορικής)
Ώρες Επικοινωνίας:

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Περιγραφή

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

• Την (επακριβή) επίλυση προβλημάτων που μοντελοποιούνται ως γραμμικά προγράμματα,
• Τον υπολογισμό προσεγγιστικών λύσεων για δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης,
• Την απόδειξη ιδιοτήτων παραγόμενων λύσεων για δύσκολα συνδυαστικά προβλήματα.

Ο Γραμμικός Προγραμματισμός είναι ένα από τα σημαντικότερα εργαλεία στη διάθεση της Υπολογιστικής Επιστήμης, το οποίο όμως έχει ευρύτατες εφαρμογές σε όλο σχεδόν το φάσμα των θετικών και οικονομικών επιστημών (πχ, Διοίκηση Επιχειρήσεων, Οικονομικές Επιστήμες, Εφαρμοσμένα Μαθηματικά, κ.λπ.). Θα ασχοληθούμε με ορισμένα κλασικά ζητήματα του γραμμικού προγραμματισμού, δίνοντας έμφαση και σε μερικά τυπικά παραδείγματα εφαρμογής του (πχ, σε προβλήματα δικτυακών ροών και προβλήματα ισορροπιών σε παίγνια μηδενικού αθροίσματος) αλλά και αξιοποίησής του τόσο ως αλγοριθμικό εργαλείο επίλυσης, όσο και ως τεχνική για την απόδειξη της απόδοσης αλγορίθμων επίλυσης συνδυαστικών προβλημάτων.

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

Βασικές Έννοιες

• Πινάκες, γραμμικοί χώροι -- υποχώροι, γραμμική ανεξαρτησία και βάση χώρου, χώρος λύσεων γραμμικού προγράμματος και γεωμετρία του, κορυφές (ακραία σημεία) και βασικές (εφικτές) λύσεις.
• Ο αλγόριθμος Simplex: Εναλλαγή στηλών, εκφυλισμένες λύσεις, αποφυγή κύκλων, αρχικοποίηση, χρήση ψευδομεταβλητών, πολυπλοκότητα.
• Θεωρία δυϊκότητας: Δυϊκό ενός γραμμικού προγράμματος, συμπληρωματική χαλαρότητα, το λήμμα του Farkas.
• Ανάλυση ευαισθησίας γραμμικών προγραμμάτων.
• Αλγόριθμοι Εσωτερικών Σημείων.
• Επίλυση παιγνίων μηδενικού αθροίσματος μεταξύ δυο παικτών με χρήση γραμμικού προγραμματισμού.
• Μελέτη προβλημάτων προσδιορισμού βέλτιστων ροών σε δίκτυα (ροές μέγιστου όγκου / ελαχίστου κόστους, εύρεση ελαχίστων διαδρομών κ.λπ.).

Αξιολόγηση Μαθήματος

Το μάθημα περιλαμβάνει:

• Εβδομαδιαίες ή δεκαπενθήμερες εργαστηριακές ασκήσεις εξάσκησης, με χρήση του περιβάλλοντος μαθηματικών υπολογισμών Matlab. Η συμμετοχή στις εργαστηριακές ασκήσεις είναι προαιρετική.

• Τελική (γραπτή) εξέταση μαθήματος.

όπου:

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

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

• 15/06/2017: Η βαθμολογία της εξέτασης Ιουνίου 2017 είναι ήδη αναρτημένη στον πίνακα ανακοινώσεων του τρίτου ορόφου, ενώ διατίθεται ηλεκτρονικά κι εδώ.
   

• 11/05/2017: Η διάλεξη της ερχόμενης Τετάρτης, 17/5/2017 θα γίνει κανονικά (οι φοιτητικές εκλογές μεταφέρθηκαν για την Τετάρτη 24/5).
   

• 11/05/2017: Η τρίτη εργαστηριακή άσκηση του μαθήματος ανακοινώθηκε ήδη (βλ. προτελευταία διαφάνεια 9ης διάλεξης) κι έχει προθεσμία μέχρι την Πέμπτη, 8 Ιουνίου 2017.
   

• 14/04/2017: Η δεύτερη εργαστηριακή άσκηση του μαθήματος ανακοινώθηκε ήδη (βλ. προτελευταία διαφάνεια 6ης διάλεξης) κι έχει προθεσμία μέχρι την Πέμπτη, 4 Μαΐου 2017.
   

• 08/03/2017: Η πρώτη εργαστηριακή άσκηση του μαθήματος ανακοινώθηκε ήδη (βλ. προτελευταία διαφάνεια 3ης διάλεξης) κι έχει προθεσμία μέχρι την Πέμπτη 24/03/2017.
   

• 15/02/2017: Οι διαλέξεις του μαθήματος θα γίνονται στην αίθουσα Ι2, και ξεκινούν σήμερα, Τετάρτη 15/2/2017.
   

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Ημερολόγιο Μαθήματος

Διδακτική  Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Συνοδευτικό Υλικό
			Διαφάνειες Διαλέξεων password protected	Άλλο Υλικό password protected
1η	15/ 02 / 2017	Εισαγωγή -- Βασικές Έννοιες -- Ιστορική Αναδρομή Μοντέλοποίηση Προβλημάτων ως Γραμμικά Προγράμματα	Διαφάνειες 1ης εβδομάδας [ανάγνωση]	1. Αγγλικό βιβλίο FMW2007:     -- Αντίγραφο του κώδικα που παρέχεται στο βιβλίο.   2. Σύντομος Οδηγός Χρήσης του Matlab.   3. Διδακτικές Σημειώσεις Μαθήματος.   5. Κεφάλαια 14-15 (για δικτυακές ροές και εφαρμογές τους) από το βιβλίο Vanderbei2014.
2η	22 / 02 / 2017	Μοντέλοποίηση Προβλημάτων ως Γραμμικά Προγράμματα (συνέχεια) Μορφές Γραμμικών Προγραμμάτων και ισοδυναμία τους	Διαφάνειες 2ης εβδομάδας [ανάγνωση]
3η	01 / 03 / 2017	Ανταλλαγές Jordan (pivots) Επίλυση Ομογενών Γραμμικών Συστημάτων  Εξισώσεων με Χρήση Pivots	Διαφάνειες 3ης εβδομάδα [ανάγνωση]
4η	08 / 03 / 2017	Επίλυση Μη Ομογενών Γραμμικών Συστημάτων με Χρήση Pivots Γεωμετρία Χώρου Λύσεων Γραμμικών Προγραμμάτων	Διαφάνειες 4ης εβδομάδας [ανάγνωση]
5η	15 / 03 / 2017	Ο αλγόριθμος SIMPLEX: -- Αναπαράσταση -- Pivots -- Επιλογή Στοιχείου Εναλλαγής -- Αποφυγή Κύκλων	Διαφάνειες 5ης εβδομάδας [ανάγνωση]
6η	22 / 03 / 2017	Ο αλγόριθμος SIMPLEX: -- Σημείο Εκκίνησης -- Ζητήματα Υλοποίησης (ακέραιο Pivoting, Λεξικογραφικό MIN RATIO)	Διαφάνειες 6ης-7ης εβδομάδας  [1o σετ -- 2ο σετ]
7η	29 / 03 / 2017	Θεωρία Δυϊκότητας -- Ισχυρή & Ασθενής Δυϊκότητα -- Συμπληρωματική Χαλαρότητα
8η	05 / 04 / 2017	Θεωρία Δυϊκότητας -- Λήμμα του Farkas -- Δυϊκός Simplex -- Μέθοδος του Μεγάλου-Μ	Διαφάνειες 8ης εβδομάδας [ανάγνωση]
9η	26 / 04 / 2017	Εναλλακτικές Μέθοδοι Επίλυσης ΓΠ -- Μέθοδος Εσωτερικών Σημείων -- Επίλυση Γραμμικών Προγραμμάτων σε Χώρους Μικρής Διάστασης	Διαφάνειες 9ης+10ης εβδομάδας [ανάγνωση]
10η	03 / 05 / 2017	Αξιοποίηση ΓΠ για επίλυση μη γραμμικών προβλημάτων βελτιστοποίησης -- Ανίχνευση Κενότητας Πολυέδρων -- Ελαχιστοποίηση Νορμών -- Κλασματικά Γραμμικά Προγράμματα -- Ακέραιος Γραμμικός Προγραμματισμός -- Μέθοδος Branch & Bound
11η	10 / 05 / 2017	ΕΦΑΡΜΟΓΗ: Προβλήματα Δικτυακών Ροών -- Total Unimodularity -- Ταιριάσματα σε Γραφήματα -- Ελάχιστες Διαδρομές σε Γραφήματα -- Ροές Ελάχιστου Κόστους -- Μέγιστες Ροές -- Θεώρημα Μεγίστων Ροών / Συνόλων Κοπής Ελάχιστους Βάρους	Διαφάνειες 10ης-11ης  εβδομάδας [ανάγνωση]
12η	17 / 05 / 2017	ΕΦΑΡΜΟΓΗ: Αξιοποίηση ΓΠ στα Στρατηγικά Παιχνίδια Διπίνακα -- Υπολογισμός βέλτιστων αποκρίσεων -- ΜΑΧΜΙΝ / ΜΙΝΜΑΧ στρατηγικές -- Υπολογισμός Ισορροπίας Nash σε Παίγνια Διπίνακα Μηδενικού Αθροίσματος	Διαφάνειες 12ης εβδομάδας [ανάγνωση]
13η	24 / 05 / 2017	ΔΕ ΘΑ ΓΙΝΕΙ ΜΑΘΗΜΑ ΛΟΓΩ ΠΡΟΓΡΑΜΜΑΤΙΣΜΕΝΩΝ ΦΟΙΤΗΤΙΚΩΝ ΕΚΛΟΓΩΝ
--	--	ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ -- Ώρα: -- Αίθουσα: Ι2 (στο ισόγειο του κτιρίου) -- Κλειστές Σημειώσεις -- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τρία φύλλα Α4) με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Χρήσιμο Υλικό

Βιβλιογραφία Μαθήματος

Τα βασικά εγχειρίδια του μαθήματος είναι:

Α. Διδακτικές Σημειώσεις + Εβδομαδιαίες Διαφάνειες Διαλέξεων (βλ. Ημερολόγιο του μαθήματος).

Β. Διαθέσιμα συγγράμματα από ΕΥΔΟΞΟ:

Γ. Λοιπή (ξενόγλωσση) Βιβλιαγραφία:

• [FMW2007] M. C. Ferris, O.L. Mangasarian, S.J. Wright. Linear Programming with MATLAB, MPS-SIAM Series on Optimization.
• [Vanderbei2014] R. Vanderbei. Linear Programming: Foundations and Extensions, Springer 4th edition (2014), ISBN 978-1-4614-7630-6.
• [DS2011] T.A. Davis, K. Sigmon. MATLAB Primer (8th edition), Chapman & Hall /CRC (2011).
• [Karloff1991] ] H. Karloff. Linear Programming, Birkhäuser 1991.
• [PS1982] C. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Prentice Hall, 1982.
• [Schrijver1986] Al. Schrijver. Theory of linear and integer programming. Chichester: Wiley, c1986.
• [Chvatal1983] V. Chvatal. Linear Programming. New York: W. H. Freeman and Company, c1983.
   

Παλιά Θέματα Εξετάσεων: Φεβρουάριος 2010 | Φεβρουάριος 2011 | Φεβρουάριος 2012 | Φεβρουάριος 2013 |  Ιανουάριος 2014 .

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Δημιουργία και συντήρηση σελίδας μαθήματος: Σπύρος Κοντογιάννης. Ημερομηνία τελευταίας αλλαγής: 15/06/2017.