第二讲 生活中的数学建模问题

数学建模 讲义 NUDT 2023SP

---

---

2.1 席位分配问题

• 某系有 200 名学生，甲专业 103 名，乙专业 63 名，丙专业 34 名.
• 若学生会设 20 个代表席位，问应该如何分配席位?
• 若席位增加为 21 个，又该如何分配?

---

按比例平均分配

如果按照人数比例进行分配，结果如下：

$$\begin{array}{c|cc|cc|cc} \text{专业} & \text{学生人数} & \text{人数比例}\% & \text{按比例分配数} & \text{分配结果} & \text{按比例分配数} & \text{分配结果}\\\hline \text{甲} & 103 & 51.5 & 10.3 & 10 & 10.815 & 11\\ \text{乙} & 63 & 31.5 & 6.3 & 6 & 6.615 & 7\\ \text{丙} & 34 & 17 & 3.4 & 4 & 3.570 & \bbox[orange]{\;3\;}\\\hline \text{合计} & 200 & 100 & 20 & 20 & 21 & 21 \end{array}$$

• 总席位增加了，丙专业的席位却不增反减！

---

分配方案的公平性

• 如何度量分配方案的公平性？
• 以两方的情况为例：设 A、B 两方人数分别是 $p_1, p_2$，分别占有 $n_1,n_2$ 个席位，则两方每个席位所代表的人数分别是，$p_1/n_1, p_2/n_2$.
• 所谓公平，可以理解为 $\bbox[yellow]{p_1/n_1 = p_2/n_2}$.
  
  • 通常上式不会严格成立，对于存在的 “不公平” 的可以用数值 $\bbox[lightgreen]{|p_1/n_1 − p_2/n_2|}$ 来度量.

---

从绝对差异到相对差异

• 如果 $p_1/n_1 > p_2/n_2$，则意味着对 A 方不公平，定义 对 A 的相对不公平值 为
  
  • $\bbox[yellow]{r_A(n1, n2)=\dfrac{p_1/n_1 − p_2/n_2}{p_2/n_2} = \dfrac{p_1n_2}{p_2n_1} − 1}$.
• 同理，若 $p_1/n_1 < p_2/n_2$，可以定义 对 B 的相对不公平值
  
  • $\bbox[lightgreen]{r_B(n_1,n_2)=\dfrac{p_2/n_2 − p_1/n_1}{p_1/n_1}=\dfrac{p_2n_1}{p_1n_2}-1}$.

---

新增席位的分配

假设 A、B 两方已分别占有 $n_1, n_2$ 个席位，当总席位再增加 1 席时，应该给 A 还是 B？

• 不妨设 $p_1/n_1>p_2/n_2$，即此时对 A 方不公平. 讨论如下：
  
  1. 若 $p_1/(n_1+1)>p_2/n_2$，即新增一席给 A 方后，仍对 A 方不公平，此时当然分给 A.
  2. $p_1/(n_1+1)<p_2/n_2$，即新增一席分给 A 方后，将对 B 方不公平，对 B 的相对不公平值为 $r_B(n_1+1,n_2)=\dfrac{p_2(n_1+1)}{p_1 n_2}-1$
  3. $p_1/n_1>p_2/(n_2+1)$，新增一席给 B 方，必然使对 A 的不公平程度增加，对 A 的相对不公平值为 $r_A(n_1,n_2+1)=\dfrac{p_1(n_2+1)}{p_2 n_1}-1$

---

分配思路

• 除了第一种情形必然分给 A 以外，公平的席位分配方法应该使得相对不公平值尽量小，
  
  • 也即：若 $r_B(n_1+1,n_2)<r_A(n_1,n_2+1)$，则分配给 A 方；反之，应分给 B 方.
• 上式等价于 $\dfrac{p_2^2}{n_2(n_2+1)}<\dfrac{p_1^2}{n_1(n_1+1)}$.
• 对于第一种情形，上式显然也成立.
• 结论： 当 $\bbox[yellow]{\dfrac{p_2^2}{n_2(n_2+1)}}<\bbox[lightgreen]{\dfrac{p_1^2}{n_1(n_1+1)}}$ 成立时，新增的 1 个席位应当分给 A 方；反之，应分配给 B 方.

---

涉及多方的席位分配

