PROGRAMACION ENTERA

Autor: CERISOLA LOPEZ DE HARO SANTIAGO.
Año: 2003.
Universidad: PONTIFICIA COMILLAS.
Centro de lectura: ESCUELA TECNICA SUPERIOR DE INGENIERIA.
Centro de realización: ESCUELA TECNICA SUPERIOR DE INGENIERIA.

Resumen: En esta tesis se aborda el problema de la descomposición de Benders cuando los subproblemas incorporan variables enteras. Esto dificulta su resolución puesto que se pierden las propiedades típicas de convexidad de los casos lineales. En la presentación se resume el trabajo realizado de cara a la extensión teórica del algoritmo, su implantación y aplicación a modelos de coordinación hidrotérmica.

Autor: PARREÑO TORRES FRANCISCO.
Año: 2003.
Universidad: VALENCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: FACULTAD MATEMÁTICAS.

Resumen: El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequeños, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio obtenido. En esta Tesis se han abordado dos problemas concretos de corte. En ellos suponemos que las piezas a cortar y los tableros son rectangulars y que se permiten cortes que no sean de tipo guillotina. En el primer problemas se dispone de un tablero del que se ha de cortar el máximo número de piezas de un solo tipo. Este problema es conocido como el Pallet-Loading Problem. Nuestro trabajo ha consistido, en primer lugar, en el desarrollo de un algoritmo exacto, basado en procedimietnos Branch and Cut, que no habían sido aplicados hasta ahora a este problema. Este algoritmo resuelve óptimamente problemas de hasta 100 cajas que no habían sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heurístico basado en Tabu Search que resuelve de forma eficiente problemas de hasta 150 cajas. El segundo problema tratado es el problema en el que se dispone de un tablero, del que se ha de cortar un subconjunto de las piezas demandadas. Este problema admite, a su vez, varias versiones, dependiendo de la función objetivo y de la existencia o no de cotas. Se han desarrollado algoritmo heurístico que resuelven todas las versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rápidos, que pueden servir como sbrutinas de algoritmos más complejo. En una segunda fase, se ha diseñado un algoritmo metaheurístico más complejo, GRASP, para obtener soluciones, que superan en calidad a las de los mejores algoritmos publicados en menores tiempos de computación.

Autor: ALBIACH VICENT JOSÉ .
Año: 2003.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: GESTIÓN DE LA EDIFICACIÓN.
Centro de realización: UNIVERSIDAD POLITÉCNICA DE VALENCIA.

Resumen: El principal objetivo de esta tesis es introducir la dependencia horaria de los costes y restricciones temporales (ventanas de tiempo) en el conocido Problema del Agente Viajero asimétrico (PAV asimétrico) obtenido el Problema del Agente Viajero con Dependencia Horaria de los Costes (PAVDHC). Este problema básicamente consiste en: "Sea G un grafo dirigido completo donde cada vértice tiene asociada una ventana de tiempo y tanto el coste como el tiempo de recorrer cada arco dependen del momento en que empieza a ser recorrido. El problema consiste en encontrar una ruta óptima para un vehículo que abandone un vértice determinado, llamado depósito dentro de su ventana temporal, visite todos los vértices exactamente una vez dentro de su ventana de tiempo y regrese al vértice depósito antes de que se agote su ventana temporal. De tal forma que teniendo en cuenta la dependencia horaria de los costes, la ruta obtenida sea aquella cuyo coste sea el menor de todas las rutas posibles. Y en vistas a minimizar el coste total de la ruta el problema permite esperar, con coste cero, hasta el mismo momento en que un vértice activa su ventana temporal. En cuyo caso el vehículo deberá abandonar el vértice en el primer instante de tiempo". Seguidamente, se muestran los resultados teóricos que nos permitirán transformar el PAVDHC en un PAV asimétrico en un tiempo pseudo-plinomial y con ello, la posibilidad de resolver el problema de una forma óptima. Prueba de esto, es la experiencia computacional llevada a cabo con un algoritmo de resolución exacta para el PAV asimétrico transforamdo de PAVDHC. También se propondrá una generalización del PAVDHC en la que se permite esperar hasta cualquier instante de la ventana de tiempo de cualquier vértice. A este problema le llamaremos el Problema del Agente Viajero con Dependencia Horaria de los Costes y Tiempos de Espera (PAVDHCTE). Por otra parte, se ofrece un estudio detallado de la resolución aproximada del PAVDHC mediante tres procedimientos heurísticos desarrollados durante el transcurso de este proyecto de tesis. Su comparación con los resultados obtenidos con el algoritmo exacto nos proporcionarán una referencia clara para validar los resultados recogidos. Por último, se presenta una generalización del PAVDHC en la que se introducen capacidades, es decir, la posibilidad de que existan varios vehículos para satisfacer las demandas de los clientes. A este problema lo hemos llamado el Problema de Rutas de Vehículos Capacitado con Dependecia Horaria (PRVCDH), para el cual presentaremos su definición y una estrategia de resolución basada en su transformación en un tiempo pseudo-polinomial a un Problema de Rutas de Vehículos Generalizado (PRVG) y posteriormente a un Problema de Rutas por Arcos Capacitado (PRAC), para el que sí existen algoritmos de resolución exacta y heurística en la literatura científica.

