Vague指派问题的求解方法研究

1、vague指派问题的求解方法研究摘要：vague指派问题的特殊性在于用vague值表述效益矩阵，进而反映了指派问题中存在的诸多不确定性和模糊性。论文根据vague值的 特点，提出了 vague指派问题的求解转化为经典指派问题思想，进而借助“马太效应”函数、特征值向量和pareto三种方法实现问题的求解。最后，论文以参考文献中的一组数据为例，采用以上方法进行计算，得到了理想的结果。关键词：运筹学；vague指派；记分函数；特征值；pareto中图分类号：0224文章标识码：a文章编号：1007-3221 (2015) 02-0058-06引言指派问题是运筹学中一类特殊的线性规划问题，用于解决如何

2、分派n个人去完成企业中n个不同的任务，以获得最佳的工作效率。指派问题中的效益矩阵代表每个人完成不同工作花费的时间，属于极小化问题，如果效益矩阵的含义有所变化，变成每个人完成不同工作得到的收益，指派问题就变成求目标函数极大的问题。一般的，指派问题的数学模型可以表示为：其屮，h标函数的系数cij 0 (i, j=l, 2, n)o通常，把这些数写成矩阵形式：c称为系数矩阵或效益矩阵。指派问题的形式很多，平衡指派问题研宄人数与任务数相等，一人一事且一事一人。这种问题可以借助于匈牙利法、削高排除法、缩阵分析法和差额法等进行求解。广义指派问题也有很多形式，如人数大于事数，一人一事且一事多人；事数大于人数

3、，一事一人且一人多事；实际分配任务数不超过总人数也不超过总任务数的c指派间题。这些问题一般需要转换成平衡指派问题进行求解。运筹学教材中的指派问题一般是在c anter集上求解，效益矩阵用实数来表示；模糊数学中运用fuzzy集解决指派问题，效益矩阵中用模糊数刻画每个工作人员完成每项任务的熟练程度或满意程度。吴祈宗等人提出了 vague指派的思想，借助于记分函数方法实现了 vague值向实数值的转化。但是，记分函数在处理指派问题时并不能完全表达指派目标函数中的最小值的思想，因此有必要进一步探讨vague指派的方法。1 vague指派问题的描述vague指派是指效益矩陈中的每一个数均为vague值，

4、表征了每个人完成每项工作花费时间(或取得收益)的不确定性。不确定程度的大小反映在vague值之间的差异。vague集来源于fuzzy集，在fuzzy集基础上，通过真隶属度和假隶属度引入，给出以区间形式表示的隶属程度一一该区间能够同时给出支持证据和反对证据的程度，并且能够表示中立的程度，从而提出vague集的 概念。vague集较模糊集在描述客观事物时更贴近现实，更加形象。一个实数值vague集a是由真泶属函数ta和假隶属函数fa描述的：对于xeu，ta (x)是从支持的xa证据所导出的xea的肯定隶属度的下界，f (x)是从反对xea的证据所导出的xea的否定隶属度的下界,并且tax) +fa

5、 (x) lo x关a的隶属度可由0，1上的子区间ta (x)，1-fa (x)表示，或者称ta (x)，1 一 fa (x)是在 vague 集 a 中的 vague值。为关于a的未知度，也称为犹豫度或踌躇度。na是相对于的未知信息的度量，na的值越大，说明x相对于a的未知信息越多。当ta=l-af时，a=0,即ta+fa=l时，vague值x退化为普通模糊值。在vague指派当中，肯定隶属度是乐观工作效率的表征，否定隶属度是悲观工作时间的表征，而未知度反映了工作效率的确定性程度。进而vague指派的数学模型可以表示为：2 vague指派的转化通常来讲，vague指派问题的求解可以有三种思路

6、：第一，指派问题的木质是求解最小化的线性规划问题，同时也是特殊的整数规划、0-1规划，还是需求量和供应量均为1的特殊运输问题，所以，可以采用vague线性规划以及vague运输问题的求解方法。第二，vague值的核心是一种概率的思想，其表现形式类似于区间数，因而可以将其看成是一种特殊的区间数，采用区间数指派问题的求解方法。第三，vague指派问题求解的一般思路是将vague值转化为一般的实数值进行求解。鉴于第一和第二种情况己有论述此，论文采用第三种思路探讨vague指派问题。2.1基于“马太效应”的vague值转化vague集中记分函数表示了支持证据和反对证据之间的力量对比，主要用于相似度的计

