Ingeniero Civil Matemático / El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.

Ingeniero Civil Matemático / El propósito de esta memoria es estudiar un modelo de aprendizaje en juegos repetidos. A diferencia de otros esquemas estudiados en la literatura, en este caso se estudia una situación en que los jugadores disponen de muy poca información, pudiendo observar solamente el pago recibido en cada etapa pero sin observar las estrategias usadas por los demá́s jugadores ni sus correspondientes pagos. En base a la información individual recolectada a medida que se desarrolla el juego, cada jugador genera una percepción del pago esperado de las distintas estrategias puras, y en base a estas percepciones adapta su comportamiento para las siguientes etapas del juego. En el capítulo 1 se presentan los modelos de las principales referencias bibliográficas, junto a los resultados mas relevantes que allí se obtienen. Se definen además las instancias y variantes a los modelos anteriores con las que se trabajará a lo largo de esta memoria. El capítulo 2 contiene todas las herramientas técnicas y conocimientos previos que fueron necesarias para desarrollar los resultados obtenidos. Se comienza con una sección de introducción a la topología diferencial, cuya principal referencia es el texto Topology from the differentiable viewpoint de Milnor, donde el resultado de mayor interés es el conocido Teorema de Poincaré-Hopf. En la siguiente sección se describen resultados referentes a martingalas, diferencias de martingalas y algunos teoremas de convergencia. La última sección está dedicada a estudiar los algoritmos de aproximación estocástica, basado en trabajos de las principales referencias en el tema, como Benaïm, Chen y Kushner. El capítulo 3 está dedicado a estudiar el proceso de aprendizaje propuesto, que consiste en una regla de actualización de las percepciones de los jugadores sobre su espacio de estrategias puras al enfrentarse a un juego repetido, los resultados asintóticos (cuando la iteración n tiende a ∞) guarda estrecha relación con una dinámica continua asociada, cuyos puntos estacionarios corresponden a los equilibrios de Nash de un juego potencial subyacente. Bajo la regla de decisión Logit y algunas condiciones sobre los parámetros del modelo, se obtienen interesantes resultados de convergencia casi segura y con probabilidad positiva a atractores de la dinámica continua. Finalmente en el capítulo 4 se estudia el modelo de Cominetti et al. [7], para unas instancias específicas (caso de 2 y 3 jugadores con 2 rutas) con el objetivo de contar a cantidad de equilibrios del sistema.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Cada semi-grupo tiene asociado un generador infinitesimal. Hille y Yosida descubrieron de manera independiente, alrededor de 1948, una condición necesaria y suficiente para saber cuándo un operador es el generador infinitesimal de un semi-grupo (de clase C0). Por otro lado, cada semi-grupo tiene asociado un potencial, concepto dual al de generador infinitesimal. Hunt, Meyer y Lion, entre otros, encontraron condiciones para saber cuándo un operador es el potencial de un semi-grupo. El problema propuesto para esta tesis es el siguiente : dado el núcleo de Green del movimiento browniano en un dominio, ¿ qué potencias de este núcleo y sobre qué clase de dominios generan un potencial de semi-grupo ? La idea central para resolver este problema es la aproximación del núcleo por procesos discretos, usar resultados conocidos para matrices y extender estos resultados al caso continuo. Para que funcione la aproximación, es necesario restringir la clase de conjuntos considerados, tratando de quedar lo más general posible. En esta tesis damos respuesta para el caso de los abiertos acotados regulares. Los conjuntos regulares son, simplificando, los conjuntos adecuados de la teoría del potencial. Si se debe resumir la memoria en una palabra seria «aproximación», se trata de reducir el problema a un caso conocido y se busca como extenderlo. / Este trabajo ha sido parcialmente financiado por el CMM Center for Mathematical Modeling

