Μελέτη γραμμικών υποδειγμάτων με περιορισμούς και εφαρμογές στην επιχειρησιακή έρευνα

• Κύριος συγγραφέας: Νικολοπούλου, Ειρήνη
• Άλλοι συγγραφείς: Nikolopoulou, Eirini
• Γλώσσα: Greek
• Έκδοση: 2020
• Θέματα: Γραμμικά υποδείγματα με περιορισμούς; Ταξινόμηση περιορισμών; Προγραμματισμός παραγωγής; Μείωση διάστασης; Γραμμικός προγραμματισμός; Linear constrained models; Constraint classification; Production planning; Dimension reduction; Linear programming

Στον πραγματικό κόσμο, η μεγάλη διάσταση των προβλημάτων, έχει μεταξύ άλλων ως αποτέλεσμα την αυξημένη πολυπλοκότητα κατά την επίλυση τους. Περαιτέρω, στα προβλήματα που μοντελοποιούνται με βάση τον γραμμικό προγραμματισμό, μόνο ένα μικρό ποσοστό των περιορισμών είναι απαραίτητοι για τη βέλτιστη λύση. Αυτό έχει ως αποτέλεσμα την αδιαμφισβήτητη ανάγκη για τη μείωση της διάστασης των προβλημάτων και προς αυτήν την κατεύθυνση κινείται η μέχρι τώρα έρευνα είτε αναφορικά με τον εντοπισμό των δεσμευτικών ή χαλαρών περιορισμών είτε με την ταξινόμηση των περιορισμών σε κάποια από τις παραπάνω κατηγορίες. Η παρούσα διατριβή έχει ως αντικείμενο αρχικά την ανάπτυξη ενός αλγόριθμου σε προβλήματα γραμμικού προγραμματισμού για τον εντοπισμό των δεσμευτικών περιορισμών οδηγώντας με αυτόν τον τρόπο στη μείωση της διάστασης των προβλημάτων. O αλγόριθμος εφαρμόζεται στις βασικές κατηγορίες προβλημάτων επιχειρησιακής έρευνας, όπως στα προβλήματα που αφορούν τη μεγιστοποίηση της απόδοσης, της ελαχιστοποίησης του κόστους, της βελτίωσης της παραγωγικότητας εντός μιας καθορισμένης χρονικής περιόδου και στα προβλήματα που ανήκουν στην κατηγορία του χρονικού προγραμματισμού. Τα συνηθέστερα αυτά προβλήματα είναι προβλήματα ανάθεσης και χρονικού προγραμματισμού με κοινή ημερομηνία παράδοσης. Στην παρούσα διατριβή γίνεται επίσης και μια προσπάθεια χαρακτηρισμού των περιορισμών σε δεσμευτικούς και πλεονάζοντες με έναν κανόνα ταξινόμησης, χρησιμοποιώντας πληροφορίες τόσο από τους περιορισμούς του προβλήματος όσο και από την αντικειμενική συνάρτηση. Η έρευνα για την εκπόνηση της διατριβής επικεντρώθηκε στην υλοποίηση μιας μεθόδου εντοπισμού των δεσμευτικών περιορισμών. Η μέθοδος που αναπτύχθηκε εφαρμόστηκε αρχικά σε γενικά προβλήματα γραμμικού προγραμματισμού και στη συνέχεια σε προβλήματα επιχειρησιακής έρευνας και συγκεκριμένα σε προβλήματα προγραμματισμού παραγωγής. Η προτεινόμενη μέθοδος βασίστηκε σε μια νέα έννοια, που παρουσιάστηκε πρόσφατα, τον σταθμικό μέσο κάθε περιορισμού του προβλήματος που αποτελεί σημείο εκκίνησης της μεθόδου και ενδεχόμενο εκτιμητή της βέλτιστης λύσης του προβλήματος. Η μέθοδος που αναπτύχθηκε, μετατρέπει το αρχικό πρόβλημα στο οποίο το πλήθος των περιορισμών είναι κατά πολύ μεγαλύτερο από το πλήθος των μεταβλητών, σε ένα ισοδύναμο, μικρότερης διάστασης. Ο αλγόριθμος που προτείνεται, μειώνει τη διάσταση των προβλημάτων αναφορικά με το πλήθος των περιορισμών, εντοπίζοντας παράλληλα πλήθος απαραίτητων περιορισμών για τη λύση του προβλήματος ίσο με τον πλήθος των μεταβλητών του. Στη συνέχεια, κατά την εφαρμογή του αλγόριθμου σε προβλήματα ανάθεσης όπου όλοι οι περιορισμοί είναι δεσμευτικοί, εντοπίζονται οι περιορισμοί που παίζουν σημαντικότερο ρόλο στην επίτευξη της βέλτιστης λύσης και κατατάσσονται με μια σειρά προτεραιότητας. Κατά αυτόν τον τρόπο, προτάσσονται ως πιο σημαντικοί συγκεκριμένοι περιορισμοί στους οποίους θα βασιστούμε περισσότερο για τον εντοπισμό της βέλτιστης λύσης. Η εφαρμογή του αλγόριθμου σε προβλήματα ανάθεσης που βρίσκονται σε δυϊκή μορφή έχει ως αποτέλεσμα τον εντοπισμό της βέλτιστης λύσης του πρωτεύοντος προβλήματος και τον εντοπισμό εναλλακτικών οικογενειών λύσεων εκτός από τη βέλτιστη, οι οποίες μπορεί να χρησιμοποιηθούν σε περίπτωση ενδεχόμενης αδυναμίας λειτουργίας του συστήματος. Σε προβλήματα χρονικού προγραμματισμού με κοινή ημερομηνία παράδοσης που βρίσκονται στη μορφή του πρωτεύοντος προβλήματος ο εντοπισμός των απαραίτητων περιορισμών και οδηγεί επίσης σε σημαντική μείωση της διάστασης του προβλήματος, και εντοπίζει τους περιορισμούς που αφορούν τους χρόνους έναρξης των εργασιών ή την περάτωση των εργασιών στις οποίες θα πρέπει να δώσουμε βάση κατά την επίλυση του προβλήματος προσδιορίζοντας με αυτόν τον τρόπο μια αρχική λύση του προβλήματος. Η επιστήμη της επιχειρησιακής έρευνας ασχολείται με τη μελέτη και την ανάλυση των επιχειρησιακών προβλημάτων, αναζητώντας τη βέλτιστη ή μια προσέγγιση της βέλτιστης λύσης. Για την επίλυση ενός προβλήματος χρησιμοποιούνται τόσο ποσοτικά όσο και ποιοτικά στοιχεία. Η υιοθέτηση μιας συνολικής προσέγγισης όπως προτείνεται από τον αλγόριθμο και η δυνατότητα περαιτέρω ανάλυσης των προβλημάτων με αξιοποίηση και ανάλυση των δεδομένων που προκύπτουν από αυτά, έχει ιδιαίτερη σημασία σε σχέση με οποιαδήποτε συγκεκριμένη επιλογή εφαρμογής ποσοτικών μεθόδων που θα οδηγήσει μόνο στην εύρεση της λύσης σε ένα μεμονωμένο πρόβλημα και που η υλοποίηση της οποίας να μην είναι προς όφελος του συνολικού συστήματος.