数学建模竞赛论文评审优化协商方案.docx

《数学建模竞赛论文评审优化协商方案.docx》由会员分享，可在线阅读，更多相关《数学建模竞赛论文评审优化协商方案.docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数学建模竞赛论文评审优化协商方案摘要 大数据时代下，如何利用数据信息，调配资源，合理分配任务是提高系统效能的关键。本文针对数学建模竞赛中论文评分差异过大相关的分数协商分配问题，利用了非线性整数优化、多目标优化及动态演变分析等方法，建立了论文评分协商最优分配模型、有约束的论文协商分配模型和多目标约束协商优化模型。通过MATLAB编程计算，求解得到了最佳的协商方案。针对问题一，首先利用数据信息构造协商关系图，将论文协商分配问题转化为协商关系图的最大边覆盖问题，建立了非线性整数优化模型，并运用遗传算法进行求解模型，得到最优的协商分配方案，整个协商过程耗时仅28min。针对问题二，考虑到不同教师协商

2、工作大小的差别，构造了加权的协商关系图，将老师间协商任务量作为协商关系图中边的权值，在每一轮迭代过程中，动态更新协商关系图中边的权重，建立了动态约束目的优化模型，并运用粒子群算法求解优化方程，在协商教师互不相识的情况，得到最佳的协商分配方案，整个方案耗时65min。针对问题三，鉴于三位老师的特殊情况，将整体论文协商分配问题转化多个协商子问题，分步构造目标优化子模型，从而结合形成有约束多目标优化模型，并提出迭代的多目标遗传优化算法，通过计算，求解得知此条件下的最优协商分配方案，整个协商过程耗时64min,三位老师花费24min结束协商，符合需在14:30之前结束协商的需求。关键词 非线性整数优化

3、 多目标约束 遗传算法 最大边覆盖 论文协商分配MathematicalmodelingcontestpaperreviewandoptimizationnegotiationschemeAbstract Intheeraofbigdata,howtoutilizedatainformation,allocateresourcesandallocatetasksreasonablyisthekeytoimprovesystemefficiency.Inthispaper,theoptimalallocationmodel,theconstrainedallocationmodelandthec

4、onstrainedallocationmodelareestablishedbyusingthemethodsofnonlinearintegeroptimization,multi-objectiveoptimizationanddynamicevolutionanalysis.ThroughMATLABprogrammingcalculation,thebestnegotiationschemeisobtained.Inviewofproblem1,firstly,anegotiationgraphisconstructedbyusingdatainformation,thethesis

5、negotiationallocationproblemistransformedintothemaximumedgecoveringproblemofthenegotiationgraph,anonlinearintegeroptimizationmodelisestablished,andageneticalgorithmisusedtosolvethemodel,soastoobtaintheoptimalnegotiationallocationscheme.Thewholenegotiationprocesstakesonly28min.Toquestion2,considering

6、thedifferencesbetweendifferentteachersconsultationworksize,diagram,constructstheweightednegotiationwillnegotiatetoquotaasnegotiationbetweenteacherdiagramedgeweights,ineachroundofiterationprocess,dynamicupdateconsultationofedgeweightsinthediagram,thedynamicconstraintobjectiveoptimizationmodelwasestab

7、lished,andusedtosolvetheoptimizationequationofparticleswarmoptimization(pso),teacherstrangersinconsultation,negotiationscheme,forthebest,thewholeschemetakesonly56min.Forquestion3,inviewofthethreeteachersofspecialcircumstances,thewholethesisnegotiationassignmentproblemintosubproblemsmultiplenegotiati

8、on,constructtheobjectiveoptimizationmodel,stepbystepsoastoformaconstrainedmulti-objectiveoptimizationmodelofmulti-objectivegeneticoptimizationalgorithm,andproposestheiterationbycalculation,solvingabouttheoptimaldistributionplanforthenegotiation,undertheconditionofthewholenegotiationprocesstakes64min

