مسئله منشی

در مسئله منشی مشکل، پیدا کردن نقطهٔ بهینه بین میزان اطلاعات دریافت شده و لحظهٔ مناسب برای استفاده از اطلاعات است.

مقدمه

در اواخر دهه 1950 و اوایل دهه 1960 مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.

این مسئله برای نخستین بار در ستون بازی های ریاضی در یک مجله آمریکایی مطرح شد.

بیان مسئله آسان و راه حل آن قابل توجه است.میان آمار دانان و احتمال دانان چندین نفر از جمله لیندلی ، داینکین[1] ، چو ، موگریتی ،روبینز،ساموئلز،گیلبرت و موستلر [2] این مسئله را اخذ کردند و توسعه دادند.بعد از آن مسئله منشی فراگیر و عمومی تر شد که اکنون می توان به آن عنوان یک گرایش درسی بین ریاضیات،احتمال و بهینه سازی داد.

شکل استاندارد مسئله منشی به اینگونه است که ${\displaystyle N}$ نفر برای منشی گری تقاضا می دهند و به طور تصادفی مرتب و یکی پس از دیگری مصاحبه می شوند. مصاحبه کننده در هر لحظه اطلاعات متقاضی های قبلی و متقاضی فعلی را دارد و باید در همان لحظه تصمیم بر انتخاب یا رد مصاحبه شونده بگیرد.

مصاحبه کننده امکان انتخاب کاندیدی که رد کرده است را ندارد و مصاحبه تا آن جایی ادامه می یابد که بهترین منشی را انتخاب کند.هدف این مسئله بالا بردن احتمال انتخاب بهترین متقاضی است.

صورت دقیق مسئله

بیان مسئله منشی بسیار متنوع است امّا ساده ترین شکل آن به شرح زیر است:

1. تنها یک نفر برای موقعیت منشی نیاز است.
2. تعداد متقاضیان مشخص و برابر ${\displaystyle N}$ است.
3. متقاضیان که به شکل تصادفی مرتب شده‌اند ، به ترتیب مصاحبه می شوند.
4. وضعیت متقاضیان بدین گونه است که می توان آن ها را از بدترین به بهترین رده بندی کرد و تصمیم گیری در هر مرحله بر مبنای رده بندی متقاضیان قبلی است که رد شده اند.
5. متقاضی که رد شده است دوباره فراخوانده نمی‌شود.
6. مصاحبه کننده تنها در حالتی که بهترین منشی را انتخاب کند راضی می شود.

حل مسئله

سیاست بهینه برای این مسئله ، قانون توقف است. بنابراین مصاحبه کننده ، ${\displaystyle r-1}$ نفر اولِ متقاضیان را رد می کند (در حالی که متقاضی ${\displaystyle M}$ ام بهترین بین ${\displaystyle r-1}$ نفری باشد که رد شده اند) و پس از آن هر متقاضی ای که بهتر از متقاضی ${\displaystyle M}$ ام بود را انتخاب میکند . احتمال انتخاب بهترین منشی به شکل زیر است:

متقاضی i ام انتخاب شود ${\displaystyle A:}$

متقاضی i ام بهترین باشد ${\displaystyle B:}$

بهترین متقاضی بین ${\displaystyle i-1}$ نفر اول ، از میان ${\displaystyle r-1}$ نفر اول باشد ${\displaystyle C:}$

=${\textstyle P(r)=\sum _{i=1}^{n}p(A\cap B)}$

=${\textstyle \sum _{i=1}^{n}p(A\mid B)\times p(B)}$

=[${\displaystyle [\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}p(C\mid B)]\times {\tfrac {1}{n}}}$

${\displaystyle {\tfrac {r-1}{n}}\sum _{i=r}^{n}\times {\tfrac {1}{i-1}}}$=${\displaystyle \sum _{i=r}^{n}{\tfrac {r-1}{n-1}}\times {\tfrac {1}{n}}}$