• 上述方法可推广到 $m$ 方分配席位的情况.
• 设第 $i$ 方已获得 $n_i$ 席，记 $\bbox[yellow]{Q_i=\dfrac{p_i^2}{n_i(n_i+1)}}\; (i=1,2,\ldots,m)$
• 当增加一个席位时，这一席位应分配给 $Q_i$ 值最大的一方.
• 然后重新计算$Q_i\ (i=1,2,\ldots,m)$，直到所有席位分配完为止.
• 此方法称为 Q 值方法.

---

解答

• 应用 Q 值方法于本例中三方分配席位的情形，可以先按比例的整数部分分配，即甲、乙、丙分别获得 10、6、3 个席位，然后按下表分配.
• 也可以三方初始各有 1 席，之后始终按 Q 值法分配.
• 结果： 甲获得第 20 个席位，丙获得第 21 个席位.

$$\begin{array}{c|c|c|c} n & \text{甲} & \text{乙} & \text{丙}\\\hline 2 & 5304.5(4) & 1984.5(5) & 578.0(9) \\ 3 & 1768.2(6) & 661.5(8) & 192.7(15)\\ 4 & 884.1(7) & 330.8(12) & \bbox[lightgreen]{96.3(21)}\\ 5 & 530.5(10) & 198.5(14) & \\ 6 & 353.6(11) & 132.3(18) & \\ 7 & 252.6(13) & 94.5 & \\ 8 & 180.4(16) & & \\ 9 & 147.3(17) & & \\ 10 & 117.9(19) & & \\ 11 & 96.4(20)& & \\ 12 & 80.4 & & \end{array}$$

---

小结

• 发现常识中的不合理之处，尝试进行改进.
  
  • 本例的一个隐含假设：各方席位数与总席位数应该是单调的.
• 找到问题的关键：公平性的度量
  
  • 将最后一个席位应该给谁的问题，明确为给谁更公平.
  • 给出一个各方都能接受的合理的公平性度量.
  • Q 值方法，可操作性强，与原来的方法兼容.
• 先研究解决较为简单的情况，然后尝试向更复杂的情形推广.

---

2.2 行走步长问题

人在匀速行走时步长多大最省劲 ？

---

• 假设： 不考虑行走时人上半身的动作和外界环境对速度的影响.
• 参数：
  
  • 人的体重 $M$
  • 腿重 $m$
  • 腿长 $l$
  • 行走速度 $v$
  • 单位时间步数 $n$
  • 步长 $x$（$v=nx$）

---

分析

• 省劲 = 做功少，耗能低.
• 人行走时所做的功主要转化为两部分：
  
  1. 抬高重心，转化为势能；
  2. 两腿运动的动能.
• 上身运动的动能是常数，与步长无关，故不考虑.

---

1. 重心升高所需的能量

• 记每一步中重心升高的量为 $\delta$，则
  
  • $\delta = l-l\cos\theta = \bbox[yellow]{l-l{\left(1-\dfrac{x^2}{4l^2}\right)}^{1/2} \approx l-l\left(1-\dfrac{x^2}{8l^2}\right)}= \dfrac{x^2}{8l}$
• 单位时间重心升高所需做功为 $W_{\mbox{势}}=nMg\delta=\dfrac{nMgx^2}{8l}=\dfrac{Mgv}{8l}\,x$.

---

2. 腿运动所需的能量

• 将人行走时腿的运动视为均匀直杆（腿）绕腰部的转动，
  
  • 则在单位时间内所需动能为 $W_{\mbox{动}}=\dfrac{1}{2}I\omega^2 \cdot n$
  • 其中转动惯量 $I=\dfrac{1}{3}ml^2$, 角速度$\omega=\displaystyle\frac{v}{l}$.
• 故 $W_{\mbox{动}}=\dfrac{1}{2}\cdot\dfrac{1}{3}ml^2{\left(\dfrac{v}{l}\right)}^2 n=\dfrac{n}{6}mv^2=\dfrac{mv^3}{6x}$.

---

总功

• 单位时间所做的功为 $W=W_{\mbox{势}}+W_{\mbox{动}}=\dfrac{Mgv}{8l}x+\dfrac{mv^3}{6x}$
• 令 $\displaystyle\frac{\mathrm{d} W}{\mathrm{d} x}=0$，解得 $x=\sqrt{\dfrac{4}{3}\dfrac{mlv^2}{Mg}}, n=\sqrt{\dfrac{3}{4}\dfrac{Mg}{ml}}$
• 为检验此结果的合理性，代入具体数值，假定：$M/m=4$, $l=1$米, $g=9.8\mbox{米/秒}^2$, 计算得到：$n=5.4\mbox{步/秒}$.

---

改进的思路

