• Author / Uploaded
• Juan FSH

Citation preview

Investigación de operaciones Unidad 2. Comunicación y análisis de redes

Carrera: Desarrollo de software Semestre 5

Asignatura: Investigación de operaciones

Unidad 2. Comunicación y análisis de redes

Clave: 15143525

Universidad Abierta y a Distancia de México

1

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Índice Presentación de la unidad...................................................................................................... 3 Propósitos de la unidad ......................................................................................................... 3 Competencia específica......................................................................................................... 3 Temario de la unidad ............................................................................................................. 3 Unidad 2. Comunicación y análisis de redes .......................................................................... 4 2.1. Problema de transporte................................................................................................... 4 2.2 problema camino más corto ............................................................................................. 8 2.3. Programación no lineal ................................................................................................. 11 2.4. Problemas no restringidos programación no lineal ........................................................ 14 Cierre de la unidad............................................................................................................... 17 Para saber más… ................................................................................................................ 17 Fuentes de consulta............................................................................................................. 17

2

Investigación de operaciones Unidad 2. Comunicación y análisis de redes

Presentación de la unidad En la unidad anterior se presentaron métodos de resolución de problemas de programación lineal. En la presente unidad, Comunicación y análisis de redes, se ampliará el horizonte con otro tipo de problemas que requieren de un tratamiento diferente. La Comunicación y el análisis de redes son problemas a los que se enfrentan las organizaciones cuando requieren dar a conocer información o hacer entregas de productos a distintas partes. La problemática que se pretende resolver está relacionada con los problemas de transporte, desde la materia prima hasta productos perecederos, que pudieran implicar el uso de autotransporte; donde, por la complejidad de cada problema, se hace necesario el uso de programas de software que pueden ser adquiridos para casos genéricos o pueden ser desarrollados de manera específica en cada caso. Otra área, es la definición de mejores rutas durante los procesos de producción y, por último, los problemas de programación no lineal que no cuentan con las características antes vistas en la Unidad 1 y, por tal motivo, su tratamiento debe ser diferente.

Propósitos de la unidad Analizar procesos con los métodos de programación no lineal, tales como: el procedimiento de optimización, la ruta crítica y de transporte para la resolución de problemas dentro de las organizaciones.

Competencia específica Analizar la comunicación y análisis de redes en la resolución de problemas empleando la programación no lineal.

Temario de la unidad 2. Comunicación y análisis de redes 2.1. Problema de transporte 2.1.1. Método esquina noroeste 2.1.2. Procedimiento de optimización 2.2. Problema camino más corto 2.2.1. Problema árbol expandido mínimo 2.2.2. Problema flujo máximo 2.2.3. Ruta crítica (PERT-CPM) 2.3. Programación no lineal 2.3.1. Problemas de programación no lineal 2.3.2. Optimización clásica programación no lineal 2.3.3. Puntos de inflexión programación no lineal 2.3.4. Máximos y mínimos programación no lineal

3

Investigación de operaciones Unidad 2. Comunicación y análisis de redes 2.4. Problemas no restringidos programación no lineal 2.4.1. Multiplicadores de LaGrange Lambda 2.4.2. Interpretación económica programación no lineal

Unidad 2. Comunicación y análisis de redes En la unidad anterior se revisaron algunos métodos de resolución de problemas de investigación de operaciones, como el método simplex y el de la M, que están basados en la aplicación de la programación lineal. En la presente unidad se exhibe un tipo de problema particularmente importante y relacionado con la programación lineal. El problema de transporte recibe este nombre por que sus aplicaciones involucran la determinación de formas óptimas de transportar cosas. También se presentan algunos conceptos relacionados con la administración de proyectos y su optimización por medio del uso de rutas críticas (PERT-CPM), llevándote a resolver problemas de programación no lineal, durante la optimización de sistemas.

2.1. Problema de transporte Una parte del proceso de fabricación y venta en cualquier industria es la entrega de los productos a distribuidores o cliente final. Parte de las utilidades de las empresas se ven afectadas por las formas como este proceso de distribución es diseñado y ejecutado. Para aquellos casos en los que una fábrica de determinados productos requiera entregar a diferentes almacenes, dentro de un territorio como un país, y que busca la disminución de costos y tiempos, existen métodos que sirven para establecer la mejor forma de hacer dichas entregas y se verán a detalle durante el presente tema. Método esquina noroeste Este método es utilizado para resolver problemas de transporte o de distribución de productos. Es tan solo una solución inicial que cumple satisfactoriamente con las restricciones del problema, aunque el resultado no siempre será el mejor. La ventaja principal, es que es un método de resolución rápida de problemas en donde existe un gran número de fuentes de productos o fábricas y un gran número de destinos ya sea de distribuidores o clientes finales de dichos productos a donde se deben entregar. Su nombre viene de la forma de aplicación del método, así que de igual manera existen otros métodos tales como Noreste, Sureste y Suroeste. En Taha (2004, pp., 165), se presenta una definición de este modelo de transporte llamado de esquina Noroeste que incluye un ejemplo muy claro de cómo deben plantearse los

