缺省指派问题及其求解算法

在研究周良泽于1998年首先提出的最短时限最少耗费缺省指派问题基础上,从对称的角度给出了缺省指派问题的两种不同提法:拟从m个人中派出β个人去干n件事中的β件事(β≤min{m,n},每件事由一个人完成)。已知第i人做第j事的时间为tij,第i人做第j事的耗费为pij,i=1,2,…,m;j=1,2,…,n。问派出哪β个人去完成哪β件事,才能使得:(1)在最短时限内完成n件事中的β件事,并且在满足最短时限前提条件下总耗费最少?(2)以最少总耗费完成n件事中的β件事,并且在满足总耗费最少前提条件下完成时限最短?给出了求解该问题的数值算法,证明了算法的理论依据,并举例说明算法的应用。

2种限制性指派问题

提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.

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

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