Rotación de los niños en las mesas cada mes

Question

Mi mujer da clases de jardín de infancia por la mañana y por la tarde. La AM tiene 14 alumnos y la PM 11. Al principio de cada mes, ella pone una nueva tabla de asientos donde rota a los estudiantes de tal manera que (idealmente) se sientan en una mesa diferente y con diferentes estudiantes para ese mes.

Hay 3 estudiantes por mesa, pero si los números obligan a ello, la última puede tener más o menos. Somos conscientes de que, al final del año, habrá algunas situaciones inevitables en las que los estudiantes acaben sentados unos con otros o en las mismas mesas de nuevo, y esto está bien.

Trabaja en este diagrama de asientos cada mes y es una tarea enorme. Es angustioso verla hacer esto porque lleva mucho tiempo, y me siento impotente. Sé que tiene que haber una forma matemática de hacerlo. Encontré una fórmula aquí, pero no pude averiguar qué representaban las variables y cómo cambiarlas para satisfacer sus necesidades a medida que los estudiantes van y vienen. ¿Puede alguien ayudarme? Sería aún mejor si pudiera usar Excel para automatizar este proceso. [perdón si las etiquetas son inapropiadas; sólo lo he adivinado].

Answer 1

Si entiendo bien el problema (el inglés puede ser ambiguo, las matemáticas no), aquí tienes un modelo que puedes utilizar. El enlace en el comentario no es exactamente el mismo problema (aquí, usted tiene sólo los estudiantes, no los clientes y proveedores). Para la resolución, excel debería estar bien (tengo otras cosas en el trabajo que puedo aconsejar, cualquier solucionador de programación de enteros/programación de restricciones debería servir). Tienes

Un conjunto $[1,N]$ de mesas (esto no es abstracto, pon una pegatina con un número en cada una)

Un conjunto $[1,S]$ de los alumnos (poner una pegatina con un número en la frente de cada uno)

Un conjunto $[1,M]$ de meses

Definir, $\forall$ (para todos, puedes entenderlo como la palabra inglesa si te ayuda) $n \in [1,N], s \in [1,S], m \in [1,M] $ la variable booleana (variable que es igual a $0$ o $1$ ) $x_{n,s,m}$ que es igual a $1$ si el estudiante $s$ se le asigna la tabla $n$ en el mes $m$ .

Definir, $\forall (s,s') \in [1,S]^2$ (pareja de estudiantes), $\forall m \in [1,M],y_{s,s',m}$ la variable binaria que es igual a $1$ si y sólo si los estudiantes $s$ y $s'$ están en la misma mesa en el mes $m$

Entonces, usted quiere tener valores para $x$ que verifican

$\forall n \in [1,N], \forall m \in [1,M], \sum_{s} x_{n,s,m} \leq 3$ (como máximo $3$ estudiantes por mesa al mismo tiempo)

$ \forall s \in [1,S], \forall m \in [1,M], \sum_{n} x_{n,s,m} = 1 $ (cada alumno tiene una mesa afectada en cada periodo de tiempo)

