求解最大割问题的分枝定界算法

最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在谈模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解，是求解中小规模最大割问题的有效方法。     

目标函数为加权完成时间和的单机维护调度问题研究

讨论了带有可控性维护的单机调度问题,目标是实现工件加权完成时间和的最小化．此问题是强 NP难的,因此给出了三个启发式算法和一个分枝定界算法,并通过实验对这些算法进行评价．实验结果表明其中的两个启发式算法(WSPT算法和综合算法)能得到比较好的近似最优解,分枝定界算法对小规模(n≤10)的问题很容易得到最优解．     

整数规划算法效率研究

通过对整数规划问题的算法Groebner基和分枝定界法的求解过程分析比较,以同样整数规划问题实例,采用数学软件Maple,用Groebner基方法和分枝定界法分别进行了求解,对求解的的效率进行了比较,并对影响效率的原因进行了讨论.     

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．     

订货与发货整合批量调度问题

在对文题进行数学描述的基础上，建立求解该类问题的混合整数线性规划模型.证明问题NP 困难性并研究多项式可解子问题，进一步提出了3个启发式算法以及精确求解的分支定界算法.数值实验表明，所提出启发式算法以及分支定界算法的有效性与高效性.     

序列相关Setup单机调度的最小化最大拖期分枝定界算法

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.     

混合整数分式多目标规划及其在企业计划管理中的应用

本文将修正的Dakin分枝定界法用于求解带有线性分式目标的混合整数多目标规划问题,提出了“弹性约束”的概念及其处理方法和交互型分枝定界的两步算法,并将其应用于实际问题中。     

一种求3机Flow—shop调度问题的遗传算法

提出一种遗传分枝定界算法求解3机Flow-shop调度问题，该算法似于常用的遗传局部算法和遗传动态规划算法，用随杨方法生成测试例子，通过与著名的Taillard的禁忌搜索算法和Reeves的遗传算法进行比较，实验结果证实了遗传分枝定界算法的有效性。     

基于Q0-1规划模型用分枝定界法求解最大团问题

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型（简称Q0-1规划模型）寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。     

整凸二次规划

本文给出了一种求解整凸二次规划的分枝定界法，该算法把松弛问题转化为线性互补问题，由于求解线性互补问题时，充分地利用了前一分枝点所对应的线性互补问题解的信息，从而地减少了计算量。     

求解组合优化问题的一种方法-分枝定界法

较为详细地分析了分枝定界法的算法特征和过程,讨论了以该算法求解具体优化问题时所要采取的算法策略。笔者结合简单、具体的例子说明了上述过程,并且也说明了在实际应用该算法时,根据问题的局部信息和其它启发算法求解问题的必要性。     

梁弯曲问题的样条小波边界元法

采用四阶（三次）样条小波尺度函数,构造了函数的B样条小波插值格式,并将其应用于梁的弯曲问题边界元法．算例的计算结果与精确解完全一致．文中给出的样条小波插值函数,可应用于其他有限元法、边界元法的的计算．     

极大熵Newton-SOR迭代算法求解绝对值方程

主要研究绝对值方程Ax＋B｜z｜=b的求解问题．首先通过利用极大熵理论将该绝对值方程转化为光滑方程组，建立求解该形式绝对值问题的Newton-SOR方法，并对算法的收敛性进行分析和证明；最后通过数值试验对算法的有效性进行测试．     

B 3G MIMO—OFDM系统同步问题研究

B 3G移动通信系统可提供高达100Mbit／s的速度,MIMO-OFDM作为B 3G的核心技术,同步问题一直是该系统的关键问题．介绍了正交频分复用技术（OFDM）,多输入多输出系统（MIMO）技术的原理,分析MIMO—OFDM系统中存在的同步问题,总结MIMO—OFDM系统的同步方法．     

一种新的长期配电网络规划方法

本文介绍一种配电系统多阶段优化规划的数学模型及其求解方法。模型包括配电站和线路的位置、容量及建设时间的最优选择。模型用混合整数规划描述,投资费和网损费的当前值为目标函数.采用Tong,J.V.Roy提出的交叉分解法(Cross Decomposition),将原问题分解为一个主问题和易于求解的独立的多个子问题.并在他们之间反复迭代直至收敛;还通过线性规划求解Lagrangean松弛因子的办法使问题的求解变得简单。实例计算表明,该方法能用较短时间求得最优解。     

重掺砷硅单晶中痕量硼的二次离子质谱定量分析

重掺砷硅单晶中杂质硼含量的控制是十分关键的，因无法用常规的红外光谱法测试，于是转而使用二次离子质谱法来测试，虽然二次离子发射机理复杂，基体效应明显，但通过相对灵敏度因子法，还是能够比较精确地给出定量测试结果，解决重掺砷硅单晶中硼杂质的定量检测问题，进而为控制硼含量提供了依据和帮助。     

受约束的两类数据分割算法及其应用

针对权值约束、相互制约的两类数据A、B分类问题,提出一种带修补规则的数据分割算法。首先,基于密度法,依赖于数据类B确定数据类A的代表点,并依据最短距离原则和数据类A的代表点,对数据类B进行分类;进而,依据邻域法的思想及数据类B的权值,对各个分类进行修补,使各类满足权值约束;最后,基于优化模型,对数据类B的分类进行优化。实验结果表明,该分割算法获得了满意的分类效果。     

旋转坐标情况下钻井布局的最优化问题

对1999年大学数学建模竞赛中钻井布局问题进行了深入的研究,利用特殊时刻将时间分段的方法,从理论和计算两方面解决了这个难题,提供了连续问题在某些条件如何离散化而结果不产生遗漏的一种思想方法。     

n皇后问题的一种解

在ＦａｌｋｏｗｓｋｉＢＪ和ＳｃｈｍｉｔｚＬ的论文中，大于３的自然数被分成７部分，并对每部分中的ｎ给出了ｎ皇后问题的一个特解。本文改进了他们的方法，将大于３的自然数仅分成５部分，然后对每部分中的ｎ用统一方法给出ｎ皇后问题的一种解，从而有效地简化了已有的结果。     

B样条曲线刀具半径补偿方法

在数控激光切割加工中,由于作为刀具的激光焦点具有一定的半径,因而刀具中心轨迹并非零件实际轮廓,存在一个刀具半径补偿问题。为此提出了激光切割B样条曲线的一种刀具半径补偿方法。该方法利用常规等距曲线的数学模型及B样条曲线的端点性质,通过主动调整控制参数,获得精确的保形的等距曲线。其交点采用数值迭代求解,算法过程简单。