Universidad Autónoma de Baja California

Facultad de Ingeniería
Laboratorio de Investigación de Operaciones
Nombre: Ernesto Rios Valenzuela
Matrícula: 1162299
Fecha: 4/12/20
N° Práctica: 10
Clave de Laboratorio: 693-1

MODELOS DE OPTIMIZACIÓN DE REDES

Los problemas de redes surgen en una gran variedad de situaciones. Las redes de
transporte, eléctricas y de comunicaciones predominan en la vida diaria. La
representación de redes se utiliza ampliamente en áreas tan diversas como
producción, distribución, planeación de proyectos, localización de instalaciones,
administración de recursos y planeación financiera, para nombrar sólo unos
ejemplos. De hecho, una representación de redes proporciona un panorama general
tan poderoso y una ayuda conceptual para visualizar las relaciones entre los
componentes del sistema, que se usa casi en todas las áreas científicas, sociales y
económicas.
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 impacto
importante, al igual que las ideas de ciencias de la computación acerca de
estructuras de datos y la manipulación eficiente de los mismos. En consecuencia,
ahora se dispone de algoritmos y paquetes de computadora y se usan en forma
rutinaria para resolver problemas muy grandes que no se habrían podido manejar
hace dos o tres décadas.
Existen 5 tipos importantes de problemas que son:
• Árbol de mínima expansión
• Ruta más corta
• Flujo máximo
• Costo mínimo
• PERT/ CPM
Terminología de Redes
• Red: conjunto de puntos y líneas que unen ciertos pares de puntos.
• Nodos: Puntos (o vértices).
• Arcos: Líneas, ligaduras, aristas o ramas. Se etiquetan para dar nombre a los
nodos en sus puntos terminales.
• Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección.
La dirección se indica agregando una cabeza de flecha al final de la línea que
representa el arco.
• Arco no dirigido: Si el flujo a través de un arco se permite en ambas
direcciones.
• Red dirigida: Red que tiene sólo arcos dirigidos.
• Red no dirigida: Todos sus arcos son no dirigidos.
• Trayectoria: Sucesión de arcos distintos que conectan nodos.
• Ciclo: Trayectoria que comienza y termina en el mismo nodo.
• Red conexa: Red en la que cada par de nodos está conectado.
• Árbol: Red conexa (para algún subconjunto de n nodos) que no contiene
ciclos no dirigidos.
• Árbol de expansión: Red conexa para los n nodos que contiene ciclos no
dirigidos.
• Capacidad del arco: Cantidad máxima de flujo (quizá infinito) que puede
circular en un arco dirigido.
• Nodo fuente: Nodo origen, tiene la propiedad de que el flujo que sale del nodo
excede el flujo que entra a él.
• Nodo de demanda: Nodo de destino, donde el flujo que llega excede al que
sale de él.
• Nodo de trasbordo: Intermedio, satisface la conservación del flujo, es decir,
el flujo que entra es igual al que sale.
Árbol de expansión mínima
El algoritmo del árbol de expansión mínima es un modelo de optimización de redes
que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con
el objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase
por longitud del arco una cantidad variable según el contexto operacional de
minimización, y que puede bien representar una distancia o unidad de medida).
Este problema surge cuando todos los nodos de una red deben conectarse entre
ellos.
El árbol de expansión mínima es apropiado para problemas en los cuales la
redundancia es expansiva, el flujo a lo largo de los arcos se considera instantáneo.
Este problema se refiere a utilizar las ramas o arcos de la red para llegar a todos los
nodos de la red, de manera talque se minimiza la longitud total. La aplicación de
estos problemas de optimización se ubica en las redes de comunicación eléctrica,
telefónica, carretera, ferroviaria, aérea, marítima, etc.; donde los nodos representan
puntos de consumo eléctrico, teléfonos, aeropuertos, computadoras.
Otro ejemplo es en la construcción de carreteras pavimentadas que unen varias
poblaciones. El camino entre dos poblaciones puede pasar por una o más
poblaciones adicionales. Y los arcos podrían ser de alta tensión, cable de fibra
óptica, rutas aéreas, etc.
Para la solución se emplean los algoritmos PRIM y Kruskal.
Ejemplo: La urbanizadora SOVIPE está en proceso de instalar líneas de energía
eléctrica en un desarrollo habitacional grande. El gerente quiere minimizar la
longitud total de cable, lo cual minimizará sus costos. El desarrollo habitacional se
muestra en la red que se muestra. Cada casa se numeró y las distancias entre ellas
se dan en cientos de pies. ¿Qué le recomienda?

