estudiantes de grupo de probabilidad para maximizar las expectativas
Dado $3n$ gente que el $i^{\text{th}}$ la persona puede pasar una prueba con probabilidad $p_i$, ahora debe dividirlos para $n$ grupos que tiene cada grupo $3$personas. La puntuación de un grupo es igual a$1$ si al menos dos personas pasan la prueba, $0$de otra manera. Para maximizar la expectativa de puntuación total, ¿cómo los agrupa?
He pensado un poco en este problema y creo que intuitivamente tiene sentido agrupar dos $p_i$ con un pequeño $p_i$. Además, he pensado en la disposición óptima, intercambiar dos$p_i$de diferentes grupos debería reducir la expectativa. Puedo escribir matemáticamente la diferencia de expectativa al intercambiar a dos de los estudiantes, pero no parece dar ningún resultado obvio. Me he estrellado contra una pared.
Respuestas
Puede resolver el problema mediante la programación lineal de enteros utilizando la siguiente formulación de partición de conjuntos. Dejar$S=\{1,\dots,3n\}$ ser el conjunto de estudiantes, y dejar $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$ser el conjunto de triples de alumnos. Xa$(i,j,k)\in T$, sea variable de decisión binaria $x_{i,j,k}$ indicar si triple $(i,j,k)$está asignado a un grupo. Si$x_{i,j,k}=1$, la probabilidad de aprobación para ese grupo es \begin{align} P_{i,j,k}&:=p_i p_j p_k+(1-p_i) p_j p_k+p_i (1-p_j) p_k+p_i p_j (1-p_k)\\ &=p_i p_j + p_i p_k + p_j p_k - 2 p_i p_j p_k. \end{align} El problema es maximizar $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$sujeto a \ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {para$s\in S$} \ tag2 \ end {align} La función objetivo$(1)$es la puntuación total esperada. Restricción$(2)$ asigna a cada estudiante a exactamente un grupo.
Experimentación numérica para pequeños $n$ y distribuido uniformemente $p_i$confirma su intuición de dos probabilidades grandes y una pequeña por grupo. De hecho, la probabilidad más pequeña aparece con las dos más grandes, la siguiente más pequeña con las dos siguientes más grandes, y así sucesivamente. Por ejemplo, si los estudiantes se vuelven a etiquetar en orden creciente de$p_i$ (sin pérdida de generalidad), entonces $n=6$ grupos de rendimiento $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Actualización : aquí hay un pequeño contraejemplo con$n=2$. Tomar$p=(0,0,0.1,0.6,0.8,0.8)$. Entonces grupos$\{\{1,2,3\},\{4,5,6\}\}$ producir una puntuación esperada de $0.832$, mientras que los grupos $\{\{1,5,6\},\{2,3,4\}\}$ producir una puntuación esperada menor de $0.7$.
He aquí una forma de simplificar el problema. Dejar$p_i = x_i + 1/2$. Entonces deseamos maximizar la expresión
\begin{align*} &\sum_{(i,j,k)\in T}p_ip_jp_k+(1-p_i)p_jp_k+p_i(1-p_j)p_k+p_ip_j(1-p_k)\\ =&\sum_{(i,j,k)\in T}\frac12+\frac12(x_i+x_j+x_k)-2x_ix_jx_k\\ =&N/2 +\frac12\sum_{i<3N}x_i-2\sum_{(i,j,k)\in T}x_ix_jx_k \end{align*}
en el que solo el último término depende de la partición $T$. Así que hemos simplificado el problema para encontrar el$T$ que minimiza la suma de los productos de la $x$s en cada grupo de tres.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$