《系统工程》03-系统工程的理论基础

3系统工程的理论基础

系统工程是一门交叉学科，其最基础的理论涉及系统最优化、系统控制与系统的信息处理三个方面。3.1控制理论基础3.2信息论基础3.3系统最优化理论3.1控制理论基础3.1.1控制系统的描述：外部,内部;

能控性,能观性,鲁棒性.3.1.2系统最优控制:

容许控制,系统约束,性能指标,

极大值原理3.1.3大系统理论控制论创始人：维纳（N.Wiener，1894-1964）美国数学家，控制论的创始人。其于1948年出版的《控制论》（CYBERNETICS)一书标志了控制论的诞生。控制论的基本概念：控制——根据系统内外部条件对系统进行调节，以克服系统的不稳定性，使系统保持或达到某种特定的稳定状态，或使系统按照某种规律变化的过程。控制系统

结构：一般由施控者、传递者和受控者三部分组成。目的：控制系统的行为，达到既定的目标。行为：在外界环境作用下系统作出的反应。反馈：控制系统将输入的信息作用于受控对象后所产生的结果再一次送到输入端，并对信息的再输出发生影响的过程。反馈种类：正反馈负反馈

大系统理论

大系统一般是指规模庞大（维数很高）、结构复杂（多层次、多关联）、目标众多（目标间往往有冲突）、时标各异（同一系统中有多个时标）、位置分散，并常常具有随机性和不确定性的复杂系统，广泛存在于社会、政治、经济、生态、环境、工业等许多领域中。大系统的主要特征之一体现在其结构复杂上。大系统结构取决于组成大系统的子系统集合和各子系统之间的关联，并决定了大系统的功能，不同结构往往会产生不同的总体功能。由于大系统的对象分散，变量数目众多，关联复杂，往往不宜采用集中式结构，而多为递阶结构和分散结构。

大系统理论研究大系统的结构方案，稳定性，最优化，建立模型的模型简化等问题称为大系统理论。3.2信息论基础随着科学技术的发展和社会进步，越来越多的事实证明，系统元素之间、子系统之间的相互联系和作用，系统与环境的相互联系和作用，都要通过交换、加工、利用信息来实现，系统的演化行为也需要从信息观点来理解。因此，信息是系统工程的基本概念之一。两个基本问题：什么是信息和如何度量信息。信息论基础创始人：申农(C.E.Shannon)（1916-2001）美国科学家。1948年申农的“通讯的数学理论”（ThemathematicalTheoryofcommunication)，长达数十页的论文，成了信息论正式诞生的里程碑。回顾20世纪的信息革命风暴，把信息论的创始人称为伟大的科学家并不为过。确实，他对人类贡献远远超过了一般的诺贝尔获奖者。信息论基础美国数学家申农（C.E.Shannon）和维纳以信息为主要研究对象，以信息的运动规律和应用方法为主要研究内容，以计算机、光导纤维等为主要研究工具，以扩展人类的信息功能为主要研究目标。信息论基础信息——具有新内容或新知识的消息信息是对事物存在方式、运动状态、相互联系的特征的一种表达和陈述。表现为文字、图象、图形、语言、声音等形式。