9、,inlinewiththethreeteachersdemandshouldbenegotiatedbeforecomestoend.Key words nonlinearintegeroptimization multi-objectiveconstraint geneticalgorithm maximumedgecovering papernegotiationallocatio目 录引 言11.问题重述22.符号说明33.问题分析44.模型的建立与求解54.1问题一模型的建立与求解54.1.1模型的分析及建立54.1.2模型的求解及结果84.2问题二模型的建立与求解114.2.1模型

10、的分析及建立124.2.2模型的求解及结果134.3问题三模型的建立与求解164.3.1模型的分析及建立164.4模型的求解结果195.模型的优缺点255.1模型的优点255.2模型的缺点25总 结25参考文献26致 谢27附 录28引 言2019年全国大学生数学建模竞赛江苏赛区论文评审在南京林业大学进行，每个队提交的论文都由三位老师独立打分，打分结束后，对于最高分和最低分差距比较大的论文，打最高分和最低分的老师再进行协商，重新打分。由于涉及到的论文和老师较多，很多老师相互之间还不太认识，如何合理安排协商是一件比较麻烦的事情。如果能够给出科学合理的协商方案，可以节约很多时间，以这一个事情为背景

11、设计了如下这个比赛题目。这个问题解决方法的初步设想是使用运筹学建立约束规划模型来求解，还需要使用图论相关知识，编程求解，撰写论文等。1. 问题重述现在对大学生数学建模论文评审，每篇论文由三名老师独立打分，如果最低分和最高分差距超过10分，需要两位老师面对面协商，两人修改自己的分数，修改完后不需要再进行一次修改。如果一人空着，另一人与别的老师协商，那么前面的这位老师需要等待。如果两位老师不熟悉，需要取得联系，这需要花费一点时间。如果两位老师熟悉，不需要再在取得联系上花费时间，协商用时会短一些。下午14:00协商开始。问题一：如何安排，使得全部协商完后需要的时间最少？问题二：由于老师之间互相不熟悉

12、，一名老师新找一名老师协商需要4分钟。问如何安排，使得全部协商完后需要的时间最少？问题三：有三位徐州（赵老师、周老师、林老师）的老师赶时间坐车，需要优先协商完，要求三位徐州的老师全部协商完的时间不迟于下午14:30（越早结束越好），问在满足三位徐州老师时间的条件下，如何安排，使得全部协商完成后需要的时间最少。表1 需要协商的教师信息论文编号教师A教师B论文编号教师A教师B论文编号教师A教师B215赵张261邱吴110赵张262钱周256吴钱16邱张159邱费122俞周233邱范240钱范248吴周15吴林323孙范13俞林90吴林18邱吴29钱周150张林156吴周54吴孙451吴费198邱孙

13、315钱牛31邱孙101张周53钱俞208邱周293邱周278吴周291陆张232吴林322赵陈192钱周20孙周391邱张263陆牛154赵陈4陈范343张费注：表中只列举中教师姓名，且排名不分先后2. 符号说明针对上述问题，本文建模了单目标、多目标的优化模型，为便于大家理解本文所提的优化模型，这里将建模过程中主要应用到的符号作如下说明，具体符号及其物理意义如下所示：符号物理意义pi，i=1,2,n第i篇论文P=p1,p2,pnn篇论文mi第i位评委M=m1,m2,mm评委老师集合S=sijnm打分矩阵DPT=dijmm协商矩阵dij第i位老师与第j位老师协商情K=kij当前参与协商矩阵Ri

14、矩阵K的第i行Cj矩阵K的第j列Pt第t分钟评委老师间协商次数矩阵T协商时间3. 问题分析在大学生数学建模论文评审过程中，每篇论文由三名教师独立打分，如果最低分和最高分差距超过10分，需要两位老师面对面协商，两人修改自己的分数。注意到每次协商过程中，只能是两位面对面协商，即不能出现3或多位教师共同协商的情形。此问题与经典的任务分配类似，需要给出具体的协商方案，以使整个协商过程时间最短，这就涉及到单指标/多指标的优化问题。表1所示，此次需要协商的论文共计39篇，共涉及陈、陆、钱、邱、孙、吴、俞、张、赵、范、费、林、牛和周14位评委教师间的协商问题。图1统计了各位评委老师共需要协商次数情况，可以看

