数据挖掘之综合案例

玫瑰有约问题问题的提出目前，许多城市大龄青年的婚姻问题已引起了妇联、工会和社会团体组织的关注。某单位现有20对大龄青年男女，每个人的基本条件都不同，如外貌、性格、气质、事业、财富等。每项条件通常可以分为五个等级：A、B、C、D、E，如外貌分别代表很好、好、较好、一般、差；财富分别代表很多、多、较多、一般、少等等。每个人的择偶条件也不尽相同，即对每项基本条件的要求是不同的。该单位拟根据他们的年龄、基本条件和要求条件进行牵线搭桥。下面给出20对大龄青年男女的年龄、五项基本条件和要求条件。一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。该单位希望根据每个人的情况和要求，建立数学模型解决如下问题：（1）在尽量满足个人要求的条件下，给出一种最佳的配对方案，并使得配对成功率尽可能的高；（2）给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大；（3）如果20对男女青年双方都互相了解对方的条件和要求，让每个人做出一次选择，只有当男女双方相互选中对方时才认为能够配对成功，每人只有一次选择机会，请问，这20对男女青年应该如何选择，使得自己配对成功的可能性最大？按你的选择方案最多能配对成功多少对？数据表1男青年的基本条件和要求条件男青年基本条件要求条件外貌性格气质事业财富年龄外貌性格气质事业财富B1ACBCA29AABBDB2CABAD29BABBCB3BBABB28BAABCB4CABBD28CABCDB5DBCAA30CBBBEB6CBCBB28BBCDCB7ABBDC30CBBDCB8BABCD30ABCCDB9ADCEB28AAACCB10DBAAA28ABADEB11BACDA32ABCDBB12ABCAB29BABBCB13BADEC28ACBBCB14AABBD30ACCDCB15ABBCC28AABCDB16DEBAA30AAAEEB17BABAD28BABBCB18ABACB31BBACCB19CDAAA29ABAEDB20ABCDE27BCBDB表2女青年的基本条件和要求条件女青基本条件要求条件外性气事财年外性气事财年貌格质业富龄貌格质业富G1ACCDA28BABADG2BABAD25CBBABG3CBAEA26BACBCG4ABBCD27AABBAG5BDCEC25ABCBBG6ACBCA26BABBCG7DCBAB30CBAACG8ABAEC31BABABG9AAACE26CBBBAG10BCDBB27BBAACG11ABBCB28CBABCG12BECEA26AABBEG13EACBB26CABCCG14BBCAA25BAABDG15CBAAC29BABBBG16BACDC28BABBAG17AEEDA25AADACG18AABBC28CABACG19BACCE25BBBAAG20DBACD29BBABB注：表中的要求条件一般是指不低于所给的条件模型的假设与符号说明假设：1、题目所给出的男女青年的评价是客观真实的。2、每个人在选择对方时都是理智的。3、五项条件在选择对方时所起的作用是相等的符号说明iB：第i个男青年jG：第j个女青年1j0jijx第i个男青年与第个女青年配对第i个男青年没有与第个女青年配对(0)ika：第i个女青年的基本条件量化指标(1)ika：第i个女青年对第j个男青年的要求条件量化指标(1)ikb：第i个男青年对第j个女青年的要求条件量化指标(0)ikb：第i个男青年的基本条件量化指标(0)()ijSk：第i个女青年对第j个男青年的的k项要求条件的量化指标(1)()ijSk：第i个男青年对第j个女青年的的k项要求条件的量化指标(0)ijS：第i个女青年对第j个男青年的综合满意度(1)ijS：第i个男青年对第j个女青年的综合满意度ijSS：第i个女青年与第j个男青年的综合相互满意度ijP：第i个女青年与第j个男青年的配对成功的概率TP：所给方案配对成功的概率(1)2020()ijSS：所有男青年对女青年的满意度矩阵(0)2020()ijSS：所有女青年对男青年的满意度矩阵d：男（女）青年的要求条件距离最高等级A的档数；h：男（女）青年的基本条件高出对方所要求条件等级的档数；模型准备1、条件的量化处理对于每个人的外貌、性格、气质、事业和财富五项条件的五个等级A、B、C、D和E，分别作量化处理，即赋予权重9,7,5,3,1.于是得到男女青年的基本条件量化矩阵和要求条件量化矩阵如下：(0)(0)95759597937797759773375995757797735797539351737999()79539975977931599773977553179979793979575399997531ikBb,,,,，，，，，(1)B：男青年的要求条件量化指标，用表格表示如下9977379775799755975357771775355773597553999559793197537797759577595535997539991179775779559791375737同理，可以得到女青年的基本条件量化指标(0)A和要求条件量化指标(1)(1)()jkAa2.条件过滤由于问题明确要求“男青年至多比女青年大5岁，或女青年至多比男青年大2岁，并且要至少满足个人要求5项条件中的2项”。在20对男女青年所有可能的配对中，首先将不满足这些基本条件的情况过滤掉，编程可以过滤掉58对组合。3.满意度确定（1）对单项条件的满意度要确定jG对iB的第k(1,20,15)ijk项条件的满意度。首先注意两个事实：事实一：如果iB的基本条件(0)ikb比jG的要求条件(1)jka差得越多，则jG对iB的第k项条件的满意度(0)()ijSk就越小，反之亦然。事实二：如果iB的基本条件(0)ikb比jG的要求条件(1)jka高，则jG对iB的第k项条件的满意度(0)()ijSk就会增加，但增加不会太多。即当一方的实际条件高于对方的期望（要求）条件时，则对方对另一方的好感（相对要求条件）增加不会太大。根据上面两个事实，先以女青年jG对男青年iB的第k项条件的满意度(0)()ijSk为例。若iB的实际条件比jG的要求差，那么jG对iB的该项指标的满意度将迅速减小，减小的速度一般会与jG的要求条件相差的档数有关，二者会成一定的比例关系。当iB的实际条件比jG的要求条件很大（例如，相差三个档次以上）时，则认为jG会对iB失去信心，即满意度为0.若iB的实际条件比jG的要求条件还要好，那么jG对iB的这项条件的满意度会略有增加，但增加的不会太大。根据实际情况，一般认为如果男青年iB的条件达到女青年jG的要求条件时，那么jG会以90%的可能性接受iB的这项条件，此时，可以认为jG对iB的第k项条件的满意度为(0)()0.9jiSk参考模糊数学的思想，可以定义jG对iB的第k项条件的满意度如下：(0)(1)(0)(0)(0)(1)(1)(0)(1)(1)(0)0.10.9,()0.9*,0,3jkikjkjijkikikjkikikjkhbadbSkbaabaab且同理可以定义iB对jG的第k项条件的满意度如下：(0)(1)(0)(1)(0)(1)(1)(0)(1)(1)(0)0.10.9,()0.9*,0,3ikjkikjiikjkjkikjkjkikhabdaSkabbabba且（2）综合满意度一对男女青年相互之间的综合满意度主要取决于对对方的各项条件的满意度(1)()ijSk和(1)()ijSk由假设，可以定义男青年iB对女青年jG的综合满意度为5(1)(1)11()5ijijkSSk，同理可以定义女青年jG对男青年iB的满意度如下：5(0)(0)11()5jijikSSk（3）相互满意度男青年iB与女青年jG的相互满意度定义为(1)(0),0ijjiijijijSSBGSBG当与满足可能配对的条件时，当与不满足可能配对的条件时模型的建立与求解问题（1）：根据问题的要求，要使在尽量满足个人要求的条件下，使配对成功率尽可能的高。事实上，我们可以用20对男女青年的满意度指标ijSS之和来刻画总的配对成功的成功率TP，于是问题归结为所有20对男女青年如何配对使得202011ijijijSSx有最大值，即问题转化为如下模型202011maxijijijzSSx2012011,1,2,...20.1,1,2,...2001ijiijjijxjSTxixor这是一个0——1规划问题，可以用匈牙利算法（或LINGO软件）求解，得到最优配对方案如下表，最优值（总满意度）为16.75132问题（1）的最优配对方案男B1B2B3B4B5B6B7B8女G4G18G15G20G2G5G3G13满意度0.84990.90950.88740.80160.89300.77770.83490.836男B9B10B11B12B13B14B15B16女G17G9G16G10G7G1G6G19满意度0.64650.93270.82960.82240.75680.92990.86740.7796男B17B18B19B20女G14G11G8G12满意度0.89720.90750.87840.7133问题（2）：要使20对男女青年同时配对，使得全部配对成功的可能性最大。记20对男女青年可同时配对成功的概率为,ijijPP，即问题为求,maxijijPP由于ijijPSS（配对成功比例与满意度成正比），则问题等价于求一个20对青年男女同时配对的方案，使目标函数202011maxijijijZSSP最大，其约束条件与问题（1）的条件相同。令ln()ijijCSS，考虑相应的目标函数202011max'ijijijzCx，约束条件不变，求解可以得到最优的配对方案如下问题（2）的最优配对方案男B1B2B3B4B5B6B7B8女G2G18G6G14G19G5G3G13满意度0.88120.90950.86120.86990.82230.77770.83490.83600.7577男B9B10B11B12B13B14B15B16女G11G20G11G17G7G12G15G9满意度0.75770.85060.84350.73390.75680.80750.83790.8501男B17B18B19B20女G16G8G4G10满意度0.81200.83980.85320.7259问题（3）：根据问题的分析可以建立该问题的对策模型。假设有两个虚拟的局中人：男青年和女青年，其策略集分别为1{|1,...20}iSBi和2{|1,...20}iSGi局中人男青年和女青年的赢利矩阵分别为(1)ijSS和(0)jiSS，于是构造一个二人非零和双矩阵对策模型。按照每个人的条件量化的原则，对于每个人来说，自己在每个异性心目中的地位——满意度的大学都是可以已知的。对策双方不应该追求自己的最高赢利，要保证配对的成功率，只要选择对策双方都能接受的策略，即确保男女双方相互选中对方，才是最理智的行为，于是，根据假设2，问题就是求给出的赢利矩阵的纳什平衡点的问题。通过求解此问题，得到最佳的配对成功为10对，具体如下表：表问题（3）的最优配对方案男B1B3B5B10B12B14B15B17女G15G18G19G9G2G6G4G14满意度0.85070.90990.82330.93270.88750.91750.84590.8972男B18B19女G11G8满意度0.90750.8784招聘公务员问题问题的提出我国公务员制度已实施多年，1993男10月1日颁布施行的《国家公务员暂行条例》规定：“国家行