Obtención de facetas de poliedros asociados a problemas de empaquetamiento

  1. Landete Ruiz, Mercedes
unter der Leitung von:
  1. Alfredo Marín Pérez Doktorvater
  2. Lázaro Cánovas Martínez Doktorvater/Doktormutter

Universität der Verteidigung: Universidad de Murcia

Fecha de defensa: 28 von Februar von 2001

Gericht:
  1. Laureano Fernando Escudero Bueno Präsident/in
  2. Carmen Noemí Zoroa Alonso Sekretärin
  3. Ángel Corberán Salvador Vocal
  4. S. Nickel Vocal
  5. Juan José Salazar González Vocal
Fachbereiche:
  1. Estadística e Investigación Operativa

Art: Dissertation

Teseo: 82566 DIALNET

Zusammenfassung

El objetivo general de la memoria es profundizar en el estudio políedrico de los problemas de empaquetamiento, El problema de empaquetemiento es el problema de maximizar un función objetivo lineal sujeta a un conjunto de restricciones lineales con termino independiente unitario y variables binarias. El estudio poliédico consiste basicamente en la identificacion de desigualdades validas o, preferiblemente, de facetas. Por otro lado, el estudio poliedrico es un procedimiento para tratar problemas enteros en general: no es exlusivo para los problemas de empaquetamiento. Varios motivos para abordar el estudio de desigualdades válidas del problema de empaquetamiento son: 1. Los métodos de ramificación y corte son herramientas muy usadas y útiles para resolver problemas enteros en general. 2. Algunos problemas enteros o mixtos contienen restricciones con coeficientes 0-1 exclusivamente. 3. Algunos procesadores de problemas enteros generan de manera automática restricciones con coeficientes binarios como, por ejemplo, cotas. La memoria se propone cuatro objetivos específicos: 1.Obtener procedimientos que transformen facetas de poliedros en facetas de otros poliedros. Por un lado se busca transformar facetas de poliedros en otros de mayor dimensión, lo que se conoce con el nombre de levantamientos, y por otro transformar las originales en otras de poliedros de menor dimensión, lo que se dice proyectar la faceta. 2. Identificar familias de poliedros de las que se conozcan familias de facetas. Aprovechando los procedimientos transformadores se pueden exportar las facetas de poliedros pequeños con buenas propiedades a toros más complejos. 3. Aplicar todo lo anterior para mejorar la descripción poliédrica actual de dos problemas conocidos de localización discreta que se formulan como problemas de empaquetamiento: los llamados "problema de localización de plantas simple" y "problema de localización de plantas con capa