Autor: ROJAS JERÓNIMO JENNY MARGARITA.
Año: 2002.
Universidad: VALLADOLID.
Centro de lectura: CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: En el presente trabajo, se aplica la metodología de los planos de corte Fenchel para resolver el problema de localización de fuente úncia en dos etapas (TSCFL). Las desigualdades Fenchel describen la envolvente convexa de la región factible XCRn sin tener que conocer de forma explícita la estructura poliédrica de --(X). Los cortes Fenchel se obtienen de resolver el problema de separación asociado a la estructura especial X. Los más violados se agregan a la formulación lineal del problema primal generando la relajación lineal Fenchel, de donde se obtiene una cota inferior fuerte para el problema TSCFL. Simultáneamente, aplicamos una heurística basada en la relajación Fenchel para obtener soluciones factibles que nos proporciona una cota superior. Ambas cotas se integran en un algoritmo Branch-and-Bound basado en relajación lineal para obtener el óptimo global.

Autor: LANDETE RUIZ MERCEDES.
Año: 2000.
Universidad: MURCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: FACULTAD DE MATEMATICAS UNIVERSIDAD DE MURCIA.

Resumen: 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 capacidades". Se distinguen cinco capitulos. En el Capitulo I se responde a las cuestiones¿cuáles son los problemas de empaquetamiento?, ¿para qué sirve resolver un problema de empaquetamiento?, ¿cómo se resuelve un problema de empaquetamiento? ¿cuáles son los contenidos de la memoria?. Además, se presentan los conceptos preliminares sobre teórica poliedrica y propiedades conocidas del problema de empaquetamiento. En el Capitulo 2 se estudian varias tecnicas para transformar facetas; partiendo de una faceta de un poliedro de empaquetamiento se obtienen diversas facetas de poliedros de empaquetamiento distintos entre sí y distintos al original de manera que el número de coeficients no nulos en las nuevas facetas es siempre mayor o igual que el número de coeficientes no nulos en la faceta original: en cierto sentido, podemos decir que se estudian técnicas que refuerzan facetas dadas. El número de facetas distintas que se pueden obtener a partir de una misma depende del número de procedimientos transformadores que se introduzcan. En el Capitulo 3 se aborda la construcción de grafos que inducen facetas de poliedros de empaquetamiento utilizando parte de la teoría desrrollada en el Capitulo 2. Una propiedad del problema de empaquetamiento es que su poliedro factible esta univocamente asociado a un grafo que se llama "grafo de intersección". Cualquier vector de incidencia de un empaquetamiento de nodos en el grafo de intersección es una solución factible del problema de empaquetamiento asociado y viceversa. Así el problema de empaquetamiento se traduce en encontrar el empaquetamiento de nodos del grafo intersección de mínimo peso y el problema de obtener facetas del poliedro factible del problema de empaquetamiento en el problema de obtener subgrafos del grafo intersección con determinados propiedades. A la búsqueda de los grafos con dichas propiedades se dedica el Capitulo 3. En particular, a estos grafos se les llama grafos productores de facetas. En los Capitulos 4 y 5 aplicaremos lo resultados de los capitulos anteriores para identificar facetas asociadas a dos problemas muy conocidos que se pueden formular como problemas de empaquetamiento: el llamado"problema de localización de plantas simple" y el llamado "problema de localización de plantes con capacidades". En ambos casos,obtendremos nuevas familias de facetas, algunas que generalizan otras conocidas. Una característica atractiva de la mayoría de las familias de facetas del poliedro factible del problema de empaquetamiento que se presenta en esta memoria es el carácter no binario de sus coeficientes: el lado izquierdo de muchas de las facetas conocidas de dicho poliedro es una suma de variables con coeficientes 0-1.

