Clase de asignacion

Modelos de Transporte:
Problemas de asignación y
de transbordo
M. En C. Eduardo Bustos Farías

Problemas de Asignación

2

Problemas de Asignación:
Son problemas balanceados de transporte en los cuales
todas las ofertas y todas las demandas son iguales a
1.
Consiste en determinar la asignación óptima de agentes
u objetos indivisibles a n tareas.
Son indivisibles en el sentido de que ningúnagente se
puede dividir en varias tareas.
La restricción importante, para cada agente, es que
será designado a una y solo una tarea.
3

„

„

Uno de los problemas que utilizan el modelo
de transporte, es el de asignación, el cual se
refiere a la disposición de algunos recursos
(equipos o personas) para la realización de
ciertos productos o tareas a un costo
diferenciado.
El problema consiste enminimizar los costos
por asignación de recursos para el
desempeño de actividades.
4

Problemas de Asignación


Definición del Problema
* m trabajadores deben ser asignados a m trabajos.
* Un costo unitario (o ganancia) Cij es asociado al trabajador i
que realizara el trabajo j.
* Minimizar el costo total ( o maximizar la ganancia total) de la
asignación de trabajadores a sus respectivos empleos quele
corresponde a cada uno, tratando de que esta asignación
sea la óptima posible.

EJEMPLO 1
Electrónica Ballston
Problema de asignación

6

Electrónica Ballston


Existen 5 diferentes proyectos eléctricos sobre 5
líneas de producción que necesitan ser
inspeccionadas.



El tiempo para realizar una buena inspección de un
área de pende de la línea de producción y del área
de inspección.



Lagerencia desea asignar diferentes áreas de
inspección a inspectores de productos tal que el
tiempo total utilizado sea mínimo.



Datos
* Tiempo de inspección en minutos para la línea de
ensamble de cada área de inspección.

Linea
Ensamble

1
2
3
4
5

A
10
11
13
14
19

B
4
7
8
16
17

Area de Inspección
C
6
7
12
13
11

D
10
9
14
17
20

E
12
14
15
17
19

RED QUE REPRESENTA EL PROBLEMA
Línea deensamble
S1=1
1

Área de Inspección
A D1=1

S2=1

2

B

D2=1

S3=1

3

C D3=1

S4=1

4

D

D4=1

S5=1

5

E

D5=1



Supuestos restricciones
* El número de trabajadores es igual al número de empleos.
* Dado a que el problema esta balanceado, cada trabajador es
asignado sólo una vez y cada trabajo tiene exactamente un solo
trabajador.
* Para un problema desbalanceado se debe agregar un
trabajador“ficticio” (en el caso de que existan más trabajos que
trabajadores) o un empleo “ficticio” (en el caso de que existan
más trabajadores que trabajos), quedando así el problema
balanceado.

Solución mediante el método
Húngaro


Problema:
El profesor Michell ha terminado 4 capítulos de su libro y esta
pensando en pedir ayuda para terminarlo. El ha elegido a 4 secretarias
que podrían tipearle cada unode sus capítulos. El costo asociado
refleja la velocidad de la secretaria y la exactitud con la que realiza el
trabajo. Además los capítulo difieren en la cantidad de hojas y en la
complejidad. ¿Qué puede hacer el profesor si conoce la siguiente
tabla:
Capítulos
Secretaría
13
14
15
16
Juana
96
99
105 108
María
116
109
107
96
Jackeline
120
102
113 111
Edith
114
105
118 115



Restricciones delMétodo
* Solo problemas de minimización.
* Número de personas a asignar m es igual al número de
lugares m.
* Todas las asignaciones son posibles
* Una asignación por persona y una persona por asignación



Matriz de Costos
Secretaría
Juana
María
Jackeline
Edith

Capítulos
13
14
96
99
116
109
120
102
114
105

15
16
105 108
107
96
113 111
118 115



Restar el Menor valor de cada fila
SecretaríaJuana
María
Jackeline
Edith



Capítulos
13
14
15
0
3
9
20
13
11
18
0
11
9
0
13

16
12
0
9
10

Restar el menor valor de cada columna en la matriz
anterior
Secretaría
Juana
María
Jackeline
Edith

Capítulos
13
14
15
0
3
0
20
13
2
18
0
2
9
0
4

16
12
0
9
10



Trazar el mínimo número de líneas que cubran los
ceros de la matriz obtenida en el punto anterior.
Secretaría
Juana
María
Jackeline
Edith...