4

Investigación de operaciones Unidad 2. Comunicación y análisis de redes problemas de este tipo para llegar a una solución por medio del método simplex. Debes aprender la definición y la forma del modelo. Este modelo de transporte cuenta con gran número de restricciones y variables lo que lo hace muy complejo, pero ya existen algoritmos de computadora que te ayudan a resolverlos de manera rápida. Revisa el programa llamado TORA que Taha (2004, pp., 166-172) utiliza para describir las soluciones a problemas y ejemplos de investigación de operaciones que te ayudaran a comprender como resolver problemas de transporte y de otros temas. Este programa llamado TORA es un software anexo al libro de Investigación de Operaciones de Hamdy A. Taha, aunque también está la posibilidad de descárgalo he instalarlo desde una liga de Internet que es la siguiente. https://www.dropbox.com/s/zeb3h8289fw2ci9/TORA.rar Haz clic en la liga o cópiala en tu navegador de Internet. Se abre una página de Internet, ahí haz clic en el rectángulo que dice TORA.rar Download (4.27 MB), y guarda el archivo en tu carpeta personal. Descomprime el archivo ahí mismo en una capeta que se llame TORA. Aparecerán varias carpetas y varios archivos. Para empezar a utilizar el software has doble clic en el archivo llamado index, donde aparecerá una página Web con un menú del lado izquierdo, donde puedes seleccionar varias opciones. La primera de las opciones es la de instalación del software TORA haz clic en la opción 1, TORA SETUP, esto instalará el software y creará un enlace en el menú de inicio de Windows. Sigue las instrucciones de instalación y lo podrás usar de inmediato. Este software TORA contiene varios ejemplos resueltos de investigación de operaciones, pero también puedes plantear y resolver los propios, que pueden estar relacionados con los siguientes temas:         

Matrix Inversa Solución de ecuaciones lineales simultáneas Programación lineal Modelos de transporte Modelos de redes Programación entera Modelos de colas Planeación de proyectos con CPM y PERT Teoría de juegos

También existen otros programas para resolver problemas de investigación de operaciones tales como:

5

Investigación de operaciones Unidad 2. Comunicación y análisis de redes 





What´sBest, que es un agregado para Excel que permite construir grandes modelos de optimización de escala en un diseño de forma libre dentro de una hoja de cálculo. Se pueden plantear problemas para modelos lineales o no lineales y de optimización con Excel. LINGO es una herramienta diseñada para la construcción y resolución lineal y no lineal y modelos de optimización con enteros más rápido y eficiente. Contiene un lenguaje para expresar modelo de optimización y un ambiente con todas las funciones para la creación y edición de problemas. LINDO es apropiado para la construcción y resolución de modelos lineales y enteros de tamaño moderado. Permite que se puedan crear aplicaciones propias de optimización.

