论文部分内容阅读
资源种数为M的资源分配问题就是M维资源分配问题,它是指将M种资源分配给N个部门,使之产生最大的生产效益。对资源分配问题的研究相对成熟的是一维和二维资源分配问题。用于求解一维资源分配问题的经典方法是动态规划算法。对多维的资源分配问题的求解常采用模拟退火、遗传算法和禁忌搜索等智能算法。但存在两个主要问题:一是对大规模问题的求解速度较慢;二是即使能对较大规模的问题进行快速求解,却很可能陷入局部最优解的困境。因此,本文立足于特殊的资源分配问题,提出了一种新的资源均匀占有问题。同时它也是生产与生活中常见的问题,如何更好地对资源进行合理的分配,关乎每位参与者的收益,因此对资源均匀占有问题的算法研究具有重要的理论意义与实际价值。 文中建立了资源均匀占有问题的数学规划模型,随后结合递归理论和归约转换的基本技术,将一个资源均匀占有问题转化为了若干个受限的资源分配问题。但这条求解路径存在两个问题:转换后的资源分配问题个数较多,且资源分配问题的维数从1维到M维不等。 本文结合贪心算法和算法博弈论对资源均匀占有问题进行求解。首先构造了资源均匀占有博弈,设计出一种用于求解此问题的LORUP算法,由此获得一个资源占有方案。运用数学归纳法证明了一个占有方案是纳什均衡的充要条件是该方案可以由LORUP算法生成。证明了非均衡分配可有限次优化改进为均衡分配后,得到了均衡分配就是最优分配。最后对资源均匀占有问题进行拓展,给出了若干实例。理论与实际结果表明,本文提出的LORUP算法可对资源均匀占有问题进行有效求解。