Estudio de las características y técnicas de resolución de los problemas de asignación multiperiodo

Abstract

In this Master Thesis we will work with combinatorial optimization problems with integer variables that can be difficult to solve exactly due to having a large number of variables or a set of complicating restrictions. To deal with these problems, a decomposition method known as “Lagrangian Relaxation”will be applied. The aim of this work involves different aspects of research in combinatorial optimization. Firstly, the main concepts associated with mathematical programming problems and some results will be recalled. Secondly, the Lagrangian Relaxation concept of a problem will also be defined and how it can help us to bound or find the solution of the original problem. Finally, Multiperiod Assignment Problems will be studied, and some solution methods and procedures will be developed and detailed to show through practical cases of these problems how the well-known iterative methods that use Lagrangian Relaxation can help us to approximate the solution of the original problem in a reasonable time limit.

En este Trabajo Fin de M´aster trabajaremos con problemas de optimizaci´on combinatoria con variables enteras que pueden ser dif´ıciles de resolver con exactitud debido a que tienen un gran n´umero de variables o un conjunto de restricciones complicadas. Para hacer frente a estos problemas, se aplicar´a un m´etodo de descomposici´on conocido como “Relajaci´on Lagrangiana”. El objetivo de este trabajo involucra diferentes aspectos de la investigaci´on en optimizaci´on combinatoria. En primer lugar, se definir´an los principales conceptos asociados a los problemas de programaci´on matem´atica y algunos resultados. En segundo lugar, tambi´en se definir´a el concepto de Relajaci´on Lagrangiana de un problema y c´omo nos puede ayudar a acotar o encontrar la soluci´on del problema original. Finalmente, se estudiar´an los Problemas de Asignaci´on Multiper´ıodo, y se desarrollar´an y detallar´an algunos m´etodos y procedimientos de soluci´on para mostrar a trav´es de casos pr´acticos de estos problemas c´omo los conocidos m´etodos iterativos que utilizan la Relajaci´on Lagrangiana pueden ayudarnos a aproximarnos a la soluci´on del problema original en un l´ımite de tiempo.