15、出最大需要协商的次数为11次，最小需要协商的次数为2次，其中，周、吴、邱三位评委老师的协商任务均超过10。分析不难发现，所以老师完成协商最短时间为44min。图1 各评委老师协商次数问题1要求给出最佳协商方案，使得全部协商完成时间最短。问题2在问题1的基础上，增加了寻找评委老师的时间。问题3则基于问题1、问题2提出优先安排三位徐州（赵老师、周老师、林老师）评委教师，确保这三位教师在最短时间内完成自己的协商任务，同时也使得剩余评委老师协商任务在尽可能短的时间内完成。三个问题均为优化问题，问题2/3则增加了相应约束条件，则可认为是有约束的优化问题。为使总协商时间最短，需要尽可能降低等待机会，即尽可

16、能安排所有需要协商的教师尽可能多地参与协商。建模过程中，我们根据表1中打分情况，构造协商关系图邻接矩阵，需要协商的位置用大于1的数表示，不需要协商的教师间取值为0，这里数值大小表示两位老师间的最大协商次数。则整个协商过程可转变为对协商关系图的最大边覆盖问题。每轮协商问题可转化为在协商关系图中找到最大不相邻边。通过不断迭代，知道协商关系图所以的边都被覆盖到，则整个协商过程全部完成。4. 模型的建立与求解4.1 问题一模型的建立与求解4.1.1 模型的分析及建立问题1要求给出最佳的协商安排方案，以使得整个协商进程时间最短。针对此问题，为简化模型，建模过程中，本文对其进行必要的限定，作如下假设：1）

17、假设需要协商的两位老师，当且仅当协商一次，即即使多篇文章需要协商，只需协商一次便可完成所有任务；2）对于每篇论文，三位老师打分出现重复且最高分最低分差距超过10分时，只需与其中一位老师协商（所给数据中不存在此情况）；3）假设两位需要协商老师需要协商多篇论文，其总共所需时间仍为4分钟；4）评委老师只协商共同打分的论文。基于上述假设，下面给出具体的建模方法。设现有n篇论文记为P=p1,p2,pn，m位评委老师M=m1,m2,mm，其形成的打分矩阵记为S=sijnm,且有sij=g 第j位老师给第i篇论文打分 0 第j位老师未给第i篇论文打分则根据打分矩阵S，可以获得需要协商的论文Ps及对应的评委老

18、师Ts,则有：Ps=i|maxsij-minsij10,i=1,2,nTs=i,jmaxsij-minsij10,i=1,2,n,j=1,2,m文Ps及对应的评委老师Ts，构造如下协商矩阵DPT,其满足：DPT=d11d1mdm1dmm其中，di,j表示第i位老师与第j位老师协商情况，即有：dij=1 第i位老师需与第j位老师协商 0 第i位老师无需与第j位老师协商结合Ts，不难发现dij=1 i,jTs 0 i,jTs 协商过程中，每位需要协商的老师可结合自身安排选择评委老师进行协商，但实际中，往往容易出现多个同时寻找一位老师协商，这就造成时间和资源的浪费。为此，需合理安排协商过程，确保协商

19、过程在最短时间内完成。考虑到协商策略的变化并不影响总共需要协商的次数，也就是协商过程中的最短用时是一定的，因此，在制定协商策略过程中，只需尽可能避免两位或者多位评委老师同时找某一位评委老师的情况，即尽可能让所有需要老师参与协商但不重复即可。每一轮协商可视为在矩阵DPT中寻找尽可能多不在同行同列的1，迭代直到矩阵DPT中所有为1的元素都被遍历过，则有：maxi=1mj=1mkij0Ri11,i=1,2,m0Cj11,j=1,2,m0Ri1, RiZ*0Cj1, CjZ*其中，Ri表示矩阵K的第i行，Cj表示矩阵K的第j列，K=kij,且kij满足：kij=dij,kji=0,i=1,2,m,j=

