Problemas De Asignacion

PROBLEMAS DE ASIGNACIO´ N

1.– Un sistema de procesamiento compartido tiene seis ordenadores diferentes Oi , i = 1, . . . , 6 y debe procesar seis tareas Tj , j = 1, . . . , 6 que pueden re- alizarse en cualquiera de los seis ordenadores, pero con la condici´on de que tendran que completarse en el ordenador en el que se iniciaron. Los costes de procesamiento cij de las tareas variar´an segu´n el ordenador, tal como se muestra en la tabla.

T1 T2 T3 T4 T5 T6

O1

O2

O3

O4

O5

O6 8 4 10 2 1 6

6 6 12 4 3 5

2 4 8 1 1 6

10 8 15 6 2 3

5 7 20 4 4 1

8 2 10 4 2 4

Determinar qu´e ordenador se asignar´a a cada trabajo de modo que el coste total sea m´ınimo.

2.– Los tres cursos de tercero de la escuela superior de inform´atica de la Uni- versidad Antonio de Nebrija quieren ganar algu´n dinero para cubrir los gastos de un viaje al final del cuatrimestre. Para ayudarles, la universidad les ofrece tres tareas diferentes: Pintar las ventanas de las clases, la fachada del edificio y las paredes de las aulas.

A cada curso se le manda escribir su propuesta de precios, estas propuestas vienen descritas en la tabla siguiente:

Ventanas Fachada Paredes

3IM1

3IT1

3IT2 15 10 9

9 15 10

10 12 8

¿Qu´e tarea deber´ıa hacer cada grupo para que el coste para la universidad sea m´ınimo?

3.- Dadas las ecuaciones de los modelos de programaci´on lineal asociados a los problemas de asignaci´on siguientes, construye la tabla de asignaci´on asociada y calcula la soluci´on ´optima mediante el algoritmo hu´ngaro.

a)

min 4x11 + 7x12 + 6x13 + 6x14 + 7x21 + 5x22 + 6x23 + 7x24 +

+4x31 + 8x32 + 7x33 + 5x34 + 5x41 + 4x42 + 5x43 + 8x44

sujeto a x11 + x12 + x13 + x14 = 1

x21 + x22 + x23 + 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

xij = 0 o 1, i, j = 1, . . . , 4

b)

min x12 + 2x22

sujeto a x11 + x12 = 1

x21 + x22 = 1

x11 + x21 = 1

x12 + x22 = 1

xij = 0 o 1, i, j = 1, . . . , 2

c)

min −x12 + 3x14 + 2x21 + x23 + 2x24 − x31 +

+2x32 + x33 + x34 − x41 + 3x42 + 2x43

sujeto a x11 + x12 + x13 + x14 = 1

x21 + x22 + x23 + 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

xij = 0 o 1, i, j = 1, . . . , 4

4.- Indica, en la siguiente tabla de asignaci´on, si pueden existir soluciones al- ternativas o si, por contra, la soluci´on es u´nica. Especifica el valor o valores objetivos ´optimos.

...