• 上述结果与实际情形差异较大，可以考虑将模型改进为：将腿的质量集中在脚部，行走看作是脚的直线运动.
• 则动能部分改变为：$W_{\mbox{动}}=\dfrac{mv^3}{2x}$.
• 这时的最优解为 $n=\sqrt{\dfrac{Mg}{4ml}}$.
• 代入具体数值，得 $n=3.1$步/秒.

---

小结

• 后一模型的结果似乎更接近实际，但改进的理由也并不充分，合理性仍可讨论.
• 事实上，以上两个模型可能都过于简化，人在行走时腿的运动不能近似为匀速运动，每一步都有一个从静止到运动再到静止的加速与减速过程，而在这个变速过程中所多消耗的能量也许不是一个可忽略的量.
• 思考： 如何改进行走步长问题的模型，使之更符合实际？

---

2.3 稳定匹配问题

假设在一个 $n$ 对男女的联谊会上配对跳交谊舞，每个人都按自己的喜好程度对所有异性排序，排序中没有并列. 下表是一个简单的例子（大写字母代表男生，小写字母代表女生）。

$$\begin{array}{cccc|c|cccc} \hline A & B & C & D & & w & x & y & z \\ \hline w & x & x & y & & D & B & D & C \\ x & z & w & x & & C & A & C & B \\ y & w & y & z & & A & D & B & A \\ z & y & z & w & & B & C & A & D \\ \hline \end{array}$$

• 问题： 应该如何组合才能达到最优？

---

分析

• 因为配对需要双方都能接受，因此如果还存在至少存在一对男女，他们都认为对方比自己当前的搭档更理想，则当前的组合就不能说是最优的！
• 问题：
  
  • 是否一定存在最优的方案？
  • 如果存在最优的方案，是否唯一？
  • 如何得到最优的方案？

---

稳定匹配

• 本例的中的最优组合方案可以称为 稳定匹配（Stable matching），即：每个人当前的搭档恰好是他（她）在当前现实中的最优选择.
• 例如：
  
  • 不稳定匹配：$\{(A,\bbox[yellow]{\;w\;}), (B,x), (\bbox[yellow]{\;C\;},y), (D,z)\}$
  • 稳定的匹配：$\{(A,z), (B,x), (C,w), (D,y)\}$

---

Gale-Shapley 算法

1. 第一轮，每位男生向各自最中意的女生发出邀请，然后每个女生在所收到的邀请中选择自己最中意的男生；
2. 第二轮，还没有搭档的男生向其第二中意的女生（无论该女生是否已有搭档）发出邀请，然后每个女生在新收到邀请的男生以及当前搭档中选择一个最中意的；
   
   • （已有搭档的男生不再发新邀请，没有收到新邀请的女生保持当前状态。）
3. 第三轮，重复上述过程直到结束.

---

运行结果

每一轮次的运行结果：

1. $(A,w), (B,x), (C,x), (D,y)$, $x$拒绝$C$
2. $(A,w), (B,x), (C,w), (D,y)$, $w$拒绝$A$
3. $(A,x), (B,x), (C,w), (D,y)$, $x$拒绝$A$
4. $(A,y), (B,x), (C,w), (D,y)$, $y$拒绝$A$
5. $(A,z), (B,x), (C,w), (D,y)$

---

算法的可行性

• 证明：首先注意到，在这个过程中，对于男生而言，是越选越差，
  而女生是越选越好.
• 用反证法. 假设算法得到的匹配方案不稳定，
• 则在最后的方案中存在一男（$M$）与一女（$f$），都觉得对方比自己的搭档更好.
• 记最终的匹配方案为$(M,F)$ 和$(m,f)$，既然 $M$ 认为 $f>F$，则 $M$ 必然曾经向 $f$ 发出过邀请，但是被$f$拒绝了，这说明 $f$ 最终的搭档比 $M$ 要优，矛盾！

---

讨论

• 稳定匹配方案是否唯一？

  • 不一定唯一. 例如
  • $\begin{array}{cccc|c|cccc} \hline A & B & C & D & & w & x & y & z \\ \hline w & x & w & y & & A & A & B & D \\ x & y & y & x & & B & C & A & C \\ y & z & z & w & & C & B & D & B \\ z & w & x & z & & D & D & C & A \\ \hline \end{array}$

• 算法能否在有限步内结束？

  • 可以. 每个男生最多发出 $n$ 次邀请，必然能邀请到女生，所以算法可以在有限步后结束.
• 男女双方哪一方先选，是否有区别？
  
  • 有区别.先选择的一方有利.
