Hungaro Noroeste CostoMinimo Vogel Percy

Modelo de Asignación de
Recursos
y
Modelo de Transportes
Ing. Percy Segura Vigil

Problema de Asignación
El problema de asignación es un tipo especial de problema de
programación lineal en el que los asignados son recursos
destinados a la realización de tareas.
Para que el problema se ajuste a la definición de un problema de
asignación, es necesario que este tipo de aplicaciones se formule
de lasiguiente manera:
1.
2.
3.
4.

El número de asignados es igual al número de tareas.
Cij se asigna solo una tarea.
A cada asignado
Cada tarea debe realizarla solo un asignado.
Existe un costo
asociado con el asignado i que realiza la
tarea j.
5. El objetivo es determinar cómo deben hacerse las asignaciones
para minimizar los costos totales.
2
Ing. Percy Segura Vigil

Método Húngaro
1. En lamatriz original del costo, identificar el mínimo de
cada renglón y restarlo de todos los elementos del
renglón
2. En la matriz que resulte del paso 1, identificar el mínimo
de cada columna, y restarlo de todos los elementos de la
columna.
3. Identificar la solución óptima como la asignación factible
asociada con los elementos cero de la matriz obtenida en
el paso 2.

Ing. Percy Segura Vigil

3Ejemplo:
Los tres hijos de José, Pedro, Karen y Juan, quieren ganar algo de
dinero para sus gastos personales, durante un viaje de la escuela al
zoológico. El señor José ha destinado tres tareas para sus hijos:
podar el pasto, pintar la cochera y lavar los autos de la familia.
Para evitar discusiones, les pide que presenten ofertas secretas
que es un pago justo para cada una de las tres tareas. Latabla
muestra las ofertas recibidas.
Podar Pintar lavar
Pedro
15
10
9
Karen
9
15
10
Juan
10
12
8
Con base a esta información ¿Cómo debe asignar las tareas el
señor José?
Ing. Percy Segura Vigil

4

Podar Pintar
Pedro
15
10
Karen
9
15
Juan
10
12

lavar
9
10
8

9
9
8

Seleccionar el valor mas
pequeño para cada fila.
Seleccionar el valor mas
pequeño para cada columna.

Podar Pintar
Pedro
6
1
Karen
0
6Juan
2
4
0
1
Resultado:
Pedro: Pintar = $10
Karen: Podar = $9
Juan: lavar = $8
Total:
$27
Ing. Percy Segura Vigil

lavar
0
1
0
0
Podar Pintar
Pedro
6
0
Karen
0
5
Juan
2
3

lavar
0
1
0
5

El ejemplo anterior se amplía a cuatro hijos y cuatro tareas. La
siguiente tabla resume los elementos de costo en el problema.

Tarea
1
2
Niñ 3
o 4

Ing. Percy Segura Vigil

1
1
9
4
8

2
4
7
5
7

3
6
10
11
8

4
39
7
5

6

Tarea

Niñ
o

1
2
3
4

1
1
9
4
8

2
4
7
5
7

Tarea
3
6
10
11
8

4
3
9
7
5

1
7
4
5

1
2
Niñ 3
o 4

1
0
2
0
3

2
3
0
1
2

3
5
3
7
3

4
2
2
3
0

0
0
3
0
Identificamos los valores
mínimos por columna.

Identificamos los valores
mínimos por fila.
Asignación de tareas.
Tarea
1
2
Niñ 3
o 4
Ing. Percy Segura Vigil

1
0
2
0
3

2
3
0
1
2

3
2
0
4
0

4
2
2
3
0
7

Otro caso
En algunos casos losceros que se producen en los pasos 1 y 2 no
producen una solución factible en forma directa. En este caso se
necesitan mas pasos para llegar a la asignación óptima.
2ª. Si no se puede asegurar una asignación factible con los pasos
1 y 2,
i) Trazar la cantidad mínima de líneas horizontales y verticales
en la última matriz reducida que cubran todos los elementos
cero.
ii) Seleccionar el elementomínimo no cubierto, restarlo de todo
elemento no cubierto y a continuación sumarlo a todo
elemento en la intersección de dos líneas.
iii) Si no se puede encontrar una asignación factible entre los
elementos cero que resulten, repetir el paso 2ª. En caso
contrario, seguir en el paso 3 para determinar la asignación
8
Ing. Percy Segura
Vigil
óptima.

Tarea
1
2
Niñ 3
o 4

1
0
2
0
3

2
3
0
1
2

3
2
0
4
04
2
2
3
0

3
1
0
3
0

4
1
2
2
0

Tarea
1
2
Niñ 3
o 4

Ing. Percy Segura Vigil

1
0
3
0
4

2
2
0
0
2

Solucion
Niño 1: Tarea
Niño 2: Tarea
Niño 3: Tarea
Niño 4: Tarea
Total:

1
3
2
4

=
=
=
=

1
10
5
5
$21 9

Modelo Matemático
min

C
i

i, j

X i, j

j

s. a.

X

i, j

1 i

j

 X i, j 1 j
i

X i , j  0,1
Ing. Percy Segura Vigil

Donde :
i : Niño .
j :Tarea .
Ci , j : Costo de asignar...