Autor: RAMOS GARCIA M. TERESA.
Año: 2000.
Universidad: VALLADOLID.
Centro de lectura: CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: El objetivo de programación entera es la optimización de una función en presencia de retricciones con la condición añadida de que alguna o todas sus variables han de ser enteras. El algoritmo principal para la resolución de este tipo de problemas es el algoritmo de branch and bound. Con el fin de mejorar los resultados computancionales obtenidos las investigaciones se han centrado en los últimos años, en la reducción del árbol de ramificación, ya sea obteniendo buenas cotas o la descripción lineal, completa o parcial, de la envolvente convexa de las soluciones factibles, objetivo este último que persiguen las tecnicas poliédricas en programación entera. La mayor parte de las familias de desigualdades validas conocidas parten de un conocimiento teórico del poliedro subyacente. En cuanto a la obtención de buenas cotas, una de las técnicas más utilizadas en la actualidad es la relajación lagrangeana. Los planos de corte Fenchel que dan la descripción lineal del poliedro subyacente en unproblema de programación entera, resuelven el problema convexificado asociado a cualquier relajación lagrangeana integrando de esta forma, las técnicas poliédricas con la relajación lagrangeana. Hasta este momento, solo se habían estudiado las desigualdades Fenchel para algunos problemas de programación entera mixta. En primer lugar se estudian las propiedades del problema separador para la familia de desigualdades Fenchel en modelos generales de programación entera mixta. Dichas propiedades dependen tanto de la solución fraccional que se desea separar como el soporte y características especiales de la estructura subyacente. Todo ello se traduce en una reducción de la dimensión del problema separador, lo que facilita enormemente la resolución de la relajación Fenchel asociada a la estructura. A continuación se proponen para el problema de localización capacitado, una relajación lagrangeana y una relajación Fenchel equivalente que proporciona una cota fuerte del problema considerado. La relajación Fenchel se extiende también a problemas lot-sizing. En el problema separador para esta familia de desigualdades se tendrán en cuenta, además de las propiedades válidas para modelos genéricos de programación entera mixta, las que se derivan de las características especiales de la región factible del problema capacitado de producción e inventario para un único item. En el capítulo se dan desigualdades Fenchel válidas para dos de las estructuras más estudiadas en los últimos años en el problema de flujo en redes con costes fijos. Además se desarrolla un algoritmo de programación dinámica para la resolución de un problema de programación entera mixta, para el que no existia hasta ahora, un algoritmo de resolución. Todos los capítulos se complementan con una heurística primal obtenida a partir del algoritmo de planos de corte Fenchel y con resultados computacionales que ponen de manifiesto la superioridad de los cortes Fenchel frente los cortes langrangeanos y la efectividad de las heurísticas propuestas.

Autor: MEJIA QUIROS GUSTAVO ANTONIO.
Año: 2000.
Universidad: POLITECNICA DE VALENCIA.
Centro de realización: E.T.S.I. INDUSTRIAL.

Resumen: Los problemas de rutas tiene su origen en el conocido problema de los puentes de konigsberg planteado por Euler. Consisten, basicamente en encontrar rutas de longitud minima en un grafo cumpliendo una serie de condiciones. Algunas aplicaciones conocidas son el reparto de correo, recogida de basuras, mantenimiento de redes de todo tipo, etc. Casi todos estos problemas son NP-duros, por lo que el estudio de la estructura facial de su poliedro de soluciones es de fundamental importancia para el diseño de algoritmos exactos de resolucion basados en la formulacion decada Problema de Rutas como un Problema de Programacion Lineal. El Problema general de Rutas sobra un grafo mixto, MGRP, consiste en, dado un grafo mixto, encontrar un tour de longitud minima que pase, al menos una vez, por un subconjunto dado de aristas"requeridas", por un subconjunto dado de arcos "requeridos" y por un subconjunto dado de vertices "requeridos". Asi, el MGRP incluye, como casos particulares, a una gran parte de los problemas de rutas clasicos y puede considerarse como el problema de rutas con un solo vehiculo mas general. Estudios poliedricos conocidos de este problema describen varias familias de desigualdades que inducen faceta del poliedro de soluciones asociado. Este problema fue estudiado por Romero (1997) y por Corberan, romero y Sanchis (1998). En estos trabajos, se definio un poliedro de soluciones asociado, y se encontraron varias familias de desigualdades que inducen faceta del poliedro de soluciones asociado. En esta tesis presentamos una nueva familia de desigualdades que inducen faceta del poliedro de soluciones asociado al MGRP, las desigualdades Honeycomb. Esta es una familia muy amplia de desigualdades que fueron introducidas por Corberan y Sanchis(1998) para el GRP no dirigido. Hemos presentado dos versionesde estas desigualdades, las desigualdades Honeycomb"estandar", es decir, con los mismos coeficientes que en el caso no dirigido, y las desigualdades Honeycomb(0,2), que tienen la misma estructura pero coeficientes distintos. Tambien hemos mejorado el unico algorito de planos de corte para el MGRP existentes, incluyendo procedimientos heuristicos de separacion para las desigualades K-C y Honeycomb estandar, y hemos obtenido resultados computacionales satisfactorios.

Autor: MOLINA LUQUE JULIAN.
Año: 1999.
Universidad: MALAGA.
Centro de lectura: CIENCIAS ECONOMICAS Y EMPRESARIALES.
Centro de realización: FACULTAD DE CIENCIAS ECONOMICAS Y EMPRESARIALES.