El principal objetivo de estudio de esta tesis son los mecanismos eficaces y eficientes para computar respuestas en formalismos de argumentación estructurada probabilística, en particular, en el modelo DeLP3E. Dicho formalismo nos permite modelar y razonar sobre información inconsistente, incompleta, y asociada a eventos probabilísticos. En particular, el objetivo es estudiar y proponer mecanismos que nos permitan aproximar las respuestas por medio de algoritmos que se basen en toda la información disponible de cada componente del modelo. Nos enfocamos en investigar este aspecto dado que, dar una respuesta exacta a una consulta en DeLP3E no es aplicable en un tiempo razonable para instancias grandes. La principal contribución de esta tesis es la definición y estudio de algoritmos, junto con una guía para seleccionar cuál de ellos aplicar, que nos permitan aproximar el valor de una respuesta en base a toda la información disponible en el modelo DeLP3E. A su vez, y con la finalidad de poder evaluar el desempeño no de los algoritmos propuestos, otra importante contribución de esta tesis son tres generadores para crear modelos DeLP3E. Cada uno de estos generadores nos permite crear diferentes escenarios de complejidad de manera automática, y teniendo como principal característica que los valores de sus métricas son ajustables en base al valor de los parámetros de entrada que guían el proceso de generación. A su vez, y para mostrar un caso de uso de lo desarrollado en esta tesis, se presenta P-DAQAP, una plataforma web que facilita el análisis de los proceso llevados a cabo en el modelo DeLP3E y en la Programación Lógica Rebatible (DeLP, en inglés). Se mostró, a través de casos de uso y ejemplos prácticos, que una herramienta de este tipo puede ser de gran utilidad para usuarios que requieran analizar dominios complejos y que tengan eventos probabilísticos asociados. Además de esa utilidad en entornos reales, también puede ser usada con fines educativos, ya que ofrece un conjunto de herramientas gráficas para facilitar la lectura y entendimiento de los procesos argumentales llevados a cabo en el formalismo DeLP. P-DAQAP es una herramienta pública que consideramos de gran utilidad para la comunidad de argumentación estructurada. / The main objective of this thesis is the study of the effective and efficient mechanisms to compute answers in formalisms of probabilistic structured argumentation, in particular, in the DeLP3E model. This formalism allows us to model and reason on inconsistent and incomplete information, as well information associated with probabilistic events. In particular, the objective is to study and propose mechanisms that allow us to approximate the answers by algorithms that are based on all the available information of each component of the model. We focused on investigating this aspect since giving an exact answer to a query in DeLP3E is not applicable in a reasonable time for large instances. The main contribution of this thesis is the definition and study of algorithms, and a guide to select which of them to apply, which allow us to approximate the value of a response based on all the information available in the model DeLP3E. Also, and in order to be able to evaluate the performance of the proposed algorithms, another important contribution of this thesis is three generators to create DeLP3E models. Each of these generators allows us to create different complexity scenarios automatically, and having as main characteristic that the values of their metrics are adjustable based on the value ofthe input parameters that guide the generation process. Also, and to show a use case of what has been developed in this thesis, P-DAQAP is presented, a web platform that facilitates the analysis of the processes carried out in the DeLP3E model and in Defeasible Logic Programming (DeLP). It was shown, through use cases and practical examples, that a tool of this type can be very useful for users who need to analyze complex domains and have associated probabilistic events. In addition to this utility in real environments, it can also be used for educational purposes, since it offers a set of graphic tools to facilitate the reading and understanding of the argumentative processes carried out in the DeLP formalism. P-DAQAP is a public tool that we consider very useful for the structured argumentation community.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Hace algunas décadas ha nacido dentro de la investigación de operaciones la subdisciplina denominada sports scheduling, la cual se propone abordar los problemas y desafíos que se presentan en el diseño de torneos deportivos. Esta tesis pretende ser una contribución al área de sports scheduling dentro del contexto del fútbol profesional chileno. Su objetivo es modelar de modo conjunto los dos principales torneos del fútbol profesional chileno, la Primera A y la Primera B, utilizando instancias basadas en la temporada 2015-2016. Debido a la complejidad del modelo, que es consecuencia de la enorme cantidad de restricciones y de variables que contiene, una resolución directa por medio de un solver estándar actual no entrega resultados en tiempos razonables. Por ello, es necesario desarrollar una estrategia que permita disminuir los tiempos de resolución. Esta estrategia está basada en el empleo de patrones asociados a equipos, los cuales establecen sus secuencias de localías y visitas. La estrategia desarrollada consiste en una metodología secuencial que comienza con la obtención de patrones por medio de un modelo generador que considera las restricciones básicas del problema, entre las cuales se encuentran aquellas que fijan localías y visitas de antemano. Posteriormente, los patrones obtenidos son asociados a los equipos en el modelo principal, con lo cual se asegura que al comienzo de su resolución las restricciones básicas estén satisfechas. Luego, se intenta incluir la mayor cantidad de las restricciones faltantes dejando fijos todos los patrones. Para aquellas restricciones que no se haya podido incluir, se puede relajar de 2 a 4 patrones hasta que se encuentre un nuevo conjunto de patrones factibles. Los resultados obtenidos al aplicar la estrategia descrita son satisfactorios. La mayor parte de las restricciones se incluye fijando los patrones obtenidos por el modelo generador de patrones, mientras que la relajación de algunos de ellos permite agregar las restantes. Los tiempos de resolución son razonables, pues el mayor de ellos, correspondiente al del modelo que considera todas las condiciones impuestas sobre la temporada 2015-2016, es menor a media hora.

