Logo Studenta

DIOP_U2_Contenido

¡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 
 
 
 
 
 
 
 
 
 
 
 
Carrera: Desarrollo de software 
Semestre 5 
 
 
 
 
Asignatura: 
Investigación de operaciones 
 
 
 
Unidad 2. Comunicación y análisis de redes 
 
Ciudad de México, mayo del 2022 
 
 
Clave: 
15143525 
 
 
 
Universidad Abierta y a Distancia de México 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
2 
 
 
Índice 
Presentación de la unidad .......................................................................................................... 3 
Logros ......................................................................................................................................... 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 
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. 
 
Logros de la unidad 
 
• Identificar el procedimiento de optimización. 
• Presentar la ruta crítica como parte de la resolución de problemas. 
• Analizar los métodos de programación no lineal para la resolución de problemas 
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 porque 
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 
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 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 carpetasy 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: 
https://www.dropbox.com/s/zeb3h8289fw2ci9/TORA.rar
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
6 
 
 
• 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: 
• https://www.lindo.com/index.php/products/lingo-and-optimization-modeling 
WinQSB está en la siguiente liga: 
• https://www.tuinformaticafacil.com/descargas-gratis/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. 
https://www.lindo.com/index.php/products/lingo-and-optimization-modeling
https://www.tuinformaticafacil.com/descargas-gratis/formacion/tools-formacion/winqsb
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
7 
 
 
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. 
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. 
 
 
 
2.2 Problema camino más corto 
 
Problema árbol expandido mínimo 
 
Una vez que ya conoces la definición deRedes 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 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
9 
 
 
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. 
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 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. 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
11 
 
 
Con respecto al uso de lostres 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. 
 
 
 
 
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, 
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). 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
12 
 
 
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. 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
13 
 
 
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., 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 le conoce como minimax. 
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
14 
 
 
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).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, 
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 fuente: Lasmatemáticas.es (2017, 19 
de marzo) Máximos y mínimos y puntos de inflexión de una función - Selectividad 2016 
Catalunya (2ºBach) [video]. YouTube: 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. 
http://www.youtube.com/
https://www.youtube.com/watch?v=08o6nWKxiuw
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
15 
 
 
et al. (2002, pp., 230-238), revisa los procedimientos y observa qué tipo de problemas han 
sido resueltos con este método. 
 
 
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é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. 
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. Julioprofe (2013) Multiplicadores de Lagrange-Problema-1 
[video]. YouTube: 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 
http://es.scribd.com/doc/36345383/TRABAJO-de-Prog-No-Lineal
http://es.scribd.com/doc/36345383/TRABAJO-de-Prog-No-Lineal
http://www.youtube.com/watch?v=iTfqb7eheJw
http://sgpwe.izt.uam.mx/files/users/uami/ceciliahd/cvvi/Multiplicadores_de_Lagrange.pdf
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
16 
 
 
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. 
 
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. 
 
 
 
 
http://www.uv.es/~sala/Clase11.pdf
http://aulavirtual.agro.unlp.edu.ar/course/view.php?id=153
http://es.scribd.com/doc/71985539/Programacion-No-Lineal
Investigación de operaciones 
Unidad 2. Comunicación y análisis de redes 
17 
 
 
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/formu
lacion.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. 
• 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. 
https://laboratoriomatematicas.uniandes.edu.co/metodos/contenido/contenido/formulacion.pdf
https://laboratoriomatematicas.uniandes.edu.co/metodos/contenido/contenido/formulacion.pdf

Continuar navegando