संभावना समूह के छात्रों को अपेक्षा को अधिकतम करने के लिए

Aug 18 2020

दिया हुआ $3n$ लोगों को कि $i^{\text{th}}$ व्यक्ति संभावना के साथ एक परीक्षा पास कर सकता है $p_i$, अब आप उन्हें विभाजित करने के लिए आवश्यक हैं $n$ प्रत्येक समूह के पास समूह $3$लोग। एक समूह का स्कोर बराबर होता है$1$ यदि कम से कम दो लोग परीक्षा पास करते हैं, $0$नई तो। कुल स्कोर की अपेक्षा को अधिकतम करने के लिए, आप उन्हें कैसे समूह बनाते हैं?

मैंने इस समस्या के बारे में थोड़ा सोचा है, और मुझे लगता है कि सहज रूप से यह दो बड़े समूह के लिए समझ में आता है $p_i$ एक छोटे के साथ $p_i$। इसके अलावा, मैंने इष्टतम व्यवस्था में, किसी भी दो को स्वैप करने के बारे में सोचा है$p_i$विभिन्न समूहों से उम्मीद कम करनी चाहिए। मैं छात्रों में से दो की अदला-बदली करते हुए गणितीय रूप से अपेक्षा में अंतर लिख सकता हूं, लेकिन यह कोई स्पष्ट परिणाम नहीं देता है। मैंने एक दीवार पर प्रहार किया है।

जवाब

2 RobPratt Aug 20 2020 at 08:56

आप निम्न सेट विभाजन विभाजन का उपयोग करके पूर्णांक रैखिक प्रोग्रामिंग के माध्यम से समस्या को हल कर सकते हैं। चलो$S=\{1,\dots,3n\}$ छात्रों का सेट हो, और जाने दो $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$छात्रों के तीनों का सेट हो। के लिये$(i,j,k)\in T$, बाइनरी निर्णय चर दें $x_{i,j,k}$ इंगित करें कि क्या ट्रिपल $(i,j,k)$एक समूह को सौंपा गया है। अगर$x_{i,j,k}=1$उस समूह के लिए पास संभावना है \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} समस्या को अधिकतम करना है $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$इस विषय के लिए \ begin {align} \ राशि _ {(i, j, k) \ टी में: \\ s \ में \ {i, j, k \}} x_ {i, j, k} और = 1 && \ पाठ {के लिये$s\in S$} \ tag2 \ end {संरेखित करें} उद्देश्य फ़ंक्शन$(1)$अपेक्षित कुल स्कोर है। बाधा$(2)$ प्रत्येक छात्र को ठीक एक समूह को सौंपता है।

छोटे के लिए संख्यात्मक प्रयोग $n$ और समान रूप से वितरित किया गया $p_i$प्रति समूह में दो बड़े और एक छोटे प्रायिकता के आपके अंतर्ज्ञान की पुष्टि करता है। वास्तव में, सबसे छोटी संभावना दो सबसे बड़ी के साथ दिखाई देती है, अगली दो सबसे बड़ी के साथ सबसे छोटी और इसी तरह। उदाहरण के लिए, यदि छात्रों को बढ़ते हुए क्रम में स्थानांतरित किया जाता है$p_i$ (सामान्यता की हानि के बिना), तब $n=6$ पैदावार समूह $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$

अद्यतन : यहाँ एक छोटा सा जाल है$n=2$। लेना$p=(0,0,0.1,0.6,0.8,0.8)$। फिर समूह$\{\{1,2,3\},\{4,5,6\}\}$ के एक अपेक्षित स्कोर उपज $0.832$, जबकि समूह $\{\{1,5,6\},\{2,3,4\}\}$ के एक छोटे से अपेक्षित स्कोर उपज $0.7$

OscarCunningham Oct 18 2020 at 20:07

यहाँ समस्या को आसान बनाने का एक तरीका है। चलो$p_i = x_i + 1/2$। तब हम अभिव्यक्ति को अधिकतम करने की इच्छा रखते हैं

\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*}

जिसमें केवल अंतिम शब्द विभाजन पर निर्भर करता है $T$। इसलिए हमने इस समस्या को आसान कर दिया है$T$ जो के उत्पादों के योग को कम करता है $x$तीन के प्रत्येक समूह में।

$$\sum_{(i,j,k)\in T}x_ix_jx_k$$