Los puedes encontrar en las siguientes ligas: LINGO, WHAT´s BEST y LINDO están en la liga http://www.lindo.com/index.php?option=com_content&view=article&id=34&Itemid=15 y WinQSB está en la siguiente liga https://www.tuinformaticafacil.com/descargasgratis/formacion/tools-formacion/winqsb En esas páginas, encontrarás las indicaciones necesarias para su instalación en computadora. Se te sugiere descargar cada programa para que te vayas familiarizando con cada uno ya que son los más utilizados para resolver problemas de investigación de operaciones. Otra descripción del modelo de transporte es la que Muñoz, et al. (2011, pp., 35-37) presenta, donde encontrarás una definición muy clara de un modelo de transporte como una clase especial de programación lineal y una explicación del objetivo que se persigue al utilizar este modelo. También podrás encontrar un ejemplo de un ejercicio que podría resolverse por el método simplex; sin embargo, la estructura de las restricciones puede permitir solucionarlo con el método de transporte. El método de transporte es entonces un modelo lineal de tamaño variado que podría ser resuelto utilizando el método simplex de resolución de modelos lineales, pero resultará ineficiente debido al gran número de 1´s y 0´s que se encuentran en las restricciones, es por ello que se requiere utilizar el método de transporte. En Omaña (2004, pp., 63 a 76), encontrarás un resumen de las características de este método y de las condiciones que se deben cumplir para aplicarlo correctamente, observa que es necesario la definición correcta de la oferta y la demanda y la toma de decisiones, cuando estas cantidades se presentan en mayor y menor medida dentro del modelo. También se presentan 3 ejemplos donde se explica el uso del método de transporte para su solución y lo que es muy importante; una interpretación de los resultados que apoyarán en gran medida a la toma de decisiones dentro de las organizaciones. Revisa los ejemplos del texto y toma en cuenta que por su complejidad han sido resueltos con el uso de computadora y del software LINGO y WHAT´s BEST mencionados en el presente tema. Replica cada ejemplo en tu computadora pues te servirá de práctica para realizar las actividades de la Unidad 2. 6

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Debido a que un problema de transporte contiene m puntos de origen y n puntos de destino, entonces cuenta con m + n ecuaciones de restricción y tiene m + n – 1, variables básicas. Esta estructura del modelo de transporte según Taha (2004, pp., 178), permite asegurar que haya una solución básica no artificial de inicio que pudiera obtenerse con uno de los tres métodos siguientes: 1.- Método de la esquina noroeste (superior, izquierda) 2.- Métodos del costo mínimo 3.- Método de aproximación de Voguel. De manera muy sencilla, Taha (2004, pp., 177-187) en su libro de investigación de operaciones, explica los tres métodos antes mencionados basándose en el ejemplo 5.3-1 llamado (SunRay Transport). Muestra que los pasos del algoritmo de transporte como él lo llaman son 3 y que además son los mismos que dé inicio utiliza el método simplex. Empieza explicando paso a paso el uso del método de la esquina noroeste, llegando a una solución básica para el modelo, después explica paso a paso el método del costo mínimo que determina una mejor solución de inicio porque se concentra en las rutas menos costosas y termina con el método de Voguel que es una versión mejorada del método del costo mínimo. Revisa cada método mencionado antes, para que aprendas los pasos necesarios para resolver problemas de transporte. Revisa los ejercicios de ejemplo que vienen en el texto, esto te ayudará a ampliar tu conocimiento sobre estos tres temas. Procedimiento de optimización Uno de los mayores desarrollos recientes en investigación de operaciones (IO) ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización de redes. La aparición de algunos algoritmos ha tenido un efecto importante, al igual que las ideas de ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de éstos. En la actualidad se dispone de algoritmos y paquetes de computadora que se usan en forma rutinaria para resolver problemas muy grandes que no se habrían podido manejar hace dos o tres décadas.Hillier, & Lieberman (2006, pp., 374) Los problemas de transporte son en esencia problemas especiales de programación lineal que pueden ser modelos de optimización de redes. Taha (2004, pp., 213-214), muestra algunas aplicaciones posibles de las redes que te servirán para darte una idea de la magnitud de situaciones diferentes que se pueden presentar. También describe cómo se logra una solución de esas situaciones con gran variedad de algoritmos de optimización de redes. Revisa el texto para conocer los 5 algoritmos. En Muñoz, et al. (2011, pp., 67 y 69), se encuentra la definición de una red y muestra cómo se representa, puedes ampliar tu conocimiento si también revisas la definición que viene en Taha (2004, pp., 214), compáralas y analiza las coincidencias que puedas observar. 7

Investigación de operaciones Unidad 2. Comunicación y análisis de redes En Hillier & Lieberman (2006, pp., 376-377) se presenta la terminología de redes y sus componentes, revisa a que se refiere con Nodos, Arcos y el Flujo y compara con las lecturas anteriores para saber si se nombran o no de la misma manera. Pon énfasis también en el problema que viene en Muñoz, et al. (2011, pp., 68-69), para conocer las partes de una figura que representa una red. Esta información te servirá para realizar la siguiente Actividad. Ahora, abre el archivo actividades de la Unidad 2 y realiza la Actividad 1 Procedimiento de optimización, donde reafirmarás tu conocimiento con respecto a la resolución de problemas de transporte dentro de la programación lineal y estarás listo para el siguiente tema que son problemas de ruta crítica dentro de las redes.

