第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

线性约束规划拓广的既约梯度法及其收敛性

本文首先给出由线性等式和不等式以及部分变量非负组成的约束集的一个新的转轴运算。它是以往转轴运算的推广。然后,以此为基础,建立该约束条件下的非线性规划的一个拓广的既约梯度法,它是既约梯度法的广泛推广和改进。算法不需增加任何松驰变量,以致提高问题的维数,扩大问题的规模;方法直接对原问题进行求解。本文算法对一般线性约束规划具有广泛的实用性,其处理技巧带有普遍意义。在非退化假设下,本文算法具有全局收敛性。     

一个求线性代数方程组非负解的算法及其在线性规划中的应用

1.引言关于线性规划的多项式算法,哈奇扬于1979年首先把一个线性规划问题化成一个线性不等式组的求解问题,然后用椭球方法求解线性不等式组,并证明是多项式时间可解的。Karmarkar于1984年也给出了一个求解线性规划的多项式时间解法,他     

一种改进的双层规划内点算法(英文)

本文针对线性双层规划问题提出一个由KMY算法演变而来的原对偶内点算法.与现在很多线性双层规划单纯型算法不同,作者提出的算法从一可行初始点穿过约束多面体内部直接得到近似最优解,当约束条件和变量数目增加时,本算法的迭代次数和计算时间变化很小.所以大大提高实际可操作性能和运算效率.     

基于部分基变量的LP问题矩阵算法

基于部分基变量提出了LP问题的矩阵算法. 该算法以最优基矩阵的一个充分必要条件为基础,首先将一个初始矩阵转化为右端项和检验数均满足要求的矩阵,再转为检验数满足要求的基矩阵,最后转化为最优基矩阵.该算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现的优势.矩阵算法的核心运算是求逆矩阵的运算,提出了矩阵算法的求逆问题,讨论并给出了求逆快速算法,该算法充分利用了矩阵算法迭代过程中提供的原来的逆矩阵的信息经过简单的变换得到新的逆矩阵,该算法比直接求逆法计算效率更高.     

常系数线性分数阶微分方程组的解

本文研究了常系数线性分数阶微分方程组的求解问题.利用逆Laplace变换,Jordan标准矩阵和最小多项式,得到矩阵变量Mittag-Leffler函数的三种不同的计算方法,包含了常系数线性一阶微分方程组的解.     

对矩阵初等行变换的算法改进

对矩阵初等行变换的算法改进夏日，张裕生（蚌埠职工大学）（蚌埠高等专科学校）在线性数与线性规划课程的内容中，初等行变换这个运算工具占有举足轻重的地位，不管是线性代数中求逆矩阵、求矩阵的秩、解线性方程组，还是线性规划中换基迭代等运算都离不开初等行变换。初...     

混合边界条件下的三维定常 旋转Navier-Stokes方程的原始变量有限元计算

本文利用原始变量有限元法求解混合边界条件下的三维定常旋转Navier-Stokes方程,证明了离散问题解的存在唯一性,得到了有限元解的最优误差估计.给出了求解原始变量有限元逼近解的简单迭代算法,并证明了算法的收敛性.针对三维情况下计算资源的限制,采用压缩的行存储格式存储刚度矩阵的非零元素,并利用不完全的LU分解作预处理的GMRES方法求解线性方程组.最后分析了简单迭代和牛顿迭代的优劣对比,数值算例表明在同样精度下简单迭代更节约计算时间.     

求线性规划问题初始可行基的一种方法

Smale 证明了采用单纯形法求解线性规划问题,在概率平均意义下转轴次数为变量数目的线性函数.下面介绍不引进人工变量,直接由所给问题的标准形式     

方向选择约束单纯形算法

一、引言人们一直致力于求解线性规划的单纯形算法的改进工作.1976年,Powell 发表过降低基维数的改进单纯形算法,这个算法是将基矩阵的一个块用基矩阵的其它块的乘积来表示,虽然实现了降低基维数,节省了存贮空间,却增加了计算次数,减慢了计算速度.Sethi and Thompson 针对线性规划问题也提出过竞争和非竞争约束(candidate andnoncandidate constraints)的概念.他们发现,随机生成的实验问题,其总约束中大约只有15%—25%是竞争约束,并提出了一个仅对竞争约束进行旋转运算的单纯形算法.他们的算法,对某些特殊的线性规划提高了求解速度,但并不减少基的维数,并不节省内存空间,增加了程序复杂性.1984年,Sethi and Thompson 又提出 PAPA 算法,再次利用线性规划问题通常只有少量竞争约束这个事实来提高求解速度.但 PAPA 算法往往要在原问题的可行域外运行.况且,上面提到的各种算法,均不能从理论上表明,它们较标准改进单纯形算法到底节省了多少存贮单元和节省了多少计算次数.     