信息论基础信号最具体，它是一物理量，可测量、可显示、可描述，同时它又是载荷信息的实体-----信息的物理层表达消息是具体的、非物理的，可描述为语言文字、符号、数据、图片，能够被感觉到，同时它也是信息的载荷体。是信息论中主要描述形式-----信息的数学层表达信息是抽象的、非物理的，是哲学层表达。信息论基础信息论的创立者香农将信息定义为“两次不确定性之差”，即“不确定性的减少”。从通信角度看，信息是数据、信号等构成的消息所载有的内容。消息是信息的“外壳”，信息是消息的“内核”。从应用角度讲，信息是指能为人们所认识和利用的、但事先又不知道的消息、情况等，也就是说，信息对于收信者应该是有用的和未知的。信息论基础以通信为例，凡通信过程至少涉及信息发送者（称为信源）和信息接收者（称为信宿），通信是信源和信宿之间的一种特定联系。信宿需要了解信源发出的信息的内容，但在得到信息前该内容是不知道的，或称信宿对信息内容的“猜测”是具有不确定性的。一旦信宿收到了信源发来的信息就消除了这种不确定性，所以通信系统中传送的正是这种能够消除不确定性的信息，从而增加了系统的确定性。然而，实际的通信过程可能完全消除了不确定性，也可能只是部分消除了不确定性，甚至完全没有消除不确定性，这取决于信息量的大小。因此将信息定义为不确定性的减少是完全合理的。3.3系统最优化理论系统工程，其核心目标之一是使系统运行在最优状态，因此，系统最优化技术是其最重要的理论支撑。系统最优化理论系统优化理论主要包括线性规划、非线性规划、整数规划、动态规划等内容，如果考虑到最优化技术在不同应用领域中的拓展，还应包括排队论、对策论、决策论等，这些都属于运筹学的研究范畴。本书仅介绍与系统工程有关的系统最优化理论包括：线性规划、非线性规划、整数规划、动态规划3.3.1线性规划线性规划上世纪30年代出现，40年代丹兹格提出单纯形法。线性规划主要研究的问题有两类：1．在给定数量的的人力、物力等资源下，如何科学地运用这些资源，以获得最大效益（去完成最大的任务），或在一定的条件下，寻求最优化的设计；2．在给定任务的情况下，如何统筹安排，使用最小量的资源去完成这项任务。线性规划问题：求一组变量，使之满足线性约束条件，且具有线性的目标函数取最大（或最小）值的一类最优化问题。线性规划数学模型一般形式目标函数：满足约束条件:

例3-3-1(生产计划问题)

某工厂有三种原料B1、B2和B3，储量分别为170千克、100千克和150千克。现用此三种原料生产两种产品A1和A2。已知每生产1千克A1需要原料5千克B1、2千克B2和1千克B3。每生产1千克A2需要原料2千克B1、3千克B2和5千克B3。又知每千克A1产品利润为10元，每千克A2产品利润为18元。问在工厂现有资源条件下，应如何安排生产，才使工厂获得最大利润。B1(kg)B2(kg)B3(kg)利润(元)A152110A223518总量170100150解：设安排生产A1、A2产品的产量分别为和，则根据题意，数学模型为

s.t.求解方法：1.图解法

2.单纯形法例3-3-2运输问题（产销平衡）从两个仓库（发点）运送库存原棉到三个纺织厂（收点），两仓库的库存量、三个纺织厂的需求量、每吨原棉从个仓库运到工厂的所需运费如下表：问：在保证各个纺织厂的需求都得到满足的条件下，应采用哪一种运送原棉的方案使得运费最少？工厂1工厂2工厂3库存量（吨）仓库121350仓库222430需求量(吨)40152580s.t.求解方法：

1.表上作业法

2.单纯形法线性规划模型三个基本要素：决策变量目标函数约束条件线性规划问题的标准形：s.t.Maxz=c1x1+c2x2+…

+cnxn

Maxz=cTx(LP)s.t.Ax=b

x≥0线性规划问题的标准形描述：目标函数求最大决策变量均非负约束条件为等式右端常数项非负线性规划问题的标准形的转化方法：

1）若约束条件不是等式，则加松弛变量（≤）或减剩余变量（≥）；

2）若目标函数求最小，则对应目标函数反号后求最大；3）若有的条件的右端常数为负，则将该条件的两边同乘以-1；

4）若某变量没有非负约束，则可引入两非负变量，将该变量表示成两非负变量之差。

5)若某变量为负，引入新变量等于该变量的反号.例

将下列线性规划模型化为标准形s.t.相关的概念

相关的概念

图解法求解主要讲解图解法（对两个决策变量有效）；和单纯形法（决策变量个数不限）。用图解法求解线性规划问题时不必将线性规划模型化为标准形式，其求解过程一般经历以下几步：以两个决策变量为轴在平面上建立直角坐标系；图示由线性等式和不等式构成的约束条件，标出可行域；图示并移动目标函数，寻找最优解。图解法求解图解法求解图解法求解练习:用图解法解线性规划问题min z=-x1-3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2线性规划模型及单纯形法矩阵形式：线性规划的标准形式：

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩阵线性规划模型及单纯形法线性规划的规范形式：

MaxcTx(P)s.t.Ax≤b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩阵线性规划模型及单纯形法

线性规划模型及单纯形法定理3-3-4考虑(LP),条件同上，设x*为极点,存在分解A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],