2.2 Problema camino más corto Problema árbol expandido mínimo Una vez que ya conoces la definición de Redes y su representación gráfica, entramos a la solución de problemas de Investigación de Operaciones relacionados con las redes. El problema de la ruta más corta, que es el tema 2 de esta Unidad, es determinar la distancia menor entre un punto de origen y un punto de destino. En una red de transporte se puede utilizar para distintas situaciones, tal vez para encontrar la ruta más corta entre un origen y varios destinos, o la ruta más corta entre dos nodos no necesariamente origen y destino sino intermedios. Existen principalmente dos algoritmos para resolver problemas de este tipo, Algoritmo de Dijkstra y Algoritmo de Floyd. Muñoz, et al. (2011, pp., 70), describe los pasos del algoritmo de Dijkstra que describen como los cálculos avanzan de un nodo i a otro nodo j por medio de una clasificación entre nodos temporales y permanentes. También describe el algoritmo de Floyd como más general que el de Dijkstra ya que determina la ruta más corta entre dos nodos cualesquiera de la red. Revísalos y encuentra las diferencias entre ellos. En Taha (2004, pp., 224-233), vienen explicados los dos algoritmos (Dijkstra y Floyd) de una manera complementaria, lo que te ayudará a conocer otro punto de vista y además a reforzar tu conocimiento de cómo calcular rutas más cortas en las redes. Analiza cada una y observa como en los dos ejemplos que vienen en el texto, se explican paso a paso los procedimientos integrando además soluciones de cada uno por medio del software TORA descrito en la sección 2.1. Cada ejemplo contiene una descripción clara de lo que se debe hacer con dicho software, analiza y usa el software para llevar los ejemplos a los mismos resultados, te servirá de práctica. Una forma de enlazar nodos en las redes en forma directa o indirecta con la mínima longitud es usando el Algoritmo de Árbol de expansión mínima. Taha (2004, pp., 215-220) presenta 8