De acuerdo al algoritmo de Kruskal, conectamos las dos casas más cercanas

de la urbanización siendo estas la 1 y la 3 que están a 100 pies, a partir de las dos
casas conectadas observamos cuales están más cercas de ellas y observamos que
la casa 4 está a 200 pies de la casa 1 y de la casa 3 por lo que se puede conectar
por cualquiera de ellas y lo hacemos con la casa 3. Ahora ya tenemos tres casas
conectadas y la más cercana a ellas es la casa 6 que está a 300 pies de la casa 3
y la conectamos, de la misma manera procedemos con las casas resaltante hasta
conectarlas todas, tomando en cuenta que no se nos forme bucle o loop. De manera
que la cantidad mínima de cable será de 45 pies.

Ruta más corta

El problema de la ruta más corta determina la distancia menor entre un punto de
origen y un punto de destino.
Un problema de la ruta más corta involucra una red conexa con un costo
no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro se le
denomina destino. El objetivo es determinar una ruta que una a la fuente con el
origen, de manera que la suma de los costos asociados con las ramas en la ruta
sea la mínima.
El algoritmo de Dijkstra es útil para determinar la ruta más corta entre el nodo del
punto de origen y cada uno de los nodos de la red. Por otra parte, el algoritmo de
Floyd es más general porque permite determinar la ruta más corta entre cualquier
par de nodos de la red.
Vale la pena considerar, que en la práctica, es muy frecuente la utilización del
algoritmo resultante con variaciones que consisten en la minimización de tiempos,
no necesariamente de distancias.
El problema de ruta más corta tiene muchas aplicaciones prácticas, algunas son:
encontrar la ruta más corta o más rápida entre dos puntos en un mapa, redes
eléctricas, telecomunicaciones, transporte, planeación de tráfico urbano,
trasbordo, diseño de rutas de vehículos, planeación de inventarios, administración
de proyectos, planeación de producción, horarios de operadores telefónicos, diseño
de movimiento en robótica, redes de colaboración entre científicos, reemplazo de
equipo, etc.
Además, como se mencionó anteriormente los algoritmos de solución pueden
adaptarse en la búsqueda inicial de una solución aproximada de problemas
complejos, esto significa que la aplicación consiste precisamente en proveer
estructura para varios problemas de optimización combinatoria como: el problema
de la mochila, secuencia de alineación en biología molecular(secuenciación del
ADN), el problema del agente viajero, etc.
El ejemplo más sencillo para explicar el problema de la ruta más corta es tomar el
viaje de una persona que quisiera ir de la Ciudad de México a la ciudad de
Monterrey, Nuevo León, podría tener varias alternativas dependiendo de sus
intereses, es decir, si deseara llegar más rápido (minimizando el tiempo o la
distancia) o de una forma más económica (minimizando el costo), toda vez que cada
carretera tiene una longitud específica (kms) y un precio por el derecho de transitar
en ella (costo). Entonces, el problema consiste en encontrar la ruta más eficiente (la
ruta mínima) con base en la longitud o el costo. Este problema se representa por
una red, donde las ciudades son identificadas por nodos y las carreteras por arcos.

Flujo máximo
Muchas situaciones pueden ser modeladas como un problema de red, en algunos
casos cada arco puede tener una cierta capacidad que limite la cantidad de algún´
producto que pueda ser enviado a través de cada arco. En tal caso, es importante
determinar la cantidad máxima que puede ser transportada desde un punto inicial
(fuente) a un punto terminal (pozo, sumidero o destino). Este tipo de problema se
denomina problema de Flujo Máximo.
Entre las aplicaciones que tiene este método se puede mencionar que
• se puede maximizar el flujo de productos dentro de la red de distribución de
una compañía a sus clientes,
• maximizar el flujo de agua a través del sistema de acueductos
• maximizar el flujo de vehículos a través de una red de transporte.
Características:
• 1.- Todo flujo a través de una red conexa dirigida se origina en un nodo,
llamado origen, y termina en otro llamado destino
• 2.- Los nodos restantes son nodos de transbordo.
 • 3.- Se permite el flujo a través de un arco solo en la dirección indicada por la
