La página presenta varios ejercicios corregidos sobre problemas de programación y planificación automatizada, en particular sobre problemas de asignación.
Ejercicio 1
La red de la Costa Atlántica sirve a cuatro ciudades. La gerencia quiere asignar cuatro fábricas a las ciudades. El precio para enviar energía desde una fábrica 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 fábrica solo puede ganar una ciudad, y una ciudad solo puede obtener energía de una fábrica. Encuentra la mejor misió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 :
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
| 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. Reorganiza las columnas para que la solución forme una diagonal.
Ejercicio 3
Tres robots {a,b,c} deben completar tres tareas {t1, t2, t3} en la siguiente cuadrícula. A un robot le toma un día moverse de una celda a una de sus vecinas.
En la siguiente tabla, enumeramos los días en que cada robot puede completar cada tarea por sí solo. Las tareas deben completarse lo antes posible.
Agregue la distancia desde Manhattan en días a la última tabla. Resuelva el problema de asignación.
Ejercicio 4
Braneast Airlines se encargará de los vuelos fallidos entre Nueva York y Chicago que se enumeran en la siguiente tabla. Cada miembro del equipo de Braneast vive en Nueva York o Chicago. Cada día, una tripulación debe realizar un vuelo NY-Chicago y un vuelo Chicago-NY con al menos una hora de inactividad entre vuelos.
Braneast quiere programar cuadrillas para minimizar el tiempo de inactividad total. Desarrolle un problema de asignación que pueda usarse para lograr este objetivo. Por supuesto, algunas asignaciones no son posibles. Encuentre asignaciones de vuelos que minimicen el tiempo de inactividad total. ¿Cuántas tripulaciones deberían estar basadas en cada ciudad? Suponga que al final del día, cada tripulación debe estar en su ciudad natal.
La tabla de asignación se construye de la siguiente manera: para el primer vuelo que sale de Chicago, dada la hora de llegada a NY, cuánto tiempo debe esperar la tripulación en el aeropuerto. Por ejemplo, para el primer vuelo desde Chicago, llega a las 10 am:
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 los vuelos 4, 5, 6, 7 desde Chicago no pueden ser el punto de partida, por lo que calculamos el tiempo de espera desde el vuelo desde Nueva York. Tenga en cuenta que el vuelo 7 desde NY no puede ser un punto de salida, por lo que estamos calculando el tiempo de espera del vuelo desde Chicago. De cada uno de los elementos de la tabla, conservamos el valor calculado más bajo (para vuelos desde Chicago y NY).
Solución :
Comienza en Nueva York: (1.3), (2.4), (3.5), (5.6), (6.7).
Comienza en Chicago: (4.1), (7.2).
Tiempo de inactividad total = 25h.
Ejercicio 5
Considere los datos en la siguiente tabla. 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 emparejamiento dado, la tripulación estará basada en la ciudad que resulte en la escala más pequeña.
El problema es encontrar parejas de forma que se minimice 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 basarse las tripulaciones?
Como en el ejercicio anterior, primero calcule 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 tabla a continuación. Por ejemplo (7.2) es el mínimo entre (7.2) en la primera matriz y (2.7) en la segunda.
La solución a este problema son los pares (7,3) Mumbai, (8,4) Mumbai, (9,2) Delhi, (10,5) Mumbai, (11,6) Delhi, (12 , 1) from Delhi con tiempo de inactividad total = 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
Necesitas resolver el problema de asignación:
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 por semestre. Hay siete profesores en el departamento, cada uno de los cuales solo puede impartir ciertos cursos, como se muestra en la tabla. ¿Es posible asignar los seis cursos a los maestros para que ningún maestro enseñe 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 misión, es mejor utilizar el método del trampolín en lugar del método húngaro.
ES 
FR 
EN