系统优化技术PPT课件.ppt

系统工程优化技术,程森林重庆大学自动化学院,1,主要内容,1线性规划2最短路径3层次分析法4主成分分析法5最小二乘6极大似然估计7最早完工时间8决策树9最小部分树,2,1线性规划,某钢筋车间制作一批直径相同的钢筋，需要长度为3米的90根，长度为4米的60根。已知所用的下料钢筋长度为10米，问怎样下料最省，请建立解决此问题的数学模型。解：有三种下料方案，(1)10=33+1，(2)10=32+4，(3)10=42+2，设三种方案分别下了x1、x2、x3根，则有：3x1+2x2=90 x2+2x3=60目标函数：min(x1+x2+x3)约束：x1、x2、x3为大于0的整数,3,1线性规划,一公司饲养动物出售，设每头动物每天至少需700克蛋白质、50克矿物质，现有四种饲料可供选用。各种饲料每千克营养成分及单价如下，要求确定满足动物生产的营养需要，又使费用最省的饲料方案。,4,1线性规划,动物每天至少需700克蛋白质、50克矿物质,动设14种饲料需要的量分别是x1x4千克20 x1+10 x2+2x3+5x4=700(1)(蛋白质条件)3x1+2x2+x3+4x4=50(2)(矿物质条件)目标函数min(c)=2x1+7x2+4x3+5x4约束条件是每种饲料不能为负，即x1x40,5,1线性规划,6,x,y,A,B,C,7,2最短路径,下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,8,Dijkstra算法步骤：,第二步：考虑满足条件的所有点；vi具有P标号;vj具有T标号;修改vj的T标号为，并将结果仍记为T(vj),第一步：始点标上固定标号,其余各点标临时性标号T(vj)=,j1;,第三步：若网络图中已无T标号点，停止计算。否则,令，s为T标号点集,然后将的T标号改成P标号，转入第二步。,9,v1,6,图上标号法,0,0,M,M,v1,3,M,M,M,v1,1,v1,1,永久标号,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,10,v1,6,图上标号法,0,0,M,M,v1,3,M,M,M,0,0,v1,1,v4,11,v1,3,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,11,0,0,M,v1,1,M,M,M,1,3,图上标号法,v4,11,v1,3,v1,6,v3,5,v3,5,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,12,0,0,M,v4,11,v1,1,M,M,M,v1,3,图上标号法,v3,5,v2,6,v2,6,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,13,0,0,M,v4,11,v1,1,M,M,v1,3,v5,12,v5,9,v5,9,图上标号法,v3,5,v2,6,永久标号,临时标号,v5,10,v1出发到v8去，使总费用最小的旅行路线,14,0,0,v5,10,v1,1,M,v5,12,v1,3,v5,9,v5,12,v3,5,v2,6,图上标号法,永久标号,临时标号,v5,10,v1出发到v8去，使总费用最小的旅行路线,15,0,0,v5,10,v1,1,M,v1,3,v5,12,v3,5,v2,6,图上标号法,v5,9,永久标号,临时标号,标号结束反向追踪,v1出发到v8去，使总费用最小的旅行路线,16,3层次分析法,日常生活中有许多的决策问题，在面临多种方案时需要依据一定的标准选择某一种方案。买饭如何依据色、香、味、价格等方面的因素选择某种饭菜？旅游是去金刀峡，还是去峨眉山，或者是去张家界？一般会依据景色、费用、食宿条件、旅途等因素选择去哪个地方。择业毕业时，可能有高校、科研单位、企业等单位可以去选择，一般依据工作环境、工资待遇、发展前途、住房条件等因素择业。面对各种各样的方案，要进行比较、判断、评价、最后作出决策。这个过程主观因素占有相当的比重，给用数学方法解决问题带来不便！,17,3层次分析法,基本原理如果知道n个西瓜的重量为，这些西瓜两两比较（相除），可以得到表示n个西瓜相对重量关系的比较矩阵（判断矩阵）。,18,3层次分析法,基本原理由于AWW，对应A矩阵的特征根，W对应A矩阵的特征向量。在比较矩阵中AWnW，n是A矩阵的一个特征根，W对应特征根为n时的特征向量，W代表每个西瓜重量，此时n代表西瓜的个数或矩阵的阶数。假如不知道每个西瓜的重量W，但通过某种手段，设法知道每两个西瓜的相对比较重量，即构造出判断矩阵A，因为A矩阵满足完全一致性要求时，或具有较满意的一致性要求时，maxn，其余特征根接近于零。对于复杂的社会、经济、技术等评价与决策问题，利用上述反命题的设想，根据评价或决策的总目标和影响因素，构造出各影响因素的比较矩阵，并按照一定原则排序，可求出各自（方案、过程）的权重，为决策者提供决策依据。,19,3层次分析法,实施步骤(1)分析系统要素间的关系，建立系统的递阶层次结构；(2)相同层次各元素针对上一层次中某一准则的重要性进行两两比较，构造两两比较判断矩阵，(3)进行一致性检验；(4)由判断矩阵计算被比较要素针对上一级准则的相对权重；(5)计算各层准则要素（指标）对系统目的(总目标)的合成(总)权重，并对各方案进行排序。,20,3层次分析法,实施步骤(1)建立层次结构模型根据对问题的了解和初步分析，将评价系统涉及的各要素按性质分层排列。对于一般的系统，层次分析法模型的层次结构大体分为三层。,21,3层次分析法,实施步骤(1)建立层次结构模型最高层是目标层在这一层中是系统所要达到的总目标，是系统评价的最高准则，是分析问题的预定目标或期望实现的理想结果。通常只有一个目标，一般是分析问题的预定目标或理想结果。如有多个分目标时，可以在此目标层下面再建立一个分目标层。中间层是准则层列出实现总目标所要采取的各项准则，包括了为实现目标所涉及的中间环节，可有若干个层次组成。包括所需考虑的准则、子准则等。最低层是方案层列出可供选择的各种可替代方案，是评价方案的具体化。,22,3层次分析法,实施步骤(1)建立层次结构模型注意：A、层次之间元素的支配关系不一定是一一对应的，即可以存在这样的元素，它并不支配下一层次的所有元素。若上层的每个因素都支配着下一层的所有因素，称为完全层次结构，否则称为不完全层次结构。B、层次数与问题的复杂程度和所需要分析的详尽程度有关。每一层次中的元素一般不超过9个，否则会给两两比较判断带来困难。C、一个好的层次结构对于解决问题是极为重要的。如果在层次的划分和确定层次之间的支配关系上举棋不定，最好重新分析问题，弄清问题各部分相互之间的关系，以确保建立一个合理的层次结构。层次分析法所要解决的问题是关于最低层对最高层的相对权重问题，按此相对权重可以对最低层中的各种方案、措施进行排序，从而在不同的方案中作出选择或形成选择方案的原则。,23,3层次分析法,实施步骤(2)建立各阶层的判断矩阵判断矩阵是AHP的基本信息，也是进行层次单排序的依据。构造判断矩阵是人们给出每一层次各要素之间的相对重要性。判断矩阵是以上一级要素作为评价准则，对本级（同一层次）的各元素的重要性进行两两比较，来确定矩阵元素。即针对上一层次某元素，本层次有关元素之间的相对重要性。,24,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,为了使判断定量化，设法使任意两个方案对于某一准则的相对优越程度得到定量描述。一般对单一准则，两个方案进行比较总能判断出优势。层次分析法多用1-9标度方法（选择1-9之间的整数及其倒数作为取值的主要原因是符合人们进行比较判断时的心理习惯）。,25,3层次分析法,实施步骤(2)建立各阶层的判断矩阵判断矩阵A=(aij)aij要素i与要素j相比的重要性标度aij的确定一般根据资料统计，由专家和分析者一起根据经验反复讨论后，凭定性分析的直觉和判断而定。即运用量化标度将思维判断数量化。显然有：0aij9aii=1aji=1/aij在特殊情况下，判断矩阵A的元素具有传递性，即满足aik.akj=aij若该式对判断矩阵A所有元素均成立，则称A为一致性矩阵。,26,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,27,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,28,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,29,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,30,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,31,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,32,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,33,3层次分析法,实施步骤(2)建立各阶层的判断矩阵,34,3层次分析法,实施步骤(3)进行一致性检验一致性判断一般地，由于客观事物的复杂性与人的认识的多样性和片面性，我们并不要求判断判断矩阵是否严格地具有这种传递性和一致性。但是，在构造两两判断矩阵时，要求判断大体上的一致是必要的，以防止人们的思维出现矛盾。出现甲比乙极端重要，乙比丙极端重要，而丙又比甲极端重要的判断，这显然是违反常识的。所以，一个混乱的经不起推敲的判断矩阵很有可能导致决策的失误，如果当判断矩阵过于偏离一致性时，以上述方法计算的排序权重作为决策依据，其可靠程度就很值得怀疑。因此，必须对判断矩阵进行一致性检验。,35,3层次分析法,实施步骤(3)进行一致性检验一致性检验需要引入的四个参数：判断矩阵A的最大特征根max、一致性指标(C.I.)、平均随机一致性指标(R.I.)、一致性比例(C.R.),36,3层次分析法,实施步骤(3)进行一致性检验2）查找相应的R.I.,37,3层次分析法,实施步骤(3)进行一致性检验3）计算C.R.,38,3层次分析法,实施步骤(3)进行一致性检验,39,3层次分析法,实施步骤(4)求各准则(方案)的总重要度(指标满足程度)根据各层次的相对总要度的计算结果，计算各评价准则综合权重及不同方案在该综合评价准则下的评价结果。,40,3层次分析法,特点层次分析法特别适用于在人的定性判断可以起到重要作用，却又难以进行精确量化的情况下，进行多准则、多目标的分析评价，将方案措施层的层次总排序结果作为方案优选的依据。,41,3层次分析法,不足(1)将定量指标主观化处理，仿照定性指标建立判断矩阵。(2)判断矩阵的建立本身会因人而异，针对某一个准则，只建立一个判断矩阵，所以难以综合各位评价人员的意见，随意性强。(3)AHP的结果只是方案的优劣顺序，不能回答方案是否可行。(4)由心理学家试验可知，人们只能对72个事物同时进行比较。对于因素众多、规模较大的复杂系统（如要素大于9），采用AHP进行评价，容易出现问题。实际应用中，一般用AHP法解决评价指标的权重确定。,42,产生背景大规模复杂系统的变量多、且多数相关，增加分析问题的难度与复杂性能否用较少的新变量代替原来较多的旧变量，且尽可能多地保留原来变量所反映的信息？主成分分析方法就是综合处理这种问题的一种强有力的工具：把原来多个变量划为少数几个综合指标,4主成分分析,43,问题本质主成分分析是把各变量之间互相关联的复杂关系进行简化分析的方法。主成分分析试图在力保数据信息丢失最少的原则下，对多变量的数据进行最佳综合简化，也就是说，对高维变量空间进行降维处理。,4主成分分析,44,例子说明成绩的评估可以用下面的综合成绩来体现：a1数学a2语文a3英语a4体育确定权重系数的过程就可以看作是主成分分析的过程，得到的加权成绩总和就相对于新的综合变量主成分当某一问题需要同时考虑好几个因素时，我们并不对这些因素个别处理而是将它们综合起来处理，这就是主成分分析,4主成分分析,45,基本思想如果用x1,x2,xn表示n门课程，a1,a2,an表示各门课程的权重，且满足加权为：s=a1x1+a2x2+anxnm个学生对应了m个综合成绩为s1,s2,sm我们希望选择适当的权重能更好地区分学生的成绩如果这些值很分散，表明区分得好。,4主成分分析,46,基本思想方差反映了随机变量取值的分散程度。我们把方差最大那一组系数与课程成绩的内积所构成的向量Z1=a1X称为第一主成分如果第一主成分所含信息不够多，还不足以代表原始的n个变量，则需考虑再使用一个综合变量Z2=a2X,且满足：使Z2方差达到最大。则Z2为第二主成分,4主成分分析,47,优点主成分分析法通过研究指标体系的内在结构关系，从而将多个指标转化为少数几个相互独立且包含原来指标大部分信息（80%或85%以上）的综合指标。确定的权数是基于数据分析而得出的指标之间的内在结构关系，不受主观因素的影响，有较好的客观性。得出的综合指标（主成分）之间相互独立，减少信息的交叉，这对分析评价极为有利。,4主成分分析,48,步骤设n个随机变量取得的一组（m个）样本为：,4主成分分析,49,步骤（1）对样本进行标准化处理,4主成分分析,50,步骤（2）计算样本协方差矩阵（样本相关系数矩阵）协方差数据矩阵的每一列对应一个变量的m个量测值，任意两列之间可以计算两变量间的协方差,4主成分分析,51,步骤当分析中所选择的变量具有不同的量纲，变量水平差异很大，应该计算样本相关系数（选择基于相关系数矩阵的主成分分析）,4主成分分析,52,步骤（3）计算特征值和特征向量,4主成分分析,53,步骤（4）计算各主成分利用所得单位化特征向量，构造一个正交矩阵a,4主成分分析,54,步骤对于m个样本中的第k个样本，由Zi=aiX，可得到n个主成分,4主成分分析,55,主成分选择贡献率若i为协方差矩阵的第i个特征根，则有：为第i个主成分的贡献率，反映了原来n个指标多大的信息，有多大的综合能力。累积贡献率表示前k个主成分共有多大的综合能力，第k个主成分的累积贡献率为：,4主成分分析,56,主成分的选择主成分分析的目的之一是希望用尽可能少的主成分Z1，Z2，Zp（pn）代替原来的n个指标。应该选择多少个主成分？在实际工作中，主成分个数的多少取决于能够反映原来变量80%以上的信息量为依据，即当累积贡献率80%时的主成分的个数就足够了。,4主成分分析,57,例子,4主成分分析,58,4主成分分析,例子,59,4主成分分析,例子,60,例子,4主成分分析,61,4主成分分析,例子,62,例子,4主成分分析,63,4主成分分析,64,5最小二乘,例子无线定位时，用n个锚节点为(xi,yi)(i=1,2,n)到未知的距离di节点节点(x,y)。没有干扰时：di2=(xi-x)2+(yi-y)2有干扰时：di2+ei2=(xi-x)2+(yi-y)2每个锚节点到未知节点的干扰各不相同，体现出来的误差也不同。最小二乘就是希望确定出来的误差的平方和取极小值,65,5最小二乘,通用示例x,y具有关系y=f(x)，因为干扰的原因，n个x对应的y都存在干扰，即：yi=f(xi)+ei最小二乘即要求minei2=yi-f(xi)2y=f(x)=ax+b为时，称为线性回归minei2=yi-axi-b2对a、b参数求偏导可得其估计值,66,5最小二乘,通用示例f(xi)=f(j,xi)，其中j为函数参数，不是所有的函数都能通过偏导求解的。di2=(xi-x)2+(yi-y)2+ei2变换一下,67,6极大似然估计,原理一个随机试验如有若干个可能的结果A，B，C，。若在仅仅作一次试验中，结果A出现，则一般认为试验条件对A出现有利，也即A出现的概率很大。一般地，事件A发生的概率与参数相关，A发生的概率记为P(A，)，则的估计应该使上述概率达到最大，这样的顾名思义称为极大似然估计。,68,6极大似然估计,原理,69,6极大似然估计,步骤,70,6极大似然估计,71,6极大似然估计,72,6极大似然估计,73,6极大似然估计,74,7最早完工时间,网络计划原理把所要做的工作，哪项工作先做，哪项工作后做，各占用多少时间，以及各项工作之间的相互关系等运用网络图的形式表达出来；通过简单的计算，找出哪些工作是关键的，哪些工作不是关键的，并在原来计划方案的基础上，进行计划的优化。组织计划的实施，并且根据变化了的情况，搜集有关资料，对计划及时进行调整，重新计算和优化，以保证计划执行过程中自始至终能够最合理地使用人力、物力，保证多块好省地完成任务。,75,7最早完工时间,绘图符号和术语(1)工作（活动、工序、作业）任何一项计划，都包含许多项待完成的工作。在网络图中，工作用箭线(弧)表示。箭尾表示工作的开始，箭头表示工作的完成。箭头的方向表示工作的前进方向（从左向右）。工作的名称或内容写在箭线的上面，持续时间写在箭线的下面。,双代号网络计划图,76,7最早完工时间,绘图符号和术语（2）节点节点表示工作之间的联结。在时间上它表示指向某节点的工作全部完成后，该节点后面的工作才能开始。节点用圆圈表示，圆圈中编上整数号码。对于某项工作来说，紧接在其箭尾节点前面的工作，是其紧前工作，紧接在其箭头节点后面的工作是其紧后工作；和它同时进行的工作称为平行工作。（3）虚工作虚工作仅仅表示工作之间的先后顺序，用虚线箭线表示，它的持续时间0。,77,7最早完工时间,网络图表达方式（1）工作a结束后才可以开始b和c。,78,7最早完工时间,网络图表达方式（2）工作c在a和b均结束后才能开始。,79,7最早完工时间,网络图表达方式（3）a和b两作工序均结束后才可以开始c和d。,80,7最早完工时间,网络图表达方式（4）工作c在a结束后即可进行，但工作d必须同时在a和b结束后才能开始。,81,7最早完工时间,网络图表达方式,A、B都完成DB、C都完成E,A完成CB完成EA、B都完成D,82,7最早完工时间,网络图表达方式1）P的紧前工作为A、BF的紧前工作为B、CG的紧前工作为C、D2）P的紧前工作为A、BF的紧前工作为B、C、DG的紧前工作为C、D,83,7最早完工时间,绘图规则（1）起点和终点为了表示工程的开始和结束，网络图只能有一个起点和一个终点。（2）方向与节点网络图是有向图，按照工艺流程的顺序，规定工作从左向右排列。（3）虚工作虚工作，用虚线箭线表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作间的先后次序关系。,84,7最早完工时间,绘图规则（4）两个节点之间不能有两道或两道以上的工作。即两个节点只能表示一道工序，否则将造成逻辑上的混乱。,85,7最早完工时间,绘图规则（5）网络图中不能有缺口和回路。有缺口，将使某些工作失去与其紧前或紧后工作应有的联系；有回路，将使组成回路的工作永远不能结束，工程永远不能完工。,86,7最早完工时间,绘图规则(6)平行作业为缩短工程的完工时间，在条件允许的情况下，某些工作可以同时进行，即可采用平行作业的方式。如下图中的工作b,c,d。,87,7最早完工时间,绘图规则（7）交叉作业对需要较长时间才能完成的一些工作，在工艺流程与生产组织条件允许的情况下，可以不必等待该工作全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程的完工时间。如工作A与工作B分别为挖沟和埋水管，可以挖一段埋一段，不必等沟全部挖好后再埋。这种关系可以用交叉作业来表示，如果把这两项工作各分为三段，则A=a1+a2+a3，B=b1+b2+b3，如下图所示。,88,7最早完工时间,实例例1某项建筑工程的部分工作与所需时间以及它们之间的关系如下表所示。,89,7最早完工时间,实例步骤1、2可用上表表示。根据表所示的工作及它们之间的关系可作出网络图。,90,7最早完工时间,实例例2某项研制新产品工程的各个工作与所需时间及它们之间的相互关系见下表。作出该项工程的网络计划图。,91,7最早完工时间,实例,网络图中的虚工作表示在D工作结束后H工作才能开始。,92,7最早完工时间,画出下列表对应的网络计划图,93,7最早完工时间,定义：在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条路称为路线。而这样的路线往往有多条，称其中时间最长的路线为关键路线（CP），关键路线上的工作称为关键工作。整个工程所需的最短时间就等于关键路线所需的时间，因此关键工序完工时间的提前或拖延就直接影响了整个工程的完工时间。,94,7最早完工时间,最早可能开始时间,最迟必须完成时间,最早可能完成时间,最迟必须开始时间,95,7最早完工时间,1）最早可能开始时间：ESi-j2）最早可能完成时间：EFi-j3）最迟必须开始时间：LSi-j4）最迟必须完成时间：LFi-j5）总时差：TFi-j6）自由时差：FFi-j,j,j,i,i,96,7最早完工时间,（1）、工作最早开始时间ES和工作最早完成时间EF由于任一工作只能在其所有的紧前工作结束之后开始，如果某项工作有多项紧前工作，则只有在这些紧前工作都完成后，本项工作才能开始。因此本项工作的最早开始时间是：ES=max（紧前工作的EF）。其中，EF=ES+工作持续时间D。表示为：ESi-j=maxh(EFh-j)=maxh(ESh-j+Dh-j)任一工作的最早开始时间等于其所有的紧前工作最早完成时间中的最大值。,97,7最早完工时间,例：,0,0,5,2,2,2,4,4,5,5,11,10,11,11,11,16,11,14,Tc=16,98,7最早完工时间,(2)、工作最迟开始时间LS和工作最迟完成时间LF最迟完成时间的计算从网络的终点开始，从右向左反向进行。网络图中最后一项工作(i-j)(j=n)的最迟完成时间应由工程的计划工期确定。如果没有给定，则可以令其等于最早完成时间，即LFi-n=EFi-n。若EFi-n的结果已经出来了，并且应当小于或等于计划工期规定的时间Tr。最迟开始时间是它的最迟完成时间减去该工作的持续时间之差。LS=LF-工作持续时间D,99,7最早完工时间,例：,16,16,11,13,13,13,8,13,11,11,5,9,5,5,0,3,3,1,100,7最早完工时间,(3)、工作时差工作时差是指工作有机动时间。常用的有两种时差：工作总时差和工作自由时差。（A）工作总时差TFi-jTFi-j是指在不影响工期的前提下，工作所具有的机动时间，按工作计算法计算。,注意：工作总时差往往为若干项工作共同拥有的机动时间。,101,7最早完工时间,（B）工作自由时差FF工作自由时差是指：在不影响其紧后工作最早开始的前提下，工作所具有的机动时间。工作自由时差是某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响。,102,例：,0,0,1,7,0,1,0,0,2,7最早完工时间,FFi-j=ESj-k-EFi-j,103,7最早完工时间,例2的计算结果。,104,7最早完工时间,关键路线的特征：在线路上从起点到终点都是由关键工作组成。在确定型网络计划中是指线路中工作总持续时间最长的线路。在关键线路上无机动时间，工作的总时差为零。在非确定网络计划中是指估计工期完成可能性最小的线路。,105,8决策树,用决策树表示决策问题有形象化、直观的特点。矩形表示决策点从矩形引出的线段表示方案用圆圈表示机会点从圆圈引出的直线和折线表示概率分支菱形表示方案费用把概率和相应的结果（或效用值）放在概率分支上和概率分支的右端上。,106,8决策树,有一钻探队做石油钻探，可以先做地震试验，费用为0.3万元/次，然后决定钻井与否，钻井费用为1万元，出油收入为4万元。根据历史资料，试验结果好的概率为0.6，不好的概率为0.4；结果好钻井出油的概率为0.85，不出油的概率为0.15；结果不好钻井出油的概率为0.1，不出油的概率为0.9。也可不做试验而直接凭经验决定是否钻井，这时出油的概率为0.55，不出油的概率为0.45，试用决策树进行决策。有几个决策点？有几个机会点？,107,8决策树,108,8决策树,3.4,0.4,2.2,2.4,0,1.2,|,|,|,1.44,|,1.2,109,8决策树,某企业对产品生产工艺进行改进，提出两个方案：一是从国外引进生产线，另一是自行设计生产线。引进投资较大，但产品质量好成本低，成功率为80%；自行设计投资相对较小，