étudiants du groupe de probabilité pour maximiser les attentes
Donné $3n$ les gens que le $i^{\text{th}}$ la personne peut passer un test avec probabilité $p_i$, maintenant vous devez les diviser en $n$ groupes que chaque groupe a $3$personnes. Le score d'un groupe est égal à$1$ si au moins deux personnes réussissent le test, $0$autrement. Afin de maximiser l'attente du score total, comment les regroupez-vous?
J'ai réfléchi un peu à ce problème et je pense intuitivement qu'il est logique de regrouper deux grands $p_i$ avec un petit $p_i$. Aussi, j'ai pensé à la disposition optimale, en échangeant deux$p_i$de différents groupes devraient abaisser les attentes. Je peux écrire mathématiquement la différence entre les attentes lors de l'échange de deux élèves, mais cela ne semble pas donner de résultat évident. J'ai heurté un mur.
Réponses
Vous pouvez résoudre le problème via la programmation linéaire entière en utilisant la formulation de partitionnement d'ensemble suivante. Laisser$S=\{1,\dots,3n\}$ être l'ensemble des étudiants, et laissez $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$être l’ensemble des triples d’élèves. Pour$(i,j,k)\in T$, laissez la variable de décision binaire $x_{i,j,k}$ indiquer si triple $(i,j,k)$est affecté à un groupe. Si$x_{i,j,k}=1$, la probabilité de réussite pour ce groupe est \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} Le problème est de maximiser $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$sujet à \ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {pour$s\in S$} \ tag2 \ end {align} La fonction objectif$(1)$est le score total attendu. Contrainte$(2)$ affecte chaque élève à exactement un groupe.
Expérimentation numérique pour les petits $n$ et uniformément distribués $p_i$confirme votre intuition de deux grandes et une petite probabilité par groupe. En fait, la plus petite probabilité apparaît avec les deux plus grandes, la suivante la plus petite avec les deux suivantes les plus grandes, et ainsi de suite. Par exemple, si les élèves sont réétiquetés par ordre croissant de$p_i$ (sans perte de généralité), alors $n=6$ produit des groupes $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Mise à jour : voici un petit contre-exemple avec$n=2$. Prendre$p=(0,0,0.1,0.6,0.8,0.8)$. Puis groupes$\{\{1,2,3\},\{4,5,6\}\}$ donner un score attendu de $0.832$, tandis que les groupes $\{\{1,5,6\},\{2,3,4\}\}$ donne un score attendu inférieur de $0.7$.
Voici un moyen de simplifier le problème. Laisser$p_i = x_i + 1/2$. Ensuite, nous souhaitons maximiser l'expression
\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*}
dans lequel seul le dernier terme dépend de la partition $T$. Nous avons donc simplifié le problème pour trouver le$T$ qui minimise la somme des produits de la $x$s dans chaque groupe de trois.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$