metodo de transporte

UNIDAD N°4
CASOS ESPECIALES DE
PROGRAMACIÓN LINEAL
Problema de transporte

Definición del problema
Determinación de un plan de costo mínimo
para transportar una mercancía desde varias
fuentes (plantas) a varios destinos
(almacenes o bodegas). Este modelo se
puede adaptar de manera directa a
situaciones de programación de empleo y
asignación de personal.

Formulación de un modelode PL
El problema de transporte puede resolverse con un
modelo de programación lineal.
Modelo:
Variables de decisión: Xij
F.O.: Minimizar costos de transporte
Restricciones:
1. Capacidad máxima de almacén
2.- Demanda máxima para cada planta

Problema de transporte
Debido a la estructura especial de este
problema se puede utilizar un algoritmo
diseñado para este tipo de problema.Algoritmos:
• La regla de la esquina noroeste
• El método de aproximación de Vogel
• El método del paso secuencial
• El método de distribución modificada.

Propósitos de los algoritmos
Para hallar una solución factible inicial:
Método de la esquina noroeste y método de
aproximación de Vogel.
Para hallar una solución óptima: el método del
paso secuencial y el método de distribuciónmodificada.

Ejemplo
La compañía SunRay Transport transporta grano
desde tres silos hasta cuatro molinos. La oferta (en
camionadas) y la demanda (también en
camionadas) se resume en la tabla de transporte
siguiente, junto con los costos unitarios de
transporte por camionada en las distintas rutas, los
cuales se ven en la esquina noreste de cada
recuadro (en cientos de $). Se busca el programade transportes entre silos y molinos que tenga
costo mínimo. Eso equivale a determinar la
cantidad Xij transportada del silo i al molino j (i =
1, 2, 3; j = 1, 2, 3, 4).

Ejemplo - Tabla de transporte
Molino
1

2
10

1

x11

2
x12

12
Silo 2

x21

Demanda

4
20

x13
7

x22
4

3

3

11
x14

9
x23

14

Oferta
15
20

x24
16

25
18

x31

x32x33

x34

5

15

15

15

10

Regla de la esquina noroeste
1.- Comience en la esquina superior izquierda
(origen 1, destino 1) y asigne a esa celdilla
tantas unidades como sea posible. Esto es,
use toda la oferta del origen 1 que se pueda,
para satisfacer la demanda del destino 1.
Esto significa que la cantidad asignada será
el mínimo entre la oferta en 1 y la demanda
en1.

Regla de la esquina noroeste
2.- Reduzca la oferta actual disponible del
origen y la demanda actual insatisfecha del
destino en la capacidad asignada.
3.- Identifique el primer origen con oferta
disponible. Esto es o bien el origen actual o
el que está directamente abajo.

Regla de la esquina noroeste
4.- Identifique el primer destino con demanda
insatisfecha. Este es o bien eldestino actual o el
que está inmediatamente a la derecha de él.
5.- Asigne, como en el paso 1, tantos artículos como
sea posible a la ruta asociada con la combinación
de origen-destino identificados en los pasos 3 y 4.
6.- Regreso al paso 2.

Ejemplo - Regla de la esquina
noroeste
Molino
1

2
10

1

5

3
2

20

11
15

7

5

Silo 2
4

9

15
14

20

5
1615

15

25
18

10

3
5

Oferta

10
12

Demanda

4

15

10

Ejemplo - Regla de la esquina
noroeste
• Solución factible inicial:
x11 = 5, x12= 10
x22 = 5, x23 = 15, x24 = 5
x34 = 10

• Costo = $520

Método de aproximación de Vogel
1. Para cada renglón con una oferta disponible
y cada columna con una demanda
insatisfecha calcule un costo de penalidad
restandoel dato menor del que le sigue en
valor.
2. Identifique el renglón o columna que
tengan mayor costo de penalidad (los
empates se resuelven arbitrariamente).

Método de aproximación de Vogel
3. Asigne la máxima cantidad posible a la ruta
disponible que tenga el costo más bajo en el
renglón o columna elegida en el paso 2.
4. Reduzca la oferta y la demanda adecuados
en la cantidad...