Modelos de programación lineal.

Modelos de programación lineal.

Se presenta una variante del método de punto interior (MAE) para resolver un programa matemático lineal. Describe el método de escalado afín, relevando su aspecto geométrico y presentando aplicaciones. Compara la eficiencia de este método con la del método simplex. / Tesis

En el presente trabajo de tesis se realiza un Análisis Situacional a la Empresa Grupo Digigraf S.A., haciendo uso de la metodología del Enfoque Sistémico o Enfoque de Sistemas. El análisis Situacional nos brinda información que sirve de guía para enfocar la realidad de la Empresa. Luego de realizar un análisis minucioso de todos los subsistemas de la institución, se determina que la Empresa cuenta con un serio problema de baja rentabilidad económica que debe resolver; continuando con el Análisis de los procesos internos, se logra identificar que la causa principal que genera este problema es el mal procedimiento que utiliza la empresa para realizar los cortes de rollos de película que se utilizan como insumo principal en el proceso de producción. Para resolver el problema se utiliza la Programación Lineal que permite construir un Modelo Matemático que describe el problema y para cuya solución utilizamos el Método Simplex que permite obtener la solución optima que permitirá solucionar el problema y por ende mejorar la situación de la Empresa. Finalmente, se propone este modelo de solución el cual remplazará la metodología actual que realiza la empresa, y se recomienda su pronta implementación, para poder favorecer el mejoramiento de la Empresa. / --- In this Thesis work is carried out a Situational Analysis to the Grupo Digigraf S.A. Enterprise, using the Systems Approach Methodology or Systemic Approach. The Situation Analysis provides us with information that guides us to set focus in the reality of the Company. After to make a thorough analysis of all company subsystems, is determined that the company has a serious problem of low profitability economic to be solved; continuing with the analysis of internal processes, is possible to detect that the main cause that generates this problem is the wrong method using by the company to make cuts rolls of film used as the main input in the production process. To solve the problem is used the Linear Programming that permit build a mathematical model that describe the problem and to solve it we used the Simplex Method for obtain the optimal Solution that will resolve the problem and therefore improve the Company Situation. Finally, is proposed this model of solution which will replace the current methodology is performed in the company, and is recommended for early implementation, in order to promote the improvement of the Company. / Tesis

El objetivo de la presente investigación es mejorar la asignación de ternas arbitrales para los encuentros del Torneo Descentralizado del Fútbol Peruano mediante la implementación de un modelo matemático de Programación Lineal Entera Mixta. En el marco teórico se describen investigaciones similares realizadas para resolver problemas relacionas al fútbol haciendo uso de herramientas matemáticas. Además, se explica la importancia y aplicación de la Programación Deportiva en el fútbol. Por último, se exponen los conceptos de Investigación Operativa que son usados en la presente investigación. En el diagnóstico del problema se detalla el contexto en el cual se encuentra el problema objeto de estudio. Además, en la definición de los requerimientos se expone la información básica para la elaboración del modelo como condiciones iniciales, información de equipos participantes, ternas arbitrales y categoría de los mismos. Para el desarrollo del modelo se definen las entradas y salidas, así como los supuestos a considerar. También se definen las partes que conforman el modelo como variables, restricciones y función objetivo. Luego, en la resolución del modelo se definen los parámetros, se presenta el modelo aplicado al fútbol peruano que será resuelto, y los resultados del mismo. Asimismo, en la validación del modelo se realizan diferentes análisis donde se exponen las mejoras de la asignación propuesta frente la actual, como disminución de costos en 2%; mejor distribución de los ingresos, cantidad de partidos, coincidencias por equipo y distancia a recorrer por cada terna disminuyendo la desviación en 82%, 83%, 46% y 68% respectivamente; además, se presenta una matriz de asignaciones propuestas, en donde se demuestra el cumplimiento de diferentes restricciones. Finalmente, se detallan las conclusiones y recomendaciones de la presente investigación. / Tesis

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%.

El tema principal de esta memoria es el estudio del problema de planificación minera, junto con el análisis detallado de un nuevo algoritmo propuesto en la literatura para resolverlo. El problema de planificación minera consiste en determinar la secuencia de extracción de una mina a tajo abierto. Para esto, típicamente se modela la mina como un conjunto de bloques y se diseña un calendario tentativo de su extracción. En la industria minera se resuelve este problema siguiendo una serie de pasos consecutivos que terminan por entregar una planificación. Por otro lado, existen distintos modelos de optimización que han sido propuestos para resolver este problema, pero debido a que las instancias son de gran tamaño, obtener soluciones requiere de técnicas y algoritmos más elaborados. Una instancia típica posee millones de variables y millones de restricciones. Por estas razones resulta ser un problema desafiante y con una aplicación muy importante, para el cual distintos tipos de descomposiciones han sido propuestas para resolverlo, junto con pre-procesos, heurísticas o versiones simplificadas de manera de hacer el problema más manejable. Todas estas técnicas pueden resolver problemas del orden de 200.000 bloques, lo cual es bueno, pero está lejos de poder resolver problemas reales. Recientemente, Chicoisne et. al. (Operations Research, 2012) desarrollaron un algoritmo eficiente capaz de resolver instancias con millones de bloques, pero en una versión simplificada del problema. Y por otro lado, Bienstock y Zuckerberg (Optimization Online, 2009) propusieron otro algoritmo, el cual es capaz de resolver eficientemente instancias de millones de bloques y bajo ningún supuesto importante. Este último resulta ser un algoritmo muy ingenioso y será el foco principal de este trabajo estudiarlo. En el desarrollo de este trabajo se estudió principalmente el problema de planificación minera, junto con la implementación del algoritmo de Bienstock y Zuckerberg. Además, usando algunas técnicas originales y otras técnicas clásicas, se diseñaron una serie de mejoras al algoritmo que lo hacen más eficiente, aprovechando la estructura del problema de planificación minera. Se verá que estas modificaciones producen mejoras significativas en el tiempo necesario para resolver las instancias disponibles. Y por último, y como un inicio para trabajo futuro, se propone una generalización del algoritmo a un contexto más amplio. Esta generalización se implementó para un nuevo modelo de Optimización Robusta propuesto en este trabajo para el mismo problema de minería, de esta forma dando un primer paso a una nueva manera de considerar incertidumbre en este problema.

