Ένας ακριβής αλγόριθμος για μια ομάδα τετραγωνικών προβλημάτων σακιδίου με περιορισμούς εύρους και άνω ορίων

Abstract

Αυτή η μελέτη αφορά συνεχή προβλήματα Quadratic Knapsack με περιορισμούς άνω ορίων. Τα προβλήματα αυτά αποτελούν ειδικές περιπτώσεις Quadratic Programming και γενικότερα Μη Γραμμικού Προγραμματισμού. Η επιβολή περιορισμών τύπου Knapsack σε τέτοιου είδους προβλήματα έχει αρκετές ενδιαφέρουσες θεωρητικές εφαρμογές. Επιπρόσθετα παρουσιάζονται εφαρμογές σε σημαντικούς τομείς που χρησιμοποιούν τη μορφοποίηση αυτή ως βάση για την επίλυση προβλημάτων, όπως για παράδειγμα η Βέλτιστη Επιλογή και Αναπροσαρμογή Χαρτοφυλακίου στον Οικονομικό Κλάδο, Προβλήματα Μεταφοράς και Ροών σε Δίκτυα στην Επιχειρησιακή Έρευνα, ο Ισοσκελισμός Πινάκων στο Μαθηματικό Κλάδο καθώς και εφαρμογές στον Τομέα της Συντήρησης Αεροσκαφών. Οι μελέτες που έχουν γίνει μέχρι τώρα αφορούν την κλασσική μορφοποίηση όπου ο περιορισμός τύπου Knapsack ικανοποιείται σαν ισότητα. Σε αυτή την μεταπτυχιακή εργασία ερευνάται η περίπτωση όπου επιτρέπονται αποκλίσεις γύρω από μια κεντρική τιμή. Προτείνουμε και αναλύουμε έναν καινούριο αλγόριθμο και τροποποιούμε έναν ήδη υπάρχοντα για να καλύψουμε αυτή τη διαφοροποίηση. Τέλος παρουσιάζουμε αποτελέσματα που προκύπτουν από την υλοποίηση και εφαρμογή του αλγορίθμου σε διάφορα αριθμητικά προβλήματα.