2024年秘书问题最优解VIP专享VIP免费

秘书问题最优解要]经典秘书问题是最优停止理论中的一个著名例子，属于一类序贯观察选择问题。其报酬函数仅与观察项的秩相关，而与观察项的实际值无关。现在一定假设条件下，将经典秘书问题推广，建立一个更有实际意义的模型。采用动态规划的方法得到该类模型的选择策略，为实际决策问题提供一种可供参考的方法。秘书问题是一类序贯观察与选择问题，描述了一种动态的信息搜索与决策过程。[关键词]秘书问题；简易公式；最小概率[前言]已有解决秘书问题的方法，主要特征是以取样选项中的最大值作为标杆，其优点是能保证赢的概率最大，其不足是很少考虑决策者的有限理性与启发式偏见。提出了基于次大值标杆策略的设想，通过理论求解以及仿真实验的方法研究了该策略的特征与规律。结果发现：赢的概率随着标杆由最大值向次大值、第三大值等的变化而逐渐降低，且最优截止阀值也不断后移。一、假设与最优停止规则[1]：假设下列条件成立（只要左方构成条件的事件的概率大于零）条件b）的直观意义是：如果已知第n个到达的姑娘的相对名次，则在此时刻以前的信息下引理：若若（1）式成立则最优停止规则是：其中sn可以归纳地计算出来：，对于预测她的绝对名次及拒聘与否，不起任何作用。根据如（1）则这里约定，对空的指标集求和为零。所以最优停止规则是。二、秘书问题的两个简单公式[2]：我们知道秘书问题中有两个简易的计算公式。它是对n为有限情形的秘书问题给出两个简易计算公式。情形1：设经理放过前k个申请者不予考虑，从第k+1个开始选择比前面都好的那位（如果有的话），记ak={放过前k位第1页共14页结果选到1号}因此，对于n个申请者的情形，，使选到最差的那位概率最小。情形2。对于n个申请者由于经理每次招见一批人，他可以在同一批中选择最好的，如果最后一批的人数大于1，经理不可能招聘到1号申请者（最差的那位），因此我们只考虑最后一批人数为1的情形。设这n个人随机地按d批进见经理，各批的人数分别为n1，n2，···，nd，nd=，最小.即经理应放掉第1位，才能1，，记。假设经理放过前k批不予考虑，从第k+1批开始选择比前面各批都好的那位（如果有的话），ak={放过前k批最后结果选到1号}，则有公式2在上述条件下由此可计算的最优值。[3]。三、次大值标杆策略的仿真实验解决秘书问题的关键，并非决定去选择哪一个选项，而是决定何时停止取样观察选项，即何时停止搜索决策信息。但近些年研究发现，相比较最优解策略，人们往往停止搜索得太早或者搜索量太少[4]。这意味着决策者往往并没有遵循最优解策略去决策。下面我们做一个仿真实验来解决秘书问题的满意解。实验内容是截止阀值与标杆交叉组合的截止阀法则。根据最优解策略的阀值37%以及现实生活中的经验值，我们测试了7个截止阀值r与2个标杆m的策略组合。它们分别是：截止阀值为选项集的10%、1/3、37%、50%、0618、2/3、90%;标杆为取样选项集中的最大值（m=1）与次大值（m=2）。这样，本研究一共实验了14（7x2）个组合策略。首先，与已有研究[4]类似，我们用数字的大小表示选项的优劣程度，数字越大意味着选项越优，否则越差。其次，采用第2页共14页序数集的随机排列来模拟选项被随机会见的情境。设选项集n=100，将1、2、……、100共一百个序数随机置乱作为测试集。在不同的截止阀值下，分别采用最大值与次大值标杆进行选择;而截止阀值与标杆的每种组合策略重复测试100次。然后计算即赢的次数（选中最大值100的次数），实验结果如表1所示。从表中可以看出。（1）当采用最大值标杆（m=1）时，截止阀值r为37%的组合策略赢的概率最大，即组合点（r=37%，m=1）赢的概率为35%。（2）当采用次大值标杆（m=2）时，截止阀值r为50%的组合策略赢的概率最大。即组合点（r=50%，m=2）赢的概率为23%。（3）在最大化赢的概率的条件下，随着标杆由最大值（m=1）向次大值（m=2）的变化，截止阀值也由r=37%向r=50%变动。这说明标杆不同，截止阀值也不同;而且还有标杆降低、截止阀值后移的趋势。另外，从表中还可以看出。在阀值37%、最大值标杆处，赢的概率达到最大（为35%）。该值与理论计算的赢的概率1/e=37%[5]只差2个百分点，与seale和rapoport[4...