Hola!!!!!!
Necesito que alguien me de algunas ideas, para poder resolver estos problemas.
1)En la empresa Losa Preta, O.S. andan escasos de espacio y necesitan distribuir los trabajadores de una forma óptima. Disponen de M puestos de trabajo y N trabajadores. Cada trabajador i tiene unas restricciones horarias ri, una carga de trabajo ci y una preferencia pip por cada puesto p de trabajo. Naturalmente en un puesto no pueden estar trabajando al mismo tiempo dos trabajadores distintos.
Diseñe heurísticas voraces para resolver los problemas que siguen.
Se trata de determinar el horario de tal forma que todos los trabajadores cubran su carga de trabajo y se maximice la preferencia del conjunto.
Naturalmente puede ocurrir que las restricciones sean demasiado fuertes y el problema no tenga solución en los términos planteados. En tal caso, determine cuál es el mínimo número de puestos de trabajo necesarios para satisfacer las restricciones horarias, y supuesto que los empleados tienen una preferencia nula por los nuevos puestos añadidos determine la distribución que maximice la preferencial global.
NOTA: La carga de trabajo es el número de horas semanales que tiene que trabajar. Las restricciones horarias se entiende que son las horas a las que puede trabajar durante la semana.
2)Tenemos un procesador que debe realizar una serie de N trabajos. De cada trabajo i sabemos el instante exacto ci en que debe comenzar, su duración di y el beneficio bi que proporciona si se realiza. El procesador sólo puede realizar una tarea al mismo tiempo. Supuesto que el procesador está operativo entre los instantes C y F, diseñe algoritmos basados en Programación Dinámica que resuelvan los siguientes problemas:
i) Maximizar el beneficio de los trabajos que se procesen.
ii) Maximizar el número de trabajos procesados.
Si es posible debe diseñarse un algoritmo de complejidad polinomial y calcular la complejidad del mismo.
3) Recorrido del Caballo de Ajedrez con Condiciones. Se considera la lista ordenada formada por cuatro casillas del tablero de ajedrez. Se trata de encontrar el camino que debe seguir el caballo para realizar la “vuelta” al tablero de tal forma que la primera casilla del camino sea la primera de la lista, y las restantes casillas de la lista se encuentran en el camino en el mismo orden relativo que en la lista, si bien no necesariamente son contiguas en el camino. Dicho de otra forma, dada la lista ordenada {c0, c1, c2, c3} de casillas del tablero de ajedrez, hay que determinar el camino que sigue el caballo en su “vuelta” al tablero tal que c0 es su casilla inicial y la lista dada es una subsucesión del mismo.
Diseñe un algoritmo que resuelva el problema para el caso de un tablero de dimensión N.
Considere la resolución del problema para el caso en el que únicamente sean tres casillas las que forman la lista considerada, una de las cuales es la casilla de partida.
En ambos casos, si el problema no tiene solución, el algoritmo desarrollado debe indicarlo.
NOTA: El problema de la “vuelta” al tablero del caballo de ajedrez consiste en que partiendo de una casilla origen recorrer todas las casillas del tablero visitando cada casilla una única vez y regresar a la casilla origen una vez visitadas todas las casillas del tablero, esto es, la casilla origen es accesible por el caballo desde la última casilla del recorrido.
4) Pluma Blanca es un pequeño indio que ya tiene edad para pasar a una edad adulta. Sólo le falta la prueba que probará ante los demás miembros de su tribu su madurez. Se trata de dejar a Pluma Blanca sólo en el desierto con una pequeña cantimplora de agua y esperar que vuelva al poblado sano y salvo trayendo consigo, un mechón de pelo del puma Malo Malo, una ramita del viejo árbol del arroyo en el que se mira la Luna, un pedazo de roca del Monte Olvidado, una flor de más allá del lago y una serpiente de las Tierras Lejanas. Todos estos destinos están muy lejos unos de otros, y por lo tanto, en algún punto Pluma Blanca deberá volver a rellenar su cantimplora. Durante largo tiempo los ancianos de su poblado le han hablado de multitud de fuentes naturales a lo largo de los diversos lugares que tiene que visitar, y Pluma Blanca los ha aprendido al igual que las distancias que hay entre éstos y los lugares a los que tiene que ir.
Diseñe un algoritmo basado en Programación Dinámica o Backtracking que le permita a Pluma Blanca encontrar todos los objetos para demostrar su madurez, sin deshidratarse y sin tardar más de un tiempo T del que dispone antes de la próxima luna llena.
