Este documento describe tres algoritmos para resolver problemas de transporte: el método de la esquina noroeste, el método del costo mínimo y el método de Vogel. Explica cómo cada método asigna cantidades a transportar entre fuentes y destinos de manera iterativa para minimizar los costos de transporte totales sujeto a restricciones de oferta y demanda.
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
Este documento describe tres algoritmos para resolver problemas de transporte: el método de la esquina noroeste, el método del costo mínimo y el método de Vogel. Explica cómo cada método asigna cantidades a transportar entre fuentes y destinos de manera iterativa para minimizar los costos de transporte totales sujeto a restricciones de oferta y demanda.
Este documento describe tres algoritmos para resolver problemas de transporte: el método de la esquina noroeste, el método del costo mínimo y el método de Vogel. Explica cómo cada método asigna cantidades a transportar entre fuentes y destinos de manera iterativa para minimizar los costos de transporte totales sujeto a restricciones de oferta y demanda.
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
Este documento describe tres algoritmos para resolver problemas de transporte: el método de la esquina noroeste, el método del costo mínimo y el método de Vogel. Explica cómo cada método asigna cantidades a transportar entre fuentes y destinos de manera iterativa para minimizar los costos de transporte totales sujeto a restricciones de oferta y demanda.
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
Descargar como pptx, pdf o txt
Está en la página 1/ 29
Algoritmos de transporte
Diana Katherinne Robayo
Eida Lucena Huertas Martínez AGENDA
1. Definición Algoritmo de Transporte
2. Fuente y Destino Ficticios
3. Métodos del algoritmo de
Transporte
3.1 Método de la esquina noroeste
(superior, izquierda) 3.2 Método del costo mínimo 3.3 Método de aproximación de Vogel 2 Recordemos que… > El modelo de Transporte es una clase especial de programación lineal que tiene que ver con transportar un articulo desde sus Fuentes hasta sus Destinos > El Problema general se representa en forma de red donde hay m fuentes y n destinos. Cada destino representado por un nodo y los arcos que representan las rutas que enlazan los destinos. > Arco (i,j) y la fuente (i) y el destino (j) 3 Recordemos que…
FUENTES Y DESTINOS FICTICIOS 5 Fuente y Destino Ficticios
Modelo BALANCEADO --->>
Demanda Total = Oferta Total
Modelo NO BALANCEADO --->>
Aumentar una fuente o un destino Ficticio
6 Ejemplo
7 Se agrega renglón ficticio:
8 MODELO DE TRANSPORTE
ALGORITMOS DE TRANSPORTE 9 EJERCICIO Tres Compañías, C1, C2 y C3 pueden abastecer 50, 50 y 75 (miles) de botellas de agua, respectivamente, a la semana.
Cuatro grandes Bodegas B1, B2, B3 y B4 requieren cada semana 40,
55, 60 y 20 (miles de botellas de agua).
Los Costos de envió son:
De la compañía 1: $3, $1, $4 y $5 para cada una de las 4 bodegas
De la compañía 2: $7, $3, $8 y $6 para cada una de las 4 bodegas De la compañía 3: $2, $3, $9 y $2 para cada una de las 4 bodegas
No negatividad m x11 , x12 , x13 , x14 , x21 , x22 , x23 , x24 , x31 , x32 , x33 , x34 >= 0 11 Tabla de Transporte O F D1 D2 DESTINOS D3 D4 E R O1 T 3 1 4 COSTOS 5
A
S X11 X12 X13 X14 50 O2 7 3 8 6 X21 X22 X23 X24 50 O3 2 3 9 2 X31 X32 X33 X34 75 40 55 60 20 12 Algoritmos De transporte 1. Método Esquina Noreste 1. Nos Situamos en la celda Superior Izquierda (X11) 2. Asignar todo lo que mas se pueda con tal de cumplir con la oferta y demanda. 3. Escogemos el valor mas pequeño
D1 D2 D3 D4 O1 3 1 4 5 40 50 O2 7 3 8 6 50 O3 2 3 9 2 75 40 55 60 20 14 > 1. Método Esquina Noreste 4. Marcamos la columna o fila que ya cumplió con su oferta o demanda. 5. Avanzar hacia la derecha si se marco una columna o hacia abajo si se marco una fila.
16 Algoritmos De transporte 2. Método del Costo Mínimo Este Método plantea una solución desde el inicio ya que se concentra en rutas menos costosas, si se satisfacen en forma simultanea una columna o una sola se tacha una de las dos. 1. SELECCIONAMOS Cij CON MENOR COSTO. 2. PARA SATISFACER LA FILA Y LA COLUMNA TOMAMOS LA OFERTA O LA DEMANDA MAS PEQUEÑA. 3. SELECCIONAMOS LA SIGUIENTE CELDA CON MENOR COSTE Y SATISFACEMOS CON LA OFERTA O DEMANDA
19 Algoritmos De transporte 2. Método Voguel Es una versión mejorada del método del costo mínimo, en el cual se plantean mejores soluciones. 1. CALCULAR LA GANANCIA DE CADA COLUMNA Y FILA DE OFERTA Y DEMANDA, RESTANDO LOS DOS COSTES DE MENOR VALOR.
21 2. Identificar la FILA con mayor ganancia y el elemento de menor COSTO 3. Intentamos satisfacer la DEMANDA con la cantidad de la OFERTA.
En algunos D1 1D2 2D3 4D4 3
casos no se O1 pueden 3 1 4 5 satisfacer las 2 50 demandas, O2 así que 7 3 8 6 intentamos satisfacer las ofertas 3 50
O3 2 3 9 2
0 60 75
40 55 60 20
22 4. Identificar la COLUMNA con MAYOR ganancia y el elemento de menor COSTE. 5. Intentamos satisfacer la DEMANDA con la OFERTA. 6. Al satisfacer la demanda marcamos la columna o fila. 7. DEVOLVEMOS AL PASO 1
D1 1D2 2D3 4D4 3
O1 3 1 4 5
2 50
O2 7 3 8 6
3 50
O3 2 3 9 2 55 DIFERENCIA
0 20 75
40 55 60 20
23 1. CALCULAR LA GANANCIA DE CADA COLUMNA Y FILA DE OFERTA Y DEMANDA, RESTANDO LOS DOS COSTES DE MENOR VALOR. 2. Identificar la FILA con mayor ganancia y el elemento de menor COSTO 3. Intentamos satisfacer la OFERTA con la cantidad de la DEMANDA.
D1 1D2 2D3 4D4
O1 3 1 4 5
2 50 50
O2 7 3 8 6
4 50
O3 2 3 9 2 55
1 20 75
40 55 60 10 20
DIFERENCIA 24 1. CALCULAR LA GANANCIA DE CADA COLUMNA Y FILA DE OFERTA Y DEMANDA, RESTANDO LOS DOS COSTES DE MENOR VALOR. 2. Identificar la FILA con mayor ganancia y el elemento de menor COSTO 3. Intentamos satisfacer la demanda con la cantidad de la oferta. D1 5D2 0D3 1D4
O1 3 1 4 5
50 50
O2 7 3 8 6
4 50
O3 2 3 9 2 15
1 40 20 75
40 55 60 10 20
25 PUNTOS CLAVE: 1. Las columnas o filas que ya están marcadas no se tienen en cuenta para el calculo de las ganancias. 2. Tener en cuenta la diferencia del total de las ofertas para saber cuanto hace falta para satisfacerlas.
D1 5D2 0D3 1D4
O1 3 1 4 5
50 50
O2 7 3 8 6 40
5 10 50
O3 2 3 9 2 15
6 40 20 75
40 55 60 10 20
26 PUNTOS CLAVE: 1. Cuando ya tenemos solo una columna o fila no podemos hallar la diferencia entre los costes. Por lo tanto intentamos satisfacer las DEMANDAS con las diferencias.
D1 5D2 0D3 1D4
O1 3 1 4 5
50 50
O2 7 3 8 6 40 DIFERENCIA
NO 40 10 50
O3 2 3 9 2 15
NO 40 15 20 75
40 55 60 10 20 27
Valor Objetivo Asociado a la solución. > X13=50 > X22=40, X23=10 > X31=40, X32=15, X34=20
