Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

EMPAREJAMIENTO MAXIMO DE MAXIMO PESOS EN GRAFOS BIPARTITOS

No description
by

María A

on 9 June 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of EMPAREJAMIENTO MAXIMO DE MAXIMO PESOS EN GRAFOS BIPARTITOS

PRESENTACIÓN DEL PROBLEMA
APLICACIONES NOTABLES
MODELO DE PROGRAMACIÓN MATEMÁTICA
RESULTADOS
TEÓRICOS

Matriz TUM
(unimodularidad)
Teorema de
Holgura Complementaria
Teorema fundamental de la asignación
, (algoritmo húngaro).
Teorema
Primal-Dual
Teorema de König
(algoritmo auxiliar)
Asignación de puestos de trabajo en una empresa.
PROBLEMA PRIMAL
ALGORITMOS
Algoritmo Húngaro (O(n3))
PASO INICIAL:
(Obtención matriz reducida)
Buscar el mínimo de cada fila y restarlo a todos los elementos de esa fila.
A partir de la matriz anterior, buscar el mínimo de cada columna y restarlo a todos los elementos de esa columna.
PASO PRINCIPAL:

Trazar el mínimo número(n) de líneas sobre las filas y columnas para cubrir todos los ceros. (
Algoritmo auxiliar
)
n=m :Solución óptima.
Seleccionar el mínimo elemento no tachado. Restarlo a cada elemento no tachado y sumarlo a los tachados por dos líneas .
PROBLEMA DUAL

TUM
PROBLEMA PRIMAL
RELAJADO
EJEMPLO
Para cubrir los ceros, se ha usado el siguiente resultado teórico...
"El número máximo de celdas cero independientes en una matriz de asignación reducida es igual al mínimo número de líneas que cubren todos los ceros de la matriz."
El mínimo número de lineas es 3.
El mínimo elemento no tachado es 1.
Restamos dicho elemento a cada elemento no tachado.
Sumamos a los tachados por dos líneas este número.
Portales de citas:
Meetic.
¿PARA QUÉ SURGIÓ?
Y AHORA
HAZLO TÚ

EMPAREJAMIENTO MÁXIMO DE MÁXIMO PESO EN GRAFOS BIPARTITOS
BIBLIOGRAFÍA
Sean dos conjuntos U y V, tal que card(U)=n, card(V)=m.
Nuestro objetivo es formar el máximo número de parejas entre dichos conjuntos, de tal manera que la suma total de los pesos de las aristas sea el mayor posible.

REVOLUCIÓN INDUSTRIAL
1
2
8
1
6
1
Marta (a), Sara (b), Ángela (c), Natalia (d) y Gema (e) tendrán una cita con Marcos (1), Ricardo (2), Alberto (3), Jesús (4) y Óscar (5). ¿Cómo podemos formar las parejas de forma que, en conjunto, las chicas sean lo más felices posible?
(Lo que le gusta cada chico a cada una de las chicas queda recogido en la siguiente matriz)
https://compdiscretas.wordpress.com/4-3-teoria-de-emparejamiento/
https://es.slideshare.net/binnasser2007/kuhn-munkres-algorithm
https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture10.pdf
https://www.topcoder.com/community/data-science/data-science-tutorials/assignment-problem-and-hungarian-algorithm/
https://prezi.com/lra7sohxqpnd/problema-de-emparejamuento-de-maximo-peso/
http://www.est.uc3m.es/esp/nueva_docencia/comp_col_leg/ing_info/io/doc_generica/archivos/ocr.pdf
http://eenube.com/images/pdf/emparejamiento.pdf
http://ma1.eii.us.es/Material/FTG_itis_Tema5.pdf
Mokhtar S. Bazaraa, Jhon J. Jarvis.(1996) "Programación Lineal y flujo en redes" Limusa Noriega Editores
Peso máximo del emparejamiento : -5
0
-1
-2
1
-3
SOLUCIÓN
SOLUCIÓN
a

b
c
d
e
6
4
5
3
6
Peso máximo del emparejamiento : 24
Justificación teórica del algoritmo
1. Método Primal-Dual
Sol. factible dual
Sol factible primal
Holgura complementaria
Sol factible dual (Kuhn):
3. Tabla de costes reducidos / Variables de holgura duales
Variable de holgura de la restricción ij-ésima del dual
Elemento ij-ésimo de la tabla de costes del algoritmo
0 en la tabla
No hay holgura en la ij-ésima restricción del dual
La variable del primal asociada (Xij) puede ser mayor que cero, es decir, podemos asignarle el valor 1
Tma Holgura Complementaria
Factibilidad primal
Exactamente una Xij con valor 1 en cada renglón y en cada columna.
No parar hasta que el mínimo número de ceros asignados o líneas para tachar sea m.
4. Justificación del algoritmo auxiliar
2. Teorema fundamental de la asignación
"Si a todos los elementos de una fila o de una columna de una matriz de rendimientos se le suma o se le resta una cantidad constante la asignación óptima no varía."
Martínez Álvarez, Miriam
Díaz Hernández, Marina
Antón Prieto, María
Martín Sierra, Pablo
Revuelto Ruiz, Mercedes
Santana Belchi, Álvaro
Trabajo realizado por:
Full transcript