《数学建模获奖专业论文工作指派问答.doc》由会员分享，可在线阅读，更多相关《数学建模获奖专业论文工作指派问答.doc（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、,河南理工大学2014年数学建模竞赛论文答卷编号（竞赛组委会填写）：题目编号：（ F ）论文题目： 工作的安排 参赛队员信息(必填)： 姓 名专业班级联系电话队员1机制11-5队员2机制11-5队员3计算机11-3 答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：评阅1.评阅2.评阅3. 工作的安排摘 要：工作指派问题是日常生活中常见的一类问题。本文所要研究就是在效率与成本的背景下，如何安排每个人员的工作分别达到以下三个要求：1、使得总的工作效率最大。2、使得总的成本最低。3、兼顾工作效率和成本，优化工作安排方案。对于问题一，该问题属于工作指派问题，要求使工作效率最大。为了得到最优的
2、安排方案，我们采用0-1规划模型，引入0-1变量，即其中一人负责某一项工作记作1，否则为0，然后与之对应的效率相乘，然后把所有的工作安排情况这样处理后，再求和作为目标函数。此外我们对该问题进行了如下约束：因为六个人刚好六份工作，所以每个人只能被安排一份工作，而且每份工作只允许一人来完成。最后在模型求解中我们应用lingo软件编程使目标函数值最大化，根据此时对应的0-1变量的所有值，最终得到最优安排方案。对于问题二，要求的方案使工作成本最低。该问题与问题一相似，只是求解的是目标函数的最小值，为此我们建立了成本最小化模型，该模型同样应用了0-1规划方法，然后用与问题一中相似的方法建立目标函数，然后
3、应用lingo软件编程使目标函数值最小，最终得到使成本最小的相应安排方案。对于问题三，该问题兼顾效率与成本,属于多目标规划。首先,数据标准化处理。给出的效率成本数据属于两个不同性质的指标，两个指标之间存在着不可公度性，而且两项的数值整体大小水平不一样，会有大数起主导作用的影响，如果不对两个指标的数据进行标准化，就会得到错误的结果，为此我们首先采用极值差方法，用matlab编程对两项指标数据进行标准化。经过极差变换后，两项指标值均在0和1之间。 对于此问题的多目标规划解决，我们采用理想点方法将多目标规划转化为单目标规划，建立了偏离理想点距离模型。所谓的理想点就是只考虑效率时得到的最大效率值为横坐
4、标，与以只考虑成本时得到的最小成本值为纵坐标组成的点。然后我们再求出任意工作安排方案对应的效率值与成本值组成的点。最后求出这两点之间的距离表达式，得到我们要求的目标函数。最后,在与问题一问题二相同的约束条件下，我们采用lingo编程使目标函数逐渐向理想点逼近（但永远达不到理想点），即：使目标函数达到最小值时，此时对应的工作指派方案在问题三情况下是最佳方案。关键词：0-1规划；数据标准化；多目标规划；偏离理想点距离模型；lingo一、问题重述已知有6个人，可以做6项工作，每个人做每项工作的效率和所用的成本如表中所示。表1：每个人做每项工作的效率工作人员工作1工作2工作3工作4工作5工作6人员13
5、51002人员2643254人员3142212人员4123331人员5213242人员6325466表2：每个人做每项工作的成本工作人员工作1工作2工作3工作4工作5工作6人员1481004人员212753119人员32104425人员4255794人员5527474人员6851081113建立数学模型回答下面的问题：1、 如何安排每个人的工作，使得总的工作效率最大。2、 如何安排每个人的工作，使得总的成本最低。3、 如何兼顾工作效率和成本，优化工作安排方案。二、问题分析对于问题一，要安排每个人的工作，使得总的工作效率最大。因为题目中的效率已经经过量化，所以要想反应效率的高低我们也可以通过数值
6、大小来反应工作安排后的效率高低。然而每个人的工作安排有很多种情况，为了简化问题，采用0-1规划模型，引入0-1变量，我们把其中一个人负责某项工作记作1，否则记作0，然后我们便可以把每个人工作安排的所有情况的效率与相应的0-1变量乘积的求和，便得到效率目标函数，而且考虑到lingo软件的强大优化求解能力，于是便可以借助lingo编程来求解实现目标函数的最大化，即工作效率综合的最大化，根据此时对应的0-1变量的所有值得到的工作安排方案就是最佳的。对于问题二，要求安排每个人的工作，使得总的成本最低，该问题与问题一相似，同样可以应用0-1规划模型，求出目标函数表达式然后应用lingo软件编程来求解目标
7、函数的最小值，便可得到最优工作分派方案。问题三，要兼顾效率与成本这两个指标，即让效率尽量最大的同时让成本也最小，来得到最优的分派方案。由于两个指标的性质不同，同时整体大小水平不一，所以第一步需要进行数据标准化，标准化方法有很多种，这里我们采用极值差方法对两项指标进行处理，经过极差变换后，两项指标值均在0和1之间。数据标准化处理处理后，要兼顾效率与成本，则效率和成本就都会偏离问题一、问题二中的最优值，如果所给的工作安排方案能使两者距各自最优值的偏移量最小化则就意味着效率和成本都得到了兼顾，而且相对最优。为此，我们便引入了理想点法，让任意安排方案得到的效率值与成本值组成的点距离理想点的距离最小化，
8、而得到最小值对应的工作分配方案，此过程的求解我们同样可以借助lingo软件编程来解决，最终能够实现问题三的要求。三、问题假设1.所有人对每个工作的效率与成本是定值，即不受外界影响；2.所有人都服从相应的安排；3.效率和成本重要程度相同；4只考虑成本与效率两个指标。四、符号说明:表示第人做第个工作的相应效率表示第人是否负责第个工作，如果负责记为1，否则为0；：表示只考虑效率时所有人的工作效率之和；：表示第人做第个工作的需要的成本；：表示只考虑成本时所有人工作所需成本之和；：表示标准化后的；：表示标准化后的：表示标准化后理想点。其中表示只考虑效率指标时，效率的最大值。 表示只考虑成本时，成本的最小
9、值。：表示任意工作方案对应的坐标。其中表示任意一种工作分配方案得到的效率值，表示任意一种工作分配方案得到的成本值；：表示与的距离：五、模型的建立与求解5.1问题一的模型建立与求解5.1.1模型的建立首先我们根据题目建立效率矩阵表示第人做第个工作的效率。然后我们建立反应第人是否负责第个工作的0-1变量 由题目可知，六个人负责六项工作，所以每个人只能负责一项工作，而且每个工作只能由一个人来完成。于是便有下面的约束条件: 且则目标函数为总的效率表达式如下：综上便可得到最终效率模型如下: 51.2 模型求解这是一个0-1优化问题，lingo软件具有强大的优化问题解决能力，所以我们通过lingo软件编程
10、求解出最佳分配方案，根据程序运行结果我们最终得到的最优分配方案如下：（lingo程序见附录，运算结果见附录）：人员1人员2人员3人员4人员5人员6工作分配方案214356表1 最大效率工作分配方案而且此时的最大效率值为26。5.2问题二的模型建立与求解5.2.1成本最小化模型的建立由题目中给定的成本数据我们建立成本矩阵具体如下：同样有反应第人是否做第个工作的0-1变量 而且六个人负责六项工作，所以每个人只能负责一项工作，而且每个工作只能由一个人来完成。于是便有下面的约束条件： 且则最终得到只考虑成本总成本的目标函数如下：于是得到完整的成本最小化模型如下： 5.2.2、模型的求解与问题一类似的解
11、法，应用lingo软件编程求解使目标函数值最小（即：使成本最小）根据程序运行结果（程序及运行结果见附录，），我们得到的最佳分配方案如下：人员1人员2人员3人员4人员5人员6工作分配方案345162表2 最低成本分配工作方式5.3问题三的模型建立与求解5.3.1多目标规划模型的建立第一步：进行数据标准化。由于该问题要求兼顾效率与成本，而这两项指标却不是同性质的，而且成本数据都偏大一些，为了防止成本数据影响最终结果，需要对两项数据进行标准化，标准化方法有很多种，这里我们采用极值差方法对两项指标进行处理。具体如下： 首先对用极值差方法进行标准化后得:通过matlab编程我们可以得到矩阵,此时矩阵的值
12、均在0和1之间，最优值为1，最劣值为0。然后对指标数据矩阵用极值差法标准化后得到:同样可以用matlab编程得到矩阵且值均在0和1之间和 matlab标准化程序及结果见附录。第二步：多目标规划模型的建立由第一问及第二问的基础我们可以得出两个规划目标函数如下：首先，有总效率的目标函数： 其中表示任意一种工作分配方案得到的效率值。同时有总成本的目标函数: 其中表示任意一种工作分配方案得到的成本值。于是，多目标函数规划模型建立如下： 5.3.2多目标规划转化为单目标规划模型由于以上所建的多目标规划模型问题求解过于复杂，为了简化问题，我们采用了理想点法，求出任意工作分配方案的效率与成本偏离理想点的距离
13、的目标函数表达式，然后使目标函数表达式的值逼近最小，此时对应的方案就是在兼顾效率与成本的前提下的最优工作分配方案，具体步骤如下：第一步：设标准化后理想点。其中表示只考虑效率指标时，效率的最大值。表示只考虑成本时，成本的最小值。、求解可以借助问题一、二中的程序只是将其中的效率，成本中的数据替换成标准化后的和中的数据。、，即理想点为。第二步：求点与理想点之间距离的表达式。其中表示任意一种工作分配方案得到的效率值，表示任意一种工作分配方案得到的成本值。则与的距离表达式如下： （3）然后将多目标规划模型中德(1)、（2）式代入（3）式得到最终表达式.第三步：最终单目标规划模型建立。六个人负责六项工作，
14、所以每个人只能负责一项工作，而且每个工作只能由一个人来完成。于是便有下面的约束条件如下： 且综上所述，可以得到偏离理想点距离模型如下： 5.3.3 模型的求解 此模型的求解主要借助lingo编程，使目标函数值逐渐逼近理想点，但达到理想点是不可能的，只需达到目标函数最小值，即最接近理想点的点就是兼顾成本与效率的最佳工作分配方案，此时效率与成本都达到了最优。根据程序运行结果，最佳工作分配方案如下（求解模型的lingo程序及运行结果见附录）：人员1人员2人员3人员4人员5人员6工作分配方案241365表3 兼顾成本与效率下时最优工作分配方案此时的最小值为1.695967六、模型的评价与推广6.1模型
15、的优点1、本题中的模型都是有简单到复杂一步步建立，文章整体逻辑性强，可读性强。2、对于问题一二的解决中我们应用了0-1规划模型大大降低了问题的难度，使目标函数成为求和的形式，便于计算。同时我们应用lingo这一软件大大减小了解决0-1规划模型的计算。 3、问题三中，我们使数据都标准化这样使得数据才有衡量的标准，防止了因为成本原始数据较大儿在最终结果中起主导影响，此外，我们应用理想点法把多目标规划转化为单目标规划使问题得以简化，同时使用距离这一概念使模型简单易于理解而且有益于编程计算。 6.2模型的缺点首先就是该模型不能解决当效率与成本的重要性不同时得工作指派问题（即在效率与成本的权重不同时），
16、比如有时决策者希望七成考虑效率，三成考虑成本的情况。而我们的模型只考虑了成本与效率整体下的最优解。6.3 模型的推广如果数据能进一步符合工人的真实情况，那么该模型可以在一定程度上帮助决策者做出最佳的决定。还有其他一些类似的优化问题，比如路径最短问题，原料分配等一些生活中的实际问题中。七、参考文献1陈东彦，刘凤秋著，数学建模，北京：科学出版社 ，2013。2苏金明，阮沈勇著，MATLAB实用教程，北京：电子工业出版社，2008。3赵东方，数学模型与计算，河北：科学出版社，2007。4穆学文，多目标规划，5谢金星,LINGO优化软件， 2014.5.30。附录问题一 !求解最大效率分配方式的lin
17、go程序;model: !定义; sets: people/1.6/; work/1.6/; match(people, work): efficient,k; endsets data: efficient= 351002643254142212123331213242325466enddata ! 效率矩阵; ! 目标函数：最大效率和; max = sum(match: efficient*k); for(people(i): sum(work(j): k(i,j)=1); ! m每个人都有且只有一份工作; for(work(j): sum(people(i): k(i,j)=1); !每
18、个工作有且只有一个人做; for(match:bin(k); !变量k(i,j)为0-1变量；end运行结果如下： Global optimal solution found. Objective value: 26.00000 Objective bound: 26.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost EFFICIENT( 1, 1) 3.000000 0.000000 EFFICIENT( 1, 2) 5
19、.000000 0.000000 EFFICIENT( 1, 3) 1.000000 0.000000 EFFICIENT( 1, 4) 0.000000 0.000000 EFFICIENT( 1, 5) 0.000000 0.000000 EFFICIENT( 1, 6) 2.000000 0.000000 EFFICIENT( 2, 1) 6.000000 0.000000 EFFICIENT( 2, 2) 4.000000 0.000000 EFFICIENT( 2, 3) 3.000000 0.000000 EFFICIENT( 2, 4) 2.000000 0.000000 EFF
20、ICIENT( 2, 5) 5.000000 0.000000 EFFICIENT( 2, 6) 4.000000 0.000000 EFFICIENT( 3, 1) 1.000000 0.000000 EFFICIENT( 3, 2) 4.000000 0.000000 EFFICIENT( 3, 3) 2.000000 0.000000 EFFICIENT( 3, 4) 2.000000 0.000000 EFFICIENT( 3, 5) 1.000000 0.000000 EFFICIENT( 3, 6) 2.000000 0.000000 EFFICIENT( 4, 1) 1.0000
21、00 0.000000 EFFICIENT( 4, 2) 2.000000 0.000000 EFFICIENT( 4, 3) 3.000000 0.000000 EFFICIENT( 4, 4) 3.000000 0.000000 EFFICIENT( 4, 5) 3.000000 0.000000 EFFICIENT( 4, 6) 1.000000 0.000000 EFFICIENT( 5, 1) 2.000000 0.000000 EFFICIENT( 5, 2) 1.000000 0.000000 EFFICIENT( 5, 3) 3.000000 0.000000 EFFICIEN
22、T( 5, 4) 2.000000 0.000000 EFFICIENT( 5, 5) 4.000000 0.000000 EFFICIENT( 5, 6) 2.000000 0.000000 EFFICIENT( 6, 1) 3.000000 0.000000 EFFICIENT( 6, 2) 2.000000 0.000000 EFFICIENT( 6, 3) 5.000000 0.000000 EFFICIENT( 6, 4) 4.000000 0.000000 EFFICIENT( 6, 5) 6.000000 0.000000 EFFICIENT( 6, 6) 6.000000 0.
23、000000 K( 1, 1) 0.000000 -3.000000 K( 1, 2) 1.000000 -5.000000 K( 1, 3) 0.000000 -1.000000 K( 1, 4) 0.000000 0.000000 K( 1, 5) 0.000000 0.000000 K( 1, 6) 0.000000 -2.000000 K( 2, 1) 1.000000 -6.000000 K( 2, 2) 0.000000 -4.000000 K( 2, 3) 0.000000 -3.000000 K( 2, 4) 0.000000 -2.000000 K( 2, 5) 0.0000
24、00 -5.000000 K( 2, 6) 0.000000 -4.000000 K( 3, 1) 0.000000 -1.000000 K( 3, 2) 0.000000 -4.000000 K( 3, 3) 0.000000 -2.000000 K( 3, 4) 1.000000 -2.000000 K( 3, 5) 0.000000 -1.000000 K( 3, 6) 0.000000 -2.000000 K( 4, 1) 0.000000 -1.000000 K( 4, 2) 0.000000 -2.000000 K( 4, 3) 1.000000 -3.000000 K( 4, 4
25、) 0.000000 -3.000000 K( 4, 5) 0.000000 -3.000000 K( 4, 6) 0.000000 -1.000000 K( 5, 1) 0.000000 -2.000000 K( 5, 2) 0.000000 -1.000000 K( 5, 3) 0.000000 -3.000000 K( 5, 4) 0.000000 -2.000000 K( 5, 5) 1.000000 -4.000000 K( 5, 6) 0.000000 -2.000000 K( 6, 1) 0.000000 -3.000000 K( 6, 2) 0.000000 -2.000000
26、 K( 6, 3) 0.000000 -5.000000 K( 6, 4) 0.000000 -4.000000 K( 6, 5) 0.000000 -6.000000 K( 6, 6) 1.000000 -6.000000 Row Slack or Surplus Dual Price 1 26.00000 1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.00
27、0000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000-问题二 -!求解最低成本分配方式的lingo程序;model: !定义; sets: people/1.6/; work/1.6/; match(people, work): cost,k; endsets data: cost= 481004127531192104425255794527474851081113enddata ! 成本矩阵; min = sum(match:
28、cost*k);! 目标函数：总共最低成本; for(people(i): sum(work(j): k(i,j)=1); ! m每个人都有且只有一份工作; for(work(j): sum(people(i): k(i,j)=1); !每个工作有且只有一个人做; for(match:bin(k); !变量k为0-1变量；end程序运行结果：Global optimal solution found. Objective value: 17.00000 Objective bound: 17.00000 Infeasibilities: 0.000000 Extended solver ste
29、ps: 0 Total solver iterations: 0 Variable Value Reduced Cost COST( 1, 1) 4.000000 0.000000 COST( 1, 2) 8.000000 0.000000 COST( 1, 3) 1.000000 0.000000 COST( 1, 4) 0.000000 0.000000 COST( 1, 5) 0.000000 0.000000 COST( 1, 6) 4.000000 0.000000 COST( 2, 1) 12.00000 0.000000 COST( 2, 2) 7.000000 0.000000 COST( 2, 3) 5.000000 0.000000 COST( 2, 4) 3.000000 0.000000 COST( 2, 5) 11.00000 0.000000 COST( 2, 6) 9.000000 0.000000 COST( 3, 1) 2.000000 0.000000