ΠΛΕ-047 : Γραμμικός Προγραμματισμός Ακαδημαϊκό Έτος 2011--2012

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

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

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

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

Περιγραφή

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

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

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

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

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

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

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

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

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

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

όπου:

• ΒΤΕ      =    Βαθμός Τελικής Εξέτασης
• ΜΟΑ    =    Μέσος Όρος Ασκήσεων.

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

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

• [22-2-2012]: Η βαθμολογία της εξέτασης Φεβρουαρίου 2012 είναι αναρτημένη στον πίνακα ανακοινώσεων του 3ου ορόφου, ενώ μπορείτε να τη δείτε κι εδώ. Δείτε επίσης τις ενδεικτικές λύσεις της εξέτασης εδώ.
   

• [11-1-2012]: Οι διαλέξεις 25-16/1/2012 μεταφέρονται (λόγω απουσίας του διδάσκοντα) την Παρασκευή 13/1/2012 και την Παρασκευή 20/1/2012 αντίστοιχα (ώρα διαλέξεων: 16:00--18:00).
   

• [23-11-2011]: ΕΠΕΙΓΟΝ Στο εξής οι διαλέξεις της Τετάρτης μετατίθενται (από 18:00--20:00) κατά δυο ώρες και θα γίνονται 16:00--18:00. Οι διαλέξεις της Πέμπτης θα γίνονται 17:00--19:00.
   

• [17-11-2011]: Δείτε την 2η εργαστηριακή άσκηση (τελευταία διαφάνεια διαλέξεων 3ης εβδομάδας). Ημερομηνία παράδοσης: Πέμπτη 8 Δεκεμβρίου 2011 (αμέσως μετά το μάθημα, στο γραφείο του διδάσκοντα). Θα πρέπει να έχει αποσταλεί στον διδάσκοντα με ηλεκτρονικό ταχυδρομείο ο κώδικας κάθε φοιτητή, πριν την εξέταση.
   

• [17-11-2011]:  Η παράδοση της 1ης εργαστηριακής άσκησης (η εκφώνησή της βρίσκεται στην τελευταία διαφάνεια των διαλέξεων 2ης εβδομάδας) μετατίθεται για την Τετάρτη 23 Νοεμβρίου 2011, αμέσως μετά το μάθημα. Θα πρέπει να έχει αποσταλεί στον διδάσκοντα με ηλεκτρονικό ταχυδρομείο ο κώδικας κάθε φοιτητή, πριν την εξέταση.
   

• [16-11-2011]: Στο Χρήσιμο Υλικό υπάρχει ένα αντίγραφο των πρώτων κεφαλαίων του βιβλίου, για όσους δεν το έχουν ήδη προμηθευτεί.
   

• [4-11-2011]: Δείτε την 1η εργαστηριακή άσκηση (τελευταία διαφάνεια διαλέξεων 2ης εβδομάδας). Ημερομηνία παράδοσης: Τετάρτη 16 Νοεμβρίου 2011 (μετά το μάθημα, στο γραφείο του διδάσκοντα).
   

• [4-11-2011]: Οι κωδικοί πρόσβασης που δόθηκαν στη διάλεξη της Τετάρτης 2-11-2011 για το Συνοδευτικό Υλικό του μαθήματος, λειτουργούν πλέον κανονικά.

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

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

Διδακτική  Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Συνοδευτικό Υλικό
			Διαφάνειες Διαλέξεων password protected	Άλλο Υλικό password protected