Resumen: En el capitulo primero hemos realizado un estudio de todos los aspectos relevantes de la Progrmaación Multiobjetivo y la Progrmaciónpor Metas Lineal, con especial orientación a aquellos aspectos computacionales y de espcial interes en las aplicaciones, ofreciendo nuestro punto de vista de algunos de estos aspectos así como algunas aportaciones. En el segundo capítulo hemos tratado estas mismas cuestiones cuando nos enfrentamos a problemas con variables enteras, prestando una especial atención al aspecto más relevante de estas metodologías, como es el elevado coste computacional que conlleva la resolución de estos problemas. El capítulo tercero es uno de los elementos fuandmaentales de este trabajo. En él se realiza una descripción detallada de la implementación computacional que hemos realizado de las principales metodologías de la Programación Multiobjetivo y la Programación por Metas Lineal, tanto en variable entera como en varibale continua, dando lugar esta labor a los progrmas PROMO y PROMOE. En el capítulo cuarto se desarrollará una aplicación a un problema real de la Programación Multiobjetivo. En este capítulo se realiza un análisis vía Progrmación Multiobjetivo de los posibles efectos de la reducción de la jornada laboral en la generación de empleo en la Comunidad Autónoma Andaluza. Para ello se formulará un modelo de Programación Multiobjetivo que se estudiará utilizando el programa PROMO. Por último, en el capítulo quinto realizaremos una aplicación a un problema real de la Programación por Metas Entera. Esta aplicación es um modelo que tratará de asignar plazas y mejoras de contrato a los distintos departamentos de una Universidad española de forma que se mejore su calidad en ciertos aspectos que se detallarán más adelante. En este caso, este problema se estudiará utilizando el progrma PROMOE.

Autor: ALONSO AYUSO ANTONIO JOSE.
Año: 1997.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: ESTADISTICA E INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: El objetivo de esta memoria es el desarrollo de formulaciones equivalentes en programación combinatoria multiperiodo con parámetros inciertos via análisis de escenarios y los desarrollos algorítmicos correspondientes. Se materializan los resultados del trabajo en su aplicación a la resolución de problemas de control del tráfico aéreo. En una primera parte se abordan los modelos determinísticos, en los que todos los parámetros están perfectamente determinados. Se presentan una novedosa formulación matemática para el problema y un procedimiento de Ramificación y Corte que permiten obtener la solución para un conjunto de casos simulados con un esfuerzo computacional aceptable. En la segunda parte de la memoria, se introduce la incertidumbre en el término independiente de las condiciones (materializado en la capacidad de los aeropuertos y del espacio aéreo del problema piloto utilizado). En este caso se presentan diversas modelizaciones según el tipo de solución buscada y se desarrollan métodos exactos y heurísticos para obtener la solución de los mismos.

Autor: ROMERO ROZALEN ANTONIO.
Año: 1997.
Universidad: VALENCIA .
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: ESTADISTICA Y INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: La memoria plantea el estudio del poliedro de soluciones del Problema del Cartero Rural definido sobre un grafo mixto. Este problema generaliza al problema del Cartero Chino sobre un grafo mixto, así como al problema del Cartero Rural sobre un grafo no dirigido. El estudio del poliedro de sus soluciones comprende: su dimensión y una descripción parcial pero importante de sus facetas. La memoria se completa con el desarrollo de un heurístico, basado en Tabú Search, para la obtención de cotas superiores y con un esquema de planos de corte en el que se incorporan los resultados teóricos obtenidos anteriormente. Todo ello supone un esquema algorítmico completo que permite la resolución óptima, o casi óptima, de los problemas, como queda reflejado en el estudio computacional que cierra el trabajo.

Autor: MARIN PEREZ ALFREDO.
Año: 1995.
Universidad: MURCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: DEPARTAMENTO DE MATEMATICA APLICADA Y ESTADISTICA PROGRAMA DE DOCTORADO: ESTADISTICA MATEMATICA.

Resumen: EL OBJETIVO DE LA TESIS ES EL ESTUDIO DE LOS PROBLEMAS DE LOCALIZACION DISCRETA EN DOS ETAPAS, ASI COMO LA OBTENCION DE ALGORITMOS EFICIENTES PARA LA RESOLUCION HEURISTICA APROXIMADA Y EXACTA DE ALGUNOS DE ESTOS PROBLEMAS. ESTOS ALGORITMOS SE BASAN EN LA TECNICA DE DESCOMPOSICION LAGRANGIANA PARA PROGRAMACION MATEMATICA ENTERA MIXTA. LOS PROBLEMAS DE LOCALIZACION DISCRETA EN DOS ETAPAS PUEDEN ESQUEMATIZARSE COMO SIGUE: ENCAUZAR UN FLUJO DE PRODUCTO DESDE UNOS ORIGENES QUE LO SUMINISTRAN, HASTA UNOS DESTINOS QUE LO DEMANDAN, A TRAVES DE UNOS PUNTOS DE TRANSBORDO, DE FORMA QUE EL COSTE TOTAL DE LA INSTALACION DE ORIGENES Y LOS PUNTOS DE TRANSBORDO MAS TRANSPORTE EN AMBAS ETAPAS SEA MINIMO. LA TECNICA DE DESCOMPOSICION LAGRANGIANA HA SIDO APLICADA CON EXITO A PROBLEMAS CONCRETOS DE ESTA FAMILIA, COMO EL PROBLEMA DE TRANSPORTE CON LOCALIZACION DE PUNTOS DE TRANSBORDO Y EL PROBLEMA DE LOCALIZACION DE PLANTAS CON RETORNO, ASI COMO A PROBLEMAS DE LOCALIZACION DISCRETA MONOETAPICA. SE HAN CONSTRUIDO ALGORITMOS PARA LA OBTENCION DE SOLUCIONES HEURISTICAS EFICIENTES Y PARA LA RESOLUCION EXACTA DE LOS PROBLEMAS, Y SE HAN OBTENIDO RESULTADOS COMPUTACIONALES A PARTIR DE CONJUNTOS DE DATOS GENERADOS ALEATORIAMENTE Y OTROS OBTENIDOS DE LIBRERIAS DISTRIBUIDAS A TRAVES DE INTERNET.

