Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En el presente trabajo se estudia el problema de envasado y embotellado de pedidos en líneas de producción. El problema es de tipo scheduling con características propias. La resolución del problema se aborda desde dos ángulos. El primer enfoque consiste en plantear un problema de programación lineal mixto satisfaciendo las restricciones operacionales del sistema. Los resultados de esta primera estrategia satisfacen los requerimientos técnicos, sin embargo, los altos tiempos computacionales impiden su utilización para casos reales. El segundo enfoque consiste en la utilización de un Algoritmo Glotón Usando Constraint Programming (AGUCP) más una estrategia de mejoramiento de la solución. AGUCP permite encontrar una solución factible al problema planteado en el modelo de programación lineal mixto con una calidad aceptable. En este caso, los tiempos computacionales son excelentes incluso para casos de gran tamaño. Sin embargo existe un porcentaje de entre el 15% y el 20% de los casos estudiados en los cuales el algoritmo no encuentra solución. Se presenta además una mejora a la heurística AGUCP, la cual se denomina AGUCP++ y consiste básicamente en una implementación propia de AGUCP adaptando el modelo para enfocarse directamente en las variables de decisión de modo de insertarse mejor al espíritu del Constraint Programming. La implementación de este algoritmo fue hecha en Python. Las principales mejoras de este nuevo algoritmo son: (i) Se trabaja con una menor cantidad de variables debido al modo de guardar la información. (ii) El algoritmo entrega una solución, a pesar que, haya uno o más trabajos que no pudieron incorporarse. (iii) Se disminuye la cantidad de casos en los cuales no todos los trabajos son agendados a un 5 %. Esto depende esencialmente de cuan exigentes sea el caso de estudio. (iv) Los tiempos computacionales disminuyen en un 70% en comparación con AGUCP Finalmente, se incorpora una técnica de mejoramiento de la solución obtenida a través de AGUCP++, utilizando una estrategia basada en la técnica llamada Local Search. Estas búsquedas locales operan optimizando sobre un número acotado de trabajos -a partir de una solución inicial-, dejando fijos los demás. Esta estrategia permite, en poco tiempo, obtener mejoras sustantivas de la solución. Según los experimentos realizados, el porcentaje de mejora varía entre un 5% y un 28%.

Ingeniero Civil Matemático / El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N candidatos a un puesto de secretaria para maximizar la probabilidad de contratar al mejor de ellos, bajo el supuesto que las entrevistas se realizan en orden aleatorio y que las decisiones tomadas: rechazar o aceptar, son irrevocables. Esto permite modelar directamente la versión discreta del problema. También se puede considerar una versión contínua con una infinidad de candidatos, suponiendo que los instantes de entrevista son tiempos aleatorios uniformes sobre el intervalo [0,1]. Este problema y sus variantes tienen muchas aplicaciones. Esta memoria se enfoca en el estudio de la variante llamada Problema de la Secretaria con Restricciones de Tiempo (TCSP). En la formulación discreta del (TCSP) se rechazan k candidatos y luego se quiere contratar al mejor de los N−k que quedan, mientras que en su formulación contínua se rechazan todos los candidatos entrevistados antes de un tiempo T y luego se quiere contratar al mejor de los candidatos entrevistados después del tiempo T. En ambos casos los candidatos rechazados al principio forman un sampleo, y se puede utilizar la información acumulada en este sampleo inicial para mejorar la toma de decisión durante la fase de aceptación que sigue. Después de familiarizarse con esta variante, se demuestran propiedades que cumple la regla óptima que resuelve el (TCSP) discreto. Basándose en esto, se estudia la siguiente estrategia para el caso contínuo. Se selecciona una sucesión creciente de constantes absolutas {T_i} en [0,1] o tiempos barreras, independientes del tiempo T del sampleo. El proceso de selección se realiza del siguiente modo: sólo se acepta un candidato entrevistado entre los tiempos T_i y T_{i+1} si es mejor que todos los ya entrevistado después del tiempo T y mejor que el i-ésimo mejor del sampleo inicial. Se encuentran fórmulas explícitas para calcular dichas barreras. La regla óptima para resolver el (TCSP) discreto tiene una forma similar, donde en vez de tiempos barreras, se usan candidatos barreras. Se comprueba que a medida que N tiende a infinito, las razones entre la posición del candidato barrera i-ésimo y el número de candidatos tienden al valor encontrado para los tiempos barreras en el caso contínuo. Finalmente, se estudia una variante del (TCSP) en la cual el empleador sólo puede recordar un candidato del periodo del sampleo (no necesariamente el mejor) y al mejor candidato entrevistado luego del sampleo. Se deduce en el caso discreto la forma de la regla óptima en la situación donde el algoritmo guarda el i-ésimo mejor candidato de la zona sampleada. Esta regla interpretada en el caso contínuo consiste en: rechazar a todos los candidatos hasta un tiempo T_1 > T, luego aceptar un candidato entrevistado entre los tiempos T_1 y T_0 > T_1 si es mejor que ambos miembros en memoria, y luego si no se aceptó a nadie, aceptar a un candidato entrevistado después del tiempo T_0 solamente si es mejor que el mejor entrevistado después del tiempo T. Se encuentran fórmulas explícitas para las barreras T_1 y T_0 como función de T y del rango i del candidato del sampleo guardado en memoria.

