OBJETIVOS

- Introducir los temas de redes y transporte.

- Entender la relación entre las redes y los problemas de programación lineal.
- Demostrar que un problema de redes se puede expresar como un modelo matemático
de programación lineal.
- Hallar la solución a través de un paquete como SOLVER.

INTRODUCCION

MODELO DE REDES

Los modelos de redes los utilizaremos en muchos de los problemas de optimización que
encontraremos. Estos problemas serán por lo general problemas reales, como los de
transporte o flujo de activos y recursos. En su mayoría los problemas de redes serán más que
una simple representación simbólica de procesos o actividades, como el del camino crítico en
los procesos entre las redes de una gestión administrativa. Los mismo serán representados de
manera sencilla utilizando arcos de redes, y nodos.

Definición del modelo de red

En general, cualquier sistema que represente gráficamente un proceso que requiera una serie
de actividades entrelazadas para llevar energía-materia o información a través de referencias
geográficas bien definidas, tal como podrían ser un mapa de carreteras, un tendido eléctrico o
una red de internet, lo podríamos simbolizar o describir por medio de una red. Que al ser una
representación de un entorno real le llamaremos modelo de red, así como los siguientes:

Modelo de Transporte y costo mínimo de flujos- Modelo de Camino más corto- Modelo de
Problemas de asignación- Modelo de Flujo máximo- Modelo de Camino crítico.

Los problemas serán establecidos fácilmente mediante el uso de arcos de redes y de los nodos,
y contarán con terminología exclusiva, necesaria para su descripción e interpretación.

Presentaremos a continuación la notación y terminología que utilizaremos.

Nodo

Denominado también vértice, o punto. Representado generalmente por un círculo. En las redes
de transporte, serán las localidades o ciudades en un mapa (grafico 1).

Grafico1. Representación gráfica de un nodo.

Arco

Denominado también borde o flecha. Este podría ser directo o indirecto. La cabeza es el
destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen
como al final. En las redes de transporte, los arcos podrían ser los caminos, los canales de
navegación en un río, o los patrones de vuelo de un avión. Los arcos proporcionan la
conectividad entre los nodos. Una calle de una sola dirección podría ser representada por un
arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o
por dos arcos que apuntan a direcciones opuestas.

Grafico2. Representación gráfica de un arco.

• Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a
otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y que
se compone por los elementos [1-4, 4-7].

Gráfico 3. Representación gráfica de una cadena.

• Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente tenemos
[1, 4, 7].

Gráfico 4. Representación gráfica de una ruta.

Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente
ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].

Gráfico 5. Representación gráfica de un ciclo.

• Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es
decir que posee un nodo fuente y un nodo destino.

Gráfico 6. Representación gráfica de un ramal orientado.

Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran
orientados

Gráfico 7. Representación gráfica de un arco.

• Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

• Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la
red, de igual manera no permite la existencia de ciclos.

Gráfico 8. Representación gráfica de un árbol de expansión.

Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran
orientados hacia afuera.

Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran
orientados hacia él.

Modelo ejemplo de Red

Gráfico 9. Representación gráfica de un modelo de red

Los nodos 0 y F representan el origen y destino de la red, mientras que los nodos A, B, C, D y E,
son nodos de trasbordo, el número en los arcos o líneas puede indicar distancia en kilómetros,
por ejemplo, entre nodos adyacentes

DESARROLLO
En este tema observaremos, como los problemas de redes o también llamados de trasbordo
capacitado o limitado, son situaciones de programación lineal, y su modelo matemático
corresponde a uno de PL.

El objetivo en un ejercicio de trasbordo capacitado, es llevar un producto, de un nodo fuente a

un nodo destino, a través de todos los nodos que conforman la red de distribución, con el
menor costo.

Este modelo también llamado modelo de red, es el más general de todos los modelos
desarrollados para este tipo de situaciones.

El diagrama general de redes es:

Diagrama10. Diagrama general de redes

NODOS: 1,2,3, …n…J

Variables de decisión: XIJ=flujo del nodo i al j

(I, J) =ruta de transporte en la red

CIJ: costo de transporte en la red

I<=J

Lj=Oferta total del nodo J.

Si Lj>=0 es un nodo de Oferta (Fuente)

Si Lj<=0 es un nodo Demanda (Sumidero)

Las restricciones del tipo:

Expresan la capacidad de flujo (Lj) de cada uno de los nodos de la red, si el resultado de:

Lj=0

Estará indicando que todo lo que entra-sale; por lo que es simplemente un nodo de
transbordo. El termino Limitado, es referente a la capacidad de oferta o demanda del nodo.

Para poner en práctica el modelo matemático de un problema de flujo de carga(producto),

realizaremos el siguiente ejemplo.

Ejercicio prototípico DISTRIBUIDORA MORALES.

