基于0-1整数规划的就业选择模型.doc

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 孔甜程 2. 王成 3. 刘子恒 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 8月 15 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：基于0-1整数规划的就业选择模型摘要：当今社会，大学生就业问题已引起了广大的关注，针对这一现象，假设有25个用人单位和25位应聘者，每个人及每个单位的基本条件和要求条件各不相同，某高等院校学生就业指导中心就如何根据用人单位和大学生的基本条件和要求条件进行牵线搭桥，使用人单位和大学生签订就业协议。本文利用0-1型整数规划建立了大学生就业问题的数学模型，并结合实际提出了通用可行的算法。首先将用人单位的五个要求条件和应聘者的五个要求条件等级A、B、C、D、E分别做量化处理为5、4、3、2、1，得到用人单位和应聘者的基本条件量化矩阵和要求条件量化矩阵，得出满意度分量。然后确定最优方案模型，被选人员对用人单位的满意度最大时的人员选取即为所求，从而建立了应聘人员最优选取的0-1整数规划模型关键词：0-1整数规划 条件量化 满意度1 问题重述目前，随着我国高等教育的持续发展，大学生毕业人数逐年增多，大学生就业难问题已经引起了社会各方的广泛关注。一方面，大量大学生毕业后不能很快找到工作，实现就业；一方面，用人单位也苦于不能招收到适合的人才。这种现象的持续，严重影响到我国高等教育和国民经济的持续发展。本题要求根据所给原始数据，解答以下五个问题：问题一:在尽量满足双方各自要求的条件下，给出一种最佳的配对方案，并使得配对成功率尽可能高；问题二：给出一种25个用人单位和25位应聘者可同时配对的最佳方案，使得全部配对成功的可能性最大；问题三:如果25个用人单位和25位应聘者都相互了解对方的条件和要求，让每个用人单位和每位应聘者都可以做出一次选择，只有当双方都选中对方时才能够配对成功，每方只有一次选择机会。请问25个用人单位和25位应聘者应该如何选择，使得自己配对的可能性最大？按你的选择方案最多能配对成功多少对？问题四：由于用人单位工作要求的限制，如用人单位5和用人单位13只招聘男生，用人单位9和用人单位20只招聘女生会对你上面的结论产生怎样的影响？问题五：你的方法对一般的情况，即N个应聘人员M个用人单位时，是否可行？2 模型假设(1)每位应聘者只能被一个用人单位录取，一个单位只能录取一个一个人；（2）题目所给出的条件的评价是客观真实的；（3）用人单位和应聘者的相关数据是透明的，即双方都知道；（4）应聘者的基本要求在综合评价中的地位是等价的；（5）用人单位的五项基本要求对应聘者的影响地位是同等的；（6）双方在选择的时候是理智的。3 符号说明用人单位的基本条件量化矩阵用人单位的要求条件量化矩阵应聘人员的基本条件量化矩阵应聘人员的要求条件量化矩阵1,2,3,4,5分别表示五个基本条件表示用人单位的序号表示应聘单位的序号用人单位对应聘人员在第方面的满意度分量用人单位对应聘人员的综合满意度应聘人员对用人单位在第方面的满意度分量应聘人员对用人单位的综合满意度应聘人员与用人单位之间的综合满意度应聘人员与用人单位之间的相互满意度应聘人员应聘成功的概率4 问题分析 该问题是现实生活中的实际问题，主要就是确定合理配对方案，使得在尽量满足个人要求条件下，使配对成功率尽可能的高。对于问题（1），在充分考虑用人单位和应聘者的要求条件的前提下，综合双方的满意度，尤其将双方的基本条件和要求条件有机结合而综合确定一个优化指标，建立起优化模型（或算法）,给出最优的配对问题。对于问题（2），要是25个用人单位和25位应聘者同时配对，使得全部同时成功的可能性（概率）最大。对于问题(3),因为每个人只有选择一次，能不能配对成功取决于双方是不是同时选中对方，即要看双方彼此的满意度如何。实际上，假如一个用人单位对一个应聘者的满意度最高，但是对的满意度不一定最高，即若选择，但不一定选择。因此与不一定配对成功，反之亦然。现在的问题是谁选谁，使得配对成功的可能性最大呢？对于问题(4),要基于前面三个方案来看，可对应每个方案中这四个用人单位最优配对中其配对对象的性别讨论前面的最优方案是否受到影响。若和这几个用人单位的工作要求限制符合，则对整个方案而言，不会造成影响；若不符合，则需先考虑用人单位的工作要求。寻求他们的最优方案，将余下的用人单位和应聘者如上如上三问那样建立模型，并求解。对于问题（5），只有把上述模型推广到N个应聘者M个用人单位时情况。在建模时，其模型与前述问题的模型一致，只需将的取值推广到M，的值推广到N即可。5 模型建立与求解5.1 问题一的模型建立与求解针对问题一要使配对成功率尽可能的高，也就是给出一种方案，使得25个用人单位和25位应聘者的配对成功指数之和最高。5.1.1 模型准备5.1.1.1 条件量化处理 对于每位应聘者对用人单位的工资待遇、工作条件、劳动强度、晋升机会、深造机会的五个要求条件和每个用人单位对应聘者的基本知识面、专业知识面、动手能力、计算机能力、表达能力的五个要求条件等级A、B、C、D、E分别作量化处理为5、4、3、2、1.于是根据上表可以得到用人单位和应聘者的基本条件量化矩阵和要求条件量化矩阵以及满意度分量分别记为：则， 最后，用人单位对应聘者的综合满意度为应聘者对用人单位的综合满意度为则用人单位与应聘者之间的综合满意度为5.1.2 模型建立在充分考虑应聘人员的意愿和用人单位期望要求的情况下，寻求更好的录用分配方案。应聘人员的意愿包括对用人单位的工资待遇、劳动强度等五个要求条件，即可用应聘人员对用人单位的综合满意度来表示，用人单位对应聘者的期望要求也用综合满意度来表示。一个好的录用方案就是使二者的满意度都尽可能的高，故就是要求两者之间的综合满意度之和最大，可以建立如下优化模型：目标函数：约束条件: 5.1.3 模型求解根据上述建立的模型中，可以看出这是一个0-1整数规划问题，在求解过程中，我们用lingo软件寻求其最优配对方案，并得出其最优解为。方案如下:配对成功率最高方案用人单位P1P2P3P4P5P6P7P8P10应聘人员Q8Q17Q20Q12Q11Q23Q18Q19Q15满意度1.60.211.61.611.61.20.2用人单位P11P12P13P14P15P16P17P18P19应聘人员Q21Q3Q7Q2Q13Q22Q28Q4Q10满意度10.811.60.80.20.60.80.8用人单位P20P21P22P24P25应聘人员Q6Q16Q5Q18Q9满意度1.21.60.81.80.6表一 5.2 问题二的模型建立与求解针对问题二求解得出的匹配方案应使25个用人单位与25位应聘者全部配对成功，且配对的成功率之和最大。5.2.1 模型建立要使25个用人单位与25位应聘者同时配对且配对成功率尽可能高，记25个用人单位与25位应聘者成功配对概率为则目标函数为： 由于，正比于，所以目标函数等价于令，则，约束条件:：5.2.2 模型求解在求解过程中，应聘人员与用人单位的综合满意度有为0的情况，但是在求解全部配对成功的概率最大的情况时，利用对数函数求解过程中，0不能求出来，得出负无穷大的情况，为了方便计算，我们把负无穷换为-10000。至于求解过程，与问题一的方法一致。我们利用lingo软件计算出其最优配对方案，并得出其最优解z=-3.9。（注意：其最优解并不是所求概率，只是其变化趋势与概率等价，当Z最大时，其概率就最大。）方案如下：全部配对成功的概率最大方案用人单位P1P2P3P4P5P6P7P8P9应聘人员Q19Q14Q10Q23Q5Q21Q1Q9Q12满意度10.30.810.810.810.6用人单位P10P11P12P13P14P15P16P17P18应聘人员Q11Q24Q7Q18Q25Q3Q6Q16Q4满意度0.81110.810.60.80.8用人单位P19P20P21P22P23P24P25应聘人员Q22Q2Q13Q20Q8Q17Q15满意度0.811.210.410.8表二5.3 模型改进 首先要注意两个事实：其一，如果基本条件比的要求条件差很多的话，则对的第项条件的满意度就越小，反之亦然。也就是说，如果一方的实际条件比对方期望的条件差距越大，则对方对另一方失望就越大，即满意度就越小。其二，如果的基本条件比的要求条件高，则对的第项条件的满意度就会增加，但不会增加很多。即当一方的实际条件高于对方期望的条件是，则对方对另一方的满意度增加不会太大。也就是说，人们对不满意程度的敏感远远大于对满意程度的敏感，即用人部门对应聘者的满意程度降低一级可能导致用人单位的极大不满，但满意度增加一级只能引起满意程度的少量。为此现在在模型一的基础上把满意度稍加修改。如果（）基本条件（）达不到（）的要求()，即（）时，给它赋值（）它是一个负值，体现了当一方实际条件低于期望的条件是，则对方对他失望（相当于要求条件）就会增加差距越大，失望度就越大，相应的满意度就越小。显然改进后成功的解决了上述所提的问题，所以更加合理。满意度矩阵中的各个分量分别表示如下：至于模型的求解与优化与模型一类似，我们通过原始数据得出满意度，然后编程求的结果：方案如下:配对成功率最高方案用人单位P1P2P3P4P5P6P7P8P9应聘人员Q14Q6Q22Q13Q5Q23Q9Q4Q12满意度1.60.80.80.80.8111.60.6用人单位P10P11P12P13P14P15P16P17P18应聘人员Q2Q21Q24Q18Q25Q20Q16Q7Q19满意度0.410.810.810.40.80.4用人单位P19P20P21P22P23P24P25应聘人员Q3Q10Q8Q15Q11Q1Q17满意度10.61.80.80.40.80.6表三5.4 模型比较在模型一中，我们忽略了用人单位对应聘者综合满意度的负值及应聘者对用人单位综合满意度的负值，也就是说在模型一中，我们认为满意度及不满意度（满意度为负值时）对配对成功率的影响是一样的，但在实际情况中，人们对不满意度的敏感度比满意度的敏感度高的多，于是在模型改进中，我们对双方的满意度定义加以修正。根据得出的结论可知，模型改进后的得到的配对方式更优。5.5 问题三的模型建立与求解针对问题三，由于每个人只能选择一次，能否配对成功主要取决于双方能否同时选中对方，则需从双方彼此的满意度来看。要使配对率最高，则要使双方的相互满意度达到最大。5.5.1 模型建立用人单位与应聘者的相互满意度定义为当与满足可能配对的条件时：当与不满足可能配对的条件时：配对成功率达到最大取决于双方的相互满意度之和达到最大值。于是根据0-1整数规划模型，得出目标函数为,其约束条件与问题一相同，即为5.5.2 模型求解 根据上述模型，编程可以得到最优解为Z=11.57，其配对方案如下:配对方案用人单位P1P2P3P4P5P6P7P8P11应聘人员Q22Q23Q19Q12Q18Q13Q15Q24Q14满意度0.490.20.40.80.60.40.570.70.7用人单位P12P13P14P15P17P18P19P20P21应聘人员Q7Q8Q21Q5Q16Q2Q10Q11Q3满意度0.490.570.70.40.40.40.40.70.7用人单位P22P24P25应聘人员Q6Q20Q4满意度0.70.70.6表四5.5.3 模型改进由于只能选择一次，要使成功率尽可能的大，则不能单纯的只考虑自己对对方的满意度。因为在实际中，一个用人单位对一位应聘者的满意度高，但不代表这位应聘者对该用人单位的满意度高，即选择了，但不一定选择，于是两人不一定配对成功。因此，要使每一个个体配对成功的可能性最大，要保证双方的满意度差值不能太大。 所以我们定义了双方满意度差值的绝对值为差异指数，那么双方满意度差异指数为：=要使其配对成功率最高，则要使双方满意度差异指数最小，故根据上述分析，利用0-1整数规划模型，得出目标函数：，约束条件如下;5.5.4 模型求解根据模型，我们得出最优解Z=2.00，其最佳配对方式如下：配对方案用人单位P1P5P6P7P8P12P14P22应聘人员Q7Q21Q23Q8Q20Q4Q3Q24满意度0.20.20.20.60.20.20.20.2表五5.5.5 模型比较在问题三中，模型一我们定义了相互满意度，相互满意度等于用人单位对应聘者的满意度与应聘者对用人单位的满意度的几何算术平均数，在实际情况中，如果一方的满意度过高，另一方的满意度偏低，两者相差太大，但是由于前者的满意度过高，使得相互满意度还是有点高，那样得出的结论可能会与实际情况有偏差。于是我们在模型改进中，又定义了满意度差异指数，要使配对成功率尽可能高，则要求满意度差异指数之和最小，这样得出的配对方案更具可取性，并且得出的结论更符合实际情况。5.6 问题四的模型建立与求解针对问题四，我们只需将工作要求也作为过滤条件，在已知的方案中对配对进行筛选，使得在满足工作条件的情况下，配对尽可能成功。由于用人单位的工作要求的限制，用人单位招收有男女限制。这样对于用人单位5,13,9,20,的要求条件就多了一项，其他的不变。首先我们根据用人单位的用人限制，再对照前面已求的方案对照，如果已有的配对方案与用人单位的要求不冲突，那么我们就不用在进行优化，通过比较，发现已有方案不符合用人单位的要求，则我们用条件过滤的方法首先对特殊用人单位进行筛选。5.6.1 模型建立对于工作单位的性别要求，针对问题一，我们在进行条件筛选时，只需在模型一的基础上强化约束条件。目标函数：其约束条件:5.6.2 模型求解根据lingo软件求的Z=23.6，其配对方式如下：配对成功率最高方案用人单位P1P2P3P4P5P6P7P8P10应聘人员Q6Q17Q13Q15Q21Q11Q8Q7Q22满意度1.60.20.80.811.61.81.60.2用人单位P11P12P13P14P15P17P18P19P20应聘人员Q5Q24Q20Q4Q23Q19Q18Q12Q14满意度0.80.80.81.610.40.81.61.2用人单位P21P22P24P25应聘人员Q16Q10Q2Q3满意度1.60.81.61表六对于问题二和问题三的求解方法也问题一类似，只需在约束条件方面加强。问题二的配对方式：Z=，全部配对成功的概率最大方案用人单位P1P2P3P4P5P6P7P8P9应聘人员Q22Q6Q13Q3Q20Q24Q25Q9Q14满意度10.80.81110.810.4用人单位P11P12P13P14P15P16P17P18P19应聘人员Q19Q2Q16Q15Q23Q12Q7Q4Q10满意度0.8111.210.80.80.80.8用人单位P20P21P22P23P24P25应聘人员Q18Q1Q21Q8Q17Q5满意度10.810.410.8表七根据上表，可得由于用人单位的条件限制，不可能全部配对成功，用人单位10未找到合适的应聘人员，应聘人员11未找到合适的工作。问题三的配对方式：配对方案用人单位P1P8P11P16P17P20P21P25应聘人员Q7Q8Q21Q3Q6Q16Q24Q23满意度0.20.60.20.20.20.20.20.2表八5.7 问题五的求解对于N个应聘人员和M个用人单位的情况，如上的方法都实用，只是两个优化模型的规模会变大，给求解带来一定的困难。实际中，用人单位个数M不会太大，当应聘人员的个数N达到一定的程度时，可以分步处理。对于问题一而言，取所有应聘人员综合满意度与用人单位的综合满意度的均值，即可得，对于满足应聘人员应该淘汰掉