TECNOLÓGICO NACIONAL DE MÉXICO

INSTITUTO TECNOLÓGICO DE LA PAZ

TÍTULO DEL PROYECTO

“Optimización de redes”

CARRERA

Ingeniería Industrial

PRESENTAN

17310316 - Talamantes López Brayan Nicolás

17310294 – Mejía Castillo Guillermo.
17310307 - Bravo Flores Braulio.
17310705 - López Sánchez Edson.
17310298 – Ortiz Pérez Luis Fernando.
17310306 – Damián Vázquez Jordy Alexis.

La Paz, Baja California Sur, México, a miércoles 25 de septiembre del 2019

1
Resumen.

En el presente documento se plasma el uso de la optimización de redes, ya que

estos se emplean en diversos sectores industriales y ámbitos administrativos con
dicha finalidad de la obtención de soluciones que puedan satisfacer nuestras
necesidades, u optimizar las soluciones para lograr nuestro objetivo mediante
diferentes caminos.

Así pues, en la asignatura Investigación de las Operaciones II se llevó a cabo una

consulta bibliográfica que nos permite ampliar el panorama respecto a la
optimización de redes. La metodología utilizada abarco diferentes fases, ya que a
la hora de desarrollar un modelo de redes nos damos cuenta de que no solo existe
uno, sino que existe una gran cantidad de estos, el cual hace uso de elementos
conocidos como la red, nodos, arcos, etc. que involucran diferentes métodos con su
respectiva aplicación.

Además, es importante el uso de la metodología en relación con el uso del software,

el cual se ve un poco en el presente documento, aunque existan muchos más estilos
de software dedicados al mismo.

2
Índice.

1.1 Introducción……………………………………………………………………………4
2.1 Terminología…………………………………………………………………………...5
2.2 Problema de la ruta más corta………………………………………………………6
2.2.1 Ejemplo de la ruta más corta……………………………………………….……6
2.2.2 Características generales………………………………………………………...7
2.2.3 Supuestos para un problema de la ruta más corta…………………………….7
2.2.4 Aplicaciones………………………………………………………………………..8
2.3 Problema de árbol de mínima expansión………………………………….............9
2.3.1 Solución del problema árbol de minima expansión……………………………9
2.3.2 Ejemplo 1…………………………………………………………………………..9
2.3.3 Ejemplo 2………………………………………………………………………....10
2.4 Problema de flujo máximo………………………………………………………….12
2.5 Problema de flujo de costo mínimo……………………………………………….12
2.6 Programación lineal en Teoría de redes………………………………………….14
2.7 Uso de software……………………………………………………………………...16
2.8 Conclusión…………………………………………………………………………...17
2.9 Bibliografía……………………………………………………………………………18

3
1.1 Introducción.

La mayoría de los problemas de optimización se llevan a cabo con el objetivo

de minimizar o maximizar los recursos de una empresa (ya sean utilidades, costos,
materia prima, rutas, etc.), estos a su vez, se puede llevar a cabo mediante una
representación gráfica o de red la cual facilita el análisis del problema. Algunos
ejemplos de estos problemas son de producción, distribución, localización de
instalaciones, planificación de proyectos, administración de recursos y planificación
financiera, entre otros.

Estos métodos se utilizan en la mayoría de los ámbitos sociales, científicos y

económicos debido a que son herramientas visuales y conceptuales que muestran
las relaciones (dependencias) entre los componentes de los sistemas.

Los problemas de redes surgen en una gran variedad de situaciones como

por ejemplo las redes de transporte, redes eléctricas en fin una inmensa lista que
predominan en la vida diaria.

La metodología de los modelos de optimización de redes (OP) se ha

convertido en uno de los mayores desarrollos recientes en la Investigación
Operaciones (IO). Muchos modelos de Optimización de Redes son en realidad tipos
especiales de problemas de Programación Lineal, por ejemplo, tanto el problema
de transporte como el de asignación pueden ser representados mediante una red.

En resumen, una representación de redes nos proporciona un panorama

general poderoso y una ayuda conceptual para visualizar las relaciones entre los
componentes del sistema que se utiliza casi en todas las áreas científicas, sociales
y económicas.

4
2.1 Terminología.

La figura 6.6 es un ejemplo de diagrama de red. Cada una de las flechas que
aparecen entre dos locales se llama arco o rama de la red. A veces, el arco de (2)
a (4) se designa simbólicamente con el par (2, 4). Cada uno de los locales recibe el
nombre de nodo de la red.

