解一类对称不定线性方程组的奇异方向法

此处B为n×n对称正定矩阵,G是秩为m的n×m矩阵.这是在最优化问题和混合有限元法中大量出现的一类方程组,因此,它的求解问题引起人们的注意. 求解对称不定线性方程组问题已有较多讨论,但针对(2)中A的特殊性构造的算法尚     

复合并行机F''''2|m1≥2,m2=1|Cmax排序问题的归并算法研究

在文献[1]中,已经证明了排序问题F2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F'2|m1≥2,m2=1|Cmax排序问题的一个启发式算法--归并算法,并证明了该算法在最坏情况下的性能比(Performance Ratio)是2m-1/m,且优于文献[2]中算法.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n~(k+2))/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n~(k-1))/((k-1)!).     

极大代数上有限生成模的凸性

研究极大代数上有限生成模的凸性.基于极大代数上有限生成模的几何形态,运用代数与几何方法,分析空间维数n≤3和生成向量数m≥1的有限生成模的凸性.证明n=1,2的有限生成模是凸集.对于n=3,给出m=2的有限生成模为凸集的一个充分必要条件,以及m≥3的有限生成模为凸集的一个充分条件.此外,对于极大代数上有限生成模的几何形态,发现n=3,m≥3的形态有三种情形.     

MapReduce同类机排序问题的改进算法

研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进.     

一类新的分批排序问题的NP完备性证明

本文研究了加权的延迟工作和的排序问题,即极小化的批处理问题, 其中.本文主要考虑了B≥n的情形,即 证明了这个问题是NP-完备的.     

关于上三角矩阵代数之间经典伴随交换单射

令F是一个域,且|F|n+1,m,n为整数且m,n≥3.Tn(T_m)(F)是F上所有n×n(m×m)上三角矩阵的集合.本文中,刻画了从T_n(F)到T_m(F)的保经典伴随交换的单映射,给出了映射的表达式,对相应的方阵的工作是一个新的补充,所用方法是将其化归为相应的线性保持问题.     

有负荷约束的指派问题

通过组合最优化的理论和方法,研究机器有负荷(时间)限制的指派问题,证明其NP困难性,并建立多项式可解的特殊情形算法及一般情形的隐枚举算法.     

带交易费用的离散多因素投资组合最优化(英文)

研究带有凹的交易费函数的离散多因素投资组合模型.与传统的投资组合模型不同的是,该模型中投资组合的决策变量是交易手数(整数),其最优化模型是一个非线性整数规划问题.为此本文提出了一个基于拉格朗日松弛和连续松弛的混合分枝定界算法,为测试算法的有效性,我们分别采用美国股票市场真实数据和随机产生的数据,数值结果表明该算法是有效的.     

隐含条件藏在何处

隐含条件是题设信息一种重要且常见的形式 ,能否发现并利用好题目的隐含条件 ,常常成为能否顺利解题的关键因素 .那么隐含条件到底身藏何处呢 ?一藏在基本概念之中例 1计算C38-n3n +C3n2 1 +n的值 .分析　有些同学做这道题时只是简单地套用一下组合数公式后就不知所措了 ,原因是忽略或忘记了组合数Cmn 中m ,n所应满足的条件 .对此概念缺乏足够的认识 .事实上 ,只要我们注意到Cmn 中m≥ 0 ,m≤n ,n∈N ,则问题立即得到解决 .解　由　3n≥ 3 8-n3 8-n≥ 02 1+n≥ 3n3n≥ 0 192 ≤n≤2 12 .又n∈N ,故n =10 .∴　原式 =C2 830 +C3031 =C230…     

解线性互补问题的区间GAOR方法

1引言设M∈Rn×n,q∈Rn,则线性互补问题LCP(M,q)指的是寻找一个向量x∈Rn,使其满足下面的条件: x≥0 Mx+q≥0 xt(Mx+q)=0由于线性互补问题在工程物理、管理学、经济学、约束最优化等领域的应用非常广泛,所以该问题的研究一直倍受大家的关注,至今已有很多有效的算法.早在20世纪80年代     

排序问题的一个判别条件和一类特殊的m×n排序问题

一、引言 在排序理论的一篇开创性的文章中,Johnson给出了2×n排序问题(二台“机床”,n个“零件”的同顺序排序问题,这里机床和零件被理解成广义的)的最优顺序的算法。在导出这算法时,Johnson给出的判别两个相邻零件的先后次序的一个条件起着关键作用。这判别条件是:设i,j是相邻的两个零件,α_i和b_i(α_j,b_j)是i(j)分别在机床M_1和M_2上的加工时间,如     

平行机物流排序的近似算法

本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究“满足一致性条件”和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

贯序和并行求解线性与非线性方程组的一类算法

1.引论 Abaffy,Broyden和spedicato在最近的论文中,提出了一类求解线性和非线性方程组的算法(有可能推广于求解其它问题,例如最优化问题).我们首先给出这类算法求解线性方程组时的基本形式.设线性方程组为 或把它写成矩阵形式 其中A=(a_1,…,a_m)是n×m阶矩阵,共秩q可以小于m.算法具有拟Newton型结构,其计算步骤如下:     

关于同顺序m×n排序问题消去法的两点注记

本文对[1,2]中指出的一类同顺序m×n排序问题有关的消去法提出两点注记。这里补充提出了一种不涉及下界计算并且检验方法简单的消去准则,同时,对[2]中给出的下界B(S…S′)的算法做了改进,从而使下界B(S…S′)的估值精度有所提高。 一、一个消去准则 首先说明,文中运用的术语和记号除特殊说明外均与[2]的定义相同,不再另述。 同顺序m×n排序问题是指:设有n个零件J_1,J_2,…,J_n和m台机床M_1,M_2,     

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

工件加工可拒绝的无界批量分批排序问题的几点探讨

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.     

具有可用时间限制的两道工序柔性流水车间排序问题

1 引言与符号定义 经典排序问题一般假定机器是一直可用的,但出于定期检修等原因而使得机器并不是在所有时间都可用的情况在实际生产中是比较常见的.机器可用时间限制(LimitedMachine Availability,简记为LMA)模型就是用来刻画某些机器存在不可用时间段情况下的排序问题的.[1]讨论了单机LMA模型的计算复杂性并对一些算法进行了最坏情形分析.[2]研究了平行机环境下的一些LMA模型.继[3]第一个研究了流水车间环境下的LMA模型之后,[4]扩展了其关于复杂性和算法分析的结果。