关键词： 均衡约束数学规划   均衡约束均衡规划   一阶最优性条件   二阶最优性条件   稳定性   灵敏度   Levenberg-Marquardt方法   误差界   电力市场  

摘要： 均衡约束数学规划问题(Mathematical programs with equilibrium constraints简称MPEC)是约束中含有参数变分不等式或者参数互补问题的约束规划问题MPEC的一个重要来源是双层规划问题(Bilevel programming problem简称BLPP)该问题在经济均衡、博弈论、工程设计、交通科学和顶层设计等领域有着重要的实际应用背景.但是,因为MPEC的约束在任何可行点处都不满足M-F约束规范(Mangasarian-Fromovitz constraint qualification)(实际上它的约束不满足大部分约束规范),所以这类问题不管在理论分析还是在算法设计上都是非常难处理的. 在过去的二十多年里,学者们对MPEC的理论和算法都做了深入的研究.但是仍然存在很多值得研究的地方.在本文,我们将进一步在理论和算法方面深入研究MPEC问题.特别地,我们得到如下的结果： (1)尽管MPEC的一阶最优性条件和约束规范理论已经比较完善,但是文献中一直没有关于MPEC的各种稳定性的最弱约束规范的任何研究结果.为此在第2章,我们首先深入研究了保证各种稳定性的最弱的约束规范.然后,考虑到最近有文献提出一种很弱的保证稳定点孤立性的条件,但没有说明该条件是否为约束规范,作为其补充,我们利用最弱约束规范条件证明了上述条件不仅是一个新的约束规范,并且还蕴含局部误差界条件. (2)在第3章,我们系统地研究了MPEC的二阶最优性条件.我们首先利用奇异或者非奇异的S-乘子研究了MPEC的二阶充分性条件.然后,我们给出了一些更弱的MPEC约束规范,并在这些约束规范条件下,得到了多种MPEC的二阶必要最优性条件.最后,我们在非常弱的条件下讨论了MPEC的局部最优解和稳定点的孤立性. (3)在第4章,我们研究了一类比参数MPEC更广泛的几何约束参数数学规划问题(MPGC)的稳定性.我们证明了,在某种约束规范和二阶充分性条件或者二阶增长性条件下,局部最优解映射和稳定点映射关于扰动参数都是非空连续的,且在合适的条件下,稳定对映射是平稳的.然后我们把这些结果应用到文献中已存在的几类问题上.尤其,对MPEC问题,我们证明了在M-乘子二阶充分性条件下,M-稳定对映射是平稳的；在S-乘子二阶充分性条件和双退化指标集为空集的条件下,S-稳定对映射是平稳的. (4)第5章旨在研究参数MPEC问题的灵敏度.我们在扰动的MPEC-RCR正则性和MPEC-NNAMCQ(均弱于MPEC-LICQ)条件下,得到了参数MPEC的价值函数的一阶方向导数的表达式.而且,我们把新的结果应用到局部的参数MPEC问题,把文献中所需要的所有分片问题都满足强二阶充分性条件减弱到S-乘子精炼二阶充分性条件.在本章的最后,我们用加强的M-/C-稳定性乘子研究了价值函数的极限次微分和地平次微分的上估计. (5)第6章旨在开发求解MPEC的有效算法.由于MPEC的约束不满足标准的约束规范,在文献中存在几种流行的稳定性条件：C-/M-/S-稳定性.我们首先把这些稳定性系统再定式为带有简单约束的光滑方程组,然后提出了一种改进的Levenberg-Marquardt方法来求解这些约束方程组并且把该方法全局化.我们证明了,在弱局部误差界条件下,该方法是全局收敛的且是局部超线性收敛的.最后我们讨论了一些使弱局部误差界成立的充分性条件且通过大量的数值试验说明了这些条件是容易满足的. (6)第7章旨在求解一类具有特殊结构的EPEC问题的正规C-/M-/S-Nash稳定点.我们证明了,在目标函数满足某种分离性条件下,该EPEC问题的正规C-/M-/S-Nash稳定点等价于某个MPEC的C-/M-/S-稳定点.而且,我们用电力市场中的两个数值例子来说明我们提出的方法的有效性.

关键词： 网络性能   链路丢包率   性能推理   数学规划  

摘要： 随着计算机网络的飞速发展,多种多样的网络应用日趋流行,计算机网络的性能受到了前所未有的关注,如何有效地监测并推理网络性能成为网络管理领域的一个十分重要的课题。当前的网络性能推理技术着眼于网络时延、链路丢包率等性能指标展开研究并取得了显著的成果,但这些技术依然面临很多亟待解决的问题,包括对网络造成的额外负载过重、实时性较差等,距离快速、准确的网络性能推理的目标依然存在一定的差距。 本文在深入研究和分析现有网络性能推理技术的基础上,针对网络链路丢包率的推理,根据不同的网络规模特征分别设计了基于数学规划的小规模网络和大规模网络的丢包率推理算法,利用数学规划方法的优势克服了现有网络性能推理中存在的探测开销大、实时性差、测量时间长、推理结果准确度低等问题。算法根据网络相关信息,将丢包率推理问题转化为数学规划问题,具有耗时较短、结果较准确并且可以避免对网络造成大量额外负载等诸多优点。本文还在仿真网络环境和真实网络环境中开展了实验,将本文提出的算法与现有的网络性能推理算法进行比较分析。实验结果表明,与现有算法相比,本文提出的基于数学规划的网络性能推理算法能够更加准确、快速地得到推理结果,具有显著的优越性。

