مسئله منشی

مسئله منشی

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

مقدمه

در اواخر دهه ۱۹۵۰ و اوایل دهه ۱۹۶۰ مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.

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

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

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

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

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

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

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

حل مسئله

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

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

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

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

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

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

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

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

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

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

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

کاربرد و مثال

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

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

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

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

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

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

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

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

منابع

• 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