PROGRAMACION ENTERA

Autor: SIMON DE BLAS CLARA.
Año: 2003.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FACULTAD DE CC. MATEMÁTICAS.
Centro de realización: FACULTAD DE CIENCIAS MATEMATICAS.

Resumen: La presente monografía está dedicada a problemas clásicos de la Investigación Operativa bajo un enfoque distinto: la optimización en el mayor de los coeficientes del problema. La dificultad de abordar bajo este objetivo problemas que ya de por sí son irresolubles en un tiempo computacional razonable, hace que en la actualidad esté casi sin explorar. Se han seleccionado por su envergarudra los problemas de transporte, asignación cuadrática y de rutas para ampliar su estudio y ofrecer soluciones alternativas a un objetivo clásico, como es la optimización en la suma de las componentes de los coeficientes del problema. Se considera en la presente monografía el problema de embotellamiento tal y como viene definido por Burkard en 1973 con la formulación alternativa de Punnen, así como para el problema cuadrático. Se presentan algoritmos de resolución, tanto generales como aproximados, así como su planteamiento mediante la Teoría de Grafos. Se presentan diferentes teoremas clásicos en la literatura que permiten caracterizar las soluciones óptimas, bajo un enfoque común establecido en la monografía, de una Teoría General del Embotellamiento. Se analizan los diferentes casos particulares: transporte, asignación, localización, viajante, lexicográfico, petición, árbol soporte biconexo, capacidad, camino mínimo, emparejamiento, árboles de Steiner y sus variantes, ancho de banda, entre otros. Por último se presentan las aplicaciones más notables existentes en la literatura.

Autor: MERINO MAESTRE MARÍA.
Año: 2004.
Universidad: PAÍS VASCO.
Centro de lectura: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).
Centro de realización: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).

Resumen: En el trabajo se desarrollan los siguientes aspectos: En primer lugar, se persigue explicar el interés de la Programación Estocástica en general y su aplicación en el mundo financiero y económico en particular. Para ello se describen los conceptos fundamentales, las tecnologías de modelización, los métodos de resolución y las múltiples aplicaciones de esta disciplina. En segundo lugar, en el campo de la modelización estocástica, se persigue generalizar conceptos definidos en los modelos lineales bietapa a los modelos multietapa mixtos 0-1, incorporar medidas de riesgo, así como contrastar la bondad de la solución estocástica propuesta frente a la determinista basada en el escenario promedio. En tercer lugar, en cuanto a las metodologías de resolución en optimización bajo incertidumbre, se diseña y se contrasta mediante la correspondiente experiencia computacional algoritmos de descomposición de modelos estocásticos mixtos 0-1, tanto para el caso bietápico como multietápico, todos ellos de grandes dimensiones. Por último, se describen, modelizan y resuelven de forma eficiente dos aplicaciones en el ámbito financiero. La primera consiste en la estructuración de una cartera de títulos con garantía hipotecaria bajo incertidumbre y la segunda trata la gestión de una cartera de activos y pasivos de renta fija bajo incertidumbre.

Autor: Plana Andani Isaac.
Año: 2004.
Universidad: VALENCIA.
Centro de lectura: Facultad de Matemáticas.
Centro de realización: Facultad de Matemáticas.