Investigación de operaciones Unidad 2. Comunicación y análisis de redes los pasos a seguir para resolver problemas de transporte con este algoritmo, revisa cada paso y estudia su aplicación en el ejemplo 6.2-1 que de manera muy completa es resuelto. Deberás también trabajar con el software TORA el cual ya conociste en el tema anterior. El problema es resuelto con este software y te será de gran ayuda estudiarlo para realizar las actividades de esta Unidad. El problema de árbol de expansión mínima es un algoritmo como dice Hillier & Lieberman (2006, pp., 384), que resuelve problemas de la ruta más corta, en problemas que no cuentan con ligaduras ya establecidas, a diferencia de los problemas de la ruta más corta que si tienen ligaduras ya definidas como los resueltos por los algoritmos de Dijkstra y Floyd. Lee el tema en Hillier & Lieberman (2006, pp., 384-388) y compara los pasos del algoritmo con los propuestos en Taha (2004, pp., 215-220). Problema Flujo máximo Aunque este tipo de problemas también son redes de nodos, la solución viene de manera diferente puesto que el objetivo es diferente. En los casos anteriores solo interesa conocer las rutas más cortas entre dos nodos ya sean origen o destino o intermedios, en cambio ahora esa ruta además debe garantizar que exista un flujo máximo en todo momento entre esos nodos. Analiza el ejemplo que viene en Taha (2004, pp., 239-241) que está referido a una de red de oleoductos que van desde los pozos de petróleo a las refinerías. Muñoz, et al. (2011, pp., 71), presenta las características del modelo de flujo máximo, analiza y observa que se puede formular como un problema de programación lineal y resolverse con el método simplex o con cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficiente que se basa en una red residual y en otro de trayectoria aumentada. Revisa en Hillier & Lieberman (2006, pp., 391) el algoritmo de la trayectoria de aumento del problema de flujo máximo, y analiza cuales son las modificaciones que tiene con respecto al tema de problemas de flujo máximo. También revisa la resolución de problemas de este tipo utilizando software Microsoft Excel y que viene explicado en Hillier & Lieberman (2006, pp., 395-396). Por otro lado, también puedes ver la solución de problemas por medio del Excel en Taha (2004, pp., 250-252), ahí se explica cómo debe hacerse la formulación de problemas de flujo máximo con programación lineal y cómo se anejan las restricciones del problema y como lograr el máximo en la función objetivo. Revisa el procedimiento de solución del problema de flujo máximo con hoja de cálculo Excel, te servirá de complemento junto con el ejercicio del que se habló en el párrafo anterior. Hillier & Lieberman (2006, pp., 389-390), menciona algunas aplicaciones comunes del problema de flujo máximo, es importante que las analices y relaciones con la aplicación práctica en tu trabajo o en tu comunidad. 9

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Ruta crítica (PERT-CPM) Los métodos CPM (Método de la Ruta Crítica) y PERT (Técnica de Evaluación y Revisión de Programa) están basados en redes y sirven para apoyar en la planeación, programación y control de proyectos. Taha (2004, pp., 266-267) define un proyecto como un conjunto de actividades interrelacionadas, en la que cada actividad consume tiempo y recursos. El objetivo del CPM y del PERT es contar con un método analítico para programar las actividades. Revisa en Taha (2004, pp., 267) en la figura 6.50 un resumen de los pasos de estas técnicas. El primer paso es la representación en una red donde cada actividad se une a otra y se establecen relaciones de precedencia. Analiza las reglas que se deben cumplir para esta actividad y que vienen descritas en Taha (2004, pp., 267-268). Hillier & Lieberman (2006, pp., 416-417), presenta lo que se llama una red de proyecto, que es una red para representar un proyecto que cosiste en cierto número de nodos, revisa lo que se refiere al ejemplo de la Red de proyecto del contrato de Reliable Construction Co. en la página 417, donde se hace una lista de actividades, predecesores y duración. Compara con lo descrito en Taha (2004, pp., 271-272), que son ejercicios propuestos donde se pide al lector hacer redes en base a una lista de actividades. El segundo paso es el cálculo de la ruta crítica CPM que es la formulación del programa del proyecto haciendo cálculos espaciales con lo que se obtiene según Taha (2004, pp., 272): 1.- Duración total necesaria para terminar el proyecto 2.- Clasificación de las actividades del proyecto en críticas y no críticas. Encontrarás ahí mismo la descripción de las actividades y como se clasifican en críticas y no criticas dependiendo de la definición de un evento como un momento en el tiempo en el terminan algunas actividades y otras inician. La conclusión a la que se llega según Hillier & Lieberman (2006, pp., 418), es “La duración del proyecto (estimada) es igual a la longitud de la ruta más larga a través de la red de proyecto. Esta trayectoria más larga se llama ruta crítica. (Si varias trayectorias son iguales, todas son rutas críticas). Analiza los pasos que describen el cálculo de esas rutas críticas y que está ampliamente abordados en Taha (2004, pp., 272-275). El paso 3, es la construcción de un cronograma de actividades, donde se puede usar la información obtenida con los cálculos del paso 2 para desarrollar el programa de tiempos, la construcción se ilustra con un ejemplo, ve a Taha (2004, pp., 275-277), ahí se explica cómo se utiliza el tiempo más temprano de iniciación de una actividad y el tiempo más tardío de terminación, generándose así un intervalo máximo que limita el tiempo en el que se puede programar dicha actividad. 10

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Con respecto al uso de los tres pasos anteriores que son usados para la programación de actividades, Taha (2004, pp., 278-279), presenta el ejemplo 6.6-4 como su aplicación donde se deben calcular las holguras de las actividades no críticas de la red del ejemplo 6.6-2 que está en Taha (2004, pp., 273-274). Como complemento del tema, la solución del ejemplo 6.6-2 se presenta también utilizando el software llamado TORA que fue explicado con anterioridad en el tema 2.1. Esta solución está en Taha (2004, pp., 278-279), revisa el ejemplo y busca en el software el archivo correspondiente al ejemplo ahí mencionado. Para saber más… puedes encontrar la resolución de problemas por los métodos PERT y CPM con software como Lingo Whats´s BEST y QSB descritos con anterioridad. Encuentra los ejemplos en Omaña (2004, pp., 85-96). Ahora, abre el archivo actividades de la unidad y realiza la Actividad 2 Ruta Crítica. Se compone de varias etapas, y cada una de ellas representa una parte del proceso de la solución de un problema de transporte, desde el planteamiento en un caso real, donde deberás plantear el modelo y llevarlo a una solución. Esta actividad te permitirá utilizar el procedimiento aprendido para la solución de problemas de Investigación de Operaciones específicos para CPM y PERT.

2.3. Programación no lineal Problemas de programación no lineal Un supuesto importante de programación lineal es que todas sus funciones (objetivo y de restricciones) son lineales. Lo anterior se cumple en parte, aunque muchos economistas han probado que cierto grado de no linealidad es la regla y no la excepción. Hillier & Lieberman (2006, pp., 547). De manera general, el problema de programación no lineal consiste en encontrar x = (x1, x2, …, xn) para maximizar f (x), sujeta a gi(x) ≤ bi, para i = 1, 2, …, m, y x ≥ 0, 11

