俞昊辰

摘要：依托DVD在线租赁问题，并行实现Monte-Carlo随机模拟计算方法，使用WinAPI、OpenMP和MPI三种并行模式并行。通过数值的直观比较，得出MPI并行模式最优。最终获得结论并行算法可以推广至大样本下的计算机智能模拟问题。

关键词：并行计算；蒙特卡洛方法；WinAPI；OpenMP；MPI

针对下面提出的DVD在线租赁问题，本质上就是多目标线性规划求解，而本例以蒙特卡洛模拟为背景，实操上简而言之便是计算机智能模拟。蒙特卡洛实验模拟本身而言便是个反复进行足够多次的实验，根据大数定律，在大样本的前提下，所得到的结果才更为有说服性和一般性。蒙特卡洛實验的计算量偏大，且大多数的处理方法都是串行算法，在高性能计算领域对简单蒙特卡洛实验的实现已有许多案例，然而较为复杂的蒙特卡洛实验的数值解法则鲜有文章详细解释。为了弥补此不足，利用WinAPI、OpenMP和MPI三种并行模式改造并精选出三种最优的并行计算方法。

1问题提出

现存在一种DVD在线租赁服务，会员通过对喜欢的DVD在线下单，网站就会以快递的方式将DVD送达至会员手中。会员可同时订购多张DVD，并且按照其偏爱程度进行排序。网站会根据目前现有的DVD数量以及会员订单情况进行分发，其中网站约束每个会员每个月租赁次数不得超过2次，且最多获得3张DVD。会员浏览完所借DVD之后，只需将DVD放进网站提供的信封里寄回（邮费由网站承担）。

现在，网站准备引进一批新的DVD，通过问卷调查会员，得到了时下DVD受欢迎的主流类型。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外40%只租赁一次。那么在既定的会员数量下，网站对不同类型的DVD各需要准备多少张，才可以保证想要看到并且能在一个月内看到该DVD的会员至少达到50%，才可以保证在三个月内看到该DVD的会员至少达到95%。

2串行模型建立

假设既定会员人数为100000人。

分类：A类会员：租赁频率为2次/月的会员；B类会员：租赁频率为1次/月的会员；

说明：会员的身份随时有可能发生变化，但是从大样本上看，A类会员和B类会员在总人数中的比率必须分别为60%和40%；同一张碟在一个月内最多被允许租借两次；该网站租赁DVD处于一种供不应求的状态。

假设：A类会员在每月一号租借的碟十五日归还，再租借其他的碟到月底归还；B类会员在一日租借碟，到月底归还。

定义：表示在每月第一批次租借碟的会员中，A类会员所占比例；表示B类会员所占比例；表示一个月内看到第种碟片的总人数；表示需要采购的第种碟片的数量。

这里认为抽样调查的结果和一般意义下的统计规律相吻合。

根据上述假设，可以认为一张碟在一个月内至多被租出两次。

首先，我们就DVDl的购买情形做分析。根据表中数据可知，占调查人数总数的20%。则在总人数为10万的前提下，一个月内希望看到DVDl的人数总共有20000个，又，所以至少要保证10000人能看到DVDl。因为会员分为A、B类，且A类会员占60%，若我们所保证的会员10000人都是A类会员，此时所需购买的DVDl数目最少，为5000张；在20000个会员中最多有8000个B类会员，而如果20000个人中恰好包含了这8000个会员，此时所需购买DVDl数目最多，为9000张。

然而，事实是不可能保证这10000人都是A类会员，但至少可以说明所需购买DVDl的数量必须大于等于5000张。假设，则看到DVDl的A类会员数服从于分布，则一个月内看到DVDl的人数应为。若，即此次模拟购买张DVDl是可以确保在一个月期间，会员中想要借到DVDl的人，至少50%可以成功借到DVDl。若在的条件下，我们重复大量模拟实验（规定试验次数次），有次使得成立，我们就认为购买张DVDl能以99%的概率确保，在一个月期间内会员群体中想要看到DVDl的人，至少50%可以成功借取DVDl。此时，即为所求。因为5000张是购买DVDl的最低限制，若在的条件下，经过重复大量模拟实验，并没有实现使得成立的次数，我们就令，即在之间重复大量模拟实验，直到找到我们所期望的以尽可能高的概率值保证结果成立的。其他种类的DVD碟数的购买量都可以类似地求解，先计算最少购买量，然后再做模拟仿真实验找寻结果。

针对保证在三个月内至少95%的会员能够看到DVD这一情况，仍以DVDl为例，我们可以做类似的处理，若购买张，那么第一个月内希望看到DVDl的A会员人数应服从于分布，第二个月内希望看到DVDl的A会员人数应服从于分布，第三个月内希望看到DVDl的A会员人数应服从于分布。则三个月内总共能看到此碟的总人数为，若，我们便可以确保本店会员至少有95%的人在三个月期间可以成功借到这个DVD。其他种类的DVD碟数的购买量都可以类似地求解，先计算最少购买量，然后再做模拟仿真实验找寻结果。