20、i,i+1,m不难发现，上述优化问题是有约束的非线性整数规划问题，该问题的可行域并非连续，采用一般的有约束的优化算法如梯度下降法、单纯性法、对偶单纯性法等求解比较困难。遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点表现在：1）直接对结构对象进行操作，不存在求导和函数连续性的限定；2）具有内在的隐并行性和更好的全局寻优能力；3）采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。遗传算法(Genetic algorithms

21、, GAs)是在进化和自然遗传学原理指导下的随机搜索和优化技术，具有大量的隐式并行性。GAs在复杂、大型和多模态的景观中执行搜索，并为目的或优化问题的“灵敏度函数”提供近似最优解。在GAs中，搜索空间的参数以字符串(称为染色体)的形式编码。这样的字符串集合称为总体。在模式识别领域，为了获得最优解，需要在复杂空间中进行适当的参数选择和搜索，在分析和识别模式的过程中涉及很多任务。因此，将GAs应用于解决模式识别的某些问题(需要优化计算要求，以及鲁棒性、快速性和近似解)似乎是合适且自然的。遗传算法求解优化问题的一般步骤如图2所示，包括生成初始种群、计算适应度、选择、变异、交叉等，通过多次迭代，保留群

22、体中最优个体，从而得到适合问题的最佳解。图2 遗传算法流程图具体求解过程中，首先对题目中教师编号（如表2）非整数规划问题，先随机选择一定数量的原始染色体，这些染色体经过杂交，变异得到的染色体经过计算后，得到适应度。最终选择适应度最高的染色体。表2 协商教师编号教师编号陈#1陆#2钱#3邱#4孙#5吴#6俞#7张#8赵#9范#10费#11林#12牛#13周#14采用上述编号，结合表1，构造协商关系图邻接矩阵，并画出其对应的协商关系图，得到：图3 协商关系图4.1.2 模型的求解及结果针对上述邻接矩阵，下面运用遗传算法对其进行求解，得到第一轮迭代结果如表3所示，其中，1所处位置对应的行和列所对应的

23、老师参与本轮协商，0所处位置对应的行列所对应的老师不参与本轮协商。根据表3，不难发现，本轮所有老师均参与协商。表3 协商关系矩阵#1#2#3#4#5#6#7#8#9#10#11#12#13#14#100000000100000#200000000000010#300010000000000#400100000000000#500000000010000#600000000000001#700000000000100#800000000001000#910000000000000#1000001000000000#1100000001000000#1200000010000000#1301000

24、000000000#1400000100000000将表3对应的协商关系转化为具体的协商方案为：#1#9，#2#13，#3#4，#5#10，#6#14，#7#12，#8#11。完成本轮协商之后，从原始的协商矩阵中去除本轮已经协商的老师，得到更新协商关系图如下所示：图4 第一轮协商关系图 按照上述过程，继续进行迭代，得到第二轮的协商方案：#1#10，#2#8，#3#13，#4#5，#6#12，#7#14，去除已经协商过的教师，则此时更新后的协商关系图变为：图4 第二轮协商关系图同样，可得到上述协商关系图的第三轮协商方案：#3#7，#4#10，#5#14，#6#11，#8#12，去除已经协商过的教

25、师，则此时更新后的协商关系图变为：图5 第三轮协商关系图利用遗传算法，求解得到上述协商关系对应的第四轮协商方案：#3#10，#4#11，#5#6，#8#14，去除已经协商过的教师，则此时更新后的协商关系图变为：图6 第四轮协商关系图继续重复上述过程，求解得到上述协商关系对应的第五轮协商方案：#3#6，#4#14，#8#9，去除已经协商过的教师，则此时更新后的协商关系图变为：图7 第五轮协商关系图重复上述过程，求解得到上述协商关系对应的协商方案：#3#14，#4#8，去除已经协商过的教师，则此时更新后的协商关系图变为：图7 第六轮协商关系图根据第六轮协商关系图，则最后一次的协商方案为：#4#6，