$\forall (s,s') \in [1,S]^2$ tal que $ s \neq s', \forall m \in [1,M], \forall n \in [1,N], x_{n,s,m} + x_{n,s',m} \leq 1 + y_{s,s',m} $ (hacer $y$ igual a $1$ al menos donde debería estar según su definición )

$\forall (s,s') \in [1,S]^2$ tal que $ s \neq s', \sum_m y_{s,s',m} \leq 1$ (no más de $1$ mes juntos para cada pareja de estudiantes)

Este modelo que escribí tiene MUCHA simetría, y supongo que no quieres buscar cómo romper la simetría en la programación lineal entera. Por lo tanto, no busques una solución óptima, sólo una factible (si alguna vez has oído hablar de los algoritmos de rama y límite, apesta siempre que la simetría está presente).

Si el sistema no es factible, dímelo, y con algo más elaborado puedes intentar juntar a los alumnos sólo en los tramos de tiempo más alejados (necesitarás un poco más de variables si quieres que siga siendo lineal).

PD : Vivo con una mujer que es profesora, verla hacer este tipo de cosas es realmente agonizante

Answer 2

Alguien más ha señalado que esto es bastante equivalente al "problema de las colegialas de Kirkman".

El artículo estándar de la wikipedia me ha resultado bastante útil ( aquí ), pero he preferido otro artículo ( aquí ) que explican los algoritmos para encontrar una solución.

En los artículos citados se da una solución para 15 alumnos. La guardería de su mujer tiene 14 alumnos por la mañana, por lo que es posible que el 15º alumno sea un asiento vacío. La solución indicada sólo funciona durante siete meses y no satisface la restricción de cambio de mesas:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} &\text{Jan} &\text{Feb} &\text{Mar} \\ \hline \hline \hline\text{Table 1}& 1, 6, 11 & 1, 2, 5 & 2, 3, 6 & 5, 6, 9 &3, 5, 11 &5, 7, 13& 4, 11, 13\\ \hline \text{Table 2}& 2, 7, 12 & 3, 4, 7 & 4, 5, 8 & 7, 8, 11 &4, 6, 12 &6, 8, 14& 5, 12, 14\\ \hline \text{Table 3} & 3, 8, 13 &8, 9, 12&9, 10, 13&1, 12, 13& 7, 9, 15&2, 9, 11&2, 8, 15 \\ \hline \text{Table 4}&4, 9, 14&10, 11, 14& 11, 12, 15& 3, 14, 15 & 1, 8, 10& 3, 10, 12& 1, 3, 9\\ \hline \text{Table 5} & 5, 10, 15& 6, 13, 15& 1, 7, 14 & 2, 4, 10 &2, 13, 14 & 1, 4, 15 & 6, 7, 10 \\ \hline \end{array}$$

Para que sea una solución adecuada al problema de tu mujer, hay que mover las posiciones de las tablas y añadir otros cinco meses. He traducido los números de las cinco primeras columnas para obtener un nuevo conjunto de trillizos (ninguno repetido del primer conjunto) y luego los he añadido como las cinco columnas siguientes. También cambié las posiciones para que todos los alumnos se sentaran en cada mesa al menos una vez.

El arreglo final es:

Para intentar solucionar el problema de los 11 estudiantes de tu mujer por la tarde, he modificado el algoritmo de Foster. Traté el problema como si hubiera 12 estudiantes, uno de los cuales puede ser asignado posteriormente como asiento vacío.

En primer lugar, no fue posible establecer trillizos de la forma $(x, a_1, a_2), (x, b_1, b_2)$ etc.

En su lugar, decidí omitir el $x$ y pasar directamente a pensar que los alumnos son parejas: $a_1, a_2, b_1, b_2, c_1, c_2, ... , e_1, e_2$

A continuación, identifiqué un conjunto de tripletas que permitían todas las combinaciones.

Trabajé alfabéticamente para que mis trillizos fueran: $abc, ade, bdf, cef$ . Esta sería la base de mi acuerdo para el mes 1.

Creé otro conjunto de trillizos encontrando el complemento de cada uno del primer conjunto de trillizos: $def, bcf, ace, abd$ . Esta sería la base de mi acuerdo para el mes 2.

A continuación, conté el número de emparejamientos que existían y descubrí que hasta el momento no había ningún trío con los emparejamientos: $af, be, cd$ . Utilicé estos emparejamientos para crear los trillizos: $aaf, bbe, ccd$ junto con un cuarto triplete $def$ (para completar la lista de posibles emparejamientos). Esto sería para el mes 3.

A continuación, creé una cuarta serie de trillizos como una especie de complemento de la tercera serie: $add, cee, bff, abc$ . Esto sería para el mes 4.

Ahora tenía lo siguiente:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} \\ \hline \hline \hline\text{Table 1}& a, b, c & d, e, f & a, a, f & a, d, d \\ \hline \text{Table 2}& a,d,e&b,c,f&b,b,e&c,e,e \\ \hline \text{Table 3} & b,d,f&a,c,e&c,c,d&b,f,f \\ \hline \text{Table 4}&c,e,f&a,b,d&d,e,f&a,b,c\\ \hline \end{array}$$

Luego utilicé el método de Frost para etiquetar las letras:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} \\ \hline \hline \hline\text{Table 1}& a_1, b_1, c_1 & d_1, e_2, f_1 & a_1, a_2, f_1 & a_1, d_1, d_2 \\ \hline \text{Table 2}& a_2,d_1,e_1&b_2,c_1,f_2&b_1,b_2,e_2&c_1,e_1,e_2 \\ \hline \text{Table 3} & b_2,d_2,f_1&a_1,c_2,e_1&c_1,c_2,d_1&b_1,f_1,f_2 \\ \hline \text{Table 4}&c_2,e_2,f_2&a_2,b_1,d_2&d_2,e_1,f_2&a_2,b_2,c_2\\ \hline \end{array}$$

Luego sustituí las letras por los números del 1 al 12.

Sólo tengo los primeros cuatro meses, así que tengo que aumentar esto hasta los 12 meses - ¡más por venir!