英语原文共 20 页

第二章 系统建模基础

一. “系统”的概念

英文中系统(system)一词来源于古代希腊文(systεmalpha;)，意为部分组成的整体。一般系统论的创始人贝塔朗菲(Ludwig Von Bertalanffy)将系统定义为：系统是相互联系、相互作用的诸元素的综合体。这个定义强调了元素间的相互作用、以及系统对元素的整合作用。中国科学家钱学森认为：系统是由相互作用、相互依赖的若干组成部分结合而成的具有特定功能的有机整体，而且这个有机整体又是它从属的更大系统的组成部分。可以说，一群有相互关联的个体组成的集合称为系统。

可以这样对系统的定义进行数学描述：如果对象集S满足下列两个条件

(1)S中至少包含两个不同元素；

(2)S中的元素按一定方式存在相互联系；

那么则称S为一个系统，S的元素为系统的组成部分。

系统具备以下三个特性：

(1)多元性：系统是多样性的统一，差异性的统一；

(2)相关性：系统不存在孤立元素组分，所有元素或组分间相互依存、相互作用、相互制约；

(3)整体性：系统是所有元素构成的复合统一整体。

满足以上数学描述，并具备以上三个特征的有机整体，就可以作为系统来进行建模和分析。按照形成和运行特征划分，系统可以分为以下三类：

自然系统：系统内的个体按自然法则存在或演变，产生或形成一种群体的自然现象与特征。自然系统的典型特征是“自组织性”，即：系统高度自治，并且通过自组织的方式协调运行，如：生态平衡系统、生命机体系统、天体系统、物质微观结构系统等等，就是典型的自然系统。人脑属于自然系统，是迄今我们所知道的最复杂的系统。

人工系统：系统内的个体根据人为的、预先编排好的规则或计划好的方向运作，以实现或完成系统内各个体不能单独实现的功能、性能与结果。人工系统的典型特征是“设计性”，即：系统是以设计为基础而产生的，并且依据设计的规则协调运行，如：产品组件系统、自动控制系统、计算机系统、液压系统、教育系统、医疗系统等等，都是典型的人工系统。

复合系统：复合系统是自然系统和人工系统的组合，既具有一定的设计特征，又具有显著的自组织特征，如：社会系统、交通系统、生产系统、经济系统等等，这些系统在形成和运行过程中，经过了人为的设计，但是，由于系统所包含的元素存在复杂关联特征，使得系统在运行与演化过程中，并不能完全在人为设计的控制之内，而是具有自组织特征，这就形成了复合系统。

可以从三个方面理解系统的概念：

(1)系统是由若干要素组成的。这些要素可能是一些个体、元件、零件，也可能其本身就是一个系统。如运算器、控制器、存储器、输入和输出设备组成了计算机的硬件系统，而硬件系统又是计算机系统的一个子系统。

(2)系统有一定的结构。一个系统是其构成要素的集合，这些要素相互联系、相互制约。系统内部各要素之间相对稳定的联系方式、组织秩序及失控关系的内在表现形式，就是系统的结构。例如钟表是由齿轮、发条、指针等零部件按一定的方式装配而成的，但一堆齿轮、发条、指针随意放在一起却不能构成钟表；人体由各个器官组成，但各器官简单拼凑在一起不能成其为一个有行为能力的人。

(3)系统有一定的功能，或者说系统要有一定的目的性。系统的功能是指系统与外部环境相互联系和相互作用中表现出来的性质、能力、和功能。例如信息系统的功能是进行信息的收集、传递、储存、加工、维护和使用，辅助决策者进行决策，帮助企业实现目标。

二. 系统建模的一般步骤

系统建模，就是对现实世界中的某一特定系统，根据问题的求解目标和约束条件，抽象出可以通过数学或软件方法求解的仿真与优化模型。凡是用模型描述系统的因果关系或相互关系的过程都属于建模，因描述的关系各异，所以实现这一过程的手段和方法也是多种多样的。可以通过对系统本身运动规律的分析，根据事物的机理来建模，也可以通过对系统的实验或统计数据的处理，并根据关于系统的已有的知识和经验来建模。

系统建模主要用于三个方面：

(1)分析和设计实际系统。例如，工程界在分析设计一个新系统时，通常先进行数学仿真和物理仿真实验，最后再到现场作实物实验。用数学仿真来分析和设计一个实际系统时，必须有一个描述系统特征的模型，对于许多复杂的工业控制过程，建模往往是最为关键和最为困难的任务。

(2)预测或预报实际系统的某些状态的未来发展趋势。例如，根据以往的测量数据建立气象变化的数学模型，用于预报未来的气象。

