Εισαγωγή στην επιχειρησιακή έρευνα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Τμήμα Μαθηματικών
Έτος: 2013
Διδάσκων: Απόστολος Μπουρνέτας
Περιγραφή Μαθήματος
Το μάθημα αποτελεί μια εισαγωγή στις βασικές έννοιες του μαθηματικού προγραμματισμού σε ντετερμινιστικό περιβάλλον και ειδικότερα στο γραμμικό και δυναμικό προγραμματισμό. Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής ή η φοιτήτρια θα, 1) μπορεί να αναπτύσσει μοντέλα γραμμικού προγραμματισμού για μια μεγάλη κατηγορία προβλημάτων λήψης αποφάσεων, 2) έχει κατανοήσει τις βασικές γεωμετρικές ιδιότητες των προβλημάτων γραμμικού προγραμματισμού (π.γ.π.) και την αντιστοιχία τους με τις αλγεβρικές, 3) γνωρίζει τη μέθοδο Simplex για την επίλυση π.γ.π., 4) έχει εξοικειωθεί με τις βασικές έννοιες της δυϊκότητας στο γραμμικό προγραμματισμό, 5) έχει κατανοήσει την εφαρμογή του γραμμικού προγραμματισμού σε προβλήματα ροής δικτύων και ειδικότερα στο πρόβλημα μεταφοράς και τον εξειδικευμένο αλγόριθμο επίλυσής του, 6) έχει εξοικειωθεί με τις βασικές έννοιες του ντετερμινιστικού δυναμικού προγραμματισμού
Video-Διαλέξεις
Διάλεξη 01 (2013-02-13)
Επιχειρησιακή Έρευνα: Αντικείμενο, Σκοπός, Ιστορία, Εφαρμογές. Βασικές Αρχές Μαθηματικής Μοντελοποίησης. Το μοντέλο του μαθηματικού προγραμματισμού. Μεταβλητές Απόφασης. Αντικειμενική Συνάρτηση. Περιορισμοί. Παραδείγματα
Διάλεξη 02 (2013-02-18)
Το υπόδειγμα του Γραμμικού Προγραμματισμού. Γενική Μορφή - Πινακομορφή. Παραδείγματα
Διάλεξη 03 (2013-02-25)
Γεωμετρική Επίλυση Προβλημάτων Γραμμικού Προγραμματισμού. Σχεδιασμός Εφικτής Περιοχής. Γραμμές Σταθερού Κέρδους. Βέλτιστες λύσεις σε κορυφές
Διάλεξη 04 (2013-02-27)
Γεωμετρική Επίλυση Προβλημάτων Γραμμικού Προγραμματισμού. Παραδείγματα. Ειδικές Περιπτώσεις. Ανέφικτο πρόβλημα. Μη φραγμένο πρόβλημα. Πολλαπλές βέλτιστες λύσεις. Πλεοναστικοί περιορισμοί
Διάλεξη 05 (2013-03-04)
Κανονική Μορφή Προβλήματος Γραμμικού Προγραμματισμού. Κανόνες Μετασχηματισμού σε Κανονική Μορφή - Περιθώριες Μεταβλητές. Παραδείγματα
Διάλεξη 06 (2013-03-06)
Ικανές συνθήκες για ύπαρξη λύσης ΠΓΠ. Γεωμετρικές Ιδιότητες Λύσεων ΠΓΠ. Κυρτοί Συνδυασμοί. Κυρτά Σύνολα
Διάλεξη 07 (2013-03-11)
Ιδιότητες Λύσεων ΠΓΠ. Ακρότατα Κυρτού Συνόλου. Κυρτά Πολύεδρα - Κορυφές. Υπερεπίπεδα - Ημίχωροι. Θεώρημα : Βέλτιστη λύση φραγμένου πγπ σε κορυφές της εφικτής περιοχής
Διάλεξη 08 (2013-03-13)
Αλγεβρικός Προσδιορισμός Κορυφών Εφικτής Περιοχής. Βασικές Λύσεις. Βασικές Εφικτές Λύσεις. Γεωμετρική Ερμηνεία
Διάλεξη 09 (2013-03-20)
Αντιστοιχία Βασικών Εφικτών Λύσεων και Κορυφών της Εφικτής Περιοχής. Αποδείξεις. Παραδείγματα
Διάλεξη 10 (2013-03-27)
Εισαγωγή στη μέθοδο Simplex. Κριτήριο Βελτιστότητας. Βελτίωση Βασικής Εφικτής Λύσης
Διάλεξη 11 (2013-04-01)
Μέθοδος Simplex. Πινακική Μορφή. Υπολογισμοί με Ταμπλό
Διάλεξη 12 (2013-04-03)
Μέθοδος Simplex. Αρχική Βασική Εφικτή Λύση. Μέθοδος Τεχνητών Μεταβλητών
Διάλεξη 13 (2013-04-08)
Μέθοδος Simplex. Πολλαπλές Βέλτιστες Λύσεις. Ημικανονική Μορφή. Ορισμός Δυϊκού Προβλήματος
Διάλεξη 14 (2013-04-10)
Ασθενές και Ισχυρό Θεώρημα Δυϊκότητας
Διάλεξη 15 (2013-04-15)
Θεώρημα Συμπληρωματικότητας. Αντιστοιχία Λύσεων Πρωτεύοντος – Δυϊκού
Διάλεξη 16 (2013-04-22)
Πρόβλημα Μεταφοράς. Ορισμός. Ισορροπημένα και Μη Ισορροπημένα Προβλήματα. Υπόδειγμα Γραμμικού Προγραμματισμού. Ύπαρξη Λύσης
Διάλεξη 17 (2013-04-24)
Πρόβλημα Μεταφοράς. Εύρεση Αρχικής Βασικής Εφικτής Λύσης. Αλγόριθμος Δυναμικών
Διάλεξη 18 (2013-05-13)
Πρόβλημα Μεταφοράς. Αλγόριθμος Δυναμικών. Πολλαπλές Βέλτιστες Λύσεις
Διάλεξη 19 (2013-05-15)
Εισαγωγή στο Δυναμικό Προγραμματισμό. Πρόβλημα Ελάχιστης Διαδρομής
Διάλεξη 20 (2013-05-20)
Δυναμικός Προγραμματισμός. Πρόβλημα Πεπερασμένου Ορίζοντα. Μοντελοποίηση. Εξισώσεις Βελτιστότητας. Αλγόριθμος Αναδρομής προς τα πίσω
Διάλεξη 21 (2013-05-21)
Επαναληπτικές Ασκήσεις. Γραμμικός Προγραμματισμός
Διάλεξη 22 (2013-05-22)
Εφαρμογές Δυναμικού Προγραμματισμού. Αντικατάσταση και Συντήρηση Μηχανήματος
Διάλεξη 23 (2013-05-27)
Εφαρμογές Δυναμικού Προγραμματισμού. Διαχείριση Αποθεμάτων
Διάλεξη 24 (2013-05-28)
Επαναληπτικές Ασκήσεις. Γραμμικός Προγραμματισμός. Αλγόριθμος Μεταφοράς
Διάλεξη 25 (2013-05-29)
Εφαρμογές Δυναμικού Προγραμματισμού. Κατανομή Πόρων