1η	19-20 / 10 / 2011	Οι διαλέξεις αναβάλλονται λόγω κινητοποιήσεων.		1. Αγγλικό βιβλίο FMW2007:     -- Αντίγραφο του κώδικα που παρέχεται στο βιβλίο.   2. Σύντομος Οδηγός Χρήσης του Matlab.     -- Αρχείο με κώδικα που παρέχεται στο βιβλίο.   3. Διδακτικές Σημειώσεις Μαθήματος.   4. Πρώτα κεφάλαια από ελληνικό βιβλίο (ΠΡΟΣΟΧΗ: 3η έκδοση).
2ηη	26-27 / 10 / 2011	Εισαγωγή -- Μοντέλοποίηση Προβλημάτων ως Γραμμικά Προγράμματα -- Βασικές Έννοιες Άλγεβρας	Διαφάνειες 1ης Εβδομάδας
3η	2-3 / 11 / 2011	Μορφές Γραμμικών Προγραμμάτων και ισοδυναμία τους Ανταλλαγές Jordan (pivots)	Διαφάνειες 2ης Εβδομάδας
4η	9-10 / 11 / 2011	Οι διαλέξεις αναβάλλονται λόγω απουσίας του διδάσκοντα
5η	16 / 11 / 2011	Επίλυση Γραμμικών Συστημάτων με Χρήση Pivots	Διαφάνειες 3ης Εβδομάδας
6η	23-24 / 11 / 2011	Γεωμετρία Χώρου Λύσεων Γραμμικών Προγραμμάτων	Διαφάνειες 4ης Εβδομάδας
7η	30 / 11-1 / 12 / 2011	Ο αλγόριθμος SIMPLEX: -- Αναπαράσταση -- Pivots	Διαφάνειες 5ης+6ης+7ης Εβδομάδας
8η	7-8 / 12 / 2011	Ο αλγόριθμος SIMPLEX: -- Επιλογή Στοιχείου Εναλλαγής -- Αποφυγή Κύκλων
9η	14-15 / 12 / 2011	Ο αλγόριθμος SIMPLEX: -- Σημείο Εκκίνησης -- Ζητήματα Υλοποίησης (ακέραιο Pivoting, Λεξικογραφικό MIN RATIO)
10η	21-22 / 12 / 2011	Θεωρία Δυϊκότητας -- Ισχυρή & Ασθενής Δυϊκότητα	Διαφάνειες 8ης+9ης Εβδομάδας
11η	11-12 / 1 / 2012	Θεωρία Δυϊκότητας -- Συμπληρωματική Χαλαρότητα -- Λήμμα του Farkas
12η	18-19 / 1 / 2012
13η	25-26 / 1 / 2012
--		ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ -- Ώρα: -- Αίθουσα: Ι1 (στο ισόγειο του κτιρίου) -- Κλειστές Σημειώσεις -- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τρία φύλλα Α4) με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

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

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

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

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

1. Διδακτικές Σημειώσεις + Εβδομαδιαίες Διαφάνειες Διαλέξεων (βλ. Ημερολόγιο του μαθήματος).
    
2. [Παπαρρίζος2009] Παπαρρίζος Κωνσταντίνος. Γραμμικός Προγραμματισμός: Μια Προσέγγιση με Matlab.
   Εκδόσεις ΖΥΓΟΣ (2009). Κωδικός ΕΥΔΟΞΟΥ: 1775.
    
3. [Μπότσαρης2002] Μπότσαρης Χαράλαμπος. Επιχειρησιακή έρευνα. Τόμος Ι. Γραμμικός Προγραμματισμός και Θεωρία Παιγνίων.
   Έκδοση 4η, ΕΛΛΗΝΙΚΑ ΓΡΑΜΜΑΤΑ Α.Ε. (2002). Κωδικός ΕΥΔΟΞΟΥ: 9980.
   Δείτε εδώ ένα αντίγραφο των πρώτων κεφαλαίων του βιβλίου (ΠΡΟΣΟΧΗ: 3η έκδοση).

Τα ακόλουθα βιβλία είναι επίσης πολύ χρήσιμες αναφορές για το μάθημα::

4. [FMW2007] M. C. Ferris, O.L. Mangasarian, S.J. Wright. Linear Programming with MATLAB, MPS-SIAM Series on Optimization.
    
5. [Vanderbei2007] R. Vanderbei. Linear Programming: Foundations and Extensions (online edition, 2007).
    
6. [DS2011] T.A. Davis, K. Sigmon. MATLAB Primer (8th edition), Chapman & Hall /CRC (2011).
    
7. [Karloff1991] ] H. Karloff. Linear Programming, Birkhäuser 1991 (αντίγραφο στο γραφείο του διδάσκοντα).
    
8. [PS1982] C. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Prentice Hall, 1982 (βιβλιοθήκη).
    
9. [Schrijver1986] Al. Schrijver. Theory of linear and integer programming. Chichester: Wiley, c1986 (βιβλιοθήκη).
    
10. [Chvatal1983] V. Chvatal. Linear Programming. New York: W. H. Freeman and Company, c1983 (βιβλιοθήκη).
     

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

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

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