Modelo de Transporte
Páginas: 17 (4058 palabras)
Publicado: 17 de mayo de 2015
Capítulo 4
Modelo de Redes
Objetivos del Capítulo
Conceptos y definiciones de redes.
Importancia de los modelos de redes
Modelos de programación lineal, representación
en redes y soluciones usando el computador para:
* Modelos de transporte.
* Modelos de capacidad de transporte
* Modelos de asignación
* Modelo del vendedor viajero
* Modelos de la ruta mas corta
* Modelos de la rama mascorta
6
8
Un problema de redes es aquel que puede
representarse por:
10
9
7
Nodos
10
Arcos
Funciones en los arcos
4.1 Introducción
La importancia de los modelos de redes:
* Muchos problemas comerciales pueden ser resueltos a
través de modelos redes
* El resultado de un problema de redes garantiza una solución
entera, dada su estructura matemática. No se necesitan
restriccionesadicionales para obtener este tipo de solución.
* Problemas de redes pueden ser resueltos por pequeños
algoritmos , no importando el tamaño del problema, dada su
estructura matemática.
Terminología de Redes
* Flujo: Corresponde a la cantidad que debe transportarse
desde un nodo i a un nodo j a través de un arco que los
conecta. La siguiente notación es usada:
Xij= cantidad de flujo
Uij= cotamínima de flujo que se debe transportar
Lij= cota maxíma de flujo que se puede transportar.
* Arcos dirigidos /no dirigidos: Cuando el flujo puede
transportarse en una sola dirección se tiene un arco dirigido
(la flecha indica la dirección). Si el flujo puede transportarse
en ambas direcciones existe un arco no dirigido (sin flecha).
* Nodos adyacentes: Un nodo j es adyacente con un nodo
i si existe unarco que une el nodo j con el nodo i.
Rutas/Conexión entre nodos
*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.
* Arbol : Una serie de nodos que nocontienen ciclos.
*Arbol expandido: Es un árbol que conecta todos lo
nodos de la red (contiene n-1 arcos).
4.2 Problemas de transporte
Un problema de transporte surge cuando
se necesita un modelo costo-efectividad que
permita transportar ciertos bienes desde un
lugar de origen a un destino que necesita
aquellos bienes , con ciertas restricciones en la
cantidad que se puede transportar.1
Definición del problema
* Se tienen m lugares de origen. Cada lugar de origen
tiene una capacidad de producción Si
*Se tienen n destinos. Cada destino j demanda D j
*Objetivo:
Minimizar el costo de transporte de la carga al lugar de
destino
cumpliendo con las restricciones de los lugares de
origen.
Farmacéutica Carlton
La farmacéutica Carlton abastece de drogas y
otros suministrosmédicos.
Esta tiene tres plantas en: Claveland, Detroit,
Greensboro.
Tiene cuatro centros de distribución en:
Boston, Atlanta, St Louis.
La gerencia de Carlton desea realizar el
trnsporte de sus productos de la manera más
económica posible.
Datos
Costo de transporte por unidad, oferta y demanda.
Desde
Cleveland
Detroit
Greensboro
Demanda
Boston
$35
37
40
1100
Richmond
30
40
15
400
HaciaAtlanta
40
42
20
750
St. Louis
32
25
28
750
Supuestos
* El costo de transporte por unidad es constante
* Todos los transportes ocurren simultáneamente.
* Solo se considera el costo de transporte entre el lugar de
origen y el de destino
* La oferta total es igual a la demanda total.
Oferta
1200
1000
800
RED QUE REPRESENTA
EL PROBLEMA
Origenes
Destinos
D1=1100
Boston
35
30
Cleveland
S1=120040
32
37
Detroit
S2=1000
25
35
Greensboro
S3= 800
40
42
D2=400
Atlanta
15
20
28
Richmond
D3=750
St.Louis
D4=750
Modelo matemático
* La estructura del modelo es la siguiente:
Minimizar
sujeto a :
cantidad a transportar desde la fabrica = oferta de la
fábrica
cantidad a recibir por la distribuidora = demanda de la
distribuidora.
* Variables de...
Modelo de Redes
Objetivos del Capítulo
Conceptos y definiciones de redes.
Importancia de los modelos de redes
Modelos de programación lineal, representación
en redes y soluciones usando el computador para:
* Modelos de transporte.
* Modelos de capacidad de transporte
* Modelos de asignación
* Modelo del vendedor viajero
* Modelos de la ruta mas corta
* Modelos de la rama mascorta
6
8
Un problema de redes es aquel que puede
representarse por:
10
9
7
Nodos
10
Arcos
Funciones en los arcos
4.1 Introducción
La importancia de los modelos de redes:
* Muchos problemas comerciales pueden ser resueltos a
través de modelos redes
* El resultado de un problema de redes garantiza una solución
entera, dada su estructura matemática. No se necesitan
restriccionesadicionales para obtener este tipo de solución.
* Problemas de redes pueden ser resueltos por pequeños
algoritmos , no importando el tamaño del problema, dada su
estructura matemática.
Terminología de Redes
* Flujo: Corresponde a la cantidad que debe transportarse
desde un nodo i a un nodo j a través de un arco que los
conecta. La siguiente notación es usada:
Xij= cantidad de flujo
Uij= cotamínima de flujo que se debe transportar
Lij= cota maxíma de flujo que se puede transportar.
* Arcos dirigidos /no dirigidos: Cuando el flujo puede
transportarse en una sola dirección se tiene un arco dirigido
(la flecha indica la dirección). Si el flujo puede transportarse
en ambas direcciones existe un arco no dirigido (sin flecha).
* Nodos adyacentes: Un nodo j es adyacente con un nodo
i si existe unarco que une el nodo j con el nodo i.
Rutas/Conexión entre nodos
*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.
* Arbol : Una serie de nodos que nocontienen ciclos.
*Arbol expandido: Es un árbol que conecta todos lo
nodos de la red (contiene n-1 arcos).
4.2 Problemas de transporte
Un problema de transporte surge cuando
se necesita un modelo costo-efectividad que
permita transportar ciertos bienes desde un
lugar de origen a un destino que necesita
aquellos bienes , con ciertas restricciones en la
cantidad que se puede transportar.1
Definición del problema
* Se tienen m lugares de origen. Cada lugar de origen
tiene una capacidad de producción Si
*Se tienen n destinos. Cada destino j demanda D j
*Objetivo:
Minimizar el costo de transporte de la carga al lugar de
destino
cumpliendo con las restricciones de los lugares de
origen.
Farmacéutica Carlton
La farmacéutica Carlton abastece de drogas y
otros suministrosmédicos.
Esta tiene tres plantas en: Claveland, Detroit,
Greensboro.
Tiene cuatro centros de distribución en:
Boston, Atlanta, St Louis.
La gerencia de Carlton desea realizar el
trnsporte de sus productos de la manera más
económica posible.
Datos
Costo de transporte por unidad, oferta y demanda.
Desde
Cleveland
Detroit
Greensboro
Demanda
Boston
$35
37
40
1100
Richmond
30
40
15
400
HaciaAtlanta
40
42
20
750
St. Louis
32
25
28
750
Supuestos
* El costo de transporte por unidad es constante
* Todos los transportes ocurren simultáneamente.
* Solo se considera el costo de transporte entre el lugar de
origen y el de destino
* La oferta total es igual a la demanda total.
Oferta
1200
1000
800
RED QUE REPRESENTA
EL PROBLEMA
Origenes
Destinos
D1=1100
Boston
35
30
Cleveland
S1=120040
32
37
Detroit
S2=1000
25
35
Greensboro
S3= 800
40
42
D2=400
Atlanta
15
20
28
Richmond
D3=750
St.Louis
D4=750
Modelo matemático
* La estructura del modelo es la siguiente:
Minimizar
sujeto a :
cantidad a transportar desde la fabrica = oferta de la
fábrica
cantidad a recibir por la distribuidora = demanda de la
distribuidora.
* Variables de...
Leer documento completo
Regístrate para leer el documento completo.