studenti del gruppo di probabilità per massimizzare le aspettative
Dato $3n$ persone che il $i^{\text{th}}$ persona può superare un test con probabilità $p_i$, ora devi dividerli in $n$ gruppi che ogni gruppo ha $3$persone. Il punteggio di un gruppo è uguale$1$ se almeno due persone superano il test, $0$altrimenti. Al fine di massimizzare l'aspettativa di punteggio totale, come li raggruppa?
Ho riflettuto un po 'su questo problema e penso che intuitivamente abbia senso raggrupparne due grandi $p_i$ con un piccolo $p_i$. Inoltre, ho pensato nella disposizione ottimale, scambiando due qualsiasi$p_i$provenienti da gruppi diversi dovrebbero abbassare le aspettative. Posso scrivere matematicamente la differenza di aspettativa quando scambio due studenti, ma non sembra dare alcun risultato ovvio. Ho sbattuto contro un muro.
Risposte
È possibile risolvere il problema tramite la programmazione lineare intera utilizzando la seguente formulazione di partizionamento dell'insieme. Permettere$S=\{1,\dots,3n\}$ sii l'insieme degli studenti e lascia $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$essere l'insieme delle triple di studenti. Per$(i,j,k)\in T$, lascia la variabile di decisione binaria $x_{i,j,k}$ indicare se tripla $(i,j,k)$è assegnato a un gruppo. Se$x_{i,j,k}=1$, la probabilità di passaggio per quel gruppo è \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} Il problema è massimizzare $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$soggetto a \ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {per$s\in S$} \ tag2 \ end {align} La funzione obiettivo$(1)$è il punteggio totale previsto. Vincolo$(2)$ assegna ogni studente a esattamente un gruppo.
Sperimentazione numerica per piccoli $n$ e uniformemente distribuito $p_i$conferma la tua intuizione di due probabilità grandi e una piccola per gruppo. In effetti, la probabilità più piccola appare con le due più grandi, la successiva più piccola con le due successive più grandi e così via. Ad esempio, se gli studenti vengono rietichettati in ordine crescente di$p_i$ (senza perdita di generalità), quindi $n=6$ produce gruppi $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Aggiornamento : ecco un piccolo controesempio con$n=2$. Prendere$p=(0,0,0.1,0.6,0.8,0.8)$. Quindi gruppi$\{\{1,2,3\},\{4,5,6\}\}$ produrre un punteggio previsto di $0.832$, mentre i gruppi $\{\{1,5,6\},\{2,3,4\}\}$ produrre un punteggio atteso inferiore di $0.7$.
Ecco un modo per semplificare il problema. Permettere$p_i = x_i + 1/2$. Quindi desideriamo massimizzare l'espressione
\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*}
in cui solo l'ultimo termine dipende dalla partizione $T$. Quindi abbiamo semplificato il problema per trovare il file$T$ che minimizza la somma dei prodotti del $x$s in ogni gruppo di tre.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$