Ejercicios de los Temas 1 y 2

Para todos los problemas las preguntas son siempre las mismas.
Tema 1
a) Encuentra los elementos (piezas) importantes del problema.
b) Invéntate una solución factible y calcula la función objetivo.
c) ¿De qué diferentes maneras puede ser una solución infactible?
d) ¿De qué diferentes maneras puede ser una solución incompleta?
e) Invéntate una codificación. Da la codificación para la solución del apartado b).
f) Diseñar un algoritmo constructivo aleatorio, otro inteligente y otro inteligente aleatorizado, de
manera que las codificaciones sean factibles. Si puedes, que las codificaciones obtenidas sean
completas directamente (sin aplicar mecanismo de completitud). Explica si las codificaciones que se
obtienen siempre son completas.
g) Diseñar un mecanismo de factibilidad y otro de completitud, por si tuviéramos una codificación
infactible y una incompleta.
h) Diseñar un movimiento para una búsqueda local.
Tema 2
Suponemos que tenemos una codificación de una solución factible y completa.
a) Diseñar una perturbación para un ILS que proporciones una solución factible y completa.
b) Diseñar un operador de cruce y una mutación, de manera que las codificaciones sean factibles y
completas.

1. Asignación I
Se dispone de una lista de n trabajadores para formar K grupos. La empresa exige que cada grupo contenga
todas las habilidades de una lista de m habilidades. Cada trabajador tiene algunas o todas estas habilidades.
Además, hemos calculado el ‘roce potencial’ de tener a dos personas en el mismo grupo, Rjh es el roce de
tener a las personas j y h en el mismo grupo. Decidir qué trabajadores se contratan para cada grupo de
manera que se minimice el roce potencial total.
Instancia
n= 10, K = 2, m = 5
Liderazgo Informática avanzada Marketing en redes sociales Inglés fluido (C1)
1 1 0 0 1
2 0 1 0 1
3 0 0 1 1
4 1 1 0 0
5 0 0 1 0
6 1 0 0 1
7 0 1 0 0
8 1 0 1 0
9 0 0 1 1
10 0 1 1 0

1 2 3 4 5 6 7 8 9 10
1 - 8 7 6 4 10 3 5 6 8
2 - 12 5 7 6 4 8 9 11
3 - 3 1 0 5 4 2 3
4 - 0 6 9 15 1 4
5 - 3 5 4 6 8
6 - 1 5 4 3
7 - 3 5 4
8 - 11 4
9 - 2
10 -
2. Problema Multimodo
Una empresa constructora debe decidir qué tareas realizar. Puede escoger entre 10 tareas. Cada una de ellas
tiene una duración y un ingreso. La empresa tiene un mes para realizar esas tareas y lo que quiere es escoger
las tareas para maximizar el beneficio. La empresa además puede acortar la duración de las tareas dedicando
más trabajadores a una tarea, y/o empleando maquinaria más eficiente. Acortar la duración tiene un coste,
y la empresa tiene un presupuesto para ello. Este coste sí se tiene en cuenta en la función objetivo, al calcular
el beneficio. Añadir trabajadores tiene dos posibilidades: un primer nivel (extra) donde la duración se reduce
un 10% o un 2º nivel (extra plus) donde se reduce un 20%. Lo mismo ocurre con la maquinaria. En las tareas
que realiza la empresa, ésta debe decidir a qué nivel emplear los trabajadores y la maquinaria.
Instancia
n= 10. Presupuesto: 1000

1 2 3 4 5 6 7 8 9 10
Duración 5 3 8 6 7 5 4 6 8 10
Coste Tr. Extra 100 75 200 175 80 125 60 140 250 300
Coste Tr. Plus 200 150 400 350 160 250 120 280 500 600
Coste M. extra 80 100 250 150 100 150 80 120 200 250
Coste M. plus 160 200 500 300 200 300 160 240 400 500
Ingreso 1250 1225 1550 1400 1300 1350 1180 1400 1700 1800