26、此时，协商关系图已无边即原始协商关系图中的所有边已经被覆盖过，所有的协商均已完成。综合上述六轮协商过程，可得到整个过程的协商耗时：24min+4min= 28min。至此，完成整个协商需要耗时28分钟。4.2 问题二模型的建立与求解4.2.1 模型的分析及建立问题2提到老师之间相互不熟悉，一名老师新找一名老师协商需要4分钟，在此种条件下，如何安排协商方案，可使得全部协商完后需要的时间最短。针对此问题，为便于建模，简化问题原型，在建模过程中，本文作如下假设：1）不同评委老师协商一篇论文所需时间均为4分钟；2）不同评委老师寻找协商评委所需时间相等，均为4分钟；3）若需要协商多篇论文，则只需进行一次

27、协商即可完成所有协商任务。基于上述假设条件，考虑到评委老师之间互不熟悉，因此在评阅协商过程中，寻找对应的老师需要耗费一定时间，同时评委协商过程中，可能存在多篇论文需要协商，因而不同评委间协商所需时间不同，而在此期间，其他与正在协商的评委老师有协商需求的评委老师可选择等待或者继续寻找其他评委老师进行协商。设工作需要协商的论文总数为Ns,当有m位评委老师时，定义协商次数矩阵表示t时刻协商次数矩阵的状态 Smt=sijmmt , sij表示第i位老师和第j位老师剩余协商次数，显然有0sijNs, ti=1mj=1msij=2Ns, sij=sji。假设协商总共经过T分钟，每1分钟评委老师间协商次数矩

28、阵为Pt,为便于计算，这里同样约束每分钟内不可存在两位评委同时寻找一位评委的情形，则有：tPt=Sm0这里，Pt=qijmm, qij0,1，jqij=1, iqij=1,同时有：Smt=Smt-1-Pt-1=Sm0-i=0t-1Pi根据Pt的定义，则经过T分钟，可以得到完成整个协商所需要的时间Ttotal为:Ttotal=2tPt-max(Sm0-Id,Id)其中，Id=Idij为mm的矩阵，且有：Idij=1 sijsijmmt,sij0, t=0 0 otherwise 综合上述，要使得整个协商过程时间最短，则有：minPt2tPt-max(Sm0-Id,Id)s.t. tPt=Sm00

29、Rpti11,i=1,2,m0Cptj11,j=1,2,m0Rpti1, RptiZ*0Cptj1, CptjZ*其中，Rpti，Cptj分别表示矩阵Pt第i行，第j列。不难发现上述优化问题是一个复杂的非线性的规划问题，模型中含有非线性约束条件，且目标函数非凸，因而，常规方法求解困难。粒子群算法（Particle Swarm Optimization，PSO）是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于对鸟群捕食行为的研究。发展该理论的一个动机是模仿人类的社会行为，这当然与鱼群或鸟群不同。重要的区别在于它的抽象性。鸟类和鱼类调整它们的身体运动，以避免捕食者，寻找食

30、物和配偶，优化环境参数，如温度等。人类不仅要调整身体运动，还要调整认知或经验变量。我们通常不会步调一致地走路。尽管一些有关人类从众的有趣研究表明，我们有能力做到这一点;相反，我们倾向于调整我们的信念和态度，以符合我们的社会同伴。4.2.2 模型的求解及结果利用PSO生物智能优化算法，对上述问题进行求解。求解过程中，首先将协商关系图（图8）转化为带权值的协商关系图，如图9所示，图中边的权值表示两节点间共需协商的次数。图8 协商关系图图9 加权协商关系图调用粒子群算法，针对上述协商关系图，求解得到协商方案：#1#9，#2#13，#3#4，#5#10，#6#11，#7#12，#8#14，采取此协商方

31、案后，更新协商关系图，得到新的协商关系图，如下：8min 图10 第一轮8分钟后商议图按照上述过程，继续进行迭代，得到第二轮的协商方案：#1#9，#8#9，#3#13，#4#11，#6#12，#5#14。注意到，由于寻找对应的协商老师，需要花费1分钟，因此，在此轮协商过程中，正参与上一轮协商的教师，下一轮将要与其协商的教师，可在其即将剩余最后一篇论文协商任务时，开始寻找该教师，对应协商关系图上，即允许存在相邻的两条边被同时选择（如图10，#1#9，#8#9，）。2分钟后，在协商的教师完成一篇论文的协商，去除已经协商过的教师，则此时更新后的协商关系图变为：8min 图10 第二轮8分钟后商议图继

