EL PROBLEMA DE LA ASIGNACION

INTRODUCCION
Se ha analizado la solución de los problemas de programación Lineal por medio
de los métodos simplex y del transmita. Existen sin embargo algunos casos
especiales de problemas de programación lineal que pueden resolverse
aplicando ciertas técnicas especiales qué reducen enormemente los pesados
cálculos que habrá que hacer aplicando los dos métodos anteriores. En esto
consideraremos uno de tales casos el problema de designación que tiene
muchas aplicaciones en los campos dela planificación asignación de recursos
Formulación del problema
El problema de la asignación es un caso particular del problema del trasporte el
cual puede formularse de esta forma: dados n servicios y n tareas y dado el
rendimiento de cada servicio aplicado a cada tarea (el cuadro que contiene los 𝑛2
valores de rendimiento se llama una matriz de orden n x n o 𝑛2 ). El problema
consiste en asignación cada servicio a un trabajo, y solo a uno de forma que la
medida del rendimiento sea la optima
Sea 𝑐𝑖𝑗 = coeficiente de costo (ganancia) de ejecución de la tarea j por el servicio
(operario) i.
Además hagamos:
𝑥𝑖𝑗 = 1 si el servicio i es asignado a la tarea j

𝑥𝑖𝑗 = 0 si el servicio i no es asignado a la tarea j

Nuestro problema será entonces:

Max o Min ∑𝑛𝑖=1. ∑𝑛𝑗=1 𝑐𝑖𝑗 . 𝑥𝑖𝑗

El servicio i de4be se asignado a una y solamente a una tarea

Al igual QUE EN EL PROBLEMA DEL TRANSPORTE, definamos dos matrices esta vez
en orden n x n.
X= [𝑥𝑖𝑗 ] c= [𝑐𝑖𝑗 ]
X es la matriz programa (solución) y c es la matriz costo. Si consideramos este
problema de transporte y le aplicamos el método UV, vemos que toda la solución
básica x tendrán n + n – 1 = 2n – 1 componentes. No obstante sabemos que de
antemano que la solución de problema de la asignación solo puede tener n
componentes no nulas.
Esto solo implica que siempre inevitablemente habrá degeneraciones presentes.
Se impone entonces el estudio de un nuevo método que resuelve este tipo de
problemas. Debe observarse también que una matriz de orden 𝑛2 tiene n!
posibles distribuciones, evaluar su costo total (en función de una medida
determinada de rendimiento) y elegir la asignación de costo mínimo. Fácilmente
se comprende que este método adquiere dimensiones formidables incluso para
valores pequeños o medidas de n. así si n=20, situación nada anormal el número
de posibles distribución es:
N!= 20!= 2432902008176640000
Programando una distribución por milésima de segundo y trabajando 8 horas
diarias y 365 días al año un computador rápido emplea un cuarto de millón de
años para hallar la solución óptima. Este ejemplo nos demuestra la necesidad
de encontrar técnicas de cálculo fáciles para resolver estos problemas de
asignación.
METODO DE SOLUCION
Se han desarrollado varias técnicas para resolver el problema de asignación
representados por las condiciones 1; 3; 4 y cada vez se presta más interés a este
campo.
Entre los que han realizado importantes contribuciones hay que citar a Dever
Blood, Kuhn, Veltan.
Teorema 1
Si dividimos los elementos de una matriz en dos clases mediante una propiedad
R; el número mínimo de líneas que contiene a todos los elementos con propiedad
P, es igual al máximo número de elementos con la propiedad P, donde dos de
los cuales no caen en la misma línea. (Por una línea entendemos cualquier fila
o columna de la matriz).
Lema 1
No se cambia la o las soluciones optimas de un problema de asignación
disminuyeron o aumentando una misma cantidad a todos los elementos de una
misma fila o columna de la matriz 𝑐𝑖𝑗