${\displaystyle n}$ را به بی نهایت میل می دهیم و ${\displaystyle x}$ را حد${\displaystyle {\tfrac {r}{n}}}$ میگیریم و ${\displaystyle t}$ را ${\displaystyle {\tfrac {i}{n}}}$ و ${\displaystyle dt}$ را ${\displaystyle {\tfrac {1}{n}}}$میگیریم و مجموع به انتگرال تبدیل می شود:

${\displaystyle P(x)=x\int _{x}^{1}{{\tfrac {1}{t}}dt}=-xln(x)}$

با صفر گذاشتن مشتق ${\displaystyle P(x)}$، مقدار بهینه ${\displaystyle x}$را برابر ${\displaystyle {\tfrac {1}{e}}}$در می آوریم.با افزایش ${\displaystyle n}$ ، برش مطلوب به ${\displaystyle {\tfrac {n}{e}}}$میل می کند و احتمال انتخاب بهترین منشی تقریباً برابر با ${\displaystyle {\tfrac {1}{e}}}$است.

کاربرد و مثال

• می توان در استخدام برای هر گونه شغلی نه تنها منشی گری از آن استفاده نمود.
• در زمینه خرید خانه توجه به این مسئله اهمیت زیادی دارد.[3]
• برعکس استخدام، می توان از این مسئله برای انتخاب شغل استفاده کرد.
• خریدن یک کالا یا منتظر تخفیف بودن
• مزایده در بازار

مسئله منشی زیر چتر مسائل توقف بهینه برای تعداد زیادی از شرایط دنیای واقعی اعمال می شود، در صورتی که دو شرط اولیه زیر را داشته باشند:

1. اقلام ، داده ها یا متقاضیان به طور پیوسته و پشت سر هم وارد می شوند.
2. هر مورد مستقل هست و یکسان توزیع شده اند (${\displaystyle i.i.d}$).

مثال دیگر می تواند مسئله دزدی باشد، بدین گونه که دزد، برنامه سرقت های سریالی دارد و اگر دستگیر شود، بازنشسته خواهد شد. او می خواهد تا قبل از دستگیری بازنشسته شود. امّا می خواهد بداند بعد از چند سرقت باید بازنشسته شود.

و مثال دیگر سفارش گرفتن از مشتریان توسط یک شرکت که منابع محدودی دارد است.[4]

جستارهای وابسته

این مسئله برای N نامشخص نیز مطرح می شود.

اگر تعداد نامحدودی از «متقاضیان» وجود داشته باشد، همیشه بهتر است منتظر بمانیم تا بتوانیم یک مورد بهتر را پیدا کنیم. در این موارد باید تعداد کاندیدا ها تخمین زده شود و سپس بر ${\displaystyle e}$ تقسیم شود. با مطالعه متقاضیان به طور تقریبی می توان به توزیع آنان پی برد و سپس تصمیم بهتری گرفت.[5]

منابع

1. "Eugene Dynkin". Wikipedia. 2018-08-09.
2. "Frederick Mosteller". Wikipedia. 2018-09-19.
3. «How I used mathematics to choose my next apartment – The Reflective Educator». davidwees.com (به انگلیسی). دریافت‌شده در ۲۰۱۸-۱۰-۲۸.
4. "(PDF) A Survey of Secretary Problem and its Extensions". ResearchGate. Retrieved 2018-12-03.
5. «Secretary problem for unknown n?». Mathematics Stack Exchange. دریافت‌شده در ۲۰۱۸-۱۲-۰۳.

• https://projecteuclid.org/download/pdf_1/euclid.ss/1177012493
  • http://rs.io/the-secretary-problem-explained-dating/http://rs.io/the-secretary-problem-explained-dating/
  • https://www.jstor.org/stable/3213519?seq=1#page_scanhttp://rs.io/the-secretary-problem-explained-dating/_tab_contents