Investigación de operaciones Unidad 2. Comunicación y análisis de redes donde f(x) y gi(x) son funciones dadas de n variables de decisión. Al existir diferentes tipos de problemas de programación no lineal que dependen de sus funciones f(x) y gi(x), se emplearían varios algoritmos para cada uno y que se verán más adelante en este tema. Para aquellos que tienen formas simples se pueden resolver eficientemente. Para cursar este Tema 3 de la asignatura, se te recomienda estudiar a profundidad los temas descritos en Hillier & Lieberman (2006, pp., 1006-1013), quienes en el apéndice 2, hablan de la convexidad con funciones convexas o cóncavas de una sola variable y funciones convexas o cóncavas de varias variables, terminando con conjuntos convexos; en el apéndice 3, abordan métodos de optimización clásica, referentes a la optimización no restringida de una función de una sola variable, de varias variables o con restricciones de igualdad. Los problemas de programación lineal son comunes y con varias aplicaciones, pero existen también otro tipo de problemas no lineales. El siguiente material que se te sugiere analices, contiene varios ejemplos de problemas resueltos con programación no lineal, es importante prestar especial atención, puesto que cada ejercicio está relacionado con situaciones de la vida cotidiana donde se busca la maximización de espacios, volúmenes o cantidades de materias primas. Revisa, entonces, ampliamente lo que Castillo, Conejo, Pedregal, García & Alguacil (2002, pp., 47- 69), presentan en cada uno de sus ejemplos, que aunque son de programación matemática en ingeniería y ciencia, se les puede comparar sin duda como problemas de investigación de operaciones. Toma en cuenta que son distintas áreas de aplicación y que tal vez tengas que recurrir a conocimientos de matemáticas relacionado con el uso de cálculo. Las áreas que son referidas en cada problema del párrafo anterior son: ejemplos geométricos, ejemplos mecánicos, ejemplos de ingeniería eléctrica y de asignación de tráfico en una ciudad; como puedes ver son problemas comunes, a los que te puedes enfrentar en tu trabajo o comunidad. Te sugiero que compares y contrastes los ejemplos anteriores con los presentados por Hillier & Lieberman (2006, pp., 548-556), y logres hacer una clasificación de ellos. Optimización clásica programación no lineal Los problemas se presentan de maneras distintas y no se dispone de un algoritmo que resuelva todos los problemas, en su lugar sólo existe algunos tipos especiales de problemas de programación no lineal. Hillier & Lieberman (2006, pp., 556-561), presenta una clasificación de problemas de programación no lineal que está basada en la formulación de problemas como se vieron antes en este tema. Compara los tipos descritos con los ejemplos de Castillo, et al. (2002, pp., 47- 69) y observa si existen coincidencias en ambos textos.

12

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Taha (2004, pp., 731-738), habla de una clasificación de los problemas de programación no lineal como directos e indirectos, revísalos para que te des una idea de que en realidad existen tantos métodos como tipos de problemas, esto te servirá para que hagas una clasificación de los métodos y sus tipos de problemas para cuando requieras utilizarlos. Ahí se presentan dos métodos para el problema no restringido: Método del gradiente y método de búsqueda directa. Observa que existen varios tipos de problemas, pon especial atención a los relacionados con la optimización no restringida, revisa su modelo y observa que no tienen restricciones por lo que la función objetivo es solo Maximizar f(x). Encuentra la diferencia que hay con la optimización restringida linealmente en Hillier & Lieberman (2006, pp., 558). Analiza los diferentes tipos de programaciones y encuentra las diferencias primordiales en cada modelo. La optimización no restringida de una variable es uno de los objetivos de este tema, el cual implica uno de los problemas más sencillos de programación no lineal, incluye los métodos de Bisección y el método de Newton que son ampliamente descritos en Hillier & Lieberman (2006, pp., 561-567). Más adelante se verán métodos en los que la optimización es requerida para más de una variable. Los métodos de optimización clásica se resumen en Hillier & Lieberman (2006, pp., 10111013), revísalos y compleméntalos con los métodos de otros autores que se han visto en el presente tema. Puntos de inflexión, Máximos y mínimos Los problemas de programación no lineal cuando son graficados representan curvas y no líneas como en la programación lineal. Esas curvas representan las soluciones factibles y. dentro de su espacio. Existen dos valores que representan resultados buscados durante la aplicación de algoritmos de solución. Estos conceptos relacionados con problemas de programación no lineal, se usan durante la aplicación de los algoritmos de resolución de problemas de este tipo. Puntos de inflexión, Máximos y Mínimos son esos dos conceptos importantes. Los puntos de inflexión se refieren a: un punto donde los valores de x en una función continua, pasan de un tipo de concavidad a otro. Esa curva atraviesa la tangente como se describe en Hillier & Lieberman (2006, pp., 1011-1013). La explicación matemática es que la derivada de la segunda función f en el punto de inflexión es cero. Para otro tipo de problemas de programación no lineal, donde la búsqueda de la solución no es un Maximizar o Minimizar, sino que se busca un intervalo donde exista un máximo y un mínimo, se conoce al punto como el lugar donde se pretende Maximizar la ganancia mínima o Minimizar la pérdida máxima. A este punto se le conoce como minimax.

