Asignacion

PROBLEMA DE LA ASIGNACION
Muchas de las situaciones en la vida exigen
una de dos respuestas posibles: si o no.  Así
Muchas de las situaciones en la vida exigen
una de dos respuestas posibles: si o no. 
El PA consiste en asignar recursos a tareas
en función de un objetivo ligado a la
eficiencia del sistema. Un ejemplo típico es
el de asignación de personas a turnos
horarios, o el de asignarpersonas a
máquinas

El esquema tabular del PA es:
MAQUIN AS
M1

TAREAS

c22

cm1

cm2

...............
...............

...............

1

c2n

1

cmn

Tm
bj

c1n

...............
1

ai

.........

c12

Mn

...............

.........

.........

c12

.........

T2

c11

.........

T1

M2

1

................

1
1

Formulación del Programa
Minimizar el costo total de operación de modo que:
• cadatarea se asigne a una y sólo una máquina
• cada máquina realice una y sólo una tarea
m

Min

n



cij xij

i 1 j 1

s .a .
m

x

ij

1, j 1..n

x

ij

1,i 1..m

i 1
n

j 1

xij   0 ,1

Xij: 1 si la tarea i se hace con la
máquina j
cij: costo de realizar la tarea i con
máquina j
n tareas
m máquinas
Si hay más máquinas que tareas
se formula con desigualdades, y
se resuelve con tareasficticias

METODO HUNGARO
Existen 5 operarios (A, B, C, D y C) que tienen
que llenar 5 cargos (I, II, III, IV y V). La matriz de
costos que caracteriza el problema de asignación
es la siguiente
I II III IV V
A 5 3 7 3 4
B 5 6 12 7 8
C 2 8 3 4 5
D 9 6 10 5 6
E 3 2 1 4 5
Determinar la asignación óptima

1- Se calcula C’ij= Cij – elemento mas pequeño
de cada columna
A
B
C
D
E

I
3
3
0
7
1

II
1
4
6
40

III
6
11
2
9
0

IV
0
4
1
2
1

V
0
4
1
2
1

2. Se calcula C*ij = C’ij – elemento mas pequeño de
cada fila
A
B
C
D
E

I
3
0
0
5
1

II
1
1
6
2
0

III
6
8
2
7
0

IV
0
1
1
0
1

V
0
1
1
0
1

3. Procederemos a encontrar el número mínimo de recta r
que cubren todos los ceros de la matriz C*
A
B
C
D
E

I
3
0
0
5
1
2

II
1
1
6
2
0
1

III
6
8
2
7
0
1

IV
0
1
1
0
1
2

V
0
1
1
0
1
2

2
1
1
2
2

Vemos que r= 4 que es diferente de m=5, por consiguiente
no se ha llegado al óptimo
4. En este caso ⍬= 1 (elemento mínimo no cubierto por las
rectas). Se resta ⍬ a todos los elementos no cubiertos por
las rectas- Se suma ⍬ a todos los elementos en las
intersecciones entre 2 rectas y se vuelve al paso 3. La matriz
C* se transforma en

A
B
C
D
E

I
3
0
0
5
2
2

II
0
0
5
1
0
3
2
1

III
5
7
1
6
0
1

IV
0
1
10
2
2
1

V
0
1
1
0
2
2
1

3
2
1
2
2

1

Se observa que r = 5 = m =5, por consiguiente se ha llegado
al óptimo
5. Determinamos la asignación óptima
A
B
C
D
E

I
3
0
00
5
2
2

II
0
00
5
1
0
3

III
5
7
1
6
00
1

IV
00
1
1
00
2
2

V
00
1
1
00
2
2

3
2
1
2
2

Hay dos soluciones óptimas:
A es asignado a IV
B es asignado a II
C es asignado a I
D es asignado a V
E es asignado a III
O bien:
A es asignado aV
B es asignado a II
C es asignado a I
D es asignado a IV
E es asignado a III
El costo total del programa en ambos casos es Z
= $ 18

CASO 1: MATRIZ NO CUADRADA
Cuatro trabajadores requieren el uso de una
cualesquiera de las de las maquinas A, B, C y D. Los
tiempos tomados por cada maquina para realizar
cada trabajo son mostradas en la matriz siguiente:

A
B
C
D
E

I
II III IV
10 5 9 18
13 19 612
3 2 4 4
18 9 12 17
11 6 14 19

Encuentre la asignación que minimice el tiempo total.

CASO 2: ASIGNACIONES IMPOSIBLES
El
El hospital de Chiclayo ha comprado tres máquinas nuevas de diferentes
tipos. Existen cuatro lugares dentro de la planta de quirófanos en donde se
podría instalar cada una de estas máquinas. Algunos de ellos son más adecuados
que otros para una máquina en particular por sucercanía a las mesas de cirugía
que tendrían un flujo intenso de trabajo hacia estas máquinas y desde ellas. Por
lo tanto el objetivo es asignar las nuevas máquinas a los lugares disponibles de
manera que se minimice el costo total del manejo de materiales. En la tabla
siguiente se proporciona el costo estimado por unidad de tiempo del manejo de
los materiales en cuestión con cada una de las...