Ακέραιος Προγραμματισμός και Συνδιαστική Βελτιστοποίηση

Το μάθημα ακέραιος προγραμματισμός και συνδυαστική βελτιστοποίηση είναι μάθημα του 6ου εξαμήνου το τμήματος μηχανολόγων μηχανικών του Πανεπιστημίου Θεσσαλίας. Κατά την διάρκεια του εξαμήνου οι φοιτητές διδάσκονται όλες τις βασικές γνώσεις γραμμικού ακέραιου και μεικτού προγραμματισμού. Οι φοιτητές διδάσκονται ευρετικές και ακριβείς μεθόδους επίλυσης αυτών των προβλημάτων με αναλυτικά παραδείγματα μικρού και μεγάλου μεγέθους. Τέλος μέσα από βασικά παραδείγματα της βιβλιογραφίας άλλα και παραδείγματα πραγματικού μεγέθους η διδασκαλία επικεντρώνεται σε τεχνικές μοντελοποίησης με στόχο την απόκτηση εμπειρίας από τους φοιτητές στην όσο το δυνατόν πιο αποδοτικής μοντελοποίησης προβλημάτων μαθηματικού προγραμματισμού.

Στόχοι Μαθήματος

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

Προαπαιτούμενες Γνώσεις

Οι φοιτητές χρειάζονται βασικές γνώσεις επιχειρησιακής έρευνας και πιο συγκεκριμένα γνώσεις γραμμικού προγραμματισμού και άλγεβρας.

Περιεχόμενα

Μορφοποίηση και εφαρμογές προβλημάτων ακέραιου και μεικτού ακέραιου προγραμματισμού. Ευφυείς χρήσεις δυαδικών μεταβλητών στη μορφοποίηση μοντέλων. Μέθοδος διακλάδωσης και φραγμού (branch and bound). Μέθοδος επίπεδων τομών (cutting planes). Σχεδιασμός και ανάλυση αλγορίθμων συνδυαστικής βελτιστοποίησης. Πολυπλοκότητα αλγορίθμων. Εφαρμογές σε δίκτυα και γραφήματα. Επίλυση προβλημάτων με τη χρήση τεχνικών τοπικής βελτιστοποίησης, δυναμικού προγραμματισμού, μυωπικών αλγορίθμων, προσεγγιστικών και ευρετικών μεθόδων.