• 算法在"多对一"时（如：企业与求职者，研究生导师与研究生等）是否有效？
  
  • 有效.
• 算法是否能够防止欺诈行为得逞？
  
  • 不能.

---

小结

• 结合问题的背景，明确“最优”、“最佳”的含义.
  
  • 本例中，"最优" = “稳定”.
• 通过刻画“不稳定”来定义稳定，并给出迭代求解的思路.
  
  • 与席位分配问题从“不公平”程度入手有相似之处.
• 算法简单明了，具有广泛的适用性.

---

2.4 雨中行走问题

人在雨中沿一直线行走，雨速已知，问人行走的速度多大才能使淋雨量最小？

• 记：
  
  • 人行走速度 $(U,0,0)$, $(U>0)$,
  • 雨速 $(V_x,V_y,V_z)$（常值向量）,
  • 行走距离为 $S$.

---

淋雨量的计算

• 将人视为长方体，前、侧、顶的面积之比为 $1:L:T$.
• 单位时间淋雨量
  
  • $(|U-V_x|,|0-V_y|,|0-V_z|)\cdot (1,L,T)=|U-V_x|+A$，
  • 其中 $A=|V_y|\cdot L+|V_z|\cdot T$.
• 总淋雨量为 $\bbox[yellow]{R(U)=\dfrac{S}{U}(|U-V_x|+A)}$.
• 优化问题：已知 $S, V_x, A$, 求 $U$ 为何值时 $R(U)$ 最小？

---

讨论

• $V_x<0$ 时（即：风迎面吹来 ）
  
  • $R(U)=\dfrac{S}{U}(|U-V_x|+A)$
  • $=\dfrac{S}{U}(U+|V_x|+A)=S+S\dfrac{|V_x|+A}{U}$
• $R(U)$ 关于 $U$ 递减，显然 应该走得越快越好 .

---

