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

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

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

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

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

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

0-1整数规划问题的巨磁电阻型DNA计算模型

给出了基于GMR(巨磁电阻)型DNA芯片技术的0-1整数规划问题的DNA计算模型。将问题的变量编码成DNA链,在GMR型芯片表面固定DNA探针,然后将被生物素标记的待分析目标DNA链与探针进行充分杂交,通过芯片上的GMR传感器对芯片上纳米磁珠的检测,以电信号方式输出,得到问题的解,避免了荧光分析中的信号转换而引起的失真。该模型具有较高灵敏度,信号检测和分析较为简单,对信号检测设备要求较低。

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

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

对带有盒约束的二次整数规划的一种线性化方法

本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合0-1整数规划问题,然后利用Ilog-cplex或Excel软件中的规划求解工具进行求解,从而解决原二次整数规划.

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

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

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究,是运筹学和管理科学中应用最广泛的优化模型之一.首先简要回顾整数规划的历史和发展进程,概述线性和非线性整数规划的一些经典方法.然后着重讨论整数规划若干新进展,包括0-1二次规划的半定规划(SDP)松弛和随机化方法,带半连续变量和稀疏约束的优化问题的整数规划模型和方法,以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划(SDP)逼近.最后,对整数规划未来研究方向进行展望并对一些公开问题进行讨论.

汽车涂装中虚拟重排序问题建模与求解

针对汽车涂装中的虚拟重排序问题,建立了关于颜色转换次数最少的0-1二次整数规划模型.根据0-1变量的特点,把该0-1二次整数规划转化为以相邻颜色个数最大为目标的0-1线性整数规划,从而使得所建立的虚拟重排序模型可直接用现有优化软件求解,无须设计专门解法.所建模型在任何虚拟重排序场合均可采用或借鉴.

基于协同效应的知识创新团队伙伴选择方法

在知识创新团队的伙伴选择问题中着重考虑了伙伴间的协同效应信息。首先,分析了伙伴之间的协同关系与协同效应,描述了考虑多个协同效应评价指标的知识创新团队伙伴选择问题;然后,建立了团队伙伴选择的数学模型,该模型是一个0-1二次整数规划问题,为了求解该问题,开发了一种GRASP启发式算法;最后,通过一个实例分析说明了所提出方法的可行性和实际应用价值。

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

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