Spelling suggestions: "subject:"programación - (matemáticas)"" "subject:"programación - (matemáticase)""
1 |
Algoritmos en línea para problemas de balanceamiento robustoGálvez Verdugo, Waldo Elías January 2015 (has links)
Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina menos cargada. En el problema en linea los trabajos son revelados uno a uno sucesivamente, y ante la llegada de cada trabajo el programador debe decidir a qué máquina asignar el trabajo. A diferencia del modelo clásico, donde las decisiones son irrevocables, se considera un modelo dinámico introducido por Sanders et al. \cite{SSS09}. En este modelo, ante la llegada de un trabajo nuevo, algunos trabajos anteriores pueden ser reasignados. Sin embargo la carga total de trabajos migrados debe ser a lo más proporcional al tamaño del trabajo entrante. La constante de proporcionalidad se denomina \emph{factor de migración} del algoritmo, y mide la robustez de las soluciones construidas.
En primer lugar se estudian algoritmos de búsqueda local, ya que gran parte de estos algoritmos pueden ser adaptados de manera sencilla al contexto en línea con migración. Se demuestra que para la vecindad de \emph{Saltos} e \emph{Intercambios}, el factor de aproximación de una solución localmente óptima yace en el intervalo $[1.691, 1.723]$. Además, usando técnicas de sensibilidad para programación entera, se da una vecindad para la cual las soluciones localmente óptimas son $(1+\e)$-aproximadas y pueden ser halladas en una cantidad polinomial de iteraciones, obteniéndose un PTAS basado exclusivamente en búsqueda local.
Posteriormente se analizan y diseñan algoritmos para el problema en línea con migración. El primer resultado es una mejora en la cota inferior del factor de competitividad alcanzable con migración constante de $\frac{20}{19}$ obtenida por Skutella y Verschae \cite{SV10} a $\frac{17}{16}$. Luego, utilizando un procedimiento de redondeo para la instancia distinto al usado en trabajos anteriores, denominado redondeo a múltiplos, se diseña una versión en línea de optimalidad local respecto a saltos con factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Modificando esta propiedad levemente, se obtiene un algoritmo $\left(\frac{3}{2} + \e\right)$-competitivo usando factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Finalmente, explotando la simetría otorgada por el redondeo a múltiplos, se diseña una versión en línea de $\LPT$, que es una $(\frac{4}{3}+\e)$-aproximación para el problema de Cubrimiento de Máquinas, con factor de migración $O\left(\frac{1}{\e^3}\log\frac{1}{\e}\right)$. Usando la intuición generada por esta simetría junto a las técnicas de programación entera y \emph{configuraciones} de máquinas, se obtiene un nuevo programa entero para el problema que es más simple y abre las puertas a obtener un PTAS para el problema de Minimización de Makespan en línea cuyo factor de migración tenga dependencia polinomial en $\frac{1}{\e}$, lo que aún es un problema abierto.
|
2 |
Algoritmo primal - dual para el problema de programación lineal basado en el método de barrera logarítmicaQuijano Urbano, Pedro Edgar January 2019 (has links)
Presenta un método que sigue la trayectoria central para resolver un problema de programación lineal. Las ideas están basadas en el trabajo realizado por Kojima, Mizuno y Yoshise [15] y Monteiro y Adler [18]. El método permite deducir un algoritmo conocido como Algoritmo Primal-Dual de pasos cortos y alcanza una complejidad de orden de tiempo, debido a que hace uso de una medida de proximidad. / Tesis
|
3 |
Algoritmos de aproximación para la programación de trabajos divisibles con tiempos de instalación en máquinas paralelasVerdugo Silva, Víctor Ignacio January 2014 (has links)
Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En este trabajo se estudian problemas de programación de tareas en un entorno de máquinas paralelas. A diferencia de la literatura clásica, asumimos que los trabajos pueden ser divididos en distintas partes, cada una de las cuales puede ser procesada en distintas máquinas. Antes de procesar cualquier parte de un trabajo, la máquina debe prepararse y requiere un tiempo de instalación. Primero se estudia el problema de minimizar la suma ponderada de tiempos de completación, para el cual se obtiene una $(2+\varepsilon)$-aproximación cuando los tiempos de instalación son todos iguales. Este resultado corresponde al primer algoritmo de aproximación de factor constante para este problema. Usando técnicas similares se diseña una 2-aproximación para el caso de una ponderación uniforme de los trabajos, que en particular mejora el factor 2.781 obtenido por Schalekamp et al. Finalmente, con un algoritmo de {\it programación en lista}, se obtiene una 4-aproximación para el problema original con tiempos de instalación dependientes del trabajo.
Posteriormente se estudia el problema en máquinas no relacionadas, donde los tiempos de proceso e instalación dependen de cada máquina. Los algoritmos diseñados en esta sección están basados en técnicas de redondeo de relajaciones lineales. La primera relajación que se estudia permite diseñar una 3-aproximación para el problema. Al realizar un paso de {\it lift and project} sobre una restricción es posible fortalecer la relajación, lo que permite diseñar una $(1+\phi)$-aproximación, donde $\phi=\frac{\sqrt{5}+1}{2}$. Respecto a la inaproximabilidad del problema se demuestra una cota inferior igual a $\frac{e}{e-1}$ basada en un resultado de Feige para {\it Max-$k$-Cover}. Usando la relajación lineal fuerte se muestra una 2-aproximación para la versión del problema en que cada trabajo posee un conjunto restringido de máquinas en las que puede ser procesado, teniendo igual tiempo de instalación y procesamiento en todas ellas. Finalmente, se estudia relajaciones basadas en {\it configuraciones} sobre trabajos, es decir, las variables corresponden a vectores que representan la asignación de un trabajo a máquinas en una cierta programación. El programa lineal de configuraciones de trabajos posee una cantidad infinita de variables, sin embargo, se demuestra que es posible restringirse a una cantidad finita de ellas y que además es posible aproximar este programa lineal en tiempo polinomial a un factor de $1+\varepsilon$. Determinar el gap de integralidad de esta relajación queda como una pregunta abierta.
|
4 |
Asignación de Árbitros para un Campeonato de Fútbol Mediante el Uso de Programación MatemáticaAlarcón Lorca, Fernando Esteban January 2009 (has links)
La gestión en deportes es una creciente y muy fértil área para aplicaciones de
Gestión de Operaciones. Dentro de una liga deportiva existen múltiples factores
económicos y logísticos que la transforman en un interesante elemento de estudio.
Hasta la fecha, los investigadores de esta disciplina, conocida mundialmente como
Sports Scheduling, se han centrado principalmente en resolver el problema de la
programación de partidos o fixtures considerando diversas condiciones, que lo
suelen convertir en un problema combinatorial de difícil solución. Estas condiciones
se refieren a conseguir mayores beneficios económicos tanto para los equipos
participantes como para las entidades organizadoras, mayor equidad deportiva,
espectáculos más seguros y torneos más atractivos para el público, entre otros
objetivos.
Entre las últimas y nuevas aplicaciones del Sports Scheduling se encuentra el
problema conocido como TUP (Tournament Umpire Problem) o RAP (Referee
Assignment Problem) que consiste en encontrar la mejor programación de los
árbitros para un fixture ya definido, considerando diversos factores. El problema se
ha estudiado y/o aplicado en Brasil, Inglaterra y EE.UU. a deportes en particular. A
pesar que en el torneo de fútbol profesional de Chile existen las condiciones
favorables para implementar un sistema automático de asignación de árbitros, este
proceso se realiza semanalmente de forma manual, lo que lo transforma en una de
las situaciones que mayor desconfianza y problemas trae a lo largo del campeonato.
En Chile, desde el año 2005 a la fecha, el Centro de Gestión de Operaciones
(CGO) del Departamento de Ingeniería Industrial de la Universidad de Chile elabora
el fixture del campeonato de fútbol, tarea encargada por la Asociación Nacional de
Fútbol Profesional (ANFP), con excelentes resultados. Se espera que a partir de un
futuro cercano, el CGO también elabore la asignación de los árbitros al campeonato
de fútbol nacional.
Este trabajo presenta un estudio del problema de asignación de árbitros a
partidos de un campeonato de fútbol. El modelamiento matemático utilizado
incorpora metas de partidos por dirigir y distancias por recorrer, además de
novedosas restricciones que buscan hacer la asignación lo más justa y equitativa
posible para todos los actores involucrados. El caso de estudio es el campeonato de
fútbol chileno de primera división (Primera A). Se obtiene una solución óptima para el
modelamiento en tiempos bastante razonables y que satisface todos los
requerimientos impuestos. Comparada con la asignación manual realizada para el
campeonato del año 2007, las pruebas realizadas presentan una mejora en los
indicadores de equidad en la asignación de árbitros y de distancias por recorrer de
hasta un 99%. Para su implementación, se diseña una herramienta computacional
que permite asistir el proceso de asignación. Además, se propone un modelamiento
alternativo y discuten futuras extensiones.
|
5 |
Análisis e implementación del modelo de line switching en el sistema eléctrico chilenoHunt Penna, Ricardo Andrés January 2017 (has links)
Ingeniero Civil Eléctrico / El presente trabajo de memoria se centra en los beneficios económicos asociado al control topológico de la red de transmisión nacional. Para esto se propone un modelo de programación matemática que co-optimiza el despacho de generación con la topología del sistema (conocido en inglés como el problema de Transmission Switching) mediante una representación lineal entera mixto (MILP por su nombre en ingles de Mixed Integer Lineal Program). Además, se propone un algoritmo de solución mediante una técnica de descomposición que separa el sistema en una cantidad determinada de zonas, que se optimizan por separado y de forma iterativa.
La metodología propuesta se aplica en el sistema eléctrico chileno proyectado para el año 2025. El objetivo es analizar las mejoras producidas por los cambios topológicos en la operación del sistema, en especial en términos de costos, vertimiento de generación renovable (solar y eólico) y emisión de CO2. Para esto se comparan soluciones de dos corridas: con y sin control topológico (donde el resto de los parámetros y restricciones se mantienen sin alterar).
Los resultados de este trabajo demuestran que el control topológico presenta grandes ahorros en términos de costos (hasta un 7%) y en términos de vertimiento (hasta casi un 100%) para los ejemplos estudiados. Una conclusión de particular interés para operadores y reguladores es que varios tramos de transmisión local/subtransmisión (especialmente en la zona de la Región Metropolitana) podrían operar abiertos para algunas condiciones de operación con el fin de: (i) aumentar la transferencia de energía por el sistema nacional/troncal y (ii) permitir un despacho más económico de la generación hidráulica dentro de la Región Metropolitana.
|
6 |
Formulación de un Modelo de Programación Matemática para la Asignación de Horarios EscolaresBarco Gamarra, Roberto del January 2010 (has links)
No description available.
|
7 |
Formulación de un modelo de programación entera para asignación de turnos de trabajo. Caso: Gendarmería de ChileBorquez Aros, Georgi Mauricio January 2012 (has links)
Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / A partir del año 2005 luego del término a nivel nacional del proceso de implementación de la Reforma procesal penal se ha originado un mayor número de imputados y en consecuencia de condenados cumpliendo sus penas de privación de libertad dentro de los recintos penitenciarios del país. Esto genera una mayor demanda de personal de Gendarmería pues se deben hacer cargo de los recintos penitenciarios que albergan a imputados privados de libertad que están a la espera de condena. Lo anterior ha traído como consecuencia lógica una mayor sobrepoblación de los recintos penitenciarios nacionales, aumentando por consiguiente, la demanda del sistema penal.
En esta tesis se abordará el problema de la gestión de personal dentro de los recintos penitenciarios en las condiciones actuales del sistema. En ese sentido, se propone un modelo de programación entera para adecuar los tiempos de trabajo de las personas dentro de ellos.
El problema de generar un Scheduling (programación de turnos) será abordado con un método basado en programación entera, tomando en cuenta todas las restricciones propias que enfrenta actualmente Gendarmería (Demanda por cargos , Sistemas de franquía, Polivalencia del personal, Personal existente entre otras, las cuales serán propias al recinto penitenciario en estudio), para complementar el estudio y dado que las ausencias a lugares de trabajo son una variable importante al momento de hacer la programación se desarrolla la versión con incertidumbre del mismo, tomando las probabilidades de falla de personas a puestos de trabajo como otro factor importante para la programación, se construye un algoritmo iterativo el cual toma como entrada las demandas de personal por cargo y las probabilidades de falla y entrega como salida el recalculo de estas demandas, las cuales a su vez conforman una nueva entrada para el problema original sin incertidumbre. En ambos casos como salida se genera una programación de turnos por cada cargo a cubrir y la persona que debe realizarlo en un determinado momento en el horizonte de planificación de la programación.
El costo total de una programación corresponde a los costos de incumplir una franquía más el costo de no cumplir la demanda un día dado y el costo de sobre programar personas, es así como usando una simulación tipo MonteCarlo para una semana tipo en el penal Santiago I se aprecia que los costos de la programación determinista con respecto a la programación actual son un 96,9% en el caso de la programación con incertidumbre estos costos caen al 50% lo cuál muestra las potencialidades de este trabajo respecto a mejoras en el servicio.
Finalmente cabe mencionar que esta tesis fue desarrollada en conjunto con el departamento de estudios de Gendarmería de Chile y que todos los levantamientos de información mostrados a lo largo del trabajo corresponden a datos reales y actuales de la institución.
|
8 |
Programación Matemática en la Confección de Fixtures del Futbol ChilenoWolf Yadlin, Rodrigo Alberto January 2010 (has links)
El presente trabajo se centra en la confección del fixture de Primera A y del fixture de
Primera B del fútbol profesional chileno para su temporada 2009. También se analiza el
caso del fixture del Torneo de Apertura 2009 de Argentina. Por su parte, esta tesis tiene
por finalidad el ser un aporte en el área de sports scheduling, solucionando los problemas
antes mencionados en tiempos prudentes.
El modelo de programación entera que se desarrolla para Primera A posee 3272
restricciones y 6426 variables binarias. Un problema de estas características es muy difícil
de resolver. En tanto que el de Primera B es un poco más pequeño. Si se intenta dar solución
a estos problemas en un computador con 4 GB de memoria RAM y procesador Intel Core 2
Duo 2.20 GHz utilizando GAMS y como solver CPLEX 10.2 no hay solución tras más de 100
horas. La misma situación acontece para el problema del fixture de Argentina. Es por ello
que se hace necesario implementar una serie de técnicas y procedimientos que permitan
acelerar la obtención de resultados.
Los procedimientos implementados en esta tesis permiten obtener soluciones en
menos de 5 minutos para Primera A. En tanto que para el problema de Primera B por las
particularidades del sistema de torneo existen 3 posibles enfoques de solución. Con uno de
los enfoques es imposible obtener soluciones que satisfagan todas las restricciones, con
los otros enfoques aquello si es posible, tardándose una de las alternativas desde poco
más de 30 minutos a alrededor de 18 horas en arrojar soluciones y la otra obteniéndolas
en el orden de los 15 minutos.
Por último, el caso argentino se utiliza para validar las técnicas expuestas en este
trabajo. Y los resultados que se obtienen para este problema son bastante positivos, lo que
permite reafirmar la validez de lo que se expone en esta tesis.
|
9 |
Asignación de Flota Bajo Imprevistos en ItinerarioReus Heredia, Lorenzo Andrés January 2009 (has links)
No description available.
|
10 |
Modelo de Programación Matemática para Sustentar la Transición Rajo SubterráneaSolar Droguett, Andrés Alejandro January 2010 (has links)
No description available.
|
Page generated in 0.0775 seconds