关键词： 计算机数学教学   算法与算法思想   途径方法  

摘要： 本文立足于《计算机数学》课程改革,分析了目前《计算机数学》课程教学中存在的主要问题,提出从算法思想的融入为着手点进行高职计算机数学课程改革,并对算法思想的概念与来源进行了考证,对算法思想融入《计算机数学》途径与方法提出了自己的观点。

关键词： 形态学骨架   猝熄函数   骨架提取   骨架重建  

摘要： 我们想用一个简单的方法去描述一个图像的外形，这个外形（轮廓）要尽可能包含原始图像的重要信息。这种转换或者说简化，通常包含了原始图像的骨架，由一种细化方法或骨架化方法来实现。 形态学骨架在图像分割，图像的表达，和离散的二值图像的编码等方面是非常有用的，因为它的拓扑信息和原始图像能够通过形态学骨架重建。本文围绕数学形态学骨架以及骨架提取和重建算法展开研究工作。首先，对本文用到的一些数学形态学相关基本理论作了研究，并对他们的性质进行了证明；然后，着重研究了数学形态学骨架，即骨架的形态学表示和形态学骨架的性质，包括连续的形态学骨架表示和它的性质，以及离散的二值形态学骨架表示和骨架的性质，本文中还对这些性质做了较详细的证明，通过本文的研究，使得对形态学骨架有了更深的理解和认识；最后，在本文中列举了一些传统常见的骨架提取算法，分别对它们的优缺点进行了简单的描述，结合上一章对形态学骨架性质的研究，对传统形态学骨架提取算法进行了改进，使得提取的骨架具有更好的连通性和中轴对称性，采用本文中的算法实现了原始图像的骨架提取与重建。

关键词： Dual energy X-ray (DXA)   image reconstruction   discrete tomography   algebraic reconstruction techniques (ART)  

摘要： Relatively high radiation CT techniques are being widely used in diagnostic imaging raising the concerns about cancer risk especially for routine screening of asymptomatic populations. An important strategy for dose reduction is to reduce the number of projections, although doing so with high image quality is technically difficult. We developed an algorithm to reconstruct discrete (limited gray scale) images decomposed into individual tissue types from a small number of projections acquired over a limited view angle. The algorithm was tested using projection simulations from segmented CT scans of different cross sections including mid femur, distal femur and lower leg. It can provide high quality images from as low as 5-7 projections if the skin boundary of the cross section is used as prior information in the reconstruction process, and from 11-13 projections if the skin boundary is unknown.

关键词： 高中数学   新课程   算法初步   教学探讨  

摘要： 本文首先对算法的概念进行了科学的界定,简述了高中数学新课程中算法的内容;其次,从新课程标准对算法的要求、学生认知能力及高考要求这三个方面对算法的教学进行定位进行了分析并在此基础上对算法初步的教学进行探讨。

关键词： 小学数学   算法多样化   逻辑结构   研究成果  

摘要： 《数学课程标准》提倡算法多样化新理念,激发教师对它从不同的角度进行解读和探讨,形成林林总总的观点和经验交流。本文特将算法多样化的相关文献整理,加以研究,以其逻辑结构为视角,形成综述,一方面对研究成果总结肯定,另一方面促进对其系统解读。

关键词： 小学数学   算法   多样化  

摘要： 算法多样化是指在计算一道试题时,由于学生的生活背景、知识基础、思维方式、思考角度等方面的差异,学生选择不同的计算方法。这些不同的计算方法,就构成了算法多样化。新课程实验以来,广大教师对算法多样化展开了多层面的探讨,但困惑不少。

关键词： Engineering   Industrial Engineering   Mathematics   Job Shop Scheduling   Max Plus Algebra   Mathematical Modeling   Computational Complexity   Makespan   Heursitics   Simulation   Scheduling Algorithm  

摘要： This dissertation develops efficient methods for calculating the makespan of a perturbed job shop. All iterative scheduling algorithms require their performance measure, usually the makespan, to be calculated during every iteration. Therefore, this work can enhance the efficiency of many existing scheduling heuristics, e.g. Tabu Search, Genetic Algorithms, Simulated Annealing etc. This increased speed provides two major benefits. The first is the capability of searching a larger solution space, and second is the capability to find a better solution due to the extra time. The following is a list of major highlights of this dissertation. The dissertation extends the hierarchical block diagram model formulation and composition that was originally proposed by Imaev. An algorithm is developed that reduces the complexity of calculating the makespan of the perturbed schedule of job shop with no recirculation from O(MNlogMN) to O(N2), where M is the number of machines and N the number of parts. An efficient algorithm that calculates kleene star of a lower triangular matrix is presented. This algorithm has complexity of O((n3)/6) which is 1/16th of the traditional approach. Finally, a novel pictorial methodology, called the SBA (Serial Block Addition), is developed to calculate the makespan of a perturbed job shop. A very efficient single perturbed machine scheduling algorithm, with complexity of O(N2), is derived using the SBA method. The algorithm was tested on 10,000 randomly generated problems. The solutions provided by scheduling algorithm were 95.27% times, within a 3% deviation of the optimal solutions.