Open AccessDesign and development of a hybrid mathematical programming algorithm
Author(s) -
Themistoklis Glavelis,
Θεμιστοκλής Γλαβέλης
Publication year - 2021
Language(s) - English
Resource type - Dissertations/theses
DOI - 10.12681/eadd/46141
Subject(s) - interior point method , simplex algorithm , simplex , algorithm , point (geometry) , benchmark (surveying) , linear programming , computer science , mathematics , mathematical optimization , combinatorics , geometry , geography , geodesy
Κύριος στόχος της διατριβής είναι η μελάτη των αλγορίθμων γραμμικής βελτιστοποίησης και των 3 μεγάλων κατηγοριών, συνοριακοί αλγόριθμοι, μέθοδοι εσωτερικών σημείων (interior point methods) και αλγόριθμοι εξωτερικών σημείων (exterior point algorithms). Εκτός από τη μελέτη τους, σκοπός της διατριβής είναι η προσπάθεια συνδυασμού αυτών.Ένας σημαντικός τομέας του γραμμικού προγραμματισμού είναι οι προλυτικές διαδικασίες. Με τις προλυτικές διαδικασίες οι διαστάσεις του γραμμικού προβλήματος μπορούν να μειωθούν αισθητά με αποτέλεσμα την παραγωγή ενός νέου γραμμικού προβλήματος ισοδύναμου με το παλιό αλλά με μικρότερες διαστάσεις με απώτερο σκοπό ο λύτης να γίνει πιο αποτελεσματικός. Επίσης, πέρα από τις υπάρχουσες διαδικασίες στην βιβλιογραφία παρουσιάστηκε κι αναπτύχθηκε μια καινούρια μέθοδος με όνομα «Εντοπισμός και διαγραφή πλεονασματικών μεταβλητών». Ο πρωτεύων αλγόριθμος εξωτερικών σημείων (Exterior Point Simplex Algorithm - EPSA) αποτελεί την πρώτη προσπάθεια ανάπτυξης αλγορίθμων που κινούνται εκτός της εφικτής περιοχής. Παραλλαγή του EPSA είναι ο πρωτεύων-δυικός αλγόριθμος τύπου Simplex δύο δρόμων (Primal Dual Exterior Point Simplex Algorithm - PDEPSA). Ο PDEPSA αν και καλύτερος του EPSA, υποφέρει εντούτοις από πιθανή εμφάνιση των φαινομένων της στασιμότητας και της κύκλωσης. Για την αποφυγή των φαινομένων της στασιμότητας και της κύκλωσης παρουσιάζουμε μια συγκεκριμένη παραλλαγή του PDEPSA που ονομάζεται Primal Dual Interior Point Simplex Algorithm (PDIPSA. Στην συγκεκριμένη εργασία πραγματοποιήθηκε υπολογιστική μελέτη για να ελεγχθούν στην πράξη τα παραπάνω. Η κύρια συνεισφορά της διατριβής είναι η μελέτη για το κατά ποσό μπορούν να συνδυαστούν αλγόριθμοι διαφορετικών κατηγοριών. Πιο συγκεκριμένα, ο συνδυασμός αλγορίθμων εσωτερικών σημείων και αλγορίθμων εξωτερικών σημείων είναι στο επίκεντρο. Αναλυτικότερα, γίνεται χρήση του PDIPSA διότι αποτελεί μια από τις πιο αποδοτικές παραλλαγές των αλγορίθμων εξωτερικών σημείων και του αλγορίθμου Mehrotra Predictor-Corrector από την ομάδα των αλγορίθμων εσωτερικών σημείων. Επομένως, ο συνδυασμός αυτός αποτελεί έναν πολλά υποσχόμενο αλγόριθμο, διότι με αυτόν τον τρόπο εκμεταλλευόμαστε τα δυνατά σημεία της κάθε ομάδας και αποφεύγουμε τις αδυναμίες τους. Για τον έλεγχο των παραπάνω πραγματοποιήθηκε υπολογιστική μελέτη, όπου έχουν χρησιμοποιηθεί προβλήματα benchmark από την ομάδα Netlib, από την ομάδα Kennington αλλά κι από την συλλογή Meszaros.