自由边界问题的改进投影算法

【目的】自由边界问题在变分不等式中具有重要的应用,而很难用数值方法直接得到它的解。【方法】利用有限差分近似,得到该问题的一个新的投影不动点算法。【结果】将自由边界问题离散为一个标准的有限维线性互补问题,而该问题又等价于一个投影不动点问题。于是得到求解自由边界问题的改进投影算法,并给出了算法的具体过程。【结论】理论分析和数值结果都表明了所给算法的有效性。     

匹配在管理科学中的应用

图论中的匹配有着广泛的应用,这里就匹配在“排课表问题”、稳定匹配在“婚配问题”和“大学招生问题”以及完美匹配在“人员分配问题”给出了数学模型和相关算法。     

自由边界问题的改进投影算法

【目的】自由边界问题在变分不等式中具有重要的应用,而很难用数值方法直接得到它的解。【方法】利用有限差分近似,得到该问题的一个新的投影不动点算法。【结果】将自由边界问题离散为一个标准的有限维线性互补问题,而该问题又等价于一个投影不动点问题。于是得到求解自由边界问题的改进投影算法,并给出了算法的具体过程。【结论】理论分析和数值结果都表明了所给算法的有效性。
     

稳定匹配：起源、定义和进展

经济管理领域存在许多双边匹配决策问题,而匹配的稳定性对于决策制定非常重要。为了深入了解稳定匹配理论的本质、起源和目前发展现状,把该理论运用到当前的研究问题上,收集整理了该领域的国内外相关文献,在此基础上进行分析和综述。首先概述了当前理论研究和应用研究成果,介绍双边匹配和稳定匹配的起源,阐述稳定匹配的定义、基本定理和实现的机制,然后分析稳定匹配网格定理和结构特性,并考虑多方匹配的特性和相关理论,最后展望了稳定匹配的应用前景。稳定匹配有了较好的理论基础,但仍然存在许多亟待解决的问题,在应用领域有着宽阔的领域。
     

给定匹配数的图的代数连通度的上界

【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先，利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图；其次，利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的，从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图，克服了以往利用图的最小度，最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征，但无法得到此类图的连通度的上界这一弊端。     

芬斯勒流形上的Bochner不等式及热方程整体解的构造

【目的】研究芬斯勒几何中的Bochner公式及与Laplacian算子相关的问题。【方法】利用偏微分方程及Sobolev空间的相关理论展开讨论。【结果】利用L²-梯度估计证明了一个重要的Bochner不等式,讨论了芬斯勒流形上热方程整体解的应用并构造了热方程的若干整体解。【结论】给出了一类Bochner公式成立的充分条件并构造了热方程的若干整体解。     

基于可变速率M/M/c排队的接触匹配模型分析

【目的】针对实际生活中利用手机软件呼叫出租车的排队场景,建立并分析了可变到达率和可变服务率的接触匹配的M/M/c排队模型。【方法】利用概率分析方法导出拟生灭过程的状态转移规律及无穷小生成元矩阵,利用矩阵几何解方法给出系统的稳态平衡条件、稳态概率分布及系统的主要性能指标。【结果】通过数值分析讨论系统参数对于性能指标的影响,并建立系统收益函数研究系统最优收益。【结论】得到了系统参数对系统性能指标及系统收益的影响关系,表明在接触匹配中应当同时调整服务率及接触匹配成功率才能显著提高系统收益。     

工件可外包的单机准时排序问题

【目的】研究一类单机准时排序问题,其中工件有公共的交货期和交货截止期,允许工件外包加工,外包加工将产生外包费用,目标是极小化总提前时间,总延迟时间与总外包费用之和。【方法】首先给出该问题的若干最优性性质,然后对于交货期和交货截止期都待定,以及给定交货截止期两种情形分别讨论。【结果】对于第一种情形,设计了多项式时间算法,对于第二种情形,证明了它是NP-困难的并设计了伪多项式时间的动态规划算法。【结论】所讨论的单机准时排序问题所得到的结果为冷鲜食品生产管理者提供了有效决策支持。     

正交Haar变换的眉毛识别方法

【目的】提高现有眉毛识别方法的识别效率。【方法】采用快速正交Haar变换模板匹配算法(FOHT),设计一种基于正交Haar变换的眉毛识别方法;同时,使用最大标准子模板和自适应阈值解决了FOHT算法只能处理标准模板且需要手动设置阈值的缺陷。【结果】所构建的眉毛识别方法比原方法效率提高约32%。【结论】正交Haar变换的眉毛识别方法实时性强,具有一定的实用价值。     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。