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 quepueden 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 cijde 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 612 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´eordenador 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 quierenganar 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, lafachada 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 FachadaParedes
3IM1
3IT1
3IT2 15 10 9
9 15 10
10 12 8
¿Qu´e tarea deber´ıa hacer cada grupo para que el coste parala 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 ycalcula 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...