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

Abstract

The first objective of this thesis is the development of an algorithm for linear programming problems to identify binding constraints, leading simultaneously to the reduction of the problem dimension. The application of the algorithm to linear programming problems, such as efficiency maximization, cost minimization and time scheduling problems are also presented. These kinds of problems are basically summarized into the categories of the assignment and common due date problems. The second objective of this thesis, is an attempt to classify the constraints of linear programming problems, using a classification rule, while applying information from both the constraints of the problem and the objective function. The research for this thesis has been focused on the implementation of a method of locating binding constraints in linear programming problems. The developed method was first applied to general linear programming problems and then to operational research problems, specifically to production planning problems. The proposed method was based on a newly introduced notion, the weighted average of any constraint of the problem, which is a starting point of the proposed method and a potential estimator of the optimal solution. The developed method, transforms the initial problem, in which the number of constraints is much larger than the number of variables, into an equivalent one having a smaller dimension. The proposed algorithm reduces the size of the problems with respect to the number of constraints, while identifying a number of binding constraints to solve the problem. Then, when applying the algorithm to assignment problems where all constraints are binding, the constraints that play a more important role in achieving the optimal solution are identified and ranked in a priority order. In this way, the most important constraints on which we will rely most to identify the best solution are preferred. Applying the algorithm to assignment problems that are in a dual form results in identifying the optimal solution of the primal problem and identifying alternative solutions families apart from the optimal one, that can be used in case of a possible system failure. In case of time scheduling problems with a common due date that are in the primal problem form, the identification of binding constraints is achieved as well as a significant reduction in the dimension of the problem. The proposed method identifies the constraints relating to the starting times of the work or the completion of the work in which we should give a basis in solving the problem by proposing an initial solution to the problem.

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