指派模型（精选9篇）
指派模型 篇1
0 引言
信息条件下的高技术局部战争装备保障具有全局性、分布性的特点。为了使整个装备维修保障系统能够高效、协调的运行，装备保障指挥控制系统必须能够灵活、快速、高效、合理地分配维修任务。尤其是在战时，战争进行激烈，装备损坏严重，维修任务大，而可用机动维修力量又十分有限的条件下，维修力量派遣的“优化”问题就显得更加重要，有必要对维修力量的指派问题建立一种模型。
传统的战场抢修任务指派模型：
其中，cij≥0表示第i个人完成第j项任务时的效率（所费时间或成本等），把目标函数的系数矩阵C=(cij)n×n称为指派问题的效率矩阵。匈牙利法是求解传统指派问题的有效方法之一。
1 战场抢修任务指派的数学模型描述
1.1 任务需求
战役级维修机动小组作用就是在一定的作战要求下，对所属战役军团中的部队维修进行加强支援，从而满足作战指挥部门的要求。某战役级维修机构有m个维修机动小组，现要完成n项紧急程度不同的任务，己知维修机动小组维修保障能力不尽相同，第i个小组完成第j项任务的效率为cij,cij≥0，当cij=∞时，表示第i个小组没有能力完成第j项任务，如何进行维修任务指派，才能使完成n项任务的总效率达到最高（维修总时间最少）。
设决策变量：
效率矩阵C,
式中：Ji表示第i项任务的紧急程度。
1.2 紧急程度
将紧急程度划分3个等级，具体的含义如表1所示。
1.3 指派策略
实战中，战损装备的抢修主要依赖于两个方面：一是战场情况、紧急程度、装备受损情况和维修器材保障等；一是应急机动保障力量、维修人员素质，以及指挥员的决心。一般来说，战损装备抢修任务指派策略是，应急机动装备维修小组根据紧急程度高低的任务进行抢修，只要有抢修任务，已完成任务的小组就应立刻接受新的任务。
1.4 模型描述
对n项紧急程度不同的任务进行分类统计，非常紧急类（Ji=1）任务L1个，紧急类（Ji=2）任务L2个，一般类（Ji=3）任务n-(L1+L2）个；令C1,C2和C3分别为这三类任务的效率矩阵，对n项紧急程度不同任务的指派模型：
1.5 模型求解
1.5.1 非常紧急类（Ji=1）任务指派模型求解
将（3）式效率矩阵中紧急程度Ji=1的列提出来，若有L1个，分别记录项目编号，m个维修小组对这L1个紧急任务进行指派。这样构成一个非常紧急类任务的效率矩阵C1=(C1)(m×L1）。
指派模型：(7)
1.5.2 紧急类（Ji=2）任务指派模型求解
将（3）式效率矩阵中紧急程度Ji=1的列提出来，然后在m行中划去己经分配非常紧急任务的L1个维修小组，这样形成一个紧急类效率矩阵C2=(C2)(m-L1）×L2
指派模型：(9)
1.5.3 一般类（Ji=3）任务指派模型求解
将（3）式效率矩阵中紧急程度Ji=2的列提出来，然后在m行中划去己经分配非常紧急任务L1个维修小组和紧急任务的L2个维修小组，这样形成一个一般类效率矩阵C3=(C2)(m-L1-L2）×L3
指派模型：(11)
对f1,f2和f3模型求解。
2 结束语
战损装备的应急抢修应依据战场情况、紧急程度、装备受损情况、维修器材保障、应急机动保障力量和维修人员素质等因素，由指挥员决定应急机动装备维修小组的派遣。在实战中，经常会出现非常紧急的任务，针对这些不同紧急程度的抢修任务，指挥员要做出正确的决策。
参考文献
[1]何坚勇.运筹学基础[M].北京:清华人学出版社,2000.
[2]苏祥定,孙桐,马霖.不平衡指派问题的差额法求解及其应用[J].计算机工程,2005(11):178-179.
[3]张芳玉,高崎,何鹏等.战时装备维修任务指派模型及算法研究[J].运筹与管理,2006(2):62-66.
[4]自国仲,苏芳荔等.基于特殊需要的指派问题[J].华中师范大学学(自然科学版)2006(9):305-309.
[5]花文健,李炳杰.应急机动通信兵力派遣问题的通用模型[J].空军工程人学学报(自然科学版),2003,4(4):38-40.
指派模型 篇2
指派通知书
编号：皖（安宿）援民审字[]第号：
根据国务院《法律援助条例》和《安徽省法律援助条例》等有关法律援助的规定。本中心决定对关于案提供法律援助。现指派你所承办该案。该承办人在收到本通知之日起日内持本通知来本中心办理有关手续。
宿松县法律援助中心年月日
基于指派模型的人岗匹配问题研究 篇3
关键词：人岗匹配,效益最大化,指派模型
0前言
杰克·韦尔奇说：，“用人之道，其精髓就是将合适的人放在合适的位置上，使其长处得以发挥，短处得以克服。这样个人和组织都能得到持续的发展。”对人岗匹配问题进行研究，使得“用人所长”、“人尽其才”，将为企业吸引、发展和保留人才，增强企业核心能力发挥重要作用。而我国目前人力资源配置仍处在观念导入阶段，岗位设置主要是依靠管理者的经验与主观判断，缺乏科学合理的量化管理，不能将合适的人才安排到合适的岗位，结果导致人浮于事、效率低下等现象时有发生，严重影响了企业的生存和发展[1]。因此，建立一个科学透明，客观公正的评判方法保证企业员工与岗位合理适配，是人力资源管理亟待解决的问题。
目前国内外人与岗位匹配研究主要集中在概念、原理和实现方法等方面。对人与岗位匹配的测算方法，国内外学者也进行了相关研究。在国内，李耘涛和赵涛运用360度模糊综合评价模型对人力资源岗位匹配度进行定量研究：孔庆如和李小平以概率分析为基础，提出了基于概率分布特征的岗位配置与调度优化方法[2]。但大多数研究只是从理论和人工算法上对人岗匹配问题进行分析，缺乏科学的测评工具，从而导致匹配可操作性不强。因此，本文在以往研究基础上，结合计算机软件，为人岗匹配提供有效的决策依据。
1 人岗匹配的数学模型
在人力资源管理过程中经常会遇到这样的问题企业人力资源部门要指派不同员工到不同岗位工作，经考核这些员工在不同岗位上工作效率或成本有所不同，作为人力资源部门经理应如何根据企业需要，指派适当的员工到适当的岗位上工作,最大限度地利用企业现有人力资源,使企业以最小成本获得最大经济效益[3]。这就是基于指派问题的人岗匹配问题。
假定有n个员工Pi(i=1,2，…，n）,m个岗位Sj(j=1,2，…，m），并满足以下条件：(1)每个员工只能分配一个岗位；(2)xij=1时，表示指派第i个员工到第j个岗位，否则xij=0；(3)cij是第i个员工在第j个岗位上的效率（或成本）（cij≥0），对应的矩阵为[cij]；(4)k=max(n,m），当员工数目n大于岗位数m时，k=n，虚拟k-m个岗位，对应的效率为零，否则虚拟k-n个员工，对应的效率为零。当目标是求成本最小时，对应的成本取无穷大。则人岗匹配数学模型如下：
在进行人岗匹配的过程中，人力资源部门还可以考虑出勤率、工作差错率等其他单项指标，建立以上数学模型，归结为有m项工作安排n个人去做的最优指派问题。对于此类模型,求解的基本思想是将问题转化为能够用匈牙利算法求解的AP模型,然后用匈牙利算法求解。但是，匈牙利算法由于可操作性不强等缺点一直不被企业采用。事实上，采用Win QSB计算机软件同样可以求解此类模型。而且比匈牙利算法更科学、更具有可操作性。
2 人岗匹配数学模型的优化
以上模型只是在假设每个员工有且仅有一个岗位的基础上建立的岗位指派模型，但通常在分配岗位的过程中，经常会出现某些员工因为某些限制条件（例如没有取得职业资格证）而不能在某些岗位工作，这样就必须还要考虑员工的专业素质等限制性条件。这就是有限制条件的人岗匹配的优化模型[4]。
假设员工Pi由于限制条件不能在岗位Sj上工作，其他假设条件不变。此时需要令员工Pi的工作效率cij为零（或工作成本无穷大）。目标仍然是使企业总效率最高(或成本最小)。优化后数学模型可以归结为有限制条件下的最优指派问题,同样可以用“匈牙利算法”来求解。
在进行人岗匹配的过程中，人力资源部门通常需要考虑的并非是某一种指标，还需要综合考虑员工绩效、成本、工作差错率等多项指标，此时可以引入权重wi进行求解。假设有m个指标，有：
其数学模型如下：
其中：cij表示效益、效率等正相关指标时取正数，表示成本、耗时等负相关指标时取负数。该模型综合考虑了多种指标，各个指标权重wi大小可以通过专家经验来设置，也可以通过问卷调查的方式确定。
3 应用实例
某企业的人力资源部门经理根据企业需要，指派5位员工到5个不同的岗位上工作，经过考核得知，各员工对应各岗位的成本与绩效（百分制）如表1所示。问该企业人力资源部门经理如何配置这5位员工，使企业以最小的成本获得最大的经济效益。
由于该企业只考虑绩效和成本两个指标，并通过专家经验设置绩效权重为70%，则相应成本权重为30%。进行简单代数运算，用绩效权重的70%减去成本权重的30%后，得到表2所列的综合考核成绩。
目标函数为：
约束条件为：
其中xij=1或0;
通过WinQSB计算机软件求解，结果如表3所列。
由Win QSB求解结果可以看出，安排甲在E岗位工作，乙在C岗位工作，丙在A岗位工作，丁在D岗位工作，戊在B岗位工作，能实现最佳的人岗匹配。
4 结论
本文在单目标人岗指派模型基础上，建立的多指标人岗指派模型，具有公开、公正、科学等特点，可应用于指导企业各部门的人员配备，为公司创造更大的效益。同时，运用指派模型结合企业关键测评指标可以保证企业员工与岗位达到最佳动态匹配状态。但是，该模型要求企业对每个员工的多项指标进行考核，会耗费较多人力和物力。因此，对于这样的人员指派问题采用本方法会给科学的人岗匹配带来一定的困难，这些都有待于进一步的研究。
参考文献
[1]袁有明:《人力资源管理中的人岗匹配问题》[J];《市场周刊》2008(9):140-141。
[2]付继娟:《人与岗位匹配的国内外研究综述》[J];《武汉职业技术学院学报,2004,(2):41-43
[3]熊伟:《运筹学》[M];机械工业出版社,2005:112-116。
指派模型 篇4
编号：济历城查指字[2013]第号
发往单位：司法所
调查员：、事由：被调查人：
批准人：指派时间：
要求上报时间：
被调查人联系电话：
委托单位：
社区矫正对象变更居住地调查指派通知书
编号：济历城查指字[2013]第号司法所：
根据《社区矫正实施办法》的有关规定，本局受司法局委托，决定对关于变更居住地事项进行变更前社会调查工作。现指派你所、为该案调查员负责调查该案。请调查员在收到通知之日起，于年月日前完成对该案的调查工作并上报区局。
特此通知！
济南市历城区司法局
指派问题的EXCEL求解模板 篇5
在管理实践中经常会遇到这样一种问题:有n个人(P1,P2,……,Pn)需要完成m项任务(T1,T2,……,Tm),简单指派问题是m=n,即n项任务恰好有n个人可以分别去完成[1]。扩展指派问题可以是m=n,也可以是m≠n,即每项任务或交给一人,或由几人去完成;每人或完成一项任务,或完成几项任务[2]。为此在分配过程中要充分考虑个人的知识、能力、经验等因素,同时也要考虑任务的难度、重要性、风险等因素,如何分配才能使工作效率最高或消耗的资源最小?这类问题就属于指派问题。
指派问题是线性规划中的特殊形式,匈牙利数学家克尼格(Konig)提出了命名为匈牙利法手工计算方法,但计算量相当大。采用单纯法可以运用计算机的相关软件进行求解,相比之下,微软Office办公软件Excel内置的“规划求解”功能的操作更为简便,且应用广泛[3]。本文在Excel规划求解功能的基础上,通过对单元格函数程序的编制,形成指派问题的标准化求解模板,达到智能化求解指派任务的目的。
二、简单指派问题求解模板的编制和应用举例
简单指派问题是m=n,即n项任务恰好有n个人可以分别去完成,每个人只能完成一项任务,每项任务只能由一个人完成,不同人完成不同任务的效率是不同的,指派的目标是寻求效率最高的分配方案。一个n≤14的简单指派问题Excel求解模板如图1。
1、简单指派问题的求解模板单元格的函数公式[4]
指派问题求解模板的界面分为“工作效率表”和“任务安排解表”两部分。“工作效率表”处于模板的上半部,主要用于输入不同人员承担不同任务的效率,另输入每项任务安排的人数和每人安排任务的数量。“任务安排解表”位于模板的下半部,主要用于读出最优的任务指派方案和最优指派方案下的累计得分。
(1)求解模板中单元格名称的输入
人员单元格C3:C16的编号:依次输入序号P1~P14。任务单元格D2:Q2的编号:依次输入序号T1~T14。另在单元格R2内输入“任务量”,单元格C17内输入“安排人数”。
单元格C2内设置斜线,并输入“人员任务”。在单元格B2内输入“工作效率表”,然后选中B2:B17,点击菜单工具“合并及居中”,合并B2:B16。
在单元格B19内输入“任务安排解表”,然后选中B19:B30,点击菜单工具“合并及居中”,合并B19:B30。单元格B31内输入“得分累计”,并选中B31:B33,点击“合并及居中”,合并B31:B33。
单元格C19内输入引用函数公式:=C2。复制单元格C19,粘贴到单元格D19:R19和单元格C20:C34,引用人员任务编号。
选中单元格B2:R17和单元格B19:R34,设置单元格边框中所有边框,并适当调整单元格的大小和单元格格式,最终得到图1的简单指派问题求解模板的界面。
(2)任务安排表中各单元格函数公式的编制
在任务安排表中,单元格R20内输入人员P1任务量总和的计算公式:
将该单元格用复制粘贴的方法将公式粘贴到单元格R21:R33,得到所有人员任务量总和的计算公式。在单元格D34内输入任务T1安排人数总和的计算公式:
同样将该单元格用复制粘贴的方法粘贴到单元格E34:Q34,得到所有任务量总和的计算公式。任务安排表中累计得分是在单元格B34内输入函数公式:
该公式是任务安排表中单元格D20:Q33的值与各工作效率表中单元格D3:Q16的值的乘积之和,从而求得累计得分。
2、规划求解对话框设置
(1)“规划求解参数”对话框设置
通过菜单“工具”/“规划求解”,打开“规划求解参数”对话框如图2所示。设置目标
单元格的地址是:B34。等于选项组中选择是:最大值。可变单元格选项区域中设置的地址是;D20:Q33。约束选项区域中设置的地址是:
D17:Q17=D34:Q34
D20:Q33=整数
R3:R16=R20:R33。
(2)“规划求解选项”对话框设置
在“规划求解参数”对话框的右侧的一列按钮,单击“选项”按钮,打开“规划求解选项”对话框,可以选中“采用线性模型”、“假定非负”复选框并设置一系列计算精度的参数如图3。然后单击“确定”按钮,返回“规划求解参数”对话框;单击“关闭”按钮,退出规划求解对话框设置。并保存该Excel文件作为“简单任务指派”求解模板。
3、简单指派问题应用实例
例1,某办公室有4名员工可以被指派去完成4项任务,这4名员工以前都负责过这4项工作,并且得到了相应的评分。每名员工完成不同任务的评分见表1。
办公室主任希望找到累计评分为最大的任务指派方案。
求解过程:
(1)打开保存的任务指派求解模板,在求解模板上半部的工作效率表部分输入相关的工作评分,在各位员工对应的任务量栏内输入任务量为“1”,在各任务对应的安排人数行内输入安排人数为“1”,完成输入后的工作效率表如图4;
(2)点击“工具”菜单,选择“规划求解”,在图2所示的“规划求解参数”对话框内点击“求解”按钮,程序自动进行规划问题的求解,并显示“规划求解结果”对话框如图5;
(3)在图5所示的“规划求解结果”对话框内点击“确定”按钮,得到的最优解表如图6所示。即职员P1安排工作T1,职员P2安排工作T4,职员P3安排工作T3,职员P4安排工作T2。累计总得分为369分。
三、扩展指派问题的Excel求解
1、扩展指派问题求解模板函数公式的编制
扩展指派问题求解模板可以计算人员数量和任务数量相等或不相等指派问题。实际工作中往往会出现人员的数量和任务的数量可能会不一致,为此可以通过调整每个人员可安排任务的数量,或者调整每项任务可安排的人数,或者将不能安排的人员和不能安排的任务作为冗员和冗事暂时搁置,等待下次安排。在Excel求解模板上,为了达到智能调整的目的,扩展指派问题求解模板通过修改简单指派问题最后一个人员任务量的单元格为“冗事”单元格,修改最后一项任务安排人数单元格为“冗员”单元格,并编制这两个单元格的函数公式。为此可以对上一节简单指派问题的求解模板作一些修改,将工作效率表中Q2单元格的名称由“T14”改为“冗员”,将C16单元格的名称由“P14”改为“冗事”,修改后对应的引用单元格Q19和C33自动发生引用变化。修改后扩展指派问题求解模板的部分单元格如图7。调整发收不平衡的方式是在单元格Q17内输入函数公式;
用以计算多余人员作为冗员。在单元格R16内输入公式
用以计算多余任务作为冗事。保存该文件作为扩展指派问题求解模板。
由于设置了冗员和冗事,当人员数和任务量不一致时,冗员和冗事起到了调整作用;当人员数和任务量一致时,冗员和冗事的值均为零,因此扩展指派问题求解模板可用于求解任意任务指派问题。
2、应用实例
例2如果在例1中,员工P3准备去进修,而员工P1和P4能力较强,可以安排两项工作,在只有3位员工并且可以完成5项任务的情况下,这4项任务如何安排才能使累计评分最大。
求解过程:
在扩展指派问题求解模板的工作效率表中输入相关的工作评分,并输入每名员工可承担的任务量和每项任务需要安排的人数。由于可完成任务量超过任务需要安排人数,所以有员工可以安排的工作没有得到满足,因此在工作效率表中重新输入每名员工的任务量后,模板自动计算生成冗员数为“1”,然后按例1的步骤(2)、(3)完成规划求解的计算,得到全部的计算如图8。
求解后得到的安排是:员工P1承担工作T1和工作T3的任务,员工P2承担工作T4的任务,员工P3准备去进修不承担任务,员工P4可承担的两项工作只能满足一项,仅承担工作T2的任务,另一工作任务的余量只能作为冗余暂时保留。
四、结语
很多决策过程都会产生指派问题;典型的指派问题有:将工作分配给机器或人,对代理分配任务。将销售人员分配给销售区域,将合同分配给投标人,等等。引入任务指派的求解模板,可有效帮助日常决策过程中的最优化问题,包括指派后达到目标最大化的问题,也包括指派后的目标最小化的问题。建立科学的指派方法,也促进了组织建立一些科学管理制度,如本文的最优人事安排,可以有效地促进组织在管理工作中,建立起对员工工作能力的培训、评价和考核制度,形成对员工工作能力管理的制度性文件。
参考文献
[1]杜红.应用运筹学[M].浙江:浙江大学出版社,2010:P86-92.
[2](美)安德森(Anderson,D.R.)等著;侯文华等译.数据、模型与决策:管理科学篇(原书第12版)[M].北京:机械工业出版社,2009:P167-170.
[3]孙爱萍,王瑞梅.如何利用EXCEL求解线性规划问题及其灵敏度分析[J].办公自动化:2009,11:44-46.
分支定界算法求解指派问题 篇6
, 则标准指派问题的数学模型可表示如下:
模型中，cij表示第i人做第j事所需的时间, 约束条件 (a) 表示每件事有且只有一个人去做，约束条件 (b) 表示每个人做且只做一件事。
2 算法思想
分支定界算法 (Branch and Bound Method, B&B) 的思想是把给定问题分解为若干个较小的子问题，每个子问题又可继续分解，直到子问题不能再分解或不能产生最优解，根据问题的特点和不同的策略，把问题分解为子问题的过程称为分支。在分支过程中，为每一子问题估算对应的目标值的界限称为定界。定界的目的是为了测定界的趋势，留下有价值的或尚不能判定的分支。删除肯定不存在的最优解的分支称为剪支，以达到加速收敛、简化运算的目的。对问题进行分解，确定子问题的解值界限，减去非优的子问题，再进行新的分支，这样由分支到定界到剪支再到分支等反复的过程是分支定界法的基本算法步骤。
根据分支定界算法思想求解指派问题时，暂时不考虑指派问题中每个人只能指派一项任务，即每个人可以完成多个任务，这样将原问题模型 (1) 变成如下松弛模型：
此时，松弛模型 (2) 可行解区域包含了原问题模型 (1) 可行解的集合，因而松弛模型的最优解要优于原问题的最优解。通过松弛模型的解求得原问题最优解的步骤如下：
设原问题的一个解集合为A，松弛模型的一个解集合为B。
Step1：不考虑每个人只能完成一项任务，找出完成各项任务时间最少 (效率最高或费用最低) 的人员，安排其完成该任务。
Step2：如果得到的解是每个人只完成一项任务, 则求解结束，该解也是原问题的最优解。否则，得到的解只是原问题的最优解的一个下界。
Step3：从第一项任务开始固定指派不同人员，而后不考虑该任务及人员重复Step1，求得松弛模型的一个解集合C。如果集合C中的某个解是每个人只完成一项任务，则该解是原问题的一个解，也是原问题最优解的一个上界，将该解加入集合A，其它解加入集合B。
Step4：比较集合B中的解对应的总时间 (效率或费用) ，选择最小者固定指派该人员，该任务不再考虑其它指派。回到Step3，直到完成最后一项任务的指派，得到一个原问题的解，加入集合A。
Step5：比较集合A中解对应的总时间 (效率或费用) ，最小者对应解记作a k (k=1, 2, L) 。
Step6：比较ka与集合B中解对应的总时间 (效率或费用) ，若集合B中存在b f (f=1, 2 L) 对应的总时间 (效率或费用) 比ka对应的小，对解bf重复Step3、4，求得的原问题的解与进行比较，总时间 (效率或费用) 最小者对应的解就是原问题的最优解。
3 实例分析
某单位有4项任务需要完成，要求每个人只能完成一项任务，每个人完成各项任务的时间见下表，问如何安排人员使得完成任务的总时间最少。
暂时不考虑每个人只能完成一项任务，则可行解个数有4!=24个。
求解过程如下：
step1：各列取最小进行指派人员。
在此，22为所有可行解的下界。
Step2：检验是否已得完全指派(题目要求的指派)，若可得完全指派，则该解为原问题的最优解。若否 (如上表右下角标注Not yet) ，固定一个指派，删除该指派所对应的时间表，回step1，计算后找出总计时间最小者。
在指定A做任务1之后，表中第1列的数据在后续计算中不再考虑。
在指定B做任务1之后，表中第2列的数据在后续计算中不再考虑。
在指定C做任务1之后，表中第3列的数据在后续计算中不再考虑。
在指定D做任务1之后，表中第四列的数据在后续计算中不再考虑。
表2～5中，表5总时间最小，在此，28为新的下界，由此处继续。
Step3：固定下一个指派，删除该指派所对应的时间表，回到step1，计算后找出总计时间最小者。
表6～8中表7总时间最小，在此，28为新的下界，由此处继续。
Step4:
表9与10均符合完全指派，较小值32为原问题所有可
行解的上界，任何表之值大于32者均可忽略。
Step5：比较其它分支的表，检验是否有低于32之值，表2、3、4、6、8、10中只有表2低于32，予以进一步分支。
表12为可行解，但其值仍大于表9之值，表11之值虽然等于32，但由此分支下去的也一定大于等于32，并不会低于表9，所以，表9为最优解。
摘要：指派问题是现实生活中经常遇到的一类组合优化问题, 应用十分广泛。优化指派方案就是要求使完成任务的效率最高 (或所需时间最小或所需费用最低) 。本文提出了用分支定界算法优化指派问题, 分支定界算法采用了类似分而治之的算法策略, 在分析一个组合最优化问题的一切可行解的过程中, 采取了必要的限制条件, 设法排除可行域中大量非最优解区域, 从而简化了求解过程。分支定接算法是一种解决指派问题的新方法, 在工作应用中有一定实际意义。
关键词：分支定界算法,指派问题,优化指派方案
参考文献
[1]胡运权.运筹学教程[M].北京:清华大学出版社, 1998.
指派模型 篇7
英语同形异义词是指那些形状相同, 但词义却相差甚远的词。严格来说, 同形异义词可分为二类, 一类是完全同形异义词, 即读音, 词形完全相同, 但意义不同的词汇。如下表所示。
第二类是同形异音异义词, 指的是拼写相同, 但发音和意义都不相同的词汇。如下表所示。
对于完全同形异义词, 其读音完全相同, 不具备重音随意义的改变而改变的情况, 不在本文的研究范围内。而对于同形异音异义词, 其拼写相同, 但很多词具备类似于record的重音会随意义和词性改变的现象。对于不同词性对应的重音位置, 可以通过经典音位学和重音的基本理论来进行探讨。
2 英语词重音
英语是一种典型的重音语言, 20世纪90年代起, 西方学者成功地把优选论和重音结合起来, 取得一系列成果。如Kager根据Hayes的研究将重音语言的属性归纳为:1) 主峰属性:重音语言的典型特征是, 形态或句法成分 (如词干, 词, 短语等) 都有一个单一的韵律峰;2) 分界属性:重音趋于靠近组构成分 (如短语, 词, 词干等) 的边缘微循环部分;3) 节奏属性:重音语言明显趋于重轻音节搭配的节奏模式。节奏交替体现在, 避免出现相邻的重读音节或者避免延长非重读音节;4) 音量敏感性:重音通常置于具有内在突显性的成分上, 如重音的趋向就是被长元音 (而不是短元音) , 双元音 (而不是单元音) 和闭音节 (而不是开音节) 所吸纳。
2.1 动词的重音规则
动词的重音规则。
形容词的重音规则。
动词和形容词的重音分布受同一个规则的支配, 具有相同的模式及其重音规则可以解读为:
1) 对同形异义词而言, 如果词尾是一个短元音+一个辅音, 或只有一个短元音的形式, 那么单词的重音一般指派给倒数第二个音节。
2) 同样是对于同形异义词而言, 如果词尾是一个长元音+一个辅音, 或一个双元音+一个辅音, 或只有一个长元音, 或只有一个双元音, 那么单词的重音一般指派给词尾音节。
3) 如果词尾是一个短元音+至少两个辅音的形式, 那么单词的重音也一般落在词尾音节上。
这跟音位学里面的重音理论不谋而合。音段是生成音位学里面的基本概念。生成音位学家把音段定意为, 组成语符的元音和辅音。音段分为强音丛和弱音丛。强音丛是指一个元音核心后面跟着两个以上的辅音。弱音丛是指一个简单元音核心后面没有辅音, 或只有一个辅音。生成音位学从前缀, 后缀, 动词和名词等角度展示了单词重音的规则, 这跟从词性方面分类的重音规律是一致的, 如下:
1) 单词的重音规则
a.V→[1stress]/x___Co]“]”代表末尾例如:decide console
b.V→[1stress]/x___Co W]“]”代表末尾例如:consider abandon
“V”代表元音, ”→”表示得到, ”[1stress]”表示一级重音, “___”代表位置, ”Co”代表任何数目的的辅音 (consonant) , “W”表示弱音丛, ”affix”表示后缀, ”/”表示在下列情况下, ”X”表示在该词内任何音段。
2) 动词的重音规则
a.V→[1stress]/___ (V) Co1]这条规则意指重音从词尾出发, 遇到弱音丛, 就继续前移, 例如edit[‘edit], consider[kən’sidə]。
b.V→[1stress]/. (+tense) Co]这条规则意指重音从词尾出发, 遇到强音丛则落下, 不再前移, 例如maintain[mein’tein], devote[di’vəut]。
c.V→[1stress]/___Co2]这条规则旨在说明含有两个辅音以上的音节, 即可视为可接收重音落点的强音丛。例如collapse[kə’læps], lament[lə’ment]。
2.2 名词和派生词的重音规则
名词的重音规则。
派生词的重音规则。
名词和派生词的主要重音规则大致相同, 重音指派的规则如下:
1) 对同形异义词而言, 如果词尾倒数第二个音节是一个短元音+一个辅音或只有一个短元音, 那么重音指派给倒数第三个音节。
2) 如果词尾倒数第二个音节是含有一个长元音, 那么无论该音节有没有辅音, 重音都指派给这个音节。
3) 如果词尾倒数第二个音节是一个短元音+至少二个辅音, 那么重音也指派给这个音节。
承接上述动词的重音规则, 下面将着重分析名词和派生词的重音规则。
这个规则可以分成两种不同情况下的规则:
a.V→[1stress]/___Co[V-tense]Co1+V–tense]Co1这条规则意指重音从词尾倒数第二个音节出发, 遇到含有短元音的弱音丛, 就继续前移。例如America[ə’merikə], cinema[‘sinimə]。
b.V→[1stress]/___Co[V-tense]Co]这条规则意指重音从词尾倒数第二个音节出发, 如果该音节含有长元音, 则重音指派给这个音节。例如aroma[ə’rəumə], anecdotal[ænek’dəutəul]。
我们从这些规则, 可以观察出重音与强弱音丛之间的关系。大体上可以归纳为重音一般落在强音丛上。即重音一般会指派给含有两个辅音的音丛。但也有一些特例, 如两个弱音丛, 相当于一个重音, 重音遇到两个弱音丛也会落下来。
3 优选论视角下的英语同形异义词重音
3.1 英语词重音的制约条件的确定
优选论最先是由Prince和Smolensky提出。关于优选论的具体操作过程, 国内已有不少介绍。其中成果最丰厚的当属Kager, Kager于1999年出版的Optimality Theory, 于2001年由外研社在国内出版。根据我们上文提到的Hayes的关于重音语言的四个普遍性属性研究, 可以大致得到这些涉及重音的制约条件。
1) FT-BIN音步有两个音节或莫拉构成。FT-BIN的作用是限制一个轻音节构成的音步。换言之, 重音不可能出现在一个轻音节构成的音步上面。
2) NONFINALITY重音靠近组构成分的边缘位置。
3) *CLASH不能出现相邻重音。根据Halle和Vergnaud的理论, 1.每个音步必须有重音, 音步可分为左重音步和右重音步, 即不可能出现相邻重音。
以上这些都是关于重音的一些合格性准则, 即是在英语里面的重音的普遍现象的基础之上提出来的, 我们可以把它们归纳为英语词重音的制约条件。
优选论评价器除了有触发变化的忠实性制约条件外, 还有与此冲突的标记性制约条件。标记性制约条件本质上是要求输出项保持其原有的词汇基本形式的属性, 从则使输入项和输出项具有一定相似性。
3.2 英语同形异义词重音的优选论分析
1) 同形异义词中的单音节词
英语中的同形异义词有很大一部分是单音节词, 例如board, mouse等, 并且绝大部分属于完全同形异义词, 单音节词仅由一个音节构成, 所有的单音节词都是重读的。
2) 同形异义词中的双音节词
英语同形异义词中绝大部分是双音节词。这一现象在词源学上的理据是两种。第一种是音变汇合的结果。英语在其漫长的发展过程中, 吸收了很多外来词汇, 这些词汇的不同读音与英语的语音汇合。第二种是词义发展变化的结果。在长期的发展过程中, 同一个词的两个或两个以上的意义差别越来越大, 以致人们逐渐把它们视为由一个词分化成两个或多个意义不同的词。而这些词多是不带词缀的双音节词, 所以同形异义词中以双音节词居多。
下面几个具有双重词性的同形异义词最具有启发性。如作为动词, produce (生产) , project (投射) , object (反对) , refuse (拒绝) 重音均在第二个音节上。而作为名词, 它们的重音都在第一个音节上 (意思分别是项目、客体、垃圾、农产品) 。
首先produce作为一个双音节词, 其读音方案有如下几种: (1) .[‘prodjus] (2) .[p’rɔdjus] (3) .[prɔ’djus] (4) .[prɔdju’s]。
其次, 分别从两种不同词性的角度分析produce的重音指派规律。
1) produce作动词用时, 其重音只能落在第二个音节上面。因为根据经典音位学动词重音的基本规律, 动词词尾如果有短元音, 则需要前移。Produce词尾是由长元音和辅音构成的组合, 所以重音不需前移。从制约动词重音的条件上面分析, produce只能符合V→[1stress]/. (+tense) Co]这条规则。因为这条规则意指这条规则意指重音从词尾出发, 遇到强音丛则落下, 不再前移, 则重音指派给这个音节。根据优选原则, 排除了 (2) .[p’rɔdjus]。那么根据FT-BIN, NONFINALITY和*CLASH这三个忠实性制约条件之前, 排除掉了 (1) .[‘prodjus]和 (4) .[prɔdju’s]。进而得出了其最优的输出项[prɔ’djus]。
2) produce作名词用时, 其重音只能落在第一个音节上面。因为根据经典音位学名词重音基本位置, 重音从倒数第二个音节出发, 而produce只有两个音节, 重音只能落在第一个音节上面。从制约名词重音的条件上面分析, produce只能符合V→[1stress]/___Co[V-tense]Co1+V–tense]Co1这条规则, 因为这条规则意指重音从词尾倒数第二个音节出发, 遇到含有短元音的弱音丛, 就继续前移。根据优选原则, 就排除了 (3) .[prɔ’djus]。那么根据FT-BIN, NONFINALITY和*CLASH这三个忠实性制约条件之前, 排除掉了 (1) .[‘prodjus]和 (4) .[prɔdju’s]。进而得出了其最优的输出项[p’rɔdjus]。
4 结束语
英语同形异义词的重音特征基本与英语重音指派的一般规则是一致的。不管是双音节词还是多音节词, 都可以结合优选论和生成音位学的一般规律对其进行解释。优选论的阐释力已逐步得到了认可, 而优选论在音位学方面的阐释力则更加强大。该文将优选论与生成音位学的重音理论结合, 探究同形异义词之一语言现象的潜在规律, 改变了之前的过多的句法研究和音位研究。
摘要：同形异义词即形态完全相同, 但读音和意义不同的词汇。英语有很多这样的词汇。有不少词即可以做动词, 也可以作名词, 但其读音也随着词性的改变而改变。该文根据生成音位学和英语重音指派的基本规律, 用优选论的评估器, 试图阐释出同形异义词的重音落点规律。
关键词：英语同形异义词,优选论,生成音位学,重音指派
参考文献
[1]王茂林.音系学重音理论简述[J].外语教学理论与实践, 2009 (3) .
[2]陈虎.自然语言的重音分布及其语义解释—西方研究综述[J].现代外语, 2003 (1) .
[3]端木三.重音、信息和语言的分类[J].语言科学, 2007.
[4]焦芳, 杨箫华.英语同形异义词的动因分析[J].牡丹江师范大学学报:哲社版, 2006 (4) .
[5]王丹, 杨玉芳.自然语言中焦点与重音关系的研究进展[J].陕西师范大学学报:哲学社会科学版, 2004 (7) .
[6]许希明.英语重音指派与元音变异的认知研究[D].宁波:渐江宁波大学, 2007.
[7]许曦明, 杨成虎.语音学与音系学导论[M].上海:上海交通大学出版社, 2011.
指派模型 篇8
指派问题是一种特殊的0-1整数规划问题，目前对于小规模指派问题，匈牙利法是一种常用的简单有效的解决方式；而对于大规模指派问题，则因为计算量过大，因而运算较为困难。基于生物群体遗传进化操作的遗传算法，则很适合群体规模较大问题的优化处理。因此将规模较大的指派问题应用遗传算法进行求解，就会较为简便快捷。
1 遗传算法
1.1 遗传算法简介
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[1], 它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和进化机制, 广泛应用于近似最优化、生产调度、图形分割及自动控制等领域。
1.2 遗传算法基本步骤[2]
(1) 初始化。设置初始种群、最大迭代次数及迭代计数器。
(2) 适应度评价。对当前种群计算其个体适应度。
(3) 进化操作。主要是通过选择、交叉、变异、倒位等算子作用产生下一代群体。
(4) 终止条件判断。如果已经求得最优解，则终止；否则重复以上两个步骤。
2 指派问题的遗传算法实现
2.1 指派问题模型描述
人们日常生活和工作中，经常会遇到这类问题：有n个任务需要n个人去完成，每个人完成每个任务的效率不尽相同，要求一个人只能完成其中一个任务，一个任务只能由一个人完成。要求合理分配之后，所达到的总体效率最好，这就是指派问题。
那么，根据优化模型理论，当目标为极大值时，指派问题的数学模型[3]如下：
其中，当指派第i个人去完成第j个任务时，xij=1；否则xij=0。cij表示第i个人去完成第j个任务的效率；约束条件（2）表示：第i个人只能完成一项任务；约束条件（3）表示：第j个任务只能由一个人完成。
2.2 指派问题的遗传算法设计
遗传算法[4]设计是完成遗传运算的具体方法，涵盖了决策变量的基因型与表现型之间的编码和解码，个体适应度函数构造，遗传算子构建，控制参数设置等过程。
2.2.1 指派问题适应度函数
针对指派问题在求解目标函数为极大值时的情况和考虑指派问题可行解的非负性前提下，其个体适应度与目标函数值是成正比。因此，指派问题的适应度函数构建为如下所示：
其中，xij表示第i个人是否去做第j个任务。cij表示第i个人完成第j个任务的效率。
F越大，表示个体适应度越好，其可行解越好，能够以较大概率遗传到下一代。当F取值最大时，则表示已经达到最优解。
2.2.2 指派问题染色体编码
染色体[5]编码质量是影响遗传算法计算效率和准确度的重要因素。考虑到指派问题的特殊约束性质：即每人只能完成其中一个任务且每个任务只能由一人完成。针对决策变量xij的取值，其基因型编码不采取通常的0-1二进制编码，而采用常用的十进制编码。并且，每个基因块只有两个基因位，分别表示决策变量的行下标取值和列下标取值。当问题规模为n时，则指派问题决策变量染色体编码表示为：
在这种染色体编码十进制表示方式下，对于每个个体，其染色体的n个基因块在处理时按照如下规则进行：
(1) 各代群体每个染色体中各基因块第一位分别赋予固定值：范围为0到n-1，即R11=0, R21=1，…Rn1=n-1。其目的是保证决策变量选取位于不同行。
(2) 各代群体每个染色体中各基因块第二位分别赋予无重复随机值：范围为0到n-1，即R12、R22…Rn2每次取0到n-1的随机全排列值。目的是保证决策变量选取位于不同列。
通过这种方式进行指派问题染色体编码，可以只对基因块中第二位编码进行随机产生，提高了搜索效率。同时，由于是十进制编码，各个基因块的值组合可以直接定位于效率矩阵中的对应元素位置，加快运算效率。
2.2.3 指派问题遗传算子改进策略
一般情况下，遗传算法遗传过程和进化过程主要是通过选择、交叉、变异及倒位等遗传算子组合运算完成群体迭代。考虑指派问题组合优化的特殊性：即可行解必须位于不同行不同列，已在决策变量染色体编码中进行了约束限制，那么，在遗传进化过程中，无需再对种群群体进行变异操作和倒位操作。
因此，通过优化染色体编码，在遗传进化过程中仅通过选择和交叉策略实现种群迭代，有效地提高了运算效率，加快了最优解的获得。
3 算法仿真
控制参数的设置是否合理对于遗传算法而言，关系到其优化效率。在此，我们设置种群规模为80；交叉概率为Pc=0.6，各基因块位置不变的情况随机配对基因块第二位（此时也就相当于包含了变异运算）；选择运算根据目标极大化特点，采用轮盘赌[6]策略进行优化选择。
仿真验证时，我们只需输入效率矩阵阶数和对应效率矩阵的各个元素值则可获得最优解。
假设效率矩阵阶数为5，对应的效率矩阵如下所示：
经过运算之后得到的最优解为[0:2------1:1------2:3------3:0------4:4]，其适应度为F=77。
4 结束语
在指派问题中，对于阶数越高的效率矩阵而言，运用此改进的遗传算法进行求解，效果越明显，效率也越高。如果目标函数是极小值情况，只要通过函数变换，转化为极大值则可。通过仿真验证，这种通过优化染色体编码和减少遗传算子作用相结合的改进策略，对于大规模指派问题求解十分有效。
参考文献
[1]周明, 孙树栋.遗传算法原理及应用, 北京:国防工业出版社, 1999, 6.
[2]张权, 修宏伟.遗传算法在指派问题中的应用, 沈阳建筑工程学院院报, 1997, 13 (1) .
[3]李德, 钱颂迪.运筹学, 北京:清华大学出版社, 1982, 4.
[4]Hplland J H.Adpation in Natural and Artifical systems.AnnArbor:University of Michigan Press, 1975.
[5]Davis L.Handbook of Genetic Algorithms, New York:VanNostrand Reinhold, 1991.
指派模型 篇9
1 指派问题数学模型
为方便研究将平衡与非平衡两种指派问题归纳为如下两种形式研究:
设有n项任务,要派m个人去完成,Cij表示第i个人完成第j项任务要付出的代价,tij表示第i个人完成第j项任务所需时间,则如何分派会使整体效益最好,即用时少费用低。
为建立模型引入0-1变量:
1.1 人数大于或等于工作项目时m≥≥n≥
1.2 人数小于工作项目时m<n
式中b———每人限制的最大工作量
2 指派问题的模拟退火遗传混合算法实现
2.1 模拟退火遗传混合算法思想
Step1:选定初始温度t=t0
利用模拟退火算法的温度控制方法选定较合适的初始温度。如果初始温度选择过高会导致计算时间较长,从而降低计算效率。如果初始温度选择过低又有可能使最终收敛得不到最优解。因此根据(14)式的条件来确定初始温度t0。
式中Δfij———任意两个相邻的温度差
Step2:确定初始群体initpop
首先,用实数编码方法对任务数n进行编码且不变;
其次,用实数编码方法对人数m进行编码且可以随机抽取;
最后,利用随机生成法对l!l=m-1个解中随机选取一个解为初始群体initpop。
Step3:构造适应函数f0=fitfun1,ft=fitfun1
Step4:利用遗传算法对初始群体initpop进行优化,产生种群seedpop1
(1)确定评价函数eval Vi
取一个小于1的实数α=0.9,fie是随着i的增大而不断减小的基于序的评价函数,则评价函数eva Vi是随i的增加(fie的减小)而缓慢减小的。
(2)利用评价函数可以确定进入种群的个体
当qi-1≤γ≤qi时(γ为(0～1)的伪随机数),第i个染色体进入种群,从而形成种群seedpop1。
Step5:利用模拟退火算法对种群seedpop1进行训练,产生更优的新种群seedpop2
(1)对seedpop1中1～m个体的适应值与初始群体中f0的值进行比较,满足条件的进入seedpop2;
(2)否则,根据评价函数来判断进入seedpop2的个体。当个体的适应值满足时,则选择进入seedpop2;
(3)经过优化训练,产生新种群seedpop2。
Step6:对新种群seedpop2进行交叉、变异,产生子代children
(1)对新种群seedpop2进行双亲双子法交叉,交叉率β,生成crosspop;
(2)再进行变异,交叉率ε,生成mutpop;
(3)生成子代children。
Step7:返回Step4,直到满足终止条件
Step8:得到最优解
3 算例演示
某大型生产企业为生产和人员安全每年都要定期对生产设备进行检修,检修分为平时检修和7月分大检修。现取其中一个车间来做算例,该车间只有3个维修工,平时每次平均会有2个地方出现故障,到7月大检修时该车间5个检修点都要停止运作重新进行检查和修理。已知工人维修故障所需时间Pij见表1,每个维修工的基本维修费用Cij见表2,注:在7月份大检修时天气比较炎热为保证维修工安全要求每个工人至多维修两个故障点。
单位:小时
单位:百元
混合算法相关参数选择α、初始时间t0=6、交叉率β=0.2、变异率=0.05。利用前面设计的混合算法进行运算得到结果及比较结果见表3,运行次数都为10次。按照该方案进行分配所得到的完成任务的花费时间大约要比单一使用模拟退火或遗传算法获得最优解短五分之二。
4 结论
本文结合模拟退火算法和遗传算法的优点,提出模拟退火遗传混合算法来解决实际中的指派问题。指派问题属于组合优化问题,很适合用本文研究的算法来实现。这种混合算法能够准确快速地求解最优结果或分配方案,针对较大规模的指派问题,能够缩短搜索时间,取得良好的效果。
参考文献
[1]贺国先.现代物流系统仿真[M].北京:中国铁道出版社,2008.
[2]焦永兰.管理运筹学[M].北京:中国铁道出版社,2000.
[3]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[4]谢凡荣.求解指派问题的一个算法[J].运筹与管理,2004(6):24-26.
[5]张新辉.任务数多于人数的指派问题[J].运筹与管理,1997(3):15-18.
[6]Cattrysse D G,Van Wassenhove L N.A survey of algoirths for the generalized assignment problem[J].Europena Joumla ofOperationla Research,1992,60(3):260-272.