Logo Studenta

Unidad_2

¡Este material tiene más páginas!

Vista previa del material en texto

Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
1 
 
Ingeniería en Desarrollo de software 
Cuatrimestre 07 
 
 
 
Asignatura: 
Investigación de Operaciones 
 
 
 
 
Clave: 160930725 
 
 
 
 
 
 
 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
2 
 
 
Í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 
TEMA 2.1. PROBLEMA DE TRANSPORTE ........................................................................................ 4 
TEMA 2.2 PROBLEMA CAMINO MÁS CORTO ................................................................................. 8 
TEMA 2.3. PROGRAMACIÓN NO LINEAL .........................................................................................11 
TEMA 2.4. PROBLEMAS NO RESTRINGIDOS PROGRAMACIÓN NO LINEAL .....................14 
CIERRE DE LA UNIDAD .........................................................................................................................16 
PARA SABER MÁS… ..............................................................................................................................17 
FUENTES DE CONSULTA .....................................................................................................................17 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
3 
 
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 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
4 
 
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. 
 
Tema 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 como deben plantearse los 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
5 
 
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 esta la posibilidad de descárgalo he 
instalarlo desde una liga de Internet que es la siguiente. 
http://www.mediafire.com/?t7bvhibbgjekb7m . 
 
Has clic en la liga o cópiala en tu navegador de Internet. Se abre una página de Internet, ahí 
has 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 elarchivo 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 has 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: 
 
 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. 
http://www.mediafire.com/?t7bvhibbgjekb7m
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
6 
 
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 http://winqsb.softonic.com/. 
 
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 mas 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. 
 
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. 
http://www.lindo.com/index.php?option=com_content&view=article&id=34&Itemid=15
http://winqsb.softonic.com/
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
7 
 
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 
llama son 3 y que además son los mismos que de 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 por que 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 como 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 como 
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. 
 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
8 
 
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 siguientetema que son problemas de ruta crítica dentro de las redes. 
 
 
Tema 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 ves 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 como 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 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
9 
 
los paso 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 una algoritmo como dice Hillier & Lieberman 
(2006, pp., 384), que resuelve problemas de la ruta mas corta, en problemas que no cuentan 
con ligaduras ya establecidas, a diferencia de los problemas de la ruta mas 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 paso 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 mas 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 mas 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 calculo Excel, te servirá de complemento junto con el ejercicio 
del que se hablo 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. 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
10 
 
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 estás 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 calculo de esas rutas críticas y que esta 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 como 
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. 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
11 
 
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 
esta 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 
esta 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. 
 
Tema 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, 
donde f(x) y gi(x) son funciones dadas de n variables de decisión. 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
12 
 
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 un 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. 
 
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 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
13 
 
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., 1011-
1013), 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 leconoce como minimax. 
 
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 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
14 
 
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 esta 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: http://www.youtube.com/watch?v=rUF3BJCOtEg 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, 
et al. (2002, pp., 230-238), revisa los procedimientos y observa qué tipo de problemas han 
sido resueltos con este método. 
 
http://www.youtube.com/
http://www.youtube.com/watch?v=rUF3BJCOtEg
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
15 
 
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://people.usd.edu/~jflores/ArticuloLag/articuloPDF.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-No-
Lineal 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étodos 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 lo ejemplos vistos 
en esta sección; te ayudará a crear tus propias conclusiones y a tomar decisiones durante 
las actividades del tema. 
 
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. 
 
http://www.youtube.com/watch?v=iTfqb7eheJw
http://people.usd.edu/~jflores/ArticuloLag/articuloPDF.pdf
http://es.scribd.com/doc/36345383/TRABAJO-de-Prog-No-Lineal
http://es.scribd.com/doc/36345383/TRABAJO-de-Prog-No-Lineal
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
16 
 
Ahora ya puedes decidir cuando 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. 
 
 
Autorreflexiones 
 
Además de enviar tu trabajo de la Evidencia de aprendizaje, es importante que ingreses al 
foro Preguntas de Autorreflexión y consultes las preguntas que tu Facilitador(a) presente, a 
partir de ellas, debes elaborar tu Autorreflexión en un archivo de texto llamado 
DIOP_U2_ATR_XXYZ. Posteriormente envía tu archivo mediante la herramienta 
Autorreflexiones. 
 
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 algoritmosde 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 
 
 
Investigación de Operaciones 
Unidad 2. Comunicación y análisis de redes 
 
 
17 
 
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 a cerca 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://www.investigacion-operaciones.com/Curso_Inv_Oper.htm 
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 http://www.investigacion-
operaciones.com/ARCHIVOS_LIBRO/LibroCompleto.pdf 
 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. Recuperado de http://www.investigacion-
operaciones.com/material%20didactico/MANUAL%20INV%20OPER.pdf 
 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. 
 
http://www.uv.es/~sala/Clase11.pdf
http://www.investigacion-operaciones.com/Curso_Inv_Oper.htm
http://es.scribd.com/doc/71985539/Programacion-No-Lineal
http://www.investigacion-operaciones.com/ARCHIVOS_LIBRO/LibroCompleto.pdf
http://www.investigacion-operaciones.com/ARCHIVOS_LIBRO/LibroCompleto.pdf
http://www.investigacion-operaciones.com/material%20didactico/MANUAL%20INV%20OPER.pdf
http://www.investigacion-operaciones.com/material%20didactico/MANUAL%20INV%20OPER.pdf

Continuar navegando

Contenido elegido para ti

Otros materiales