Back to search

University of Patras

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/47752

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Nikolopoulou, Eirini; Νικολοπούλου, Ειρήνη. Μελέτη γραμμικών υποδειγμάτων με περιορισμούς και εφαρμογές στην επιχειρησιακή έρευνα. University of Patras, 2020. http://hdl.handle.net/10442/hedi/47752