Autor: MARTIN GONZALEZ GERMAN.
Año: 1995.
Universidad: VALENCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: ESTADISTICA E INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: 130 ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: EL PROBLEMA DE CONSTRUCCION DE HORARIOS ESCOLARES CONSISTE EN LA ASIGNACION DE UN CONJUNTO DE LECCIONES (COMBINACION DE UNO O MAS GRUPOS DE ESTUDIANTES, PROFESORES, ASIGNATURAS Y AULAS) A UN CONJUNTO DE PERIODOS (HORAS SEMANALES DE CLASE), CON CIERTAS RESTRICCIONES DERIVADAS DE LA DISPONIBILIDAD DE LOS GRUPOS, PROFESORES Y AULAS, DE LA LEGISLACION DEL SISTEMA EDUCATIVO Y DE LOS REQUERIMIENTOS ESPECIFICOS DE CADA CENTRO.EL OBJETIVO ES OBTENER UNA SOLUCION POSIBLE QUE SATISFAGA, EN LO POSIBLE, CIERTOS OBJETIVOS, ENTRE ELLOS, QUE LOS HORARIOS DE LOS PROFESORES SEAN COMPACTOS.CONSIDERANDO LOS GRUPOS, PROFESORES, ASIGNATURAS Y AULAS COMO RECURSOS PARA LAS LECCIONES, EL PROBLEMA PUEDE SER MODELIZADO COMO LA SECUENCIACION DE UN PROYECTO CON RECURSOS LIMITADOS. PARA RESOLVERLO, HEMOS DESARROLLADO UN ALGORITMO EN TRES FASES. EN LA FASE I, SE CONSTRUYE UNA SOLUCION INICIAL USANDO EL ESQUEMA DE LOS ALGORITMOS HEURISTICOS EN PARALELO CON REGLAS DE PRIORIDAD, PERO INCLUYENDO EN CADA PERIODO UN HEURISTICO PARA OBTENER EL CONJUNTO INDEPENDIENTE DE CARDINALIDAD MAXIMA EN EL GRAFO DE RECURSOS DEL PERIODO. EN LA FASE II, UN PROCEDIMIENTO DE BUSQUEDA CON LISTAS TABU PARTE DE LA SOLUCION DE LA FASE I Y OBTIENE UNA SOLUCION POSIBLE PARA EL PROBLEMA. LA FASE III CONSISTE EN UN CONJUNTO DE PROCEDIMIENTOS QUE HACEN LOS HORARIOS MAS COMPACTOS, BASADOS EN EL CALCULO DE CICLOS DE COSTE NEGATIVO EN LOS GRAFOS DE SOLUCION. EL ALGORITMO HA SIDO PROBADO SOBRE UN CONJUNTO DE PROBLEMAS REALES, QUE HAN PODIDO SER MODELIZADOS Y RESUELTOS RAPIDA Y SATISFACTORIAMENTE EN ORDENADORES PERSONALES.

Autor: SALAZAR GONZALEZ JUAN JOSE.
Año: 1995.
Universidad: LA LAGUNA.
Centro de lectura: CENTRO SUPERIOR DE INFORMATICA .
Centro de realización: DEPARTAMENTO: DEPARTAMENTO DE ESTADISTICA, INVESTIGACION OPERATIVA Y COMP. PROGRAMA DE DOCTORADO: ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: EL CAPITULO 1 ES UNA INTRODUCCION GENERAL A LA MEMORIA. EL CAPITULO 2 REALIZA UN ANALISIS DEL POLITIPO ASOCIADO AL PROBLEMA DEL CICLO EN GRAFOS NO DIRIGIDOS. EL CAPITULO 3 TRATA LOS POLITULOS ASOCIADOS CON EL PROBLEMA DEL VIAJANTE DE COMERCIO GENERALIZADO, Y CON UNA VARIANTE DE ESTE. EL CAPITULO 4 PROPONE UN ALGORITMO DE RAMIFICACION Y CORTE PARA LA RESOLUCION DE LOS PROBLEMAS DEL CAPITULO ANTERIOR. EL CAPITULO 5 INTRODUCE Y AFRONTA LA RESOLUCION DEL PROBLEMA DE LA ORIENTACION MEDIANTE UNA TECNICA DE RAMIFICACION Y CORTE. EL CAPITULO 6 MUESTRA LOS RESULTADOS OBTENIDOS RESOLVIENDO EL PROBLEMA DE RUTAS DE VEHICULOS CON CAPACIDADES, USANDO EL CLASICO MODELO MATEMATICO CON 3 INDICES, OPORTUNAMENTE REFORZADO CON LA INCORPORACION DE NUEVAS FAMILIAS DE RESTRICCIONES. EL CAPITULO 7 PRESENTA UNA NUEVA APLICACION DE LA COMBINATORIA POLIEDRICA EN LA DIFUSION DE TABLAS ESTADISTICAS PUBLICAS. EL CAPITULO 8 INTRODUCE UN NUEVO PROBLEMA QUE GENERALIZA EL PROBLEMA DE LOCALIZACION SIN CAPACIDADES, DE GRAN UTILIDAD EN LA SELECCION OPTIMA DE INDICES EN EL DISEÑO DE BASES DE DATOS. EN CADA CASO, LA EFECTIVIDAD DE LAS TECNICAS QUE SE PROPONEN VIENE AVALADA POR RESULTADOS COMPUTACIONES QUE LAS COMPARAN FAVORABLEMENTE FRENTE A LAS TECNICAS PROPUESTAS POR OTROS AUTORES PARA ESTOS MISMOS PROBLEMAS.

