Programación vectorial lineal y entera

  1. Jesús Manuel Jorge Santiso
Supervised by:
  1. Carlos González Martín Director

Defence university: Universidad de La Laguna

Year of defence: 2002

Committee:
  1. Miguel Sánchez García Chair
  2. Joaquín Sicilia Rodríguez Secretary
  3. Francisco Ramón Fernández García Committee member
  4. Miguel Ángel González Sierra Committee member
  5. Teodoro Ravelo Mesa Committee member
Department:
  1. Matemáticas, Estadística e Investigación Operativa

Type: Thesis

Abstract

Se tratan los spectos más interesantes, tanto desde un punto de vista teórico como algorítimico, de los problemas de programación vectorial lineal y entero, proporcionándose en ambos casos un buen número de resultados y procedimientos inéditos de enorme utilidad. Cabe destacar también el trabajo de revisión bibliográfica y compilación realizado, el cual se presenta de manera elegante, homogéneo y coherente a través de una cuidada reelaboración propia. A continuación se detalla el contenido dela memoria: En el Capítulo 1, "Fundamentos de la Programación Vectorial: El Caso Lineal" se define el problema de programación vectorial y se realiza un repaso de propiedades del mismo lo más general posible, prestando especial atención al caso lineal. En el Capítulo 2, titulado "Caracterizaciones de Caras Eficientes" se aborda esta importante y compleja cuestión de la programación vectorial lineal, aportando un buen número de tests de eficiencia originales tanto para caras y puntos arbitrarios, como para caras incidentes en un vértice no degenerado y degenerado, respectivamente. Además, dado que el problema de determinar tests de eficiencia para caras está íntimamente influenciado por el mecanismo utilizado para describirlas, hay que destacar el novedoso estudio realizado sobre este tema a través de la noción de descriptor maximal de una cara y las caracterizacionies obtenidas para e conjunto de soluciones óptimas de un programa lineal escalar. En el Capitulo 3, titulado "Tópicos Seleccionados en Programación Vectorial Lineal" se tratan impecablemente algunas de las cuestiones más relevantes relacionadas con el modelo lineal, como son el análisis de eficiencia completa, la dualidad, la identificación de objetivos redundantes y la optimización de una función lineal sobre la región eficiente. En todos estos temas se hacen aportacioines de gran valor. El capítulo 4 está dedicado exclusivamente a los métodos generadores de soluciones eficientes. Después de analizar cuidadosamente los aspectos más tradicionales de este problema, entre los que están el cálculo de un vértice eficiente inicial y la deteminación de los conjuntos de vértices y aristas eficientes, se presenta una nueva clasificación algorítmica para los métodos generadores de caras eficientes maximales compuesta por cuatro categorías mutuamente excluyentes, siendo la denominada clase "descendente local" un diseño inédito en la literatura que presenta numerosas ventajas. Para cada una de estas clases se hace un estudio detallado de propiedades y se proponen nuevos algoritmos generadores de soluciones eficientes basados en los tests de eficiencia obtenidos en el Capitulo 2. El quinto Capítulo, titulado "Programación Vectorial Lineal Entera" aborda con rigor este importante (por su gran aplicabilidad al mundo real) y difícil problema. Después de estudiar las propiedades más relevantes del mismo y analizar las relaciones existentes con sus relajaciones lineal y convexa, se presentan métodos específicos para generar el conjunto de soluciones eficientes enteras.