Industria Jaramillo, tiene un distribuidor a nivel nacional de sus molinos chilenos y de Bolas.
Este es DISTRIBUIDORA MORALES, gerenciada por el Sr. Abelardo González.

Don Abelardo distribuye sus Molinos en cinco provincias. En la actualidad, DISTRIBUIDORA

MORALES tiene 10 molinos chilenos M1 en lo que designaremos como la central1. Estos
molinos deben ser enviados a los dos locales de minería más importantes, designados como
distribuidor3(3) y distribuidor 4(4). Se necesitan tres M1 en el 3 y siete M1 en el 4.

Debido a horarios planificados con anterioridad, de los cuales depende la disponibilidad de los
choferes, los molinos chilenos(M1) solamente pueden ser distribuidos de acuerdo con las rutas
alternativas que se muestran en la Gráfico 11:

Gráfico 11. Rutas transporte

El problema de DISTRIBUIDORA MORALES consiste en encontrar un plan de transporte que

satisfaga la demanda a un costo mínimo.

XIJ=número total de M1 enviadas por el arco (i, j) =flujo del nodo i al nodo j
En consecuencia, éste es el modelo:

Z(Min)= c12x12 + c23x23 + c24x24 + c25x25 + c34x34 + c43x43 + c53x53 + c54x54

Sujeto a:

+ x12 =10

-x12 + x23 + x24 + x25 =0

- x23 +x43 +x53 + x34 =3

-x24 -x43 -x34 +x54 =7

-x25 -x53 -x54 =0

Dado que el modelo de DISTRIBUIDORA MORALES es una PL, se puede hallar la solución con
Solver como cualquier otra PL.

Gráfico 12. Datos ingreso DISTRIBUIDORA MORALES

Tabla 1. Formulas usadas en las celdas de la página electrónica de Excel.

Celda Fórmula Cópiese a

J10 = C10*J3 J10:N14

H10 = SUMA (C10:G10) H11:H14

C15 = SUMA (C10:C14) D15:G15

Gráfico 13. Parámetros Solver

Gráfico 14. Resultados de Solver

Figura 15. Solución Solver

El costo mínimo del transporte es de $1615 dólares.

Figura16.Solucion Solver
Flujo obtenido:

x12 =10 M1

x23 =4 M1

x24 =3 M1

x25 =4 M1

x34 =1 M1

x54 =3 M1

Los resultados nos indican que el modelo matemático obtenido, puede tratar un esquema de
redes como un problema de programación lineal.

CONCLUSIONES

La idea principal se llevó a término, al poder interpretar un problema de redes de transporte

como el prototípico presentado (DISTRIBUIDORA MORALES), en su forma de modelo
matemático, y poder resolverlo rápidamente en un paquete como lo es SOLVER.

Lo siguiente que se obtuvo, fue poder iniciar un tema tan interesante como lo es el de las
redes, de una manera práctica, con su propia terminología y puntos de vista de construcción en
términos de redes.

GLOSARIO

• Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas
llamadas ramales o arcos

• Red. Conjunto de puntos llamados nodos (o vértices) y líneas que los unen llamadas arcos (o
ligaduras, aristas o ramas).

•Los arcos se etiquetan con los nombres de los nodos en sus puntos terminales, por ejemplo,
AB es el arco entre los nodos A y B.

• Arcos dirigidos. Un arco es dirigido cuando tiene flujo en una sola dirección y ésta se indica
con una cabeza de fecha al final del arco o línea en la dirección del flujo.

• Arcos no dirigidos. Un arco donde se permite el flujo en ambas direcciones.

• Trayectoria. Sucesión de arcos distintos que conectan dos nodos.

• Trayectoria dirigida. Una trayectoria dirigida del nodo i al nodo j, es una sucesión de arcos
cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a
través de esta trayectoria, es factible.

• Trayectoria no dirigida. Una trayectoria no dirigida del nodo i al nodo j es una sucesión de
arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo j.

• Red dirigida. Es una red que tiene sólo arcos dirigidos. Red no dirigida. Es una red donde
todos sus arcos son no dirigidos.
• Red conexa. Una red conexa es una red en la que cada par de nodos está conectado. Se dice
que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre
ellos aparte. Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la
red sea dirigida.

• Capacidad de arco. Es la cantidad máxima de flujo (quizás infinito) que puede circular en un
arco dirigido.

• Nodo fuente (o nodo de origen). Tiene la propiedad de que el flujo que sale del nodo excede
al flujo que entra a él.

• Nodo demanda (o nodo destino). Es el caso contrario al nodo fuente, donde el flujo que llega
excede al que sale de él.

• Nodo de trasbordo (o nodo intermedio). Satisface la conservación del flujo, es decir, el flujo
que entra es igual al que sale.