32、续重复上述过程，求解得到上述协商关系图，得到对应的第三轮协商方案：#2#8，#9#8，#3#10，#6#12，#7#14，#4#5，此时同样允许存在相邻的边，去除已经协商过的教师，则更新后的协商关系图变为：8min 图10 第三轮8分钟后商议图继续上述过程，求解第三轮商议图，得到对应的第三轮协商方案：#8#12，#3#7，#10#4，#5#4，#6#5，此时同样允许存在相邻的边，注意到，由于节点#4和节点#5正处于协商过程中，且还有一篇论文未协商，此时，节点#10、节点6可以分别去找#4、#5教师，当找到时，教师#4、#5恰好协商完成，则可继续协商，因此，有三个边相邻。去除已经协商过的教师，则

33、更新后的协商关系图变为：8min 图11 第四轮8分钟后商议图为展示方便，后续优化，仅拿出还需协商节点，得到如下的协商子图，继续采用粒子群算法进行优化，得到第五、六轮协商（8+4分钟后）的协商方案：第五轮：#8#4，#4#14，#6#14，#8#4，#6#14；第六轮：#4#6，#6#14，#3#14，#4#6，#3#14；其对应的协商关系图为：4min8min 图12 第五轮商议图第六轮协商（8+4分钟后）：4min8min 图13 第六轮商议图综合上述六轮协商过程，所以教师均完成对应的协商任务，很容易得到此过程总耗时为：4*8+2*12=56min。4.3 问题三模型的建立与求解4.3.1

34、 模型的分析及建立问题3提到有三位徐州（赵老师、周老师、林老师）的老师赶时间坐车，需要优先协商完，要求这三位老师全部协商完的时间不迟于下午14:30（越早结束越好），问在满足三位徐州老师时间的条件下，如何安排，使得全部协商完成后需要的时间最少。整个协商开始时间为14:00，也就是说尽量在半个小时内，三位老师的协商任务需全部完成。鉴于问题2中提到老师之间相互不熟悉，一名老师新找一名老师协商需要4分钟，对于有特殊安排的教师，在此题中，我们认为其为大家所熟知，即与其协商无须额外的寻找时间。而其他教师之间的协商则依然存在协商寻找时间。在建模过程中，本文作如下假设：1）假设三位赶车老师之间协商优先级相同

35、；2）寻找三位优先安排协商的老师协商无时间消耗；3）除三位老师之外其他教师之间的协商需要寻找时间，且寻找所需的时间为仍为4min。现三位徐州老师需要赶时间乘车，需优先安排协商，记三位老师分别为mk1, mk2, mk3, 1k1m, 1k2m, 1k3m,且k1, k2, k3Z*。实际中，这三位老师需要协商的论文数可能为1,2或多个，记与三位老师有协商需求的老师单独组成新的协商子集为vM=mv1,mv2,mvf，则剩余老师组成的集合rM=M-vM=mr1,mr2,mrh，如图1所示，取协商矩阵DPT中第k1, k2, k3列中不全为0的行，构成子协商矩阵vDPT,则有：vDPT=dv1,k1

36、dv1,k2dv1,k3dv2,k1dv2,k2dv2,k3dvf,k1dvf,k2dvf,k3此时对应的剩余老师构成的协商矩阵定义为剩余协商矩阵rDPT为：rDPT=dr1,r1dr1,r2dr2,r1dr2,r2dr1,rhdr2,rhdrh,r1drh,r2drh,rh这里，rMvM=M,f+h=m，且f，h均为正整数。DPTM1M2MK1MK2MK3MMM1d11d12d1,k1d1,k2d1,k3d1mM2d21d22d2,k1d2,k2d2,k3d2mMK1dk1,1dk1,2dk1,k1dk1,k2dk1,k3dk1,mMK2dk2,1dk2,2dk2,k1dk2,k2dk2,k

