关于多因素模糊指派问题的数学模型
时间：2022-03-06 08:07:05 浏览次数：次
〔摘要〕本文从经典指派的一般分析出发，运用模糊数学的方法，通过建立单因素“印象矩阵”，对程度模糊集加权、计算单因素评判矩阵、建立多因素评判矩阵一系列过程及最小调整法，对多因素指派问题进行综合分析和研究，提出了一种关于多因素模糊指派问题的新的数学模型，解决了经典指派问题在实际问题中的某些不足，进而得到一种在实际问题中普遍适用的方法。
〔关键词〕指派；最小调整法；模糊集；评判矩阵
中图分类号：F224．3文献标识码：A文
章编号：1008-4096(2008)06-0026-03
一、 引言
运筹学所研究的指派问题，通常是传统的指派问题。但一般情况下，在工作未完成之前，其效率矩阵中的元素应该是不确定的。为了得到具有指导性的决策,有必要对效率矩阵中的元素进行统计或粗略估计，由此产生了更加贴近于现实生活的模糊指派问题。有关模糊指派问题，已有诸多论述，但方法不一。本文通过对多因素指派问题进行综合分析和研究，提出了一种关于多因素模糊指派问题的新的数学模型。
运筹学中的指派问题的一般提法是：设有n个人（或机器等）A1,A2,…，An,分派去做n项工作B1,B1,…，Bn，要求每项工作需且仅需一个人去做，每个人需做且仅做一项工作。已知A1完成Bj工作的时间（如工时、成本、费用等）为Cij，问如何指派，才能使总的工作时间最少？
由Cij组成的方阵C=(Cij)n×n称为关系矩阵，只要关系矩阵C给定，指派问题也就相应确定。
在运筹学中的求解指派问题一般用匈牙利算法[1]，由于它由匈牙利数学家柯尼格提出，因此而得名。此外还有最小调整法[2]，该方法更加便捷。
例如：（最优匹配问题）现有A、B、C、D四项工作，需要甲、乙、丙、丁四人去做，并且每人只能做一项工作，同时每一项工作必须且只需一人去做，四人做每项工作所支付的费用如下：
利用最小调整法，取各列的一个最小值，并加括号，然后按使目标函数增值最小的原则进行调整，使每行有且仅有一个加括号的元素为止，便得到最优指派[3]：甲完成C，乙完成Ｂ，丙完成Ｄ，丁完成A。所支付的总费用f=4+4+9+11=28（k元）最低。
这种经典指派问题所考虑的因素单一，就是支付的费用，并且支付的费用是明确的数据，表示的意义也相同。然而在实际问题中，常面临已下情形：
１．经典指派中的每个人对工作的数据必须明确给出，但在实际问题中，如果考核的对象过多，则数据就很难获得。
２．在实际考核中的数据未必都是明确的，如在上例中如果考核甲、乙、丙、丁四人的工作效果，由专家、单位领导和同事评价可以给出效果很好、好、一般、不好等考核数据，即需要采用一些模糊语言作为不同程度的评语，对于这些模糊的数据是无法用经典的指派来解决的。
３．经典指派中通常考虑同一种因素，这在有些实际问题中是远远不够的。例如某大型公司欲对其员工进行素质培训，需要甲、乙、丙、丁四人分别讲授A、B、C、D四门课程，这时就不能只考虑费用最低，同时还要达到最好的教学效果。而考核教学效果就需要对教师所讲授内容的熟练程度、涉猎的深广度、逻辑性、生动性、启发性等因素进行综合考虑。因此，在考虑的因素性质不同的时候，或考虑的因素较多的时候，经典指派就不太适用。
为此，下面本文利用模糊数学的方法解决以上存在的问题。
二、数学方法
前面例子是四个人完成四项工作，现假设有n个人{p1,p2,…，pn}及n项工作{w1,w2,…,wn}，要使总支付费用最低，则要考虑n个人去做n项工作的支付费用构成的n阶关系矩阵
利用最小调整法可得到一个最优指派。
在有些问题中，所要解决的问题是要考虑的因素很多，并且考核数据是在不明确的条件下进行的，因此，如何完成n个人完成n项工作的指派问题，就需要利用模糊综合评价的思想去考虑，由此得到评判矩阵B，然后再利用最小调整法解B，求出最优解。为此，提出如下方法：
1．建立单因素“印象矩阵”
设P={p1,p2，…,pn}为被指派的n个人组成的集合，W={w1,w2,…，wn}为所指派的n项工作组合的集合，U={u1,u2,…，un}为所考虑事物相关的因素（如考核教师教学效果时的熟练程度、涉猎的深广度、逻辑性、生动性、启发性等因素）集合，其中ui为第i个因素（i=1,2,…，l）。
对于U中的第i个因素ui，设所有可能出现的评语有m个，记作V={v1,v2,…，vm}，称之为评语集或程度模糊集（如{很好、好、一般、不好}；{优、良、及格、不及格}等），用来刻画每个人完成工作的熟练程度或满意程度。
由因素ui确定该事物对评语vj（j=1,2，…,m）的隶属度rij，得出第i个因素ui的单因素评价集
称此矩阵为在因素ui下完成工作wk的“印象矩阵”，由于k=1,2,…，n，所以在情况ui下可以得到n个类似矩阵Ri1,Ri2,…，Rin。又由于ui∈U(i=1,2,…，l)，所以整个过程可以得到l×n个这样的矩阵RiK(i-1,2,…，l,k=1,2,…，n)。
2．对程度模糊集加权
由于程度模糊集{v1,v2,…，vm}中各种评价的作用不尽相同，其重要性不宜平均看待，必须综合考虑。因此在第i个因素ui(i=1,2,…，l)情况下，对程度集{v1,v2,…，vm}加权，得到权重矩阵Qi=（q1,q2,…，qm），qj∈［0,1］,∑mj=1qj=1。其加权原则是：对于作用较大的vj，给予较大的权重，作用较小的vj，给予较小的权重或零。
3．计算单因素评判矩阵
计算矩阵：Oi*RiTk
这里取*为模型M(,+)（普通矩阵乘法），为加权平均型的综合评判[4]，依权重的大小对所有因素均衡兼顾，比较适用于要求总和最大的情形。RiTk是Rik的转置，并设
5．计算矩阵B的最优解
利用经典指派中的最小调整法求出最优解，
最小调整法步骤如下：
（1） 取矩阵的每列的一个最小（最大）值，加括号，得到一个最小（最大）方案。若这些加括号元素又分属于不同行，则得到相应模糊指派问题的最优解，否则转（2）。
（2） 把有两个以上加括号的元素的行中的某一个改到同列的其他处，待到某一无加括号元素行中有一元素加括号，则算一次调整。如此进行，直到每行有且仅有一个元素加括号为止。每次调整均以目标函数（其值为各加括号元素之和）增值最小为原则，即得到相应指派问题的最优解。
这里需要指出：
（1）在单因素情况下只需计算到第3步，然后计算B的最优解。
（2）在实际中，很多信息来源于人，因此带有一定的主观性，可能包含了一些错误信息，但从总体上去分析利用综合评判的思想可以去掉错误信息。此方法对于因素很多时显得很麻烦，但在实际问题中还是有一定效果的。
参考文献：
［1］程理民，吴江，张玉林．运筹学模型与方法教程［M］．北京，清华大学出版社，2000．
［2］夏少刚．运筹学——经济优化方法与模型［M］．北京，清华大学出版社，2005．
［3］邹开其，杨昕光．指派问题的模糊方法［J］．模糊系统与数学，1999，（Vol．13）．
［4］陈水利，李敬功，王向公．模糊集理论及其应用［M］．北京，科学出版社，2005．
(责任编辑：杨放)
推荐访问： 指派 数学模型 模糊 因素[关于多因素模糊指派问题的数学模型]相关文章