Αναβάθμιση της AUGMECON-2 για βελτιστοποίηση του αλγορίθμου επίλυσης προβλημάτων πολυστοχικού ακέραιου προγραμματισμού

Abstract

Στο πλαίσιο της αξιολόγησης επενδυτικών σχεδίων κλιματικής πολιτικής, σχεδιασμού εφοδιαστικών αλυσίδων, διαχείρισης χαρτοφυλακίων μετοχών και άλλων μείζονος σημασίας προβλημάτων της επιχειρησιακής έρευνας, αναπτύσσονται αλγόριθμοι βελτιστοποίησης με στόχο την παροχή υπηρεσιών υποστήριξης αποφάσεων προς τον αποφασίζοντα. Ωστόσο τα κριτήρια με τα οποία αξιολογούνται κρίσιμες παράμετροι των παραπάνω προβλημάτων συνήθως δεν είναι ένα, αλλά πολλά, με αποτέλεσμα η ανάλυσή τους να απαιτεί την επιστράτευση μεθόδων πολυκριτήριας ανάλυσης αποφάσεων οι οποίες χαρακτηρίζονται για την αυξημένη πολυπλοκότητά τους σε σχέση με εκείνες που επιλύουν προβλήματα μονοκριτηριακού προγραμματισμού. Η επιτομή της επίλυσης των πολυκριτηριακών προβλημάτων είναι η εύρεση του επονομαζόμενου μετώπου Pareto που παρέχει πλήρη εποπτεία των αποτελεσμάτων. Οι υπάρχοντες αλγόριθμοι ανταγωνίζονται μεταξύ τους ως προς την ακρίβεια εύρεσης του μετώπου και την ταχύτητα επίλυσης. Στην παρούσα διπλωματική αφενός γίνεται μια βιβλιογραφική ανασκόπηση ορισμένων αλγορίθμων, όπου ο καθένας αποτελεί εξέλιξη του προηγούμενου, η βάση των οποίων είναι η ε-constraint method. Στην συνέχεια εντοπίζουμε τις αδυναμίες της πιο εξελιγμένης μορφής του παραπάνω αλγορίθμου (ΑUGMECON 2) και προτείνουμε ένα ολοκληρωμένο μεθοδολογικό πλαίσιο αντιμετώπισής τους τόσο σε μαθηματικό όσο και σε προγραμματιστικό επίπεδο. Βασική ιδέα είναι η τοποθέτηση συντελεστών παράκαμψης σε εξωτερικούς βρόχους καθώς και η επιστράτευση ενός πίνακα μνήμης ώστε να αποφεύγεται η επίλυση μοντέλων που δεν παρέχουν επιπλέον πληροφορία. Έτσι επιτυγχάνεται αύξηση υπολογιστικής ταχύτητας και επίλυση προβλημάτων που σχετίζονται με τα επονομαζόμενα nadir points του προβλήματος. Ο νέος αλγόριθμος (AUGMECON 3), μετά την υλοποίησή του στο περιβάλλον GAMS, επιλύει προβλήματα που υπάρχουν διαθέσιμα στην βιβλιογραφία ώστε να συγκριθεί η απόδοσή του με τον προκάτοχό του (AUGMECON 2). Τέλος ο νέος αλγόριθμος εφαρμόζεται σε ένα πρόβλημα κλιματικής πολιτικής που αφορά στη βελτιστοποίηση χαρτοφυλακίου ενεργειακών τεχνολογιών και γίνεται μια ανάλυση ευρωστίας χαρτοφυλακίου.