这里xB=B-1b≥0,xN=0，相应cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,则

x*--opt.2）若

cj-cBT

B-1pj>0,且B-1pj≤0,则(LP)无有界解.线性规划的单纯形法表格单纯形法1、原理及算法过程

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,xRn

b

Rm

A

mn

矩阵，秩（A）=m

线性规划的单纯形法

单纯形法原理及算法过程算法过程(考虑一般步,k=0,1,2,…)设x(k)

为极点,对应分解A=[B,N]，使

xT=[xBT,xNT],这里xB=B-1b>0,xN=0，相应cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,则x(k)–opt，停；

2）否则，存在

cj-cBT

B-1pj>0,a）若B-1pj≤0,则(LP)无有界解，停；

b）若存在

(B-1pj)i>0,

取α=min{(B-1b)i/(B-1pj)i

|(B-1pj)i

>0}=(B-1b)r/(B-1pj)r>0线性规划的单纯形法

单纯形法原理及算法过程得到x(k+1)=x(k)+αd是极点其中,dT=[dBT,dNT

],这里j

dB=-B-1pj,dN=(0,...,1,…,0)T有,cTx(k+1)=cTx(k)+αcTd

=cTx(k)+α(cj-cBTB-1pj)

>cTx(k)

所以，x(k+1)

比

x(k)好重复这个过程，直到停机。单纯形法基本步骤

单纯形法基本步骤

线性规划的单纯形法

表格单纯形法2、单纯形表：设x

为初始极点,相应分解A=[B,N]fxBTxNTRHS目标行1cBTcNT01行约束行0BNbM行1列m列n-m列1列作变换，使前m+1列对应的m+1阶矩阵变为单位矩阵。相当于该表左乘

1cBT-11-cBTB-1

0B

0B-1

=

线性规划的单纯形法

表格单纯形法得到：检验数fxBTxNTRHS目标行10TcNT-cBTB-1NcBTB-1

b1行

xB0IB-1NB-1bM行1列m列n-m列1列为了计算方便，我们对规范形式建立如下单纯形表：（注：引入了m个松弛变量）线性规划的单纯形法表格单纯形法考虑：bi

>0i=1,…,m

Maxz=c1x1+c2

x2+…+cnxn

s.t.a11

x1+a12

x2+…+a1n

xn

≤b1

a21

x1+a22

x2+…+a2n

xn

≤b2…………

am1

x1+am2

x2+…+amn

xn

≤bm

x1，x2，…，xn≥0线性规划的单纯形法加入松弛变量：

Maxz=c1

x1+c2

x2+…+cnxn

s.t.a11

x1+a12

x2+…+a1n

xn

+xn+1=b1

a21

x1+a22

x2+…+a2n

xn

+xn+2=b2…………

am1

x1+am2

x2+…+amn

xn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0显然，xj

=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解,对应的基是单位矩阵。以下是初始单纯形表：

m

m其中：f=-∑cn+ibi

j=cj-∑cn+iaij

为检验数cn+i

=0i=1,…,m

i=1i=1

an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m建立实用单纯形表

利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。

线性规划的单纯形法单纯形法初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY单纯形法的基本过程

例：用单纯形法的基本思路解前例的线性规划问题

Maxz=1500x1+2500x2

s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0线性规划的单纯形法线性规划的单纯形法最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000注意：单纯形法中，

1、每一步运算只能用矩阵初等行变换；

2、表中第3列的数总应保持非负（≥0）；

3、当所有检验数均非正（≤0）时，得到最优单纯形表。线性规划的单纯形法习题*

习题*

习题

3.3.2整数规划整数规划：具有特殊约束条件的线性规划问题。当用通常线性规划的求解方法（单纯形法、图解法）求出非整数解时，不能用简单的“舍入取整”的方法得到整数最优解，必须用整数规划的方法。求解方法：

1.穷举法

2.分枝定界法（要求会解一般线性规划问题）

3.割平面法（要求会解一般线性规划问题）分枝定界法

分枝定界法是一种计算与分析判断相结合的求解整数规划的重要方法。分枝定界法求解整数规划的步骤：（1）松弛：先不考虑整数约束的因素，利用线性规划求解方法（比如图解法、单纯形法）求出不带整数约束的解；（2）分枝：（3）剪枝：对边界值小于可行解的分枝不再考虑，即将这些分枝剪去。例：

