Νέες τεχνικές ανίχνευσης δεσμευτικών περιορισμών σε προβλήματα γραμμικού προγραμματισμού και εφαρμογές
Loading...
Date
2024-07-18
Authors
Τσαρμπόπουλος, Δημήτριος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στον πραγματικό κόσμο δεδομένων των ταχέως εξελισσόμενων συνθηκών που επικρατούν τη σημερινή εποχή στους τομείς της καθημερινότητας που άπτονται των προβλημάτων γραμμικού προγραμματισμού, έχει πραγματοποιηθεί μια αδιάκοπη προσπάθεια από την πλευρά των ερευνητών αυτού του είδους των προβλημάτων, καθώς και από επιστημονικούς οργανισμούς και επιχειρήσεις, για την όσο το δυνατόν ταχύτερη και αποτελεσματικότερη επίλυσή τους. Συγκεκριμένα, έχει παρατηρηθεί ότι μόνο ένα μικρό μέρος των αρχικών περιορισμών των προβλημάτων αυτών συμβάλλει στη βέλτιστη λύση του προβλήματος. Η πραγματικότητα αυτή καθιστά επιτακτική ανάγκη είτε την αφαίρεση των πλεοναζόντων περιορισμών που δεν συμβάλλουν στη βέλτιστη λύση των προβλημάτων αυτών από τη διαδικασία της επίλυσής τους, είτε τον εντοπισμό των δεσμευτικών περιορισμών, οι οποίοι συμβάλλουν στη βέλτιστη λύση, πριν από τη διαδικασία επίλυσής τους. Επειδή όμως ο απευθείας χαρακτηρισμός των περιορισμών αυτού του είδους των προβλημάτων σε δεσμευτικούς ή μη μπορεί να είναι αρκετά δύσκολος, κατά τη διάρκεια των ερευνών που πραγματοποιούνται, γίνεται χρήση προσεγγιστικών τεχνικών, οι οποίες ως στόχο έχουν να μπορούν να εντοπίσουν τους πιο πιθανούς για να καταταχθούν σε καθεμία κατηγορία.
Δεδομένης της αυξημένης πολυπλοκότητας αυτών των προβλημάτων, στην παρούσα διατριβή παρουσιάζονται πέντε νέοι αλγόριθμοι, οι οποίοι ως στόχο έχουν να κατατάξουν τους περιορισμούς δίνοντας προτεραιότητα σε αυτούς που είναι πιθανότερο να είναι δεσμευτικοί. Αυτό δύναται να συνεισφέρει στην επιτάχυνση μιας μεθόδου επίλυσης ενός προβλήματος γραμμικού προγραμματισμού και κατά επέκταση στη μείωση του κόστους επίλυσης του προβλήματος.
Κάποιοι από τους αλγόριθμους που παρουσιάζονται εφαρμόζονται σε τυχαία δημιουργημένα προβλήματα γραμμικού προγραμματισμού , στα οποία το πλήθος των περιορισμών είναι πολύ μεγαλύτερο από το πλήθος των μεταβλητών. Κάποιοι άλλοι αλγόριθμοι, εφαρμόζονται σε ένα σύνολο γνωστών νέτλιμπ προβλημάτων του πραγματικού κόσμου, όπου το πλήθος των μεταβλητών είναι κατά πολύ μεγαλύτερο σε σχέση με το πλήθος των περιορισμών, σε αντίθεση με τα τυχαία δημιουργημένα προβλήματα. Τέλος, κάποιοι από τους αλγόριθμους εφαρμόζονται και στις δύο προαναφερθείσες κατηγορίες, δηλαδή και σε τυχαία προβλήματα και σε προβλήματα νέτλιμπ. Για την πραγματοποίηση της κατηγοριοποίησης των περιορισμών, οι αλγόριθμοι που παρουσιάζονται κάνουν χρήση μιας σειράς κατάταξης, η οποία παράγεται σε κάθε αλγόριθμο με τη χρήση κάποιου συγκεκριμένου κριτηρίου, βάσει της οποίας είναι σε θέση να χαρακτηρίσουν τους περιορισμούς ως πιθανότερους ή όχι για να είναι δεσμευτικοί.
Description
Keywords
Γραμμικός προγραμματισμός, Δεσμευτικοί περιορισμοί, Πλεονάζοντες περιορισμοί, Τεχνική εγγύτητας, Ταξινόμηση περιορισμών, Ανίχνευση περιορισμών