Teorema 2
Dada la matriz de costos E= 𝑐𝑖𝑗 . Formamos otra matriz 𝑐 ∗𝑖𝑗 . Por medio de la
transformación
𝑐 ∗𝑖𝑗 = 𝑐𝑖𝑗 = 𝑢¡ . 𝑣𝑗
Con 𝑢¡ y 𝑣𝑗 constante arbitrarias el problema de la optimización representado por
las condiciones 1, 2, 3 y 4 es idéntico con el de 𝑐 ∗ .
Definición 1
Decimos que conjunto de ceros es independiente si no hay dos o más ceros del
conjunto sobre las mismas líneas.
El teorema 1 y 2 es de la base del método Húngaro utilizado en la resolución del
problema de la asignación y que veremos a continuación
Método húngaro
El método Húngaro busca determinar un conjunto de n cero independientes en
cada fila y columna. El conjunto no es necesariamente único
Los pagos a seguir son los siguientes.
1. Examine todas las columnas de la matriz C identificado en cada columna
el menor elemento.
𝑐𝑖𝑗 = 𝑐𝑖𝑗 . 𝑣𝑗 Para j=1, 2,…..n
2. Determinar para cada fila los
𝑢¡ = 𝑚𝑖𝑛 𝑐′𝑖𝑗
Y determine
𝑐 ∗𝑖𝑗 = 𝑐𝑖𝑗 𝑢¡ Para i=1, 2,…n
3. Determine el número de ceros independientes, para ello encuentre el
mínimo de rectas 𝑛1 que cubran todos los ceros de la matriz 𝑐 ∗ si 𝑛1 = 1se
encuentra el optimo
(En fundamento de esta aseveración es el teorema de koning)
Para encontrar 𝑛1 compute la imagen de la matriz 𝑐 ∗ el número de ceros
existentes en cada fila y en cada columna. Se elige la fila o columna que
tenga el mayor número de ceros y se traza una recta por sobre la línea o
columna. Esto altera el número de ceros existentes en 𝑐 ∗ . Recalcule estos
valores y trácese una recta en la fila o columna con mayor número de
ceros. Así se procede asta eliminar todos los ceros de 𝑐 ∗ . En caso de
empate, rómpase este arbitrariamente.
4. Si 𝑛1 =n haga
O= mínimo elementos de 𝑐 ∗ no cubiertos por las rectas
Reste 0 a todos los elementos no cubiertos por las rectas
Sume 0 a todos los elementos en las intersecciones entre rectas.
Vuelva al paso 3 y repita el proceso.
5. Si 𝑛1 = n se ha llegado a la solución óptima, para buscar esta solución
consiste ante todos, una de las filas o columnas que tenga al menor
cantidad de ceros
Encierre dentro de un circulo uno de los ceros de esta hilera
Marque con una cruz los ceros que se encuentren sobre la misma fila o
columna que el cero encerrado en el círculo.
Procede en la misma forma sucesivamente para todas las dilas y
columnas. Los ceros en los círculos constituyen la asignación óptima.
Ejemplo 1
Existen 5 operarios a, b, c, d para llenar 5 cargos f, g, h, i y j. la matriz de costos
C, que caracteriza el problema de la asignación es la siguiente:

Se pide determinar la asignación óptima.

1. El elemento más pequeño en la primera columna es 𝑣1 − 2; en la segunda
es 𝑣2 = 2;en la tercera 𝑣3 = 1 en la cuarta 𝑣4 = 3 en la quinta 𝑣5 = 4
Se calcula 𝑐𝑖𝑗 = 𝑐𝑖𝑗 − 𝑣𝑗 quedando la matriz C’ así:

2. El elemento más pequeño en la primera fila es 𝑢1 = 𝑂 en la segunda fila

𝑢2 = 3 en la tercera 𝑢3 = 𝑂 en la cuarta 𝑢4 = 2 en la quinta es 𝑢5 = 𝑂. Se
calcula 𝐶 ∗𝑖𝑗 = 𝑐𝑖𝑗 − 𝑢1 quedando la matriz C* así:

3. Procedemos a encontrar el número mínimo de rectas 𝑛1 que cubren todos

los ceros de matriz C*
 Vemos que 𝑛1 =4; n=5
Luego no hemos llegado al óptimo
4. En este caso 0=1 (elemento mínimo no cubierto por rectas). Se resta 1 a
todos los elementos no cubiertos por las rectas. Se Cuma 1 a todos los
elementos en cada intersección entre 2 rectas y se vuelve al paso 3. La
matriz C* se transforma en:

Se observa que:
𝑛1 =5=n. por consiguiente se encontró el óptimo.
5. Determine la asignación optima:

6. Hay dos soluciones optimas, que son las siguientes:

.a es asignado a i
.b es asignado a g
.c es asignado a f
.d es asignado a j
.e es asignado a h
O bien
.a es asignado a j
.b es asignado a g
.c es asignado a f
.d es asignado a i
.e es asignado a h
El costo del programa en ambos costos es D/ 18.00
5 VARIANTES DEL PROBLEMA DE LA ASIGNACION
a. Matriz de n x m (m<n). algunas veces, el problema de la asignación se
presenta en una forma en la que la matriz no es cuadrada. En tal caso es
fácil convertir esta matriz en una cuadrada. Como se hace en el siguiente
ejemplo:
Ejemplo 2
Una compañía dedicada al transporte de mercaderías mantiene flotas
separadas de camiones para transporte urbano y el interurbano. Los
primeros realizan los servicios locales hasta las estaciones terminales de
la ciudad, donde las cargas se distribuyen y se transfiere a los camiones
interurbanos. La estación terminal tiene capacidad para acomodar a 6
camiones urbanos simultáneamente.
El situar cada camión en uno de los seis lugares implica un costo (de
distribución y de transferencia de cargas).
En un determinado día hay que situar simultáneamente cuatro camiones
urbanos (numerados del 1 al 4 en el terminal), el cuadro 1 muestra la
matriz de costos C que puede convertirse en una matriz cuadrada C
introduciendo dos camiones ficticios 5 y 6 como se ve en el cuadro 2
Cuadro 2

La solución debe interpretarse de la siguiente forma:

El camión 1 es asignado al punto 9
El camión 2 es asignado al punto 8
El camión 3 es asignado al punto 7
El camión 4 es asignado al punto 12
Los puntos 10 y 11 se dejan vacantes.
El costo correspondiente a esta asignación es:
Z= 3+1+2+2 = 8
Z= 8 dólares