La figura muestra un número +10 asociado con el lugar (1). Esto significa que
hay 10 máquinas E-9 disponibles (artículos de oferta) en ese lugar. Los indicadores
-3 y -7 asociados a los locales (3) y (4), respectivamente, denotan los
requerimientos o demandas de esos dos locales. La figura indica también que las
E-9 pueden ser enviadas al lugar (3) a través de cualquiera de las rutas alternativas
(1)→(2)→(3), (1)→(2)→(4)→(3), (1)→(2)→(5)→(4)→(3),o (1)→(2)→(5)→(3).

Los costos asociados al hecho de recorrer las rutas, y las capacidades a lo

largo de las mismas, determinarán cuál de ellas será elegida finalmente. La figura
6.7 muestra estos datos adicionales. Por comodidad, los costos de recorrido y las
capacidades se representan en notación simbólica (es decir, paramétrica). Los
costos c_ij son costos unitarios. Por ejemplo, el costo de recorrer el arco (5,3) es
c_53 por cada tractor. Estos costos se deben principalmente a combustible, peajes
y el salario del conductor durante el tiempo promedio que tarda en recorrer el arco.
Debido a los acuerdos establecidos previamente con los conductores, Zigwell tiene
que cambiar de conductor en cada lugar que encuentre sobre las rutas. Las
limitaciones en la disponibilidad actual de conductores hacen que exista una cota
superior en el número de tractores que pueden recorrer cualquier arco dado. Así,
por ejemplo, u_53 es la cota superior o capacidad en el arco (5,3).

5
2.2Problema de la ruta más corta.

En un grafo para este tipo de problema, cada arco debe tener una longitud
asociada. Supongamos que se comienza en algún nodo, por ejemplo, el nodo 1. El
problema de encontrar la distancia mínima entre el nodo 1 y cualquier otro nodo de
la red es conocido como el problema de la Ruta Más Corta.

2.2.1 Ejemplo ruta más corta.

Littletown es un pueblo pequeño en un área rural. Su departamento de

bomberos atiende un área geográfica relativamente grande que incluye muchas
comunidades agrícolas. Como hay muchos caminos en el área, es probable que se
pueda disponer de muchas rutas para llegar a cualquier comunidad agrícola desde
la estación de bomberos. Como el tiempo es esencial para llegar al lugar de un
incendio, el jefe de bomberos desea determinar con anticipación la ruta más corta
de la estación de bomberos a cada una de las comunidades agrícolas.

Este problema (como cualquier otro de la ruta más corta) puede considerarse
como un caso especial del problema de flujo a costo mínimo (sección 6.1) donde
las millas que se han viajado ahorase interpretan como el costo del flujo a través de
la red. Un viaje desde la estación de bomberos a lacomunidad agrícola se interpreta

6
como un flujo de 1 si la ruta es elegida a través de la red, por lo que minimizar el
costo de este flujo equivale a minimizar el número de millas recorridas.

2.2.2 Características generales.

2.2.3 Supuestos para un problema de la ruta más corta.

1. Se debe escoger una ruta a través de la red que se inicie en un nodo

determinado, al que se denominaorigen, y que termine en otro nodo, que se
llama destino.
2. Las líneas que conectan algunos pares de nodos comúnmente se conocen
como ligaduras (quepermiten viajar en cualquier dirección), aunque los arcos
(que sólo permiten viajar en una dirección)también están permitidos.
3. Asociado a cada ligadura (o arco) está un número no negativo al que se
denomina distancia.(Tenga presente que el trazo de cada ligadura en la red
no está en función de su verdadera distanciasin embargo sí proporciona el
número correcto junto a esta ligadura.)
4. El objetivo es encontrar la ruta más corta (la ruta con la distancia mínima
total) desde el origenhasta el destino.

7
2.2.4 Aplicaciones.

No todas las aplicaciones de los problemas de la ruta más corta implican

minimizar la distancia que se recorre desde el origen al destino. De hecho, pueden
no involucrar todos los recorridos. Las ligaduras (o arcos) pueden más bien
representar actividades de algún otro tipo, de modo que elegir una ruta a través de
una red corresponde a seleccionar la mejor secuencia de actividades. Entonces los
números que dan las “distancias” de las ligaduras pueden ser, por ejemplo, los
costos de las actividades, en cuyo caso el objetivo sería determinar qué secuencia
de actividades minimiza el costo total. A continuación, se enumeran tres categorías
de aplicaciones.

1. Minimizar la distancia total recorrida.

2. Minimizar el costo total de una secuencia de actividades.
3. Minimizar el tiempo total de una secuencia de actividades.

8
2.3 Problema de árbol de minima expansión.

