求解整数规划Surrogate对偶问题的一种算法

本文讨论整数线性规划的Ｓｕｒｒｏｇａｔｅ对偶问题，给出了求解Ｓｕｒｒｏｇａｔｅ对偶问 题的一种算法，论述了该算法具有的某些良好性质。计算结果说明：用该算法求解 Ｓｕｒｒｏｇａｔｅ对偶问题时，所解的背包问题的次数比较少，所存在的对偶间隙也较 小。     

变量有上界的线性规划的对偶单纯形方法

给出变量有上界的线性规划问题的对偶单纯形算法, 该算法包含了一般线性规划问题的对偶单纯形算法, 为解变量有上界的线性规划问题提供了又一种方法.     

基于不可行内点算法的几何规划优化方法

提出了一种优化算法,用以解决古典正项式原－对偶几何规划问题．在一般假设下,该方法应用原－对偶不可行算法,在一类特殊的受摄动ＫＫＴ 系统中定义了一条原－对偶不可行路径,对于每个规划,都产生一个次可行解,规划问题的原－对偶目标函数值最后分别收敛到原－对偶规划值．算法迭代次数少,还不受几何规划问题艰度大小的限制．文中利用对数转换后目标函数Ｈｅｓｓｉａｎ 矩阵的特殊结构,讨论了算法实现问题．算法效果得到实例计算验证     

凸规划的一种对偶内点算法

将带有不等式约束的凸规划问题转化为拉格朗日对偶问题,构造了一种求解凸规划的偶内点算法,证明了在不存在对偶差的情况下,当对偶变量序列收敛到对偶问题最优解时,原始变量序列收敛于原始问题的最优解。     

凸二次规划的原-对偶内点算法数值实验初步

在线性规划原始对偶内点算法的基础上,进一步给出原始对偶内点算法在解凸二次规划问题中的应用, 并初步给出了该算法的数值例子, 作为对内点算法的一个重要补充.     

基于拉格朗日对偶的一类全局优化算法

针对带有非凸二次函数约束的非凸二次规划问题(NQP),提出了一个基于拉格朗日对偶的确定型全局优化算法,这类优化算法可广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中.为求解此问题,首先,应用拉格朗日对偶对原问题进行下界估计.其次,为克服拉格朗日对偶问题的非凸性,利用线性化方法,得到拉格朗日对偶问题的线性下界估计,并且由此建立了NQP拉格朗日对偶问题的松弛线性规划(RLP).如此通过对RLP可行域的细分和一系列RLP的求解过程,从理论上证明了算法收敛到NQP的全局最优解.数值算例应用结果表明,该方法是可行的.     

求解LP问题的部分基变量算法

一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法--部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.     

一类绝对值规划的算法

针对一类绝对值规划问题,提出对偶规划,给出其弱对偶性及对偶问题的最优性充分条件,并证明对偶间隙也是该类绝对值规划问题的解。同时,引入变量代换,基于线性规划的单纯形法,提出该类绝对值规划问题的全局优化求解算法。算例表明该算法是有效的。     

多用户最优化的两种对偶方法

采用多用户问题的梯度近似分布式算法,对多用户最优化的原始对偶方法和正规化对偶方法进行了比较,集中于多用户凸最优化问题的概括,其中目标函数和约束函数不可分,而目标函数可通过非线性组约束,使用户决定耦合;在算法中,对原始对偶方法和正规化对偶方法可考虑不变步长,采用跨用户自然迭代计算,使每个用户能够只更新自身的决策变量．     

带参数扰动的原始对偶内点算法求解一类非线性规划问题

给出一种通过新的原始对偶内点法求解一类非线性规划问题的算法及带参数扰动的原始对偶内点法的收敛性,并通过数值实例说明了该算法的有效性.该算法改进了原始对偶内点法,可由参数控制可行域的形状,扩大了初始点的选择范围,并通过修正牛顿法找到值函数的下降方向.     

程序设计中的循环机制

在计算机程序设计中,较为复杂的算法程序都要使用循环结构。本文分析了循环结构中循环体的共有特性,探讨了循环结构的分析与设计。     

线性互补问题的灵敏度分析

本文在Lemke互补转轴算法的基础上进一步研究线性互补问题的灵敏度分析。主要结果有二:1.线性互补问题的灵敏度分析;2.灵敏度分析在凸二次规划方面的应用。     

非线性规划的一个改进型可行方向法

本文对Frank-Wolef方法进行了改进,从而得到了一个新的算法。并且讨论了算法的收敛性及在凸规划情形具有的良好收敛性质。     

谈综合程序设计方法教学

根据计算机学科《‘93教学计划》的精神,本文在总结多年程序设计教学经验的基础上,就如何提高学生的理解能力、抽象能力和程序设计能力的问题上做了深入的讨论,探讨了将编程语言、算法、数据结构和程序设计教学的内容有机地结合成一个教学整体的可能性,提出了综合程序设计教学的新概念。     

机型指派与飞机路线一体化建模及算法研究

通常航班计划都是分阶段完成的,即航班时刻表→机型指派→飞机排班→机组排班,每一个问题都相对独立的建模并求解;这样通常无法得到全局最优解甚或无解,对后续问题求解造成很大困难。为了克服这种困难及改善航班计划的次优性,本文将机型指派、飞机路线问题综合考虑,建立多机型的一体化飞机排班多商品网络流模型。为实现模型的有效求解,本文提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线（航班串）并计算各航班串简约成本,动态选择列集并与限制主问题进行迭代。最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性,并与航空公司实际排班和分阶段优化情况进行比较研究。     

求解有限马氏决策问题的神经网络方法

在有限马尔可夫决策过程的线性规划求解方法以及神经网络算法的基础上提出了运用神经网络求解有限马尔可夫决策问题的方法．并通过算例验证了该方法的有效性．     

树的q-最优划分及其应用

本文从集合划分的概念出发,提出了关于树的q-最优划分的问题。同时,还提出了求树的q-最优划分的精确算法和启发式算法。最后,以配电网系统的实际设计为例来说明算法的应用。     

改进基因表达式编程算法及其应用研究

基因表达式编程是一种新型的自适应演化算法,它是在继承和发展遗传算法和遗传编程优点的基础上发展起来的知识发现新技术．笔者介绍了GEP的发展现状与关键技术,设计了逆淘汰策略和无树解码方式的改进方案,旨在维持种群多样性和提高算法效率,最后将改进方法应用与一元和多元函数挖掘的实验,得到准确度和拟合度良好的函数模型,收到了满意的效果．     

图像压缩与重构小波算法的另一种实现:实例编码及结果对比

采用Daubechies小波,用MATLAB语言对二维图像压缩与重构Mallat算法的另一种实现进行编程处理。实验结果表明,与流行算法比较,新算法的计算复杂度有所降低,而且达到了流行算法同样的效果。     

基于Semidefine Programming算法的无线传感器网络节点定位研究

首先在无线传感器网络模型假设下给出了模型、相关概念和定位过程的介绍,然后利用Semidefine Programming定位算法对无线传感器网络节点定位方法进行了研究。经过仿真实验证明,Semidefine Programming算法可以有效降低网络的成本,而且对定位精度的改进效果也非常明显。