Source: http://docplayer.es/319904-Un-procedimiento-optimal-para-resolver-el-median-shortest-path-problem.html
Timestamp: 2016-10-26 19:35:49+00:00

Document:
⭐UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM
María Fernández Ayala
1 UNIVERSIDAD DEL BÍO-BÍO FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL PROFESOR GUÍA: SR. CARLOS OBREQUE NIÑEZ UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM TRABAJO DE TITULACIÓN PRESENTADO EN CONFORMIDAD A LOS REQUISITOS PARA OBTENER EL TÍTULO DE INGENIERO CIVIL INDUSTRIAL Concepción, 10 de Abril de 008 GERMÁN ENRIQUE PAREDES BELMAR2 DEDICATORIA Dedico este trabajo a mis padres, Enrique y Elvira, que con su esfuerzo, su incondicional apoyo y amor, hicieron posible el cumplimiento de esta meta; a mi abuelo Luis (Q.E.P.D.) que siempre me apoyó y aconsejó; y a Dios, que siempre me guía y acompaña en este hermoso camino.3 AGRADECIMIENTOS Quiero darle las gracias al Profesor Carlos Obreque, por su confianza, entrega, paciencia y sus valiosos consejos que me entregó durante todo el desarrollo del presente Proyecto de Título. También agradezco a todas las personas (amigos, familiares, compañeros, profesores) que me entregaron ánimo y apoyo durante la realización de este trabajo, y a lo largo de todos estos años de estudio.4 RESUMEN Sea G = (N, A) un grafo conexo, donde N es el conjunto de nodos y A el conjunto de arcos. Se consideran conocidos dos nodos de N: el nodo origen y nodo destino. Cada arco de A tiene un costo de construcción y se conoce la distancia más corta entre cada par de nodos de la red. El Median Shortest Path Problem (MSPP) consiste en localizar un path (camino) entre el nodo origen y el nodo destino, llamado path principal, de tal manera que todos los otros nodos de la red, que no están sobre este path, sean asignados a partir del nodo más cercano que se encuentre sobre el mismo path principal. El MSPP es un problema multiobjetivo con trade-off entre el costo total del path principal y la accesibilidad a este path. El objetivo del costo consiste en la suma de todos los costos (o longitudes) de los arcos que conforman el path principal, entre el nodo origen y el nodo destino, y el objetivo de accesibilidad es medido en términos del tiempo (o distancia) hacia el path principal, definida como la suma de todas las distancias desde el path principal a todos los nodos que no pertenecen a este path. Estos dos objetivos están en conflicto porque mientras más grande es el costo del path principal más pequeño es el tiempo de viaje desde el path a los demás nodos de la red y viceversa. En este trabajo se propone un procedimiento para detectar arcos que no forman parte de ninguna solución no inferior. Se propone un modelo de programación lineal entera binaria para determinar soluciones no inferiores del MSPP en forma óptima. Además, se resolvió el MSPP con una formulación basada en flujo multicommodity, con el objetivo de comparar resultados. Se presenta una red de 30 nodos y 108 arcos dirigidos para mostrar el procedimiento que se propone en este trabajo. Se exponen también los resultados de las experiencias computacionales realizadas.5 Índice de Contenidos Capítulo 1: GENERALIDADES Introducción Origen del Tema Justificación del Tema Objetivos Objetivo General Objetivos Específicos Alcances y Ámbito de Estudio Metodología... 5 Capítulo : LA INVESTIGACIÓN DE OPERACIONES Y LA PROGRAMACIÓN LINEAL La Investigación de Operaciones Reseña Histórica de la Investigación de Operaciones Clasificación de los problemas de Investigación de Operaciones La Metodología de la Investigación de Operaciones La Programación Lineal La Programación Lineal Entera El Algoritmo Branch and Bound Capítulo 3: PROGRAMACIÓN MULTIOBJETIVO Formulación del Problema General de Programación Multiobjetivo Formulación del Problema No Inferioridad Clasificación de Métodos de Programación Multiobjetivo Una Categorización de Técnicas Técnicas para Generar Soluciones No Inferiores El Método de los Pesos El Método de las Restricciones El Método de Estimación de Conjuntos No Inferiores (NISE)... 3 Capítulo 4: MODELOS DE REDES Introducción Definiciones de Redes Minimun Spanning Tree Problem (Problema del Árbol de Extensión Mínima) El Problema de la Ruta Más Corta... 8 Capítulo 5: AMPL: A MATHEMATICAL PROGRAMMING LANGUAGE Introducción El Lenguaje AMPL Entorno AMPL para MSDOS Resolución de Problemas en AMPL Plus... 346 Capítulo 6: EL MEDIAN SHORTEST PATH PROBLEM (MSPP) Revisión Bibliográfica Formulación Matemática del MSPP Formulación del MSPP mediante Programación Lineal Entera Binaria Formulación mediante Flujo Multicommodity del MSPP... 4 Capítulo 7: RESOLUCIÓN DEL MEDIAN SHORTEST PATH PROBLEM Ejemplo de Aplicación del MSPP Datos del Modelo Aparición y Eliminación de Subtours en el MSPP utilizando el Método de Planos Cortantes Eliminación de Arcos Secundarios Búsqueda de las Soluciones No Inferiores del MSPP Obtención del Path Hamiltoniano Obtención de la Ruta Más Corta Obtención de las Soluciones No Inferiores y la Curva de Trade Off Aplicación del Método NISE para obtener Soluciones No Inferiores Soluciones No Inferiores para la red de 30 nodos Solución No-Inferior Nº Solución No Inferior Nº Selección de Soluciones No Inferiores Experiencias Computacionales para la red de 30 nodos Experimento 1: Obtención de SNI sin reducción de arcos secundarios Experimento : Obtención de SNI con reducción de arcos secundarios Experimento 3: Obtención de SNI mediante la Formulación Basada en Flujo Multicommodity Análisis de los Resultados de los Experimentos Procedimiento propuesto para resolver el MSPP Resultados Computacionales de los Problemas Test Red de 1 Nodos Red de 30 Nodos Red de 50 Nodos Red de 75 Nodos Red de 100 Nodos Capítulo 8: CONCLUSIONES Y FUTURAS INVESTIGACIONES Conclusiones Futuras Investigaciones BIBLIOGRAFÍA7 Índice de Figuras Figura 1.1: Una solución del MSPP sobre la red de 1 nodos de Current et al. (1987)... Figura.1: Clasificación de la Investigación de Operaciones... 8 Figura.: Metodología de la Investigación de Operaciones Figura 3.1: Interpretación gráfica de no inferioridad para una región factible arbitraria en el espacio objetivo 18 Figura 3.: Relaciones entre las categorías de los métodos Figura 4.1: Red de 7 nodos y 10 arcos dirigidos Figura 4.: El Minimum Spanning Tree.. 7 Figura 5.1: Funcionamiento de AMPL, Holmes (199) Figura 5.: Entorno de comandos de AMPL para MSDOS Figura 7.1: Red de 30 Nodos y 108 Arcos Dirigidos Figura 7.: Aparición de subtours en el MSPP Figura 7.3: Efecto de la aplicación del método de planos cortantes Figura 7.4: Eliminación de Arcos Secundarios para el MSPP 55 Figura 7.5: El Path Hamiltoniano para la red de 30 nodos. 58 Figura 7.6: Ruta Más Corta para la red de 30 nodos.. 60 Figura 7.7: Gráfico del Path Hamiltoniano (PH) y la Ruta Más Corta (RMC) Figura 7.8: Pendiente de la recta entre el PH y la RMC Figura 7.9: Obtención de una Solución No Inferior a partir del PH y la RMC...64 Figura 7.10: Obtención de una nueva Solución No Inferior Figura 7.11: Representación Gráfica del Conjunto de Soluciones No Inferiores Figura 7.1: Solución No Inferior Nº4. 68 Figura 7.13: Solución No Inferior Nº7. 69 Figura 7.14: Selección de Soluciones No Inferiores para el MSPP Figura 7.15: Búsqueda de SNI en un intervalo mediante el Método de las Restricciones... 7 Figura 7.16: Tiempos de CPU de las SNI en el Experimento Figura 7.17: Tiempos de CPU de las SNI en el Experimento Figura 7.18: Tiempos de CPU de las SNI en el Experimento Figura 7.19: Comparación de Tiempos de CPU de los Experimentos Realizados Figura 7.0: Tiempos de CPU para la red de 1 nodos, Origen:, Destino: Figura 7.1: Tiempos de CPU para la red de 1 nodos, Origen: 4, Destino: Figura 7.: Tiempos de CPU para la red de 1 nodos, Origen: 17, Destino: Figura 7.3: Comparación de tiempos totales de CPU para la red de 1 nodos Figura 7.4: Tiempos de CPU para la red de 30 nodos, Origen: 8, Destino: Figura 7.5: Tiempos de CPU para la red de 30 nodos, Origen: 15, Destino: Figura 7.6: Tiempos de CPU para la red de 30 nodos, Origen: 18, Destino: Figura 7.7: Comparación de tiempos totales de CPU para la red de 30 nodos 9 Figura 7.8: Tiempos de CPU para la red de 50 nodos, Origen: 3, Destino: Figura 7.9: Tiempos de CPU para la red de 50 nodos, Origen: 33, Destino: Figura 7.30: Tiempos de CPU para la red de 50 nodos, Origen: 33, Destino:8 Figura 7.31: Comparación de tiempos totales de CPU para la red de 50 nodos 96 Figura 7.3: Tiempos de CPU para la red de 75 nodos, Origen: 4, Destino: Figura 7.33: Tiempos de CPU para la red de 75 nodos, Origen: 1, Destino: Figura 7.34: Comparación de tiempos totales de CPU para la red de 75 nodos 99 Figura 7.35: Tiempos de CPU para la red de 100 nodos, Origen: 40, Destino: Figura 7.36: Tiempos de CPU para la red de 100 nodos, Origen: 17, Destino: Índice de Tablas Tabla 3.1: Un ejemplo de no inferioridad Tabla 7.1: Costos C(i, j) de los arcos de la red de 30 nodos.. 47 Tabla 7.: Demandas de cada nodo para la red de 30 nodos generadas aleatoriamente Tabla 7.3: Matriz de Distancias Mínimas para la red de 30 nodos Tabla 7.4: Arcos Secundarios Candidatos. 55 Tabla 7.5: Soluciones No Inferiores encontradas con el método NISE Tabla 7.6: Búsqueda de tres SNI en un intervalo mediante el Método de las Restricciones.. 7 Tabla 7.7: Resultados del Experimento Tabla 7.8: Resultados del Experimento.. 75 Tabla 7.9: Resultados del Experimento Tabla 7.10A: Resultados para la red de 1 Nodos, Origen: ; Destino: Tabla 7.10B: Resultados para la red de 1 Nodos, Origen: ; Destino: Tabla 7.11A: Resultados para la red de 1 Nodos, Origen: 4; Destino: 8 86 Tabla 7.11B: Resultados para la red de 1 Nodos, Origen: 4; Destino: 8 86 Tabla 7.1A: Resultados para la red de 1 Nodos, Origen: 17; Destino: Tabla 7.1B: Resultados para la red de 1 Nodos, Origen: 17; Destino: Tabla 7.13A: Resultados para la red de 30 Nodos, Origen: 8; Destino: Tabla 7.13B: Resultados para la red de 30 Nodos, Origen: 8; Destino: Tabla 7.14A: Resultados para la red de 30 Nodos, Origen: 15; Destino: Tabla 7.14B: Resultados para la red de 30 Nodos, Origen: 15; Destino: Tabla 7.15A: Resultados para la red de 30 Nodos, Origen: 18; Destino: 9 91 Tabla 7.15B: Resultados para la red de 30 Nodos, Origen: 18; Destino: 9 91 Tabla 7.16A: Resultados para la red de 50 Nodos, Origen: 3; Destino: Tabla 7.16B: Resultados para la red de 50 Nodos, Origen: 3; Destino: Tabla 7.17A: Resultados para la red de 50 Nodos, Origen: 33; Destino: Tabla 7.17B: Resultados para la red de 50 Nodos, Origen: 33; Destino: Tabla 7.18A: Resultados para la red de 50 Nodos, Origen: 15; Destino: Tabla 7.18B: Resultados para la red de 50 Nodos, Origen: 15; Destino: Tabla 7.19A: Resultados para la red de 75 Nodos, Origen: 4; Destino: Tabla 7.19B: Resultados para la red de 75 Nodos, Origen: 4; Destino: Tabla 7.0A: Resultados para la red de 75 Nodos, Origen: 1; Destino: Tabla 7.0B: Resultados para la red de 75 Nodos, Origen: 1; Destino: Tabla 7.1A: Resultados para la red de 100 Nodos, Origen: 40; Destino: Tabla 7.1B: Resultados para la red de 100 Nodos, Origen: 40; Destino:9 Tabla 7.A: Resultados para la red de 100 Nodos, Origen: 17; Destino: Tabla 7.B: Resultados para la red de 100 Nodos, Origen: 17; Destino: Índice de Anexos ANEXO A: Algoritmo de Generación de Números Aleatorios ANEXO B. Algoritmo de Generación de la Matriz de Rutas Más Cortas para el MSPP ANEXO C. Algoritmo de Resolución del MSPP mediante la Formulación Binaria ANEXO D. Algoritmo de Resolución del MSPP mediante la Formulación basada en Flujo Mulicommodity10 1 Capítulo 1: GENERALIDADES 1.1 Introducción En este capítulo se explica el origen del presente Trabajo de Titulación y se entregan las razones por las cuales fue necesario desarrollarlo. También se dan a conocer los objetivos de este estudio, tanto el objetivo general como los objetivos específicos, el alcance o ámbito y la metodología que se utilizó para alcanzar los objetivos propuestos. 1. Origen del Tema El Tema desarrollado fue propuesto por el académico del Departamento de Ingeniería Industrial, señor Carlos Obreque Niñez, en respuesta a la necesidad de realizar una investigación acerca del problema de redes denominado en la literatura como el Median Shortest Path Problem, que consiste en localizar un path principal entre un nodo origen y un nodo destino de tal manera de minimizar el costo de construcción del camino principal y las distancias desde cada nodo, que no se encuentra en el camino principal, a un nodo que se encuentre sobre este camino. 1.3 Justificación del Tema El problema de estudio del presente Proyecto de Título, se sitúa dentro del campo de la Programación Lineal Entera. Es importante hacer notar que el MSPP es un problema que posee dos objetivos que están en conflicto: por una parte considera el objetivo de minimizar costos de construcción de un path, y por otra parte, minimizar el tiempo (ó longitud) total de viaje requerido por la demanda cada nodo que no esté en el path principal para alcanzar al nodo más cercano que si se encuentre en el path principal. Este problema entrega como solución, un conjunto de11 caminos mediante una curva de trade-off entre el costo de construcción del path principal y los costos del usuario (accesibilidad, costos sociales, etc.) de manera que el tomador de decisión pueda elegir cuál será la ruta óptima a seguir de acuerdo a su presupuesto. En la Figura 1.1 se muestra el MSPP en forma gráfica, aplicado a la red de 1 Nodos de Current et al. (1987), donde el Nodo Origen es el Nodo y el Nodo Destino el 19. El path principal es denotado con flechas continuas (color rojo) mientras que las asignaciones a los nodos que no están en el path principal, están marcadas con flechas segmentadas (color azul). Los pesos sobre los arcos corresponden a las distancias entre el par de nodos. Nodo Destino Nodo Origen Path Principal 1 Accesos del Path Principal 90 Figura 1.1: Una solución del MSPP sobre la red de 1 nodos de Current et al. (1987) Como es usual, en los problemas multiobjetivo, no existe una única solución óptima, debido a que existen objetivos en conflicto. El concepto de solución óptima es reemplazado por soluciones eficientes, o soluciones no inferiores (SNI), Labbé et al. (1998); por lo tanto, la necesidad del estudio del MSPP radica en la aplicación del12 3 una o más técnicas para la resolución de problemas multiobjetivo, generando alternativas eficientes de solución para los tomadores de decisiones. El MSPP es aplicable en muchos problemas de diseño de redes de transporte, especialmente en aquellos en que los costos del usuario y del operador del sistema son factores importantes. Por ejemplo, si se desea conectar grandes ciudades con una nueva línea del metro, el costo total de las líneas del metro es un factor importante para el operador del sistema. Por otra parte, el acceso a la nueva línea del metro con demandas en ciudades intermedias también es un factor importante debido a que representa un costo de los usuarios del sistema y, por lo tanto, podrían afectar la demanda total del sistema. En algunas situaciones (proyectos sociales por ejemplo), el objetivo principal puede ser la satisfacción de los usuarios, medido en términos de accesibilidad. Entonces, el MSPP podría ser utilizado para generar configuraciones de líneas de alternativas por donde debería pasar el metro. Otras aplicaciones de este problema incluyen, también, problemas de transporte tales como la localización de autopistas y el diseño de rutas para aerolíneas, y por otra parte, problemas de telecomunicaciones y problemas de distribución de fluidos.13 4 1.4 Objetivos Objetivo General El objetivo principal del presente estudio consiste en modelar y resolver el MSPP, utilizando Programación Lineal Entera Objetivos Específicos Proponer distintos modelos matemáticos para el MSPP. Determinar un método para resolver problemas multiobjetivo para aplicarlo al MSPP. Resolver el MSPP utilizando el software AMPL (A Mathematical Programming Language). Implementar y resolver el modelo propuesto aplicado a diferentes problemas test de otros artículos de la literatura y problemas obtenidos de Internet. 1.5 Alcances y Ámbito de Estudio Este Proyecto de Título se sitúa dentro del ámbito de la investigación académica, con el objetivo de aplicar conocimiento en la resolución de un problema difícil de resolver. Específicamente, se trabajó en el campo de la modelación y resolución de problemas mediante Programación Lineal Entera. En este estudio se considera la aplicación de una o más técnicas multiobjetivo para la resolución del MSPP aplicado a diferentes problemas test.14 5 1.6 Metodología La metodología utilizada para alcanzar los objetivos propuestos se basa en la investigación y el aprendizaje a través de herramientas tales como cursos dictados por expertos, textos relacionados con el presente trabajo (textos de Investigación de Operaciones, Programación Multiobjetivo, Lenguaje de Programación Matemática AMPL, Programación Lineal Entera, Publicaciones Científicas, entre otros) y sitios de Internet. También se recurrió a entrevistas periódicas con el profesor Guía. Este trabajo se divide en una serie de capítulos donde los contenidos se agrupan de acuerdo a características similares. Cada uno de estos capítulos es imprescindible en el logro de los objetivos propuestos. Para el análisis del Estado del Arte del MSPP, se recurrió principalmente a información existente en distintas publicaciones realizadas por investigadores en revistas científicas. Para la obtención de información acerca de la Investigación de Operaciones, sus aplicaciones y sus distintas ramas de conocimiento, se investigó en libros clásicos y en sitios de Internet. La descripción del software que se utilizó (AMPL), se realizó principalmente haciendo uso del Manual de Usuario del mismo. Una vez realizado lo anterior se modeló y resolvió el MSPP mediante la formulación binaria del problema utilizando el método de planos cortantes para la eliminación de subtours, y mediante la formulación basada en flujo multicommodity con el fin de comparar los resultados obtenidos por ambas formulaciones.15 6 Capítulo : LA INVESTIGACIÓN DE OPERACIONES Y LA PROGRAMACIÓN LINEAL En este capítulo se presenta una breve descripción de la Investigación de Operaciones y la Programación Lineal dando a conocer algunos datos históricos, definiciones fundamentales y sus aplicaciones, con el fin de mostrar el ámbito de estudio del presente Proyecto de Título..1 La Investigación de Operaciones Existen varias definiciones de lo que es la Investigación de Operaciones. Josa (007) propone las siguientes definiciones: La ciencia que estudia el modelado de sistemas probabilísticas y determinísticos que se originan en la vida real desde un punto de vista de la toma de decisiones óptimas. El estudio de cómo formular modelos matemáticos para problemas complejos de administración e ingeniería y cómo analizarlos para tener una visión de las posibles soluciones. Un enfoque científico para la toma de decisiones ejecutivas que consiste en: a) el arte de modelar situaciones complejas; b) la ciencia de desarrollar técnicas de solución para resolver dichos modelos; c) la capacidad de comunicar efectivamente los resultados..1.1 Reseña Histórica de la Investigación de Operaciones El concepto de Investigación de Operaciones nació durante la primera guerra mundial en Inglaterra entre los años 1914 y 1915, cuando F.W. Lanchester intentó tratar cuantitativamente las operaciones militares, obteniendo ecuaciones que16 7 relacionaban el resultado de una batalla en función de la fuerza numérica relativa de los combatientes y de su capacidad relativa de fuego. Lanchester modeló una situación que involucraba opciones estratégicas, y después probó ese modelo contra la situación real. Éste procedimiento es el que los investigadores de esta ciencia han venido practicando desde entonces, Chediak (003). Después de la segunda guerra mundial, las técnicas desarrolladas empezaron a ser usadas en la planeación de los negocios. En 1950 se organizó la Operations Research Society of America (ORSA) y The Institute of Management Science (TIMS). Desde la década de los 70 s las dos sociedades realizan publicaciones con trabajos y artículos relacionados con problemas operacionales en el uso de la ciencia administrativa y la investigación de operaciones. Actualmente, existen muchas situaciones de distinta naturaleza que pueden ser representadas matemáticamente por un modelo de Programación Lineal, por ejemplo, en finanzas, medicina, transportes, etc.. Clasificación de los problemas de Investigación de Operaciones Esta clasificación atiende más bien al tipo de modelo donde encaja el problema. En algunos casos se tendrá que ajustar el problema con un Modelo Determinístico, en el cual todos los datos importantes del mismo se suponen conocidos, pero en otros, algunos de estos datos se consideran inciertos y normalmente vienen dados por una probabilidad por lo que será necesaria la utilización de un Modelo Probabilístico. Sin embargo, existen modelos que conviene tratar como Híbridos de estas dos categorías. En la Figura.1 se hace una agrupación aproximada, a grandes rasgos, de los diferentes tipos de problema dentro de la categoría a la que pertenecen, Josa (007):17 8 Figura.1: Clasificación de la Investigación de Operaciones.3 La Metodología de la Investigación de Operaciones En su forma más simple, la Investigación de Operaciones puede considerarse como un procedimiento que consta de cuatro pasos, tal como se muestra en la Figura., Josa (007):18 9 Figura.: Metodología de la Investigación de Operaciones Paso 1, Definición del problema. Quizás la parte más importante de todo el proceso sea la definición del problema. Una respuesta incorrecta a una pregunta correcta no suele tener consecuencias fatales, ya que se pueden hacer revisiones y explorar otras alternativas; sin embargo, la respuesta correcta a una pregunta incorrecta puede ser desastrosa. Es importante que el problema esté claramente definido antes de invertir una gran cantidad de trabajo y energía en resolverlo. Paso, Modelamiento Matemático. Es un procedimiento que reconoce y verbaliza un problema para posteriormente cuantificarlo transformando las expresiones verbales en expresiones matemáticas. El modelamiento matemático es un arte, que mejora con la práctica. El proceso del modelado matemático consta de cuatro pasos: 1. Identificar las variables de decisión.. Identificar la función objetivo. 3. Identificar las restricciones. 4. Traducir los elementos anteriores a un modelo matemático.19 10 Paso 3, Resolución del modelo. Aceptado ya el modelo matemático que mejor describe la situación en estudio, se aplican los algoritmos y métodos matemáticos diseñados para su resolución. Las etapas de resolución del modelo son las siguientes: 1. Elegir la técnica de resolución adecuada.. Generar las soluciones del modelo. 3. Comprobar/validar los resultados. 4. Si los resultados son inaceptables, revisar el modelo matemático. 5. Realizar análisis de sensibilidad. Paso 4, Presentación/Implementación de los resultados. Éste es el paso final dentro del proceso. Los pasos de este proceso son los siguientes: 1. Preparar informes y/o presentaciones.. Vigilar el proceso de implementación de los resultados..4. La Programación Lineal En 1947, George Dantzig creó un método eficaz, el algoritmo Simplex, para resolver problemas de Programación Lineal (PL). En una encuesta de la revista Fortune, de 500 empresas, el 85% de las que contestaron dijeron que habían utilizado la PL, Winston (1994). Desde su aparición la PL ha demostrado que es una herramienta muy efectiva dentro de la Investigación de Operaciones. Un factor importante en el uso de esta técnica es el gran avance que han tenido los programas computacionales, que permiten resolver problemas extensos de PL en muy poco tiempo.20 11 La Programación Lineal (PL) es una herramienta para resolver problemas de optimización que se caracterizan por tener como Función Objetivo y Restricciones combinaciones lineales de las Variables de Decisión. La principal ventaja radica en que existe un algoritmo eficiente (Simplex) para resolver este tipo de modelos. Un problema de PL se podría representar matemáticamente de la siguiente forma, Fernández (000): Optimizar f + ( x1, x,..., xn ) = c1x1 + c x +... cn xn (.1) Sujeto a las siguientes restricciones: g = j ( x1, x,..., xn ) = a j1x1 + a j x a jn xn b j (.) Donde: c i, a ji y b j son constantes conocidas, con i = 1,,, n y j = 1,,, m Además x 0 para todo, i = 1,,, n (.3) i La expresión (.1) se conoce como Función Objetivo. La expresión (.) se conoce como las Restricciones del modelo, y (.3) se denominan las Restricciones de no negatividad. Las variables x i se conocen como las Variables de Decisión. Los coeficientes c i son los denominados coeficientes de costos; los coeficientes a ji se conocen como los Coeficientes Tecnológicos y los b j son los coeficientes de Recursos/Requerimientos, Fernández (000). Como se puede observar, todas las variables y restricciones son lineales.21 1 La PL es un método sencillo y poderoso en su aplicación. La aplicación a nuevos tipos de problemas ha generado importantes investigaciones teóricas en esa dirección. Gracias al desarrollo de la tecnología, y por ende, los computadores y software, han surgido nuevos problemas de gran envergadura que ahora son posibles de resolver, Chediak (003)..5 La Programación Lineal Entera En algunas situaciones que pueden representarse con modelos lineales, se encuentra que sólo tienen sentido aquellas soluciones de la región factible en las que todas o algunas de las variables de decisión sean números enteros. Estas situaciones pueden representarse mediante modelos matemáticos ligeramente diferentes de la programación lineal. En este contexto, un problema de programación lineal entera es un problema de programación lineal con la restricción adicional de que algunas de las variables deben tomar valores enteros. Cuando todas las variables deben tomar valores enteros, se trata de un problema de programación lineal entera puro, en caso contrario, se dice que es mixto. Una variable es binaria si sólo puede tomar los valores 0 y 1. De este modo, se tienen tres tipos de variables, Sallán et al. (00): Variables reales Variables enteras Variables binarias La posibilidad de utilizar variables enteras o binarias amplía notablemente las posibilidades de modelación matemática. El precio por una mayor versatilidad de la herramienta es el de una mayor complejidad en la resolución del modelo. Esta complejidad se debe a los siguientes hechos, Sallán et al. (00):22 13 Para las variables enteras del modelo, los vértices de la región factible no tienen porqué ser números enteros. En consecuencia, la solución óptima se encontrará en el interior de la región factible, por lo que el método Simplex, empleado de forma directa, no proporcionará la solución óptima. A diferencia del problema con variables reales, el número de soluciones de un modelo de programación lineal es finito, por lo que podría plantearse la posibilidad de encontrar la solución mediante la exploración de todas las soluciones posibles. Sin embargo, el número de soluciones a explorar para un problema mediano puede ser muy elevado: en principio, para un problema con n variables enteras debemos explorar n soluciones (excluyendo quizás algunas descartadas por las restricciones). Se han desarrollado metodologías que permiten explorar de manera más eficiente que la mera enumeración del conjunto de soluciones posibles. Gran número de estas metodologías emplean la lógica del branch and bound (ramificar y acotar), y están incorporadas a la mayoría de programas informáticos que resuelven modelos lineales..5.1 El Algoritmo Branch and Bound Un primer paso para solucionar un problema de programación lineal entera es resolver, mediante el método Simplex, el problema lineal asociado. Se trata de un problema lineal con la misma función objetivo y restricciones que el modelo original, pero al que se ha relajado la condición de que todas o algunas de las variables de decisión sean enteras. Si la solución así obtenida es entera, se habrá encontrado la solución del modelo de programación lineal entera. En caso contrario, la solución así obtenida es una primera aproximación a la solución del modelo, Sallán et al. (00).23 14 En el procedimiento del algoritmo branch and bound se trata de ir añadiendo restricciones al programa lineal asociado hasta encontrar la solución entera óptima. Para ello se procede en dos pasos: ramificación (branch) y acotamiento (bound) Ramificación Se trata de añadir restricciones al modelo que fuercen a que una de las variables sea entera. Esto se consigue añadiendo una de estas dos restricciones para que alguna de las variables x Bi que no sea entera en la solución obtenida hasta el momento, Sallán et al. (00): - Redondeo por defecto: se impone que la variable x Bi sea inferior o igual a la parte entera del valor de esa variable en el óptimo del problema lineal x Bi con las restricciones hasta el momento. Esto equivale a añadir la restricción: x i < E(x Bi ) (.4) - Redondeo por exceso: se impone que la variable x i sea mayor o igual al entero inmediatamente superior al valor x Bi. Esto equivale a añadir la restricción: x i > E(x Bi ) + 1 (.5) En seguida, se deberá proceder a resolver mediante el método Simplex dos problemas lineales. El primero, además de las restricciones que pudiera tener de etapas anteriores, llevará incorporada las restricciones de redondeo por defecto incorporada en esta etapa. El segundo se diferenciará del primero en que incluirá la restricción de redondeo por exceso, en vez de la de redondeo por defecto. Mostrar más
Grupo B. Sistemas y Tecnologías de la información Tema 1. Tema 2. Tema 3. Tema 4. Tema 5. Tema 6. Tema 7. Tema 8. Tema 9. Sistemas de Información. Análisis y desarrollo de sistemas de información. Metodologías Más detalles 10 DECISIONES BAJO INCERTIDUMBRE 1
10 DECISIONES BAJO INCERTIDUMBRE 1 Ay, cómo es cruel la incertidumbre! Si ella merece mi dolor o yo la tengo que olvidar. Gonzalo Curiel. Incertidumbre...Aureliano saltó once páginas para no perder el Más detalles CAS (COMPUTER ALGEBRA SYSTEM) EN LA ENSEÑANZA Y APRENDIZAGE DEL CÁLCULO. ALGUNOS RESULTADOS DE INVESTIGACIÓN 2
CAS (COMPUTER ALGEBRA SYSTEM) EN LA ENSEÑANZA Y APRENDIZAGE DEL CÁLCULO. ALGUNOS RESULTADOS DE INVESTIGACIÓN 2 Matías Camacho Machín Departamento de Análisis Matemátic, Universidad de La Laguna mcamacho@ull.es Más detalles UNIDAD I CONCEPTOS PREVIOS CONCEPTOS PREVIOS
CAPITULO III CADENA DE VALOR La contabilidad tiene como objetivo fundamental transmitir información de utilidad para los usuarios internos y externos, entre los primeros se encuentran, gerentes y tomadores Más detalles INFORMACIÓN Y DATOS. II.1. Definición de Datos
-CAPÍTULO II- INFORMACIÓN Y DATOS Es usual que se interpreten los términos datos e información indistintamente, lo cual no es correcto, existiendo una importante diferencia entre ambos conceptos que detallaremos Más detalles CONSEJERÍA DE GOBERNACIÓN MANUAL DE PROYECTOS. Agencia Andaluza del Voluntariado
CONSEJERÍA DE GOBERNACIÓN MANUAL DE PROYECTOS Agencia Andaluza del Voluntariado PROYECTOS Agencia Andaluza del Voluntariado Edita: Autor: Imprime: Dep. Legal: Junta de Andalucía. Consejería de Gobernación. Más detalles MODELO INTEGRADO DE VALOR PARA ESTRUCTURAS SOSTENIBLES
UNIVERSITAT POLITÈCNICA DE CATALUNYA ESCOLA TÈCNICA SUPERIOR D ENGINYERS DE CAMINS, CANALS I PORTS PROGRAMA DE DOCTORADO EN INGENIERÍA CIVIL TESIS DOCTORAL MODELO INTEGRADO DE VALOR PARA ESTRUCTURAS SOSTENIBLES Más detalles INSTITUTO POLITÉCNICO NACIONAL
Ingeniería de Software: Una Guía para Crear Sistemas de Información Alejandro Peña Ayala INSTITUTO POLITÉCNICO NACIONAL Alejandro Peña Ayala Cursó la licenciatura en Informática en la UPIICSA del IPN. Más detalles PROBABILIDAD Y ESTADÍSTICA. APLICACIONES A LA INGENIERÍA
PROBABILIDAD Y ESTADÍSTICA. APLICACIONES A LA INGENIERÍA DEPOOL RIVERO, RAMÓN MONASTERIO, DIÓSCORO 2013 PROBABILIDAD Y ESTADÍSTICA. APLICACIONES A LA INGENIERÍA Dr. DEPOOL RIVERO, RAMÓN Profesor Titular Más detalles 4.1 GRAFICA DE CONTROL Y CONCEPTOS ESTADISTICOS
4.1 GRAFICA DE CONTROL Y CONCEPTOS ESTADISTICOS Un proceso de control es aquel cuyo comportamiento con respecto a variaciones es estable en el tiempo. Las graficas de control se utilizan en la industria Más detalles 2.- EL APRENDIZAJE COMO OBJETIVO BÁSICO DE LA ENSEÑANZA UNIVERSITARIA 2.1.- CONCEPTO CE APRENDIZAJE 2.2.- CONCEPCIONES ACTUALES SOBRE EL APRENDIZAJE
INDICE.- EL CAMBIO DE MODELO EDUCATIVO 1.1.- LOS RETOS DE LA SOCIEDAD DEL CONOCIMIENTO Y DEL APRENDIZAJE PARA ENSEÑANZA Y APRENDIZAJE 1.2.- EL NUEVO PARADIGMA DE EDUCACIÓN SUPERIOR 2.- EL APRENDIZAJE COMO Más detalles E S T A D Í S T I C A HUGO GÓMEZ GIRALDO
E S T A D Í S T I C A HUGO GÓMEZ GIRALDO Mayo/009 i TABLA DE CONTENIDO CAPÍTULO 1: CONCEPTOS GENERALES... 1 1.1 Breve reseña histórica... 1 1. Significado de la estadística... 1.3 Pasos que sigue una investigación Más detalles Educación Tecnológica
Educación Media 2 Educación Tecnológica Programa de Estudio Segundo Año Medio Educación Tecnológica Programa de Estudio Segundo Año Medio Educación Tecnológica Programa de Estudio, Segundo Año Medio, Más detalles Los indicadores educativos y las dimensiones que los integran
Los indicadores educativos y las dimensiones que los integran Alejandro Morduchowicz Buenos Aires, diciembre de 2006 Agradezco la lectura y sugerencias de Nancy Montes y Margarita Poggi a una versión preliminar Más detalles Análisis del Sistema de Información
Análisis del Sistema de Información ÍNDICE DESCRIPCIÓN Y OBJETIVOS... 2 ACTIVIDAD ASI 1: DEFINICIÓN DEL SISTEMA... 6 Tarea ASI 1.1: Determinación del Alcance del Sistema... 6 Tarea ASI 1.2: Identificación Más detalles LOCALIZACIÓN DE INSTALACIONES
AdministracióndelasOperaciones La localización de la instalación es el proceso de elegir un lugar geográfico para realizar las operaciones de una empresa. LOCALIZACIÓN DE INSTALACIONES Los gerentes de Más detalles CAPITULO II DISEÑO (JACQUARD)
Evaluación de datos de medición Guía para la Expresión de la Incertidumbre de Medida k A + B EDICIÓN DIGITAL en español (traducción ª Ed. Sept. 008) Primera edición Septiembre 008 (original en inglés) Más detalles INVESTIGACION CUANTITATIVA
INVESTIGACION CUANTITATIVA 1 1. INTRODUCCIÓN 1 2. RESUMEN 2 3. OBJETIVOS DEL TEMA 6 4. DESARROLLO 7 4.1. La Investigación social 7 a) Orígenes 7 b) Objeto y método 7 c) Los objetivos de la Investigación Más detalles UNIVERSIDAD DE ALMERÍA. Facultad de Ciencias Experimentales Departamento de Estadística y Matemática Aplicada
UNIVERSIDAD DE ALMERÍA Facultad de Ciencias Experimentales Departamento de Estadística y Matemática Aplicada Memoria presentada por Antonio Fernández Álvarez como requisito para obtener el Diploma de Estudios Más detalles A pesar de su diversidad todas ellas tienen en común dos puntos:
A pesar de su diversidad todas ellas tienen en común dos puntos: 1) Rechazan, explícita o implícitamente, el reduccionismo conductista, según el cual la conducta puede ser explicada exclusivamente tomando Más detalles MANUAL FORMULACIÓN, EVALUACIÓN Y MONITOREO
MANUAL FORMULACIÓN, EVALUACIÓN Y MONITOREO DE PROYECTOS SOCIALES Ernesto Cohen Rodrigo Martínez División de Desarrollo Social CEPAL No ha sido sometido a revisión editorial MANUAL DE FORMULACION, EVALUACION Más detalles TÉCNICAS Y HERRAMIENTAS PARA EL CONTROL DE PROCESOS Y LA GESTIÓN DE LA CALIDAD, PARA SU USO EN LA AUDITORÍA INTERNA Y EN LA GESTIÓN DE RIESGOS
DOCUMENTO TÉCNICO N 75 Versión 0.1 DOCUMENTO TECNICO N XX Versión 0.1 TÉCNICAS Y HERRAMIENTAS PARA EL CONTROL DE PROCESOS Y LA GESTIÓN DE LA CALIDAD, PARA SU USO EN LA AUDITORÍA INTERNA Y EN LA GESTIÓN Más detalles El estudio de línea de base en un
capítulo V El estudio de línea de base en un diagnóstico El estudio de línea de base en un Diagnóstico Participativo de Comunicación Rural 5.1. Los principios y el propósito de un estudio de línea de base Más detalles Guía de los Fundamentos de la Dirección de Proyectos Tercera Edición (Guía del PMBOK )
Guía de los Fundamentos de la Dirección de Proyectos Tercera Edición (Guía del PMBOK ) Norma Nacional Americana ANSI/PMI 99-001-2004 AVISO Las publicaciones de normas y guías de Project Management Institute, Más detalles PROSPECTIVA TECNOLÓGICA: UNA INTRODUCCIÓN A SU METODOLOGÍA Y A SU APLICACIÓN EN DISTINTOS PAÍSES
PROSPECTIVA TECNOLÓGICA: UNA INTRODUCCIÓN A SU METODOLOGÍA Y A SU APLICACIÓN EN DISTINTOS PAÍSES J.A. MARTÍN PEREDA de la Academia de Ingeniería PRESENTACIÓN Uno de los temas que mayor atención está recibiendo Más detalles CAD/CAM. Instituto Técnico de la Estructura en Acero ITEA
7 CAD/CAM Instituto Técnico de la Estructura en Acero ITEA ÍNDICE ÍNDICE DEL TOMO 7 CAD/CAM Lección 7.1: Introducción al Papel del Acero en la Construcción en Europa... 1 1 INTRODUCCIÓN... 4 2 EL SOPORTE Más detalles ASPECTOS BÁSICOS DEL ESTUDIO DE MUESTRA Y POBLACIÓN PARA LA ELABORACIÓN DE LOS PROYECTOS DE INVESTIGACIÓN
UNIVERSIDAD DE ORIENTE NÚCLEO DE SUCRE ESCUELA DE ADMINISTRACIÓN CURSO ESPECIAL DE GRADO ASPECTOS BÁSICOS DEL ESTUDIO DE MUESTRA Y POBLACIÓN PARA LA ELABORACIÓN DE LOS PROYECTOS DE INVESTIGACIÓN ASESOR Más detalles 2. PARTE 1. APROXIMACIÓN TEÓRICA AL PLAN DE MARKETING...

References: Resolución 
 RESOLUCIÓN 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución