分派问题的灵敏度分析及其应用

讨论分派问题的效率矩阵的元素发生变化时,对最优解的影响;在保持分派问题最优解不变的情况下,效率矩阵的元素的变化范围;及当分派问题的最优解发生变化后,如何用简单的方法求得新的最优解等.     

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

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

奇异值分解法在预测用户页面兴趣度中的应用

如何挖掘用户感兴趣的内容并向其推荐相应的产品是许多商务网站关注的重点。本文提出一个用户页面兴趣度公式,据此得到一个稀疏的页面兴趣度矩阵,考虑到矩阵的稀疏性会影响预测的准确性,我们首先用稀疏矩阵中每列非零元素的平均值对该列中值为零的元素进行修正,然后用奇异值分解法对原稀疏矩阵中值为零的元素进行再次修正,进而根据修正后的矩阵用SlopeOne算法对用户的页面兴趣度进行预测并用某网站的数据验证。结果表明:与稀疏矩阵相比,用修正后的矩阵预测的准确性有较大提高。     

线性规划问题最优解集的结构与仅有唯一基最优解的充分条件

其中,A是秩为m的m×n矩阵,m相似文献   

有限元方法中网格编码的优化问题

1　引　　言有限元理论 [1]指出 :网格编码决定了总刚矩阵中非零元素的数目及位置 .一方面 ,由于总刚矩阵的稀疏性、带状性和对称性 ,总刚矩阵有必要采用一维存贮 .存贮的最大长度即存贮空间等于矩阵中非零和有效零元素的数目 .另一方面 ,总刚矩阵的对称性和正定性 ,决定了矩阵分解 (即 LLT分解 )和回代求解过程所需的计算量与非零元素数目成立方关系 .即计算量 =d· (非零和有效零元素的数目 ) 3,其中 d是常数 .因此 ,从这两方面考虑 ,网格编码对有限元方法起着决定性和重要性的作用 .人们在处理编码问题时 ,出于直觉和简单 ,往往给予一…     

Winograd矩阵乘法算法用于任意阶矩阵时的一种新处理方法

摘要t矩阵乘法StraSsen算法及其变形winograd算法用分而治之的方法把矩阵乘法时间复杂性由传统的D(n。)改进到0(佗kg。n.但是对于奇数阶矩阵,在划分子矩阵时,要作特殊处理才能继续使用此算法.本文提出了一种非等阶“十”字架划分方法,可以最少化填零,最大化性能,使得奇数阶矩阵乘法的时间复杂性更加接近偶数阶矩阵乘法的效果.计算实例显示该方法是有效的.     

求线性规划问题相容方程组非负解的算法

本文提出一个解线性规划问题的新算法.其最优解是通过求一个相容方程组的非负解而得到.这算法的计算量在最坏情况下是O(mnτ),其中τ是相应方程的m×n矩阵非零元素的个数.     

一类极小谱任意符号模式矩阵

研究了一类恰含2n个非零元的n(n≥5)阶零-非零模式矩阵P.证明了将P中所有非零元规定适当的符号,或换为适当的复数,分别可得到一个极小谱任意符号模式矩阵A和一个极小谱任意的复符号模式矩阵S.     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

含有极小单侧理想单纯环的结构

一个矩阵称为几乎零矩阵,如果矩阵的元素除了有限多个外皆为零。一个矩阵环称为几乎零矩阵环,若它的每个元素都是几乎零矩阵。本文我们获得了如下的主要结果,任何含有极小单侧理想的单纯环必可以模同构地嵌入到一个除环上的几乎零矩阵环中。     

多尺度优势模糊目标决策系统的粗糙集、最优尺度选择及约简

多尺度决策系统的知识获取是当今的研究热点之一。然而,在处理实际数据时,多尺度决策系统中的条件属性值之间可能存在优劣关系,决策属性取值可能为模糊数。针对这一类多尺度决策系统的知识获取问题,本文构建了多尺度优势模糊目标粗糙集模型,给出了该模型的最优尺度选择算法,并讨论了获取所有最优尺度约简的分辨矩阵法和获取一个最优尺度约简的简便算法。最后将本文提出的多尺度优势模糊粗糙集模型、最优尺度选择和规则获取算法应用于计算机审计风险评估,得到较为合理的评估规则。     

一类0-1二次规划最优解的新算法

从矩阵的基础知识出发,给出了当目标函数矩阵是严格对角占优阵时,快速地获得0-1二次规划最优解的一个新算法;该方法具有很强的实用性,是此类问题的一个高效求解算法.     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。     

加权Motzkin序列的Hankel行列式

基于经典的Motzkin路引入了一类新的加权Motzkin路的定义,用这种路给出了一类指数型Riordan矩阵的组合解释,得到了相应的Riordan矩阵第0列元素(加权Motzkin序列)的加法公式.作为应用,得到了一类加权Motzkin序列的Hankel行列式的计算方法.     

瞬态动力问题的遂单元矩阵分裂和逐步积分方法

本文对瞬态动力问题,结合逐步积分方法提出了一类广义的矩阵分裂和逐单元松弛算法,摆脱了有限元法通常需形成总体刚度矩阵,总体质量矩阵和求解大型稀疏方程组的工作,理论分析和计算实例表明,本文的广义矩阵分裂是最优的分裂方案.本文的算法物理意义明确,便于编写程序推广应用.     

瞬态动力问题的逐单元矩阵分裂和逐步积分方法

本对瞬态动力问题，结合逐步积分方法提出了一类广义的矩阵分裂和逐单元松弛算法，摆脱了有限元法通常需形成总体刚度矩阵，总体质量矩阵和求解大型稀疏方程组的工作，理论分析和计算实例表明，本的广义矩阵分裂是最优的分裂方案，本的算法物理意义明确，但于编写程序推广应用。     

一类排序问题的最优解算法

文[1]讨论了将多个零件分派给多台机器加工的一类排序问题,对满足特定条件的分派给出使总花费时间最少的计算方法.但条件过于苛刻,本文讨论一般的排序问题的最优解算法.     

近似逼近l_1精确罚函数的罚函数

本文对可微非线性规划问题提出了一类新的近似渐近算法与一类渐近算法,它们都是基于一类逼近l1精确罚函数的罚函数而提出的.并证明了近似算法所得序列若有聚点则其为原问题的最优解;若所得序列为无界的,则给出了序列值收敛到最优值的一个充分条件.对渐近算法,在弱的假设条件下,证明了算法所得的极小点列有界,且其聚点均为原问题的最优解.并在Mangasarian-Fromovitz约束条件下,证明了有限次迭代之后,所有迭代均为可行的,即迭代所得的极小点为可行点.     

航空器供油问题中完全逆序类中的多项式时间可解类

航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2ⁿ),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。