Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Ruta: Una colección de arcos formados por una serie de nodos adyacentes; los nodos están
conectados si existe una ruta entre ellos.
Ciclos / Arboles /Arboles expandidos
Ciclos: Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo
nodo por otra ruta.
Árbol: Una serie de nodos que no contienen ciclos.
Árbol expandido: Es un árbol que conecta todos lo nodos de la red (contiene n-1 arcos).
2.2. Problema de Transporte
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a
varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.
Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El
objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se
minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente
proporcional al número de unidades transportadas. La definición de “unidad de transporte” variará
dependiendo de la “mercancía” que se transporte.
El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos.
Una fuente o un destino están representado por un nodo, el arco que une fuente y un destino, representa la
ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es a i , y la demanda en el
destino j es b j . El costo de transporte unitario entre la fuente i y el destino j es C ij .
34