Magíster en Ingeniería de Negocios con Tecnología de Información / La selección de nuevos negocios en UNIRED, es una de las actividades claves al momento de elegir proyectos de negocios que como premisa buscan la rentabilidad de la inversión realizada. De manera que mediante la ejecución de estos proyectos se cumplan con los objetivos de crecimiento de transacciones y posicionamiento de la marca. En la actualidad este proceso si bien existe informalmente, ya que es difícil determinar su estructura, mediante el rediseño del proceso de generación y selección de nuevos negocios, se pretende estructurar y agregar valor mediante la generación de ideas de negocios basadas en la innovación y su selección basada en métodos de selección de multicriterios y maximizando el retorno de la inversión con la restricción de un presupuesto finito disponible para la ejecución de toda la cartera de proyectos seleccionados. Para lograr lo descrito en el párrafo anterior, se formalizan los procesos de generación y selección de nuevos negocios, donde en la selección se aplican en forma secuencial la elección de ideas de negocios sometidas a la metodología de selección multicriterios AHP (Analytic Hierarchy Process), de la cual se obtienen las calificaciones para cada nuevo negocio evaluado por un comité integrados por distintas personas de UNIRED y luego se utiliza el problema de optimización de Knapsack, pero aplicado a la selección final de los nuevos negocios que deben ser ejecutados. De esta forma se obtienen los mejores proyectos para ser ejecutados sujeto a la restricción de presupuesto de inversión y maximizando las calificaciones entregadas por el comité. Se realizó una prueba de concepto sobre la selección de nuevos negocios, donde se calificaron seis proyectos reales, bajo la metodología planteada en el trabajo de tesis. Se logra mostrar que con la aplicación de este trabajo, UNIRED quedaría con la nueva capacidad de seleccionar de mejor manera su cartera de proyectos de nuevos negocios y que aporta beneficios concretos (en la prueba conceptual, el aporte fue de un 2%, del total del presupuesto de inversión para el año 2013). Adicionalmente se identifican potencialidades asociadas al rediseño de procesos en lo que respecta a diseño, construcción y puesta en producción de proyectos y mejoras en el control de los nuevos negocios a implementar y la asignación de recursos sensibles. Si bien la solución no fue implementada, se realizó su evaluación técnica económica que considera la construcción de la solución tecnológica. Los datos de la evaluación utilizados son a un horizonte de cinco años, con una tasa de descuento de 10%, la cual entrega un VPN de $ 42.6 millones.

