Problema de asignacion (ingenieria en sistemas)

Solo disponible en BuenasTareas
  • Páginas : 5 (1237 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de febrero de 2011
Leer documento completo
Vista previa del texto
Una compañía transportadora dispone de 5 camiones situados en las ciudades A, B, C, D y E. Se requiere un camión en las ciudades 1, 2, 3, 4, 5 y 6. En la tabla se muestra el kilometraje entre las ciudades. El problema consiste en determinar la asignación de camiones que minimice el kilometraje recorrido por todos los camiones.
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6|
A | 20 | 15 | 26 | 40 | 32 | 12 |
B | 15 | 32 | 46 | 26 | 28 | 20 |
C | 18 | 15 | 2 | 12 | 6 | 14 |
D | 8 | 24 | 12 | 22 | 22 | 20 |
E | 12 | 20 | 18 | 10 | 22 | 15 |
Solución:
Dado que el problema no está balanceado se agrega un origen ficticio, con distancias de cero.
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6 |
A | 20 | 15 | 26 | 40 | 32 | 12 |
B| 15 | 32 | 46 | 26 | 28 | 20 |
C | 18 | 15 | 2 | 12 | 6 | 14 |
D | 8 | 24 | 12 | 22 | 22 | 20 |
E | 12 | 20 | 18 | 10 | 22 | 15 |
FIC | 0 | 0 | 0 | 0 | 0 | 0 |

Se resta el elemento más pequeño de cada fila de los demás elementos de la misma fila; de igual forma para las columnas.
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6 |
A | 8 | 3 | 14 | 28 | 20 | 0 |B | 0 | 17 | 31 | 11 | 13 | 5 |
C | 16 | 13 | 0 | 10 | 4 | 12 |
D | 0 | 16 | 4 | 14 | 14 | 12 |
E | 2 | 10 | 8 | 0 | 12 | 5 |
FIC | 0 | 0 | 0 | 0 | 0 | 0 |

Se determina una asignación máxima y se trazan líneas para cubrir todos los ceros.

| Se toma el 4 como el número menor de los elementos no cruzados.
Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6 |
A | 8 |3 | 14 | 28 | 20 | X
0 |
B | 0 | 17 | 31 | 11 | 13 | 5 |
C | 16 | 13 | 0 | 10 | 4 | X
12 |
D | 0 | 16 | 4 | 14 | 14 | 12 |
E | 2 | 10 | 8 | 0 | 12 | 5 |
FIC | 0 | 0 | 0 | 0 | 0 | 0 |

X
X
No se tiene una asignación completa por lo tanto, se repite el paso anterior.
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6 |
A | 12 | 3 | 14 | 28 | 20 | X
0 |
B | 0| 13 | 27 | 7 | 9 | X
1 |
C | 20 | 13 | 0 | 10 | 4 | X
12 |
D | 0 | 12 | 0 | 10 | 10 | 8 |
E | 6 | 10 | 8 | 0 | 12 | 5 |
FIC | 4 | 0 | 0 | 0 | 0 | 0 |
Se toma el 1 como el número menor de los elementos no cruzados.

Aun no se tiene una asignación completa, repetimos el paso.
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | X
6 |
A | 13 | 3 | 15 | 28 | 20 | X
0|
B | 0 | 12 | 27 | 6 | 8 | 0 |
C | 20 | 12 | 0 | 9 | 3 | X
11 |
D | 0 | 11 | 0 | 9 | 9 | 7 |
E | 7 | 10 | 9 | 0 | 12 | 5 |
FIC | 5 | 0 | 1 | 0 | 0 | 0 |
X
X
Se toma el 3 como el número menor de los elementos no cruzados.

Finalmente se tiene una asignación completa y que será solución optima:
| Hasta las ciudades |
Desde las ciudades | 1 | 2 | 3 | 4 | 5 | 6 |
A | 13 | 0 |12 | 25 | 17 | 0 |
B | 0 | 9 | 24 | 3 | 5 | 0 |
C | 23 | 12 | 0 | 9 | 3 | 14 |
D | 0 | 14 | 3 | 12 | 12 | 7 |
E | 10 | 10 | 9 | 0 | 12 | 8 |
FIC | 8 | 0 | 1 | 0 | 0 | 3 |
Se toma el 3 como el número menor de los elementos no cruzados.

Desde | Hasta | Solución Óptima:
Los camiones se transportaran de su respectivo lugar a las ciudades mencionadas con una distancia mínima de 55kilómetros.
Costo |
A | 2 | 15 |
B | 6 | 20 |
C | 3 | 2 |
D | 1 | 8 |
E | 4 | 10 |
FIC | 5 | 0 |
Suma | | 55 |

Una competencia de relevos de 400 metros incluye a cuatro diferentes nadadores, quienes nadan sucesivamente 100 metros dorso, de pecho, de mariposa y libre. Un entrenador tiene seis nadadores muy veloces, cuyos tiempos esperados (en segundos) en los eventos individuales sedan a continuación:
| Evento 1(Dorso) | Evento 2(Nado de pecho) | Evento 3(Mariposa) | Evento 4(Libre) |
Nadador 1 | 65 | 73 | 63 | 57 |
Nadador 2 | 67 | 70 | 65 | 58 |
Nadador 3 | 68 | 72 | 69 | 55 |
Nadador 4 | 67 | 75 | 70 | 59 |
Nadador 5 | 71 | 69 | 75 | 57 |
Nadador 6 | 69 | 71 | 66 | 59 |

¿Cómo deberá el entrenador asignar los nadadores a los relevos a fin de minimizar...
tracking img