Tema 2

Programación Lineal
Método de transporte

1
2.1 Modelo de Transporte

El objetivo general es encontrar el mejor plan de distribución, es

decir, la cantidad que se debe enviar por cada una de las rutas
desde los puntos de suministro hasta los puntos de demanda.
El “mejor plan” es aquel que minimiza los costos totales de envío,
produzca la mayor ganancia u optimice algún objetivo corporativo.
Se debe contar con:

i) Nivel de oferta en cada fuente y la cantidad de demanda

en cada destino.
ii) Costo de transporte unitario de mercadería desde cada
fuente a cada destino.
2
 2.1 Modelo de Transporte

También es necesario satisfacer ciertas restricciones:

1. No enviar más de la capacidad especificada desde cada punto de

suministro (oferta).
2. Enviar bienes solamente por las rutas válidas.
3. Cumplir (o exceder) los requerimientos de bienes en los puntos
de demanda.

3
 2.1 Modelo de Transporte
Gráficamente: Para m fuentes y n destinos

Esquemáticamente se podría ver como se muestra en la siguiente

figura
Fuentes Destinos
C11, X11
1 1 d1
s1
Unidades de oferta

Unidades de demanda
s2 2 2 d2

sm m dn
Cmn, Xmn
n

donde Xij: cantidad transportada desde la fuente i al destino j

Cij: Costo del transporte unitario desde la fuente i al destino j
4
 2.1 Modelo de Transporte

Modelo general de PL que representa al modelo de Transporte

m n
minimizar Z   cij xij
i 1 j 1

n
sa x
j 1
ij  si i=1,2,...,m
m

x
i 1
ij  dj j=1,2,...,n
xij  o para toda i y j

El modelo implica que al menos la oferta debe ser igual a la demanda

5
 2.1 Modelo de Transporte

Modelo general de PL que representa al modelo de Transporte

Modelo de transporte equilibrado: Oferta = Demanda

x
j 1
ij  Si i=1, 2, 3,....,m

x
i 1
ij  Dj j=1, 2, 3,....,n

xij  0 para toda i y j

6
 2.1 Modelo de Transporte

Aplicaciones del modelo de Transporte

El Modelo de Transporte no sólo es aplicable al movimiento de

productos, sino que también, como modelo se puede aplicar a otras
áreas tales como:
• Planificación de la Producción
• Control de Inventarios
• Control de Proveedores
• Otras

7
 2.1 Modelo de Transporte

Ejemplo:

RPG tiene cuatro plantas ensambladoras en Europa. Están

ubicadas en Leipzig, Alemania (1);Nancy, Francia (2); Lieja,
Bélgica (3), y Tilburgo, Holanda (4). Las máquinas
ensambladoras usadas en estas plantas se producen en Estados
Unidos y se embarcan a Europa. Llegaron a los puertos de
Amsterdan (1), Amberes (2) y El Havre (3).
Los planes de producción del tercer trimestre (julio a
septiembre) ya han sido formulados. Los requerimientos (la
demanda en destinos) de motores diesel E-4 son los
siguientes:
 2.1 Modelo de Transporte

Planta Cantidad de Motores

(1) Leipzig 400
(2) Nancy 900
(3) Lieja 200
(4) Tilburgo 500
Total 2000

La cantidad disponible de máquinas E-4 en los puertos(oferta en

orígenes) son:

Puerto Cantidad de Motores

(1) Amsterdan 500
(2) Amberes 700
(3) El Hevre 800
Total 2000
 2.1 Modelo de Transporte
Los costos ($) de transporte de un motor
desde un origen a un destino son:

Al destino
Desde el
origen
1 2 3 4
1 12 13 4 6

2 6 4 10 11

3 10 9 12 4

10
 Construcción del modelo de PL 2.1 Modelo de Transporte

1. Variables de decisión

Xij = número de motores enviados del puerto i a la planta j

i = 1, 2, 3
j = 1, 2, 3, 4

2. Función Objetivo

Minimizar Z = 12 X11 + 13 X12 + 4X13 + 6X14 + 6X21 + 4X22 +

10X23 + 11X24 + 10X31 + 9X32 + 12X33 + 4X34

11
3. Restricciones: 2.1 Modelo de Transporte

1) Oferta: La cantidad de elementos enviados no puede exceder la

cantidad disponible
X11 + X12 + X13 + X14  500
X21 + X22 + X23 + X24  700
X31 + X32 + X33 + X34  800
2) Demanda: Debe satisfacerse la demanda de cada planta
X11 + X21 + X31  400
X12 + X22 + X32  900
X13 + X23 + X33  200
X14 + X24 + X34  500
y de no negatividad Xij  0 para i=1, 2, 3; j= 1, 2, 3, 4

12
 2.1 Modelo de Transporte

Solución del Modelo de

