martes, 6 de septiembre de 2011

Tabla Resumen

Tabla resumen: Problema de Asignación
Características
Observación
Página
Historia del modelo

En 1941 F. L. Hitchcock publica una solución analítica a este problema
En 1972 Thomas Jefferson quien lo sugirió para asignar a cada representante por estado.
Debe su nombre a asignar hombres a trabajos
La estructura particular del problema hace que las soliciones  sean degeneradas y permitió a los matematicos húngaros Köning y Egerváry demostrar un teorema esencial para el desarrollo del Método Húngaro.
http://en.wikipedia.org/wiki/Frank_Lauren_Hitchcock
http://es.wikipedia.org/wiki/Thomas_Jefferson
Elementos
·         Consiste en asignar recursos a tarea en función de un objetivo ligado a la eficiencia del sistema
·         Minimizar el costo total de operación de modo que: cada tarea asigne a una y sólo una máquina, cada máquina realice una y sólo una tarea
·        
·         Matriz de costos
·         Debe ser balanceado para que la matriz de costos sea cuadrada
http://www.slideshare.net/josekh89/problema-de-asignacin
Ejemplo
Un ejemplo típico es el de asignación de personas a turnos horarios, o el de asignar personas a maquinas.
En un cierto punto del algoritmo tenemos el grafo G \, y la matriz C^\prime\,.
http://upload.wikimedia.org/wikipedia/commons/6/63/Matching_maximo.PNG
matching máximo del grafo de las igualdades.
C'=\begin{pmatrix} 1 & 2 & 7 & 3 & 0 \\ 3 & 4 & 1 & 0 & 2 \\ 2 & 3 & 6 & 0 & 0 \\ 0 & 6 & 1 & 1 & 0 \\ 2 & 0 & 0 & 4 & 5 \end{pmatrix}

En G \, tengo un arco \Longleftrightarrow \; tengo un 0 \, enC^\prime\,.

M =\{ (1,5'), (2,4'), (4,1'), (5,3') \}\, es matching máximo pero no es perfecto, pues la fila 3 está sin asignar. \Rightarrow \; volvemos al paso (3) \, del algoritmo.

(a) \,
\begin{pmatrix} & & & & & \\ & 1 & 2 & 7 & 3 & 0 \\ & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix} \Rightarrow \;
(b) \,
\begin{pmatrix} & & & & \star\;& \star\;\\ & 1 & 2 & 7 & 3 & 0 \\ & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix} \Rightarrow \;

(c) \, El matching de las columnas 4'\, y 5'\, esta acopladas al de las filas 1\, y 2 \Rightarrow \;

(d) \,
\begin{pmatrix} & & & & \star\;& \star\;\\ \star \; & 1 & 2 & 7 & 3 & 0 \\ \star \; & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix} \Rightarrow \;
(e) \,
\begin{pmatrix} & & & & \star\;& \star\;\\ \star \; & 1 & 2 & 7 & & \\ \star \; & 3 & 4 & 1 & & \\ \star \; & 2 & 3 & 6 & & \\ & & & & & \\ & & & & & \end{pmatrix} \Rightarrow \;
(f) \,
\delta =min \begin{pmatrix} 1 & 2 & 7 \\ 3 & 4 & 1 \\ 2 & 3 & 5 \end{pmatrix}= 1
(g) \, Resto \delta\, a los elementos no borrados de C^\prime\, y sumo \delta\, a los elementos doblemente borrados de C^\prime\,.

C'=\begin{pmatrix} 0 & 1 & 6 & 3 & 0 \\ 2 & 3 & 0 & 0 & 2 \\ 1 & 2 & 5 & 0 & 0 \\ 0 & 6 & 1 & 2 & 1 \\ 2 & 0 & 0 & 5 & 6 \end{pmatrix} \Rightarrow \;

(h) \, Volvemos al paso (1) \,, para recrear el grafo de las igualdades y calcular de nuevo el matching máximo.
http://www.slideshare.net/josekh89/problema-de-asignacin

http://es.wikipedia.org/wiki/Algoritmo_H%C3%BAngaro
Método de Solución
Método Simplex
Técnica del transporte
Método Húngaro
(1) \, Dada la matriz de costes C \,, se construye C^\prime\, encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C}_{i,j}-\min \mathit{C}_{i,j}
( 2 ) \, Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C'}_{i,j}-\min \mathit{C}_{i,j}
(3) \, A partir de \mathit{C'}\, se considera "grafo de las igualdades" a G=(N1,N2,A) \, tal que A \, está constituido por todas las copias ({i,j})\, tales que \mathit{C'}_{i,j}=0 \,. En otras palabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.
Determinar sobre G\, un matching M\, de cardinalidad máxima.

si |\mathit{M}| = |N_1| = |N_2| \Rightarrow \; STOP
Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina el algoritmo.

(a) \, Considero C^\prime\, y se etiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.
(b) \, Se etiquetan en C^\prime\, las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).
(c) \, Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por el algoritmo de matching máximo con las columnas ya etiquetadas (con *).
(d) \, Repetir los pasos (b) \, y (c) \, hasta que no halla más filas o columnas que etiquetar.
(e) \, Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.
(f) \, Sea \delta\, el elemento de C^\prime\, de valor mínimo entre aquellos costos no borrados (o tarjados) en el paso anterior.
(g) \, Restar \delta\, a cada elemento no borrado y sumarlo a los elementos doblemente borrados (o donde haya intersección o cruces entre las líneas marcadas en el paso (e) \, )
(h) \, Volver al paso (1) \,.
http://www.slideshare.net/josekh89/problema-de-asignacin


http://es.wikipedia.org/wiki/Algoritmo_H%C3%BAngaro
Programas existentes
El programa InvOp (361 kb)
Win QSB
TORA
LINDO
SB2
http://www.investigacion-operaciones.com/Metodos_computacionales.htm
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)