最省用工方案.doc

2012年河南理工大学数学建模竞赛承 诺 书我们仔细阅读了新余学院大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）： B 我们的参赛报名号为（如果设置报名号的话）： 参赛队员 (打印并签名) ：1. 李楠楠 2. 张筠若 3. 代振 日期： 2012 年 7 月 18 日评阅编号(评阅老师填写)： 132012河南理工大学数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最省用工方案摘 要本文解决的是A公司同B劳务公司签订劳务合同后，在保证满足A公司的聘任数量下，为降低A公司的成本和实现B公司的最省用工方案准则”，根据不同职位工人的日工资、属性，分别安排相应的人数参与不同的促销方案，使A公司的付款总额达到最小。对于问题一：针对B公司所能提供的服务以及A公司的需求，从聘任数量、价格、优惠模式出发将装配工，维修工以及主管统一编号。根据各个工种参加优惠模式的不同建立了01矩阵，根据不同的工种收费的情况我们建立了他们的收费矩阵，由于在A公司给出聘任数量时我们为了找出使A公司的成本最少的各个工种的具体数目我们建立了待求矩阵。对于01矩阵考虑到可能有一部分工种是单独被A公司选用的故我们增加了一个模式六，模式六即为不参加题中所给的任一种优惠情况，而是单独的被A公司选用。对于收费矩阵考虑到70元两人和100元两人的情况我们将参加两个活动的人在参加此活动时的日工资均变为和，这对我们计算A公司的最低成本时并没有影响。而对于收费矩阵在计算时遇到的关于维修工半价活动的复杂性问题，我们根据题目对这部分数据进行了特殊的处理，来等价代替原有数据，即求得这部分数据的数学期望。而对于收费矩阵中关于部分员工未参加的那些活动下的日价由于没有参加我们将这部分日价设置为一个很大的数（在这里我们设为元，当然也可以设为其他的较大的数）以保证不被A公司选到。表示A公司针对职位的工种的聘任数量。则等效目标函数,在这里我们暂且把它看作虚拟目标函数，它与真正的目标函数可以达到一样的效果，故我们可以通过它来确定使A公司成本达到最小的具体方案。在A公司聘任数量确定时的线性约束条件下，可求得的最小值。对于问题二，其实质是根据问题一建立的模型进行计算，将问题二中的数据代入一中进行计算就可以了，这样也可以确定、检验模型是否与实际拟合。关键词：矩阵 线性规划 约束条件 0-1模型 数学期望 一 问题重述A公司为了节约成本，和B劳务公司签订劳务合同，提出“最省用工方案准则”，即同时满足多个节省方案时，以节省最多为准则。目前B劳务公司提供，1种主管职位，5种装配工职位，7种维修工职位。B劳务公司提供用工促销方案如下（计价为日工资）：1). 主模式1：1个主管+任选1个装配工或维修工优惠20元；2). 主模式2：1个主管+任选2个装配工或维修工（可以1个装配工，1个维修工）优惠40元；注：优惠的意思是：如单聘任，总价为各单项的和，参加模式后，付款为总价减去优惠款；3). 70元两人：付70元可以聘任参加“70元两人活动职位”中的两人；4). 100元两人：付100元可以聘任参加“100元两人活动职位”中的两人；5). 维修工第二人半价：第一人原价，第二人半价（两人价格不一样时，只能价格低的享受半价，高的是原价，两人可以相同）。举例如下：如A公司聘任了1个主管职位（190元），1个维修工“职位6”（60元），1个装配工“职位1”（45元）。不优惠的总价：190+60+45=295（元）1）组合1：主模式1（含维修工“职位6”）+1个装配工“职位1”，付款：（190+45）-20+60=275（元）2）组合2：主模式1（含维修工“职位1”）+1个装配工“职位6”，付款：（190+60）-20+45=275（元）3）组合3：主模式2（含维修工“职位6”，装配工“职位1”），付款：（190+45+60）-40=255（元）4)组合4：主管职位+70元两件（含维修工“职位6”，装配工“职位1”），付款：190+70=260（元）根据“最省用工方案准则”，A公司只需按最优组合“组合3”付款，付255元，获得所有方案中的最省用工方案。问题1:为了帮助B公司实现“最省用工方案准则”，请你给出解决该问题的一般数学模型，在A公司提出聘任数量时，就能按要求给出最优组合方案。你的方案最好具有一定的扩展性，在聘任数量、价格、模式优惠条件修改后，系统也能自动计算最优组合。如果职位有几百或几千种，促销方案有几十或几百时，问题应该怎样解决？问题2:按 “表一”职位情况和公司聘任数量，给出方案的最优组合方式，付款总额，优惠额度（每日），并提供最优组合明细。表一 职位情况和A公司聘任人员数量职位单价（日工资）属性主模式70元两人100元两人维修工第二人半价聘任数量（人）职位145装配工1YY6职位260装配工2YYY5职位380装配工3YY3职位4110装配工4Y1职位580装配工5Y1职位660维修工1YYY2职位750维修工2YYY2职位890维修工3YYY1职位980维修工4YYY1职位10100维修工5YY1职位11100维修工6YY1职位12120维修工7Y1职位13190主管职位Y10注：表中“Y”表示参加该模式或优惠方案二 模型假设与符号说明2.1模型假设假设1：对于A公司的任何聘任数量，B公司都能够满足，不存在供不应求的情况假设2：对于两个价钱相等的工人同时参与其中一个优惠方案时，即他们之间存在合作关系时，认为他们将所得的日工资总额均分，以此来作为他们各自的日工资2.2符号说明符号符号说明0-1模型矩阵收费矩阵待求矩阵 (或或)职位为的工种参加（或不参加）种优惠方案（; ），表示职位为的工种参加第种优惠方案参加，表示职位为的工种不参加第种优惠方案职位为的工种参加第种优惠方案的日工资（； ）当职位为的工种不参加第种优惠方案时我们为了使职位为的工种一定不能在他没有参加的优惠方案下被A公司选用设置了此时职位为的工种的日工资为一个很大的数这里选用了安排职位的工人参加第种优惠方案的人数（；）等效目标函数目标函数三 数据分析3.1矩阵中数据处理分析收费矩阵中主要有三个数据需要处理：其一，对于参加“70元两人”促销方案的工人，不计较这两人的日工资私下如何分，对于目标函数Z来讲，需求的是这两人工资的总和。因此在数据处理时，我们可以假设他们的日工资分别为元，即对应的。同理，对于参加“100元两人”促销方案的工人，对应的。这不会影响的求解。其二，建模的过程中，我们发现，种维修工职位中，参加“维修工第二人半价”促销方案的有种。根据B公司提供的促销方案要求，当A公司需要个参与此促销方案的维修工时，共有种选择，每个工人的日工资可能是中的任一种。而这种选择中要选择哪种不但要看哪种日工资最划算而且更重要的是要根据A公司的实际需求还要结合其他的几种优惠方案，这就增加了我们在计算时的难度。为了降低计算的难度我们对数据做如下合理的处理。参与此促销方案后，因为日工资元在这种职位中，价格最低，所以如果是以维修工半价的优惠方案被选用，那么它的日价一定会是元。而日工资，元在这种职位中，价格最高，所以如果以维修工半价的优惠方案被A公司选用那么就一定是以全价付款。由于对于其他的几个价位当他们被A公司选用时我们不能确定是以半价付费还是以全价付费。这就相当于投资风险盈利的问题由此我们想到了概率模型根据不同的情况出现的权重来计算它的权重，根据权重来计算它的期望并以此作为它在此优惠方案下的日工资。鉴于此实际问题处理的复杂性，我们引入期望，计算日工资元的职位在这种促销方案中的期望值作为他们的日工资。如对于这个价位的工种是以维修工第二人半价的优惠方案被选用时，另外一个与他合作的维修工可能是这几个价位的维修工，那么对于这个价位的维修工来说，共有种情况，其中日工资为元的（即这个价位的维修工是在此活动中是作为第一人付费为全价的）有50元的这一种情况故权重为，日工资为的（即在此活动中此维修工是作为第二人付费为半价的）有四种情况故权重为，而对于出现的的情况所占权重为，他们的总日工资为，根据假设二每个人所得的日工资应为。由此我们可以算得价位为元的维修工以维修工半价的优惠方案被A公司选用时的期望为,我们将此期望作为此维修工参加此优惠方案时的日工资。同理我们可以算得的期望分别为其中和的维修工以维修工两人半价的优惠方案被A公司选用时的日工资与我们上面分析所得的数据相吻合。其三，对于不参加第种优惠方案的职位工人的日工资，因为其不参加该活动，在求等效目标函数的最小值时，为避免计算过程中职位工人被误认为、安排到参与了第种优惠方案，我们将其对应的日工资设定为元，当然，这个可以用其他较大的数值代替，这对等效目标函数的求解没有影响。这种数据处理的目的是，当工种没有参加第种优惠方案时，因为要使等效目标函数最小，这就保证了这个工人一定不会被选中参加第种优惠方案，这就为实际问题的计算提供了方便。假如不用这种方式处理，仍将职位的工人日工资记为原数值，如元等，若求得的最小值表明此工人将被安排到参与第种优惠方案，这与实际显然不符。所以，这种数据处理的方式是必要的、合理的。四 问题的解答4.1矩阵的建立将0-1模型矩阵、收费矩阵、待求矩阵，根据数据分析过程中对数据所做的一系列处理，并由表一的数值可以写出三个同型矩阵为：= 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1= 1.0e+004 * 0.0045 0.0035 2.0000 2.0000 0.0045 0.0060 0.0035 0.0050 2.0000 0.0060 0.0080 2.0000 0.0050 2.0000 0.0080 0.0110 2.0000 2.0000 2.0000 0.0110 0.0080 2.0000 2.0000 2.0000 0.0080 0.0060 0.0030 2.0000 0.0037 0.0060 0.0050 0.0025 2.0000 0.0025 0.0050 0.0090 2.0000 0.0050 0.0071 0.0090 0.0080 2.0000 0.0050 0.0057 0.0080 0.0100 2.0000 2.0000 0.0100 0.0100 0.0100 2.0000 2.0000 0.0100 0.0100 0.0120 2.0000 2.0000 2.0000 0.0120 0.0190 2.0000 2.0000 2.0000 0.0190 = x11, x12, x13, x14, x15 x21, x22, x23, x24, x25 x31, x32, x33, x34, x35 x41, x42, x43, x44, x45 x51, x52, x53, x54, x55 x61, x62, x63, x64, x65 x71, x72, x73, x74, x75 x81, x82, x83, x84, x85 x91, x92, x93, x94, x95 x101, x102, x103, x104, x105 x111, x112, x113, x114, x115 x121, x122, x123, x124, x125 x131, x132, x133, x134, x135那么，用Matlab软件计算后，可得= 45*x11, 35*x12, 0, 0, 45*x15 60*x21, 35*x22, 50*x23, 0, 60*x25 80*x31, 0, 50*x33, 0, 80*x35 110*x41, 0, 0, 0, 110*x45 80*x51, 0, 0, 0, 80*x55 60*x61, 30*x62, 0, 75/2*x64, 60*x65 50*x71, 25*x72, 0, 25*x74, 50*x75 90*x81, 0, 50*x83, 285/4*x84, 90*x85 80*x91, 0, 50*x93, 567/10*x94, 80*x95 100*x101, 0, 0, 100*x104, 100*x105 100*x111, 0, 0, 100*x114, 100*x115 120*x121, 0, 0, 0, 120*x125 190*x131, 0, 0, 0, 190*x135 Z=sum(sum(D) Z =45*x11+60*x21+80*x31+110*x41+80*x51+60*x61+50*x71+90*x81+80*x91+35*x12+35*x22+30*x62+25*x72+50*x23+50*x33+50*x83+50*x93+75/2*x64+25*x74+285/4*x84+567/10*x94+45*x15+60*x25+80*x35+110*x45+80*x55+60*x65+50*x75+90*x85+80*x95+100*x101+100*x111+120*x121+190*x131+100*x104+100*x114+100*x105+100*x115+120*x125+190*x135 且知目标函数的约束条件为： 45*x11+35*x12+45*x15=6; 60*x21+35*x22+50*x23+60*x25=5; 80*x31+50*x33+80*x35=3; 110*x41+110*x45=1; 80*x51+80*x55=1; 60*x61+30*x62+75/2*x64+60*x65=2; 50*x71+25*x72+25*x74+50*x75=2; 90*x81+50*x83+285/4*x84+90*x85=1; 80*x91+50*x93+567/10*x94+80*x95=1; 100*x101+100*x104+100*x105=1; 100*x111+100*x114+100*x115=1; 120*x121+120*x125=1; 190*x131+190*x135=10; (x12+x22+x62+x72)%2=0; (x23+x33+x83+x93)%2=0; (x64+x65+x66+x67+x68+x69)%2=0;%表示求余，则目标等效函数，用Lingo软件编程求解后可得最少收费为元。4.2模型的扩展上述模型的建立，是以表一为依据确定的矩阵元素数值，因此，该模型首先可用于解决问题二，即在工人的日工资、参加优惠方案情况、A公司聘任数量已知的情况下，使A公司的付款总额最小且能实现B公司的最省用工方案准则。在问题一中，提出了使模型具有扩展性的要求，也就是在A公司聘任数量、工人日工资的价格、模式优惠条件修改后，职位达到几百或几千种，优惠方案有几十或几百种时，系统也能自动计算最优组合，使问题得到解决。对于这一要求，仍可以以这个模型为基础，需要修改的是三个同型矩阵中的行列数、元素数值以及目标函数的约束条件。当优惠方案变化时，针对不同的优惠模式，工人的日工资要采取灵活的数据处理方式，等效处理后，使数据具有合理性、正确性，从而可使目标函数的表达式清晰易处理。如上述模型对“70元两人”“100元两人” 和“维修工人第二人半价”优惠方案的灵活数据处理。五 模型的评价、改进5.1模型的评价优点：(1)0-1模型矩阵的建立和收费矩阵对应项元的设置。和分别表示职位i的工人选择第j种促销方案和不选择第j种促销方案。当时，工人对应的日工资设置为元，由此使得结果倾向于不选择收费如此高昂的员工，这样，就避免了不参加第j种优惠方案的工人被误安排的结果，与实际结果一致。(2)对于“70元两人”、“100元两人”和“维修工第二人半价”这三种优惠方案，根据假设二，对工人日工资数据的处理，避免了实际问题中涉及过多的未知量，且对目标函数的求解没有产生影响。这种处理方式是比较合理的。(3)整个的解题过程，是先以问题二为入口，根据表一把三个矩阵元素记为具体的数值，这样使得问题的解决具体易理解。之后，通过对这个具体问题的解决，把模型推广到A公司聘任数量、工人日工资价格、模式优惠条件、职位和促销方案变化时最优组合的计算，使得问题的解决过程清晰明了，易于理解。(4)在建立线性规划模型中,是以求解等效目标函数为目的的，而实际的目标函数与等效目标函数最终的答案是一致的，等效目标函数与实际问题中的目标函数存在一定的差值,这个差值的具体数值，我们是可以在算出等效目标函数之后代入计算出来.(5)我们很好的利用了数学中的转化思想,将一个看似复杂的问题转化为一个简单且易与解决的问题。缺点：模型建立的过程中，是以求解等效目标函数为目的的，而实际的目标函数与等效目标函数最终的答案是一致的，等效目标函数与实际问题中的目标函数存在一定的偏差,我们没有能够写出最真实的目标函数的具体表达式.5.2模型改进(1)在解决问题一对模型进行推广的过程中，我们认为，如果B公司推出新的优惠方案，对不同职位的工人的日工资的处理应当采取合理灵活的数据分析方法。但是如何具体实施这种方法和采取怎样的假设条件，还需要在实际问题中进一步探讨。六 参考文献1谢金星，薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，322-324，2011年附录1.问题二模型程序A=1 1 0 0 1;1 1 1 0 1;1 0 1 0 1;1 0 0 0 1;1 0 0 0 1;1 1 0 1 1;1 1 0 1 1;1 0 1 1 1;1 0 1 1 1;1 0 0 1 1;1 0 0 1 1;1 0 0 0 1;1 0 0 0 1; A = 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 B= 1.0e+004 * 0.0045 0.0035 2.0000 2.0000 0.0045 0.0060 0.0035 0.0050 2.0000 0.0060 0.0080 2.0000 0.0050 2.0000 0.0080 0.0110 2.0000 2.0000 2.0000 0.0110 0.0080 2.0000 2.0000 2.0000 0.0080 0.0060 0.0030 2.0000 0.0037 0.0060 0.0050 0.0025 2.0000 0.0025 0.0050 0.0090 2.0000 0.0050 0.0071 0.0090 0.0080 2.0000 0.0050 0.0057 0.0080 0.0100 2.0000 2.0000 0.0100 0.0100 0.0100 2.0000 2.0000 0.0100 0.0100 0.0120 2.0000 2.0000 2.0000 0.0120 0.0190 2.0000 2.0000 2.0000 0.0190syms x11 x12 x13 x14 x15 x21 x22 x23 x24 x25 x31 x32 x33 x34 x35 x41 x42 x43 x44 x45 x51 x52 x53 x54 x55 x61 x62 x63 x64 x65 x71 x72 x73 x74 x75 x81 x82 x83 x84 x85 x91 x92 x93 x94 x95 x101 x102 x103 x104 x105 x111 x112 x113 x114 x115 x121 x122 x123 x124 x125 x131 x132 x133 x134 x135; C=x11 x12 x13 x14 x15;x21 x22 x23 x24 x25;x31 x32 x33 x34 x35;x41 x42 x43 x44 x45;x51 x52 x53 x54 x55;x61 x62 x63 x64 x65;x71 x72 x73 x74 x75;x81 x82 x83 x84 x85;x91 x92 x93 x94 x95;x101 x102 x103 x104 x105;x111 x112 x113 x114 x115;x121 x122 x123 x124 x125;x131 x132 x133 x134 x135; C = x11, x12, x13, x14, x15 x21, x22, x23, x24, x25 x31, x32, x33, x34, x35 x41, x42, x43, x44, x45 x51, x52, x53, x54, x55 x61, x62, x63, x64, x65 x71, x72, x73, x74, x75 x81, x82, x83, x84, x85 x91, x92, x93, x94, x95 x101, x102, x103, x104, x105 x111, x112, x113, x114, x115 x121, x122, x123, x124, x125 x131, x132, x133, x134, x135D=A.*B.*C D = 45*x11, 35*x12, 0, 0, 45*x15 60*x21, 35*x22, 50*x23, 0, 60*x25 80*x31, 0, 50*x33, 0, 80*x35 110*x41, 0, 0, 0, 110*x45 80*x51, 0, 0, 0, 80*x55 60*x61, 30*x62, 0, 75/2*x64, 60*x65 50*x71, 25*x72, 0, 25*x74, 50*x75 90*x81, 0, 50*x83, 285/4*x84, 90*x85 80*x91, 0, 50*x93, 567/10*x94, 80*x95 100*x101, 0, 0, 100*x104, 100*x105 100*x111, 0, 0, 100*x114, 100*x115 120*x121, 0, 0, 0, 120*x125 190*x131, 0, 0, 0, 190*x135Z=sum(sum(D) Z =45*x11+60*x21+80*x31+110*x41+80*x51+60*x61+50*x71+90*x81+80*x91+35*x12+35*x22+30*x62+25*x72+50*x23+50*x33+50*x83+50*x93+75/2*x64+25*x74+285/4*x84+567/10*x94+45*x15+60*x25+80*x35+110*x45+80*x55+60*x65+50*x75+90*x85+80*x95+100*x101+100*x111+120*x121+190*x131+100*x104+100*x114+100*x105+100*x115+120*x125+190*x135 syms y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13; Y=y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 Y = y1, y2, y3, y4, y5, y6, y