按比例分配问题

按比例分配问题是把一个数量按照一定的比进行分配。它是平均分问题的发展,平均分是按比例分配的一种特例。按比例分配问题的解法主要有两种：     

双向选择问题中的最优分配

本文讨论的是双向选择中的分配问题．首先把这类问题进行量化，随即建立起一种“延缓接受算法”，然后证明了用这种算法处理双向选择问题是稳定分配和最优分配．     

一种新型的解分配问题的算法

在运筹学理论中,分配问题是最基本的问题之一,而现有解分配问题的算法都比较复杂,应用这些算法是不方便的。故提出一种用最短路径算法来解决分配问题的新型算法。 1.几个基本概念及其定理分配问题数学模型(P) 求使定义1如果某一个分配x=(x_(ij)),x_(ij)满足式子(1.1),则称此分配为可行分配。定义2如果一有向图中某一回路上边的长度之和小于0,则称此回路为负回路。下面用A={(1,j_1),(2,j_2),…,(n,j_n)}来表示分配问题的一个可行分配,即当x_(ij)=1     

成组加工中带可分配工期的最大延误问题

研究成组加工中带可分配工期的最大延误问题的排序与工期分配,对于成组加工中带可分配工期的最大延误问题的不同模型,或给出其最优序．或证明其是NP-难问题．     

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

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

几种基于匈牙利算法求解二次分配问题的方法及其分析比较

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。二次分配问题的线性化模型和下界计算方法,是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础,根据现有QAP对偶上升下界计算方法中的具体操作,提出几种可行的QAP对偶上升计算新方法。最后,通过求解QA-PLIB中的部分实例,深入分析其运行结果,详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度,这为基于匈牙利算法求解二次分配问题的方法的改进奠定了基础。     

成组加工中带可分配工期的误工任务数问题

本文研究了成组加工时带可分配工期的误工任务数问题的排序与工期分配.对于成组加工中带可分配工期的误工任务数问题的不同模型,或给出其最优序,或证明了其是NP-难问题.     

警力分配问题中的模糊优选动态规划法

根据市区公安分局基层警力的分配问题的特点,将模糊优选理论与动态规划法相结合建立了多维多目标模糊优选动态规划模型,用此模型对警力进行合理分配,以得到最优警力分配方案,为公安决策者在警力分配问题中提供科学的理论依据.     

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

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

一类特殊二次分配问题的线性化求解新方法

许多抽象于实际的二次分配问题，其流矩阵与距离矩阵中有很多零元素，求解该类二次分配问题时，可通过先行利用零元素的信息减小问题规模，缩短计算时间．以二次分配问题的线性化模型为基础，提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法，不仅从理论上证明了方法的可行性，而且从实验的角度说明了该方法比以往方法更加优越．