Ingeniero Civil Matemático / En la presente memoria se estudia la propiedad de regularidad asintótica para una variante de la iteración de \textit{Krasnoselskii-Mann} en un espacio de Banach general. Este problema está enmarcado en la teoría métrica de puntos fijos de operadores no expansivos, pues resulta ser que, bajo ciertas hipótesis, la sucesión de iterados de Krasnoselskii-Mann converge a un punto dijo de cierto operador $T$.\\ La regularidad asintótica de la iteración de Krasnoselskii-Mann ha sido ampliamente estudiada por muchos autores, ya que sirve para aproximar puntos fijos de un operador no expansivo $T:C\to C$ definido sobre un conjunto no vacío, convexo, cerrado y acotado en un espacio de Banach. Se ha establecido la regularidad asintótica de los iterados de Krasnosleskii-Mann en un espacio de Banach bajo condiciones simples, y además se conoce la tasa de regularidad asintótica en un espacio de Banach general. En esta memoria se prueba la regularidad asintótica de la iteración $$x_{k+1}=(1-\alpha_{k+1})x_k+\alpha_{k+1}(Tx_k+e_{k+1}),$$ donde $x_0\in C$, $(\alpha_k)_{k\in\N}\subseteq[0,1]$, $e_n\to 0$, $\sum\alpha_k(1-\alpha_k)=\infty$ y $\sum\alpha_k\|e_k\|<\infty$. Además, se establece la tasa de convergencia de $\|x_n-Tx_n\|$ cuando los coeficientes $(\alpha_k)_{k\in\N}$ están lo suficientemente alejados de $0$ y $1$. Por último, se aplican los resultados obtenidos en esta tesis para estudiar la regularidad asintótica de otros procesos iterativos y para estudiar cotas de la solución de una ecuación de evolución no lineal. / Este trabajo ha sido parcialmente financiado por el proyecto Fondecyt 1130564

Magister en Gestión de Operaciones / Ingeniero Civil Industrial / La importancia que ha tomado la conservación del medioambiente ha ido en aumento, lo que ha afectado directamente en los objetivos y forma de operar de las organizaciones. Es por esto que la interacción entre la operación y el desarrollo del ecosistema debe ser considerada para balancear la sustentabilidad y conservación con los objetivos productivos, siendo las perturbaciones forestales un punto de gran interés. Incendios, plagas, erupciones volcánicas e inundaciones son algunas de las perturbaciones al ecosistema que afectan la productividad del bosque. Por lo tanto, reducir el riesgo y las consecuencias de estos episodios es clave para la industria. El objetivo es crear una metodología que permita generar escenarios de incendios elipsoidales para su utilización en la toma de decisiones en el manejo de incendios y recursos forestales. Para esto se utilizan incendios elípticos generados a través de un simulador, los cuales, siguiendo el método de Monte Carlo, son asignados a uno de los patrones representativos de incendio previamente definidos, utilizando la distancia de Pompeiu-Hasudorff. La probabilidad de ocurrencia de los patrones representativos es obtenida al dar cuenta de la cantidad de simulaciones asignada a cada uno de ellos. Para dar con un algoritmo que permitiera utilizar los recursos computacionales de forma eficiente se implementaron distintos métodos para el cálculo de la distancia de Pompeiu-Hausdorff, además de utilizar múltiples procesadores en paralelo cuando esto fuese posible. Cinco métodos fueron implementados, los cuales son definidos utilizando las propiedades geométricas de las elipses para lograr resolver el problema de optimización implícito. El método que logra dar con los resultados más exactos para la distancia hace uso de optimización cónica, mientras que el más rápido calcula la distancia entre cada uno de los vértices de una elipse discretizada. Haciendo uso de estos dos métodos, se genera una estrategia multi etapa para el cálculo de la distancia de Pompeiu-Hasdorff entre dos elipses que es eficiente y precisa. La estabilidad de los resultados obtenidos para 200 patrones es lograda luego de 100,000 sampleos, sin embargo, se observaron variaciones muy pequeñas incluso después de 20,000 simulaciones. En conclusión, los intervalos de confianza obtenidos para las probabilidades calculadas dependen de los recursos computacionales con los que se cuente y de las restricciones de tiempo que puedan ser impuestas. La metodología desarrollada entrega a los planificadores forestales una herramienta para analizar la probabilidad de incendio de zonas determinadas, las cuales pueden ser utilizadas en un modelo de optimización bajo incertidumbre que les permita manejar los recursos disponibles de la mejor forma posible.