Autor: VITORIANO VILLANUEVA BEGOÑA.
Año: 1994.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: ESTADISTICA E INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: EL TEMA FUNDAMENTAL DE LA MONOGRAFIA ES EL ESTUDIO DE BLOQUES Y ANTIBLOQUES DE UN "CLUTTER" DE SUBCONJUNTOS DE UN CONJUNTO FINITO. EN EL SEGUNDO CAPITULO SE OBTIENEN IMPORTANTES RESULTADOS SOBRE BLOQUES Y ANTIBLOQUES RELATIVOS A LA UNION Y DIFERENCIA DE "CLUTTER", ASI COMO SOBRE LOS "CLUTTERS" RELATIVOS A UN PROBLEMA TIPO MOCHILA. SE OBTIENEN IMPORTANTES RESULTADOS SOBRE LA COMPLEJIDAD DE PROBLEMAS COMBINATORIOS EN FUNCION DE LAS DISCREPANCIAS ENTRE LAS CLASES BLOQUE Y ANTIBLOQUE. ES DE DESTACAR LA CONEXION QUE SE REALIZA ENTRE LOS PROBLEMAS DE RECUBRIMIENTO Y EMPAQUETADO Y EL ESTUDIO DE BLOQUES Y ANTIBLOQUES. EN EL CAPITULO TERCERO SE CARACTERIZAN LAS FACETAS DEL POLITOPO DE RECUBRIMIENTO CON COEFICIENTES 0,1,2,3 O EN 0,1,2,3,4. EN EL ULTIMO CAPITULO SE OBTIENE UNA IMPORTANTE MODIFICACION DEL METODO REVISADO DEL SIMPLEX Y SE DESARROLLA UNA METODOLOGIA PARA LA INTRODUCCION DE CORTES MEDIANTE CARAS DESDE UN PUNTO DE VISTA COMPUTACIONAL.

Autor: ALMIÑANA ALEMANY MARCOS.
Año: 1993.
Universidad: VALENCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: ESTADISTICA E INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: (130) ESTADISTICA E INVESTIGACION OPERATIVA.

Resumen: EL OBJETIVO PRINCIPAL DE LA MEMORIA ES EL DESARROLLO DE NUEVOS ALGORITMOS HEURISTICOS QUE RESUELVAN DE MODO EFICIENTE EL PROBLEMA DEL CUBRIMIENTO TOTAL. PUESTO QUE ESTE ES UN CASO PARTICULAR DEL "SET COVERING PROBLEM" EL CAPITULO I ESTA DEDICADO AL PLANTEAMIENTO Y FORMULACION DE AMBOS PROBLEMAS. EN EL SE DEMUESTRAN TEORICAMENTE DIVERSAS PROPIEDADES DE LAS REGLAS DE REDUCCION. EN EL CAPITULO II SE ABORDA EL DESARROLLO DE DOS NUEVOS HEURISTICOS TIPO "GREEDY" CUYA EFICIENCIA ES ANALIZADA COMPARANDO SUS RESULTADOS CON LOS QUE SE OBTIENEN MEDIANTE OTROS DOS REPUTADOS HEURISTICOS (GH1 Y GH2) AL SER APLICADOS SOBRE UNA BATERIA DE PROBLEMAS GENERADOS ALEATORIAMENTE. EL CAPITULO II ESTA DEDICADO A LA CONSTRUCCION DE UN NUEVO ALGORITMO (RS), MUCHO MAS COMPLEJO QUE LOS ANTERIORES, BASADO EN UNA COMBINACION DE LAS TECNICAS LAGRANGIANAS CON LA RESOLUCION DE PROBLEMAS SUBROGADOS. A EFECTOS COMPARATIVOS SE RECURRE AL ALGORITMO DE LOPEZ Y LORENA (1992) Y AL DE VASKO Y WILSON (1986). LA EXPERIENCIA COMPUTACIONAL DEMUESTRA QUE NUESTRO ALGORITMO ES EL MAS POTENTE DE ENTRE LOS DISEÑADOS HASTA EL MOMENTO PARA LA RESOLUCION DE LOS PROBLEMAS DE LOCALIZACION CON CUBRIMIENTO TOTAL.

