（应用数学专业论文）最优或次优组面试问题的最佳划分选择策略.pdf

主! b 盘鲎墅生篮趋圭描蠡最优或次优组面试问题的最佳划分选择策略摘要秘书问题研究的是报酬函数仅与所选项的秩相关而与其实际值无关的序贯观察和选择问题。它属于概率论与最优化理论的一个交叉研究领域，是最优停止理论中的一个著名问题。本文主要讨论秘书问题的变形“组面试问题”在目标是选择最优或次优时的最佳选择策略( 停止规则) ，采用的主要方法是后退归纳法和边界阶段方法。在通过边界阶段方法得到的最优组面试问题的最佳选择策略基础上，第二章给出了允许重排序时获得最佳排序的定理。第三章重点讨论最优或次优组面试问题的最佳划分选择策略，并得到了确定两个边界阶段的最优不等式。关键词；组面试问题；边界阶段方法；后退归纳法；最佳排序；秘书问题i i 壅韭盘生塑生焦监塞! 盟! !o p t i m a lp a r t i t i o n i n go fg r o u p si ns e l e c t i n gt h eb e s to rt h es e c o n db e s tc h o i c ea b s t r a c ts e c r e t a r yp r o b l e m sr e f e rt ot h es e q u e n t i a lo b s e r v a t i o n sa n ds e l e c t i o np r o b l e m si nw h i c ht h ep a y o f fd e p e n d so nt h eo b s e r v a t i o n so n l yt h r o u g ht h e i rr e l a t i v er a n k sa n dn o to t h e r w i s eo nt h e i ra c t u a lv a l u e s a saf a m o u sp r o b l e mo fo p t i m a ls t o p p i n gt h e o r y ，i tc o n s t i t u t e saf i e l do fs t u d yw i t h i np r o b a b i l i t y - o p t i m i z a t i o n t h i sa r t i c l ed e a l sw i t han a t u r a lv a r i a t i o no ft h ec l a s s i c a ls e c r e t a r yp r o b l e mc a l l e dt h eg r o u pi n t e r v i e wp r o b l e m ，i nw h i c he a c hg r o u pc o n t a i n ss e v e r a la l t e r n a t i v e sa n de a c hg r o u po fa l t e r n a t i v e si sp r e s e n t e da n de v a l u a t e ds e q u e n t i a l l yo v e rt i m e i nt h es e c o n dc h a p t e rw ed e v e l o pas i m p l eh e u r i s t i cp r o c e d u r et ot h eo r d e r i n gp r o b l e mo ft h eg r o u pi n t e r v i e wp r o b l e mi ns e l e c t i n gt h eb e s tc h o i c e i nt h et h i r dc h a p t e rw ed e r i v et h eo p t i m a ls e l e c t i o nr u l ec a l l e dt h eo p t i m a lp a r t i t i o n i n gs t r a t e g yf o rt h eg r o u pi n t e r v i e wp r o b l e mi ns e l e c t i n gt h eb e s to rt h es e c o n db e s tc h o i c eb yb a c k w a r di n d u c t i o na n db o u n d a r ys t a g em e t h o d w eo b t a i nt h eo p t i m a li n e q u a l i t i e so ft h et w ob o u n d a r ys t a g ek ：a n dk ：k e y w o r d s ：g r o u pi n t e r v i e wp r o b l e m ；b o u n d a r ys t a g em e t h o d ；b a c k w a r di n d u c t i o no p t i m a lo r d e r i n g ；s e c r e t a r yp r o b l e mi i i 独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：交、1 吹日期：2 口o 笨孑目5 a学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。( 如作者和导师不同意网上交流，请在下方签名：否则视为同意。)学位论文作者签名：导师签名；签字日期：签字日期：东北大学硕士学位论文第一章绪论1 1 引言第一章绪论最优停止理论是概率论中一个具有很强应用背景的领域，它的产生可朔源很早，但在6 0 年代以后取得主要发展。最优停止理论处理的问题是基于顺序观察到的一列随机变量选择一个时间采取一定行动以便平均收益最大或平均损失最小，即研究何时停止最为有利。秘书问题是最优停止理论中个著名问题，它在最优停止理论的发展中曾起过重要的作用。一般认为秘书问题的最初文献是出现在1 9 6 0 年2 月s c i e n t i f i ca m e r i c a n 的m a r t i ng a r d e n e r sm a t h e m a t i c a lg a m e s 中的g o o g o l n 题。1 9 6 1 年d v l i n d l e y 在文献 9 】最早发表了对该问题的解。秘书问题中包含了序贯的成分，可以看作是类确定何时停止最优的问题。在c h o w ，r o b b i n s ，a n ds i e g m u n d 合著的文献 1 6 与s h i r y a y e v 的( ( o p t i m a ls t o p p i n gr u l e s ) )两本著作中将秘书问题作为最优停止问题研究。1 9 8 9 年f e r g u s o n 在文献 6 中将秘书问题定义为：报酬函数仅与所选项的秩相关而与其实际值无关的序贯观察和选择问题。此后，统计学家和应用数学家通过许多不同的方法对秘书问题进行推广和变形，使之镊到广大的发展空间，属于概率论与最优化理论的一个交叉研究领域。1 2 经典秘书问题的提出及数学模型秘书问题中，已知有个随机到来的应聘者申请一个秘书职位。假设这个应聘者优劣的名次有一个客观的评价，设为1 , 2 ，n 。其中1 为最优者，为最劣者。决策人每次面试一名应聘者，面试后决定是否录用，如果录用当前应聘者则停止面试，否则面试下一个。每次面试时，决策人只知道当前人的相对名次，而不知道其绝对名次。假定每个当时不被录用的人不能再召回。现在的闯题是决策人在何时停止他的面试( 即录用当前的应聘者) 是最好的。采用下面的标准：使录用到最优应聘者的概率最大。这种标准是最早被提出和研究的，故称为经典秘书问题，又由于在这一标准下只希望录用到最优的应聘者，有时也称为最优选择问题。东北大学硕士学位论文第一章绪论在一定假设条件下，可以建立秘书问题的数学模型。1 9 8 9 年f e r g u s o nt s 将经典秘书问题归结为如下五条基本假设：1 )有个应聘者申请一个职位，其中已知：2 )应聘者随机的被依次面试，每次一人，j v ，种顺序机会相等；3 )这个应聘者优劣的名次有一个客观的评价：1 ，2 ，n ( 其中1 为最优者，为最劣者) 。每次面试决策人只知道当前应聘者的相对名次，不知道其绝对名次，面试后决定是否录用，如果录用当前人则停止面试，否则面试下一个：4 )假定每个当时不被录用的应聘者不能再召回；5 )目标是选出最优的应聘者。在以上假设下，研究何时选择个候选人( 相对名次最优的应聘者) 并停止面试最好。1 3 常用求解方法d v l i n d l e y 于1 9 6 1 年发表了对该问题的解，得到如下形式的选择策略：不管相对名次如何，对前，一1 个应聘者只面试不录用，然后录用下一个相对最优的应聘者( 如果有的话) 。其中m 僻击s t 在此策略下，p ( 录用到最优应聘者) = 寻砉丢i( 1 1 )当n 寸。时，有，。盟已_ p ( 录用到最优应聘者) 。一1( 1 2 )( 1 3 )东北大学硕士学位论文第一章绪论在讨论秘书问题及其各种变形时，主要的研究分析方法有两种类型。第一种重要方法是后退归纳法( 动态靓划原则) 。这一方法是1 9 6 1 年l i n d l e y 在文献【9 】和1 9 6 6 年g i l b e r ta n dm o s t e l l e r 在文献 1 8 中开始使用的。另外，在c h o w ，r o b b i n s ，a n ds i e g m u n d 的著作 1 6 中也有具体介绍。这类方法应用动态规划的思想推导出递推方程，然后分析这些方程。第二种方法，最早在1 9 6 3 年由d y n k i n 提出使用，他将候选人( 相对最优的应聘者) 到来的时间序列看作m a r k o v 链，应用m a r k o v 停时理论得到结果。这个问题研究的是停时理论中的单调情形。1 9 7 1 年c h o w ，r o h b i n s ，a n d s i e g m u n d 提出的在当前停止比下一阶段停止好时停止所谓“o n e - s t a g e 1 0 0 ka h e a d ”规则是最优且理想的形式。1 4 秘书问题的推广变形在决策问题的应用上发现，经典秘书问题的假设要求严格，不能很好地适合现实生活。所以很多人设法将其中某一条或某几条假设予以放宽，从而得到更为实用的数学模型。这些问题可以看成“秘书问题”的推广变形。下面根据新模型对原模型基本假设所做的改动分类介绍。1 4 1 应聘人数未知改变假设1 ) ，将应聘总人数视为服从某一己知分布的随机变量。1 9 7 2 年p r e s m a na n ds o n i n 在文献 2 5 】中研究了这类问题，主要集中在均匀分布的情况。1 9 8 2 年a b d e l h a m i d ，b a t h e ra n d t m s t m m 在文献【2 6 】考虑了这类问题停止规则的可接受性，随后1 9 8 3 年j d p e t r u c c e l l i 在文献 2 7 】给出了此问题的最佳规则是阀规则的条件。1 4 2 组面试问题假设2 ) 中每次面试一人，这在实际应用中有定的局限性，因为可能会出现每次不只面试一人的情况。1 9 9 3 年c h u ne t a l ，在文献 4 1 q b 提出了所谓“组面试问题”，此时应聘者分成若干个不同的组，面试时是随机到来的一组，各组可能性相同。文章通过m a r k o v 决策过程的方法推导出最优选择问题( 即目标是使选择最优应聘者的概率最大的问题) 的选择策略。1 9 9 6 年c h u ne t a l 在文献【5 】中又考虑了平均名次问题( 即目标是使选中应聘者的平均名次最小的闫题) 。3 东北大学硕士学位论文第一章绪论1 4 3 加权秘书问题假设2 ) 中，每次面试一人，种顺序可能性相等，即对每个应聘者一视同仁，假定每个应聘者成为最优的可能性是相同的。但在现实生活中，如果事先可以了解到应聘者的一些情况，根据这些情况可以对每个应聘者赋以相应的一个权，将每个应聘者成为最优的可能性视为有区别的。1 9 9 6 年y o u n g h a k c h u n 在文献【2 】中提出这个问题并得至选择策略。1 4 4 可召回秘书问题假设4 ) 中应聘者一旦被拒绝将不能召回，而现实生活中有些应聘者可能被召圈。另外，还可能会出现应聘者拒聘的情况。现放宽假设4 ) 为允许以一定的概率将过去拒绝过的应聘人召回，关于这个问题的最早文献是1 9 7 7 年r u b i na n ds a m u e l s 的文献 2 8 和1 9 7 3 年b e n i a m i na n dg o l d y s 的文献 2 9 。在这两篇论文中假定前1 步或前1 步至前k 步的召回概率为1 ，其它为0 。1 9 7 4 年y a n g 在文献 3 0 研究了当前人不拒聘且每位应聘者一经拒绝就再不能召回的情况。1 9 7 5 年s m i t ha n dd e e l y 在文献 3 1 考虑了可以将观察过的后皿个应聘者召回的情况。1 9 8 2 年p e t r u c c e l l i 在文献 3 2 将这一问题推广到全信息情况。1 4 5 广义秘书问题将假设7 ) 推广，设决策人录用每个应聘者获得的效用为应聘者绝对名次的函数u ( a ) ，其中口为应聘者的绝对名次。这里假定u ( 1 ) u ( 2 ) u ( ) 是合理的。经典秘书问题可以看作是u o ) = l ，u ( 2 ) = = u ( ) = 0 时的特殊情况。东北大学硕士学位论文第一章绪论1 5 本文主要研究内容前面介绍了“秘书问题”的几种推广变形，这些问题都是将经典秘书问题数学模型基本假设中的一条改变或放宽，使之更适合实际应用的需要。最近的研究表现出的趋势是不仅局限于改变基本假设中某一条，而是要将某两条甚至更多条加以修改，得到与现实生活更接近的数学模型，著找到形式篱单。易操作的选择策略。2 0 0 1 年y o u n gh c h u n 在文献【l 】中提出用边界阶段方法( b o u n d a r ys t a g em e t h o d )研究一般效用函数下的组面试问题，并以最优选择问题为例推导出一种简单的称为最佳划分选择策略的选择规则。这种最佳划分选择策略将全部组分为两个互不相交的集合，分别称为“学习集”己和“行动集”“，决策人对“学习集”工中的所有元素只面试不录用，然后录用“行动集”a 中首次得到的相对最优的应聘者。本文将应用边界阶段方法讨论目标是选择最优或次优的组面试问题，得到该问题的一种较简单的最佳划分选择策略。另外，还在允许调整面试顺序的情况下，得到了在最优组面试问题中如何重新安排面试顺序以使录用到的应聘者是最优的概率最大的定理。5 东北大学硕士学位论文g - 章最优组面试问题的最佳顺序安排第二章最优组面试问题的最佳顺序安排2 1 基本概念组面试问题中当目标是使录用到最优应聘者的概率最大时，称为最优组面试问题。事实上，在最优组面试问题中，决策人只对选出最优的应聘者满意，并希望该概率最大。所以，最优组面试问题可以看做是效用函数为u ( 1 ) = 1 ，u ( 2 ) 一u ( m 。) = 0的情况。y o u n gh c h u n 在文献【1 】提出了一般效用函数组面试问题的边界阶段方法( b o u n d a r ys t a g em e t h o d ) 并对最优组面试问题提出最佳划分选择策略。我们在此基础上采用启发式方法，得到了最佳排序定理，考虑当允许决策人调整面试顺序时，如何重新安排面试顺序最好。下面先介绍我们在闯题中将要用到的一些符号及其含义。2 1 1 符号说明这里，我们把第j 组被面试称为第k 阶段。令g 。：第t 个被面试的组m t ：g 中包含的人数g = 卸，m ：，m 。溶示有n 个组被依次面试的组面试问题埘名= m i + + + 拱，( i = 1 , 2 ，坊r ：第阶段某一应聘者的相对名次( 即他在m 。中的秩)口：第n n 某- - f 2 聘者的绝对名次( 即他在m 。中的秩)u ( 口) ：选择绝对名次为口的应聘者获得的效用值，其中d = 1 , 2 ，m 。假定v o ) 是口的一个单调非增的函数，即u ( 1 ) u ( 2 ) - u ( m )2 1 2 边界阶段方法在一般效用函数组面试问题中，每个阶段决策人只能采取两种行动之一：( 1 ) 录用当前组中最优应聘者，结束面试；( 2 ) 拒绝当前组，继续面试下一组。东北大学硕士学位论文第二章最优组面试问题的最佳顺序安排基于决策人采取每种行动获得的平均效用，引进下面的两个符号：e u ( r ，k ) 表示在第k 阶段选择相对名次为r 的应聘者，停止面试获得的平均效用，e 玑( 七) 表示在第k 阶段不选择当前组中任何应聘者，继续面试获得的平均效用，如果e u , ( ，七) 占玑( 后) ，则应该停止面试；如果e u , ( ，k ) e u ，( ，+ l ，| 】 ) 及e u ，( ，七) e u ；p ，七+ 1 ) 。即e 玑( r ，七) 随，增大而减小，随k 增大而增大。弓l 理2 【l j ：e u 。( 七) e 玑( 七+ 1 ) ( k = 1 , 2 ，一， 一1 ) 。即e u c ( 七) 随k 增大而非严格单调减少。引理3 0 1 ：若烈l ( r ，) s e u 。( 幻，则烈丘( r ，k 1 ) e 玑( 七+ 1 ) 。此引理表明：如果当前阶段选择相对名次为，的应聘者是值得的，段选择同样名次的应聘者也是值得的。那么在前一阶那么在下一阶综上引理，对每个，存在阶段边界k + p ) ，在前1 , 2 ，k ( ，) 一l 阶段录用相对名次为r 的应聘者都是不值得的，而在后七+ ( r ) k ( ，) + l ，一阶段录用相对名次为，的应聘者都是值得的。即对于r 来说，七( r ) 是使得下列两个不等式同时成立的最小的愈点玑 ，膏 e u 。斟( 2 4 )e 以 ，k t 2 ，2 0 0 1 年c h u n 在o p t i m a lp a r t i t i o n 吨o fg r o u p si ns e l e c t i n gt h eb e s tc h o i c e 【j 】中采用边界阶段方法对最优组面试问题这种特殊效用函数，得到最佳划分选择策略。这一策略将全部面试组划分成两个部分：三和爿，分别称为“学习集”和“行动集”。对于“学习集”上中的应聘者只面试不录用，然后在“行动集”一中录用第一个相对最优的应聘者。将最优组面试问题的效用函数，代入式( 2 2 ) 中，得耻脍，川，舻坨，泣，0 ，2 ，显然，e u 。( r ，) 随孟增加而增加。在最后阶段甩，五玑( 玎) = 0于是，f 1 ，= 1 ，脚、，帕2 o ，醌( 2 8 )在中问阶段k ， = 1 , 2 ，n - - i )e u 。( ，的：m a ) ( 忸以( ，d 寥虬 ) 】，= 1 ，( 2 9 ) e u , ( i ) r 2 ，东北大学硕士学位论文第二章最优组面试问题的最佳顺序安排由式( 2 3 ) 和式( 2 9 ) ，在第k 阶段继续的平均效用e u 。( | 】 ) 可表示为： f 。“e u 。( 七) = e u ( ，七+ 1 )r 司( m k + - - - r )= 州瓦m k + l + e u ( 川) 鼍( 2 1 。)从式( 2 7 ) 看出，e u , ( ，忌) 只有当，= 1 时才是非零值，所以只需定义一个边界阶段七= 七+ ( r = 1 ) 。记三- - 0 ，2 ，七一1 ) 是“学习集”，爿= 传，七+ l ，一) 是“行动集”。这样，最优组面试问题的最佳选择策略的关键就是确定i 。引理5 1 1 ：对任何i a ，占v o ( h ，2 等薹嚣基于引理5 ，下面的定理2 给出确定的最优不等式。定理2 【1 】：( j 最优不等式)七是七，如果_ j 满足下面的不等式：篇m j 垭喜。彘篇m ，1 盎岛j l 一l可以定义= 幽艟老，( 2 1 1 )( 2 1 2 )2 3 最佳排序定理及其证明根据动态规划的最优原则( t h ep r i n c i p l eo f o p t i m a l i t y ) ，按照最佳划分选择策略在最优组面试问题中决策人得到的平均效用是层u ( 1 ，1 ) 。在最佳划分选择策略下，有e u + ( 1 ，1 ) = e u c ( 1 ) = e u 。( 2 ) = 一e 一1 )- l m东北大学硕士学位论文第二章最优组面试问题的最佳顺序安排故决策入所录用的应聘者是绝对最优的概率：稍= 鲁妊眨现在考虑一个有趣的决策问题。在组面试问题中。如果允许决策人调整应聘者面试的顺序，我们讨论如何重新安排能使录取到的应聘者是最优的概率最大。也就是要选出使得决策人录用到最优应聘者的概率最大的那个顺序，我们称之为最佳排序问题。首先，完全枚举法可以用来决定最佳排序策略。即对每种顺序计算出式( 2 1 3 )中的成功概率，然后选择出其中最大的那个。显然，这种方法当问题的规模相对较大时将难以处理，因为刀个不同应聘组的总的可能顺序共有h ，种。( 例如n = l o 时，n ! 就要大于3 6 + 1 0 6 ) 。其次，可以把最优排序问题作为一个非线性任务安排问题处理。然丽，在最优排序问题中应聘组数量的增加会大量的增加了变量的数目和限制条件，这提高了处理问题的难度。在动态规划中这类问题指t h ec u r s eo fd i m e n s i o n a l i t y ( b e l i m a na n dd r e y f u s1 9 6 2 ) 。最后，换个角度，在这里我们提出一种简单的启发式步骤。基于下面证明的定理，决策人应采用最佳划分选择策略，在面试而不录用“学习集”上中的应聘组后，根据各组所含有的应聘者的数目r r ：的大小的非增顺序，重新安排“行动集”a 中应聘组的面试顺序，也就是先面试含有人数多的组。定理3 ：如果对f a ，m 。m 。，那么a 中的顺序是最佳的。证明：( 反证法)假设m ， m ，f a由式( 2 1 3 ) ，得到此时该序列的成功概率为：2 等喜彘2 可m k1 ，1 岔i - 1 瓦m j + 瓦m i 十瓦m t + 1 + 毫老汜也l 怠鸠一im ，lm ，。+ 角m ，_ lf“查i ! 垄生塑主兰堡垒查苎三主墨垡丝重苎璺塑堂皇垡塑堑兰：塑lm ，= 等喜云=萌m倍t-1彘m+石mi+l+菇蠹十角mjmz - - , mm mm j 一_ 。i ，hf _ lj - 1 + m “l 篇一i j郴m 鼬) = 等脍+ 瓦m 而i 一瓦m i 一东= 生生土j 竺出二竺! +翌!一竺出_ 二二堕一! l lm im hm f - 1 + m f + lm f _ 1 + m ，m h + ，j= 等卜- 吨，亡一瓦m c 瓦杀一瓦) = 等 器焉一蒜m 1m ，( m 一，l f )：一- 。一坂( 蟛一】+ m ，) 玎1 上m ；_ 1 + m j + j )：! ! 量翌f ! 竺! ! j 二竺! !竺! ! ! 厶( m 。- 1 + m f ) m 。_ ( 峨q + 卅“1 ) 0从而，在i 彳中当m ， 1 ：, - 0 6 1 1 = 若所以k = 3 。面试序列阶段分成两个互不相交的部分：三= 1 ，2 和爿= 3 ，4 ，5 ) 最佳选择策略是：从第三个阶段开始录用最先获得的相对名次最优的。并且获胜概率石( 3 ) 一面4 【- 2 + 吾+ 争= 0 4 4 “现在，允许我们重新安排面试的顺序，根据定理获胜概率会增加。下表列出“行动集”a 中组不同顺序时的获胜概率。o r d e r i n gi naw i n n i n gp r o b a b i l i t y 3 ，4 ，5 ) 3 ，5 ，4 ) 4 ，3 ，5 4 ，5 ，3 ) 5 ，3 ，4 ) 5 ，4 ，3 )o 4 4 4 40 4 3 8 10 4 5 8 70 4 5 7 10 4 3 1 40 4 4 0 0从上表我们可验证，“行动集”a 中的顺序当按照阶段 4 ，3 ，5 ) 即按照a 中各组所含的应聘人数大小的非增顺序排列时，可获得最大的成功概率0 4 5 8 7 1 3 。查些查苎堡主茎堡垒墨釜三主墨垡壅奎垡塾重垡塑壅箜壅堡型坌鳖i 垦堡一第三章最优或次优组面试问题的最佳划分选择策略现在把组面试问题中决策人的要求放宽，如果能录用到最优( 绝对名次第一) 或次优( 绝对名次第二) 的应聘者都认为是满意的，我们把这样的问题称为最优或次优组面试问题。本章主要讨论最优或次优组面试问题的最佳选择策略，这里决策人对能录用所有应聘者中绝对名次为第一或第二的应聘者都是满意的，所以可以把效用函数取成u ( 1 ) 一u ( 2 ) ；l ，u ( 3 ) - u ( 4 ) 一一u 似) 一0 。采用边界阶段方法- 我们得到这种情况下具体的最佳划分选择策略。3 1 重要结果最优或次优组面试问题也可以看作是一般效用函数组面试问题的另一种特殊情况。这时效用函数为：u ( n ) _ j 1 4 主2 ，( 3 1 )【0 ，a 2 ，由于对一般效用函数组面试问题有如下结果【4 le u , ( r 肋。虬塞”u 。r 一1 2 ，m i 1 + 1( 2 2 )剐哺1 枷智m 如加，汜占以钟，一警1 占u p ，七+ ，1 彳；三掣七al z ，朋一，c 2 3 ，l 掰m ，- 1 4 -东北大学硕士学位论文第三章最优或次优组面试问题的最佳划分选择策略刚m = 筹+ 黼= 篙篙学五乩( 2 ，| | ) =于是，e 仉( r ，k ) =m ( m k 一1 )( m 。一1 )帆( 2 以一m 。一1 )帆( 一1 )m k o 以一1 )m 。哪。一1 ) o ，r = 1 ，r = 2 ，( t = 1 , 2 ，0r 2 可以验证e 以( 尼) 随，增加而减少，随k 增加而增加。在最后阶段行，有e u c ( n ) = 0于是，f 1 ，r = 1 或2厕_ ，班 o ， 2在中间阶段k ，= 1 , 2 ，刀一1 )e u ( r ，k ) =m 戕忙以( 1 ，i ) ，占玑( 幻 r = 1 ，m a x e u ( 2 ，七) ，五u ( 七) ) ，= 2 ，e 玑( t ) r 2 ，由式( 2 3 ) 和式( 3 4 ) ，得在第k 阶段继续的平均效用用l ( 七) 可表示为：m + le u 。( i ) = e u ( ，七+ 1 )1 5 ( 3 2 )( 3 3 )( 3 4 )查! ! 垄兰堡主兰堡堕圭墨三主垦堡皇鉴些塑重曼璺垄整垦壁竺丝望望至j 垦! l划( 1 川) 嚣+ e u ( 2 n 1 ) 面淼倒融+ 1 ) 瓣m , ( m k - i )( 3 5 )从式( 3 2 ) 看出e u , ( r ，动只有当r = l 或，= 2 时才是非零值，所以只需要定义两个边界阶段片= 七p = 1 ) 和砖= 七( r = 2 ) 根据定理1 ，日e 。记三： l ，2 ，日一1 是学习集，4 = 妊0 七：+ 1 ，一l 是第一行动集以= 救，+ 1 ，押j 是第二行动集a这样，最优或次优组面试问题的最佳选择策略的关键就是确定与耳。下面的两节将讨论如何确定最优或次优组面试问题中的和片。3 2 的确定本节在3 1 节基础上，利用后退归纳法，得到确定e 的最优不等式。引理6 ：对任何七a 2 ，有e u c ”驴黼薹瓮瓮等 a ，证明：采用关于七的后退归纳法。首先，七= 玎时，此引理正确。由式( 3 3 ) 得e u + ( 1 ，竹) = 1和e u ( 2 ，拧) = 1由式( 3 5 ) 得e u o ( 川，= 薏+ 赢= 鼍筹铲其次，假设k = s + 1 时，此引理正确。下面去证明k = j 时，此引理仍正确。根据式( 3 2 ) 中e u ( ，j ) 的性质：e u ，( ，i ) 随r 的增大而减小。1 昏东北大学硕士学位论文第三章最优或次优组面试问题的最佳划分选择策略在中间阶段k ，( 七= 1 , 2 ，n 一1 ) 应有e u s ( 1 ，k ) e u s ( 2 ，七)根据对第二行动集- 4 2 的定义，对j i t ：，有e 虬( 2 ，s ) e 以( s )从而，当s a ，时，有e u s ( 1 ，s ) e u ，( 2 ，s ) e 玑( s )故有e u ( 1 ，s ) = e u 。( 1 ，j )e u ( 2 ，s ) = e 玑( 2 ，s )于是，将式( 3 7 ) 和式( 3 8 ) 代人式( 3 5 ) ，并用s 1 替换岛得e 珥。一1 ) = e u 0 ，s ) 埘m s ，十e 矿( 乏曲j 考i 老 兰万+ e 配粼钉吣，老柑u s ( 2 神素+ 酬曲粼：丝! ! 鉴二丝= 1 2眠一1 )旦lj m s ( m 。一1 ) 胁；m ，一1m ，m 。瞅n 一1 ) m ，擞。- i )( 3 7 )( 3 ，8 )“啪) 黼= 篙羟掣+ 而m a m 丽_ i 啦黼1帆( m 。一1 )坂( 帆一1 ) 。“竹。( m 一)：m , ( 2 m - m , + m , q - 1 ) _m 。( 鸩一1 )砌u o ( s ，粼。笺m 擀帆黼1。( m 。一1 )“。m ，( m ，一)经过归纳，得到占以2 糍措喜。丽m j ( 2 m , , - m j - 1 )将式( 3 1 0 ) 代入式( 3 9 ) 中，得到e v ( s 1 ) ：竺i 呈：鱼二! ! 二堕+ e u o ) 兰生= 生= l 二坠。m n m ，- 1 )“、m s ( m ，一吣( 3 9 )( 3 1 0 )：m , ( 2 m - m , - 1 ) + 丝! f 丝 ! ! 争m j ( 2 m , - m j - 1 ) 1 墼= d 丝型二坠托( 一1 )螈( 峨一1 ) 盘一m j 一，( m j 。一1 ) 。鸩( m 一1 )1 7 查些垄兰堡主望堡垒圭箜三主墨堡垒查垡塾墨塑坚墨塑垦堡型坌塑簦!m , ( 2 m - m , - 1 ) 1 m 。( 厶一1 )m ，l ( m ，i 一1 ) 坍，( 2 m 。一肌一1 )a 丸( 螈- 1 ) l “- j + lm j l ( 影川一1 )：丝d 坐塑二! 副塾! ! 丝二坠二1 2 + 争竺! 型! 二竺，二坚峨。一1 ) l 坂一，一1 ) 二一lm j _ - ( 呜一，一1 ) jm ，1 ( m 。一l 一1 ) m ( 2 m 。一研，一1 )帆( m 。一1 ) 舞时，l ( 膨j _ l 一1 )从而，我们所需要的结果得证。定理4 ；( 最优不等式)k 是，如果k 满足下面的不等式：证明：k ：是使e u ，( 2 ，七) e u o ( j ) 成立的最小的“于是，对七= ，有e 玑( 2 ，) e u c ( e )对k = 一1 ，有e u ，( 2 ，一1 ) 丝! 竺二! ! 争m ：( 2 m , , - m j - ! )一心( 鸩一1 ) 盘t 屿一，( 鸠1 _ 1 )= e u c ( 麓)即。亡掰，( 2 辑一所，一1 )l y ：尘! 竺竺! ：竺：!基，鸩一i ( 鸩r1 )同理，由式( 3 1 3 ) ，得- 1 8 -( 3 1 1 )( 3 1 2 )( 3 1 3 )( 3 1 4 ) | d竺一。瓮m等案东北大学硕士学位论文第三章最优或次优组面试问题的最佳划分选择蓑略e 嘏轴= 等筹，蝇o m ；一一1 ) 亡鸭( 2 帆一m j 1 )心眠一1 ) 磊m j 一- ( 鸩一，一1 )：e u o ( k = ：一1 )即， l 争一m j ( 2 m 一- , , , , j - 1 ) 。、盏鸠一- ( 屿1 1 )，嚣1 鸠一l 1 - 1 )定理得证。定理4 得到了应满足的最优不等式，从中我们可以看出k 2 的性质，也可以按下面的方式定义磁：铀m 惟帮姐3 3 写的确定本节继续利用后退归纳法找到确定k ? 的最优不等式。引理7 ：对任何k 4 ，有础母志群峨一d 鞴 m j ( 2 m , - m 2 - 1 ) 卜，证明：采用关于k 的后退归纳法证明。根据式( 3 2 ) 中层玑( ，k ) 的性质：e 玑( r ，k ) 随，的增大而减小。在中间阶段k ，( 七= 1 , 2 ，托一1 ) 应有e 玑( 1 ，七) e u ，( 2 ，七)1 9 东北大学硕士学位论文第三章燕堡燮盟鲤鱼垡塑整塑墨堡型坌垫堡篷堕根据对第一行动集a ，的定义，对f a ，有e u 。( 1 ，r ) e 玑( f )e u ，( 2 ，r ) e u 。( 2 ，f )故有e u ( 1 ，f ) = e u s ( 1 ，f )( 3 1 8 )e u ( 2 ，f ) = e u c ( 0( 3 1 9 )于是，将式( 3 1 s ) 和式( 3 a 9 ) 代人式( 3 5 ) 。并用r 一1 替换毛得刚郴咖卺删( 2 ，o 赢“号器等= e 玑( 1 ，) 肘m t 。+ e 也( r ) j 豸毫等 = 兰万+ e u c ( r ) 尘搿= 等篙铲卺嘲卷崛搿鸩( 托一1 ) mm ( m 一。)m ( m 一1 )= 等瓮擎。e u 。鲁n 2 首先，t = 一1 时，此引理正确。这是因为，将式( 3 7 ) 代入式( 3 。1 9 ) 得矾c ，= 笔等铲笔筹熹制 等= 以m t ；- 2 ) i r 型篆业也。_ 1 ) 鑫黼i以一1 ) l。一一盘雌- ( 啄一1 ) l经过归纳，得到喇2 志医鼍产鸭一孵m ：( 2 9 - m y - 1 ) 旺2 。其次，假设后= t + 1 时，此引理正确。下面去证明七= ，时，此引理仍正确。将式( 3 2 1 ) 代入式( 3 2 0 ) 中得到东北大学硕士学位论文第三章最优或次优组面试问题的最佳划分选择策略e 配p 一1 )= 型m 篙铲“哪) 等m。( ，。一1 )，一错+志f铲专竽峨一d磊j羹而mj(2m-mj-1)111阿m,mmmmm。一1 )i 1 ) i 鲁，- l。牛1 惫，。一1 ) l f 2群+高隰掣峨rv,磊,丽mj(2m-mj-1)mmm1帆。一1 )。暇；一1 ) l 启，h、小11 盎i 。一1 ) i。丽mi-巧i掣+产竽+眠；-1-1)磊丽m：(zm-mj-1)mm1心。一1 ) im 。惫- l”o幺；。一1 ) i。盎降掣峨。叫杰糟】从而，我们所需要的结果得证。定理5 ；( 蠹：最优不等式)七是k ：，如果k 满足下面的不等式：12 m , “轧一1孵其中，弼) 口似。一1 ) 荟叫址赤陲号产叫 z 2 ，“( 2 膳一m 一1 )m 1 - ( 膨h 一1 )证明。砰是使e u 。q 七) e u 。( 七) 成立的最小的七于是，对k k ：，有e u ，( 1 ，_ | ：) e u 。 ? )( 3 2 3 )对k ，k i 一1 ，有e u ，( l 七i 一1 ) t e u 。 ：一1 )( 3 2 4 )由式( 3 2 3 ) ，得砒粉笔筹铲z 志m隧掣m峨。嚷篇m1。一1 ) i ，幺-、b 1 惫，一。，d 一1 ) f2 1 。东北大学硕士学位论文第三章最优或次优组面试问题的最佳型坌坚i 垦堕= f u 。 。)即h 蒜杀隰型焉罢型魄一9 蓄蒜等 ( 3 1 2 s ，巩一心一1 i j 帛蚂一4 惫够。一一1 ) l同理，由式( 3 2 4 ) ，得毗籼- 掣擀t 蒜陲掣m+似k,-i一嚷帮m-t】坂似，一1 ) l 詹，。、7 惫( 膨j 一一1 ) lt e u 。僻：一1 )即，c 丽1 2 m 砰陲掣一唼案若 z s ，一。一1 l 岔、定 铂- 一1 ) l记，皑) a 眠。一1 ) 磊 瓦m j ( 2 丽m , , - m j - 1 )综上，由式( 3 2 5 ) 和式( 3 2 6 ) 得，砑1 窿号竽叫垭南隰毪# 叫定理得证。定理得到了k i 应满足的最优不等式，从中我们可以看出七：的性质，也可以按下面的方式定义：q - r a i n q 赤隰号罢地峨一的蓍篙凳若卜慨z 7 ，现在我们已经得到确定h 和的最优不等式。最优或次优的组面试问题的最佳划分选择策略就是将全部应聘组划分成三个部分：“学习集”l ，“第一行动集”4 和“第二行动集”a ：，对“学习集”l 中的应聘组只面试不录用，然后在“第一行动集”a l 的各组中只录用第一个相对最优( 相对名次r = 1 ) 的应聘者，如果在“第一行动集”4 中没录取到，进入“第二行动集”a ：后录用各相中第一个相对嚣优或相对次优的( 相对名次r ，1 或r 。2 ) 的应鹏者。东北大学硕士学位论文第四章总结4 1 本文综述第四章总结秘书问题是最优停止理论中个著名的问题，研究的是报酬函数仅与所选观察项的秩相关而与其实际值无关的序贯观察和选择问题，它在最优停止理论的发展中曾起过重要的作用。由于近年统计学家和应用数学家的研究而得到了更大的发展空间，属于概率论与最优化理论的一个交叉研究领域。同时随着不断的推广变形，模型也越来越朝接近现实的方向发展。本文主要考虑的是秘书问题的变形“组面试问题”在目标是选择最优或次优应聘者时的最佳划分选择策略以及在允许重新安排面试顺序的最优组面试问题中如何获得最佳顺序。本文采用的主要方法有动态规划的后退归纳法和边界阶段方法。本文首先对秘书问题的产生发展作了一个大致的回顾，介绍了经典秘书问题的结果，建立了经典秘书问题的模型。特别介绍了目前出现的对模型中基本假设条件做若干修改的各种新模型。这些新模型采用各种不同的方法将原模型推广完善，更加接近实际问题。特别是动态规划，后退归纳法和随机m a r k o v 决策方法的引入，使得结论形式更简单，易操作。第二章首先介绍解决一般效用函数组面试问题的边界阶段方法，然后是最优组面试问题的最佳划分选择策略，最后讨论了在允许重新安排面试顺序的情况下，该问题的最佳顺序安排，这个结果的形式非常简单，在现实中能容易应用。如果改变所给的效用函数，采用边界阶段方法。可以得出类似的最佳划分选择策略。这正是我们下步将要做的工作。第三章重点讨论最优或次优组面试问题的最佳划分选择策略。由于前面介绍了边界阶段方法对一般效用函数的普遍结果，对于最优或次优组面试问题取定具体的效用函数待入后，只需确定两个边界阶段七1 = 七( ，= 1 ) 和e = 七( ，= 2 ) ，所以我们对砰= 七。( r ：1 ) 和= k ( ，= 2 ) 都作了相关的讨论。对这两个值都给出了具体的最优不等式，最后得n t 最优或次优组面试问题的最佳划分选择策略。- 2 3 东北大学硕士学位论文第四章总结4 2 应用及扩展方向秘书问题还有许多不同的名称，如：候选人问题，找工作问题，停车位问题，选美比赛l - j 题，卖房子问题，婚姻问题等等。这个模型及其各种变形，在现实中有很多的应用。组面试闯题实际上是经典秘书问题的推广，所以它也可应用于秘书问题曾应用过的地方。组面试问题进一步可以研究的方向：其一，录取的人数多于一人( 即多职位) ：其二，被拒绝过的应聘者可召回的情况。_ 2 昏东北太学顾士学位论文参考文献参考文献1 c h u r ly ho r ) t i m a lp a r t i t i o n i n go fg r o u p si ns e l e c t i n gt h eb e s tc h o i c e 【j 】，c o m p u t e r o p e r a t i o n sr e s e a r c h ，2 0 0 1 ，2 8 ：l3 6 7 1 3 8 6 2 c h u ay h s e l e c t i n gt h eb e s tc h o i c ei nt h ew e i g h t e ds e c r e t a r yp r o b l e m 明，e u r o p e a nj o u r n a lo f o p e r a t i o n a lr e s e a r c h ，1 9 9 6 ，9 2 ：1 3 5 - 1 4 7 3 s h o o u - r e nh s i a ua n dj f i n g - r uy a n g an a t i l r a lv a r i a t i o no ft h es t a n d a r ds e c r e t a r yp r o b l e m j q ，s t a t i s t i c as i m c a ，2 0 0 0 ，1 0 ：6 3 9 - 6 4 6 4 c h u r ly i - i ，m o s t e l l e rf p l a n t er o p t i m a ls e l e c t i o ns t r a t e g yf o rt h eg r o u pi n t e r v i e wp r o b l e m叨，d e c i s i o ns c i e n c e s ，1 9 9 3 ，2 4 ：2 9 5 - 3 1 3 5 c h u ny - i o nt h er a n k - b a s e ds e l e c t i o ns t r a t e g yf o rt h eg r o u pi n t e r v i e wp r o b l e m j 】，d e c i s i o n s c i e n c e s ，1 9 9 6 ，2 7 ：8 0 1 - 8 1 6 6 f e r g u s o nt s w h os o l v e dt h es e c r e t a r yp r o b l e m ? 闭，s t a t i s t i c a ls c i e n c e ，1 9 8 9 ，4 ：2 8 2 - 2 9 6 7 f r e e m a np 1 li h es e c r e t a r yp r o b l e ma