University of Patras
Μελέτη γραμμικών υποδειγμάτων με περιορισμούς και εφαρμογές στην επιχειρησιακή έρευνα
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2020
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Nikolopoulou, Eirini
- Νικολοπούλου, Ειρήνη
Subjects
dc:subject × 18- Γραμμικός προγραμματισμός
- Προγραμματισμός παραγωγής
- Μείωση διάστασης
- Ταξινόμηση περιορισμών
- Ποσοτική ανάλυση
- Linear programming
- Production planning
- Dimension reduction
- Constraints classification
- Quantitative analysis
- Φυσικές Επιστήμες
- Μαθηματικά
- Κοινωνικές Επιστήμες
- Οικονομικά και Επιχειρήσεις
- Natural Sciences
- Mathematics
- Social Sciences
- Economics and Business
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/47752