俞昊辰

摘要：依托DVD在線租賃問題，并行實現(xiàn)Monte-Carlo隨機模擬計算方法，使用WinAPI、OpenMP和MPI三種并行模式并行。通過數(shù)值的直觀比較，得出MPI并行模式最優(yōu)。最終獲得結論并行算法可以推廣至大樣本下的計算機智能模擬問題。

關鍵詞：并行計算；蒙特卡洛方法；WinAPI；OpenMP；MPI

針對下面提出的DVD在線租賃問題，本質上就是多目標線性規(guī)劃求解，而本例以蒙特卡洛模擬為背景，實操上簡而言之便是計算機智能模擬。蒙特卡洛實驗模擬本身而言便是個反復進行足夠多次的實驗，根據(jù)大數(shù)定律，在大樣本的前提下，所得到的結果才更為有說服性和一般性。蒙特卡洛實驗的計算量偏大，且大多數(shù)的處理方法都是串行算法，在高性能計算領域對簡單蒙特卡洛實驗的實現(xiàn)已有許多案例，然而較為復雜的蒙特卡洛實驗的數(shù)值解法則鮮有文章詳細解釋。為了彌補此不足，利用WinAPI、OpenMP和MPI三種并行模式改造并精選出三種最優(yōu)的并行計算方法。

1問題提出

現(xiàn)存在一種DVD在線租賃服務，會員通過對喜歡的DVD在線下單，網(wǎng)站就會以快遞的方式將DVD送達至會員手中。會員可同時訂購多張DVD，并且按照其偏愛程度進行排序。網(wǎng)站會根據(jù)目前現(xiàn)有的DVD數(shù)量以及會員訂單情況進行分發(fā)，其中網(wǎng)站約束每個會員每個月租賃次數(shù)不得超過2次，且最多獲得3張DVD。會員瀏覽完所借DVD之后，只需將DVD放進網(wǎng)站提供的信封里寄回（郵費由網(wǎng)站承擔）。

現(xiàn)在，網(wǎng)站準備引進一批新的DVD，通過問卷調查會員，得到了時下DVD受歡迎的主流類型。此外，歷史數(shù)據(jù)顯示，60%的會員每月租賃DVD兩次，而另外40%只租賃一次。那么在既定的會員數(shù)量下，網(wǎng)站對不同類型的DVD各需要準備多少張，才可以保證想要看到并且能在一個月內看到該DVD的會員至少達到50%，才可以保證在三個月內看到該DVD的會員至少達到95%。

2串行模型建立

假設既定會員人數(shù)為100000人。

分類：A類會員：租賃頻率為2次/月的會員；B類會員：租賃頻率為1次/月的會員；

說明：會員的身份隨時有可能發(fā)生變化，但是從大樣本上看，A類會員和B類會員在總人數(shù)中的比率必須分別為60%和40%；同一張碟在一個月內最多被允許租借兩次；該網(wǎng)站租賃DVD處于一種供不應求的狀態(tài)。

假設：A類會員在每月一號租借的碟十五日歸還，再租借其他的碟到月底歸還；B類會員在一日租借碟，到月底歸還。

定義：表示在每月第一批次租借碟的會員中，A類會員所占比例；表示B類會員所占比例；表示一個月內看到第種碟片的總人數(shù)；表示需要采購的第種碟片的數(shù)量。

這里認為抽樣調查的結果和一般意義下的統(tǒng)計規(guī)律相吻合。

根據(jù)上述假設，可以認為一張碟在一個月內至多被租出兩次。

首先，我們就DVDl的購買情形做分析。根據(jù)表中數(shù)據(jù)可知，占調查人數(shù)總數(shù)的20%。則在總人數(shù)為10萬的前提下，一個月內希望看到DVDl的人數(shù)總共有20000個，又，所以至少要保證10000人能看到DVDl。因為會員分為A、B類，且A類會員占60%，若我們所保證的會員10000人都是A類會員，此時所需購買的DVDl數(shù)目最少，為5000張；在20000個會員中最多有8000個B類會員，而如果20000個人中恰好包含了這8000個會員，此時所需購買DVDl數(shù)目最多，為9000張。

然而，事實是不可能保證這10000人都是A類會員，但至少可以說明所需購買DVDl的數(shù)量必須大于等于5000張。假設，則看到DVDl的A類會員數(shù)服從于分布，則一個月內看到DVDl的人數(shù)應為。若，即此次模擬購買張DVDl是可以確保在一個月期間，會員中想要借到DVDl的人，至少50%可以成功借到DVDl。若在的條件下，我們重復大量模擬實驗（規(guī)定試驗次數(shù)次），有次使得成立，我們就認為購買張DVDl能以99%的概率確保，在一個月期間內會員群體中想要看到DVDl的人，至少50%可以成功借取DVDl。此時，即為所求。因為5000張是購買DVDl的最低限制，若在的條件下，經(jīng)過重復大量模擬實驗，并沒有實現(xiàn)使得成立的次數(shù)，我們就令，即在之間重復大量模擬實驗，直到找到我們所期望的以盡可能高的概率值保證結果成立的。其他種類的DVD碟數(shù)的購買量都可以類似地求解，先計算最少購買量，然后再做模擬仿真實驗找尋結果。

針對保證在三個月內至少95%的會員能夠看到DVD這一情況，仍以DVDl為例，我們可以做類似的處理，若購買張，那么第一個月內希望看到DVDl的A會員人數(shù)應服從于分布，第二個月內希望看到DVDl的A會員人數(shù)應服從于分布，第三個月內希望看到DVDl的A會員人數(shù)應服從于分布。則三個月內總共能看到此碟的總人數(shù)為，若，我們便可以確保本店會員至少有95%的人在三個月期間可以成功借到這個DVD。其他種類的DVD碟數(shù)的購買量都可以類似地求解，先計算最少購買量，然后再做模擬仿真實驗找尋結果。