多因素指派模型全局优化问题研究

基于多因素资源优化分配问题的不确定性,建立基于区间数型下的不确定多因素指派模型,给出模型建立的理论依据与全局优化算法,拓展区间数型多因素指派模型,解决了不确定条件下多因素资源优化分配问题.考虑多因素影响,基于任务完成效率,以5类任务多因素分配问题为例,获得了指派模型全局优化的解.为不确定条件下资源优化分配问题的研究拓宽了决策途径.     

人数与任务数不相等的指派问题

本提出人数与任务数不相等的指派问题应当视为一个多目标决策问题，首先要求指派给各人的任务数目两两之间相差不能超过1，其次要求所需总时间最少；并且给出了该问题的求解方法。     

作战时耗指派矩阵取胜指派矩阵兵力耗损指派矩阵的一体构造

指派矩阵构造是指派问题应用研究的难点,在作战应用领域展开指派矩阵构造专题研究.文中回望了1914年Lanchester关于"兰氏"平方律作战过程取胜条件与剩余兵力的分析结果,以及1996年本文第一作者提出的关于"兰氏"平方律作战过程存在胜负的情况下其作战持续时间计算的数学模型,提出了关于"兰氏"平方律作战过程在作战双方势均力敌的情况下作战持续时间的数学模型.综合运用上述的已有理论与新建理论,建立了取胜矩阵、时耗矩阵、兵力耗损矩阵的一体构造模型.该一体构造模型从作战系统的4类可知数据出发,对于具体的多部队参战的作战过程均能构造出具体的取胜、时耗、兵力耗损数值矩阵.最后给出了取胜、时耗、兵力耗损矩阵的一个一体构造实例,并运用(n×m)-k缺省指派问题理论对该实例求得了其最多K胜条件下的最短时限最少耗费缺省指派最优解.     

有资格限制的指派问题的求解方法

在实际的指派工作中，常会遇到某个人有没有资格去承担某项工作的问题，因此，本建立了有资格限制的指派问题的数学模型。在此数学模型中，将效益矩阵转化为判定矩阵，由此给出了判定此种指派问题是否有解的方法；在有解的情况下，进一步将效益矩阵转化为求解矩阵，从而将有资格限制的指派问题化为传统的指派问题来求解。最后给出了一个数值例子来说明这样的处理方法是有效的。     

基于可信性理论的模糊广义指派问题研究

鉴于广义指派问题的参数确定上通常包含不确定性,因此,将模型的主要参数,即单位费用、资源消耗量,用梯形模糊变量来刻画,从而建立模糊广义指派模型.在模型求解过程中,结合到决策者的实际要求,利用可信性理论将目标函数和约束条件进行清晰化处理,进而通过参数分解法求解.最后,通过数值例子说明模糊广义指派问题的应用,并检验所提方法的有效性.     

任务数多于人数的指派问题

本文给出任务数多于人数指派问题的两种解决方法。     

一类二阶段指派问题

经典的指派问题是研究资源与任务的二元匹配。作为推广,三维指派问题是研究资源、任务与作业的三元匹配。前者已有成熟的有效算法,后者是著名的NP困难问题。本文讨论介于二者之间的一类二阶段指派问题,即可分解为二阶段决策的特殊三维匹配问题,给出多项式时间算法。     

非平衡指派模型及其在航空机务维修中的应用

非平衡指派问题是最优平衡指派问题的推广与深化,在航空机务维修工作中,维修任务的合理配置对及时完成维修任务,保障训练作战计划非常重要.本文从装备完好率和人力资源的优化配置角度出发,按照不考虑维修任务等待时间和考虑维修任务等待时间两种情况分别建立了非平衡指派优化模型,并给出了这两种情况下效益矩阵的构造方法,进而将优化模型转化为最优平衡指派模型进行求解,从而为航空机务维修工作中维修人员的优化配置提供了一种科学、合理的决策方法.     

一个实际指派问题的研究

在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现优化管理的。本文通过运用匈牙利法对一个航班时刻表中的机组人员在异地的停留时间进行分析与研究，发现现有的人员指派方案不是理论上的最优解，进而在假设条件成立的前提下，提出了更加科学的人员指派方案。     

一类非确定型多目标指派问题及其算法研究

研究每个人承担的工作数不受限制,但每项工作只能由一人承担的情况下,如何给每个人指派工作,才能使完成所有工作的工期最短,并且在此前提下,使完成所有工作的总用时最少.针对这种多目标非确定型指派问题,本文给出了一种向量标记算法,这种算法不但使用方便,而且有很好的运算效率。     

求解指派问题的一个算法

为了便于建立与指派问题有关的决策支持系统，本给出了一个求解指派问题的数值算法，证明了算法的理论依据。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

Test Problem Generator for the Multidimensional Assignment Problem

The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignment problem. Test problems of known solution are useful in exercising solution methods. A method of generating an axial MAP of controllable size with a known unique solution is presented. Certain characteristics of the generated MAPs that determine realism and difficulty are investigated.     

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

双目标瓶颈指派问题的遗传算法

给出一种双目标瓶颈指派问题的新模型,本模型结合了决策者和工人两方面的因素,特别之处在于考虑到了工人对工作的排名偏好.进而,将双目标瓶颈指派问题转化为单目标规划,并设计了解此问题的遗传算法,算法的解均为双目标瓶颈指派问题的Pareto最优解.     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.