背包问题，经典0-1规划问题例：

求解整数规划问题解：先考虑没有整数约束问题（2）s.t.（1）s.t.1）问题（2）的最优解：x1=4.81，x2=1.82，f(x)=356。x1、x2非整数，增加约束条件后再求解；2）在（2）中增加条件：x1≤4后（将相应的问题记为（3）），求得最优解为：x1=4，x2=2.1，f(x)=349。x2非整数，增加约束条件后再求解；3）在（2）中增加条件：x1≥5后（将相应的问题记为（4）），求得最优解为：x1=5，x2=1.57，f(x)=341。x2非整数，增加约束条件后再求解；4）在（2）中增加条件：x1≤4，x2≤2后（将相应的问题记为（5）），求得最优解为：x1=4，x2=2，f(x)=340。是整数解，停止计算；5）在（2）中增加条件：x1≤4，x2≥3后（将相应的问题记为（6）），求得最优解为：x1=10/7，x2=3，f(x)=327。停止计算；6）在（2）中增加条件：x1≥5，x2≤1后（将相应的问题记为（7）），求得最优解为：x1=5.44，x2=1，f(x)=308。停止计算；7）在（2）中增加条件：x1≥5，x2≥2后（将相应的问题记为（8）），无解。停止计算。故原问题的最优解为：x1=4，x2=2，最优值：f(x)=3403.3.3非线性规划如果目标函数或约束条件中存在任何非线性因子，则称为非线性规划。线性规划问题：最优解如果存在，则一定在可行解域的某一顶点达到；解法有单纯形法（一般方法）、图解法、等等；非线性规划问题：最优解不一定在约束区域的边界上达到，可能在约束区域上的某一点上达到。解法较多，无一般方法。一般有解析法和数值法2种：解析法（间接优化法）：先建立数学模型（比较困难），再用数学解析的方法求出数学方程的最优解。数值法（直接搜索法）：不需知道数学模型，在变量的取值上直接搜索，通过少数次试验，寻找其最优解；例：

设平面上有m个点，找覆盖这m个点的最小圆盘。

无约束的非线性规划问题，其解法有：区间消去法、Fibonacci法、最速下降法等；例：

设有n个商店，其位置和对货物的需求都是已知的，货物由m个仓库提供，仓库容量已知。决定这m个仓库建于何处，使仓库提供各商店货物时的运量与里程之积的总和最小。

有约束的非线性规划问题，其解法有：罚函数法、线性逼近法等。非线性规划一般形式：

1、无约束非线性规划

（3-32）

2、有约束非线性规划

（3-33）

（3-34）s.t.相关概念和性质定义1

全局最优解定义2

局部最优解定义3

凸组合定义4

凸函数，严格凸函数，凹函数几何意义（下单峰）定义5

凸规划凸规划的解析解的性质：引理1引理2定理1，2，3定义1全局最优解设f(x)为目标函数，S为可行域，x*S

。若对每一个x都有f(x)≥f(x*),则称x*为极小化问题（3-36）的全局最优解（最小）。定义2局部最优解设f(x)为目标函数，S为可行域，x*S

。若存在x*的一个邻域,使得对该邻域的每一个x都有f(x)≥f(x*)，则称为极小化问题（3-36）的局部最优解（最小）。凸规划是非线性规划中一种重要的特殊情况，具有许多良好的解析性质，可以用解析解法求解。定义6

设f(x)存在一阶偏导数，称列向量为f(x)在点x=[x1

x2…xn]T

处的梯度。定义7

设f(x)存在二阶偏导数，称矩阵为f(x)在点x=[x1

x2…xn]T

处的Hesse矩阵。引理3

局部极小点的一阶必要条件：该点处的梯度为0。引理4

局部极小点的二阶必要条件：该点处的梯度为0，且Hesse矩阵半正定。定理2

局部极小点的二阶充分条件：该点处的梯度为0，且Hesse矩阵正定。定理3

凸规划问题的结论（简单介绍）练习:数值迭代法的基本思想：首先给一个初始解x(0)，然后按某种规则（算法）找出比x(0)

更好的解x(1)

，再按此种规则找出比x(1)更好的解x(2)

，可得到一个解序列{x(k)}

。若这个序列有极限x*