具有带状系数矩阵的无限维线性规划的解法

研究一类每个约束条件有两个变量且每个变量出现在两个约束条件中的无限维线性规划.引入松弛变量后,得到约束方程组的系数矩阵为无限阶带状矩阵,用它的左逆以及属于零的特征向量可以表示这类问题的最优解.获得目标函数值收敛的一个充分条件.     

凸函数的若干新性质及应用

本文证明了凸函数的若干新性质 ,讨论了这些性质在求解线性与非线性不等式组和线性规划中的应用 ,为线性与非线性不等式组、线性规划的求解提供了一种新方法 .     

基于旋转算法的随机模糊均值-方差投资组合优化

Markowitz首先采用方差度量风险，并应用于投资组合优化中，大多数的均值方差模型仅对随机投资组合优化或模糊投资组合优化进行研究，然而，实际投资组合优化问题既包含随机信息也包含模糊信息。本文首先定义随机模糊变量的方差，并用其度量风险，提出了具有交易成本、借贷约束和阀值约束的均值-方差随机模糊投资组合优化模型。基于随机模糊理论，将上述模型转化为具有线性等式和线性不等式约束的凸二次规划问题，并得到其KKT条件。本文还提出改进的旋转算法求解上述模型，该算法消掉KKT条件中部分变量，减少计算量。最后，采用中国证券市场的实际数据进行样本内分析和样本外分析，验证了上述模型和算法的有效性。     

行(列)反对称矩阵的满秩分解和广义逆

本文研究了行(列)转置矩阵与行(列)反对称矩阵的性质.利用分块矩阵理论获得了许多新的结果,给出了行(列)反对称矩阵的满秩分解、秩分解和广义逆的公式及快速算法.它们可极大地减少行(列)反对称矩阵的满秩分解、秩分解和广义逆的计算量与存储量,并且不会丧失数值精度.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

LMI优化的一种原对偶中心路径算法

系统和控制理论中许多重要的问题,都可转化为具有线性目标函数、线性矩阵不等式约束的LMI优化问题,从而使其在数值上易于求解.本文给出一种求解LMI优化问题的原对偶中心路径算法,该算法利用牛顿方法求解中心路径方程得到牛顿系统,并将该牛顿系统对称化以避免得到非对称化的搜索方向.文章详细分析了算法的计算复杂性.     

非线性约束条件下的SQP可行方法

本文对非线性规划问题给出了一个具有一步超线性收敛速度的可行方法。由于此算法每步迭代均在可行域内进行，并且每步迭代只需计算一个二次子规划和一个逆矩阵，因而算法具有较好的实用价值。本文还在较弱的条件下证明了算法的全局收敛和一步超线性收敛性。     

全局求解线性多乘积规划的分支定界算法

本文针对一类线性多乘积规划问题提出一种分支定界算法.首先将原问题转化为其等价形式,然后利用提出的线性松弛技术将等价问题松弛为线性规划问题,通过求解一系列线性规划问题得到原问题的全局最优解.最后给出算法的收敛性和计算复杂性.数值实验表明算法是有效的.     

线性方程组的矩阵求解算法

设计的算法是 ,在约当消元法的基础上 ,只需对行最简形矩阵进行删除行和列、增加行、交换行等运算即可得到方程组的通解 .本算法的独特之处是 ,消元过程结束后 ,不需指定自由变量和非自由变量 ,不需写出由自由变量表示非自由变量的具体表达式 ,利用行最简形矩阵求通解时 ,再不需进行乘法和加法运算 ,因而不会增加算法的精度损失量 ,并且由于算法中的运算对象只有矩阵 ,因而算法简单 ,易于实现     

线性规划的约束条件“滚雪球”算法

为使线性规划的每个约束条件部分或全部地拥有原整个约束条件所包含的信息,将线性规划的约束条件“滚雪球”后得到与原约束条件等价的新约束条件,对新约束条件所构成的线性规划采用目标函数最速递减算法.有一定规模的随机数值算例显示了该算法只需进行m(约束条件数)次迭代即可求得最优解.