• $V_x>0$时（即:风从背面吹来）
  
  • $R(U)=\left\{\begin{array}{ll} \displaystyle\frac{S}{U}(V_x-U+A)=\frac{S(V_x+A)}{U}-S & U\leqslant V_x \\ \displaystyle\frac{S}{U}(U-V_x+A)=\frac{S(A-V_x)}{U}+S & U>V_x \end{array}\right.$
  • $\dfrac{\mathrm{d} R}{\mathrm{d} U}=\left\{ \begin{array}{ll} -\displaystyle\frac{S(V_x+A)}{U^2}, & U\leqslant V_x \\ -\displaystyle\frac{S(A-V_x)}{U^2}, & U>V_x \end{array}\right.$

---

$\dfrac{\mathrm{d} R}{\mathrm{d} U}=\left\{ \begin{array}{ll} -\displaystyle\frac{S(V_x+A)}{U^2}, & U\leqslant V_x \\ -\displaystyle\frac{S(A-V_x)}{U^2}, & U>V_x \end{array}\right.$

• 当 $V_x<A$ 时，恒有 $R'(U)<0$，无极小值，即走得越快越好；
• 当 $V_x>A$ 时，$R(U)$ 如图.
  
  • 当 $U=V_x$ 时，$R_{\min}=R(V_x)=\dfrac{SA}{V_x}$.
• 结论： 当 $0<A<V_x$ 时，取 $U=V_x$，其他情况下，$U$ 应尽可能大.

---

小结

• 抓住主要矛盾，简化问题.
  
  • 如果改为将人视为圆柱体，结论会有很大差别吗？
• 分情况讨论，再综合给出结论.
• 基于常识对结论的合理性给出初步判断.

---

2.5 传球游戏

• A，B，C，D，E 五人站成一个圆圈玩传球游戏，规定每人只能传给自己两侧的人. 球由 A 开始传.
• 问：传球 10 次后，球回到 A 手中的概率是多少？

---

概率解法

• 由于每次只能向两侧的人传球，因此，每次传球只有两种可能，向左传球记为 0，向右传球记为 1. 则，传 10 次，全部可能的情况共有 $2^{10}$ 种.
• 考虑传 10 次后回到 A 手中的条件. 若传球有左有右（有 0 有 1 ），则只有 5 次向左，5 次向右，才能回到 A，即，共有 $C_{10}^5$ 种情况.
• 如果始终向同一个方向传 10次，球正好也能回到A手中.
• 因此，总共可能的情况是 $2+C_{10}^5$.
• 所以传球 10 次后，球回到 A 手中的概率是：$P=\dfrac{2+C_{10}^5}{2^{10}}=\dfrac{127}{2^9}\approx 0.248$.

---

递归解法

• 设 $A_n$ 表示第 $n$ 次传球后，球在 A 手中的概率，同样定义 $B_n, C_n, D_n, E_n$.
• 由传球规则及对称性可知：$B_n=E_n,\; C_n=D_n$.
• 进而可以得到如下关系：
  
  • $A_n = \frac{1}{2}\cdot B_{n-1} + \frac{1}{2}\cdot E_{n-1}=B_{n-1}$；
  • $B_n = \frac{1}{2}\cdot A_{n-1} + \frac{1}{2}\cdot C_{n-1}=\frac{1}{2}\cdot B_{n-2}+\frac{1}{2}\cdot C_{n-1}$；
  • $C_n = \frac{1}{2}\cdot B_{n-1} + \frac{1}{2}\cdot D_{n-1}=\frac{1}{2}\cdot B_{n-1}+\frac{1}{2}\cdot C_{n-1}$.

---

• 进一步得到递归关系式：
  
  • $B_n=\frac{1}{2}\cdot B_{n-2}+\frac{1}{2^2}\cdot B_{n-2}+\frac{1}{2^3}\cdot B_{n-3}+\cdots+\frac{1}{2^{n-2}}\cdot B_2+\frac{1}{2^{n-1}}\cdot B_1+\frac{1}{2^{n-1}}\cdot C_1$.
• $A_1=0, B_1=\frac{1}{2}, C_1=0$，$B_2=\frac{1}{2}\cdot A_1+\frac{1}{2}\cdot C_1=0$.
• 递归得到：$A_{10}=B_9=\frac{127}{2^9}$.

---

计算机仿真

• 使用计算机模拟传球游戏 $N$ 场，每场传球 $10$ 次，记录下球回到A手中的场次数 $l$，则 $P=\frac{l}{N}$.
• 某次仿真的结果为 0.247815.

#!/usr/bin/env python
# encoding: utf-8
import numpy
n = 10
N = 1000000.
num = 5
l = 0
for j in range(N):
    pos = 0
    for i in range(n):
        k = numpy.random.randint(2) * 2 - 1
        pos = (pos + k) % num
    if pos == 0:
        l += 1
print l/N

---

小结

• 解决问题的方法和角度可能有很多，这些方法的适用条件、特点各不相同.
• 遇到具体问题，应该根据现实的条件和约束进行选择.
• 不同的方法通常可以相互印证，相互检验.

---

2.6 不可召回的秘书招聘问题

• 某企业需要招聘一位秘书，现对多名候选人进行逐一面试，当场决定是否录取，一旦拒绝，无法召回；一旦录取，面试停止.
• 该企业应该采取何种录取策略？效果如何？

---

最优停止策略

一种可行的策略如下：

• 前 $k$ 人一律拒绝，从第 $k+1$ 人开始，只要比前一个人优秀就录取.
• 如何确定 $k$，使得选到最优秀秘书的概率最大？

---

分析

• 假设：最优秘书在面试序列中的位置服从均匀分布. 即，出现在任何一个位置的概率均为 $\dfrac{1}{n}$. ($n$ 为参加面试的总人数).
• 对于某个固定的 $k$，企业选中最优秀秘书 s 需要具备两个条件：
  
  • s 不能被拒绝：s 不能位于前 $k$ 位. 假设 s 位于第 $i$ 位，则 $k+1\leqslant i\leqslant n$.
  • s 不能被遗漏：s 之前的 $i-1$ 人中的最优秀者，必须位于前 $k$ 位.
• 于是在第 $k$ 位选到最优秀秘书的概率 $P(k)=\sum\limits_{i=k+1}^n \dfrac{1}{n}\cdot \dfrac{k}{i-1}=\dfrac{k}{n}\sum\limits_{i=k+1}^n \dfrac{1}{i-1}$.

---

求解

• 问题：寻找最优的 $k$ 值，使得在该位置选到最优秀秘书的概率 $P(k)$ 最大.
• 求解技巧：将离散形式的问题近似为连续的，已更方便地使用微积分中的求最值方法.
• 令 $x=\dfrac{k}{n}$，当 $n$ 充分大时，
  
  • $P(k)=\dfrac{k}{n}\sum\limits_{i=k+1}^n \dfrac{1}{i-1}=x\sum\limits_{i=nx}^{n-1}\dfrac{1}{i}=\bbox[yellow]{x\sum\limits_{t=x}^{1-1/n}\dfrac{1}{n\cdot t}\approx x\displaystyle\int_x^1 \dfrac{1}{t} \mathrm{d} t} = -x\ln x$.

---

• 令 $\dfrac{\mathrm{d}}{\mathrm{d} x}(-x\ln x)=-1-\ln x=0$，
• 得到：$x=\dfrac{1}{\mathrm{e}},\; k=\dfrac{n}{\mathrm{e}} \approx 0.3679\cdot n \approx 37\% \cdot n$
• 代入 $P(k)$，得到最大概率为恰好也为 $\dfrac{1}{\mathrm{e}}$，即 $P(n/\mathrm{e}) = \dfrac{1}{\mathrm{e}}$.
• 结论 ( 37% 准则 ) 该企业应该拒绝前 $37\%$ 的应聘者；之后，一旦发现更优秀的应聘者，立即录用.

---

计算机仿真

---

计算机仿真

---

小结

• 通过适当地转换，得到对问题的数学描述.
  
  • 最优的策略：得到最优秘书的概率最大.
  • 思考： 有没有其他可行的策略？
• 离散问题转化为连续问题处理，充分发挥现代数学工具的强大威力.
• 结合计算机仿真验证结果.

---

2.7 有奖销售的抽奖策略

• 某人可获得一笔奖金 $x$, $x$ 由他在区间 $[0,1]$ 中随机地抽取.
• 一轮抽奖可最多重复抽 3 次，如果第一次满意，可以领取 $x$ 奖金而不再抽取；
• 如果他不满意，可以放弃这个 $x$ 而重新抽，第三次抽取后不得放弃.
• 应该采取何种策略以期获得最多奖金？

---

分析：

• 策略描述的关键就是决定第一次放弃和第二次放弃的条件.
• 该抽奖人的收入定义为：$S(a,b)=\begin{cases}X_1, & X_1>a; \\ X_2, & X_1\leq a, X_2>b; \\ X_3, & X_1\leq a,X_2\leq b.\end{cases}$
• 其中 $a,b$ 为第一次和第二次抽奖放弃的阈值，因此策略由 $(a,b)$ 决定.
• 随机变量 $X_1, X_2, X_3\sim U(0,1)$.
• 问题目标为获最多的奖金，即 $S$ 的期望达最大值.

---

$$E(S)=\iiint\limits_{[0,1]^3}s(a,b)f(x_1,x_2,x_3)\mathrm{d}x_1\mathrm{d}x_2\mathrm{d}x_3=\dfrac{1}{2}(1-a^2+a-ab^2+ab).$$

• 其中 $f(x_1,x_2,x_3)$ 为 $(X_1,X_2,X_3)$ 的联合密度函数.
• 令 $\triangledown E(S)=0$，即 $\begin{cases}\dfrac{\partial E(S)}{\partial a}=\dfrac{1}{2}(1-2a+b-b^2)=0\\ \dfrac{\partial E(S)}{\partial b}=\dfrac{a}{2}(1-2b)=0\end{cases}$
• 解得 $a=\dfrac{5}{8}$，$b=\dfrac{1}{2}$.
• 最大期望奖金 $E(S)=\dfrac{89}{128}\approx 0.7$.

---

条件期望法

• 第一次抽奖的奖金期望 $E(S_1)=P\{X_1>a\}E(X_1|X_1>a)=\dfrac{1-a^2}{2}$.
• 第二次抽奖的奖金期望
  
  • $E(S_2)=P\{X_1\leq a,X_2>b\}E(X_2|X_1\leq a,X_2>b)=\dfrac{a(1-b^2)}{2}$.
• 第三次抽奖的奖金期望
  
  • $E(S_3)=P\{X_1\leq a,X_2\leq b\}E(X_3|X_1\leq a,X_2\leq b)=\dfrac{ab}{2}$.
• 最终的奖金期望 $E(S)=E(S_1)+E(S_2)+E(S_3)$.

---

课后思考

1. ($\star\star$) 分析、评价稳定匹配问题与高考录取“平行志愿”制度的联系与区别.
2. ($\star\star\star$) 在秘书招聘问题中，如果策略改为，拒绝前 $k$ 人，从第 $k+1$ 人开始，一旦有比前面次优人选更优秀的人选，就录取. 那么最佳的 $k$ 又是多少？
3. ($\star\star\star$) 在秘书招聘问题中，如果目标改为所招秘书的平均水平最佳，而不是招到最优秀秘书的概率最大，那么，招聘策略应如何调整？结果如何？