學術產出-Theses
Article View/Open
Publication Export
-
題名 男女配對的模型及應用
Men and women matching models and its applications作者 詹博翔
Chan, Po Hsiang貢獻者 吳柏林<br>劉明郎
Wu, Po Lin<br>Liu, Ming Long
詹博翔
Chan, Po Hsiang關鍵詞 指派問題
配對問題
男女配對問題
assignment problem
matching problem
men and women matching problem日期 2012 上傳時間 1-Feb-2013 16:53:15 (UTC+8) 摘要 近年來，越來越多單身男女希望能夠透過網路交友平台找到自己的另一半。本論文考慮一個網路交友平台的經營，期望能夠讓每位參與者都找到適合彼此的另一半。我們使用工作指派問題的數學模型整合配對問題及穩定室友問題的概念建構男女配對問題的數學模型。並且考慮多位交友對象、拒絕對象與分級制度等問題，分別提出不同的數學模型。最後，我們使用隨機產生的資料模擬參與者的雙向配度，以GAMS軟體求解，分析不同的配對結果，亦探討不同模型的難易度及求解所需之運算時間。
In recent years, more and more single women and men hope that they can find their Mr. or Mrs. Right through the internet dating platform. This paper considers the operation of an internet dating platform which expects each participant to find the other half of each other. We propose mathematical models of the women and men matching problem by using the mathematical model of the assignment problem and integrating the idea of matching problem as well as the stable roommate problem. We also consider the problems of multiple dating objects, matching with rejection, and classification member. Finally, a simulate study will be performed by using the randomly generating data to simulate the two-way matching degree of each pair of participants. We analyze the different matching results obtained by the different models. We also present the difficulty of different models and the solution times.
第一章 緒論...1 1.1 研究動機...1 1.2 研究目的與架構...2 第二章 文獻回顧...3 2.1 配對問題...3 2.2 指派問題...6 2.3 速配指數...8 第三章 建構男女速配問題的數學模型...9 3.1 指派問題的數學模型...9 3.2 男女速配問題基本數學模型建構...11 3.3 多位交友對象的數學模型...16 3.4 特殊狀況的男女速配問題數學模型...19 第四章 模擬研究...23 4.1 不同模型在相同資料下的配對差異...24 4.1.1 男女人數相同配對人數為一人的配對結果...24 4.1.2 男女人數不同配對人數為一人的配對結果...26 4.1.3 配對人數為多人的配對結果...29 4.1.4 有拒絕條件的配對結果...32 4.2 比較不同模型的難易度及求解運算時間的差異...34 4.2.1 探討不同模型難易度...34 4.2.2 比較不同模型求解運算時間的差異...38 第五章 結論與建議...40 參考文獻...42參考文獻 Berger, A., J. Gross, and T. Harks, 2010, The k-Constrained Bipartite Matching Problem: Approximation Algorithms and Applications to Wireless Networks, Proceedings of the 29th conference on information communications, 2043-2051, IEEE Press Piscataway, NJ, USA. Brooke, A., D. Kendrick, and A. Meeraus, 1998, GAMS-A User’s Guide, The Scientific Press, Redwood City, CA. Burkard, R. E. and P. Butkovič, 2003, Max Algebra and the Linear Assignment Problem, Mathematical Programming Series B 98, 415-429 . Erkut, E., R. L. Francis, T. J. Lowe, and A. Tamir, 1989, Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems, Operations Research 37(3), 447-461. Gale, D. and L. S. Shapley, 1962, College Admissions and the Stability of Marriage, The American Mathematical Monthly 69(1), 9-15. Gusfield, D. and R.W. Irving, 1989, The Stable Marriage Problem: Structure and Algorithms, The MIT Press, Boston, MA. Hauskrecht, M. and E. Upfal, 2001, A Clustering Approach to Solving Large Stochastic Matching Problems, Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, 219-226, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. Irving, R. W., 1985, An Efficient Algorithm for the “Stable Roommates” Problem, Journal of Algorithms 6, 577-595. Irving, R. W. and D. F. Manlove, 2002, The Stable Roommate Problem with Ties, Journal of Algorithms 43(1), 85-105. Kong, N. and A. J. Schaefer, 2006, A Factor 1/2 Approximation Algorithm for Two-Stage Stochastic Matching Problems, European Journal of Operational Research 172, 740-746. Kuhn, H. W., 1955, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly 2, 83-97. Ronn, E., 1990, NP-Complete Stable Matching Problems, Journal of Algorithms 11, 285-304. Shmoys, D. B. and Tardos É., 1993, An Approximation Algorithm for the Generalized Assignment Problem, Mathematical Programming 62, 461-474. Taha, H. A., 2007, Operations Research: An Introduction, Pearson, NJ. Tamir, A. and J. S. B. Mitchell, 1998, A Maximum b-Matching Problem Arising From Median Location Models with Applications to the Roommates Problem, Mathematical Programming 80(2), 171-194. Taşkın, Z. C. and T. Ekim, 2011, Integer Programming Formulations for the Minimum Weighted Maximal Matching Problem, Optimization Letters 6(6), 1161-1171. Yang, L., M. Nie, Z. Wu, and Y. Nie, 2008, Modeling and Solution for Assignment Problem, International Journal of Mathematical Models and Methods in Sciences 2(2), 205-212. 王竣玄，民91，著色數的規畫模型及應用，國立政治大學應用數學系碩士論文。 吳柏林，2005，模糊統計導論方法與應用，五南書局，臺北市。 陳彥豪，民99，區間最小距離及其應用於網站男女最速配模式，國立政治大學應用數學系碩士論文。 描述 碩士
國立政治大學
應用數學研究所
98751013
101資料來源 http://thesis.lib.nccu.edu.tw/record/#G0098751013 資料類型 thesis dc.contributor.advisor 吳柏林<br>劉明郎 zh_TW dc.contributor.advisor Wu, Po Lin<br>Liu, Ming Long en_US dc.contributor.author (Authors) 詹博翔 zh_TW dc.contributor.author (Authors) Chan, Po Hsiang en_US dc.creator (作者) 詹博翔 zh_TW dc.creator (作者) Chan, Po Hsiang en_US dc.date (日期) 2012 en_US dc.date.accessioned 1-Feb-2013 16:53:15 (UTC+8) - dc.date.available 1-Feb-2013 16:53:15 (UTC+8) - dc.date.issued (上傳時間) 1-Feb-2013 16:53:15 (UTC+8) - dc.identifier (Other Identifiers) G0098751013 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/56877 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學研究所 zh_TW dc.description (描述) 98751013 zh_TW dc.description (描述) 101 zh_TW dc.description.abstract (摘要) 近年來，越來越多單身男女希望能夠透過網路交友平台找到自己的另一半。本論文考慮一個網路交友平台的經營，期望能夠讓每位參與者都找到適合彼此的另一半。我們使用工作指派問題的數學模型整合配對問題及穩定室友問題的概念建構男女配對問題的數學模型。並且考慮多位交友對象、拒絕對象與分級制度等問題，分別提出不同的數學模型。最後，我們使用隨機產生的資料模擬參與者的雙向配度，以GAMS軟體求解，分析不同的配對結果，亦探討不同模型的難易度及求解所需之運算時間。 zh_TW dc.description.abstract (摘要) In recent years, more and more single women and men hope that they can find their Mr. or Mrs. Right through the internet dating platform. This paper considers the operation of an internet dating platform which expects each participant to find the other half of each other. We propose mathematical models of the women and men matching problem by using the mathematical model of the assignment problem and integrating the idea of matching problem as well as the stable roommate problem. We also consider the problems of multiple dating objects, matching with rejection, and classification member. Finally, a simulate study will be performed by using the randomly generating data to simulate the two-way matching degree of each pair of participants. We analyze the different matching results obtained by the different models. We also present the difficulty of different models and the solution times. en_US dc.description.abstract (摘要) 第一章 緒論...1 1.1 研究動機...1 1.2 研究目的與架構...2 第二章 文獻回顧...3 2.1 配對問題...3 2.2 指派問題...6 2.3 速配指數...8 第三章 建構男女速配問題的數學模型...9 3.1 指派問題的數學模型...9 3.2 男女速配問題基本數學模型建構...11 3.3 多位交友對象的數學模型...16 3.4 特殊狀況的男女速配問題數學模型...19 第四章 模擬研究...23 4.1 不同模型在相同資料下的配對差異...24 4.1.1 男女人數相同配對人數為一人的配對結果...24 4.1.2 男女人數不同配對人數為一人的配對結果...26 4.1.3 配對人數為多人的配對結果...29 4.1.4 有拒絕條件的配對結果...32 4.2 比較不同模型的難易度及求解運算時間的差異...34 4.2.1 探討不同模型難易度...34 4.2.2 比較不同模型求解運算時間的差異...38 第五章 結論與建議...40 參考文獻...42 - dc.description.tableofcontents 第一章 緒論...1 1.1 研究動機...1 1.2 研究目的與架構...2 第二章 文獻回顧...3 2.1 配對問題...3 2.2 指派問題...6 2.3 速配指數...8 第三章 建構男女速配問題的數學模型...9 3.1 指派問題的數學模型...9 3.2 男女速配問題基本數學模型建構...11 3.3 多位交友對象的數學模型...16 3.4 特殊狀況的男女速配問題數學模型...19 第四章 模擬研究...23 4.1 不同模型在相同資料下的配對差異...24 4.1.1 男女人數相同配對人數為一人的配對結果...24 4.1.2 男女人數不同配對人數為一人的配對結果...26 4.1.3 配對人數為多人的配對結果...29 4.1.4 有拒絕條件的配對結果...32 4.2 比較不同模型的難易度及求解運算時間的差異...34 4.2.1 探討不同模型難易度...34 4.2.2 比較不同模型求解運算時間的差異...38 第五章 結論與建議...40 參考文獻...42 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0098751013 en_US dc.subject (關鍵詞) 指派問題 zh_TW dc.subject (關鍵詞) 配對問題 zh_TW dc.subject (關鍵詞) 男女配對問題 zh_TW dc.subject (關鍵詞) assignment problem en_US dc.subject (關鍵詞) matching problem en_US dc.subject (關鍵詞) men and women matching problem en_US dc.title (題名) 男女配對的模型及應用 zh_TW dc.title (題名) Men and women matching models and its applications en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) Berger, A., J. Gross, and T. Harks, 2010, The k-Constrained Bipartite Matching Problem: Approximation Algorithms and Applications to Wireless Networks, Proceedings of the 29th conference on information communications, 2043-2051, IEEE Press Piscataway, NJ, USA. Brooke, A., D. Kendrick, and A. Meeraus, 1998, GAMS-A User’s Guide, The Scientific Press, Redwood City, CA. Burkard, R. E. and P. Butkovič, 2003, Max Algebra and the Linear Assignment Problem, Mathematical Programming Series B 98, 415-429 . Erkut, E., R. L. Francis, T. J. Lowe, and A. Tamir, 1989, Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems, Operations Research 37(3), 447-461. Gale, D. and L. S. Shapley, 1962, College Admissions and the Stability of Marriage, The American Mathematical Monthly 69(1), 9-15. Gusfield, D. and R.W. Irving, 1989, The Stable Marriage Problem: Structure and Algorithms, The MIT Press, Boston, MA. Hauskrecht, M. and E. Upfal, 2001, A Clustering Approach to Solving Large Stochastic Matching Problems, Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, 219-226, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. Irving, R. W., 1985, An Efficient Algorithm for the “Stable Roommates” Problem, Journal of Algorithms 6, 577-595. Irving, R. W. and D. F. Manlove, 2002, The Stable Roommate Problem with Ties, Journal of Algorithms 43(1), 85-105. Kong, N. and A. J. Schaefer, 2006, A Factor 1/2 Approximation Algorithm for Two-Stage Stochastic Matching Problems, European Journal of Operational Research 172, 740-746. Kuhn, H. W., 1955, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly 2, 83-97. Ronn, E., 1990, NP-Complete Stable Matching Problems, Journal of Algorithms 11, 285-304. Shmoys, D. B. and Tardos É., 1993, An Approximation Algorithm for the Generalized Assignment Problem, Mathematical Programming 62, 461-474. Taha, H. A., 2007, Operations Research: An Introduction, Pearson, NJ. Tamir, A. and J. S. B. Mitchell, 1998, A Maximum b-Matching Problem Arising From Median Location Models with Applications to the Roommates Problem, Mathematical Programming 80(2), 171-194. Taşkın, Z. C. and T. Ekim, 2011, Integer Programming Formulations for the Minimum Weighted Maximal Matching Problem, Optimization Letters 6(6), 1161-1171. Yang, L., M. Nie, Z. Wu, and Y. Nie, 2008, Modeling and Solution for Assignment Problem, International Journal of Mathematical Models and Methods in Sciences 2(2), 205-212. 王竣玄，民91，著色數的規畫模型及應用，國立政治大學應用數學系碩士論文。 吳柏林，2005，模糊統計導論方法與應用，五南書局，臺北市。 陳彥豪，民99，區間最小距離及其應用於網站男女最速配模式，國立政治大學應用數學系碩士論文。 zh_TW
