二次型0-1分配问题的遗传算法求解

文章针对数学中一类计算非常困难的二次型０－１分配问题，提出遗传算法的求解思想，并根据问题的具体特点对算法进行改进，将复杂的约束条件包含在适应值函数中，构造非线性变化的动态适应值来求解该类问题。最后成功地运用于一个分散决策问题实例，与常规遗传算法相比该搜索算法具有明显的优越性。

二次型0-1分配问题的蚂蚁算法求解

通过介绍蚂蚁觅食过程中基于信息素的最短路径的搜索策略,给出蚂蚁算法在二次型0-1分配问题中的应用。针对蚂蚁算法存在的过早收敛问题,使用距离以及流量作为启发式信息,并且引入局部优化对蚂蚁算法的结果加以改进。计算机仿真结果表明,蚂蚁算法对求解二次型0-1分配问题有较好的效果。

与0-1二次规划问题等价的连续问题(英)

在较一般的条件下，证明了线性约束0-1二次规划问题等价于一个凹二次规划问题，改进了已有的结果．

二次0-1型整数规划的线性化求解

对目标函数为二次、约束条件为线性的二次规划问题,如果采用一定变换将其变为普通的线性规划,这既能保证结果的正确性,又可以大大地简化计算。讨论了二次0-1型整数规划的线性化求解:将二次0-1型整数规划问题等价转化为一次函数的线性0-1型整数规划问题,这样可以有效地简化求解。并给出了二次0-1型整数规划问题等价转化为线性0-1型整数规划问题的理论证明。实例分析进一步说明了该方法的适用性和可行性。

解二次背包问题的一个线性化方法

讨论了二次背包问题(QKP)的一种线性化方法.利用文献中的相关结论,通过增加变量和线性约束,将(QKP)的二次0-1规划模型等价转化为一个线性混合整数规划模型,再利用计算线性混合整数规划的软件(如Ilog-cplex或Lingo)求解,从而解决原问题.对所构造问题实例的计算,验证了求解(QKP)方法的有效性.

最大团问题的一个线性混合整数规划模型

最大团问题(MCP)是图论中的一个传统问题,在很多领域都有广泛的应用.主要利用已有研究的相关结论,将(MCP)的二次0-1规划模型等价转化为一个线性混合整数规划模型,再利用计算线性混合整数规划的软件求解.通过对所构造实例的计算,验证了求解(MCP)方法的有效性.

传感器网络能源有效任务分配算法

为了延长网络生命期,传感器网络在设计过程中,通常利用节点本身的处理能力,进行网内处理,以减少通信量,节省能量.在传感器网络内引入处理或计算后,应用可以描述为一个任务集及任务之间的数据依赖关系.不同的任务分配方案导致应用执行所需的通信量和计算量不同,从而影响应用执行的能量消耗.在使用任务图对传感器网络应用描述的基础上,提出了传感器网络任务分配模型.由于应用的任务可划分为感知任务集和处理任务集,因而传感器网络中的任务分配可分成感知任务分配和处理任务分配两个阶段.针对处理任务分配,将其建模为二次0-1规划问题,并提出了分布式逐层优化分配算法OALL.仿真实验验证了分布式算法OALL的有效性.

基于分支定价算法的异质品装箱问题研究

在多物品物流系统中,异质品的装载运输往往会造成物品损坏、管理困难等问题.针对这种场景,本文提出了异质品装箱问题的0-1二次规划,并根据Dantzig-Wolfe分解,设计了变邻域搜索算法与分支定价算法来进行求解.实验验证了异质品装箱方案相比两种传统装箱方案的优越性,新方案兼顾了经济性和灵活性.在180个随机对比算例上,两种算法都展现了较好的性能:变邻域搜索算法的Gap值平均为1.8%,运算时间平均为1.06秒;分支定价算法则分别为0.30%和815.40秒,性能超过了Gurobi求解器.最后,本文通过引入“决策者对异质品的容忍度”这一参数,供决策者在装箱成本与异质性惩罚之间寻求一个平衡点.相较已有研究,该方案更加精细、合理,可为企业提供科学的决策依据.