Autor: CODINA SANCHO ESTEVE.
Año: 1993.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMATICA.
Centro de realización: DEPARTAMENTO: ESTADISTICA E INVESTIGACION OPERATIVA PROGRAMA DE DOCTORADO: APLICACIONES CUANTITATIVAS Y TECNOLOGICAS DE LA INFORMATICA..

Resumen: ESTE TRABAJO DE TESIS SE HA CENTRADO EN LAS APROXIMACIONES DE CONTROL OPTIMO DEL PROBLEMA DE ASIGNACION DINAMICA DE TRAFICO (ADT). SE DESCRIBEN CON DETALLE POR SU IMPORTANCIA EL MODELO DE MERCHANT Y NEMHAUSER, EL MODELO DE CAREY Y DIVERSOS MODELOS HEURISTICOS. POSTERIORMENTE SE DESCRIBEN LOS MODELOS DE CONTROL OPTIMO COMO UNA EVOLUCION DE LOS ANTERIORES. SE PROCEDE DESPUES A EFECTUAR UN ESTUDIO CRITICO DE DICHOS MODELOS QUE CONDUCEN A PROBLEMAS DE OPTIMIZACION NO LINEAL DE GRANDES DIMENSIONES, INCLUSO PARA EL CASO DE REDES DE TAMAÑO MEDIANO. TAMBIEN HA CONSTITUIDO UN OBJETIVO EL DESARROLLO DE UN ALGORITMO QUE PERMITE LA DESCOMPOSICION DE LOS PROBLEMAS DE OPTIMIZACION RESULTANTES EN OTROS DE MENOR TAMAÑO BAJO EL QUE SE PUEDEN ABORDAR LOS SUBPROBLEMAS DERIVADOS DE ESTOS MEDIANTE ALGORITMOS DE GENERACION DE VERTICES. DADA UNA DESCRETIACION DE UN PCO MEDIANTE LA DIVISION DEL HORIZONTE DE TIEMPO EN SUBINTERVALOS DE IGUAL LONGITUD, EL ALGORITMO QUE SE PRESENTA PERMITE EL TRATAMIENTO DE CADA PAREJA DE SUBINTEVALOS CONSECUTIVOS DE TIEMPO POR SEPARADO. POSTERIORMENTE, SE PRESENTA LA EXTENSION DEL ALGORITMO DESARROLLADO A PCOS CON RESTRICCIONES DE DESIGUALDAD EN SUS VARIABLES DE CONTROL Y DE ESTADO Y CON RESTRICCIONES LINEALES ADICIONALES EN LOS CONTROLES DE MANERA QUE SEA POSIBLE MEDIANTE ESTOS ALGORITMOS EL CALCULO DE LOS EXTREMALES DE LOS MODELOS DE ASIGNACION DINAMICA PLANTEADOS COMO PCOS.

Autor: HERRERA TRIGUERO FRANCISCO.
Año: 1990.
Universidad: GRANADA .
Centro de lectura: CIENCIAS.
Centro de realización: DEPARTAMENTO: CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL PROGRAMA DE DOCTORADO: TRATAMIENTO DE LA INFORMACION EN INTELIGENCIA ARTIFICIAL.

Resumen: EN ESTA MEMORIA SE ESTUDIAN LOS MODELOS DE PROGRAMACION ENTERA DIFUSA, ASI COMO LOS ALGORITMOS QUE PUEDEN RESOLVERLOS, COMO PASO PREVIO PARA PODER APLICARLOS EN CONTEXTOS EN LOS QUE SEA NECESARIO RESOLVER PROBLEMAS CON VARIABLES DE NATURALEZA INTEGRO-DIFUSA ASI COMO A PROBLEMAS DE RAZONAMIENTO EN SISTEMAS BASADOS EN CONOCIMIENTO IMPRECISO. EN PRIMER LUGAR, SE ABORDA LA CLASIFICACION DE LOS PROBLEMAS DE PROGRAMACION ENTERA DIFUSA. A PARTIR DE LA MISMA SE PASAN A FORMULAR Y RESOLVER LOS MODELOS SIGUIENTES: - PROGRAMACION LINEAL ENTERA CON VARIABLES DIFUSAS, RESTRICCIONES DIFUSAS Y COSTOS DIFUSOS. - PROGRAMACION LINEAL BOOLEANA CON RESTRICCIONES Y COSTOS DIFUSOS. LA MEMORIA TERMINA CON UNA INTRODUCCION A LAS LINEAS ABIERTAS PARA FUTURAS INVESTIGACIONES.

Autor: SAVALL CASTELLA JUAN VICENTE.
Año: 1989.
Universidad: VALENCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: DEPARTAMENT D'ESTADISTICA I INVESTIGACIO OPERATIVA FACULTAT DE MATEMATIQUES. UNIVERSITAT DE VALENCIA. .