b. PROBLEMAS DE MAXIMIZACION
Los ejemplos considerados hasta ahora son esencialmente problemas de
maximización, pero puede comprobarse fácilmente que la misma técnica
es aplicable a los problemas es el de asignar un cierto número de
personas a determinados trabajos de forma que se obtenga el beneficio
máximo.
Para resolver este problema por el método Húngaro solo tenemos que
convertir la matriz C en matriz Co de la siguiente manera:
Buscamos el Max. 𝐶𝑖𝑗 En la matriz C, construimos después
I,j
La matriz Co mediante la siguiente transformación
𝐶𝑖𝑗 (𝑜) = (𝑚𝑎𝑥. 𝑐𝑖𝑗 ) − 𝑐𝑖𝑗
La matriz Co tendrá al menos, un elemento nulo. Seguimos después el
mismo procedimiento que para los problemas de maximización
Ejemplo 3
Supongamos que la sociedad “Manpower”. Se encarga de proporcionar
trabajo femenino en una pequeña ciudad comercial.
Mantiene un personal de 4 mujeres (numeradas de 1 al 4) que además de
saber realizar muchos tipos de trabajos corrientes son expertas en sus
propios campos de actividad. La sociedad mantiene una seria de jóvenes
amas de casa que conocen diversos trabajos y que están dispuestas a
trabajar sobre una base temporal de días en que hay que hacer más de 4
trabajos A los clientes se les cobra los servicios según la productividad de
las mujeres que realizan (por ejemplo: número de pedidos enviados etc.
En un determinado día, la compañía recibe encargos de sus clientes para
la realización de cuatro trabajos (numerada del 5 al 8), conociéndose por
la experiencia anterior, la productividad esperada de cada joven en los
trabajos. Pueden construirse la matriz C de benéficos que nos del
beneficio esperando del día al asignar la muchacha i (i=1, 2, 4,….) al
trabajo j (j= 5,…… 8) cuadro (3)
El objetivo es asignar los cuatro jóvenes a los cuatro trabajos de manera
que sea máximo el beneficio esperado del día.
Cuadro 3
Matriz C de beneficios ($)

Aplicamos el procedimiento establecido

El máximo beneficio en la matriz C es 8; luego calculamos la matriz Co
aplicando (Max. 𝐶𝑖𝑗 )- 𝐶𝑖𝑗 el resultado es el siguiente:
I, j
 A partir de aquí seguimos el mismo procedimiento que para los problemas
de minimización y llegamos a la siguiente solución óptima.

La asignación óptima es:

La empleada 1 es asignada a la tarea 6
La empleada 2 es asignada a la tarea 8
La empleada 3 es asignada a la tarea 5
La empleada 4 es asignada a la tarea 7
El beneficio esperado del día para esta asignación es:
z= 8+5+36= 22
z= $22
NOTA: una segunda alternativa es multiplicar toda la matriz por (-1) y
aplicar directamente el método.
c. PROBLEMA CON ASIGNACIONES IMPOSIBLES
Si existe restricciones legales o de otro tipo que prohíben la asignación de
un servicio determinado a un determinado trabajo podemos asociar un
costo M infinitamente grande a la celda correspondiente y es decir
hacemos:
Cij=M es decir el costo del servicio y asignación a la tarea j es M
Esta actividad quedara automáticamente excluida de la solución óptima
Seguiremos después el mismo procedimiento establecido para optimizar
Ejemplo 4
Una pequeña compañía aérea, que opera 7 días por semana sirve tres
ciudades (A, B Y C) de acuerdo con el itinerario dado en el cuadro adjunto.
El costo de detención por parada (que le significa a la compañía tener sus
aviones inactivos), es proporcional al cuadrado del tiempo de detención.
Como debería la compañía asignar sus aviones a los diferentes vuelos de
modos de minimizar los costos de detención
Solución
Evaluemos los tiempos de detención entre los distintos vuelos
Tiempo de detención entre vuelos (horas)

En los espacios dejados en blanco los vuelos no son posibles. Así

aparecerán asignados costos M caracterizados con un valor
extremadamente grande
Como el costo de detención por parada es proporcional al cuadrado del
tiempo de detención, el costo de detención está dado por:
COSTO DE DETENCION
Esto conduce a resolver problemas de asignación independientes, que
representan respectivamente los vuelos en las ciudades A, B y C.
Aplicamos el método Húngaro a estos 3 problemas.
Por consiguiente la asignación óptima viene dada por:

Aeropuerto B

Por consiguiente la asignación óptima viene dada por:

Aeropuerto C
La solución óptima total es:

La asignación óptima está determinada en la siguiente forma:

Este programa puede llevarse a cabo por medio de 5 aviones que realicen
los siguientes itinerarios:
2 aviones en los vuelos 1-8-5-10
1 avión en los vuelos 2-6
1 avión en los vuelos 3-7-4-9
𝑐𝑖𝑗 = 𝑀1 Es decir el costo del servicio y asignado a la tarea j es M

Esta actividad quedara automáticamente excluida de la solución óptima

Seguimos después el mismo procedimiento establecido para optimizar