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.
En la siguiente tabla, enumeramos los días en que cada robot puede terminar cada tarea solo. Las tareas deben completarse lo antes posible.
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.
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).
Solució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.
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?
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.
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.
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:
Ejercicio 7
Resuelva el siguiente problema como un problema 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?
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.
ES 
FR 
EN