57MetodoParaLaSlnOptimaProbAsignacion

Investigación de operaciones

5.7. Método para obtener la solución óptima del problema de asignación

UNIDAD V. ALGORITMOS ESPECIALES
5.7. Método para obtener la solución óptima del problema de
asignación
Ejemplo. Se desea asignar un depósito que logre abastecer a una
localidad, de forma tal que la distancia en global recorrida sea la
mínima posible.
Tabla de distancias (km).
Depósito
1
2
3
4Paso 2. Restar el valor mínimo ha seleccionado a cada renglón
correspondiente; por ejemplo a los valores del primer renglón se le
resta 200, a los valores del segundo renglón se le resta 190 y así
sucesivamente, quedando:

30
0
20
40

0
20
0
0

10
10
65
30

40
10
40
50

Localidad
1
230
190
200
220

2
200
210
180
180

3
210
200
240
210

4
240
200
220
230

Paso 3. Ahora seleccionamos el mínimo de cadacolumna y dicho valor
lo colocamos debajo de cada una (equivalente a crear otro renglón).

En este caso buscaremos la solución óptima a este tipo de problemas,
el algoritmo es como sigue:
Paso 1. En el cuadro de distancias o costos seleccionar el mínimo por
renglón (subrayado y colocado a la derecha de la tabla).

230
190
200
220

200
210
180
180

Elaboró: MC. Marcel Ruiz Martínez

210
200
240210

240
200
220
230

200
190
180
180

30
0
20
40
0

0
20
0
0
0

10
10
60
30
10

40
10
40
50
10

Paso 4. Restar el valor a la columna correspondiente; en este ejemplo
no se resta nada a las primeras dos columnas (o se les resta cero) a las
columnas 3 y 4 se les resta 10 unidades a cada uno de sus valores.
Quedando:

30
0
20
40

0
20
0
0

0
0
50
20

30
0
30
40

1

Investigación de operaciones

5.7.Método para obtener la solución óptima del problema de asignación

Paso 5. Trazar líneas buscando seleccionar todos los “0’s” posible
usando la mínima cantidad de líneas.

30
0
20
40

0
20
0
0

0
0
50
20

30
0
30
40

A los que están no tachados: se les resta “20”, quedando:

0
20

30
0

10
20

A los tachados pero no interceptados, sin cambio.
Aquí fue posible seleccionar solo con 3 líneas todoslos ceros, por lo
cual no se ha logrado terminar el problema, ¿Cuándo se termina el
proceso? Cuando se seleccionan con 4 líneas, ya que es una matriz de
4x4.

30
0
0
20

0
0

0
0
30
0

30
0
10
20

0
0
30
0

30
0
10
20

Paso 6. Se debe buscar el número más pequeño de los valores NO
TACHADOS, dichos valores se muestran en la siguiente tabla:
A los interceptados, se les suma.

20
40

50
20

30
40

Comopuede notarse el número más pequeño de los no tachados es el
20. Entonces con dicho valor se hace lo siguiente a los valores de toda
la tabla:
A los valores que están:
• No tachados: Se les resta “20”.
• Tachados pero no interceptados: sin cambio.
• Interceptados: Se les suma “20”.

Elaboró: MC. Marcel Ruiz Martínez

30
0
0
20

20
40
0
0

Paso 7. Repetir desde el paso 5 hasta que la cantidad deceros forcen a
seleccionarlos con 4 líneas, en este caso ya no hay forma de seleccionar
los ceros con menos de 4 líneas, por lo cual hemos terminado las
interaciones.
30
0
0
20

20
40
0
0

0
0
30
0

30
0
10
20

2

Investigación de operaciones

5.7. Método para obtener la solución óptima del problema de asignación

Ahora la posición de los ceros, nos indica la posibilidad de asignar una
fuente conun destino, ahora como en un renglón hay varios ceros para
este problema debemos hacer la asignación por un proceso de descartar
cada opción, es decir, en el primer renglón no hay otra opción mas que
asignar el depósito 1 con la localidad C
Depósito
1
2
3
4

A
30
0
0
20

B
20
40
0
0

C
0
0
30
0

D
30
0
10
20

Esta claro que la respuesta final debe ser:
Depósito Surte a:
1.
C
2.
D
3.
A
4.
B
Ladistancia global mínima posible es: Z = 790 km.

Dado que la localidad C ha sido surtida la tabla queda ahora reducida,
podemos notar que el depósito 4 debe ser forzosamente asignado a la
localidad B:
Depósito
1
2
3
4

A
30
0
0
20

B
20
40
0
0

C
0
0
30
0

D
30
0
10
20

C
0
0
30
0

D
30
0
10
20

Quedando ahora la tabla de ésta forma:
Depósito
1
2
3
4

A
30
0
0
20

B
20
40
0
0

PREGUNTA PARA LOS...