Τμημα Πληροφορικης Πανεπιστημιου Ιωαννινων

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 (στο Ισόγειο του Κτιρίου Πληροφορικής)
Ώρες Επικοινωνίας:

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

Περιγραφή

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

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

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

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

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

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

ΤΕΛΙΚΟΣ ΒΑΘΜΟΣ = ΜΑΧ{ ΒΤΕ , 0.05 Χ ΣΥΜ + 0.3 Χ ΜΟΑ + 0.65 Χ ΒΤΕ }

όπου:

ΒΤΕ =   Βαθμός Τελικής Εξέτασης
ΜΟΑ =   Μέσος Όρος Ασκήσεων
ΣΥΜ =   Ενεργή Συμμετοχή στις Διαλέξεις

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

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

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

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

Διδακτική  Εβδομάδα Ημερομηνίες Διδασκαλίας Ύλη Εβδομάδας Συνοδευτικό Υλικό
Περιοχη Περιορισμενης Προσβασης
Διαφάνειες Διαλέξεων
password protected
Άλλο Υλικό
password protected
15/ 02 / 2017 Εισαγωγή
-- Βασικές Έννοιες
-- Ιστορική Αναδρομή
Μοντέλοποίηση Προβλημάτων ως Γραμμικά Προγράμματα
Διαφάνειες 1ης εβδομάδας
[ανάγνωση]

1. Αγγλικό βιβλίο FMW2007:
    -- Αντίγραφο του κώδικα που παρέχεται στο βιβλίο.

 

2. Σύντομος Οδηγός Χρήσης του Matlab.

 

3. Διδακτικές Σημειώσεις Μαθήματος.

 

5. Κεφάλαια 14-15 (για δικτυακές ροές και εφαρμογές τους) από το βιβλίο Vanderbei2014.

22 / 02 / 2017 Μοντέλοποίηση Προβλημάτων ως Γραμμικά Προγράμματα (συνέχεια)
Μορφές Γραμμικών Προγραμμάτων και ισοδυναμία τους
Διαφάνειες 2ης εβδομάδας
[ανάγνωση]
01 / 03 / 2017 Ανταλλαγές Jordan (pivots)
Επίλυση Ομογενών Γραμμικών Συστημάτων  Εξισώσεων με Χρήση Pivots
Διαφάνειες 3ης εβδομάδα
[ανάγνωση] 
08 / 03 / 2017 Επίλυση Μη Ομογενών Γραμμικών Συστημάτων με Χρήση Pivots
Γεωμετρία Χώρου Λύσεων Γραμμικών Προγραμμάτων
Διαφάνειες 4ης εβδομάδας
[ανάγνωση] 
15 / 03 / 2017 Ο αλγόριθμος SIMPLEX:
--
Αναπαράσταση
-- Pivots
-- Επιλογή Στοιχείου Εναλλαγής
-- Αποφυγή Κύκλων
Διαφάνειες 5ης εβδομάδας
[ανάγνωση]
22 / 03 / 2017 Ο αλγόριθμος SIMPLEX:
--
Σημείο Εκκίνησης
-- Ζητήματα Υλοποίησης (ακέραιο Pivoting, Λεξικογραφικό
MIN RATIO)
Διαφάνειες 6ης εβδομάδας

 [1o σετ -- 2ο σετ] 

29 / 03 / 2017 Θεωρία Δυϊκότητας
-- Ισχυρή & Ασθενής Δυϊκότητα
-- Συμπληρωματική Χαλαρότητα
Διαφάνειες 7ης-9ης εβδομάδας
[ανάγνωση] 
05 / 04 / 2017 Θεωρία Δυϊκότητας
-- Λήμμα του Farkas
--
Δυϊκός Simplex
--
Μέθοδος του Μεγάλου-Μ
26 / 04 / 2017 Εναλλακτικές Μέθοδοι Επίλυσης ΓΠ
-- Μέθοδος Εσωτερικών Σημείων
-- Επίλυση Γραμμικών Προγραμμάτων σε Χώρους Μικρής Διάστασης
10η 03 / 05 / 2017 Αξιοποίηση ΓΠ για επίλυση μη γραμμικών προβλημάτων βελτιστοποίησης
-- Ανίχνευση Κενότητας Πολυέδρων
-- Ελαχιστοποίηση Νορμών
-- Κλασματικά Γραμμικά Προγράμματα
Διαφάνειες 10ης εβδομάδας
[ανάγνωση] 
11η 10 / 05 / 2017 Αξιοποίηση ΓΠ για επίλυση μη γραμμικών προβλημάτων βελτιστοποίησης
-- Ακέραιος Γραμμικός Προγραμματισμός
-- Μέθοδος Branch & Bound
 
12η 17 / 05 / 2017 ΕΦΑΡΜΟΓΗ: Προβλήματα Δικτυακών Ροών
-- Total Unimodularity
-- Ταιριάσματα σε Γραφήματα
-- Ελάχιστες Διαδρομές σε Γραφήματα
-- Ροές Ελάχιστου Κόστους
-- Μέγιστες Ροές
-- Θεώρημα Μεγίστων Ροών / Συνόλων Κοπής Ελάχιστους Βάρους
Διαφάνειες 12ης εβδομάδας
[ανάγνωση] 
13η 24 / 05 / 2017 ΕΦΑΡΜΟΓΗ: Αξιοποίηση ΓΠ στα Στρατηγικά Παιχνίδια Διπίνακα
-- Υπολογισμός βέλτιστων αποκρίσεων
-- ΜΑΧΜΙΝ / ΜΙΝΜΑΧ στρατηγικές
-- Υπολογισμός Ισορροπίας Nash σε Παίγνια Διπίνακα Μηδενικού Αθροίσματος
Διαφάνειες 13ης εβδομάδας
[ανάγνωση]
-- --

ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ
-- Ώρα:

-- Αίθουσα: Ι2 (στο ισόγειο του κτιρίου)
-- Κλειστές Σημειώσεις
-- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τρία φύλλα Α4) με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

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

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

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

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

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

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

Κωδικός Ευδόξου Τίτλος Συγγραφέας Έκδοση ISBN
   Γραμμικός Προγραμματισμός Σίσκος Γιάννης έκδοση 5η/2000 960-7981-00-6
  Εισαγωγή στην Επιχειρησιακή Έρευνα

Κολέτσος Ιωάννης, Στογιάννης Δημήτρης

έκδοση 2η / 2015  
  Γραμμικός Προγραμματισμός: Αριστοποίηση σε δίκτυα Λουκάκης Μανώλης έκδοση 3η / 2010 978-960-87438-8-5
  Γραμμικός Προγραμματισμός Δεσπότης Δημήτρης έκδοση 1η / 2011 978-960-93-2477-9

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

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

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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