UNIVERSIDAD NACIONAL DE SAN CRISTOBAL DE
HUAMANGA
FACULTAD DE INGENIERIA DE MINAS, GEOLOGIA Y CIVIL
ESCUELA DE FORMACION PROFESIONAL DE INGENIERIA
DE MINAS
CASOS ESPECIALES DE PROGRAMACION LINEAL
Capítulo 4
Problema de Asignación
CURSO : ANALISIS DE SISTEMAS MINEROS (MI-547)
PROFESOR : MsC. Ing. EDMUNDO CAMPOS ARZAPALO
E – MAIL : edmcam@[Link]
Definición
• Los problemas de asignación ocurren en muchos
contextos de la administración.
• En general, un problema de asignación consiste en
determinar la asignación óptima de agentes u
objetos indivisibles a n tareas.
• La restricción importante para cada agente es que
puede ser asignado a una y solo una tarea
Enumeración completa
• Es una manera de encontrar una solución que
consiste en hacer una lista de todas las
soluciones posibles, calcular el costo de cada
alternativa y elegir la mejor
Asignación como problema de
transporte
• El problema de asignación puede resolverse
como un problema de transporte en el cual la
oferta de cada origen y la demanda de cada
destino son iguales a 1
Formulación y solución de PL
• Como la asignación es un caso particular de
un problema de transporte, se puede
formular como un problema de programación
lineal.
• Donde: Xij ij = asignación del elemento i a la
posición j.
Método Húngaro
Paso 1.- Elabore una nueva matriz eligiendo el
costo mínimo de cada renglón y restándolo de
cada costo de ese renglón
Destinos Destinos Reducc.
en
orígenes 1 2 3 4 orígenes 1 2 3 4 renglón
A 24 10 21 11 A 14 0 11 1 10
B 14 22 10 15 B 4 12 0 5 10
C 15 17 20 19 C 0 2 5 4 15
D 11 19 14 13 D 0 8 3 2 11
Método Húngaro
Paso 2.- Reducción en columnas. Elíjase el
elemento de costo mínimo de cada columna y
réstelo de cada elemento de la columna.
Destinos Reducc.
en
orígenes 1 2 3 4 renglón
A 14 0 11 0 10
B 4 12 0 4 10
C 0 2 5 3 15
D 0 8 3 1 11
columna de
reducción 0 0 0 1
Método Húngaro
Paso 3.- Determínese si la matriz es reducida.
Encuentre el número mínimo de líneas rectas que
se pueden trazar sobre los renglones y las
columnas para cubrir todos los ceros. Si este
número es igual al de renglones(o columnas), se
dice que la matriz es reducida; continúese con el
paso 5 en este caso. Si el número de rectas es
menor que el número de renglones(o columnas),
continúe en el paso 4.
Método Húngaro
Paso 4.- Reducciones posteriores. Encuentre la menor
de las celdillas no cubiertas( sin línea recta). Reste
el valor de esta celdilla a todas las celdillas no
cubiertas. Agréguelo al valor de las celdillas que se
encuentren en las intersecciones de las rectas
dibujadas en el paso 3. Deje como están las otras
celdillas. Regrese al paso 3 y ejecútelo con las
celdillas no cubiertas por las rectas
Método Húngaro
Paso 5.- Localización de la solución óptima. Ya es
posible encontrar una asignación usando sólo
celdillas que tengan costo cero. Queremos asignar
un elemento a cada destino. Para tener una
solución óptima debemos coger celdillas de costo
cero. El valor óptimo se encuentra de la matriz de
costos
Otras consideraciones
1.- El número de elementos a asignar y el
número de destinos no son iguales.
Cuando el número de destinos es menor, se crea un
destino ficticio con costos de asignación igual a
cero.
Cuando el número de elementos a asignar es menor,
entonces se crea un elemento ficticio con costos de
asignación igual a cero.
Otras consideraciones
2.- Problemas de maximización
Se aplica el método húngaro, con la variante
que en la reducción de renglones se toma el
mayor y se resta de éste los demás de la fila.
De este modo se procede con el método ya
enseñado.
Otras consideraciones
3.- Asignaciones inaceptables
Cuando se encuentre el inconveniente de
asignaciones inaceptables en la celdilla
correspondiente a esta asignación se
coloca un costo muy alto.