(3)对系统实行最优控制。只有先建立一个能表征系统特征的数学模型，才能在数学模型的基础上，根据极大值原理、动态规划、反馈、解耦、极点配置、自组织、自适应和智能控制等方法，设计各种各样的控制器或控制律，从而实现系统优化。

对于同一个实际系统，人们可以根据不同的用途和目的建立不同的模型。因为既不可能、也没必要把实际系统的所有细节都列举出来，所以建立的任何模型都只是实际系统原型的简化。如果在简化模型中能保留系统原型的一些本质特征，那么就可认为模型与系统原型是相似的，是可以用来描述原系统的。因此，实际建模时，必须在模型的简化与分析结果的准确性之间做出适当的折中。

系统建模的一般流程如图2.1所示：

图2.1 系统建模的一般方法

(1)模型准备：首先要了解问题的实际背景，明确题目的要求，然后搜集各种必要的信息。

(2)模型假设：在明确建模目的、掌握必要资料的基础之上，通过对资料的分析与计算，找出起着主导作用的因素，经过必要的精炼、简化之后，提出若干符合客观实际的假设，使问题的主要特征凸现出来，忽略问题的次要方面。一般来说，一个实际问题不经过简化假设，就很难转换成数学问题。假设不合理或过于简单，会导致模型的失效；假设过分详细，则大幅度提升了建模复杂度，使建模和求解工作都很难进行。因此，模型假设，是在简化与可行之间的折中，其目标是在求解正确性的前提下，尽可能简化模型、高效求解。
(3)模型构成：根据所作的假设以及事物之间的联系，利用适当的数学工具去刻画各变量之间的关系，建立相应的数学结构，把问题转化为数学问题。

(4)模型求解：利用已知的数学方法来求解上一步所得到的数学问题，这时往往还要做出进一步的简化或假设。在难以得出解析时，可以借助计算机通过迭代搜索的方式求出数值解。

(5)模型分析：对模型解答进行数学上的分析，有时要根据问题的性质分析变量间的依赖关系或稳定状况，有时是根据所得结果给出数学上的预报，有时则可能要给出数学上的最优决策或控制，不论哪种情况，常常都需要进行误差分析、模型对数据的稳定性或灵敏性分析等。

(6)模型检验：分析所得结果的实际意义，与实际情况进行比较，看是否符合实际。如果结果不够理想，应该修改、补充假设或重新建模，有些模型需要经过几次反复的修改，才能不断完善。

(7)模型应用：所建立的模型必须在实际中应用才能得到验证和产生效益，在应用中不断改进和完善，应用的方式取决于问题的性质和建模的目的。

系统建模的一般步骤如下：

(1)抽象设计变量

通过调研，对所研究的系统有全面的深入的了解，然后将问题进行抽象和分离，将错综复杂的问题分离出能反映问题特征的研究对象，对系统进行尽可能详细的描述。

(2)构造目标函数

目标表示仿真要回答的问题以及系统方案的说明，明确系统的范围与环境。一般来说，仿真目标不同，所建立的模型以及所需采集的数据也不同。目标函数(objective function)是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。

(3)构造约束条件

从纯数学的角度讲，存在无约束问题，但是在工程实际中，任何一个模型几乎都是有限制条件的。这些限制条件在建模过程中称为约束条件。只有满足所有约束条件的建模方案才可以作为用于求解的模型。

(4)设计求解方法

建立完整的数学模型，只是系统建模的第一步，更重要的是，采用何种方法来求解数学模型，从而得到满足约束条件的优化解。求解方法有传统优化方法和仿生方法，根据问题的特性，可以选择不同的方法进行模型求解。

三. NP-hard问题与NP完全问题

3.1系统复杂性的概念及其基本特征

复杂系统(Complex System)是由许多平级要素构成的网络，这些组分通过使用一些既定的规则来对外界复杂的信息进行井然有序地处理，自身可以通过学习和记忆从而做出更好的决策，并不断完善系统以应对更复杂的信息。复杂系统具有一定的规模，是不断进化的系统，如生物的大脑、细胞、社会总体以及生态系统等，每个复杂系统内部都有多个子系统，这些子系统之间相互联系、相互作用，影响着最终的决策。

一般认为复杂系统具有以下特征：

(1) 非线性

非线性表明整个系统不是简单的组分堆砌而成的，而是各组分之间有机地结合在一起，即整个系统远大于各组分之和，每一个子系统以及部分子系统之和也不能代表系统整体，它们只能是该系统的一部分。

这就表明非线性是复杂系统的前提，是必要条件。

(2) 动态性