3. Problema Lineal Entero

Una empresa editorial publica y comercializa tres tipos de libro: novela, ensayo y poesía. El proceso de
publicación y comercialización de cada uno de estos libros pasa por dos secciones: edición del texto e
impresión y comercialización. La tabla adjunta indica el número de horas que se invierten en cada sección
por unidad y los beneficios estimados (en cientos de euros) para cada tipo de libro.

Impresión y
Tipo de libro Edición texto Beneficios
encuadernación

Novela 10 24 12

Ensayo 9 28 15

Poesía 15 48 25

Disponemos de 809 horas en la sección de edición del texto y 1950 horas en la sección de impresión y
encuadernación. La empresa desea conocer cuántos libros debe publicar y comercializar de cada tipo para
maximizar sus beneficios.
Los algoritmos tienen que realizarse para un número n de tipos de libro. Llamaremos HE a las horas
disponibles en la sección de edición y HI a las disponibles en la sección de impresión.

4. Asignación II
La encargada de recursos humanos de una gran empresa debe escoger 5 trabajadores diferentes de entre
10 trabajadores para cubrir 5 puesto nuevos que va a crear la empresa. Tras realizarles un test de
conocimientos obtiene una calificación que le indica el rendimiento de cada trabajador en cada puesto de
trabajo. Los resultados del test son los que se muestran en la tabla (10: rendimiento alto, 1: rendimiento
bajo). La encargada debe decidir qué trabajador asigna a cada puesto para maximizar el rendimiento total.

Puesto 1 Puesto 2 Puesto 3 Puesto 4 Puesto 5

Trabajador 1 9 9 9 9 1

Trabajador 2 7 8 2 1 8

Trabajador 3 2 2 4 9 9

Trabajador 4 4 8 2 5 8

Trabajador 5 5 9 8 2 1

Trabajador 6 1 2 3 3 6

Trabajador 7 7 3 4 9 9

Trabajador 8 2 4 8 8 8

Trabajador 9 9 10 4 9 10

Trabajador 10 7 6 4 3 2

5. Asignación de recursos
Una empresa tiene que realizar 10 tareas que consumen recursos de 6 tipos. En la tabla se muestra la
cantidad de recurso que consume cada tarea, la disponibilidad de cada recurso (última fila) y el beneficio
que se obtendría si se realizara la tarea. Se trata de decidir qué tareas deben ejecutarse para maximizar el
beneficio.

1 2 3 4 5 6 Beneficio

1 2 - 4 1 - 1 2

2 2 2 3 - - - 4

3 3 - 2 4 - - 6

4 6 - 6 6 6 6 7

5 3 - 3 3 6 7 4

6 2 - - 2 - 1 3

7 3 3 3 3 5 - 6

8 - - - - - - 2

9 - - - 5 5 5 10

10 - - - 5 1 3 2

Disponibilidad 10 20 30 25 18 10

6. Ejemplos de la tarea de programación

Puedes practicar con los 4 ejemplos con los que no hayas trabajado ya.

7. Secuenciación de proyectos
Supongamos un proyecto formado por 8 actividades (la primera y la última indican principio y fin del
proyecto). Cada una de las actividades tiene una duración y requiere para su realización de un número de
operarios. Se dispone de 3 operarios durante todo momento en la ejecución del proyecto. Hay que decidir
en qué momento comenzar cada actividad, lo que se conoce como secuencia. La actividad dura entonces lo
que marca su duración. Las flechas indican precedencia, una actividad debe finalizar antes de que la siguiente
comience. Por ejemplo, la actividad 4 debe finalizar antes de que la actividad 7 comience. Una secuencia
factible debe respetar las relaciones de precedencia y las restricciones de recurso. El objetivo es que la última
actividad, la 8, acabe lo antes posible.

La codificación para este problema es un vector V de n posiciones, con n el número de actividades. V(i)
simboliza el inicio de la actividad i.