PROBLEMAS DE
ASIGNACIÓN Y TRANSPORTE
Método
esquina
Noroeste
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
D R
i a1 C11 b1 e
s q
p u
C1n C12
o e
n C21 r
i i
b
a2 C22 b2 m
i . . i
. C2n .
l . . . . e
i
. Cm1 n
d . . .
am Cm2 t
a bn o
d Cmn s
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Ejm. Método de la esquina noroeste: caso de minimización.
Cuatro expendedores de gasolina A, B, C y D requieren 50000, 40000,
60000 y 40000 galones de gasolina respectivamente. Es posible
satisfacer estas demandas a partir de localidades 1, 2 y 3 que disponen
de 80000, 100000 y 50000 galones respectivamente. Los costos de
despachar 1000 galones de gasolina se presentan en la siguiente tabla.
El problema consiste en determinar las cantidades de gasolina que
deben enviarse desde cada localidad hasta cada expendedor, de manera
que los requerimientos de los distribuidores sean satisfechos y los
costos totales de despacho sean mínimos.Costo de despachar 1000 galones de gasolina
A B C D
1 70 60 60 60
2 50 80 60 70
3 80 50 80 60
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Solución
Expendedor
Localidad Suministro
A B C D Ficticia
70 60 60 60 0
1 8
50 80 60 70 0
2 10
80 50 80 60 0
3 5
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Solución
El método de esquina noroeste requiere comenzar en la esquina
noroeste (fila 1, columna1) y hacer una asignación suficientemente
grande para agotar la capacidad del origen de la primera fila o
satisfacer el requerimiento del destino de la primera columna o
ambos. Por consiguiente, se hacen asignaciones a lo largo de la fila
2 hasta agotar la cantidad disponible (suministro) sin hacer una
asignación mayor que la requerida. Continuando de esta forma, se
agotan las capacidades de los orígenes y se satisfacen los
requerimientos de los destinos.
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Solución
Expendedor
Localidad Suministro
A B C D Ficticia
70 60 60 60 0
1 8
5 3
50 80 60 70 0
2 10
1 6 3
80 50 80 60 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Expendedor
Solución Localidad
A B C D
Fictici Suministro
a
70 60 60 60 0
1 8
5 3
50 80 60 70 0
2 10
1 6 3
80 50 80 60 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
La asignación mostrada en la tabla indica lo siguiente:
Despachar 50000 galones desde la localidad 1 al expendedor A.
Despachar 30000 galones desde la localidad 1 al expendedor B.
Despachar 10000 galones desde la localidad 2 al expendedor B.
Despachar 60000 galones desde la localidad 2 al expendedor C.
Despachar 30000 galones desde la localidad 2 al expendedor D.
Despachar 10000 galones desde la localidad 3 al expendedor D.
40000 galones desde la localidad 3 no se despachan
c.T.=50(70)+30(60)+10(80)+60(60)+30(70)+10(60)+40(0)=12400
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Prueba de optimalidad y degeneración
Número de asignaciones< m+n-1
entonces el problema es degenerado
Donde:
m: es el número de filas
n: es el número de columnas
Si no es degenerado realizar la prueba de optimalidad:
Ejm 7<3+5-1
7<7
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Paso 1. Formar una matriz que contenga los costos asociados con las
casillas en las que han hecho asignaciones
70 60
5 3
80 60 70
1 6 3
60 0
1 4
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Paso 2. Utilizando esta matriz, establecer un conjunto de números vj y
otro conjunto de números ui tales que su suma iguale los costos
obtenidos en el paso 1.
𝒄𝒊𝒋 = 𝒖𝒊 + 𝒗𝒋
vj
ui
0 -10 -30-20 -80
70 60
70
5 3
80 60 70
90
1 6 3
60 0
80
1 4
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Paso 3. Colocar el valor de ui+vj en las casillas que no tienen
asignaciones.
vj
ui
0 -10 -30 -20 -80
70 60 40 50 -10
70
5 3
90 80 60 70 10
90
1 6 3
80 70 50 60 0
80
1 4
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Paso 4. Restar los valores obtenidos en la anterior tabla de los
respectivos coeficientes de costos. 𝒄𝒊𝒋 − (𝒖𝒊 + 𝒗𝒋 )
vj
ui
0 -10 -30 -20 -80
70 60 40 60 50 60 -10 0
70
5 3 20 10 10
90 50 80 60 70 10 0
90
-40 1 6 3 -10
80 80 70 50 50 80 60 0
80
0 -20 30 1 4
Si cualquiera de los resultados obtenidos son negativos, la solución
no es óptima.
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
vj
Desplazamiento hacia una solución óptima. ui
0 -10 -30 -20 -80
Paso 1. Identificar la casilla que tenga el 70
5
70
3
60 40 60 50 60 -10 0
20 10 10
meno valor, en caso de empates se realiza 90
90 50 80 60 70 10 0
-40 1 6 3 -10
una elección arbitraria, de la anterior tabla. 80 80 70 50 50 80 60 0
80
0 -20 30 1 4
Expendedor
Localidad Suministro
A B C D Ficticia
70 60 60 60 0
1 8
5 3
50 80 60 70 0
2 10
1 6 3
80 50 80 60 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Desplazamiento hacia una solución óptima.
Paso 2. Trazar una trayectoria más - menos en la matriz de transporte.
Se debe comenzar y terminar en la casilla identificada en el paso1.
Además está casilla es positiva. Las demás esquinas de la trayectoria
(donde la trayectoria cambia de dirección) se designan alternativamente
menos y mas. Además, en todas las esquinas deben haber asignaciones,
excepto en la casilla identificada en el paso 1. No es necesario que está
trayectoria sea rectangular.
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Expendedor
Localidad Suministro
A B C D Ficticia
1 - 70 + 60 60 60 0
8
5 3
2 + 50 - 80 60 70 0
10
1 6 3
80 50 80 60 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Paso 3. Seleccionar en las esquinas negativas la cantidad más pequeña y
hacer una nueva asignación sumando o restando está cantidad de las
esquinas más o menos, respectivamente.
Expendedor
Expendedor A B C D Ficticia
Localidad Suministro - 70 +
60 60 60 0
A B C D Ficticia 5 3
70 60 60 60 0 + 50 -
80 60 70 0
1 8 1 6 3
4 4 80 50 80
1
60
4
0
50 80 60 70 0
2 10
1 6 3
80 50 80 60 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Prueba de optimalidad y degeneración
Número de asignaciones< m+n-1
entonces el problema es degenerado
Donde:
m: es el número de filas
n: es el número de columnas
Si no es degenerado realizar la prueba de optimalidad:
Ejm 7<3+5-1
7<7
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Prueba de optimilidad
vj
ui
0 -10 10 20 -40
70 60 80 60 90 60 30 0
70
4 4 -20 -30 -30
50 40 80 60 70 10 0
50
1 40 6 3 -10
40 80 30 50 50 80 60 0
40
40 20 30 1 4
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
vj
Desplazamiento hacia una solución óptima. ui
0 -10 10 20 -40
70 60 80 60 90 60 30 0
. 70
4 4 -20 -30 -30
50 40 80 60 70 10 0
50
1 40 6 3 -10
Expendedor 40
40 80 30 50 50 80 60 0
Localidad Fictici Suministro 40 20 30 1 4
A B C D a
- 70 60 60 60 + 0
1 8
4 4
+ 50 80 60 - 70 0
2 10
1 6 3
80 50 80 + 60 - 0
3 5
1 4
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
Desplazamiento hacia una solución óptima.
.
Expendedor
Localidad Fictici Suministro
A B C D a
70 60 60 60 0
1 8
1 4 3
50 80 60 70 0
2 10
4 6
80 50 80 60 0
3 5
4 1
Requerimiento 5 4 6 4 4 23
Elaborado por: Lic. Maria Magdalena Aguilar Guanto