Resumen: EL PROBLEMA DEL CARTERO RURAL EN UN GRAFO DIRIGIDO (DRPP) ES UNA GENERALIZACION DEL PROBLEMA DEL CARTERO CHINO EN UN GRAFO DIRIGIDO, EN EL SENTIDO DE QUE NO TODOS LOS ARCOS DEL GRAFO DEBEN SER RECORRIDOS POR UN CAMINO CERRADO DIRIGIDO CON EL MINIMO COSTE, SINO SOLAMENTE UN SUBCONJUNTO DE ELLOS. FORMULADO DICHO PROBLEMA COMO UN PROBLEMA DE OPTIMIZACION COMBINATORIA, SE ESTUDIA EL POLIEDRO ASOCIADO CON EL CONJUNTO DE SOLUCIONES POSIBLES, DETERMINANDO SU DIMENSION Y ALGUNAS DE SUS FACETAS Y DESIGUALDADES VALIDAS. UTILIZANDO EL CONOCIMIENTO POLIEDRICO SE DISEÑA UN ALGORITMO DE PLANOS DE CORTE CUYA EFICACIA SE COMPRUEBA SOBRE UNA COLECCION DE PROBLEMAS TEST RESUELTOS OPTIMAMENTE, EXISTENTES EN LA LITERATURA. POR OTRA PARTE, SE DISEÑAN DOS ALGORITMOS APROXIMADOS QUE SE COMPARAN CON DOS YA EXISTENTES, IMPLEMENTADOS LOS CUATRO EN FORTRAN, SE OFRECEN RESULTADOS COMPUTACIONALES SOBRE UNA COLECCION DE 60 PROBLEMAS TEST.

Autor: TAMARIT GOERLICH JOSE MANUEL.
Año: 1988.
Universidad: VALENCIA.
Centro de lectura: MATEMATICAS.
Centro de realización: DPTO. DE ESTADISTICA E INVESTIGACION OPERATIVA, FACULTAD DE MATEMATICAS -UNIVERSIDAD DE VALENCIA-.

Resumen: EL PROBLEMA DE SECUENCIACION CON LIMITACION DE RECURSOS QUE ESTUDIAMOS CONSISTE EN LA PLANIFICACION DE UN PROYECTO SIN POSIBILIDAD DE INTERRUPCION DE LAS ACTIVIDADES QUE LO COMPONEN UNA VEZ HAN INICIADO SU EJECUCION, CON LIMITES DE RECURSOS DISPONIBLES CONSTANTES A LO LARGO DE TODO EL PROYECTO, Y EN EL QUE EL OBJETIVO ES MINIMIZAR EL TIEMPO TOTAL DE EJECUCION. LAS DURACIONES DE LAS ACTIVIDADES, LAS RELACIONES DE PROCEDENCIA ENTRE ELLAS Y LOS REQUERIMIENTOS DE RECURSOS PARA SU EJECUCION SE SUPONEN ENTEROS, CONOCIDOS Y CONSTANTES A LO LARGO DE TODO EL TIEMPO EN EL QUE SE REALIZA EL PROYECTO. DADA LA IMPORTANCIA QUE TIENE EN LA COMBINATORIA POLIEDRICA, EL DISPONER DE BUENAS SOLUCIONES INICIALES POSIBLES, EN ESTA TESIS PRESENTAMOS EN PRIMER LUGAR, DOS NUEVAS FAMILIAS DE ALGORITMOS HEURISTICOS PARA LA OBTENCION DE TALES SOLUCIONES. EL DESARROLLO DE ESTOS ALGORITMOS SE BUSCA EN LOS CONCEPTOS DE RAMIFICACION Y ACOTACION SIN RETROCESO PARA UNA DE LAS FAMILIAS Y EN EL DE RESOLUCION DE CONJUNTOS INCOMPATIBLES PARA LA OTRA. ASIMISMO SE HACE UN ESTUDIO COMPARATIVO DE ESTOS ALGORITMOS ENTRE SI Y CON LOS QUE YA EXISTEN EN LA LITERATURA. EN SEGUNDO LUGAR SE PROPONE UNA NUEVA FORMULACION ENTERA PARA EL PROBLEMA DEFINIENDO A PARTIR DE ELLA, EL POLIEDRO ASOCIADO. SE OBTIENE LA DIMENSION DEL POLIEDRO Y SE ESTUDIA A CONTINUACION, CUALES DE LAS DESIGUALDADES QUE APARECEN EN LA FORMULACION INDUCEN FACETAS. A CONTINUACION SE GENERALIZAN LOS TEOREMAS DE LIFTING SIMULTANEO ENUNCIADO POR ZEMEL EN 1978, PARA ADECUARLOS A NUESTRO PROBLEMA, Y SE APLICAN PARA OBTENER NUEVAS DESIGUALDADES VALIDAS Y FACETAS. POR ULTIMO SE EXPONE UN METODO PARA OBTENER COTAS INFERIORES QUE JUNTO CON LAS COTAS SUPERIORES YA OBTENIDAS, PERMITIRA REDUCIR EL NUMERO DE VARIABLES Y LA COMPLEJIDAD DEL PROBLEMA ORIGINAL.

Autor: OJO MESA JUAN DEL.
Año: 1987.
Universidad: SEVILLA .
Centro de lectura: MATEMATICAS.