TRABAJO FIN DE CARRERA - UPM
Transcript of TRABAJO FIN DE CARRERA - UPM
UNIVERSIDAD POLITÉCNICA DE MADRID FACULTAD DE INFORMÁTICA
TRABAJO FIN DE CARRERA
ESTABILIDAD EN EMPAREJAMIENTOS
AUTOR: JULIO ORTEGA DÍAZ
TUTOR: GREGORIO HERNANDEZ PEÑALVER
FECHA DE PRESENTACIÓN: 6 de Septiembre de 2017
ÍNDICE
1 INTRODUCCIÓN ................................................................................................................ 1
1.1 Historia .......................................................................................................................... 1
1.2 Objetivos ....................................................................................................................... 2
1.3 Alcance .......................................................................................................................... 3
2 TEORÍA ................................................................................................................................ 5
2.1 Emparejamientos ........................................................................................................... 5
2.2 El problema de los Matrimonios Estables ..................................................................... 7
2.3 El Algoritmo GALE-SHAPLEY ................................................................................. 10
2.4 Variantes del Problema ............................................................................................... 15
2.4.1 Listas Incompletas ............................................................................................... 16
2.4.2 Empates en las Preferencias ................................................................................ 19
2.4.3 Compañeros de Habitación ................................................................................. 21
3 DISEÑO DE LA APLICACIÓN ........................................................................................ 27
3.1 Introducción ................................................................................................................ 27
3.2 Diseño de Alto Nivel ................................................................................................... 27
3.2.1 Límites del Sistema ............................................................................................. 28
3.2.2 Diagrama de Casos de Uso .................................................................................. 29
3.2.3 Actores ................................................................................................................ 33
3.2.4 Casos de Uso en Formato Extendido .................................................................. 33
3.3 Diseño de Bajo Nivel .................................................................................................. 50
3.3.1 Diagrama de Clases ............................................................................................. 50
4 MANUAL DE USUARIO .................................................................................................. 65
4.1 Partes de la Aplicación ................................................................................................ 65
4.1.1 Barra de Menús ................................................................................................... 65
4.1.2 Barra de Herramientas ......................................................................................... 69
4.1.3 Interfaz de Ejecución ........................................................................................... 70
4.1.4 Panel .................................................................................................................... 76
4.1.5 Información ......................................................................................................... 80
4.2 Operaciones ................................................................................................................. 80
4.2.1 Herramientas ....................................................................................................... 81
4.2.2 Preferencias ......................................................................................................... 83
4.2.3 Emparejamientos ................................................................................................. 86
4.3 Ejecución ..................................................................................................................... 89
5 CONCLUSIONES .............................................................................................................. 97
6 BIBLIOGRAFÍA ................................................................................................................. 99
6.1 Páginas Web .............................................................................................................. 100
Estabilidad en Emparejamientos
1
1 INTRODUCCIÓN
Existen numerosas situaciones de la vida real donde podemos encontrar problemas de
asignación, el objetivo principal es encontrar emparejamientos entre grupos que
verifiquen ciertas propiedades deseables. Esta problemática aparece en el ámbito de las
relaciones personales, el mercado laboral o inmobiliario, la asignación de estudiantes a
universidades u hospitales, etc.
1.1 Historia
A mediados del siglo XX, en Estados Unidos, surgió la necesidad de contar con un
servicio centralizado que permitiese organizar la asignación de residentes a los
hospitales según sus preferencias, y en 1951 se diseñó el llamado NRMP (National
Resident Matching Program). El éxito del NRMP radicaba en encontrar
emparejamientos estables, por lo que si un estudiante no quedaba asignado a su hospital
favorito era porque el hospital tenía sus vacantes cubiertas con estudiantes a los que
prefería.
Sin embargo, David Gale y LLoyd Shapley fueron, en 1962, los encargados de plantear
y resolver matemáticamente el problema de las asignaciones estables en problemas de
tipo bilateral, donde existen dos grupos en los que se puede tanto demandar como
ofertar.
Gale y Shapley demostraron que siempre existe un emparejamiento estable para
cualquier conjunto de listas de preferencias, siempre que la lista de preferencias de cada
individuo incluya a todos los individuos del conjunto opuesto. Un emparejamiento entre
dos grupos, los proponentes y los propuestos, se dice que es estable de acuerdo con las
listas de preferencias de cada individuo, cuando no existe un proponente y un propuesto
no emparejados que se prefieren entre sí antes que a su pareja asignada.
También demostraron que existe un emparejamiento óptimo para uno de los dos
conjuntos, de manera que cada individuo está en su mejor asignación posible, y si
Estabilidad en Emparejamientos
2
hubiera otro emparejamiento estable, estaría igual o menos conforme según sus
preferencias.
Este algoritmo, así como su aplicación al problema de los residentes/hospitales y otras
variantes del problema aplicadas en contextos reales (como por ejemplo alumnos y
escuelas en la región de Nueva York), les valió a LLoyd Shapley y Alvin Roth el
premio Nobel de Economía en el año 2012.
1.2 Objetivos
El objetivo principal de este proyecto es poner a disposición del usuario una aplicación
software que permita encontrar emparejamientos estables entre grupos de la misma
cardinalidad. La aplicación se ha denominado EeE, que son las siglas de “Estabilidad en
Emparejamientos”.
El usuario tiene la posibilidad de definir una serie de preferencias entre los integrantes
de los dos grupos sobre los que se pretende establecer un emparejamiento; para ello se
generan dos matrices de la misma cardinalidad en las que se recogen todas las
preferencias individuales.
Los algoritmos que se pueden aplicar son el algoritmo de “Gale-Shapley sobre listas
completas” y el algoritmo de “Gale-Shapley sobre listas incompletas”. La diferencia
fundamental entre estos dos algoritmos radica en que el segundo permite listas en las
que se omite las preferencias inaceptables, mientras que el primero no tolera la
inaceptabilidad y por lo tanto las listas deben incluir a todos los miembros del grupo
opuesto. Además, la aplicación permite la generación de matrices de preferencia de
forma aleatoria.
Esta aplicación es una herramienta orientada a la enseñanza con un carácter
marcadamente didáctico. Esta circunstancia es el motivo por el que los algoritmos se
pueden ejecutar en distintas modalidades: paso a paso, todos los pasos o solución final.
De esta manera se permite enfatizar determinados aspectos de los algoritmos para
Estabilidad en Emparejamientos
3
visualizar sus pasos intermedios y facilitar su comprensión, o acceder directamente a la
solución final.
1.3 Alcance
El alcance del proyecto incluye los siguientes productos:
• Código fuente de la aplicación con lenguaje de programación Java.
• Binario de la aplicación en formato Java Archive (.jar) ejecutable en cualquier
sistema operativo que soporte la máquina virtual de Java (versión 8 o superior).
• Aplicación con soporte multi-idioma (Español/Inglés).
• Documentación del proyecto que incluye conceptos teóricos del problema,
diseño de la aplicación y manual de usuario.
• Página web en HTML desde la que acceder a los contenidos del proyecto.
Estabilidad en Emparejamientos
4
Estabilidad en Emparejamientos
5
2 TEORÍA
2.1 Emparejamientos
En matemática discreta, dado un grafo G = (V, A), un emparejamiento E en G (también
conocido como matching) es un conjunto de aristas no adyacentes entre sí o
independientes, es decir, sin vértices en común.
Existen diferentes tipos de emparejamientos:
• Un emparejamiento máximo es un emparejamiento que contiene el número
máximo posible de aristas. Por lo tanto, no puede estar contenido en otro de
cardinal mayor.
• Un emparejamiento maximal es un emparejamiento que no puede crecer por
agregado de una arista. Cumple la propiedad de que al añadir alguna arista que
no pertenece al emparejamiento, se deshace el emparejamiento.
• Un emparejamiento perfecto es un emparejamiento que cubre todos los vértices
del grafo, es decir, cada vértice forma parte del emparejamiento.
Atendiendo a las definiciones anteriores se puede formular los siguientes teoremas:
• Puede haber muchos emparejamientos máximos.
• Los emparejamientos máximos son maximales, pero no todos los
emparejamientos maximales son máximos.
• Cada emparejamiento perfecto es máximo y maximal.
Estabilidad en Emparejamientos
6
Figura 2.1: Tipos de emparejamiento
Los problemas de emparejamiento guardan una importante relación con los grafos
bipartitos. Un grafo G = (V, A) se dice bipartito si el conjunto de vértices V puede
separarse en dos conjuntos disjuntos V = X ∪ Y de tal manera que las aristas del grafo
unen siempre un vértice de X con uno de Y, es decir, no hay aristas entre los vértices de
X ni entre los vértices de Y.
En este tipo de grafos, un emparejamiento también puede definirse como una función
que establece una correspondencia uno a uno entre un subconjunto de X y un
subconjunto de Y. Los emparejamientos sobre grafos bipartitos cumplen la propiedad de
que un emparejamiento completo también es emparejamiento máximo y sólo puede
darse si los dos conjuntos X e Y tienen el mismo número de vértices.
Para obtener un emparejamiento máximo bipartito, es necesario definir previamente un
par de conceptos:
• un camino alterno es un camino en el cual sus aristas alternativamente
pertenecen y no pertenecen al emparejamiento.
• un camino incremento es un camino alterno que comienza y termina en un
vértice libre.
La manera de proceder para obtener un emparejamiento máximo bipartito consiste en ir
incrementando paso a paso el cardinal del emparejamiento mediante caminos
incremento hasta obtener un emparejamiento máximo.
Estabilidad en Emparejamientos
7
Figura 2.1: Emparejamiento máximo bipartito
Para abordar los problemas de asignación óptima es necesario definir el concepto de
grafo bipartito ponderado, que no es más que un grafo en el que cada arista tiene
asociado un valor. Sobre este tipo de grafos, un emparejamiento máximo bipartito
ponderado se define como un emparejamiento perfecto donde la suma de los valores de
sus arcos tiene un valor máximo. Si el grafo no es completamente bipartito, los arcos
ausentes son introducidos con valor cero. El problema del emparejamiento máximo
bipartito ponderado se puede resolver aplicando el algoritmo Húngaro.
2.2 El problema de los Matrimonios Estables
El problema de los matrimonios estables es el problema “base” de los problemas de
asignación. Se parte de dos conjuntos de mujeres y hombres, con el mismo cardinal y
cada uno con su propia lista de preferencias, y se pretende encontrar la mejor manera de
emparejarlos para que todos queden satisfechos. Este escenario general, puede utilizarse
como modelo para gran variedad de problemas con interpretación práctica.
En términos generales, un problema de asignación busca establecer un emparejamiento,
es decir, una correspondencia entre agentes pertenecientes a diferentes conjuntos. En el
problema de los matrimonios estables se busca encontrar un emparejamiento entre
individuos de dos conjuntos disjuntos que cumpla con la propiedad de estabilidad. Se
dice que un emparejamiento es estable si no existe ningún par de agentes que hubieran
preferido estar juntos, antes que con su pareja actual. Si existiera dicho par, el mismo es
denominado par bloqueante.
Estabilidad en Emparejamientos
8
Para plantear el problema clásico de los matrimonios estables, se necesitan los
siguientes elementos:
• Dos conjuntos finitos, disjuntos entre sí y de la misma cardinalidad. M = {m1, ..,
mn} y H = {h1, .., hn} (card(M) = card(H) = n) denotan el conjunto de hombres
y mujeres respectivamente.
• Cada persona tiene una lista de preferencias estrictamente ordenada
(comenzando con la persona de sexo opuesto sobre la que muestra más interés)
en la que incluye a todos los integrantes del conjunto opuesto.
Es interesante destacar que las listas de preferencias de mujeres y hombres, se
pueden denotar por matrices n * n, por lo tanto, existen dos matrices de preferencias
(una para las mujeres y otra para los hombres).
Bajo estas condiciones, una vez establecidos los conjuntos y las listas de preferencias,
se puede obtener emparejamientos o matrimonios estables basados en los siguientes
conceptos:
• Un emparejamiento E, es una correspondencia entre mujeres y hombres que
verifica las siguientes condiciones:
o E es biyectiva
o ∀h ∈ H, E(h) ∈ M ∪ ∅
o ∀m ∈ M, E(m) ∈ H ∪ ∅
o E(h) = m ↔ E(m) = h
• El par (h, m) con h ∈ H y m ∈ M, es bloqueante del emparejamiento E si se
verifican las condiciones siguientes:
o E(h) ≠ m
o E(m) ≠ h
o h prefiere a m antes que a E(h)
o m prefiere a h antes que a E(m)
• Un emparejamiento E es estable si no existe en él un par bloqueante.
Estabilidad en Emparejamientos
9
Adicionalmente se pueden definir los siguientes conceptos sobre emparejamientos
estables:
• Un emparejamiento E es perfecto si verifica las dos condiciones siguientes:
o ∀h ∈ H, E(h) ∈ M
o ∀m ∈ M, E(m) ∈ H
• Un emparejamiento E es óptimo para el conjunto A si cumple las dos
condiciones siguientes:
o E es estable
o ∀a ∈ A, a prefiere a E(a) antes que a E’(a), ∀E’ emparejamiento estable
• Un emparejamiento E es pésimo para el conjunto A si cumple las dos
condiciones siguientes:
o E es estable
o ∀a ∈ A, a prefiere a E’(a) antes que a E(a), ∀E’ emparejamiento estable
• Diremos que (h, w) es una pareja válida si existe E emparejamiento estable tal
que E(h) = m
A continuación, se plantea un ejemplo del problema de matrimonios estables, con una
instancia de tamaño n=4 y los conjuntos H={h0,h1,h2,h3} (hombres) y
M={m0,m1,m2,m3} (mujeres), donde cada miembro tiene una lista de preferencias con
respecto al conjunto opuesto.
h0 m0 m1 m2 m3
h1 m2 m1 m3 m0
h2 m2 m1 m3 m0
h3 m1 m2 m3 m0
m0 h0 h2 h3 h1
m1 h0 h1 h2 h3
m2 h1 h2 h0 h3
m3 h3 h0 h2 h1
Estabilidad en Emparejamientos
10
En esta instancia, el emparejamiento E1={(h0, m0),(h1, m2),(h2, m1),(h3, m3)} es
estable.
Para verificar la estabilidad se debe comprobar que todos los posibles pares no bloquean
el emparejamiento, aunque más eficientemente basta con comprobar sólo los posibles
pares bloqueantes; que en este caso son: (h2, m2), (h3, m1) y (h3, m2).
Observando las listas de preferencias de m1 y de m2 puede apreciarse que ambas
prefieren a sus parejas asignadas antes que a las parejas de los pares bloqueantes. Se ve
fácilmente que la mujer m2 prefiere al hombre que le fue asignado en el
emparejamiento, antes que al hombre h2 y al h3, y que la mujer m1 prefiera a su pareja
actual antes que al hombre h3. Por lo que no hay pares bloqueantes para E1.
En cambio el emparejamiento E2={(h0,m1),(h1,m2),(h2,m0),(h3,m3)} no es estable ya
que el par (h0,m0) bloquea el emparejamiento, pues el hombre h0 prefiere estar con la
mujer m0 antes que con su pareja actual m1, y m0 prefiere estar con el hombre h0 antes
que con su pareja actual h2.
2.3 El Algoritmo GALE-SHAPLEY
En 1962 Gale y Shapley probaron que, para cualquier instancia del problema de
matrimonios estables con listas de preferencias completas y estrictas, existe por lo
menos un emparejamiento que cumple con la propiedad de estabilidad.
Estos autores probaron este resultado a través de un algoritmo que siempre encuentra un
emparejamiento para cualquier instancia dada. Por otro lado, demuestran que el
algoritmo siempre le otorga a cada hombre (mujer, si los roles se invierten) la mejor
pareja según su lista de preferencias, con respecto a las asignaciones que le hubieran
tocado en cualquier otro emparejamiento estable.
Hay que tener en cuenta que el algoritmo puede adoptar dos versiones. Una versión
orientada a hombres en la que son los hombres quienes comienzan las proposiciones y
Estabilidad en Emparejamientos
11
la contraria, una versión orientada a mujeres que, por lo general obtiene distintos
resultados. En este caso, se va a trabajar con la versión orientada a hombres.
El algoritmo de Gale-Shapley se puede describir como una secuencia de propuestas de
los hombres hacia las mujeres siguiendo las siguientes etapas:
• Primera etapa: Cada hombre le propone un compromiso a su mujer preferida.
• Segunda etapa: Cada mujer que haya recibido al menos una propuesta, rechaza a
todos los hombres salvo al más preferido de todos los que la pretendieron. Al
elegido lo mantiene, pero puede cambiar de opinión ya que en las siguientes
etapas puede obtener una propuesta mejor. Los hombres que no han sido
rechazados en esta etapa quedan comprometidos con la mujer que los aceptó.
• Tercera etapa: los hombres que han sido rechazados en una etapa previa le
proponen un compromiso a la próxima mujer en su lista de preferencias (mujer
que no le haya rechazado). Las mujeres vuelven a realizar el mismo
procedimiento de elección descrito en la segunda etapa. Se realizará este
procedimiento hasta llegar a lo descrito en la última etapa.
• Última etapa: el algoritmo para cuando ningún hombre es rechazado y cada
hombre queda comprometido con alguna mujer. El algoritmo debe parar en
alguna etapa porque solo hay un número finito de hombres y mujeres y ningún
hombre hace propuestas a ninguna mujer más de una vez.
A medida que se va avanzando en el algoritmo, los hombres que van siendo rechazados
son cada vez menos favorecidos, mientras que cada mujer que va recibiendo mayor
cantidad de propuestas, termina mejor favorecida. Por lo tanto, el emparejamiento
obtenido es óptimo para el conjunto que hace las propuestas, y es el peor para el
conjunto que las recibe. En este caso, el emparejamiento obtenido es óptimo-masculino.
Si invertimos los roles en el algoritmo, de forma tal que la mujer realice las propuestas,
el emparejamiento resultante será óptimo-femenino.
Estabilidad en Emparejamientos
12
A continuación, se explica de forma practica el funcionamiento del algoritmo. Sean los
conjuntos H={h1,h2,h3, h4} y M={m1,m2,m3,m4} con las siguientes preferencias:
Primera etapa. Los hombres proponen compromiso a sus mujeres favoritas, de manera
que h1, h2 y h3 proponen compromiso a m1 y h4 a m3.
h1 m1
h2 m1
h3 m1
h4 m3
Segunda etapa. Ahora, las mujeres seleccionan su mejor propuesta, por lo tanto m1
selecciona a h3 y m3 a h4. La asignación provisional queda de la siguiente manera.
h1 m1
h2 m1
h3 m1
h4 m3
Tercera etapa. Los hombres h1 y h2 son los rechazados en la anterior etapa, por tanto
van a proponer un compromiso a su segunda opción, que para ambos es la mujer m2.
h1 m1 m2 m3 m4
h2 m1 m2 m3 m4
h3 m1 m2 m3 m4
h4 m3 m4 m2 m1
m1 h3 h2 h1 h4
m2 h4 h1 h3 h2
m3 h4 h3 h2 h1
m4 h1 h2 h3 h4
Estabilidad en Emparejamientos
13
h1 m1 m2
h2 m1 m2
h3 m1 m1
h4 m3 m3
Segunda etapa'. Nuevamente las mujeres con más de una propuesta seleccionan al
hombre con mayor preferencia. Por tanto, m2 rechaza a h1 y se queda con h2, dejando
la asignación provisional de la siguiente manera.
h1 m1 m2
h2 m1 m2
h3 m1 m1
h4 m3 m3
Tercera etapa'. El único hombre rechazado es h2, por tanto, propone matrimonio a su
tercera opción, la mujer m3.
h1 m1 m2 m2
h2 m1 m2 m3
h3 m1 m1 m1
h4 m3 m3 m3
Segunda etapa''. La mujer m3 rechaza a h2 dado que ya está emparejada con su hombre
preferido, dejando la asignación provisional de la siguiente manera.
Estabilidad en Emparejamientos
14
h1 m1 m2 m2
h2 m1 m2 m3
h3 m1 m1 m1
h4 m3 m3 m3
Tercera etapa''. El hombre h2 propone matrimonio a su siguiente y última opción, la
mujer m4.
h1 m1 m2 m2 m2
h2 m1 m2 m3 m4
h3 m1 m1 m1 m1
h4 m3 m3 m3 m3
Última etapa. La mujer m4 acepta la proposición de h2 dado, por lo tanto, esta es la
última etapa del algoritmo y obtenemos la siguiente asignación estable para este
ejemplo.
h1 m2
h2 m4
h3 m1
h4 m3
El algoritmo de Gale-Shapley cumple las siguientes propiedades:
• Termina en un número finito de pasos. Si tenemos n proponentes y n propuestos,
el algoritmo terminaría como máximo en n2 pasos, debido a que cada
proponente realiza a lo sumo n proposiciones diferentes.
Estabilidad en Emparejamientos
15
• Genera un emparejamiento perfecto.
• Genera un emparejamiento estable.
• No rechaza ninguna pareja válida.
• Proporciona un emparejamiento óptimo para los proponentes y pésimo para los
propuestos.
• El emparejamiento obtenido es independiente del orden de las proposiciones.
• El emparejamiento obtenido no permite que más de un proponente quede
emparejado con su última opción.
2.4 Variantes del Problema
Como se ha mencionado anteriormente, el problema de los matrimonios estables es el
problema “base” de los problemas de asignación, pero existe una serie de trabajos que
plantean variantes al problema original. En esta sección citaremos los más conocidos.
En el capítulo anterior se contempla el problema original formulado por Gale y Shapley
con grupos de la misma cardinalidad y listas de preferencias estrictas y completas, de tal
forma que cada individuo de cada grupo está en la lista de preferencias de todos los
individuos del otro grupo y además estas preferencias no tienen indiferencias.
A continuación, presentamos las siguientes variantes del problema:
• Listas incompletas: 2 grupos de la misma cardinalidad con listas de preferencias
estrictas pero incompletas.
• Empates en las preferencias: 2 grupos de la misma cardinalidad con listas de
preferencias no estrictas.
• Compañeros de habitación: 1 único grupo de cardinalidad par.
Estabilidad en Emparejamientos
16
2.4.1 Listas Incompletas
En esta variante, se estudia el problema cuando las listas de preferencia no son
completas, es decir, cada individuo puede tener inaceptables en el otro grupo a los que
omite en su lista de preferencias; aunque las preferencias de los aceptables siguen
siendo estrictas.
Cuando los participantes de ambos conjuntos no están obligados a incluir en sus listas
de preferencias a todos los miembros del otro conjunto, aparece un tipo de listas
conocido con el nombre de listas incompletas. En este caso, dado una mujer m y un
hombre h, si la mujer m no incluye al hombre h en su lista, quiere decir que m prefiere
quedarse soltera antes que emparejada con h.
En este caso particular, es necesario redefinir los siguientes conceptos:
• El par (h, m) con h ∈ H y m ∈ M, es bloqueante del emparejamiento E si se
verifican alguna de las dos condiciones siguientes:
o E(h) = m y h es inaceptable para m ó m es inaceptable para h.
o E(h) ≠ m y m prefiere a h antes que a E(m) y h prefiere a m antes que a
E(h).
• Dados los conjuntos de proponentes y propuestos H y M respectivamente, y una
relación de preferencias con listas incompletas, no siempre existe un
emparejamiento perfecto.
Con estas condiciones en las listas de preferencias y con las nuevas definiciones
siempre es posible encontrar un emparejamiento estable. Basta con realizar las
siguientes modificaciones resaltadas en cursiva en la segunda y última etapa del
algoritmo original de Gale-Shapley:
• Segunda etapa: Cada mujer que haya recibido al menos una propuesta, rechaza a
los hombres que son inaceptables para ella o en el caso de tener más de un
candidato aceptable, rechaza a todos salvo al hombre más preferido de todos los
que la pretendieron. Al elegido lo mantiene, pero puede cambiar de opinión ya
Estabilidad en Emparejamientos
17
que en las siguientes etapas puede obtener una propuesta mejor. Los hombres
que no han sido rechazados en esta etapa quedan comprometidos con la mujer
que los aceptó.
• Última etapa: el algoritmo para cuando ningún hombre es rechazado. En esta
etapa cada hombre está comprometido con alguna mujer o ha sido rechazado por
todas las mujeres aceptables de su lista de preferencias y queda soltero. El
algoritmo debe parar en alguna etapa porque solo hay un número finito de
hombres y mujeres y ningún hombre hace propuestas a ninguna mujer más de
una vez.
En este caso el emparejamiento obtenido podrá dejar tanto a hombres como a mujeres
solteros, dependiendo de la lista de preferencias que establezcan. Si un individuo queda
sin pareja en un matrimonio estable dentro de una instancia con listas incompletas,
estará solo en cualquier otro matrimonio estable que posea esa instancia.
A continuación, se explica de forma practica el funcionamiento del algoritmo. Sean los
conjuntos H={h1,h2,h3, h4} y M={m1,m2,m3,m4} con las siguientes preferencias:
Primera etapa. Los hombres proponen compromiso a sus mujeres favoritas, de manera
que h1 y h4 proponen compromiso a m2, h2 a m1 y h3 a m4.
h1 m2 m3
h2 m1 m2
h3 m4 m1
h4 m2 m4
m1 h1 h2
m2 h1 h4 h3
m3 h2 h4
m4 h1 h3
Estabilidad en Emparejamientos
18
h1 m2
h2 m1
h3 m4
h4 m2
Segunda etapa. Ahora, las mujeres seleccionan su mejor propuesta, por lo tanto, m1
selecciona a h2, m2 a h1 y m4 a h3. La asignación provisional queda de la siguiente
manera.
h1 m2
h2 m1
h3 m4
h4 m2
Tercera etapa. El hombre h4 es el rechazado en la anterior etapa, por tanto, van a
proponer un compromiso a su segunda opción, que es la mujer m2.
h1 m2 m2
h2 m1 m1
h3 m4 m4
h4 m2 m4
Segunda etapa'. En este caso m4 rechaza a h4 porque no aparece en su lista de
preferencias, se trata de una propuesta inaceptable para m4. Por lo tanto, la asignación
provisional queda de la siguiente manera.
Estabilidad en Emparejamientos
19
h1 m2 m2
h2 m1 m1
h3 m4 m4
h4 m2 m4
Tercera etapa'. El hombre h4 es el rechazado en la anterior etapa y no tiene más
opciones en su lista de preferencias, por lo tanto queda soltero.
h1 m2 m2 m2
h2 m1 m1 m1
h3 m4 m4 m4
h4 m2 m4
Última etapa. Finaliza el algoritmo puesto que todos los hombres quedan
comprometidos con alguna mujer o han queda solteros. Por lo tanto, obtenemos la
siguiente asignación estable para este ejemplo.
h1 m2
h2 m1
h3 m4
h4
2.4.2 Empates en las Preferencias
En esta variante, se estudia el problema cuando las listas de preferencia son completas,
pero no son estrictas, es decir, algún individuo puede tener indiferencias entre varias
alternativas, de modo que su lista de preferencias puede incluir empates.
Estabilidad en Emparejamientos
20
En este caso, se pueden definir nuevos tipos de emparejamientos estables:
• Un emparejamiento E es débilmente estable si no existe h ∈ H y m ∈ M tal que:
o E(h) ≠ m
o h prefiere a m antes que a E(h) y m prefiere a h antes que a E(m)
Es decir, es débilmente estable si no existe un par (h, m) no unido, en el que
ambos se prefieren estrictamente antes que a sus parejas actuales.
• Un emparejamiento E es fuertemente estable si no existe h ∈ H y m ∈ M tal que:
o E(h) ≠ m
o Y se da una de las siguientes condiciones:
▪ h tiene indiferencia o prefiere a m antes que a E(h), y m prefiere a
h antes que a E(m)
▪ h prefiere a m antes que a E(h), y m tiene indiferencia o prefiere a
h antes que a E(m)
Es decir, es fuertemente estable si no existe un par (h, m) no unido, en el que
uno de los dos prefiere estrictamente al otro antes que a su pareja actual, y el
otro es al menos indiferente.
• Un emparejamiento E es súper-estable si no existe h ∈ H y m ∈ M tal que:
o E(h) ≠ m
o h tiene indiferencia o prefiere a m antes que a E(h), y m tiene
indiferencia o prefiere a h antes que a E(m)
Es decir, es súper-estable si no existe un par (h, m) no unido, que prefiere estarlo
o a ambos les resulta indiferente.
Se puede ver claramente las siguientes implicaciones:
• Si E es súper-estable entonces E es fuertemente estable.
• Si E es fuertemente estable entonces E es débilmente estable.
En consecuencia, si nos encontramos ante un emparejamiento débilmente estable se
puede aplicar el algoritmo de Gale-Shapley para obtener vínculos estables, pero no hay
Estabilidad en Emparejamientos
21
garantía de su existencia con emparejamientos fuertemente estable y por lo tanto
tampoco con emparejamientos súper-estables.
2.4.3 Compañeros de Habitación
En el problema de los matrimonios estables se pretende establecer una relación
biyectiva entre dos conjuntos, mientras que en el problema de los compañeros de
habitación, existe un único conjunto C={c1, ..., cn} que se debe dividir en parejas
disjuntas.
El problema de los compañeros de habitación surge para resolver la asignación de pares
de estudiantes en cuartos de una universidad, donde cada estudiante tiene una lista de
preferencias estrictamente ordenada de los compañeros restantes. Se trata de una
generalización del problema de los matrimonios estables, en el cual una instancia
consiste en un conjunto de n personas de cardinalidad par, cada una incluyendo en su
lista de preferencias a las n-1 personas restantes en orden estricto. Un emparejamiento
entre los miembros de este conjunto es una división del mismo en pares disjuntos.
Estos problemas son catalogados también bajo el concepto de “uno a uno”, dado que
toda persona siempre termina en pareja con una única persona.
Al igual que para el problema de los matrimonios estables, se dice que un
emparejamiento es estable si no existe ninguna pareja bloqueante. Sean ci y cj dos
personas del conjunto C, un emparejamiento E se dice inestable si:
• ci y cj no son pareja en E.
• ci prefiere a cj antes que a E(ci) y cj prefiere a ci antes que a E(cj). Es decir, ci y
cj preferirían ser pareja, en lugar de sus respectivas parejas obtenidas en E.
A diferencia del problema de los matrimonios estables, este problema puede no tener
solución. Se dice que un problema es resoluble si admite un emparejamiento estable y,
en caso contrario, se dice que es irresoluble.
Estabilidad en Emparejamientos
22
Robert Irving mostró que es posible determinar si este tipo de problema tiene solución y
propuso en 1985 un algoritmo eficiente estructurado en dos etapas para encontrar un
emparejamiento estable en el caso de que sea resoluble o responder negativamente
cuando es irresoluble:
• Primera etapa. Consiste en una secuencia de proposiciones de acuerdo a las
siguientes reglas:
o Si x recibe una propuesta de y, entonces:
▪ Lo rechaza si ya tiene una propuesta mejor, es decir, si tiene una
propuesta vigente de alguien mejor ubicado en su lista.
▪ Lo conserva si es mejor que su propuesta vigente, rechazando la
anterior, o si no tenía propuesta.
o Un individuo propone siguiendo el orden de su lista de preferencias,
deteniéndose cuando su propuesta es aceptada, y continuando si es
rechazado en el futuro.
Esta etapa finaliza en cualquiera de las siguientes situaciones:
o Una o más personas fueron rechazadas por todas las demás. En este caso
el problema es irresoluble.
o Todas las personas tienen una proposición. En este caso se generan listas
reducidas de preferencias teniendo en cuenta que las personas con menor
prioridad que la propuesta vigente no pueden ser pareja en un
emparejamiento estable.
• Segunda etapa. Trata los casos en los que existen listas reducidas con más de un
elemento y se continúa su reducción mediante las siguientes reglas:
o Buscar la primera persona X con más de un elemento en su lista
reducida.
o Buscar la segunda persona Y de la lista reducida de X.
o Buscar la última persona de la lista reducida de Y.
o Repetir los dos pasos anteriores hasta que la última persona sea X
nuevamente. En ese momento descartar de las listas reducidas todas las
propuestas obtenidas.
Estabilidad en Emparejamientos
23
Esta etapa finaliza en cualquiera de las siguientes situaciones:
o Una o más personas se quedan sin proposiciones. En este caso el
problema es irresoluble.
o Todas las personas tienen una única proposición que es la solución al
problema.
A continuación, se plantea un ejemplo en el que tenemos un único conjunto {A, B, C,
D, E, F} y una única matriz de preferencias donde cada persona incluye al resto de
posibles compañeros ordenados de tal manera que se pone en primer lugar a la persona
que más le gustaría tener por compañero:
A B D F C E
B D E F A C
C D E F A B
D F C A E B
E F C D B A
F A B D C E
Primera etapa: Se van realizando proposiciones y aceptando o rechazando conforme a
las reglas establecidas en el algoritmo.
X Propuesta realizada
X Propuesta aceptada
X Propuesta rechazada
Estabilidad en Emparejamientos
24
A B D F C E
B D E F A C
C D E F A B
D F C A E B
E F C D B A
F A B D C E
Primera etapa: Se generan las listas reducidas descartando las propuestas que son peores
que las actuales.
A B D F C E
B D E F A C
C D E F A B
D F C A E B
E F C D B A
F A B D C E
Segunda etapa: Se tratan las listas con más de un elemento.
A D E A
F C B
Segunda etapa: Se descartan las proposiciones.
Estabilidad en Emparejamientos
25
A B D F C E
B D E F A C
C D E F A B
D F C A E B
E F C D B A
F A B D C E
Segunda etapa: Se continúa tratando las listas con más de un elemento.
B B
F
Segunda etapa: Se descartan las proposiciones y se obtiene una solución estable.
A B D F C E
B D E F A C
C D E F A B
D F C A E B
E F C D B A
F A B D C E
Para terminar, se plantea un ejemplo irresoluble en el que tenemos el conjunto {A, B, C,
D} y la siguiente matriz de preferencias.
Estabilidad en Emparejamientos
26
A B C D
B C A D
C A B D
D A B C
En la primera etapa se confirma que el problema es irresoluble al quedar la persona D
sin elementos en su lista de preferencias.
A B C D
B C A D
C A B D
D A B C
En esta instancia ninguno de los pares (A, D), (B, D) y (C, D) podrá pertenecer a un
emparejamiento estable pues siempre existiría un par bloqueante. Esto es debido a que
D está en la última posición en las preferencias de sus compañeros y el resto de
personas se eligen entre ellos de manera combinada.
Estabilidad en Emparejamientos
27
3 DISEÑO DE LA APLICACIÓN
3.1 Introducción
Para la representación y documentación del análisis y modelado del sistema se ha
utilizado el estándar de notación UML (Unified Modeling Language).
UML es el lenguaje de modelado de sistemas software más conocido y utilizado en la
actualidad. Cuenta con el respaldo del OMG (Object Management Group) puesto que es
un complemento perfecto para la orientación a objetos.
Se trata de un lenguaje basado en una serie de notaciones gráficas para visualizar,
especificar, construir y documentar todos los elementos que forman un sistema
software. Ofrece un estándar para describir y especificar un modelo del sistema
mediante varios tipos de diagramas, los cuales muestran diferentes aspectos de las
entidades representadas.
Para el desarrollo de la aplicación se ha utilizado el lenguaje de programación Java
debido a las ventajas que supone ser un lenguaje multiplataforma orientado a objetos, de
manera que permite la ejecución del software construido en cualquier plataforma que
soporte la máquina virtual de Java y posibilita la reutilización y extensión de código.
Por otro lado, dispone de un amplio conjunto de APIs (Interfaces de Programación de
Aplicaciones) que facilitan el uso de varias estructuras de datos, el desarrollo de la
interfaz gráfica a través de Swing, la internacionalización de la aplicación, etc.
3.2 Diseño de Alto Nivel
En este apartado se pretende explicar el diseño que se ha empleado en el desarrollo de la
aplicación mediante una visión general del proceso realizado, sin entrar en un análisis
muy exhaustivo.
Estabilidad en Emparejamientos
28
Se abordan únicamente aquellos estándares que se consideran suficientes para una
correcta y sencilla comprensión de la aplicación, sin estar sujeto a las rigurosas normas
de nomenclatura que precisan los documentos de Ingeniería del Software.
• Límites del sistema.
• Diagrama de casos de uso.
• Descripción de los actores.
• Casos de uso en formato extendido.
3.2.1 Límites del Sistema
La herramienta permite encontrar un emparejamiento estable entre dos grupos de
agentes que establecen preferencias entre sí.
Inicialmente la aplicación crea dos matrices de preferencias de la misma cardinalidad en
el panel central y permite que los proponentes de cada grupo añadan o eliminen
propuestos a su fila siguiendo un orden estricto de preferencias. Alternativamente, se
permite borrar todas las preferencias de las matrices o terminar de completarlas
siguiendo una elección aleatoria.
Cuando se definen correctamente todas las preferencias, la aplicación permite obtener
emparejamientos estables y perfectos aplicando el algoritmo de Listas Completas; en el
caso de que los proponentes consideren inaceptables a determinados propuestos,
circunstancia que se representa mediante huecos sin rellenar en sus listas de
preferencias, la aplicación permite obtener los emparejamientos estables que sean
posibles aplicando el algoritmo de Listas Incompletas.
El acceso tanto a las opciones de selección de algoritmos y referencias, como a la
edición de preferencias, se puede realizar indistintamente desde un panel lateral de
trabajo o desde el menú superior.
Estabilidad en Emparejamientos
29
La obtención de parejas estables se puede visualizar de manera totalmente interactiva en
una nueva matriz del panel central, avanzando o retrocediendo en cada paso del
algoritmo, mostrando todos los pasos a la vez o presentando únicamente la solución
final. Todas estas opciones de ejecución están presentes en el panel de trabajo lateral.
Adicionalmente, la herramienta presenta una barra de estado inferior con información
de interés para facilitar la comprensión de los diferentes interfaces; y se trata de una
aplicación multi idioma, que se encuentra disponible en español e inglés.
3.2.2 Diagrama de Casos de Uso
Un caso de uso es un mecanismo para capturar y describir de forma sencilla la
secuencia de interacciones llevadas a cabo entre un actor y el sistema para realizar una
tarea específica.
Mediante esta técnica se puede expresar cualquier unidad funcional coherente basada en
un conjunto de acciones y reacciones, de manera que se consigue limitar el alcance del
sistema y su relación con el entorno empleando un lenguaje natural accesible para
cualquier usuario. El sistema queda reducido a una “caja negra” en el que únicamente
interesa las funciones que son visibles desde el exterior y no cómo se realizan.
El listado de casos de uso del proyecto es el siguiente:
• Cambiar Idioma
• Consultar Manual
• Consultar Información
• Crear Emparejamiento
• Cerrar Emparejamiento
• Crear Preferencia
• Borrar Preferencia
Estabilidad en Emparejamientos
30
• Limpiar Preferencias
• Completar Preferencias
• Seleccionar Algoritmo
• Seleccionar Referencia
• Reiniciar Algoritmo
• Ejecutar Anterior
• Ejecutar Siguiente
• Finalizar Algoritmo
• Mostrar Solución
Un diagrama de casos de uso es la representación visual de todos los casos de uso del
sistema y su relación con los actores. El sistema en sí está representado como un
rectángulo que contiene en su interior casos de uso comunicados mediante líneas con
los actores con los que interactúan.
Por lo tanto, los diagramas de casos de uso están formados por tres elementos
principales:
• Actores: Simboliza los usuarios del sistema (humanos,
dispositivos externos, temporizadores que envían
eventos, ..) que interactúan con el sistema mediante
casos de uso. Un actor se caracteriza por la forma de
relacionarse con el sistema, por lo que un mismo
usuario puede ejercer de varios actores, y un actor
puede representar a varios usuarios. Los actores se
representan mediante figuras de “hombre de palo” con
un nombre en la parte inferior.
Estabilidad en Emparejamientos
31
• Casos de uso: Simboliza el comportamiento del sistema
en relación con los usuarios. De esta forma, un caso de
uso define la secuencia de interacciones entre uno o
más usuarios y el sistema. Los casos de uso se
representan mediante una elipse, con un nombre en su
interior.
• Relaciones: Simboliza el flujo de información
intercambiada entre actores y casos de uso, o entre
diferentes casos de uso. Se emplean para que un caso
de uso obtenga la información necesaria para llevar a
cabo alguna acción o para que el proceso proporcione
algún resultado, tanto unidireccional como
bidireccionalmente. Las relaciones se representan
mediante flechas que unen los casos de uso y los
actores entre los que existe un flujo de información.
El Diagrama de Casos de Uso del proyecto es el siguiente:
Estabilidad en Emparejamientos
32
Estabilidad en Emparejamientos
33
3.2.3 Actores
Únicamente existe un actor que interactúa con el sistema. Este actor principal es el
usuario que tiene acceso a todas las operaciones de la aplicación para definir las
preferencias de los distintos grupos de proponentes y visualizar la ejecución de los
algoritmos hasta encontrar una solución al problema de estabilidad en emparejamientos.
3.2.4 Casos de Uso en Formato Extendido
A continuación, se describen los casos de uso con un nivel de detalle extendido superior
al formato básico del alto nivel, de manera que se especifican las interacciones
habituales entre los actores de la aplicación.
El formato empleado consta de los siguientes campos:
• Caso de Uso: Nombre del caso de uso.
• Objetivo: Qué es lo que debe hacer el sistema.
• Actor Principal: Quién utiliza el sistema para alcanzar un objetivo. En este caso
el Usuario.
• Precondiciones: Qué debe cumplirse antes de comenzar un escenario.
• Activa: Acción que inicia el caso de uso.
• Escenario principal de éxito: Describe el camino de éxito típico que satisface los
intereses del personal involucrado.
• Garantías de éxito: Qué debe cumplirse cuando el caso de uso se acaba con
éxito.
• Garantías de fracaso: Qué debe cumplirse cuando el caso de uso se abandona.
• Extensiones: Indican todos los otros escenarios o bifurcaciones tanto de éxito
como de fracaso.
Estabilidad en Emparejamientos
34
3.2.4.1 Cambiar Idioma
Caso de Uso Cambiar Idioma
Objetivo Cambiar todo el texto de la aplicación a uno de los lenguajes
soportados: español o inglés
Actor Principal Usuario
Precondiciones Ninguna
Activa El usuario accede al menú Idioma y selecciona el idioma deseado
(español o inglés)
Escenario principal
de éxito
1. El usuario solicita un cambio de idioma
2. El sistema modifica todo el texto del aplicativo al idioma
seleccionado y lo emplea a partir de ese momento para todos
los mensajes que aparezcan
Garantías de éxito Cambia todo el texto de la aplicación al lenguaje seleccionado
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.2 Consultar Manual
Caso de Uso Consultar Manual
Objetivo Mostrar el manual de usuario para que pueda ser consultado
Actor Principal Usuario
Estabilidad en Emparejamientos
35
Precondiciones Ninguna
Activa El usuario accede al menú Ayuda y selecciona la opción Ayuda
Escenario principal
de éxito
1. El usuario solicita la obtención de Ayuda
2. El sistema abre el manual de usuario en formato pdf
Garantías de éxito Se abre un documento pdf con el contenido del manual de usuario
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.3 Consultar Información
Caso de Uso Consultar Información
Objetivo Mostar información relacionada con la aplicación
Actor Principal Usuario
Precondiciones Ninguna
Activa El usuario accede al menú Ayuda y selecciona la opción "Acerca
de"
Escenario principal
de éxito
1. El usuario solicita información de la aplicación
2. El sistema abre una ventana emergente en la que se muestra
información de la aplicación
Garantías de éxito Se abre una ventana emergente con información de la aplicación
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
Estabilidad en Emparejamientos
36
encontraba antes de iniciar el caso de uso
Extensiones 3. El usuario pulsa el aspa para cerrar la ventana
4. El sistema cierra la ventana emergente de información
3.2.4.4 Crear Emparejamiento
Caso de Uso Crear Emparejamiento
Objetivo Iniciar o reiniciar un emparejamiento mediante la creación de dos
matrices de preferencias
Actor Principal Usuario
Precondiciones Ninguna
Activa El usuario accede al menú Archivo y selecciona la opción Nuevo
o pulsa el botón Nuevo de la barra de herramientas
Escenario principal
de éxito
1. El usuario solicita la creación de un nuevo emparejamiento
2. El sistema abre la ventana emergente "Nuevo
Emparejamiento"
3. El sistema solicita un número de parejas
4. El usuario introduce un número entre 1 y 99
5. El sistema inicializa un nuevo emparejamiento con dos
matrices de preferencias inicialmente vacías y sin presencia
de matrices de emparejamientos
Garantías de éxito
Se crea en el panel central dos matrices de la misma dimensión
inicialmente vacías para que el usuario pueda comenzar a
introducir preferencias
Estabilidad en Emparejamientos
37
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones
4a. El usuario introduce un valor no numérico
1. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
2. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3. Se vuelve al paso 4 del escenario de éxito
4b. El usuario introduce un valor fuera del rango 1-99
1. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
2. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3. Se vuelve al paso 4 del escenario de éxito
4c. El usuario pulsa el aspa para cerrar la ventana
1. El sistema cierra la ventana emergente "Nuevo
Emparejamiento"
3.2.4.5 Cerrar Emparejamiento
Caso de Uso Cerrar Emparejamiento
Objetivo Cerrar el emparejamiento actual eliminando las matrices de
preferencias o emparejamientos que pudiesen existir
Actor Principal Usuario
Precondiciones Ninguna
Estabilidad en Emparejamientos
38
Activa El usuario accede al menú Archivo y selecciona la opción Cerrar
o pulsa el botón Cerrar de la barra de herramientas
Escenario principal
de éxito
1. El usuario solicita el cierre del emparejamiento actual
2. El sistema elimina las matrices de preferencias y
emparejamientos que pudiesen existir
Garantías de éxito El panel central se muestra vacío sin matrices de preferencias o
emparejamientos
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.6 Crear Preferencia
Caso de Uso Crear Preferencia
Objetivo Definir una propuesta de un proponente
Actor Principal Usuario
Precondiciones • Existen las matrices de preferencias
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón izquierdo del ratón en cualquiera de las
celdas de las matrices de preferencia
Escenario principal
de éxito
1. El usuario solicita la creación de una nueva preferencia
2. El sistema abre la ventana emergente "Valor Celda"
3. El sistema solicita un subíndice de pareja entre una serie de
posibilidades
Estabilidad en Emparejamientos
39
4. El usuario introduce un número entre las posibilidades
propuestas
5. El sistema marca la celda editada con la propuesta elegida
por el usuario
Garantías de éxito Se inserta la propuesta definida en la celda editada de la matriz de
preferencias
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones
4a. El usuario introduce un valor no numérico
1. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
2. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3. Se vuelve al paso 4 del escenario de éxito
4b. El usuario introduce un valor diferente a las posibilidades
propuestas
1. El sistema muestra un mensaje de advertencia indicando
las posibilidades aceptables
2. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3. Se vuelve al paso 4 del escenario de éxito
4c. El usuario pulsa el aspa o el botón Cancelar para cerrar la
ventana
1. El sistema cierra la ventana emergente "Valor Celda"
Estabilidad en Emparejamientos
40
3.2.4.7 Borrar Preferencia
Caso de Uso Borrar Preferencia
Objetivo Eliminar la propuesta de un proponente
Actor Principal Usuario
Precondiciones • Existen las matrices de preferencias
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón derecho del ratón en cualquiera de las
celdas de las matrices de preferencia
Escenario principal
de éxito
1. El usuario solicita la eliminación de una determinada
preferencia
2. El sistema deja la celda editada sin propuesta definida
Garantías de éxito Se elimina de la matriz de preferencias el valor que hubiese
presente en la celda editada
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.8 Limpiar Preferencias
Caso de Uso Limpiar Preferencias
Objetivo Eliminar todas las propuestas de todos los proponentes
Actor Principal • Existen las matrices de preferencias
Estabilidad en Emparejamientos
41
• No hay ningún algoritmo en ejecución
Precondiciones Ninguna
Limpiar
Preferencias
El usuario accede al menú Preferencias y selecciona la opción
Borrar o pulsa el botón Borrar de la sección Preferencias del
Interfaz de ejecución
Eliminar todas las
propuestas de todos
los proponentes
1. El usuario solicita la eliminación de todas las preferencias
2. El sistema deja todas las celdas sin propuestas definidas
Garantías de éxito Todas las celdas de las matrices de preferencias quedan sin valor
definido
Garantías de fracaso Se elimina de las matrices de preferencias los valores de todas las
celdas
Extensiones Ninguna
3.2.4.9 Completar Preferencias
Caso de Uso Completar Preferencias
Objetivo Definir aleatoriamente las propuestas incompletas de todos los
proponentes
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• No hay ningún algoritmo en ejecución
Activa El usuario accede al menú Preferencias y selecciona la opción
Estabilidad en Emparejamientos
42
Completar o pulsa el botón Completar de la sección Preferencias
del Interfaz de ejecución
Escenario principal
de éxito
1. El usuario solicita la creación aleatoria de todas las
preferencias sin rellenar
2. El sistema marca las celdas sin rellenar con valores aleatorios
Garantías de éxito
Se insertan valores aleatorios elegidos entre las opciones
disponibles, en las celdas incompletas de las matrices de
preferencias
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.10 Seleccionar Algoritmo
Caso de Uso Seleccionar Algoritmo
Objetivo Definir el algoritmo de ejecución
Actor Principal Usuario
Precondiciones • Existen las matrices de preferencias
• No hay ningún algoritmo en ejecución
Activa El usuario selecciona un algoritmo desde el menú Algoritmos o
desde la sección Algoritmos del Interfaz de ejecución
Escenario principal
de éxito
1. El usuario selecciona un algoritmo de ejecución
2. El sistema establece el algoritmo seleccionado como motor
de ejecución
Estabilidad en Emparejamientos
43
Garantías de éxito Queda definido el algoritmo que se va a emplear para buscar
emparejamientos estables
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.11 Seleccionar Referencia
Caso de Uso Seleccionar Referencia
Objetivo Definir un punto de vista que sirva como referencia para buscar
emparejamientos estables
Actor Principal Usuario
Precondiciones • Existen las matrices de preferencias
• No hay ningún algoritmo en ejecución
Activa El usuario selecciona una referencia desde el menú Referencias o
desde la sección Referencias del Interfaz de ejecución
Escenario principal
de éxito
1. El usuario selecciona un punto de vista
2. El sistema establece el punto de vista seleccionado como
referencia para buscar emparejamientos
Garantías de éxito
Se muestra la matriz de emparejamientos con las referencias de A
al seleccionar “Punto de vista A’s”, la matriz de emparejamientos
con las referencias de B al seleccionar “Punto de vista B’s”, o las
dos matrices al seleccionar “Ambos”
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
Estabilidad en Emparejamientos
44
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
3.2.4.12 Reiniciar Algoritmo
Caso de Uso Reiniciar Algoritmo
Objetivo Devolver el algoritmo y su representación en las matrices de
preferencias existentes al estado inicial de ejecución
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• Se ha seleccionado un punto de vista concreto
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón Inicio de la sección Emparejamientos
del Interfaz de ejecución
Escenario principal
de éxito
1. El usuario solicita reiniciar el algoritmo
2. El sistema devuelve el algoritmo al estado inicial de
ejecución
Garantías de éxito Se eliminan todas las columnas que pudiesen existir en las
matrices de emparejamientos
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
Estabilidad en Emparejamientos
45
3.2.4.13 Ejecutar Anterior
Caso de Uso Ejecutar Anterior
Objetivo
Devolver el algoritmo y su representación en las matrices de
preferencias existentes al paso de ejecución inmediatamente
anterior al actual
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• Se ha seleccionado un punto de vista concreto
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón Atrás de la sección Emparejamientos del
Interfaz de ejecución
Escenario principal
de éxito
1. El usuario solicita retroceder un paso del algoritmo
2. El sistema devuelve el algoritmo al paso inmediatamente
anterior al actual
Garantías de éxito Se elimina la última columna de posibilidades o se deshace el
último análisis de estabilidad en las matrices de emparejamientos
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones Ninguna
Estabilidad en Emparejamientos
46
3.2.4.14 Ejecutar Siguiente
Caso de Uso Ejecutar Siguiente
Objetivo
Avanzar el algoritmo y su representación en las matrices de
preferencias existentes al paso de ejecución inmediatamente
posterior al actual
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• Se ha seleccionado un punto de vista concreto
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón Avanzar de la sección Emparejamientos
del Interfaz de ejecución
Escenario principal
de éxito
1. El usuario solicita avanzar un paso del algoritmo
2. El sistema comprueba que las matrices de preferencias están
rellenas conforme a las necesidades del algoritmo
seleccionado
3. El sistema muestra el paso del algoritmo inmediatamente
posterior al actual
Garantías de éxito Se añade una nueva columna de posibilidades o se muestra un
nuevo análisis de estabilidad en las matrices de emparejamientos
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones 2a. El sistema detecta que alguna de las matrices de preferencias
no está rellena conforme a las necesidades del algoritmo
Estabilidad en Emparejamientos
47
seleccionado
3. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
4. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3.2.4.15 Finalizar Algoritmo
Caso de Uso Finalizar Algoritmo
Objetivo Avanzar el algoritmo y su representación en las matrices de
preferencias existentes al último paso de ejecución
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• Se ha seleccionado un punto de vista concreto
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón Final de la sección Emparejamientos del
Interfaz de ejecución
Escenario principal
de éxito
1. El usuario solicita finalizar el algoritmo
2. El sistema comprueba que las matrices de preferencias están
rellenas conforme a las necesidades del algoritmo
seleccionado
3. El sistema muestra todos los pasos del algoritmo hasta su
finalización
Garantías de éxito Se muestran todas las columnas de posibilidades y todos los
Estabilidad en Emparejamientos
48
análisis de estabilidad en las matrices de emparejamientos
existentes
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones
2a. El sistema detecta que alguna de las matrices de preferencias
no está rellena conforme a las necesidades del algoritmo
seleccionado
3. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
4. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
3.2.4.16 Mostrar Solución
Caso de Uso Mostrar Solución
Objetivo Mostrar únicamente la lista de emparejamientos obtenida por el
algoritmo para cada una de las matrices existentes
Actor Principal Usuario
Precondiciones
• Existen las matrices de preferencias
• Se ha seleccionado un algoritmo concreto
• Se ha seleccionado un punto de vista concreto
• No hay ningún algoritmo en ejecución
Activa El usuario pulsa el botón Lista Final de la sección
Emparejamientos del Interfaz de ejecución
Escenario principal 1. El usuario solicita la lista de emparejamientos del algoritmo
Estabilidad en Emparejamientos
49
de éxito 2. El sistema comprueba que las matrices de preferencias están
rellenas conforme a las necesidades del algoritmo
seleccionado
3. El sistema muestra el último paso del algoritmo con la lista
de emparejamientos estables
Garantías de éxito
Se muestra únicamente una columna con los emparejamientos
estables obtenidos por el algoritmo en las matrices de
emparejamientos existentes
Garantías de fracaso El sistema se mantiene en el mismo estado coherente que se
encontraba antes de iniciar el caso de uso
Extensiones
2a. El sistema detecta que alguna de las matrices de preferencias
no está rellena conforme a las necesidades del algoritmo
seleccionado
3. El sistema muestra un mensaje de advertencia indicando
esta circunstancia
4. El usuario pulsa "enter", el aspa o el botón Ok de la
ventana de advertencia
Estabilidad en Emparejamientos
50
3.3 Diseño de Bajo Nivel
Para realizar el diseño de bajo nivel se ha empleado diagramas de clases con notación
UML, que permiten mostrar una visión global de los diferentes componentes del
sistema y su relación entre ellos.
3.3.1 Diagrama de Clases
Un diagrama de clases es un tipo de diagrama estático empleado durante la fase de
análisis y diseño de los sistemas informáticos para representar gráficamente la
estructura y especificaciones de las entidades software de una aplicación, mediante las
clases que componen el sistema.
En la programación orientada a objetos, una clase es la construcción utilizada como
modelo o plantilla a partir de la cual se pueden crear objetos. La clase almacena un
estado en sus atributos y encapsula un comportamiento a través de secciones de código
reutilizables llamados métodos.
Una clase se representa gráficamente mediante una caja formada por tres partes:
nombre, atributos y métodos. Sin embargo, para dar una visión general y facilitar la
comprensión de las relaciones existentes entre las clases, el siguiente diagrama muestra
las principales clases en formato simplificado mediante una caja en la que únicamente
aparece el nombre de la clase sin atributos ni métodos.
Estabilidad en Emparejamientos
51
A continuación, se muestran las principales clases del sistema por separado para poder
verlas con más detalle mediante su representación gráfica completa (atributos y
métodos) y se describe brevemente la funcionalidad presente en sus métodos más
relevantes.
Estabilidad en Emparejamientos
52
3.3.1.1 Clase EeE
La clase EeE es la clase principal, contiene el método main que se encarga de definir el
entorno de trabajo de la aplicación y crear la ventana principal en la que se van
incorporando los demás componentes del sistema sobre los que interactúa el usuario de
la aplicación.
Para la creación de esta clase se emplea una extensión de la clase JFrame de Java.
3.3.1.2 Clase Acerca
La clase Acerca es la encargada de suministrar información sobre la aplicación. Es, por
tanto, la clase responsable de la implementación del caso de uso “Consultar
Información”.
Para la creación de esta clase se emplea una extensión de la clase JFrame de Java.
Estabilidad en Emparejamientos
53
3.3.1.3 Clase Nuevo
La clase Nuevo es la encargada de inicializar las matrices de preferencias mediante la
elección de una dimensión o cardinalidad. Es, por tanto, la clase responsable de la
implementación del caso de uso “Crear Emparejamiento”.
Para la creación de esta clase se emplea una extensión de la clase JFrame de Java.
Estabilidad en Emparejamientos
54
3.3.1.4 Clase MenuBarEstabilidad
La clase MenuBarEstabilidad es la encargada de crear la barra de menús y dar acceso a
gran parte de las funcionalidades definidas en los casos de uso: “Crear
Emparejamiento”, “Cerrar Emparejamiento”, “Seleccionar Algoritmo”, “Completar
Preferencias”, “Limpiar Preferencias”, “Seleccionar Referencia”, “Cambiar Idioma”,
“Consultar Manual” y “Consultar Información”. Todas estas funcionalidades se agrupan
en los menús Archivo, Algoritmos, Preferencias, Referencias, Idioma, y Ayuda. La
clase dispone de métodos para habilitar o deshabilitar estas funcionalidades en base al
estado en que se encuentre el sistema.
Para la creación de esta clase se emplea una extensión de la clase JMenuBar de Java.
Estabilidad en Emparejamientos
55
Estabilidad en Emparejamientos
56
3.3.1.5 Clase ToolBarEstabilidad
La clase ToolBarEstabilidad es la encargada de crear la barra de herramientas y dar
acceso de manera más rápida y cómoda a las funcionalidades definidas en los casos de
uso: “Crear Emparejamiento”, “Cerrar Emparejamiento” y “Consultar Manual”. Estas
funcionalidades se mantienen activas en cualquier momento del flujo de ejecución de la
aplicación.
Para la creación de esta clase se emplea una extensión de la clase JToolBarde Java.
3.3.1.6 Clase SideBarEstabilidad
La clase SideBarEstabilidad es la encargada de crear el interfaz lateral de ejecución y
dar acceso a gran parte de las funcionalidades definidas en los casos de uso:
“Seleccionar Algoritmo”, “Completar Preferencias”, “Limpiar Preferencias”,
“Seleccionar Referencia”, “Reiniciar Algoritmo”, “Ejecutar Anterior”, “Ejecutar
Siguiente”, “Finalizar Algoritmo” y “Mostrar Solución”. Todas estas funcionalidades se
agrupan en las secciones Algoritmos, Preferencias, Referencias y Ejecución. La clase
dispone de métodos para habilitar o deshabilitar estas funcionalidades en base al estado
en que se encuentre el sistema.
Para la creación de esta clase se emplea una extensión de la clase Box de Java.
Estabilidad en Emparejamientos
57
Estabilidad en Emparejamientos
58
3.3.1.7 Clase CentralEstabilidad
La clase CentralEstabilidad es la encargada de presentar las matrices de preferencias y
emparejamientos mediante colaboración con los objetos de las clases Generador y
Emparejador, respectivamente. Este diálogo permite llevar a cabo las funcionalidades
definidas en los casos de uso “Crear Emparejamiento”, “Cerrar Emparejamiento”,
“Limpiar Preferencias”, “Completar Preferencias”, “Reiniciar Algoritmo”, “Ejecutar
Anterior”, “Ejecutar Siguiente”, “Finalizar Algoritmo” y “Mostrar Solución”. Estas
funcionalidades son accesibles desde los diferentes menús de la clase
MenuBarEstabilidad y las diferentes secciones de la clase SideBarEstabilidad.
Para la creación de esta clase se emplea una extensión de la clase JPanel de Java.
Estabilidad en Emparejamientos
59
Estabilidad en Emparejamientos
60
3.3.1.8 Clase Generador
La clase Generador es la encargada de gestionar las matrices de preferencias. Almacena
información sobre las propuestas seleccionadas y las propuestas disponibles para cada
fila de la matriz, y en función del algoritmo seleccionado permite completar de forma
aleatoria las preferencias que faltan por rellenar.
3.3.1.9 Clase Emparejador
La clase Emparejador es la encargada de gestionar las matrices de emparejamientos e
implementar la lógica de los algoritmos. Las funciones definidas en esta clase son, por
tanto, la generación de propuestas de emparejamiento en la que se toma como referencia
el punto de vista seleccionado, el análisis de estabilidad de estas propuestas, y en
función del resultado obtenido, el descarte en base a las preferencias y la generación de
nuevas propuestas, o la finalización del algoritmo en la que se ofrece una solución
estable para el problema de emparejamientos planteado.
Estabilidad en Emparejamientos
61
3.3.1.10 Clase Celda
La clase Celda es la encargada de insertar la propuesta seleccionada por el usuario en la
celda de la matriz de preferencias editada. Es, por tanto, la clase responsable de la
implementación del caso de uso “Crear Preferencia”.
Para la creación de esta clase se emplea una extensión de la clase JFrame de Java.
Estabilidad en Emparejamientos
62
3.3.1.11 Clase Matriz
La clase Matriz es la plantilla que sirve de estructura para almacenar el contenido de las
matrices del aplicativo, ya sean de preferencias o de emparejamientos. Se trata de una
lista de listas multidimensional, es decir sin una dimensión predefinida, y una serie de
operaciones con la lógica necesaria para manipular y consultar su contenido.
Estabilidad en Emparejamientos
63
3.3.1.12 Clase Cuadricula
La clase Cuadricula es la encargada de pintar las matrices de preferencias y
emparejamientos en el panel central de la aplicación. Dibuja la cuadrícula externa de las
matrices y el contenido de las celdas en el caso de que corresponda. El contenido de las
celdas es un valor numérico que puede estar tachado si se trata de un descarte realizado
durante la fase de análisis de estabilidad.
Estabilidad en Emparejamientos
64
Estabilidad en Emparejamientos
65
4 MANUAL DE USUARIO
EeE (Estabilidad en Emparejamientos) es una aplicación JAVA distribuida en un
paquete JAR que puede, por tanto, ser ejecutada en cualquier sistema que cuente con
una Máquina Virtual de Java (JVM).
La distribución de los elementos en la aplicación es similar a la empleada en cualquier
otra herramienta gráfica.
4.1 Partes de la Aplicación
La ventana principal de la aplicación EeE está compuesta por los siguientes elementos:
• Barra de Menús
• Barra de Herramientas
• Interfaz de Ejecución
• Panel
• Información
4.1.1 Barra de Menús
A continuación, se describen los menús de la aplicación indicando la utilidad de cada
una de las opciones, sin entrar a explicarlas en profundidad.
No todas las opciones del menú están habilitadas en cualquier momento. En función del
estado en que se encuentren las matrices de preferencias y la matriz de
emparejamientos, se activan o desactivan las distintas opciones.
Figura 4.1: Barra de Menús
Estabilidad en Emparejamientos
66
4.1.1.1 Inicio
En el menú “Inicio” aparecen las clásicas opciones Nuevo, Cerrar y Salir.
Figura 4.2: Menú Inicio
• Nuevo: Solicita el número de parejas que desean establecerse, y a continuación
crea una matriz de preferencias para los integrantes del grupo A y otra matriz de
preferencias para los integrantes del grupo B. Ejecuta la operación “Iniciar
Emparejamiento”.
• Cerrar: Deja la aplicación en su estado inicial, eliminando, en caso de que
existan, las matrices de preferencias y la matriz de emparejamientos. Ejecuta la
operación “Cerrar Emparejamiento”.
• Salir: Permite cerrar y salir de la aplicación.
4.1.1.2 Algoritmos
En el menú “Algoritmos” aparecen los distintos tipos de algoritmos que pueden
ejecutarse.
Figura 4.3: Menú Algoritmos
Este menú contiene las siguientes opciones:
• Listas Completas: Ejecuta el algoritmo sobre las matrices de preferencias A y B
completas, es decir, todos los integrantes de los grupos A y B tienen que
Estabilidad en Emparejamientos
67
establecer su orden de preferencia incluyendo a todos los integrantes del otro
grupo sin excepción.
• Listas Incompletas: Ejecuta el algoritmo sobre las matrices de preferencias A y
B incompletas, es decir, los integrantes de los grupos A y B pueden establecer
sus preferencias sin incluir a todos los integrantes del otro grupo.
4.1.1.3 Preferencias
En el menú “Preferencias” aparecen funcionalidades de ayuda para vaciar y rellenar las
matrices de preferencias.
Figura 4.4: Menú Preferencias
Este menú contiene las siguientes opciones:
• Borrar: Elimina todas las elecciones definidas en las matrices de preferencias A
y B. Ejecuta la operación “Borrar Preferencias”.
• Completar: Completa de manera aleatoria las listas de preferencias de todos los
integrantes de los grupos A y B en función del tipo de algoritmo seleccionado,
manteniendo las posibles elecciones definidas manualmente. Ejecuta la
operación “Completar Preferencias”.
4.1.1.4 Referencias
En el menú “Referencias” aparecen las distintas prioridades o puntos de vista que
pueden establecerse para la ejecución del algoritmo.
Estabilidad en Emparejamientos
68
Figura 4.5: Menú Referencias
Este menú contiene las siguientes opciones:
• Punto de Vista A’s: Ejecuta el algoritmo tomando como referencia inicial las
preferencias del grupo A.
• Punto de Vista B’s: Ejecuta el algoritmo tomando como referencia inicial las
preferencias del grupo B.
• Ambos: Ejecuta el algoritmo tomando como referencia inicial las preferencias
del grupo A y posteriormente las preferencias del grupo B.
4.1.1.5 Idioma
En el menú “Idioma” se puede definir el idioma de la aplicación. El idioma por defecto
de la aplicación es español.
Figura 4.6: Menú Idioma
Este menú contiene las siguientes opciones:
• Español: Todo el contenido de la aplicación se muestra en español.
• Inglés: Todo el contenido de la aplicación se muestra en inglés.
Estabilidad en Emparejamientos
69
4.1.1.6 Ayuda
En el menú “Ayuda” se ofrece acceso al manual de usuario e información acerca de la
aplicación.
Figura 4.7: Menú Ayuda
Este menú contiene las siguientes opciones:
• Ayuda: Abre el manual de usuario.
• Acerca de: Muestra información de la aplicación.
4.1.2 Barra de Herramientas
La barra de herramientas se encuentra situada debajo de la barra de menús y pretende
facilitar un acceso rápido a las funcionalidades angulares de la aplicación, como son el
inicio y fin de la aplicación y la visualización de la ayuda. El resto de funcionalidades
asociadas al control de ejecución de la aplicación quedan situadas en el interfaz lateral.
Esta barra se mantiene habilitada en todo momento, independientemente del estado de
definición o ejecución en que se encuentre el algoritmo.
Figura 4.8: Barra de Herramientas
A continuación, explicaremos brevemente la funcionalidad de cada elemento de la barra
de herramientas:
• Nuevo: Solicita el número de parejas que desean establecerse, y a continuación
crea una matriz de preferencias para los integrantes del grupo A y otra matriz de
preferencias para los integrantes del grupo B. Realiza la misma funcionalidad
Estabilidad en Emparejamientos
70
que al seleccionar Inicio Nuevo. Ejecuta la operación “Iniciar
Emparejamiento”.
Figura 4.9: Herramienta Nuevo
• Cerrar: Deja la aplicación en su estado inicial, eliminando, en caso de que
existan, las matrices de preferencias y la matriz de emparejamientos. Realiza la
misma funcionalidad que al seleccionar Inicio Cerrar. Ejecuta la operación
“Cerrar Emparejamiento”.
Figura 4.10: Herramienta Cerrar
• Ayuda: Se abre el manual de usuario. Realiza la misma funcionalidad que al
seleccionar Ayuda Ayuda.
Figura 4.11: Herramienta Ayuda
4.1.3 Interfaz de Ejecución
El interfaz de ejecución se encuentra situado en la parte izquierda de la pantalla.
Contiene todos los elementos necesarios para definir y controlar el flujo de ejecución de
la aplicación, excluyendo las funcionalidades de inicio y fin situadas en la barra de
herramientas.
De la misma manera que sucede en la barra de menús, no todas las opciones están
habilitadas en cualquier momento, sino que se activan o desactivan en función del
estado en que se encuentren las matrices de preferencias y la matriz de
emparejamientos.
Estabilidad en Emparejamientos
71
Figura 4.12: Interfaz de Ejecución
El interfaz de ejecución está dividido en los siguientes subgrupos:
• Algoritmos
• Preferencias
• Referencias
• Emparejamientos
4.1.3.1 Algoritmos
Permite definir el algoritmo que desea ejecutarse.
Estabilidad en Emparejamientos
72
Figura 4.13: Interfaz de Algoritmos
• Listas Completas: Ejecuta el algoritmo sobre las matrices de preferencias A y B
completas, es decir, todos los integrantes de los grupos A y B tienen que
establecer su orden de preferencia incluyendo a todos los integrantes del otro
grupo sin excepción. Por lo tanto, no pueden quedar celda de las matrices de
preferencias sin rellenar.
• Listas Incompletas: Ejecuta el algoritmo sobre las matrices de preferencias A y
B incompletas, es decir, los integrantes de los grupos A y B pueden establecer
sus preferencias sin incluir a todos los integrantes del otro grupo. De esta
manera, se permiten matrices de preferencias con celdas sin rellenar siempre que
la lista finalice tras su primera celda vacía, es decir, no puede haber celdas
rellenas tras una celda vacía.
Se trata de un radio button de alternativas, por lo tanto, sólo se permite seleccionar un
único algoritmo.
Este subgrupo sólo se habilita una vez que se ha iniciado un nuevo emparejamiento, y se
deshabilita siempre que el algoritmo no se encuentre en su estado inicial, es decir
cuando haya comenzado su ejecución.
4.1.3.2 Preferencias
Ofrece funcionalidades de ayuda para vaciar y rellenar las matrices de preferencias de
forma automática.
Figura 4.14: Interfaz de Preferencias
Estabilidad en Emparejamientos
73
• Borrar: Elimina todas las elecciones definidas en las matrices de preferencias A
y B. Todas las celdas de las matrices quedan vacías. Ejecuta la operación
“Borrar Preferencias”.
Figura 4.15: Borrar
• Completar: Completa de manera aleatoria las matrices de preferencias A y B,
manteniendo las posibles elecciones definidas manualmente y atendiendo al tipo
de algoritmo seleccionado en el grupo anterior. Ejecuta la operación “Completar
Preferencias”.
Figura 4.16: Completar
Una vez iniciado un emparejamiento, el botón Borrar siempre está habilitado para
eliminar las posibles preferencias que hayan sido definidas, pero el botón Completar
sólo se habilita cuando se ha seleccionado un algoritmo. Ambos botones se deshabilitan
siempre que el algoritmo no se encuentre en su estado inicial, es decir cuando haya
comenzado su ejecución.
4.1.3.3 Referencias
Permite definir el punto de vista desde el que va a ejecutarse el algoritmo.
Figura 4.17: Interfaz de Referencias
• Punto de Vista A’s: Ejecuta el algoritmo tomando como referencia inicial las
preferencias del grupo A. Por lo tanto, se crea una matriz de emparejamientos
Estabilidad en Emparejamientos
74
inicialmente vacía para los integrantes del grupo A, y se irán estudiando sus
preferencias sobre el grupo B.
• Punto de Vista B’s: Ejecuta el algoritmo tomando como referencia inicial las
preferencias del grupo B. Por lo tanto, se crea una matriz de emparejamientos
inicialmente vacía para los integrantes del grupo B, y se irán estudiando sus
preferencias sobre el grupo A.
• Ambos: Ejecuta el algoritmo tomando como referencia inicial las preferencias
del grupo A y posteriormente las preferencias del grupo B. Por lo tanto, se crean
dos matrices de emparejamientos inicialmente vacías para los integrantes del
grupo A y del grupo B, y se irán estudiando secuencialmente sus preferencias
sobre el otro grupo.
Se trata de un radio button de alternativas, por lo tanto, sólo se permite seleccionar una
única referencia.
Este subgrupo sólo se habilita una vez que se ha iniciado un nuevo emparejamiento, y se
deshabilita siempre que el algoritmo no se encuentre en su estado inicial, es decir
cuando ha comenzado su ejecución.
4.1.3.4 Emparejamientos
Permite controlar el flujo de ejecución del algoritmo seleccionado, actuando
directamente sobre la matriz o las matrices de emparejamientos. Se trata, por lo tanto,
del interfaz que permite avanzar o retroceder entre las diferentes propuestas de
emparejamiento y sus respectivos análisis hasta llegar a un resultado estable.
Figura 4.18: Interfaz de Emparejamientos
Estabilidad en Emparejamientos
75
• Inicio: Inicializa el algoritmo dejando vacías la matriz o matrices de
emparejamientos. Ejecuta la operación "Inicializar Algoritmo".
Figura 4.19: Inicio
• Atrás: Retrocede un paso en el algoritmo dejando la matriz de emparejamientos
en el estado anterior al actual. Ejecuta la operación "Retroceder Algoritmo".
Figura 4.20: Atrás
• Avanzar: Ejecuta el siguiente paso del algoritmo mostrando una nueva
propuesta de emparejamientos o el análisis de la propuesta anterior. Ejecuta la
operación "Comprobar Algoritmo" y si no se detectan problemas ejecuta la
operación "Avanzar Algoritmo".
Figura 4.21: Avanzar
• Final: Ejecuta todos los pasos del algoritmo hasta obtener emparejamientos
estables. Ejecuta la operación "Comprobar Algoritmo" y si no se detectan
problemas ejecuta la operación "Finalizar Algoritmo".
Figura 4.22: Final
• Lista Final: Muestra una única columna de la matriz o matrices de
emparejamientos con un resultado estable. Ejecuta la operación "Comprobar
Algoritmo" y si no se detectan problemas ejecuta la operación "Obtener Lista
Final".
Estabilidad en Emparejamientos
76
Figura 4.23: Lista Final
Este subgrupo sólo se habilita una vez que todas las matrices de preferencias están
correctamente definidas según el tipo de algoritmo seleccionado (listas completas o
incompletas) y se ha creado la matriz o matrices de emparejamientos mediante la
selección de una referencia (punto de vista de A's, de B's o ambos). Una vez que se
activa el interfaz únicamente se deshabilita cuando se cierra el emparejamiento.
Hay que resaltar el particular funcionamiento del botón "Lista Final", que altera el flujo
convencional del algoritmo omitiendo todas las propuestas previas de emparejamiento y
sus respectivos análisis de estabilidad, y muestra directamente el resultado final; por lo
tanto, una vez que se ejecuta esta operación se inhabilitan los botones de retroceso,
avance y final.
4.1.4 Panel
El panel es la parte central de la aplicación donde quedan representadas las preferencias
de los integrantes de los grupos A y B, y donde se visualiza una sucesión de propuestas
de emparejamientos hasta obtener una elección estable.
El panel está definido con una dimensión inicial, pero puede ampliarse al maximizar la
ventana y cuenta con un scroll automático que aparece en caso de necesidad para
permitir el acceso a todo el contenido que pudiese quedar fuera del campo de visión si el
número de parejas definido es elevado.
4.1.4.1 Matrices de Preferencias
Inicialmente el panel aparece completamente vacío, pero una vez que se genera un
nuevo emparejamiento se dibujan en el panel las matrices de preferencias de los grupos
A y B con todas sus celdas vacías:
Estabilidad en Emparejamientos
77
Figura 4.24: Panel Preferencias
4.1.4.2 Matrices de Emparejamientos
Una vez definidas las matrices de preferencias, se pueden rellenar manualmente
actuando directamente sobre las celdas que se desean modificar. Para ello se puede
hacer click con el botón izquierdo para establecer una preferencia, o con el botón
derecho para eliminar la preferencia, de manera que se ejecutan las operaciones "Añadir
Preferencia" y "Vaciar Preferencia" respectivamente. La edición manual de las celdas se
deshabilita en el momento que el algoritmo no se encuentra en su estado inicial, es decir
cuando ha comenzado su ejecución.
De manera alternativa se pueden rellenar o vaciar las preferencias de las matrices con
las funcionalidades Completar y Borrar del menú Preferencias o del interfaz lateral
Preferencias.
En el momento que se selecciona un Algoritmo y una Referencia, se dibuja la matriz o
las matrices de resultados en las que se muestran propuestas de emparejamientos y el
análisis de su estabilidad.
Estabilidad en Emparejamientos
78
En función de la referencia seleccionada, se mostrará una matriz de emparejamientos
para el grupo A, una matriz para el grupo B o una matriz para el grupo A y otra para el
grupo B:
• Punto de Vista de A`s: Muestra la matriz de emparejamientos del grupo A con
una única columna inicialmente vacía.
Figura 4.25: Panel Punto de Vista A
• Punto de Vista de B’s: Muestra la matriz de emparejamientos del grupo B con
una única columna inicialmente vacía.
Estabilidad en Emparejamientos
79
Figura 4.26: Panel Punto de Vista B
• Ambos: Muestra las matrices de emparejamientos del grupo A y B con una
única columna inicialmente vacía para cada una.
Figura 4.27: Panel Ambos
Finalmente, mediante las opciones presentes en el interfaz de emparejamientos se irán
visualizando las distintas propuestas y su análisis hasta llegar a un emparejamiento
estable.
Estabilidad en Emparejamientos
80
4.1.5 Información
La zona de información está situada en la parte inferior de la pantalla y muestra una
breve descripción de la funcionalidad asociada a cada una de las interfaces presentes en
la aplicación (botones, menús, matriz de preferencias, .. ).
Cuando el puntero del ratón pasa por encima de cada elemento de la aplicación con el
que se puede interactuar, se muestra un mensaje que pretende ser de utilidad para la
comprensión de cada funcionalidad. La información desaparece al alejar el puntero del
ratón del elemento interactivo.
En la siguiente figura de ejemplo, se muestra el mensaje informativo que aparece al
pasar el puntero del ratón por cada una de las celdas editables de las matrices de
preferencias:
Figura 4.28: Información
4.2 Operaciones
A continuación, se describen las principales operaciones que integran la operativa de la
aplicación.
Estas operaciones pueden dividirse en tres subgrupos:
• Herramientas
• Preferencias
• Emparejamientos
Estabilidad en Emparejamientos
81
4.2.1 Herramientas
Este subgrupo está formado por las operaciones de comienzo y fin de un
emparejamiento, funcionalidades que están dotadas de acceso rápido en la barra de
herramientas.
4.2.1.1 Iniciar Emparejamiento
La operación "Iniciar Emparejamiento" permite comenzar a definir un emparejamiento.
Es accesible desde la opción "Nuevo" del menú Inicio y desde el icono "Nuevo" de la
barra de Herramientas.
Se trata de la primera operación que debe ejecutarse para hacer uso de la aplicación,
puesto que su propósito es definir el número de parejas sobre las que se va a buscar
estabilidad en emparejamientos.
Al ejecutar esta operación aparece la siguiente ventana:
Figura 4.29: Nuevo Emparejamiento
Desde esta ventana se realiza una validación del valor introducido por el usuario.
No se permite introducir un valor no numérico, en caso contrario se muestra un mensaje
de error advirtiendo de esta circunstancia:
Estabilidad en Emparejamientos
82
Figura 4.30: Error - Nuevo
Tampoco se permite introducir un número inferior o superior a los límites establecidos
en la aplicación (1-99), en caso contrario se muestra otro mensaje de error indicando
que el número está fuera de rango:
Figura 4.31: Error - Fuera de Rango
Una vez definido correctamente el número de parejas que forman el emparejamiento, se
dibuja en el panel las matrices de preferencias de A y B, se permite la edición manual de
todas las celdas, y se habilitan la elección del algoritmo desde la barra de menús o desde
el interfaz lateral.
4.2.1.2 Cerrar Emparejamiento
La operación "Cerrar Emparejamiento" permite finalizar un emparejamiento
previamente inicializado. Es accesible desde la opción "Cerrar" del menú Inicio y desde
el icono "Cerrar" de la barra de Herramientas.
Deja la aplicación en su estado inicial. Se eliminan las matrices de preferencias y de
emparejamientos que estuviesen definidas y todo su contenido, el panel queda
completamente vacío y se deshabilitan todos los botones del interfaz lateral y todas las
opciones de la barra de menús con excepción de los menús “Inicio” y “Ayuda”.
Estabilidad en Emparejamientos
83
4.2.2 Preferencias
Este subgrupo está formado por las operaciones que permiten manipular las celdas de
las matrices de preferencias, ya sea de forma manual o automática.
4.2.2.1 Añadir Preferencia
La operación "Añadir Preferencia" permite establecer el contenido de una celda. Es
accesible desde el panel de matrices.
Al hacer click con el botón izquierdo del ratón en una celda concreta de las matrices de
preferencias (A ó B) aparece una ventana en la que se solicita la introducción de uno de
los subíndices identificativos de los integrantes del grupo opuesto que quedan libres, es
decir, que no se encuentran actualmente en otra posición de la lista.
Figura 4.32: Valor Celda
Desde esta ventana se realiza una validación del valor introducido por el usuario.
No se permite introducir un valor no numérico, en caso contrario se muestra un mensaje
de error advirtiendo de esta circunstancia:
Estabilidad en Emparejamientos
84
Figura 4.33: Error - Celda
Tampoco se permite introducir un número distinto a los definidos en la lista
"Posibilidades" en la propia ventana, en caso contrario se muestra otro mensaje de error
indicando cuales son los subíndices disponibles:
Figura 4.34: Error – Posibilidades
Esta operación se encuentra habilitada mientras existen las matrices de preferencias y no
ha comenzado la ejecución del algoritmo.
4.2.2.2 Vaciar Preferencia
La operación "Vaciar Preferencia" permite vaciar el contenido de una celda. Es
accesible desde el panel de matrices.
Al hacer click con el botón derecho del ratón en una celda concreta de las matrices de
preferencias A ó B se elimina el contenido que se hubiese definido previamente.
Esta operación se encuentra habilitada mientras existen las matrices de preferencias y no
ha comenzado la ejecución del algoritmo.
Estabilidad en Emparejamientos
85
4.2.2.3 Borrar Preferencias
La operación "Borrar Preferencias" permite vaciar en un solo paso todas las celdas de
las matrices de preferencias A y B. Es accesible desde la opción "Borrar" del menú
Preferencias y desde el icono "Borrar" del interfaz lateral Preferencias.
Esta operación permanece habilitada mientras se mantiene abierto el emparejamiento
definido, y sólo se desactiva cuando el algoritmo no se encuentra en su estado inicial, es
decir cuando ha comenzado su ejecución.
4.2.2.4 Completar Preferencias
Esta operación permite completar de manera aleatoria las matrices de preferencias A y
B. Es accesible desde la opción "Completar" del menú Preferencias y desde el icono
"Completar" del interfaz lateral Preferencias.
Las matrices se completan respetando las siguientes premisas:
• Se mantienen todas las preferencias definidas previamente de manera manual.
• No se permite repetición de preferencias en las diferentes listas de cada matriz.
• Cada celda se rellena aleatoriamente entre las opciones restantes de cada lista de
preferencias.
• Si el algoritmo seleccionado es “Listas Completas”, se rellenan todas las celdas
que estuviesen vacías en cada matriz.
• Si el algoritmo es “Listas Incompletas”, se rellenan las matrices permitiendo
listas de preferencias que finalizan tras una primera celda vacía elegida
aleatoriamente.
Esta operación se encuentra habilitada desde el momento que se selecciona un
algoritmo, y se inhabilita cuando comienza su ejecución.
Estabilidad en Emparejamientos
86
4.2.3 Emparejamientos
Este subgrupo está formado por las operaciones que permiten avanzar o retroceder la
ejecución del algoritmo por todos y cada uno de sus estados.
4.2.3.1 Inicializar Algoritmo
Esta operación permite devolver el algoritmo a su estado inicial. Es accesible desde el
icono "Inicio" del interfaz lateral Emparejamientos.
Se mantienen la selección de algoritmo y referencia, pero se reinicia la matriz o
matrices de emparejamientos a su estado inicial, dejando todas las celdas vacías sin
mostrar ninguna propuesta de emparejamiento.
Esta operación se encuentra habilitada mientras se mantiene seleccionado todo lo
necesario para la definición de un emparejamiento (algoritmo y referencia),
independiente de si las matrices de preferencias están correctamente rellenas o del
estado en que se encuentre la ejecución del algoritmo.
4.2.3.2 Retroceder Algoritmo
Esta operación permite acceder al paso anterior del algoritmo. Es accesible desde el
icono "Atrás" del interfaz lateral Emparejamientos.
Devuelve la matriz de emparejamientos al estado inmediatamente anterior al estado
actual de ejecución. Por lo tanto, deja de mostrar una propuesta de emparejamientos o el
análisis de estabilidad de la última propuesta existente.
Esta operación se encuentra habilitada mientras se mantiene seleccionado todo lo
necesario para la definición de un emparejamiento (algoritmo y referencia), con
independencia de si las matrices de preferencias están correctamente rellenas o del
estado en que se encuentre la ejecución del algoritmo. Excepcionalmente, esta
operación queda deshabilitada al ejecutar la operación “Obtener Lista Final” puesto que
altera el flujo convencional de ejecución del algoritmo.
Estabilidad en Emparejamientos
87
4.2.3.3 Comprobar Algoritmo
Esta operación realiza una serie de comprobaciones en las matrices de preferencias
antes de permitir que comience la ejecución del algoritmo seleccionado. Es accesible
desde los iconos "Avanzar", "Final" y "Lista Final" del interfaz lateral
Emparejamientos.
En función del algoritmo seleccionado se realizan las siguientes comprobaciones:
• Listas Completas: Se comprueba si existen celdas vacías, primero se analiza la
matriz de preferencias A, y a continuación la matriz de preferencias B. En el
caso de que se identifique esta circunstancia se muestra el siguiente mensaje de
advertencia:
Figura 4.35: Error – Listas Completas
• Listas Completas: Se comprueba si existen listas incompletas con un formato
erróneo, primero se analiza la matriz de preferencias A, y a continuación la
matriz de preferencias B. Una lista incompleta tiene un formato erróneo cuando
tras una celda vacía existen celdas con un valor definido. En el caso de que se
identifique esta circunstancia se muestra el siguiente mensaje de advertencia:
Figura 4.36: Error – Listas Incompletas
Estabilidad en Emparejamientos
88
Esta operación se ejecuta automáticamente antes de comenzar las operaciones “Avanzar
Algoritmo”, “Finalizar Algoritmo” y “Obtener Lista Final”, y únicamente si su
resultado es positivo se permite continuar con la siguiente operación.
4.2.3.4 Avanzar Algoritmo
Esta operación permite ejecutar el siguiente paso del algoritmo. Es accesible desde el
icono "Avanzar" del interfaz lateral Emparejamientos.
Avanza la matriz de emparejamientos al estado inmediatamente posterior al estado
actual de ejecución. Por lo tanto, muestra un nuevo grupo de propuestas en la matriz de
emparejamientos, realiza algún descarte al analizar la última columna de propuestas o
informa de que las propuestas actuales forman un emparejamiento estable. En el caso de
que se haya seleccionado la referencia “Ambos”, si el estado actual es una propuesta de
emparejamientos estable para A, mostrará una propuesta inicial de emparejamientos
para B.
Esta operación se encuentra habilitada mientras se mantiene seleccionado todo lo
necesario para la definición de un emparejamiento (algoritmo y referencia), pero su
ejecución está supeditada al resultado satisfactorio de la operación “Comprobar
Algoritmo”. Excepcionalmente, esta operación queda deshabilitada al ejecutar la
operación “Obtener Lista Final” puesto que altera el flujo convencional de ejecución del
algoritmo.
4.2.3.5 Finalizar Algoritmo
Esta operación permite ejecutar todos los pasos del algoritmo. Es accesible desde el
icono "Finalizar" del interfaz lateral Emparejamientos.
Muestra todas las columnas de la matriz o matrices de emparejamientos con todas las
propuestas y sus respectivos análisis hasta llegar a un resultado final de propuestas de
emparejamientos estables.
Estabilidad en Emparejamientos
89
Esta operación se encuentra habilitada mientras se mantiene seleccionado todo lo
necesario para la definición de un emparejamiento (algoritmo y referencia), pero su
ejecución está supeditada al resultado satisfactorio de la operación “Comprobar
Algoritmo”. Excepcionalmente, esta operación queda deshabilitada al ejecutar la
operación “Obtener Lista Final” puesto que altera el flujo convencional de ejecución del
algoritmo.
4.2.3.6 Obtener Lista Final
Esta operación permite visualizar una única columna de la matriz o matrices de
emparejamientos con un resultado estable. Es accesible desde el icono "Lista" del
interfaz lateral Emparejamientos.
Muestra únicamente una columna en la matriz o matrices de emparejamientos con una
propuesta de emparejamiento estable. Se trata de una funcionalidad que altera el flujo
convencional de ejecución del algoritmo ya que omite todas las propuestas previas de
emparejamiento y su análisis de estabilidad, mostrando directamente el resultado final.
Esta operación se encuentra habilitada mientras se mantiene seleccionado todo lo
necesario para la definición de un emparejamiento (algoritmo y referencia), pero su
ejecución está supeditada al resultado satisfactorio de la operación “Comprobar
Algoritmo”.
4.3 Ejecución
En primer lugar, es interesante destacar que en todo momento existe la posibilidad de
cambiar el idioma del aplicativo desde el menú Idioma. El cambio de idioma afecta a
cualquier parte de la aplicación con presencia de texto: títulos de ventana, menús,
interfaces y mensajes informativos. Los idiomas disponibles son español
(predeterminado) e inglés.
Estabilidad en Emparejamientos
90
El primer paso necesario para comenzar a utilizar la aplicación EeE consiste en crear un
nuevo emparejamiento desde la opción “Nuevo” del menú Inicio o desde el botón
“Nuevo” de la barra de herramientas.
A continuación, es necesario definir el número de parejas para las que se pretende
encontrar un emparejamiento estable; los algoritmos trabajan sobre grupos con el
mismo número de integrantes, por lo tanto, el número de parejas establecido define la
dimensión tanto de la matriz A como de la matriz B.
En cualquier momento se da la opción de cerrar el emparejamiento establecido y
cualquier definición que llevase asociada mediante la opción “Cerrar” del menú Inicio o
desde el botón “Cerrar” de la barra de herramientas. De esta manera la aplicación
vuelve al estado inicial y sería necesario volver al primer paso para definir un nuevo
emparejamiento.
Una vez generadas las matrices de preferencias se permite comenzar a definir las
prioridades de cada integrante de un grupo sobre los integrantes del grupo opuesto.
Para definir las preferencias de forma manual, basta con pulsar el botón izquierdo sobre
cada una de las celdas de las matrices de preferencias del Panel y definir las prioridades
de emparejamiento de los integrantes de cada grupo, de manera que las primeras
posiciones de la lista implican una mayor preferencia que el resto de posibilidades.
Al pulsar en cada celda se permite elegir entre los integrantes del grupo contrario que no
aparecen en ninguna otra posición de su propia lista. De la misma manera, para
modificar una preferencia simplemente hay que pulsar el botón izquierdo sobre su celda
asociada y elegir una nueva prioridad.
Al pulsar el botón derecho sobre una celda se elimina su preferencia asociada.
Alternativamente, se puede rellenar las celdas que han quedado sin rellenar de manera
aleatoria mediante el botón “Completar” del interfaz lateral Preferencias. Sin embargo,
este botón únicamente se habilita cuando se ha seleccionado uno de los algoritmos
existentes en el interfaz lateral Algoritmos o desde el menú Algoritmos, puesto que
Estabilidad en Emparejamientos
91
varía la forma en que se pueden rellenar las matrices. Si el algoritmo es “Listas
Completas” los integrantes de cada grupo deben indicar sus preferencias sobre todos los
integrantes del otro grupo sin excepción, si por el contrario el algoritmo es “Listas
Incompletas” se permite que los integrantes de un grupo dejen preferencias sin definir
sobre el grupo opuesto.
Si se desea devolver las matrices de emparejamientos a su estado inicial de definición,
se puede utilizar el botón “Borrar” del interfaz lateral Preferencias. Las matrices se
mantienen definidas con el número de parejas previamente seleccionado, pero todas las
preferencias que se hubiesen establecido manual o aleatoriamente, quedan eliminadas.
El siguiente paso consiste en definir un punto de vista que sirva como referencia para
buscar emparejamientos estables. Para ello, hay que seleccionar una de las opciones del
interfaz lateral Referencias o desde el menú Referencias.
Si se selecciona la referencia “Punto de Vista A’s” se comienza a analizar propuestas de
emparejamientos tomando como punto de partida las preferencias establecidas por el
grupo A. Análogamente, si se selecciona la referencia “Punto de Vista B’s” se toma
como punto de partida las preferencias establecidas por el grupo B. Si se selecciona la
referencia “Ambos” se generan dos matrices de emparejamientos en las que se toma
inicialmente como punto de partida las preferencias del grupo A y posteriormente las
preferencias del grupo B.
En el momento que las matrices de preferencias están correctamente rellenas y se ha
establecido la referencia deseada, se puede comenzar la ejecución del algoritmo. Sin
embargo, si las matrices no están correctamente rellenas en función del algoritmo
deseado, se muestra un mensaje de advertencia que impide la ejecución del algoritmo.
Finalmente, mediante los botones del interfaz lateral Emparejamientos se permite
recorrer todos los estados del algoritmo que llevan a la obtención de emparejamientos
estables.
El botón “Avanzar” ejecuta el paso del algoritmo inmediatamente posterior al actual.
Estabilidad en Emparejamientos
92
Inicialmente muestra una propuesta de emparejamientos con la primera preferencia de
los integrantes del grupo A.
Figura 4.37: Propuesta Inicial
Al pulsar nuevamente el botón "Avanzar" se realiza un análisis de estabilidad sobre la
propuesta anterior. Durante este análisis se estudian las preferencias de los integrantes
del grupo B que han recibido más de una propuesta de emparejamiento, y se descartan
aquellas propuestas con menor prioridad según su lista de preferencias.
En el siguiente ejemplo, se descarta la propuesta de A2, puesto que A1 tiene mayor
prioridad dentro de las preferencias de B4.
Estabilidad en Emparejamientos
93
Figura 4.38: Análisis Propuesta
La siguiente vez que se pulsa el botón "Avanzar " se muestra una nueva propuesta,
mantenido las preferencias que no fueron descartadas en el paso de análisis anterior y
proponiendo la preferencia inmediatamente posterior de los integrantes del grupo A que
sufrieron un descarte.
Estabilidad en Emparejamientos
94
Figura 4.39: Nueva Propuesta
Cuando el análisis de la última propuesta determina que los emparejamientos presentes
son estables, se ha alcanzado el estado final de la ejecución del algoritmo y se muestra
un mensaje indicando esta circunstancia.
Figura 4.40: Mensaje Emparejamientos Estables
El botón “Final” ejecuta todos los pasos de propuesta de emparejamientos y análisis
hasta obtener estabilidad, independiente del estado en la que se encuentre el algoritmo.
Estabilidad en Emparejamientos
95
Figura 4.41: Emparejamientos Estables
El botón “Lista Final” permite acceder directamente al final del algoritmo sin pasar por
todos los estados intermedios del algoritmo; simplemente muestra una lista con los
emparejamientos estables.
Estabilidad en Emparejamientos
96
Figura 4.42: Lista Final Estable
El botón “Atrás” retrocede al paso del algoritmo inmediatamente anterior al actual. Por
lo tanto, deja de mostrar la última propuesta de emparejamientos o deshace los descartes
realizados durante el análisis de estabilidad, en función de cuál fue el paso anterior del
algoritmo.
El botón “Inicio” retrocede al comienzo del algoritmo, dejando la matriz o las matrices
de preferencias en su estado inicial. No se muestra ninguna preferencia, simplemente
una primera columna vacía que indica que el algoritmo está preparado para comenzar su
ejecución.
Este manual de usuario está siempre accesible desde la opción “Ayuda” del menú
Ayuda y desde el botón “Ayuda” de la barra de herramientas.
Estabilidad en Emparejamientos
97
5 CONCLUSIONES
Con este proyecto se ha conseguido dar una solución gráfica a problemas de asignación
mediante una aplicación que implementa algoritmos de estabilidad en emparejamientos
sobre listas de preferencias completas e incompletas.
Considero que se ha conseguido destacar el trasfondo didáctico de la herramienta, ya
que los algoritmos disponen de un modo de ejecución interactivo, donde el usuario
puede alterar el flujo de ejecución en base a las necesidades docentes requeridas en cada
situación.
Pese a contar con varios años de experiencia laboral en el sector, realizar íntegramente
un proyecto pasando por todas las fases de su ciclo de vida ha resultado ser una práctica
muy enriquecedora en muchos aspectos.
Desde el punto de vista técnico he podido trabajar con el lenguaje de programación Java
y la API Swing para el desarrollo de interfaces gráficas, laboralmente no he tenido
experiencia con estas tecnologías y a nivel personal siempre he querido completar mis
conocimientos de programación con este lenguaje. Desde el punto de vista de la
Ingeniería del Software este proyecto me ha servido para asentar y profundizar
conocimientos en la programación orientada a objetos y en los patrones de diseño.
Posiblemente la mayor complejidad con la que me he encontrado ha sido el tener que
compaginar la vida laboral y el desarrollo del proyecto, puesto que han sido numerosas
las ocasiones en la que no me ha sido posible dedicar todo el tiempo que había
planificado. No obstante, resulta reconfortante echar la vista atrás y poder comprobar
que el tiempo dedicado ha quedado materializa de forma tangible en este proyecto.
Estabilidad en Emparejamientos
98
Estabilidad en Emparejamientos
99
6 BIBLIOGRAFÍA
• Ferré Grau, Xavier; Sánchez Segura, María Isabel
“Desarrollo Orientado a Objetos con UML”
Facultad de Informática – UPM
• Fleiner, Tamás; Irving, Robert W.; Manlove, David F.
“Efficient Algorithms for Generalized Stable Marriage and Roommates
problems”
Theoretical Computer Science 381, 162–176, Budapest University and
University of Glasgow, 2007
• Gale, D.; Shapley, L. S.
“College Admissions and the Stability of Marriage”
American Mathematical Monthly 69, 9-15, 1962
• García de Jalón, Javier y otros
“Aprenda Java”
Campus Tecnológico de la Universidad de Navarra, 2000
• Irving, Robert W.; Manlove, David F.
“The Stable Roommates Problem with Ties"
Journal of Algorithms 43, 85-105, University of Glasgow, 2002
• Király, Zoltán
“Better and Simpler Approximation Algorithms for the Stable Marriage
Problem”
Technical Report, TR-2008-04, EGRES, 2008
• Manlove, David F.
“Stable Marriage with Ties and Unacceptable Partners"
Technical Report, TR-1999-29, University of Glasgow, 1999
Estabilidad en Emparejamientos
100
6.1 Páginas Web
• http://chuwiki.chuidiang.org/index.php?title=Categor%C3%ADa:Java
• http://chuwiki.chuidiang.org/index.php?title=Categor%C3%ADa:Java:SWING
• Java™ Platform, Standard Edition 8 API Specification
http://docs.oracle.com/javase/8/docs/api/
• "Creating a GUI with JFC/Swing"
https://docs.oracle.com/javase/tutorial/uiswing/
• https://en.wikipedia.org/wiki/Matching_(graph_theory)
• https://en.wikipedia.org/wiki/Stable_marriage_problem
• https://en.wikipedia.org/wiki/Stable_roommates_problem