Magíster en Gestión de Operaciones / todos desarrollados en estudios previos. Para este tipo de problemas, la formEn este trabajo se desarrolla un nuevo enfoque para resolver el problema de diseño de redes no capacitadas con fuente única en base a la combinación de méulación multicommodity que desagrega las demandas ha sido utilizada extensamente y se ha probado que se obtienen mejores resultados que con la formulación de flujo en redes clásica al comparar sus relajaciones lineales. En este trabajo se muestra que dicha formulación puede mejorar aún más al duplicar y dirigir arcos no-dirigidos. Con este concepto, se desarrolla un método de ascenso dual específico para el problema de diseño con fuente única que entrega cotas inferiores de buena calidad. Dentro de este método se propone un esquema de clasificación de commodities que permite una representación reducida del problema y que entrega mejores cotas inferiores en las instancias testeadas. Adicionalmente, este método también entrega una subred de tamaño reducido que se utiliza para encontrar soluciones primales factibles. Se muestra, que en este sentido, el método de ascenso dual es una excelente herramienta de selección de arcos en términos del potencial que tiene la subred de encontrar soluciones primales de buena calidad. Para obtener la solución primal, se utiliza la formulación multicommodity original o un esquema de generación de filas dependiendo del tamaño de la instancia. Se testean los distintos enfoques en instancias de distintos tamaños de redes en forma de grilla generadas aleatoriamente variando sus parámetros y su relación de costos fijos a costos de flujo, testeando instancias que en su equivalente de formulación multicommodity llegan a más de 16 millones de variables. / Este trabajo ha sido parcialmente financiado por Comisión Nacional de Investigación Científica y Tecnológica (CONICYT)

Magíster en Ingeniería de Negocios con Tecnologías de Información / Ingeniero Civil Industrial / En un mundo altamente competitivo, dinámico, en el cual las necesidades de los clientes van evolucionando constantemente, se hace necesario que las empresas manufactureras optimicen su producción y desarrollen una gestión cada vez más orientada al cliente, para convertirse o mantenerse como actores relevantes en un mercado global. Este es el caso de CMPC Maderas, que se ha convertido en una importante empresa en la industria de la madera. Se dedica a la producción y comercialización de productos de madera aserrada, remanufacturas y paneles contrachapados. La empresa exporta gran parte de su producción y un porcentaje importante se destina a países muy alejados de Chile, como los ubicados en Asia, Oceanía, Europa y América del Norte. Esto presenta un desafío importante, no solo para esta empresa en particular, sino para todos los exportadores sudamericanos de madera, lo que los obliga a ser eficientes en costos para ser competitivos. Por otra parte, la empresa debe mantener un buen nivel de servicio a sus clientes, los cuales necesitan mantener confianza en que tendrán un abastecimiento constante de grandes volúmenes de madera aserrada, cumpliendo con las especificaciones de sus pedidos y los tiempos de entrega comprometidos. El proyecto aborda en parte estos desafíos, centrándose en los procesos relacionados con la planificación de la producción de aserraderos. Pretende desarrollar un apoyo que permita aumentar el beneficio de la operación de los aserraderos, por medio de optimizar la utilización de recursos de materia prima y la capacidad instalada en las plantas de producción. Para esto se propone implementar una herramienta que incorpore una lógica de negocio de optimización, a través de programación matemática, para apoyar la toma de decisiones en el proceso, acompañado de un rediseño que mejore la coordinación entre los distintos actores involucrados e inserte la herramienta en la arquitectura de procesos de la empresa. Para el desarrollo del proyecto se ha utilizado la metodología de la Ingeniería de Negocios. Es decir, se comenzó por analizar el planteamiento estratégico de la empresa, su posicionamiento competitivo y modelo de negocios. Posteriormente se diseñó la arquitectura de procesos y se rediseñaron los procesos relacionados al proyecto, siendo consistentes con la estrategia y modelo de negocios. Finalmente, se diseñó la aplicación TI de apoyo al proceso y se construyó una solución que incorpora la lógica de negocio. En un periodo de estudio se obtuvieron resultados que prueban la existencia de oportunidades de mejora en el beneficio de la operación de los aserraderos, por medio de una mejor utilización de la capacidad instalada de las plantas y de la materia prima, como consecuencia de utilizar la solución propuesta.

No description available.