Transporte
 2.1 Modelo de Transporte

Algoritmos Específicos
2.1.1 Regla de la esquina noroeste (MEN)
2.1.2 Método del costo mínimo (MCM)
2.1.3 Método por aproximación de Vogel (MAV)
2.1.4 Método por aproximación de Russel (MAR)

14
 2.1 Modelo de Transporte

Descripción de los algoritmos

La regla de la esquina noroeste, el método de aproximación
de Vogel y el método del costo mínimo son alternativas para
encontrar una solución inicial factible.

El método del escalón y el DIMO son alternativas para

proceder de una solución inicial factible a la óptima.

Por tanto, el primer paso es encontrar una solución inicial

factible, que por definición es cualquier distribución de
ofertas que satisfaga todas las demandas

15
 2.1 Modelo de Transporte

Descripción de los algoritmos

Una vez obtenida una solución básica factible, el algoritmo
procede paso a paso para encontrar un mejor valor para la
función objetivo.
La solución óptima es una solución factible de costo mínimo

Para aplicar los algoritmos, primero hay que construir una

tabla de transporte.

16
 2.1 Modelo de Transporte

Tabla Inicial
Destinos
Origen 1 2 3 4 n Ofertas
1 C11 C12 C13 C14 .... C1n

2 C21 C22 C23 C24 .... C2n

3 C31 C32 C33 C34 .... C3n

... .... ..... .... .... ....

m Cm1 Cm2 Cm3 Cm4 .... Cmn

Demanda

17
 2.1 Modelo de Transporte

Tabla Inicial del Ejemplo

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 200 500 2000

18
 2.1 Modelo de Transporte

2.1.1 Regla de la esquina Noroeste

Se inicia el proceso desde la esquina izquierda superior

Se ubican tantas unidades como sea posible en la ruta

Cantidad de Unidades = Mínimo(disponibilidad, demanda)

Las siguientes asignaciones se hacen o bien recorriendo hacia la

derecha o bien hacia abajo.
Las demandas se satisfacen recorriendo sucesivamente de
izquierda a derecha y las ofertas se destinan recorriendo de
arriba hacia abajo.

19
 2.1 Modelo de Transporte

Primera asignación

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
400 100 500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 0 400 900 200 500 2000

20
 2.1 Modelo de Transporte

Hasta cuarta asignación

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
400 100 100 500
2 6 4 10 11
700 0 700
3 10 9 12 4
100 700 800
Demanda 0 400 0 900 200 500 2000

21
 2.1 Modelo de Transporte

Esquina Noroeste: Solución final factible

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
400 100 100 500
2 6 4 10 11
700 0 700
3 10 9 12 4
100 200 500 0 800
Demanda 0 400 0 900 200 500 2000

Valor FO: 400*12+100*13+700*4+100*9+200*12+500*4= $14.200

22
 2.1 Modelo de Transporte

2.1.2 Método de aproximación de

Vogel (MAV)
MAV usa información de costos mediante el concepto de
costo de oportunidad para determinar una solución inicial
factible.
Seleccionar en una fila la ruta más barata y la que le sigue.
Hacer su diferencia (penalidad), que es el costo adicional por
enviar una unidad desde el origen actual al segundo destino y
no al primero.
En nuestro caso, para el puerto1, C13 y C14; Penalidad = 6 - 4
MAV asigna un costo de penalidad por no usar la mejor ruta
en esta fila.
23
 2.1 Modelo de Transporte
2.1.2 Método de aproximación de Vogel
Lo anterior se repite para cada fila y cada columna, esto es,
determinar todas las penalidades
Los pasos iterativos de MAV son los siguientes:
1. Identificar la fila o columna con la máxima penalidad.
2.Colocar la máxima asignación posible a la ruta no usada que
tenga menor costo en la fila o columna seleccionada en el punto
1 (los empates se resuelven arbitrariamente)
3. Reajustar la oferta y demanda en vista de esta asignación.
4. Eliminar la columna en la que haya quedado una demanda 0 (o
la fila con oferta 0), de consideraciones posteriores.
5. Calcular los nuevos costos de penalidad.
24
 2.1 Modelo de Transporte

2.1.2 Método de aproximación de Vogel

El MAV continúa aplicando este proceso en forma sucesiva

hasta que se haya obtenido una solución factible.

Los resultados obtenidos se muestran en las siguientes tablas

25
 2.1 Modelo de Transporte

2.1.2 Método de aproximación de Vogel

Paso 0: Cálculo de penalidades
Plantas
Puertos 1 2 3 4 Oferta Penalidades
1 12 13 4 6 2
500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 200 500 2000

Penalidades 4 5 6 2
Paso 1: Identificar máxima penalidad (fila o columna)

Calculadas todas las penalidades, la mayor