Este problema considera una red no dirigida y conexa. En ella se debe

encontrar un árbol de expansión con la longitud mínima de sus arcos.

2.3.1 Solución del problema árbol de minima expansión.

1. selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se

agrega una ligadura) al nodo distinto más cercano.
2. se identifica el nodo no conectado más cercano a un nodo conectado y se
conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). este
paso se repite hasta que todos los nodos están conectados.
3. Empates. Los empates para el nodo mas cercano distinto (paso 1) o para el
nodo conectado más cercano (paso 2), se pueden romper en forma arbitraria
y el algoritmo debe llegar a una solución optima. No obstante, estos empates
son señal de que pueden existir (pero no necesariamente) soluciones
optimas optimas múltiples. Todas esas soluciones se pueden identificar si se
trabaja con las demás formas de romper los empates hasta el final.La manera
más rápida de ejecutar este algoritmo en forma manual es el enfoque grafico
que se ilustra enseguida.

2.3.2 Ejemplo.

La administración de seervada park necesita determinar los caminos bajo los

cuales se deben entender las líneas telefónicas para conectar todas las estaciones
con una longitud total mínima de cable. Se describirá paso a paso la solución de
este problema con base en los datos que se dan a continuación.

Los nodos y distancias para el problema se resumen enseguida, en donde

las líneas delgadas ahora representan ligaduras potenciales.

9
 Todos los nodos han quedado conectados, por lo que esta es la solución
(optima) que se buscaba. La longitud total de las ramas es 14 millas.

Aunque con este procedimiento a primera vista puede parecer que la elección
del nodo inicial afectaría la solución final (y la longitud total de las ligaduras), en
realidad no es así. Se sugiere que se verifique este hecho para el ejemplo, aplicando
de nuevo el algoritmo, pero con un nodo inicial distinto de 0.

2.3.3 Ejemplo 2.

Una compañía constructora de conjuntos habitacionales acaba de planear un

nuevo conjunto de 6 edificios multifamiliares, se necesita seleccionar una red de
tuberías de distribución de agua que conecte tofos los edificios a un mínimo costo.
Para desarrollar una nueva red del sistema de suministros de agua se deben unir
los seis edificios, la red seleccionada debe permitir la factibilidad que deben ser
tendidas a un mínimo costo.

10
11
2.4 Problema de flujo máximo.

En una red con flujo de capacidades en los arcos, el problema es determinar

el flujo máximo posible proveniente de los orígenes de forma tal de ahogar las
capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con
un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada
arco a una capacidad de flujo, kij. En esta red, deseamos encontrar el flujo total
máximo en la red, F, del nodo 1 al nodo m.

En la formulación de la programación lineal, el objetivo es maximizar F. El

monto que parte del origen por varias rutas. Para cada nodo intermedio, lo que entra
debe ser igual a lo sale. En algunas rutas los flujos pueden tomar ambas
direcciones. La capacidad que puede ser enviada a una dirección en particular
también es mostrada en cada ruta.

2.5 Problema de flujo de costo mínimo.

Vamos a definir al flujo de un costo mínimo como el envío de la oferta

disponible o flujo, a través de los diferentes arcos o la red, satisfaciendo al mismo

12
tiempo las relaciones del flujo en la red y las cantidades de oferta y demanda en los
nodos, su solución es muy eficiente.

Una condición necesaria para que el modelo tenga solución factible es que S bi=0,
es decir, que el flujo total generado en los nodos origen sea igual al flujo total
absorbido por los nodos destino. Cuando esta condición no se cumple se generan
nodos ficticios que generen o que absorban flujo. Los costos asociados a los arcos
que parten o llegan a estos nodos son cero. A continuación, se describe el problema
del flujo de costo mínimo:

1. La red es una red dirigida conexa.

2. Al menos uno de los nodos es nodo fuente.

3. Al menos uno de los nodos es nodo demanda.

4. El resto de los nodos son nodos de trasbordo.

5. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha,

donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo
puede ocurrir en ambas direcciones, debe representarse por un par de arcos con
direcciones opuestas.)

6. La red tiene suficientes arcos como suficiente capacidad para permitir que todos
los flujos generados por los nodos fuente lleguen a los nodos demanda.

7. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde
se conoce el costo por unidad.

8. El objetivo es minimizar el costo total de enviar el suministro disponible a través

de la red para satisfacer la demanda dada. Para este tipo de problemas podemos
ubicar las siguientes clasificaciones o grandes aplicaciones:

 Ruta más Corta

 Problema de Transporte
 Problema de Asignación

13
  Problema de Transbordo
 Flujo de Personal

Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha,

donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo
puede ocurrir en ambas direcciones, debe representarse por un par de arcos con
direcciones opuestas) con el objetivo de minimizar el costo total de enviar el
suministro disponible a través de la red para satisfacer la demanda dada.

2.6 Programación lineal en teoría de redes.

Se plantea de la manera siguiente:

xij= número de unidades de flujo en el arco (i, j)

cij= costo unitario de transportación en el arco (i, j)

bij= flujo neto en el nodo i (entrada-salida)

Lij= cota inferior de capacidad en el arco (i, j)

Uij= cota superior de capacidad en el arco (i, j)

Minimizar

∑𝑡𝑜𝑑𝑜𝑠𝑙𝑜𝑠𝑎𝑟𝑐𝑜𝑠 𝑐ij 𝑥ij

s.a ∑𝑗 𝑥ij - ∑𝑘 𝑥ki = 𝑏ij para cada arco

𝐿ij ≤ 𝑥ij ≤ 𝑈ij para cada arco

bi>0 si i es un nodo origen

bi<0 si i es un nodo destino

bi=0 si i es un nodo de transbordo

14
Una condición necesaria para que el modelo tenga solución factible es que bi=0,
es decir, que el flujo total generado en los nodos origen sea igual al flujo total
absorbido por los nodos destino.

Ejemplo: la siguiente red indica los caminos posibles para llegar del nodo 1 al nodo
7. Los valores en los arcos indican la distancia entre cada nodo.

min 10x12+15x27+19x67+26x13+8x23+8x32+18x24+18x42+10x35+10x53+

+8x56+8x65+5x45+5x54+11x47

s.t. x12+x13=1

-x27-x47-x67=-1

x27+x24+x23-x32-x42-x12=0

x32+x35-x23-x53-x13=0

x42+x47+x45-x24-x54=0

15
2.7 Uso de software.

Para trabajar con problemas que involucran redes WINQSB existen 7 modelos
fundamentales de redes con el fin de optimizar el uso de algunos recursos,
generalmente son problemas de minimización de costos y en ocasiones de tiempo
o de maximización del flujo a través de una red. Estos modelos son:

Conclusión
Es muy común hallar problemas de flujo de costo mínimo en la mayoría de las
industrias, como la agricultura, la industria de los neumáticos, transportación,
manufactura, medicina, asignación de materiales y se puede observar que en cada
iteración del algoritmo establecido, se resuelve un problema de la ruta más corta,
con la restricción de que las longitudes de los arcos son no negativas. Durante cada
iteración el algoritmo selecciona un nodo con exceso de oferta un nodo con exceso
de demanda y termina cuando la solución satisface todas las restricciones de
balance. Y es importante también mencionar que deben satisfacer los
requerimientos para la aplicación del algoritmo analizado.

16
2.8 Conclusión.

Es muy común hallar problemas de flujo de costo mínimo en la mayoría de las

industrias, como la agricultura, la industria de los neumáticos, transportación,
manufactura, medicina, asignación de materiales y se puede observar que, en cada
iteración del algoritmo establecido, se resuelve un problema de la ruta más corta,
con la restricción de que las longitudes de los arcos son no negativas. Durante cada
iteración el algoritmo selecciona un nodo con exceso de oferta un nodo con exceso
de demanda y termina cuando la solución satisface todas las restricciones de
balance. Y es importante también mencionar que deben satisfacer los
requerimientos para la aplicación del algoritmo analizado.

17
2.9 Bibliografía.

Eppen, G. (2000). Modelos de red. En Investigación de Operaciones en la

Ciencia Administrativa (págs. 239-287). México: PRENTICE-HALL.

ADRIANA NIETO, A. (2014, 19 febrero). 5.5 flujo a costo minimo. Recuperado

24 septiembre, 2019, de https://es.slideshare.net/adncstell/55-flujo-a-costo-minimo

Carlos Muñoz, C. (2016). Programación lineal. Flujo de redes. Recuperado

24 septiembre, 2019, de https://www.monografias.com/trabajos16/flujo-redes/flujo-
redes.shtml

Frederick S. Hiller y Gerald J. Liberman. Investigación De Operaciones.

McGraw-Hill. Séptima Edición. 2002.

Hamdy A. Taha. Investigación De Operaciones. Ediciones Alfaomega. Cuarta

Edición. 1991.

Universidad Nacional Autónoma de México. (s.f.). FLUJO A COSTO MÍNIMO

- Redes de optimización. Recuperado 24 septiembre, 2019, de
https://sites.google.com/site/optimizaciontarea2/flujo-a-costo-minimo

18