Resumen: En esta tesis, hemos estudiado el Problema General de Rutas con Viento (WGRP). Dicho problema consiste en, dado un grafo G=(V,E), con un conjunto de vértices V, un conjunto de aristas E y dos costes c(i,j), c(j,i) asociados a cada arista, uno por sentido de recorrido, y dados un subconjunto de vértices requeridos VR perteneciente a V y un subconjunto de aristas requeridas ER incluido en E, hallar un tour de coste mínimo que recorra al menos una vez todas las aristas requeridas y visite todos los vértices requeridos. Este problema tiene un doble interés, ya que modeliza situaciones reales, de las cuales presentamos detalladamente un ejemplo en esta memoria, y, al mismo tiempo, generaliza a la mayoría de Problemas de Rutas por Arcos con un solo vehículo conocidos.Hemos estudiado el poliedro asociado al espacio de soluciones del problema, describiendo las siguientes familias de esigualdades y demostrando que definen faceta del poliedro: desigualdades triviales, desigualdades de obligatoriedad, esigualdades de conectividad, desigualdades de cortes R-impares, desigualdades K-C y K-C02, desigualdades Path-Bridge y Path-Bridge02 y desigualdades Honeycomb y Honeycomb02.También hemos introducido un teorema de ``lifting'' que afirma que todas las desigualdades de configuración que inducen faceta para el WGRP en el grafo de configuración también inducen faceta del WGRP en el grafo original. Sin embargo, hemos visto que no todas las desigualdades que inducen faceta del poliedro del WGRP son desigualdades de configuración, por lo que hemos introducido el concepto de desigualdad de configuración débil. También hemos presentado una nueva familia de desigualdades válidas que inducen facetas para el WGRP, llamadas Zigzag, y que se engloban dentro de esta nueva categoría de desigualdades. Hemos estudiado la aplicación de estas nuevas desigualdades en otros problemas que son casos particulares del WGRP, así como bajo qué condiciones son válidas e inducen facetas en estos problemas.Para la resolución del WGRP, hemos implementado un algoritmo de Ramificación y Corte (Branch & Cut), que incorpora, entre otros, un nuevo algoritmo heurístico de separación diseñado para la identificación de un cierto tipo de desigualdades Zigzag violadas. Hemos utilizado una serie de técnicas para mejorar la eficiencia del algoritmo Branch & Cut, como son la ramificación por restricciones, el tailing-off, el filtrado de desigualdades y el reinicio con cota superior artificial.Este algoritmo de Ramificación y Corte ha sido probado sobre un gran número de instancias de muy diversas características. Algunas de ellas, las más grandes, han sido generadas aleatoriamente para este trabajo, mientras que otras han sido tomadas de la literatura. No sólo hemos utilizado instancias del WGRP, sino también de problemas que aparecen como casos particulares, como el WRPP, el MGRP, el MRPP, el GRP y el GTSP. Los tamaños de las instancias varían de 7 a 1000 nodos, de 10 a 4000 aristas y de 1 a 480 componentes R-conexas. El algoritmo ha sido capaz de resolver en cuestión de segundos las instancias de tamaño pequeño y en algunos minutos las de tamaño mediano. La mayoría de las instancias de mayor tamaño también fueron resueltas óptimamente, y sólo para algunas de las instancias más difíciles y con mayor número de componentes R-conexas el algoritmo ha sido incapaz de llegar a la soluciónóptima en un tiempo límite de 10 horas, aunque el gap medio en estos conjuntos de instancias se mantiene por debajo del 0.7%.

Autor: OJEDA RODRIGUEZ JORDI.
Año: 2004.
Universidad: POLITÉCNICA DE CATALUÑA.
Centro de lectura: ETSEIB.
Centro de realización: ETSEIB, EDIFICI H Campus SUD.

