La página presenta varios ejercicios corregidos sobre problemas de planificación y programación automatizados, especialmente sobre problemas de asignación.

Ejercicio 1

La Red de la Costa Atlántica merece cuatro ciudades. La oficina quiere asignar cuatro plantas. El precio para enviar energía desde una planta a cada ciudad se describe a continuación:

 

Raleigh

Atlanta

Durham

Clemson

Planta A

210

90

180

160

Planta B

100

70

130

200

Planta C

175

105

140

170

Planta D

80

65

105

120

Una planta solo puede merecer una ciudad, y una ciudad solo puede tomar energías de una planta. Encuentre la mejor asignación al menor costo.

Después de la primera reducción:

 

R

PARA

D

VS

PARA

105

0

55

15

B

15

0

25

75

VS

35

0

0

10

D

0

0

5

0

Después de la segunda reducción:

 

R

PARA

D

VS

PARA

90

0

40

0

B

0

0

10

60

VS

55

15

0

10

D

0

15

5

0

Solución: 90 + 100 + 140 + 120 = 450.

Ejercicio 2

Permuta las columnas de una matriz cuadrada para minimizar la suma de elementos en la diagonal principal.

8

16

15

91

64

83

42

93

75

27

76

95

75

81

50

20

42

96

90

24

38

28

2

15

81

Encuentre una solución de asignación para esta matriz. Reorganice las columnas de manera que la solución forme una diagonal.

Ejercicio 3

Tres robots {a, b, c} necesitan completar tres tareas {t1, t2, t3} en la siguiente cuadrícula. Un robot tarda un día en pasar de una celda a una de sus vecinas.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

En la siguiente tabla, enumeramos los días en que cada robot puede terminar cada tarea solo. Las tareas deben completarse lo antes posible.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Agregue la distancia de Manhattan en días a la última tabla. Resuelve el problema de la asignación.

Ejercicio 4

Braneast Airlines debe contar con personal para los vuelos faily entre Nueva York y Chicago que se muestran en la tabla a continuación. Cada uno de los equipos de Braneast vive en Nueva York o Chicago. Cada día, una tripulación debe volar un vuelo NY-Chicago y un vuelo Chicago-NY con al menos una hora de tiempo de inactividad entre vuelos.

Braneast quiere programar las cuadrillas para minimizar el tiempo de inactividad total. Establezca un problema de asignación que pueda usarse para lograr este objetivo. Por supuesto, algunas asignaciones no son posibles. Encuentre las asignaciones de vuelo que minimizan el tiempo de inactividad total. ¿Cuántas tripulaciones deberían tener su base en cada ciudad? Suponga que al final del día, cada equipo debe estar en su ciudad de origen.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

La tabla de asignación está construida de la siguiente manera: para el primer vuelo desde Chicago, considerando el tiempo que llega a Nueva York, cuánto tiempo tiene que esperar la tripulación en el aeropuerto. Por ejemplo, para el primer vuelo desde Chicago, llega a las 10 a. M.:

Vuelo

1

2

3

4

5

6

7

Deja Nueva York

7

8

10

12

14

16

18

Tiempo de espera

imposible

imposible

imposible

2

4

6

8

Observamos que el vuelo 4, 5, 6, 7 de Chicago no puede ser el punto de partida, por lo que calculamos el tiempo de espera del vuelo de Nueva York. Tenga en cuenta que el vuelo 7 desde Nueva York no puede ser un punto de partida, por lo que calculamos el tiempo de espera desde el vuelo de Chicago. De cada elemento de la tabla, mantenemos el valor más bajo calculado (para vuelos desde Chicago y NY).

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Solución:

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Comienza en NY: (1.3), (2.4), (3.5), (5.6), (6.7).

Comienza en Chicago: (4.1), (7.2).

Tiempo total de inactividad = 25 h.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Ejercicio 5

Considere los datos de la tabla siguiente. Si una tripulación con base en Mumbai llega a Delhi en un vuelo determinado, debe regresar a Mumbai en un vuelo posterior. Suponga que para cualquier pareja dada, la tripulación se basará en la ciudad que resulte en la escala más pequeña.

El problema es encontrar los emparejamientos para minimizar el tiempo en tierra fuera de casa, sujeto a un intervalo mínimo de una hora entre la llegada y la salida. Dados los pares de vuelos, ¿dónde deberían tener su base las tripulaciones?

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Como en el ejercicio anterior, calcule en primer lugar las matrices de tiempo de escala, una para la escala en Mumbai y la otra para Delhi.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Ahora calculamos el mínimo de los valores para los 36 pares y construimos la siguiente tabla. Por ejemplo (7,2) es el mínimo entre (7,2) en la primera matriz y (2,7) de la segunda.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

La solución de este problema son los pares (7,3) de Mumbai, (8,4) de Mumbai, (9,2) de Delhi, (10,5) de Mumbai, (11,6) de Delhi, (12, 1) de Delhi con un tiempo total de descanso = 18h.

Ejercicio 6

Resuelva el siguiente problema como un problema de asignación.

Minimizar 4X11+ 6X12+ 5X13+ 5X14+ 7X21+ 4X22+ 5X23+ 6X24  + 4X31+ 7X32+ 6X33+ 4X34  + 5X41+ 3X42+ 4X43+ 7X44

San X11+ X12+ X13+ X14=1

X21+ X22+ X24+ X24=1

X31+ X32+ X33+ X34=1

X41+ X42+ X43+ X44=1

X11+ X21+ X31+ X41=1

X12+ X22+ X32+ X42=1

X13+ X23+ X33+ X43=1

X14+ X24+ X34+ X44=1

Aquí está la tabla para resolver:

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

Ejercicio 7

Resuelva el siguiente problema como un problema de asignación.

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

El problema de asignación se describe en la siguiente tabla:

 

1

2

3

1

5

9

inf

2

inf

2

inf

3

inf

1

1

Ejercicio 8

El Departamento de Historia del Arte desea ofrecer seis cursos en un semestre. Hay siete profesores en el departamento, cada uno de los cuales puede impartir solo ciertos cursos, como se muestra en la tabla. ¿Es posible asignar los seis cursos a los profesores para que ningún profesor imparta más de un curso?

ejercicios corregidos problemas de planificación y programación automatizados problemas de asignación

El problema de asignación se describe en la siguiente tabla:

 

Hormiga

Murciélago

Gato

Vejestorio

Rana

Mosquito

Cerdo

Antiguo

1

1

1

1

inf

inf

inf

Renacimiento

1

inf

inf

inf

1

1

inf

Barroco

1

inf

inf

inf

1

inf

inf

Impresionismo

inf

inf

inf

inf

1

1

inf

Moderno

inf

inf

1

inf

inf

1

1

Contemporáneo

1

inf

inf

inf

inf

1

inf

ficticio

1

1

1

1

1

1

1

Para encontrar una tarea, es mejor usar Escalón método en lugar del método húngaro.

Compartir, repartir
es_ESES