Beklentiyi en üst düzeye çıkarmak için olasılık grubu öğrencileri
Verilen $3n$ insanlar $i^{\text{th}}$ kişi bir testi olasılıkla geçebilir $p_i$, şimdi onları bölmeniz gerekiyor $n$ her grubun sahip olduğu gruplar $3$insanlar. Bir grubun puanı eşittir$1$ en az iki kişi testi geçerse, $0$aksi takdirde. Toplam puan beklentisini en üst düzeye çıkarmak için onları nasıl gruplandırırsınız?
Bu problemi biraz düşündüm ve sezgisel olarak iki büyük grup oluşturmanın mantıklı olduğunu düşünüyorum. $p_i$ küçük bir $p_i$. Ayrıca, en uygun düzenlemede herhangi ikisini değiştirmeyi düşündüm$p_i$farklı gruplardan beklentiyi düşürmelidir. Öğrencilerin ikisini değiştirirken beklentideki farkı matematiksel olarak yazabilirim, ancak bu herhangi bir bariz sonuç vermiyor. Bir duvara çarptım.
Yanıtlar
Aşağıdaki set bölümleme formülasyonunu kullanarak sorunu tamsayı doğrusal programlama yoluyla çözebilirsiniz. İzin Vermek$S=\{1,\dots,3n\}$ öğrenci grubu olun ve $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$üç öğrenci kümesi olun. İçin$(i,j,k)\in T$ikili karar değişkenine izin ver $x_{i,j,k}$ üçlü olup olmadığını göster $(i,j,k)$bir gruba atanır. Eğer$x_{i,j,k}=1$, bu grup için geçme olasılığı \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} Sorun maksimize etmektir $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$konu \ başlamak {hizala} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {için$s\in S$} \ tag2 \ end {hizala} Amaç işlevi$(1)$beklenen toplam puandır. Kısıtlama$(2)$ her öğrenciyi tam olarak bir gruba atar.
Küçükler için sayısal deneyler $n$ ve tekdüze dağıtılmış $p_i$grup başına iki büyük ve bir küçük olasılık sezginizi doğrular. Aslında, en küçük olasılık en büyük iki olasılıkla, sonraki en küçük olasılık sonraki en büyük iki olasılıkla ortaya çıkar ve bu böyle devam eder. Örneğin, öğrenciler artan sırayla yeniden etiketlenirse$p_i$ (genelliği kaybetmeden), o zaman $n=6$ getiri grupları $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Güncelleme : burada küçük bir karşı örnek var$n=2$. Al$p=(0,0,0.1,0.6,0.8,0.8)$. Sonra gruplar$\{\{1,2,3\},\{4,5,6\}\}$ beklenen bir puan vermek $0.832$gruplar $\{\{1,5,6\},\{2,3,4\}\}$ daha küçük bir beklenen puan verir $0.7$.
İşte sorunu basitleştirmenin bir yolu. İzin Vermek$p_i = x_i + 1/2$. Sonra ifadeyi maksimize etmek istiyoruz
\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*}
sadece son terimin bölüme bağlı olduğu $T$. Bu yüzden sorunu bulmak için basitleştirdik$T$ Ürünlerin toplamını en aza indiren $x$her üç grupta s.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$