Μελέτη γραμμικών υποδειγμάτων με περιορισμούς και εφαρμογές στην επιχειρησιακή έρευνα
Authors: Νικολοπούλου Ειρήνη 
Published: September 2021

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