Los cambios de régimen en la economía afectan el comportamiento de los activos financieros y suponen retos para los procesos de asignación de activos. Como varios autores han señalado, el Modelo de Optimización de Media-Varianza de Markowitz, ampliamente utilizado desde su publicación en la década de los 50s, presentaba ciertas limitaciones que no fueron consideradas en sus etapas iniciales de desarrollo. En la práctica estas limitaciones se evidenciaron ante la ocurrencia de cambios abruptos en los mercados financieros. En particular, esto sucedió durante la crisis financiera del 2007-2008, siendo los más vulnerables aquellos inversionistas que habían reducido significativamente su exposición a la liquidez para invertir en activos riesgosos. La poca liquidez del mercado impidió a los inversionistas vender sus posiciones riesgosas u obtener coberturas a _n de evitar las caídas pronunciadas de los activos. Este tipo de eventos extremos o riesgos de cola, puso en discusión los límites de la diversificación dada la naturaleza cambiante de los activos financieros y las limitaciones de una estrategia de inversión estática. Más aún, puso en relieve la gran influencia que puede tener el entorno macroeconómico sobre los mercados financieros y su desenvolvimiento de largo plazo. En ese sentido, desarrollos recientes plantean un proceso de optimización dinámico, que se adecúe a la naturaleza cambiante de los activos financieros y que permita incorporar las influencias macroeconómicas en los distintos regímenes. El presente trabajo tiene tres objetivos. En primer lugar, presentar la construcción y formalización matemática del Problema Intertemporal de Asignación de Activos de un inversionista que rebalancea su portafolio de manera dinámica. En segundo lugar, presentar el marco metodológico de un Proceso Oculto de Markov Discreto basado en regímenes cambiantes. El Proceso Oculto de Markov será utilizado para determinar los estados de la naturaleza en base a dos variables macroeconómicas: la tasa de crecimiento del PBI y la tasa de inflación. En tercer lugar, realizar un ejercicio de aplicación enlazando la metodología del Proceso Oculto de Markov Discreto con el Problema de Asignación de Activos del inversionista. Es decir, se incorporará al proceso de optimización de portafolios, los regímenes previamente determinados mediante el Proceso Oculto de Markov. De esta manera, la estimación de las ponderaciones óptimas de los activos financieros dependerá del estado de la naturaleza prevaleciente en cada momento del tiempo. El objetivo último será encontrar una estrategia de asignación de activos que permita ajustar dinámicamente las ponderaciones de los activos financieros de acuerdo a los regímenes determinados por las variables macroeconómicas. Los resultados del ejercicio de aplicación muestran que, en comparación a otras estrategias de inversión estáticas, la estrategia dinámica propuesta genera un mayor retorno ajustado por riesgo (mayor ratio Sharpe); ofrece mayor protección ante caídas abruptas en los mercados financieros, que suelen ocurrir en periodos de estrés; presenta un mayor retorno promedio al final del periodo de análisis y baja volatilidad, y muestra comportamientos más estables a lo largo del tiempo. / Tesis

El problema clásico de optimización de portafolio, en el que un agente escoge sus estrategias de modo de maximizar su utilidad esperada ha sido estudiado en profundidad por mucho tiempo. Sin embargo sólo hace poco ha surgido el interés por plasmar el hecho de que la selección de un modelo particular al momento de hacer la toma de decisiones es en sí riesgosa. Se conoce como optimización robusta de portafolio al problema de maximización de utilidades que un agente considera cuando toma en cuenta la incerteza sobre los modelos. El tema principal de esta memoria es estudiar el problema anterior cuando el conjunto de incerteza sobre los modelos no es compacto o cuando este se manifiesta a partir de restricciones lineales. Ninguno de estos escenarios para el problema de optimización robusta ha sido afrontado en generalidad en la literatura. Cuando el conjunto de modelos está delimitado mediante restricciones lineales, en este trabajo se resuelve inicialmente el problema tanto para mercados completos como incompletos mediante la técnica de minimización de funcionales de entropía desarrollada entre otros por C. Léonard, suponiendo la condición de compacidad débil sobre el conjunto de modelos usual en la literatura. Seguidamente, se resuelve el problema robusto en un mercado completo sólo bajo una cierta suposición de cerradura débil en un espacio de Orlicz conveniente, para lo cual se requieren además algunas condiciones sobre los ingredientes económicos del problema. En este punto se rescatan los resultados en presencia de compacidad débil entre otros por A.Schied y H. Föllmer. Con esto, se vuelven a aplicar los métodos de C. Léonard para el caso lineal pero sin compacidad, obteniéndose entre otros nuevos resultados una igualdad primal-dual para el problema de optimización robusta y una caracterización para la medida (o modelo) menos favorable. Se presenta además un ejemplo simple que escapa a la teoría desarrollada con anterioridad, pero que es abordable mediante los resultados obtenidos en esta memoria. Finalmente, se explora la relación entre la optimización robusta y el concepto de información débil introducido por F. Baudoin así como el de flujos de información. Con respecto a la información débil, se establece cómo la maximización de utilidades en presencia de esta más el cálculo de variaciones permiten resolver ciertos problemas robustos. En cuanto a los flujos de información, se propone y discute una manera de emplear la teoría desarrollada por C. Léonard respecto al problema de minimización de la entropía bajo restricciones sobre el flujo de marginales, para resolver el problema robusto asociado.

