模擬競賽-DVD在線租賃 PPT課件

DVD在線租賃 問題提出 1 問題分析 2 假設條件 3 模型建立與求解 4 模型評價 5 2 隨著信息時代的到來 電子商務已成為一個重要的商業(yè)途徑 在線DVD租賃就是其中一種典型的經營方式 但在實際的經營過程中還是存在很多問題 下面我們從復雜的現實情況中考慮一個典型的情景 鑒于業(yè)務量的考慮 網站有必要采用會員制度 顧客需繳納一定數量的月費成為會員 會員對哪些DVD有興趣 只要在線提交訂單 網站就能立即了解他們的需求 并通過快遞的方式盡可能滿足要求 會員提交的訂單內容包括他對哪幾張DVD感興趣 對不同的DVD的偏愛度 用數字表示 這些DVD是基于其偏愛程度排序的 網站會根據手頭現有的DVD數量和會員的訂單進行分發(fā) 每個會員每個月租賃次數不得超過2次 每次獲得3張DVD 會員看完3張DVD之后 只需要將DVD放進網站提供的信封里寄回 郵費由網站承擔 就可以繼續(xù)下次租賃 問題提出 3 為深入研究網站的經營策略 我們從以下幾個角度由淺入深得進行考察 1 至少準備多少張 才能保證希望看到該DVD的會員中至少50 在一個月內能夠看到 若要求保證在三個月內至少95 的會員能夠看到呢 1 由于DVD的更新速度很快 網站必須時常更新現有產品 因此在現有會員中隨機抽取1000個會員進行調查 以得知愿意觀看不同DVD的人數 表1 1給出了其中5種DVD的數據 雖然網站規(guī)定每位會員每月只能借兩次DVD 但從歷史數據顯示 60 的會員每月租賃DVD兩次 而另外的40 只租一次 現在我們假設網站現有10萬個會員 并已經知道會員對DVD的需求 以及會員每月訂DVD的規(guī)律 問題是應該至少準備多少張 才能保證希望看到該DVD的會員中至少50 在一個月內能夠看到 如果要求保證在三個月內至少95 的會員能夠看到呢 表1 1對1000個會員調查的部分結果 問題提出 4 為深入研究網站的經營策略 我們從以下幾個角度由淺入深得進行考察 1 至少準備多少張 才能保證希望看到該DVD的會員中至少50 在一個月內能夠看到 若要求保證在三個月內至少95 的會員能夠看到呢 2 如何對手中已有的DVD進行分配 以使所有會員的滿意度和達到最大 2 盡可能多的滿足會員是經營中的一大目標 但每個會員對不同DVD的偏愛度是大相徑庭的 雖然他們都對該DVD下了訂單 但最后得到該張DVD收到的效果差別很大 所以還要考慮會員滿意度的問題 表1 2列出了網站中20種DVD的現有張數和當前需要處理的100位會員的在線訂單 如何對手中已有的DVD進行分配 以使所有會員的滿意度和達到最大 D001 D020表示20種DVD C0001 C0100表示100個會員 會員的在線訂單用數字1 2 表示 數字越小表示會員的偏愛程度越高 數字0表示對應的DVD當前不在會員的在線訂單中 表1 2現有DVD張數和當前需要處理的會員的在線訂單 表格格式示例 問題提出 5 為深入研究網站的經營策略 我們從以下幾個角度由淺入深得進行考察 1 至少準備多少張 才能保證希望看到該DVD的會員中至少50 在一個月內能夠看到 若要求保證在三個月內至少95 的會員能夠看到呢 2 如何對手中已有的DVD進行分配 以使所有會員的滿意度和達到最大 3 作為網站經營管理員 如何決定每種DVD的購買量 以及如何對這些DVD進行分配 才能使一個月內95 的會員得到他想看的DVD 并且滿意度最大呢 問題提出 3 在實際的經營過程中 不可能像剛才討論的兩個問題這么簡單 我們不可能將顧客的滿意率與他們的滿意度割裂開來分開研究 可以說這是兩個問題是相互牽制的關系 假設表1 2中DVD現有數量全部為0 作為網站經營管理人員 如何決定每種DVD的購買量 以及如何對這些DVD進行分配 才能使一個月內95 的會員得到他想看的DVD 并且滿意度最大呢 只有弄清楚這個問題 我們才能初步的對DVD在線租賃問題有個認識 6 問題一類似于 貨物存儲問題 Inventoryproblem 基本思路是跟蹤DVD在一個月 三個月 內的流動情況 目標是計算出DVD的流轉次數 然后再結合滿意率要求得出所需準備的DVD數量 問題二類似于 分配問題 或 指派問題 Assignmentproblem 我們可以對偏愛度進行適當的處理以滿足我們的要求 0 1規(guī)劃是處理該問題的最佳方法 因此如何使用這一方法將是研究問題二的關鍵 問題三看似是問題一與問題二的結合 存貯 分配 但實際要復雜得多 他綜合考慮一個月內DVD的購買 分配方案 是一個多目標線性規(guī)劃 從經濟效益看 在保證95 以上會員一個月內看到想看的DVD的情況下 希望購買盡量少的DVD 從社會效應看 則要盡可能多地考慮讓總的滿意度最大 這時 可以將多目標變?yōu)閱文繕艘?guī)劃 以求得一個經濟與社會效益的綜合最優(yōu) 由于問題三牽涉到兩次分配 而對會員滿意率的理解又有多種解釋 因此目標及約束函數會和問題一 問題二有很大差別 而問題三的模型又可從當前滿意度最大和一段時間內滿意度最大兩個角度來考慮 問題分析 7 1 對1000名會員的調查足以反映10萬名會員對于各種DVD的需求及喜好2 所有會員提交訂單的時間是隨機的3 一個月的天數為30天4 會員中有60 的會員每月租賃DVD兩次 40 的會員每月租賃DVD一次5 會員只有在需要再次租賃DVD時 才會將上次租賃的DVD歸還6 會員臨近兩次借的DVD種類不會重復7 每位會員每月至少租賃1次8 會員本次提交后沒得到該DVD 則他下次仍要看該DVD 且偏愛度不變9 每類租賃出的DVD有60 在每月租賃2次的會員中 40 在每月租賃1次的會員中10 公司收到訂單時不知道此會員在一個月內會借一次或兩次 假設條件 在實際建模中還會遇到其他問題 比如問題一中可以淡化會員每次借三張的條件 即會員每次借的DVD數量不固定 問題二中不考慮多次分配的問題 問題三中對顧客滿意率的不同理解 因此 我們將在以下的討論具體問題時再給出 8 模型建立與數值求解 第時間節(jié)點上第種DVD的可分配量 所有會員中愿意觀看第種DVD的人的概率 所有會員中每月借2次的人的概率 需要滿足的會員比例 會員總數 所考慮的時間跨度 即月份數 第個會員對第種DVD的偏愛程度 第個會員對第種DVD的滿意度 分配變量 表示第個會員得到第種DVD 否則為0 網站第種DVD的現有數量其余特殊的變量將在后面的討論中具體說明 參數與變量說明 9 模型建立與數值求解 問題一的模型與求解 問題一是簡化的情形 在制定方案時 暫時不考慮每個會員每次最多借3張DVD的限制 也不考慮各種DVD間產生的影響及數量間的橫向聯系 單獨考慮每種DVD的準備量 如上所述 我們稱每個月只租賃一次DVD的會員為1類會員 每個月租賃兩次的會員為2類會員 雖然借一次和兩次的會員并不固定 但其占總體會員的比例是一定的 由于每個月租賃兩次DVD的會員的不確定性 無法預知每種DVD到底會借給哪類會員 因此 在制定購買方案時我們分別考慮悲觀情況估計及均值估計兩種方式 問題一包含兩個部分 一是至少準備多少張DVD 才能保證希望看到該DVD的會員中至少50 在一個月內能看到 二是至少準備多少張DVD 才能保證在三個月內至少95 的會員能夠看到該DVD 我們分別稱上述兩種情況為 一月情況 和 三月情況 三月情況 是 一月情況 的延續(xù) 10 模型建立與數值求解 問題一 悲觀情況估計 一個月 假設DVD1其購買量為 從表1可以認為想看DVD1的有2萬人 而會員一個月借1次或借2次是隨機的 這就可能出現極端的情況 即第一次分配時正好所有1類會員都分配到了DVD1 我們把這種情況稱為悲觀情況 則的一部分首先被會員總數40 的1類會員借走了 而且在該月不會歸還 那么 為了保證至少有50 的會員在一個月內能看到該DVD 則DVD1總的購買量應滿足 同理 設為愿意看第種DVD的人的概率 可從表1中將愿意看該DVD的人數除以總人數可獲 則5種DVD的購買量為 11 模型建立與數值求解 問題一 悲觀情況估計 三個月 從 一月情況 我們可以推廣到 三月情況 如果 則每次分配都將只能由每月借一次的會員的到DVD 這樣三個月中DVD1的流動量就僅為 為了保證至少有50 的會員在一個月內能看到該DVD 那么此時DVD1總的購買量應該滿足同理 對于其余4種DVD的購買量有 為保證三個月內至少95 的會員看到他想看的DVD 每種DVD的購買量為 12 模型建立與數值求解 問題一 均值情況估計 現實中 每天都會有訂單提交 也有DVD歸還 而且都是服從參數為的泊松分布 考慮平均情況 認為 60 的會員15天歸還DVD 40 的會員一個月歸還 即對于每張DVD有60 的可能15天流通一次 40 的可能30天流動一次 假設所有會員在每個月的某天 不妨為1號 提交訂單 那些2類會員也集中在15號歸還并提交下一份訂單 則可以發(fā)現上述的簡化是泊松分布的平均情況 因此 在處理時可以不考慮每個會員的具體租賃 歸還的時間 而只考慮每個月兩次的分配方案 即1號和15號的分配方案 同時 在DVD租賃出去后 對于某種DVD 是均勻的分布在1類會員和2類會員中 即在15號 該DVD將有60 歸還 我們用下圖表示租賃情況 每塊代表長度為15天的時段 上方的箭頭表示該時刻借出的數量 下方表示歸還的數量 則初始時刻有張可用于分配 第二次 第四次 第六次 第一次租賃 第三次 第五次 時間 13 模型建立與數值求解 問題一 均值情況估計 一月 對于 一月情況 僅觀察上圖中的前兩段 在分配時 每張DVD都有60 的可能被分配給一月個借2次的會員 40 的可能分配給每月借1次的 在初始時刻會將所有DVD借出 因此即表示網站對的購買量 而問題目標則是要求出的最小值 以達到效益的最優(yōu) 由假設可知 第1個月月中有的歸還 另外40 仍在會員中 這時網站可將的借出 則與有如下關系 這樣就可以計算在一個月中的流通量即一個月內DVD的流通量為月初購買量的1 6倍 稱這個 1 6 為 一月流通系數 那么DVD一個月最小購買量可通過以下公式來計算 14 模型建立與數值求解 問題一 均值情況估計 一月 由表1得到1000人中愿意觀看每種DVD的概率分別為 由于這1000人為10萬人的子樣本 也可表示10萬人中愿意觀看每種DVD的概率 則表示10萬人中愿意觀看第種DVD的人 經計算 各種DVD的最少月初購買量為 總的最少購買量S 12033 15 模型建立與數值求解 問題一 均值情況估計 三月 該情況需要考慮6個時段 而且各個時段節(jié)點互相影響 在 一月情況 中已經知道與之間的關系 在第3個時間點 會有張DVD歸還 觀察張DVD的組成 第1個時間點有40 的DVD分配給了1類會員 則在第3個時間點歸還 數量為 而對于第2個時間點中收回的部分DVD同樣有60 的可能分配給2類會員 40 的可能分配給1類會員 因此在第3個時間點 會有60 的人歸還 數量為 則第3個時間點收回的來源于兩個部分 分別為第1時間點借給 一類會員 的DVD以及第2個時間點借給 二類會員 的DVD 所以有 三個月內6DVD租出數如下 第一次 第二次 第三次 第四次 第五次 第六次 由此 可以得出一個通用的遞推公式 16 模型建立與數值求解 問題一 均值情況估計 三月 通過上面的遞推公式就可以建立與 一月情況 相似的模型 經計算 各種DVD的最少月初購買量為 總的最少購買量S 8147 由上面的遞推公式可得 三月情況 中DVD的流通量 4 49 為 三月流通系數 17 模型建立與數值求解 問題一 理論證明 事實上 不必認為所有人都在1號來借DVD 以DVD1為例 設某種DVD一個月內被看到1次的概率為0 4 被看到2次的概率為0 6 則其服從分布 為使想看該DVD的會員中至少50 在一個月內能夠看到 即要成立的概率盡可能大 不妨取 由于是獨立同分布的 且的數量很大 由中心極限定理知 近似服從正態(tài)分布 將其化為標準正態(tài)分布即為 查表并求解得 同理也可推出其他解 由此證明了均值情況下的估計是完全可行的 18 模型建立與數值求解 問題一 一般情況推廣 在上面的基礎中 我們把模型推廣到范圍更廣的現實經濟生活中 假設通過問卷調查分析推算出任意客戶群體的借閱分布情況 設為2類會員的概率 為需要滿足的會員比例 為所考慮的時間跨度 即月份數 為會員總數 則可得到下面更一般的帶約束的線性規(guī)劃模型 這里人設DVD種類為5種 19 模型建立與數值求解 問題二的模型與求解 問題二是在現有一定數量DVD的前提下 如何分配以使會員總的滿意度最大 這與 分配問題 或 指派問題 Assignmentproblem 有很多相同點 我們可以通過一些變化來使求解 分配問題 的模型能運用于該問題 我們把問題二中 100個會員對DVD的需求 理解為 需要完成的100項任務 20種DVD數量 理解為 有個人可以承擔這些任務 會員對于不同DVD的偏愛度 理解為 不同人去完成不同工作的效率 通過類比就能把分配問題的模型運用到問題二中了 分配問題最常用的方法是0 1型整數規(guī)劃 在具體使用前 還需要將每個會員對不同DVD的偏愛度轉化為滿意度 因為我們的目標是總體滿意度最大 從表1 2中可以看到 會員的在線訂單用數字1 2 表示 數字越小表示會員的偏愛程度越高 數字0表示對應的DVD當前不在會員的在線訂單中 通過觀察我們用一個大于9的固定數值來減偏愛數 把這個差值作為滿意度 20 模型建立與數值求解 問題二 參數定義 1 設矩陣為偏愛度矩陣 矩陣中的元素為表1 2中的偏愛數 表示第個會員對的偏愛數 越小表示會員的滿意程度越高 為1時最高 為0時表示客戶沒有下訂單 于是就得到了偏愛度矩陣 2 設矩陣為滿意度矩陣 矩陣中的元素為滿意度 表示第個會員對第的滿意度 可通過如下算法獲得 3 令為分配變量 表示第個會員得到 表示未分配給第個會員 由此得到我們要求的分配矩陣 通過矩陣就能應用0 1規(guī)劃進行求解 4 令表示的現有數量 則有數量矩陣 5 令表示所有會員滿意度的總和 我們的目標就是求出其最大值 21 模型建立與數值求解 問題二 模型建立 1 因為表1 2中的數字0意義特殊 不直接與滿意度產生關系 0代表該DVD沒有出現在訂單中 即會員不需要看該DVD 從分配費用考慮 避免把該DVD分配給會員 根據的定義 不妨認為 則時 也等于0 即避免了上述情況的發(fā)生 2 由于一次最多只能借3張 那么就有 又分配給各會員的數量肯定不超過現有數量 所以 由以上分析可得問題二的模型 用MATLAB的YALMIP工具箱 或LINGO軟件 實現對此題0 1規(guī)劃模型的求解 22 模型建立與數值求解 問題二 模型改進 約束條件改進 根據上述模型的求解 我們發(fā)現又些會員沒有分配到3張DVD 即他們的需要沒能被滿足 從網站的社會效益考慮 這樣的情況會導致網站客戶的流失 所以希望在滿足所有會員都能借到3張DVD的前提下 再通過會員總滿意度最大來決定分配方案 這就需要對上面的模型做一些改進 我們可以將改為 則得到模型 23 模型建立與數值求解 問題二 模型改進 約束條件改進 以上修改 約束條件加強了 可能導致模型無可行解 事實通過LINGO程序也發(fā)現該模型無解 因為約束條件中規(guī)定了不能分配給會員不要的DVD 而會員每次都被分到3張 則網站至少有300張DVD 而現僅有303張 只比最低限度多3張 則當某DVD需求較大時就會供不應求 所以要放寬條件1 才能找到最優(yōu)解 最優(yōu)值在第165次迭代后得到Z 2024 以上兩個模型的結果是相同的 由于約束條件的放寬 后一個模型的迭代次數較少 則在說明每個會員一次能借到3張DVD不會影響會員整體滿意度 而且從模擬結果看 改進后的對原有分配策略影響不大 24 模型建立與數值求解 問題二 模型改進 滿意度定義改進 以上的討論都是基于用一個固定數去減會員偏愛數作為滿意度來分析的 但存在一定的不合理性 比如 當看到了最想看的DVD時 心理上滿足是非常大的 但當僅僅得到了第二想看的DVD 那滿足感會大打折扣 而如果僅得到了第三想看得DVD 滿足感會更低 但與僅獲得第二想看的DVD相比 也許失落感并不會如沒有獲得第一想看的DVD那么大 所以 如果只是簡單得把會員訂單中的DVD進行了相同差別的處理 無法表示出會員的真實滿意度差別 所以我們想到了用偏愛數的倒數來表示會員的滿意度 對滿意度矩陣的元素重新定義 把新定義的滿意度代入上述模型中 并由LINGO程序計算 最優(yōu)值在第54次迭代后得到Z 153 9984 我們對分配策略的分析發(fā)現 該結果與上一個模型相比并沒有太大的變動 這是因為兩種滿意度的定義其實質是一樣的 25 模型建立與數值求解 問題三的模型與求解 在現實的網站經營中需要綜合考慮問題一 二 這就需要我們進一步討論問題三的模型 它需要考慮兩次分配方案 但我們可以簡化為僅考慮當前時間點下如何用最小的DVD購買來滿足95 的會員并找出最佳分配方案使會員總滿意度最大 那么如何將這兩個目標同時放入一個目標函數呢 最簡單的方法就是相加 由問題二知道 目標是使所有會員滿意度總和盡可能地大 而且每種DVD數量是固定的 但問題三中DVD的購買量是自己定的 因此設置一個新的變量表示當前需要購買的數量 則表示總的購買數量 而且從盈利角度考慮總的購買數量越小越好 所以我們可以將目標函數定如下 26 模型建立與數值求解 問題三 等權情況 會員總體滿意度與DVD購買量權重相等 針對 使一個月內95 的會員得到想看的DVD 的要求 可以參照問題一的處理方法 從表1 2中統(tǒng)計出原意觀看的人數占全體會員比例 結果如下 由問題一的流通量可得由于網站可自由決定其DVD的購買量 則有 為了計算上的方便直觀 我們選擇用10減會員偏愛數的來定義會員滿意度 并建立模型 最優(yōu)值在第85次迭代后得到 Z 1878 27 模型建立與數值求解 問題三 不等權情況 會員總體滿意度與DVD購買量權重不相等 如果不考慮會員總體滿意度與DVD購買量之間的權重差異 這會導致其中某個目標對整個函數的影響被過分得夸大 所以有必要進行標準化 1 先來看的最大值和最小值 對于當前的分配 最理想的是每位會員都得到了最想看的3張DVD 此時就達到了最大值 通過表1 2的統(tǒng)計我們得到最大值為 最差情況就是會員得到了3張沒有出現在訂單中的DVD 此時達到最小值0 2 再來看的最大值和最小值 由 每位會員每次分配到3張DVD 和 一個月內95 的會員得到想看的DVD 的約束 則由計算出各種DVD最小購買量 相加得的最小值522 只要某DVD出現在訂單中 就應將其購入 也就是說保證會員可以拿到他想看的任何一張DVD 則會員在一個月中的滿意率為100 此時 統(tǒng)計各種DVD的購買量并相加得最大值864 28 模型建立與數值求解 問題三 不等權情況 會員總體滿意度與DVD購買量權重不相等 我們取和的最大值及最小值的平均數1200和693來確定各自權重 因此 它們的權重分別為和 建立帶權重的模型 同樣用LINGO程序對其進行求解 最優(yōu)值在第116次迭代后得到Z 688 43 DVD購買總量為532張 比較兩個模型的計算結果 發(fā)現DVD的購買量和分配策略沒有發(fā)生變化 這是由于和的數量級相差并不大 29 模型建立與數值求解 問題三 綜合最佳方案 以上的決策是基于當前時刻的考慮 事實上 60 的DVD會面臨二次分配 考慮所有會員在一個月內總的滿意度就需要對二次分配進行分開考慮 在此我們假設 不要求會員每次借DVD都必須被分配到3張 但分配到的必須是在其訂單中的 而每次只有拿到3張的會員才能算滿意 由于要對二次分別進行討論 所以需要設置兩個新的變量 1 第一次分配的分配變量 表示第一次分配時第位會員得到了表示第一次分配時第位會員未得到2 第二次分配的分配變量 表示第二次分配時第位會員得到了表示第二次分配時第位會員未得到因此在等權情況下目標函數應為 30 模型建立與數值求解 問題三 綜合最佳方案 約束條件 1 假設中會員在這一個月不會兩次借相同的DVD 則可以表示為 2 每次分配每位會員最多得到3張DVD 即 3 第一次分配時最多只能分配出新購入的DVD 則 4 考慮前后兩分配的關系 平均情況下 可以近似的認為每種DVD每次都有60 借給2類會員 40 借給1類會員 所以有 不等式右邊表示網站在第二次分配時可用于分配的數量 5 因為規(guī)定在一個月中必須有95 的會員被滿足要求 所以DVD總的數量需大于1 6 0 95 100 3 1 6 0 05 100 2 472 相應的約束條件為 31 模型建立與數值求解 問題三 綜合最佳方案 權重設置 對于理想情況是兩次分配都給會員最想看的3張DVD 而且會員不想看已經看過的DVD 則一個中月獲得的最大滿意度