flecha, donde la capacidad máxima de flujo está dada por la capacidad del
arco.
• 4.- El objetivo es maximizar la cantidad total de flujo del origen al destino.

Costo Mínimo
Es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o
distribución, arrojando mejores resultados que métodos como el de la esquina
noroeste, dado que se enfoca en las rutas que presentan menores costos.
El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores
dado que se trata simplemente de la asignación de la mayor cantidad de unidades
posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa
de toda la matriz hasta finalizar el método.
Características:
1. La red es una red dirigida y conexa.
2. Al menos uno de los nodos es un nodo fuente.
3. Al menos uno de los nodos es un 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 en que indica la
flecha.
6. La red tiene suficientes arcos con suficiente capacidad
7. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo.
8. El objetivo es minimizar el costo total de enviar el suministro disponible
APLICACIÓN
• Determinar un plan de transporte de una mercancía de varias fuentes a varios
destinos a un costo mínimo.
PERT/ CPM
El método CPM o Ruta Crítica (equivalente a la sigla en inglés Critical Path Method)
es frecuentemente utilizado en el desarrollo y control de proyectos. El objetivo
principal es determinar la duración de un proyecto, entendiendo éste como una
secuencia de actividades relacionadas entre sí, donde cada una de las actividades
tiene una duración estimada.
Puede ser empleado para determinar cuál es el tiempo requerido para completar el
proyecto. El método CPM también permite identificar cuales actividades pueden ser
atrasadas sin afectar la duración total del proyecto. Si la duración de las actividades
no es conocida con certeza, la Técnica de Revisión y Evaluación del Programa
(PERT) puede ser empleado para determinar la probabilidad de que un proyecto
termine antes de un período definido

Ventajas del uso de CPM y PERT.

• Obliga a hacer un análisis muy detallado del proyecto y de los métodos y
equipos que se utilizarán.
• Valioso como herramienta de venta u oferta. Da prestigio y demuestra
preocupación por la eficiencia y los costos.
• Da los argumentos tan necesarios para la oportuna obtención de los planos.
• Mejora relaciones con los proveedores.
• Ayuda en el manejo de personal.
Aplicación
1.- Programación de proyectos de construcción como edificios, carreteras y
albercas.
2.- Programación del movimiento de un hospital.
3.- Desarrollo de un procedimiento de conteo regresivo y procedimiento de reserva
de un lanzamiento de vuelos especiales.
4.- Instalación de un nuevo sistema de computadora.
5.- Diseño y comercialización de un nuevo producto.
6.- Completar una fusión corporativa.
7.- Construcción de una nave.”
Conclusión
Como vemos este tipo de métodos para dar soluciones optimas a problemas de
redes, en su mayoría optimizar de redes, nos ayudan a tomar decisiones y elegir la
mejor forma de actuar dependiendo del tipo de respuesta que busquemos, ya sea
maximizar una ruta, reducir el costo o material, o en su caso el flujo.
Es muy importante conocer las diferentes herramientas que nos ofrece investigación
de operaciones, así cuando tengamos un proyecto en nuestra manos, y
necesitemos encontrar la optima respuesta, poder recurrir a estas herramientas.
Fuentes
https://revistamarina.cl/revistas/2007/4/molina.pdf
https://www.zonaeconomica.com/metodo-pert-cpm/areas
https://www.eoi.es/blogs/madeon/2013/04/14/metodo-de-ruta-critica-cpm-critical-
path-method/
http://calculemoscostos.blogspot.com/
https://operaciongadget.blogspot.com/2017/10/costo-minimo.html
https://www.ingenieriaindustrialonline.com/investigacion-de-operaciones/algoritmo-
de-la-ruta-mas-corta/
https://www.academia.edu/17257056/PROBLEMA_DE_LA_RUTA_M%C3%81S_C
ORTA
https://www.inf.utfsm.cl/~esaez/fio/s2_2003/apuntes/grafos_s2_2003.pdf
https://www.academia.edu/17383425/FLUJO_MAXIMO_INVESTIGACION_OPER
TATIVA_II
https://www.academia.edu/6268497/1_C_%C3%81RBOL_DE_EXPANSI%C3%93
N_M%C3%8DNIMA
https://1library.co/document/lzg65r8q-investigacion-operaciones-encuentro-
optimizacion-problema-expansion-minima-problema.html