37、3dk2,mMK3dk3,1dk3,2dk3,k1dk3,k2dk3,k3dk3,mMMdm1dm2dm,k1dm,k2dm,k3dmm图14 协商关系矩阵鉴于三位老师需要赶车，为确保协商过程顺利完成，则应使三位老师的协商任务尽早结束。实际中，三位赶车老师为评委老师中的特殊人群。为节约时间，这里假设这三位老师为大家熟知人员，即任何需要与这三位老师协商的其他评委老师均不需要花费4分钟的寻找时间，三位老师协商耗时只存在论文具体协商过程中。记m位评委老师协商关系矩阵为DPT， 构造选择矩阵3m的矩阵H如下：k3k2k1H=001000000001000010则从与三位评委mk1, mk2, mk3对

38、应的协商关系矩阵sDPT为：sDPT=DPT*HT容易得出，vDPT为矩阵sDPT去除元素全为0的行，即不妨将sDPT写为sDPT=vDPT0T,为推导方便，这里将矩阵H扩展为mm的矩阵H*：H*=HOO为(m-3)m的全0矩阵。类比问题1，关于三位评委mk1, mk2, mk3对应的协商关系矩阵sDPT的优化，只需每次寻找vDPT中尽可能多不同行不同列的非0即maxi,jf,hvDPT, 其等效于maxi,jm,mDPT*(H*)T，对于每次未协商老师即单次剩余矩阵DPT-H*，考虑到这些老师间存在互不相识，优化过程中存在寻找老师耗时，这个子问题的优化可采用问题二优化方法，此时Sm0=，这里

39、表示矩阵点积，多次迭代直到矩阵H*中所有不为0元素均被覆盖到，且Pt元素全为0，由于需要与三位提前走老师协商的评委也存在与综上可知，此问题为迭代的两目标的优化问题，单次多目标优化问题为：目标1 ： maxH*i,jm,mDPT*(H*)T 目标2 ：minPt2t-max(Sm0-Id,Id)s.t. t(Pt+H*)=Sm0 t tH*0Rpti11,i=1,2,m0Cptj11,j=1,2,m0Rpti1, RptiZ*0Cptj1, CptjZ*0Ri11,i=1,2,m0Cj11,j=1,2,m0Ri1, RiZ*0Cj1, CjZ*其中，Rpti，Cptj分别表示矩阵Pt第i行，第j

40、列，Ri表示矩阵K的第i行，Cj表示矩阵H*的第j列。4.4 模型的求解结果上述优化问题为多目标约束优化问题，其求解过程相对复杂。为此，本文提出迭代的多目标优化算法，在迭代过程中，动态调整与三位老师无协商教师的协商关系子图，将整个问题，分解为两个子问题，依次分别进行求解，经过反复迭代，得到问题的解。其算法具体流程如下所示：算法1：迭代多目标优化算法框架输入： DPT，k1, k2, k3，Sm0,标记矩阵F=ORepeat: 计算矩阵H*，Sm0 调用遗传算法，求解目标1、目标2的优化问题 更新 H*t+1 =H*t-H*, F=orF,H* Sm0t+1= , F=orF,tPt Until

41、: F=DPT由于三位老师需要赶车，在优化过程中，将三位老师涉及的优化任务单独列举出来，形成协商关系子图，如15下所示，其中边的权值表示两节点点需要协商的次数。 图15 三位老师（赵老师、周老师、林老师）协商关系加权图采用遗传算法，针对上述协商关系子图，求解得到协商方案，第一分钟：#1#9，#3#12，#8#14；第二分钟：#7#12，#8#9，#3#14。采取此协商方案后，经过8分钟，去掉已完成协商任务的边，得到新的协商关系图，如下：4min选择4min 图16 三位老师8分钟内协商情况演变图由于三位老师协商过程中，与其有协商关系的教师，可能未参与本次协商。为节约时间，这些需要与三位老师协商的教师可与其他正未协商的教师协商相应的论文。将无与三位老师协商的教师组合起来，构造剩余协商关系子图，如下图所示： 图17 剩余协商关系加权子图同样，运用遗传求解得到，