No description available.

En este trabajo se analizó la factibilidad de alcanzar los límites de descarga de efluentes impuestos por el DSN°90/200, a través, de la evaluación de alternativas de remoción biológica de nutrientes que permitan cumplir con los requerimientos de calidad y/o conlleven optimizar el funcionamiento de los sistemas de tratamiento de aguas servidas.

Doctor en Sistemas de Ingeniería / En este trabajo se estudia la calidad que ofrecen las soluciones óptimas locales para problemas de programación de tareas en máquinas en paralelo. Los ambientes considerados son máquinas idénticas, idénticas restringidas, uniformes restringidas y no-relacionadas. El objetivo considerado es la minimización del tiempo ponderado de completación. Para estudiar la calidad de los óptimos locales se determinan los factores de aproximación para las soluciones localmente óptimas de los vecindarios de inserción (jump) e intercambio (swap). Los resultados indican que para los ambientes de máquinas paralelas uniformes y no-relacionadas, el costo de cualquier óptimo local se encuentra alejado a lo más en un factor 2,618 con respecto al costo del óptimo. Si solo se considera la minimización del tiempo de completación, se tiene que el factor es 2. El mismo resultado se obtuvo para el ambiente de máquinas uniformes con tareas unitarias, para los casos ponderado y no ponderado. Por otra parte, para el problema de máquinas paralelas idénticas restringidas, se determinó que el factor de aproximación se encuentra entre 1,75 y 1,809. Para el caso no ponderado este factor se encuentra entre 1,5333 y 1,618. Para el caso de tareas unitarias, donde el objetivo es la minimización del tiempo ponderado de completación, se determinó que el factor de aproximación se encuentra entre 1,5333 y 1,618. Mientras que para el caso no ponderado se tienen evidencias que indican que el factor de aproximación es 1,5333. / Este trabajo ha sido parcialmente financiado por Universidad del Bío-Bío; Conicyt, Programa de Formación de Capital Humano Avanzado; Núcleo Milenio Información y Coordinación en Redes

No description available.

En muchas situaciones reales se trata de utilizar determinados recursos en una cantidad limitada pero de la mejor manera, es decir que su uso cause el mayor provecho. La programación lineal estudia la optimización de una función lineal que satisface un conjunto de restricciones lineales de igualdad o desigualdad. La programación lineal es un modelo matemático que fue planteado por primera vez por George B. Dantzing en1947 cuando era consejero matemático de la fuerza aérea de los Estados Unidos. Sabemos además que en1939 Leonid V. Kantorovich ya había planteado y resuelto problemas de este tipo. En aplicaciones de la optimización a la economía, teoría de control, problemas inversos etc, surgen problemas donde la función objetivo no siempre es diferenciable o casos en los cuales el problema no está bien puesto. Para resolver problemas como estos se utilizan técnicas en el contexto del análisis convexo, como los métodos de regularización para funciones convexas así como los métodos de punto proximal y lagrangeano aumentado ente otros. Recientemente, en el año 2009, los profesores Bauschke, Lucet y Triens propusieron la media proximal, una novedosa técnica que tiene la propiedad de ser autodual respecto a la conjugada de Fenchel, que puede trabajar incluso con funciones de dominio disjunto, veremos que esta técnica puede ser aprovechada para manipular la envoltura de Goebel y probar su autodualidad respecto a la conjugada de Fenchel, además de tratar la optimización de varias funciones objetivo en el caso convexo o inclusive en el caso de ciertas funciones no necesariamente convexas aun cuando los dominios de estas funciones sean disjuntos. / Tesis