13

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Estos dos conceptos siguen siendo parte de la optimización de funciones de programación no lineal. Revisa el material que al respecto presenta Taha (2004, pp., 731-764). Compara cada uno de los métodos descritos en el texto. Pon énfasis en los algoritmos con restricción analizando la estructura de cada problema y la relación entre a la función objetivo y sus restricciones. Ahí encontraras la descripción paso a paso de la programación separable y cómo se llega a su representación y solución, revisa la estructura de los problemas de programación convexa separable. Analiza el ejemplo 21.2-2 que está en Taha (2004, pp., 744-746). Para saber más… puedes encontrar la resolución de problemas de máximos y mínimos y puntos de inflexión en videos educativos en www.youtube.com. Un ejemplo de ello es el video que viene en la siguiente liga: https://www.youtube.com/watch?v=08o6nWKxiuw donde se describe la solución de un problema usando cálculo diferencial y encontrando la primera y la segunda derivada. Compara varios de los videos y relaciónalos con la teoría vista en el tema.

Ahora, abre el archivo actividades de la Unidad 2 y realiza la Actividad 3 Programación no lineal. Se compone de varias etapas y, cada una de ellas, representa una parte del proceso de la solución de problemas de programación no lineal. Esta actividad te permitirá analizar y describir sus características de los algoritmos de solución para la programación no lineal. Contendrá procedimientos de solución y ejemplos realizados por ti usando el software de computadora descrito en esta unidad

Tema 2.4. Problemas no restringidos programación no lineal Multiplicadores de Lagrange (Lambda) Otro de los métodos de solución que pertenecen a la teoría de optimización clásica es el Método de Lagrange. Este método utiliza como apoyo los llamados multiplicadores de Lagrange para llevar a una solución los problemas de programación no lineal encontrado los llamados máximos y mínimos. En Hillier & Lieberman (2006, pp., 1012-1013), encontrarás la aplicación de dicho método para la solución de problemas de optimización restringida con restricción de igualdad. En Castillo, et al. (2002, pp., 230- 231), revisarás el teorema de dualidad y solución del problema dual, observa como lo multiplicadores de Lagrange son utilizados para llegar a una solución. Conforme vas avanzando en el presente Tema, es importante que observes que los multiplicadores de Lagrange son una opción durante la búsqueda de soluciones a problemas no lineales. Observa el procedimiento Lagrangiano y los ejemplos resueltos por este método en Taha (2004, pp., 719-722). Compáralos con los ejemplos que viene en Castillo, 14

Investigación de operaciones Unidad 2. Comunicación y análisis de redes et al. (2002, pp., 230-238), revisa los procedimientos y observa qué tipo de problemas han sido resueltos con este método. Para saber más… Puedes ver la solución de un problema con el método de Lagrange que viene en YouTube y que muestra claramente paso a paso como se usan esos multiplicadores de Lagrange. La liga es: http://www.youtube.com/watch?v=iTfqb7eheJw. Puedes también revisar un artículo muy interesante en el que puedes observar de manera gráfica la utilización de los multiplicadores de Lagrange. La liga es: http://sgpwe.izt.uam.mx/files/users/uami/ceciliahd/cvvi/Multiplicadores_de_Lagrange.pdf Interpretación económica programación no lineal La interpretación económica está relacionada con los valores que van tomando los multiplicadores de Lagrange. Esos multiplicadores de programación no lineal tienen casi la misma interpretación que los de la programación lineal. De hecho, en el punto óptimo, el valor del multiplicador de Lagrange es la tasa de cambio instantánea del valor óptimo de la función objetivo. En la siguiente liga de Internet http://es.scribd.com/doc/36345383/TRABAJO-de-Prog-NoLineal viene una explicación de la Interpretación económica y se menciona un ejemplo de un fabricante que desea minimizar el costo total de producto. Revisa el procedimiento sugerido, así como las interpretaciones que se mencionan y compáralas con lo descrito en la parte de la teoría de la dualidad y análisis de sensibilidad que se presenta en Hillier & Lieberman (2006, pp., 217-220), y que aparece como la interpretación económica de la dualidad. Esta interpretación económica está relacionada ampliamente con el método simplex; de hecho, este método es la base para la solución de gran parte de problemas de programación lineal y no lineal, lee con atención también como se relaciona la interpretación y el método simplex y que se presenta en Hillier & Lieberman (2006, pp., 219). El tema de interpretación económica de la dualidad es también abordado por otros autores tal es el caso de Taha (2004, pp., 132-137), donde explica que los problemas de programación lineal se pueden considerar problemas duales; donde, por una parte, se busca maximizar los ingresos, pero utilizando recursos limitados. Compara el planteamiento de estos tipos de problemas con los descritos en el tema y observa como todos pueden llevarte a los mismos resultados. Analiza el ejercicio que viene en Taha (2004, pp., 133) y compara con los ejemplos vistos en esta sección; te ayudará a crear tus propias conclusiones y a tomar decisiones durante las actividades del tema.

