M Todo H Ngaro

UNIDAD 8
MODELO DE ASIGNACIÓN

características de asignación.
método húngaro o de matriz reducida.

Investigación de operaciones

Introducción

U

n caso particular del modelo de transporte es el modelo de
asignación, que tiene como propósito asignar personas u objetos a
tareas de tal forma que se optimice algún objetivo, por ejemplo:

Históricamente el problema de asignación se resolvióutilizando las
mismas técnicas que se utilizaban para el modelo de transporte,
sin embargo, resultaba tedioso hacerlo de esta manera debido a las
características particulares del mismo. A partir del trabajo realizado por
dos matemáticos húngaros, se obtiene un algoritmo eficiente para este
modelo, el cual se conoce como método húngaro.
Iniciamos la unidad planteando el problema general de asignación,hacemos hincapié en su estructura, como en el caso especial del
modelo de transporte y planteamos algunos problemas tipo. Continuamos
resolviendo el modelo de asignación por el método húngaro. Terminamos
la unidad estudiando algunos problemas de asignación desbalanceados.

8.1. Definición del modelo de asignación
Los problemas de asignación aparecen en varios contextos de la
ingeniería económica, endonde se requiere asignar de manera óptima
objetos o personas “ indivisibles” a ciertas tareas, por ejemplo:
especializados en cada tipo de soldadura existentes (mig, tig,
bajo el agua, eléctrica, oxiacetilénica, etc.). Si no se cuenta
con personal especializado representa un costo extra en gasto
de material. Por lo tanto, se debe asignar a la persona óptima en
cada puesto de trabajo paraminimizar costos.
en cada máquina (recta, zigzag, ojales, etc.) para minimizar tiempos
de producción.
grupo, pensando en optimizar los espacios disponibles.

309

Unidad 8

El problema clásico de asignación consiste en asignar n objetos o
personas indivisibles a m tareas de una manera óptima.
Las propiedades que debe cumplir un conflicto para formularse como
un problema de asignación son lassiguientes:

Cij de asignación de la persona i a la tarea j.
totales.

8.1.1. Construcción del modelo de asignación
Las variables que se utilizan en el modelo de asignación son variables
binarias, es decir, variables que sólo pueden tomar los valores 0 o 1.
Matemáticamente se escribe:
xij

1 si el asignado i realiza la tarea j
0 en caso contrario
para i=1, 2,... n j=1, 2, 3,... n

El costo total de laasignación es igual a la suma de los productos de
cada variable xij por el costo asignado Cij
n

n

Zmín

Cij xij
i 1 j 1

En las restricciones se asigna una persona a cada una de las tareas y cada
tarea debe ser realizada por una persona. Esto lo representamos como:
n

xij

1 para i 1, 2,... n

xij

1 para j 1, 2,... n

j 1
n
i 1

El modelo completo de asignación se obtiene al añadi r la restricciónde
no negatividad y la de variables binarias:

310

Investigación de operaciones

n

Zmín
i 1

n
j 1

Cij xij

Sujeto a:
n

xij

1 para i 1, 2,... n

xij

1 para j 1, 2,... n

j 1
n
i 1

xij binarias para toda i y j
xij

0

Vemos que el modelo de asignación es muy parecido al modelo de
transporte, la diferencia radica en que las variables del modelo de
asignación son binarias, mientras que en elmodelo de transporte las
variables son enteras. Entonces podemos tomar el modelo de asignación
como un problema de transporte donde cada una de las personas es el
origen y cada una de las tareas son los destinos. La oferta y demanda son
igual a uno, es decir, cada origen tiene una sola persona y cada destino
necesita sólo una persona. Los costos de capacitación representan el
costo de transportaruna unidad del origen i al destino j. Por lo tanto,
el objetivo es encontrar la combinación que minimice los costos de
asignación y cumpliendo las restricciones de oferta y demanda.
Al f inal de la unidad veremos problemas que aunque no cumplen la
primera propiedad pueden formularse como problemas de asignación.

Ejemplo 1
Una empresa contrata a cuatro personas para cubrir los siguientes
puestos:...