El objetivo de la presente memoria es proponer un nuevo método para resolver una clase general de problemas de optimización, a saber, dado un conjunto convexo y abierto , una función diferenciable , una matriz de rango completo (con ) y un vector , buscamos resolver algorítmicamente el problema: (P0) min{ f(x) : x ∈ clC, Ax = b}. Para esto, tomamos herramientas de la Geometría Riemanniana, las mezclamos con el método de máximo descenso y nos preguntamos qué sucede si miramos este algoritmo bajo la lupa de otra métrica, una no necesariamente Euclideana. Si bien la idea de usar métricas variables para resolver este tipo de problemas no es nueva, nuestro trabajo sí lo es, pues nos interesamos en una en particular, una que es inducida por el cuadrado de la matriz Hessiana de una cierta función barrera cuyo dominio coincide con . Esta métrica tiene la gran gracia de proveernos de una isometría, fácil de calcular, entre el conjunto , visto como variedad, y un espacio Euclideano apropiado. En el capítulo 1 de esta memoria damos una descripción introductoria de las herramientas de la Geometría Riemanniana que usamos para desarrollar nuestra teoría. En el capítulo 2 definimos formalmente la Métrica Hessiana Cuadrada de Legendre sobre un dominio convexo. Estudiamos también sus principales propiedades y consecuencias. En el capítulo 3 introducimos un nuevo método de optimización para resolver de forma algorítmica un problema más simple que el de minimizar la función sólo sobre la adherencia del conjunto . También introducimos una nueva noción de dualidad y presentamos algunos teoremas de convergencia. En el capítulo 4 generalizamos este método, con el fin de resolver algorítmicamente el problema . Por otra parte, en el capítulo 5 abordamos la pregunta de en qué casos nuestra métrica coincide con la inducida por la Hessiana de otra función barrera. Primeramente, planteamos el problema para el caso separable, obteniendo condiciones necesarias y suficientes, para luego pasar a un caso más general, donde sólo obtuvimos una condición necesaria. Finalmente, usando este criterio mostramos que el problema es en realidad muy restrictivo respecto al conjunto , lo cual nos hace conjeturar que esta pregunta no es fácil de responder y que la respuesta es en general negativa. Cabe destacar que la noción de dualidad que aquí introducimos crea un lazo entre las propiedades de carácter Riemanniano y las de carácter Euclideano, en particular, permite transformar problemas no convexos en otros que sí lo son. Más aún, esta noción nos muestra que es posible resolver ciertos problemas de optimización con restricciones aplicando métodos de optimización irrestricta sobre un problema dual adecuado.