15

Investigación de operaciones Unidad 2. Comunicación y análisis de redes Con lo visto hasta ahora en la Unidad 2, lograste conocer los algoritmos y métodos empleados para la solución de problemas de programación no lineal, pero además queda claro que es importante la interpretación de las variables. Ahora ya puedes decidir cuándo usar un método u otro para resolver problemas de programación no lineal. Recuerda que hay herramientas computacionales para resolver este tipo de problemas, pero es importante que conozcas los fundamentos matemáticos para ello.

Autoevaluación Para reforzar los conocimientos relacionados con los temas que se abordaron en esta segunda unidad del curso, es necesario que resuelvas la Autoevaluación de la unidad. Para realizar esta actividad, abre tu archivo de Actividades de la Unidad 2.

Ya que realizaste la autoevaluación, abre el archivo Actividades de la Unidad 2 y cumple la Evidencia de aprendizaje. Comunicación y análisis de redes donde aplicarás lo aprendido durante toda la unidad. Consta de dos ejercicios que resolverás utilizando software de computadora y describiendo el método o algoritmo que el software utiliza. Describirá paso a paso la resolución de dichos problemas. Esta Evidencia, dejará en claro que has logrado asimilar el conocimiento y cuentas con la habilidad de resolución de problemas de programación no lineal.

16

Investigación de operaciones Unidad 2. Comunicación y análisis de redes

Cierre de la unidad Has concluido la Unidad 2 del curso. Durante esta unidad se analizaron problemas de comunicación y redes para llevarlos a una solución empleando programación no lineal. Recordemos que los problemas son tan variados, como variados pueden ser los algoritmos de resolución e interpretación en la realidad. Existen algunos algoritmos de solución pero no todos pueden resolver todos los problemas, así que, deberás tener la habilidad de identificar e interpretar el problema y decidir qué algoritmos de solución le pueden ayudar. Es aconsejable que practiques ampliamente los métodos y algoritmos vistos en esta Unidad, pues te servirán para tomar decisiones durante el desarrollo de software encontrando valores como puntos de inflexión, donde conocerás los métodos para solucionar problemas de transporte, como el transporte de distintos productos a diferentes destinos en una empresa de paquetería.

Para saber más… Para conocer más acerca de los temas de la Unidad 2. Comunicación y análisis de redes puedes consultar libros o documentos que están disponibles desde Internet como los siguientes: http://www.uv.es/~sala/Clase11.pdf Dualidad en programación lineal http://aulavirtual.agro.unlp.edu.ar/course/view.php?id=153 Curso Investigación de operaciones I http://es.scribd.com/doc/71985539/Programacion-No-Lineal Puntos de inflexión y Máximos y mínimos Además, te recomiendo revisar la bibliografía básica del curso; encontrarás ejemplos y ejercicios sobre el tema.

Fuentes de consulta 

Castillo, E., Conejo, A.J., Pedregal, P., García, R., & Alguacil, N. (2002) Formulación y Resolución de Modelos de Programación Matemática en Ingeniería y Ciencia. Ciudad Real, España. Recuperado de : https://laboratoriomatematicas.uniandes.edu.co/metodos/contenido/contenido/formul acion.pdf

17

Investigación de operaciones Unidad 2. Comunicación y análisis de redes     

Hillier, F.S., & Lieberman, G.J. (2006) Introducción a la Investigación de Operaciones. México D.F.:Mc Graw Hill. Muñoz, R., Ochoa, M., & Morale, M. (2011) Investigación de Operaciones. México D.F.:Mc Graw Hill. Omaña, G. Z., (2004) Manual de Investigación de Operaciones. Venezuela. Universidad de Carabobo. Prawda, J. (2000) Métodos y modelos de investigación de operaciones. México D.F.: Limusa. Taha, A. (2004) Investigación de operaciones. México D.F.: Prentice Hall.

18