corresponde a la columna 3 (penalidad = 6)
26
2.1.2 Método de aproximación de Vogel
2.1 Modelo de Transporte

Paso 2: Asignación de unidades (MIN(oferta,demanda))

Paso 3:Reajuste de oferta y demanda

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 0 200 500 2000

27
2.1.2 Método de aproximación de Vogel
2.1 Modelo de Transporte

Paso 4: Eliminar columna (fila) con demanda (oferta) 0

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 0 200 500 2000

28
2.1.2 Método de aproximación de 2.1 Modelo de Transporte

Vogel
Paso 5: Calcular los nuevos costos de penalidad

Plantas
Puertos 1 2 3 4 Oferta Penalidades
1 12 13 4 6 6
200 300 500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 0 200 500 2000

Penalidades 4 5 2

29
2.1.2 Método de aproximación de Vogel
2.1 Modelo de Transporte

Repitiendo los pasos anteriores, finalmente se llega a la siguiente

solución

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 300 500
2 6 4 10 11
700 0 700
3 10 9 12 4
400 200 200 600 800
Demanda 400 900 0 200 200 500 2000

¿Es solución factible? ¿m + n - 1 = 6? SI

Costo: 200*4+300*6+700*4+400*10+200*9+200*4 = $12.000

30
2.1.3. Método del Costo Mínimo
2.1 Modelo de Transporte

Fundamento
Asignar la mayor cantidad de unidades a una ruta
disponible de costo mínimo
Algoritmo

1. Dada una tabla de transporte

2. Asignar la mayor cantidad de unidades a la variable
(ruta) con el menor costo unitario de toda la tabla.
3. Tachar la fila o columna satisfecha.
4. Ajustar oferta y demanda de todas las filas y columnas
5. Si hay más de una fila o columna no tachada repetir
los puntos 2, 3 y 4
31
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Ejemplo: Aplicar MCM a la tabla de transporte

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 200 500 2000

Paso 2 Existen tres rutas costo mínimo. Elijamos la 1_3

Unidades a asignar = MIN(200,500) = 200
32
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 3: Tachar fila o columna (columna 3)

Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 0 200 500 2000

Paso 4 Ajustar ofertas y demandas (fila 1 y columna 3)

Paso 5 Aún quedan más de una fila o columna sin tachar. Ir a paso 2
33
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_4 (ó 2_2)

Unidades = MIN(500,800) = 500
Paso 3: Tachar columna 4
Paso 4: Tachar ajustar fila 3 y columna 4
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700
3 10 9 12 4
500 300 800
Demanda 400 900 0 200 0 500 2000

Paso 5 Aún quedan más de una fila o columna sin tachar. Ir a paso 2
34
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 2_2

Unidades = MIN(700,900) = 300
Paso 3: Tachar fila2
Paso 4: Tachar ajustar fila 2 y columna 2
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 0
700 0 700
3 10 9 12 4
500 300 800
Demanda 400 200 900 0 200 0 500 2000

Paso 5 Aún quedan más de una fila o columna sin tachar. Ir a paso 2
35
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_2

Unidades = MIN(200,300) = 200
Paso 3: Tachar columna 2
Paso 4: Tachar ajustar fila 3 y columna 2
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 0
700 0 700
3 10 9 12 4 100
200 500 300 800
Demanda 400 200 900 0 200 0 500 2000

Paso 5 Aún quedan más de una fila o columna sin tachar. Ir a paso 2
36
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_1

Unidades = MIN(400,100) = 100
Paso 3: Tachar fila 3
Paso 4: Tachar ajustar fila 3 y columna 1
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 0
700 0 700
3 10 9 12 4 100 0
100 200 500 300 800
Demanda 300 400 200 900 0 200 0 500 2000

Paso 5 Aún quedan más de una fila o columna sin tachar. Ir a paso 2
37
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 1_1

Unidades = MIN(300,300) = 300
Paso 3: Tachar fila 1 ó columna 1 (sólo una de ellas)
Paso 4: Tachar ajustar fila 1 y columna 1
Puertos 1 2 3 4 Oferta
1 12 13 4 6 0
300 200 300 500
2 6 4 10 0
700 0 700
3 10 9 12 4 100 0
100 200 500 300 800
Demanda 300 400 200 900 0 200 0 500 2000

Paso 5 Queda sólo una fila sin tachar. Terminar

38
2.1.3. Método del Costo Mínimo (cont.)
2.1 Modelo de Transporte

¿Es solución factible? ¿m + n - 1 = 6? SI

Costo: 300*12+200*4+700*4+100*10+200*9+500*4 = $12.000

Comparación de los resultados

Método Rutas Costo

MEN 6 $14.200
MAV 6 $12.000
MCM 6 $12.000

Conclusión
Los tres métodos entregan soluciones básicas factibles,
pero ninguno asegura que la solución sea óptima.
39