动态性说明系统是活的，是持续进化的，是远离平衡态的。随着时间的迁移，在自身因素和外界环境的共同影响下，不断的调节自身以适应环境的变化，通过自组织的作用，向更条例有序的方向发展、改进。

(3)开放性

开放性表明系统是开放的，是与外部环境是相互关联、相互作用的，不断地与外界进行信息与物质的交换并及时做出反馈，只有在这种交换前提下，系统才能得到长足的发展。

(4) 积累效应(初值敏感性)

积累效应说明在系统初期的决策会对整个系统的发展起着巨大的影响。也就是人们常说的“蝴蝶效应”，当系统在起始状态时发生了微小的变化，那么随着时间的迁移，系统不断的演化，这种微小的变化就会慢慢积累并逐步放大，最终会对系统的决策产生巨大的影响。

由于这种敏感性的存在，导致不能对整个系统做出精准地预测。

(5)分型性(结构自相似性)

也就是系统中的各组分以一定的方式与系统整体相关联，同时系统中的各组分之间也会存在自相似性。这为我们研究认识系统整体与各组分提供了思路。

(6)自组织性

自组织性表明每一个子系统或者每一个组分之间的工作在各司其职的条件下，并互相保持着一定的联系，所有的行为是自发组织起来的。这就表明了当一个系统的自组织性越强时，那么这个系统进化和适应新的外界环境的速度就越快。

综上所述，一个复杂系统内部有很多相互联系有机结合的子系统，具有能独立完成相关功能的动态体系，是一个开放的、具有自组织性、自相似性的非线性系统。

正如当身体受伤时，人体的自我治愈并不是杂乱无章的，而是各组织、细胞按照相关的步骤严格执行的：身体受伤→血小板迅速抵达伤口止血并凝固→人体内的免疫系统发挥体液免疫和细胞免疫功能，来抵御外来细菌病毒的侵害→相关细胞组织的自我修复治愈→伤口愈合；即使当前世界科技已经得到了长足的发展，可是人们还是无法创造出和大脑那样聪明的机器，因为人脑中大约有成百上千亿个脑细胞，而每一个脑细胞所发挥的作用相当于世界上较为先进的计算机，成百上千亿的脑细胞之间的相互联系会导致这种制造复杂度成几何倍数飞速增加，所要面对的难题也是无法想象的。所以我们身边充满了复杂系统。

3.2 P、NP、NPC、NP-Hard问题

3.2.1 预备知识

(1)时间复杂度(Time Complexity)

时间复杂度定性描述了一个算法的运行所需的时间。它表明随着问题规模的扩大，由于解空间的爆炸，衡量一个算法求得最优解所需的时间增长的快慢。时间复杂度常用大O符号表述。程序的时间复杂度一般可以分为两种级别：

–多项式级的复杂度，如O(1)、O(log(n))等；

–非多项式级的，如O(n!)、O(a^n)等。(计算机往往不能计算这种时间复杂度)

如冒泡排序法，它是一种相对较为简单的排序方法，它的规则是对需要排序的数列进行若干次遍历，每一次遍历时，都会按照从前往后的这个顺序依次比较相邻两个数的大小，如果前面的数比后面的数大，则交换他们所处的位置。这样就会得出在第一次遍历后，该数列中最大的数字就会处于这个数列的末尾，第二次遍历之后第二大的数字就会被排在倒数第二的位置上，以此类推，就可以得知，在进行最后一次遍历后，最小的数字就会被放置在数列的首项。这样一来，整个数列会按照从小到大的顺序有序排列。

假设该数列中有N个数，遍历一遍的时间复杂度为O(N)，因为要遍历(N-1)!次，因此冒泡算法的时间复杂度为O(n^2)。

(2)约化(Reducibility)

若可寻找到一个变化法则，对任意一个问题A的输入，可以按照这个法则相应地变换成问题B的输入，使两个问题的输出结果相同，那么就可以说，问题A可以约化为问题B。简单地说，问题A可以约化为问题B的含义是，可以用问题B的解法去求解问题A，也可以说，问题A是问题B 的一种特殊情况。同时也告诉了我们一个直观的信息：B的时间复杂度高于或者等于A的时间复杂度。

约化具有传递性，如果说问题A可以约化为问题B，问题B可以约化为问题C，那么就可以说问题A也可以约化为问题C。

3.2.2 P、NP、NPC、NP-Hard问题的概念及认识

P(Polynomial)问题是计算起来很快的问题。

如果说一个问题在多项式的时间复杂度，可以寻找到解决它的算法，那么这个问题就是P问题，也就是算法的时间

资料编号：[4183]