Modelica建模软件中拓扑排序相关算法研究

为了提高现有OpenModelica软件中对DAE系统的预处理模块中，求强连通分量与拓扑排序部分的性能，提出了基于Kosaraju算法实现的策略。首先阐述Modelica软件的实现原理，叙述拓扑排序相关算法在其中的重要性，再分析现有Modelica软件中使用的求强连通分量与拓扑排序部分的算法，然后比较Tarjan算法的实现方案与Kosaraju算法实现方案。通过实现两种方案，并对实验结果进行比较和分析，验证了Kosaraju算法方案的可行性和有效性。

Modelica建模软件形成的高指标微分代数方程系统指标约简算法研究

随着产品设计的复杂化，应用领域中的数学建模和仿真越来越重要，传统建模方法基于赋值语句，主要考虑单一系统，工程人员需要对程序设计语言和算法求解有相当程度的熟悉，这导致了传统建模方法很难满足复杂产品设计的需要。欧洲仿真界的学者在总结现有建模方法的基础上于1997年推出了一种面向对象的、陈述式的基于方程的语言——Modelica，Modelica语言支持多领域建模，Modelica语言得到了仿真领域众多厂商的支持，成为统一建模领域的事实标准，实现Modelica仿真环境具有重大意义。 编译器是Modelica仿真环境中的核心组件，Modelica编译器会产生高指标DAE系统，除了部分特殊结构的高指标DAE，现有求解器一般不能对通用高指标DAE直接求解，现在一般做法是先对高指标DAE进行指标约简，将其转换成等价的低指标DAE，然后进行求解。这就要求Modelica编译器具有指标约简的功能，以便利用现有求解器进行求解。 本文介绍了几种现有的指标约简算法，给出了各个算法指标约简原理和约简步骤，并对这些算法进行了分析和比较，得出各自的优缺点。最后，本文设计并实现了一个指标约简系统，采用三个Modelica模型产生的方程对系统进行了测试，并验证了实验结果的正确性。

Modelica建模软件中求强连通分量与拓扑排序算法优化的研究

Modelica语言仿真建模在科研工作中已经得到了广泛应用。它能方便地对包含机械、电子、液压、控制、热流等领域的复合物理系统进行基于组件的仿真。现有基于Modelica语言的仿真建模软件支持图形化建模和文本建模两种方式，集成了面向对象、陈述式描述、统一建模、组件重用的优势，给科研工作带来了巨大的便利。 Modelica软件仿真的过程可归结为微分代数方程(differential algebraic equation,DAE)系统的求解。在求解DAE系统时，需要对DAE系统进行约简，直到庞大的DAE系统约简为目前自动求解方法成熟的ODE系统，或约简为方程个数不多的、指标较低的DAE系统，才能使Modelica建模仿真软件具有工业上的应用价值。在约简DAE系统之前，需要对之进行预处理，根据方程之间的数据依赖关系进行拓扑排序，确定求解顺序。排序的过程对应着将DAE系统结构关联矩阵进行块状下三角(block lower triangle,BLT)变换。寻找强连通分量和拓扑排序是对DAE系统进行预处理的重要组成部分。 本文剖析了Modelica软件在仿真时的运行机制，使用几个实例来详细描述在仿真过程中，Modelica软件完成的工作。在寻找强连通分量和拓扑排序这一步，本文提出了使用Kosaraju算法的策略，对由模型得到的有向图直接使用Kosaraju算法，得出DAE系统的求解顺序。文章叙述了强连通分量的含义，并阐述了在求强连通分量时的理论依据，由此引出了Tarjan算法和Kosaraju算法，再分析和比较Tarjan算法和Kosaraju算法，对比了两种策略的优劣，并进行了实验。同时，本文分析了OpenModelica软件包的结构，修改了软件包在寻找强连通分量及拓扑排序相关模块的代码。

Modelica软件中微分代数方程指标约简算法分析

Modelica建模软件会产生高指标的微分代数方程(DAE),因为现有数值求解器一般不能直接对高指标DAE进行求解,所以Modelica建模软件必须对高指标DAE进行指标约简。为提高Modelica建模软件性能,针对现有指标约简算法,展开了理论分析和实验比较,着重对负权二部图算法进行了详细分析,并给出了负权二部图算法的时间复杂度。理论分析和实验结果表明,负权二部图算法相对Pantelides算法有较好的性能,因此可以考虑在Modelica建模软件中使用负权二部图算法来提高性能。

DAE系统中两类指标约简修正算法的研究与实现

为了应对设计复杂产品的需求，研究者们提出了一些面向对象、基于组件的建模语言，比如说Modelica 语言。Modelica语言建模中采用了分治的思想，将大型的系统划分成一系列小型组件，极大程度地提高了模型复用性，简化了建模的过程。 Modelica语言构建的模型往往会被转化成一个DAE方程组。在一些情况中，这个DAE是指标数大于1的高指标问题。由于目前对高指标问题不存在通用的求解器，为了求解这类问题，通常的方法是先对问题进行指标约简。 指标约简有两类主流的方法，一类基于微分指标，如Gear算法；另一类基于结构指标，如Pantelides和哑导方法。Gear方法是解决一般高指标问题最为经典的方法，对它的研究和深入分析意义重大。在本文的第一部分，作者提出了一种Gear方法的修正实现。实验结果表明，对于一类特殊结构的DAE，修正实现比起经典实现做了更少的微分，最终得到了规模更小的方程组。 本文另一部分工作集中在对结构指标修正的方面。相比Gear算法，基于结构指标的指标约简算法是一类快速算法，但是并非百分之百有效。在少数情况下，当微分指标与结构指标不一致时，这类方法会失效。为了提高结构指标的适用性，必须首先消除这种不一致性。因此，作者深入分析了处理这一问题的组合松弛型算法，并做出了相应的实现。利用组合松弛型算法，作者进一步对几个Modelica模型导出的DAE方程组进行了处理。实验结果表明，作者所实现的算法解决了微分指标与结构指标不一致的问题。