Resumen: El objetivo de la tesis doctoral consiste en resolver de forma eficiente la asignación de los horarios semanales de los trabajadores polivalentes de un centro de servicios, con la condición prioritaria de asegurar una capacidad mínima en cada uno de los períodos (horas, medias horas, etc.) en que se considera dividida la semana (horizonte de programación utilizado), y procurando alcanzar una capacidad deseada, en cada uno de los períodos, teniendo en cuenta las preferencias de los trabajadores por unos u otros horarios y las prioridades de asignación de los tipos de tareas en función de la categoría de los trabajadores. La polivalencia consiste en que un trabajador de una categoría puede realizar uno o varios tipos de tareas. La prioridad indica cómo se desea que se realice la asignación de los tipos de tareas en el caso de polivalencia; de esta forma, se asigna la máxima prioridad a la tarea propia de la categoría del trabajador. También se tendrá en cuenta la eficiencia que presentan las diferentes categorías de trabajadores para ejecutar los diferentes tipos de tareas que pueden realizar, en función de la polivalencia considerada o admitida. Los datos básicos del problema son los siguientes: - Relación de trabajadores con los siguientes datos para cada uno de ellos: categoría y lista de horarios admisibles y sus preferencias. - Tipos de tareas que pueden realizar los trabajadores de cada categoría, y prioridad y eficiencia correspondiente a cada par categoría-tarea. - Capacidad mínima para cada tipo de tarea, en cada período de tiempo del horizonte de la programación (hora, media hora, etc.). - Capacidad deseada para cada tipo de tarea (que ha de ser igual o mayor que la capacidad mínima), en cada período de tiempo del horizonte de la programación. - Importancia relativa de los diferentes elementos a considerar en la función objetivo. La función a optimizar es compleja, ya que se consideran diversos objetivos: - Minimizar las desviaciones de la capacidad resultante respecto a la capacidad deseada. - Maximizar las preferencias de los trabajadores al asignar horarios. - Maximizar las prioridades al asignar los tipos de tareas a las categorías. Además, es fundamental asegurar una capacidad mínima en cada uno de los períodos, puesto que de lo contrario no podrá funcionar correctamente el centro de servicio, y aproximar la capacidad resultante el máximo posible a la capacidad deseada, utilizando una penalización no lineal asociada al déficit y al superávit de capacidad. En definitiva, se trata de aproximar la presencia de los trabajadores que proporciona la solución a la capacidad deseada, asegurando la satisfacción de dichos trabajadores. En la tesis se plantea un modelo de programación matemática mixto y un procedimiento heurístico. En total se realizan nueve experimentos diferentes para elaborar las conclusiones.

Autor: Piñana Manuel Estefanía.
Año: 2005.
Universidad: VALENCIA.
Centro de lectura: Facultad de Matemáticas.
Centro de realización: Facultad de Matemáticas.

Resumen: La minimización del ancho de banda es un problema clásico de optimización. Tuvo su origen en los años 50 en el contexto de la manipulación computacional de matrices estructurales dentro del campo de la ingeniería. Este problema es equivalente al problema del ancho de banda para grafos. Entre sus aplicaciones cabe destacar: la simplificación del proceso de resolución de sistemas de ecuaciones mediante el método de eliminación de Gauss, el diseño de sistemas de transmisión de energía, el diseño de circuitos, la aproximación de soluciones de ecuaciones en derivadas parciales o la ordenación y recuperación de la información en hipertextos. Si definimos el ancho de banda de una fila cualquiera de una matriz como el máximo de las distancias de los elementos no nulos de dicha fila a la diagonal principal, el ancho de banda de una matriz queda definido como el máximo de los anchos de todas sus filas. El objetivo es reducir el ancho de banda de la matriz en la mayor medida posible, mediante permutaciones de filas y de columnas. En el capítulo 1 presentamos una descripción más detallada del problema y sus aplicaciones, así como de los esquemas generales de las metodologías utilizadas para la resolución del problema. En el capítulo 2 presentamos un algoritmo basado en las metodologías GRASP (Greedy Randomized Adaptive Search Procedure) y Path Relinking. El capítulo 3 se centra en la resolución exacta del problema. Por un lado presentamos algunos resultados teóricos (concretamente una formulación lineal entera del problema y algunas cotas para ordenaciones parciales), y, por otro, describimos el algoritmo que sigue la metodología Branch and Bound y que hemos diseñado específicamente para este problema. Por último hemos estudiado los métodos de exploración basados en el uso de la memoria. Para ello, hemos propuesto dos nuevos métodos, uno basado en Búsqueda Tabú y otro basado en la metodología de Búsqueda Dispersa. También hemos hecho un estudio sobre la contribución de algunos elementos clave en la búsqueda heurística. Estos métodos constituyen el capítulo 4 de esta tesis. Todos los métodos diseñados han sido probados sobre una colección de instancias de libre distribución (Harwell-Boeing Sparse Matrix Collection), que ya había sido utilizada en la literatura. Los resultados han sido comparados con los obtenidos por los métodos más competitivos, obteniendo resultados muy favorables.