，则极限值就是最优解。数值迭代法的基本步骤：

1）选定初始迭代点

2）确定搜索方向

3）确定步长，产生下一个迭代点

4）检查得到的新点是否满足条件。是，停止迭代；不是，回到2）。无约束非线性规划问题的迭代算法最速下降法（算法3-1）

原理：每次迭代沿最速下降方向（负梯度方向）进行搜索，迈出最优步长，即一步达到该方向的最小点，再以此点为初始点，重复上述步骤，直至得到最优解为止。

广义牛顿法（算法3-2）

原理：用一个二次函数局部地逼近，然后求此近似函数的极小点。共轭梯度法（算法3-3）原理：以共轭方向为搜索方向，将共轭方向与最速下降原理相结合。约束非线性规划问题的迭代算法将迭代序列严格控制在可行域内，从而执行的迭代过程实际上为无约束优化过程；序列无约束优化方法，简称SUMT方法；

罚函数法（外点法）（一般约束）障碍函数（内点法））（不等式约束）在迭代点附近的序列线性化或序列二次函数逼近方法（泰勒展开）线性规划二次规划（目标函数二次，约束条件一次，解法简单，拉格朗日乘子法）最速下降法最速下降法：是应用目标函数的负梯度方向作为每步迭代的搜索方向，在计算时每步都是沿负梯度方向取最优步长，因而此方法也称最优梯度法。最速下降法，只能使得目标函数在开始几步（离目标远时）下降较快。最速下降法只是用一阶梯度的信息以确定下一步搜索方向，优点：算法比较简单；缺点：收敛较慢，且越是接近极限点，收敛越慢。改进的算法：共轭梯度法、变尺度法等。主要介绍最速下降法，它是其它优化方法的基础：梯度：梯度方向：梯度方向的单位向量：梯度的范数：最优梯度：

从一点出发，按如下公式迭代

——称为步长问题：如何选择步长和搜索方向？搜索方向：负梯度方向步长：固定步长？变步长？（变步长）用近似最优步长公式，或用微分法步长：其中H为Hesee矩阵，二阶Hesee矩阵为：例子求函数的最小值解：初值取，则习题*

3.3.4动态规划

50年代初，由美国数学家Bellman提出。将系统运行过程分为若干相继的阶段，而在每个阶段都要做出决策的过程，就叫做多段决策过程。多段决策过程的每一段的结束状态，就是下一段的初始状态。动态规划是研究多段决策而提出来的一种数学方法，它的中心思想是所谓的“最优性原理”，这个原理归结为一个基本递推关系式，从整个过程的终点出发，由后向前，使过程连续地转移，一步一步地推到始点，找到最优解。系统动态最优化习惯称为最优控制，它与系统静态最优化的区别在于其自变量是时间的函数，实质上属于泛函极值的范畴。

一个多阶段决策过程最优化问题的动态规划模型包括以下要素：（1）阶段：对整个系统的自然划分（时间顺序或空间特征），阶段变量一般用k=1,2,…，n表示。（2）状态：表示每个阶段开始时过程所处的自然状况，它应能描述过程的特征并且具有无后效性。状态变量：描述状态的变量，用表示第k阶段的状态变量（离散的或连续的）；变量允许取值的范围称为允许状态集合，用表示第k阶段的状态允许集合。（3）决策：当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策或控制。用表示第k阶段处于状态时的决策变量，用表示的允许决策集合。（4）策略：决策组成的序列。（5）状态转移方程：在确定性过程中，当某阶段的状态和决策已知时，下阶段的状态便完全确定，表示这种演变规律的方程称为状态转移方程，记作：，k=1,2,…，n。（6）指标函数和最优函数：衡量过程优劣的数量指标，是定义在全过程和后部子过程上的数量函数，用，k=1,2,…，n表示。根据状态转移方程，指标函数可以表示为状态和策略的函数，即。在给定时，指标函数对的最优值称为最优函数，记为，即式中，opt可取max或min（7）最优策略和最优轨线：定理4定理5定理6

关键公式：（73）、（74）

3.3.4动态规划3.3.4动态规划3.3.4动态规划3.3.4动态规划3.3.4动态规划3.3.4动态规划3.3.4动态规划2511214106104131112396581052C1C3D1AB1B3B2D2EC2例求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=03.3.4动态规划2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106