运筹作业

动态规划题

王磊学号：S110166

某公司去一所大学招聘一名管理专业应届毕业研究生。从众多应聘学生中，初选3名依次单独面试。面试规则为：对第1人或第2人面试时，如果满意（记3分），并决定聘用，面试不能再继续；如果不满意（记1分），决定不聘用，找下一个继续面试；如较满意（记2分）时，有两种选择，或决定聘用，面试不再继续，或不聘用，面试继续。但对决定聘用者，不能同在后面面试的人比较后再回过头来聘用。故在前两名面试者都决定不聘用时，第三名面试者不论属于何种情况均需聘用。根据以往经验，面试中满意占20%，较满意的占50%，不满意占30%。要求用动态规划办法帮助该公司确定一个最优策略，使聘用到的毕业生期望的分值为最高。

解：用k表示阶段，k=1,2,3.

1,k阶段尚需面试录用 状态变量Sk,Sk= o,否则

1对,k阶段面试者决定录用决策变量Xk,Xk= o,否则

状态转移方程Sk+1=Sk Xk

动态规划基本方程

fk Sk =

Ck(Xk)为k阶期望的记分值。

边界条件

f4 0 =1

当k=3时

f3(1)=max 0.2×3+0.5×2+0.3×1 f4(0) =1.9

0.2×3+0.5×2)f3 0 +0.3f3(1) f2(1)=max =2.19 0.2×3)f3 0 +(0.5+0.3 f3 1

0.2×3+0.5×2)f2 0 +0.3f2(1) f1(1)=max =2.336 0.2×3)f2 0 +(0.5+0.3 f2 1

结论：对第一个面试者面试时对比较满意者不录用，对第二个面试时，对比较满意者应录用，使录用人员总期望分为2.336分.

maxXk∈ 0,1 Ck(Xk) fk+1(Sk+1)

本文来源：https://www.bwwdw.com/article/8zgi.html