7、算。现实中，根据问题的不同性质，人们往往采取不同风险偏好的记分函数。即使是面对同一种事物，在不同的条件下，人们也会有不同的心态。例如，当支持证据占优时，更多采取激进乐观的策略；而当反对证据占优时，则尽可能地采取保守悲观的策略。可见当支持证据占优时，记分函数满足：s (x)s (ex),容易采取风险追求型(risk proneness)记分函数：这种情况往往高估其真实值。当反对证据占优时，记分函数满足：s (x) <s (ex),容易采取风险厌恶型(risk aversion)记分函数：这种情况往往低估其真实值。当反对证据和支持证据无法平衡时，记分函数满足s (x) =s (ex),容易采

8、取风险巾立型(riskneutralness)记分函数，风险中立的记分函数就是chen” 1提出的普通记分函数s (x) =tij=fijo在指派问题的决策中，类似于其他社会现象，存在一种“马太效应”。所谓的“马太效应”(mattheweffeet)正是人们某种心理的反映-1968年，美国科学史研宄者罗伯特?莫顿(robert k. merton)首次用“马太效应”来描述这种社会心理现象，“对已有相当声誉的科学家做出的贡献给予的荣誉越来越多，而对于那些还没有出名的科学家则不肯承认他们的成绩”。vague集中的记分函数sme (x)则反映了这种价值取向。显然，“马太效应”屮，fijfij时是风险

9、追求型的，在tijsfij时是风险厌恶的。2.2基于特征向量的vague值转化从一般问题出发，考虑效益矩阵中vague值的大小比较。显然，对vague值比较，下列假设是合理的： 从肯定隶属度角度分析，tj越大，vague值越大； 从否定隶属度角度分析，l-fij越大(fij越小)，vague值越大； 从未知度(也称犹豫度)角度分析，n i越小(1-n i越大)，vague值越大，对vague集a=cll，c12,，cln，cnn，构造如下矩阵其中y 1是含有，m=nxn个分量的一维列向量，i =1，2，3。设对应vague集a=cll, cl2,，cln，cnnvague值胡排序向量为()h(

10、)1, ()2，()mt, ()0,在二面给出的3个合理假设条件下，排序向量应该是所有的，具有m个分量的一维列向量屮与矩阵y的两个列向量的夹角之和最小的向量。因此如下定义vague值的排序向量：定理1定义2 $z=yyt,称矩阵z为vague值排序矩阵。定理2排序矩阵是正矩阵，即z0。证明显然有定理3 vague值排序矩阵z的最大特征值对应的特征向量即为排序向量。证明令oerm，0= 01, 02,，omt, 00且00t=l。令为求出厂的最大值，建立辅助函数：可知，如果f取最大值，则入是z的特征值，且0是z的一个特征向量。下面证明入是z的最大特征值。由定理2可知z0。由perron定理知z有

11、最大特征值入和x对应的唯一特征向量o满足0打0*=1。令x是z的另一个特征值，且入乒入。令对应于a 的特征向量为0，且0 to =1。有2. 3基于pareto的vague转化v ague指派问题的线性规划模型（2）进一步表示为：可以证明，问题（7）的每一个pareto解都是原问题（2）的一个有效解。引人参数入，将问题（7）转化为参数规划问题：可以证明，对应于a的最优解都是问题（7）的paret最优解。进而可以用目标区间的a水平最优解作为原问题的满意解，其中a可根据决策者的风险态度及当时的决策环境而定，当a =1时，属于乐观型决策，风险较大；当a=0时，属于悲观型决策，其追求的冃标较低，往往会

12、失去很多良机。3案例计算以论文屮rpl为例，从新的研究a容出发，采用后两种方法进行计算。3. 1基于特征向量借助mat lab计算可得：采用mat lab屮的eig函数，得最大特征值为:入=6. 1510。对应的特征向量为：0t= （0. 2088 0. 3309 0. 3192 0. 2844 0. 16550. 1248 0. 2758 0. 3106 0. 2903） t借助匈牙利方法可以得到指派结果:3. 2基于pareto求解4结论vague集在解决不确定性问题时具有自身的优点，可以更加形象的描述问题的木质，使得问题处理更加贴近实际，但是这一优点给问题的求解 带来了诸多不便之处，因而论文着重探讨vague值的转化问题。在vague指派问题中，论文中提出了三种方法。“马太效用”记分函数方法比较简单，并且具有一定的灵活性，一方妞可以根据问题的不同性质采用风险追逐的记分函数和风险厌恶型函数进行数据处理；另一力面即使在同一