El presente trabajo de título tiene como objetivo diseñar una metodología que permita obtener una asignación de turnos óptima para los cajeros de una empresa contratista de personal, determinando la dotación de individuos para cada uno de los contratos preestablecidos. Actualmente este proceso se realiza de forma manual, lo que se traduce en pérdidas de tiempo para los encargados y pérdidas de recursos para la organización. Además, debido a que existen más de 27.000 posibles combinaciones de turnos, las soluciones encontradas no logran satisfacer los requerimientos de personal exigidos. La metodología utilizada para resolver el problema, considera el desarrollo de un modelo de programación lineal entera, que busca minimizar los costos de remuneraciones maximizando el nivel de servicio entregado. Este último se calcula como la cantidad de horas requeridas de trabajo que no fueron satisfechas durante el mes. También se diseña un modelo que permite estimar las ausencias inesperadas al trabajo, basado en información histórica de la empresa y asumiendo que estas siguen una distribución Weibull. Por último, se plantean modificaciones al modelo inicial propuesto permitiendo que los trabajadores se cambien de estación durante el día, lo que busca encontrar sinergias en la utilización de recursos humanos. Para obtener soluciones factibles, se incorporan las restricciones laborales establecidas por el Código del Trabajo, las restricciones contractuales y el cumplimiento mínimo del requerimiento de personal exigido para cada estación. En el análisis se abordó el caso de dos estaciones, Pajaritos Oriente y San Pablo. Luego de aplicar el modelo, para la primera se obtuvo una reducción del 8,4% de los costos actuales, considerando un aumento de 97,6% a un 99,8%en el nivel de servicio y por ende una asignación que se ajusta de mejor forma a la demanda. Para la estación San Pablo se consiguió disminuir los costos totales en un 7,4% manteniendo el mismo nivel de cumplimiento de demanda que se tiene actualmente. En ambos casos la disminución de costos se debe a un cambio en la proporción de trabajadores Full-Time y Part-Time, lo que resulta en beneficios anuales de MM$ 2,88 para la estación Pajaritos Oriente y de MM$ 4,56 para la estación San Pablo. Considerando que la empresa contratista opera treinta y cuatro estaciones, se realiza una estimación del ahorro total anual esperado, cuyo monto asciende a $ 76 millones. Como trabajos futuros se propone desarrollar un modelo que permita cambios de cajeros entre todas las estaciones operadas por la empresa, considerando la compatibilidad de estas en términos de requerimiento de personal y los costos asociados a tiempos de viaje. Dada la magnitud de variables de este problema, sería necesario implementar métodos heurísticos que permitan obtener soluciones factibles en tiempos razonables.

Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En general, un problema de decisión min f(x) s.a. x en F0 está sometido a una gran cantidad de factores que pueden provocar incertidumbre respecto a la delidad de los valores de los datos que de finen F0, causando que la respuesta de este no sea del todo con fiable. Existen diversos métodos para hacerse cargo de la incerteza en los datos, como el Análisis de Escenarios, la Optimización Estocástica y la Simulación, entre otras. Si el decidor es adverso al riesgo, por ejemplo en situaciones donde las decisiones son poco frecuentes o bien las consecuencias de una mala decisión ponen en riesgo la vida de personas, la Optimización Robusta, es la estrategia que le permite ser en extremo conservador, buscando soluciones óptimas que sean factibles bajo cualquier escenario posible de datos. Lamentablemente un algoritmo robusto puede consumir vastos recursos computacionales. Resulta interesante ser capaz de predecir cuánto se arriesga (en términos de la función objetivo), al utilizar una solución económica que ignora la incertidumbre en vez de una costosa solución robusta, o dicho de otra forma, cuánto cuesta una solución conservadora en relación al problema con datos estimados (fácil de resolver). Es posible acotar este valor , en términos de la sensibilidad estructural del problema, una característica intrínseca de la modelación, y el nivel de incertiza que al que estan sometidos los datos, de la siguiente forma: D <= (2/k+1) (max f(x) - min f(x)) Donde k es una medida llamada Margen de Factibilidad propuesta por Ben-Tal y Nemirovski, en situaciones donde la variabilidad de los datos puede ser modelada a través de un conjunto de incerteza U poliedral. Ellos presentan una cota superior para D y en este trabajo se construye un modelo linearizado para computar una estimación simpli cada de esta cota para problemas lineales con incertidumbre en la matriz de restricciones de desigualdad, descrita a través de un conjunto poliedral. Se aplicó este modelo a 16 problemas de la librería NETLib, asumiendo perturbaciones independientes de los parámetros considerados como inciertos. La estimación implementada consiguió buenas cotas ajustadas: Para un nivel de incerteza del 1% las cotas fueron, salvo por dos ocasiones, a lo más 6 veces el valor a estimar y en general el error de la estimación no supero el 8% del valor óptimo nominal. En estos problemas se pudo observar que el error en la cota estimada es proporcional al nivel de incerteza, de comprobarse esta idea, se presentaría una ventaja signi cativa al momento de estudiar el impacto sobre problemas con nivel de incerteza desconocido.