1、数学建模培训系列讲座 最优化与离散模型 主讲: 刘 弦 (计算机系),数学建模：最优化问题,最优化问题大体分两类：,一类是求函数在一定约束条件下的极值; 另一类是求泛函的极值.,这里的函数我们称之为目标函数.目标函数中的变量称之为决策变量.约束条件是指问题对决策变量的限制条件,即决策变量的取值范围. 约束条件常用一组关于决策变量的等式与不等式给出.,如果目标函数有明显的表达式,一般可用微分法,变分法或动态规划等分析方法来求解(间接求优); 如果目标函数的表达式过于复杂甚至根本没有明显的表达式,则可用数值方法或“试验最优化”方法等直接方法来求解(直接求优).,求函数极值的数值方法或试验化方法有时
2、称为数学规划.,数学规划除了线性规划外统称为非线性规划.,求解数学规划的软件: LINDO, LINGO,LINDO(Linear INteractive and Discrete Optimizer)交互式的线性和离散优化求解器 LINGO(Linear INteractive and General Optimizer)交互式的线性和通用优化求解器,模型实例:存贮模型,问 题,配件厂为装配线生产若干种产品，轮换产品时因更换设 备要付生产准备费，产量大于需求时要付贮存费。该厂 生产能力非常大，即所需数量可在很短时间内产出。,已知某产品日需求量100件，生产准备费5000元，贮存费 每日每件1
3、元。试安排该产品的生产计划，即多少天生产 一次（生产周期），每次产量多少，使总费用最小。,要求,不只是回答问题，而且要建立生产周期、产量与 需求量、准备费、贮存费之间的关系。,第一讲 简单的优化模型,问题分析与思考,每天生产一次，每次100件，无贮存费，准备费5000元。,日需求100件，准备费5000元，贮存费每日每件1元。,10天生产一次，每次1000件，贮存费900+800+100 =4500元，准备费5000元，总计9500元。,20天生产一次，每次2000件，贮存费2900+2800+100 =28500元，准备费5000元，总计33500元。,平均每天费用950元,平均每天费用16
4、75元,平均每天费用5000元,周期短，产量小,周期长，产量大,这是一个优化问题，关键在建立目标函数。,显然不能用一个周期的总费用作为目标函数,目标函数每天总费用的平均值,模 型 假 设,1. 产品每天的需求量为常数 r；,2. 每次生产准备费为 c1, 每天每件产品贮存费为 c2；,3. T天生产一次（周期）, 每次生产Q件，当贮存量为零时，Q件产品立即到来（生产时间不计）；,建 模 目 的,设 r, c1, c2 已知，求T, Q 使每天总费用的平均值最小。,4. 为方便起见，时间和产量都作为连续量处理。,模 型 建 立,贮存量表示为时间的函数 q(t),t=0生产Q件，q(0)=Q, q
5、(t)以 需求速率r递减，q(T)=0.,一周期 总费用,每天总费用平均值 （目标函数）,离散问题连续化,一周期贮存费为,A=QT/2,模型求解,求 T 使,模型分析,模型应用,c1=5000, c2=1，r=100,回答问题,经济批量订货公式（EOQ公式）,每天需求量 r，每次订货费 c1,每天每件贮存费 c2 ，,这就是经济学中著名的用于订货、供应、存贮情形的,以上讨论的是不允许缺货的存贮模型,问：为什么不考虑生产费用？在什么条件下才不考虑？,T天订货一次(周期), 每次订货Q件，当贮存量 降到零时，Q件立即到货。,总结,则最优解为:,允许缺货的存贮模型,A,B,当贮存量降到零时仍有需求r
6、, 出现缺货，造成损失,原模型假设：贮存量降到零时Q件立即生产出来(或立即到货),现假设：允许缺货, 每天每件缺货损失费 c3 , 缺货需补足,一周期贮存费,一周期缺货费,周期T, t=T1贮存量降到零,一周期总费用,每天总费用 平均值 （目标函数）,一周期总费用,求 T ,Q 使,为与不允许缺货的存贮模型相比，T记作T , Q记作Q,允许缺货模型,注意：缺货需补足,Q每周期初的存贮量,每周期的生产量R （或订货量）,Q不允许缺货时的产量(或订货量),不允许缺货模型,记,允许缺货模型,下面将进入数学规划模型,数学规划模型,实际问题中 的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条
7、件,多元函数条件极值,决策变量个数n和 约束条件个数m较大,最优解在可行域 的边界上取得,数学规划,线性规划 非线性规划 整数规划,重点在模型的建立和结果的分析,第二讲 数学规划模型,企业生产计划,2.1 奶制品的生产与销售,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。,例1 加工奶制品的生产计划,问题:,一奶制品加工厂用牛奶生产A1,A2两种奶制品,1
8、桶牛奶,可以在设备甲上用12小时加工成3公斤A1, 或者地设备乙上加工成4公斤A2. 根据市场需求,生产的A1,A2全部能售出, 且每公斤A1获利24元,每公斤A2获利16元. 现在加工厂每天能得到50桶牛奶的供应, 每天正式工人总的劳动时间为480小时, 并且设备甲每天最多能加工100公斤A1,设备乙的加工能力没有限制.试为该厂制定一个生产计划, 使每天获利最大, 并进一步讨论以下3个附加问题:1) 若用35元可以买到一桶牛奶, 应否作这项投资?若投资,每天最多能购买多少桶牛奶?2) 若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元?3) 由于市场需求变化,每公斤A1的获
9、利增加到30元,应否改变生产计划?,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成
10、正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c (常数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形
11、的某个极点取得。,模型求解,软件实现,LINDO 6.1,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2,D
12、O RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生产A1, 30桶生产A2，利润3360元。,结果解释,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力
13、剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERAT
14、IONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.00000
15、0 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为
16、303=90，在允许范围内,不变！,(约束条件不变),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 50.000000 10
17、.000000 6.6666673 480.000000 53.333332 80.0000004 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),问题:,例1给出的生产条件,利润,资源均不变.为增加赢利, 对A1,和A2进行深加工.用2小时和3元加工费可将A1加工成0.8公斤B1,也可将1公斤A2加工成0.75公斤B2 . 每公斤B1获利44元, 每公斤B2获利32元. 试为该厂制定一个生产计划, 使每天获利最大, 并讨论以下问题:
18、1) 若用30元可以买到一桶牛奶, 投资3元可增加1小时劳动时间, 应否作这项投资? 若每天投资150元,可赚回多少?2)每公斤B1,B2获利经常有10%的波动,对制定的计划有无影响? 若每公斤B1获利下降10%,计划应变化吗?,例2 奶制品的生产销售计划,在例1基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶, 480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,出售x1 千克 A1, x2 千克 A2，,X3千克 B1, x4千克 B2,原料供应,劳动时间,加工能力
19、,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1， x6千克 A2加工B2,附加约束,模型求解,软件实现,LINDO 6.1,MAX 24x1+16x2 + 44x3 +32x4-3x5-3x6st 2) 4x1+3x2+4x5+3x6600 3) 4x1+2x2+6x5+4x6480 4) x1+x5100 5) x3-0.8x5=0 6) x4-0.75x6=0 end,OBJECTIVE FUNCTION VALUE1) 3460.800VARIABLE VALUE REDUCED COSTX1 0.000000 1.680000X2 168.000000 0.00
20、0000X3 19.200001 0.000000X4 0.000000 0.000000X5 24.000000 0.000000X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 3.1600003) 0.000000 3.2600004) 76.000000 0.0000005) 0.000000 44.0000006) 0.000000 32.000000NO. ITERATIONS= 2,MAX 24x1+16x2 + 44x3 +32x4-3x5-3x6st 2) 4x1+3x2+4x5+3x6600 3
21、) 4x1+2x2+6x5+4x6480 4) x1+x5100 5) x3-0.8x5=0 6) x4-0.75x6=0 end,OBJECTIVE FUNCTION VALUE1) 3460.800VARIABLE VALUE REDUCED COSTX1 0.000000 1.680000X2 168.000000 0.000000X3 19.200001 0.000000X4 0.000000 0.000000X5 24.000000 0.000000X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 3.1
22、600003) 0.000000 3.2600004) 76.000000 0.0000005) 0.000000 44.0000006) 0.000000 32.000000NO. ITERATIONS= 2,结果解释,每天销售168 千克A2和19.2 千克B1， 利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2， 将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE1) 3460.800VARIABLE VALUE REDUCED COSTX1 0.000000 1.680000X2 168.000000
23、0.000000X3 19.200001 0.000000X4 0.000000 0.000000X5 24.000000 0.000000X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 3.1600003) 0.000000 3.2600004) 76.000000 0.0000005) 0.000000 44.0000006) 0.000000 32.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资15
24、0元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 24.000000 1.680000 INFINITYX2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000
25、 2.026667 INFINITYX5 -3.000000 15.800000 2.533334X6 -3.000000 1.520000 INFINITY ,B1获利下降10%，超出X3 系数允许范围,B2获利上升10%，超出X4 系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6 计算，会发现结果有很大变化。,2.1 饮料厂的生产与检修,问题:,某饮料厂确定了未来四周对该饮料的需求量,以及未来,四周本厂的生产能力和生产成本(如下表所示).每周满足需求后,有剩余时,要支出存贮费,为每周每千箱0.2千元.问应如何安排生产,在满足市场需求的条件下,使四周总费用最小?
26、,单阶段生产计划,多阶段生产计划,企业生产计划,问题分析,除第4周外每周的生产能力超过每周的需求；生产成本逐周上升； 前几周应多生产一些。,饮料厂在第1周开始时没有库存； 从费用最小考虑, 第4周末不能有库存； 周末有库存时需支出一周的存贮费； 每周末的库存量等于下周初的库存量。,模型假设,目标函数,约束条件,产量、库存与需求平衡,决策变量,能力限制,非负限制,模型建立,x1 x4：第14周的生产量,y1 y3：第13周末库存量,存贮费:0.2 (千元/周千箱),模型求解,4周生产计划的总费用为528 (千元),最优解： x1 x4：15，40，25，20；y1 y3： 0，15，5 .,LI
27、NDO求解,检修计划,0-1变量wt ：wt=1 检修安排在第t周(t=1,2,3,4）,在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?,检修安排在任一周均可:,能力限制,产量、库存与需求平衡约束条件不变,增加检修约束条件：,目标函数不变,LINDO求解,总费用由528千元降为527千元,检修所导致的生产能力提高的作用, 需要更长的时间才能得到充分体现。,最优解： w1=1, w2 , w3, w4=0;x1 x4：15,45,15,25；y1 y3：0,20,0 .,min 5.0x1+5.1x2+5.4x3+5.5x4+0.2y1+0.2y
28、2+0.2y3 st 2)x1-y1=15 3)x2+y1-y2=25 4)x3+y2-y3=35 5)x4+y3=25 6)x1+15w130 x2+15w2-5w140 x3+15w3-5w1-5w245 x4+15w4-5w1-5w2-5w320 w1+w2+w3+w4=1 end int w1 int w2 int w3 int w4,例2 饮料的生产批量问题,安排生产计划, 满足每周的需求, 使4周总费用最小。,存贮费:每周每千箱饮料 0.2千元。,饮料厂使用同一条生产线轮流生产多种饮料。 若某周开工生产某种饮料, 需支出生产准备费8千元。,某种饮料4周的需求量、生产能力和成本,问题
29、:,生产批量问题,考虑与产量无关的固定费用,给优化模型求解带来新的困难,Min 8w1+8w2+8w3+8w4+5x1 +5.1x2 +5.4x3+5.5x4+0.2y1+0.2y2+0.2y3 st 2) x1-y1=15 3) y1+x2-y2=25 4) y2+x3-y3=35 5) y3+x4=25 6) x1-30w10 7) x2-40w20 8) x3-45w30 9) x4-20w40 end int w1 int w2 int w3 int w4,最优解：x1 x4：15，40，45，0；总费用：554.0(千元),用LINDO求解,决策变量,x1 x4：第14周的生产量,y
30、1 y3：第13周末库存量,0-1变量wt ：wt=1 第t周开工生产(t=1,2,3,4）,生产批量问题的一般提法,ct 时段t 生产费用(元/件)； ht 时段t (末)库存费(元/件)； st 时段t 生产准备费(元)； dt 时段t 市场需求(件)； Mt 时段t 生产能力(件)。,假设初始库存为0,制订生产计划, 满足需求,并使T个时段的总费用最小。,决策变量,xt 时段t 生产量； yt 时段t (末)库存量； wt =1 时段t 开工生产 (wt =0 不开工)。,目标,约束,混合0-1规划模型,生产批量问题的一般提法,下面将进入离散模型,离散模型：差分方程、整数规划、图论、对策
31、论、网络流、 ,分析社会经济系统的有力工具,只用到代数、集合及图论（少许）的知识,第三讲 离散模型,3.1 层次分析模型,背景,日常工作、生活中的决策问题,涉及经济、社会等方面的因素,作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化,Saaty于1970年代提出层次分析法 AHP (Analytic Hierarchy Process),AHP一种定性与定量相结合的、系统化、层次化的分析方法,目标层,O(选择旅游地),准则层,方案层,一. 层次分析法的基本步骤,例. 选择旅游地,如何在3个目的地中按照景色、费用、居住条件等因素选择.,“选择旅游地”思维过程的归纳,将决策问题分为3
32、个层次：目标层O，准则层C，方案层P；每层有若干元素， 各层元素间的关系用相连的直线表示。,通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。,将上述两组权重进行综合，确定各方案对目标的权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。,层次分析法的基本步骤,成对比较阵和权向量,元素之间两两对比，对比采用相对尺度,设要比较各准则C1,C2, , Cn对目标O的重要性,A成对比较阵,A是正互反阵,要由A确定C1, , Cn对O的权向量,选择旅游地,成对比较的不一致情况,允许不一致，但要确定不一致的允许范围,考察完全一致的情况,成对比较阵和权向量,成对
33、比较完全一致的情况,A的秩为1，A的唯一非零特征根为n,A的任一列向量是对应于n 的特征向量,A的归一化特征向量可作为权向量,对于不一致(但在允许范围内)的成对比较阵A，建议用对应于最大特征根的特征向量作为权向量w ，即,一致阵性质,成对比较阵和权向量,2 4 6 8,比较尺度aij,Saaty等人提出19尺度aij 取值1,2, , 9及其互反数1,1/2, , 1/9,心理学家认为成对比较的因素不宜超过9个,用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现， 19尺度较
34、优。,便于定性到定量的转化：,成对比较阵和权向量,一致性检验,对A确定不一致的允许范围,已知：n 阶一致阵的唯一非零特征根为n,可证：n 阶正互反阵最大特征根 n, 且 =n时为一致阵,定义一致性指标:,CI 越大，不一致越严重,为衡量CI 的大小，引入随机一致性指标 RI随机模拟得到aij , 形成A，计算CI 即得RI。,定义一致性比率 CR = CI/RI,当CR0.1时，通过一致性检验,Saaty的结果如下,“选择旅游地”中准则层对目标的权向量及一致性检验,准则层对目标的成对比较阵,最大特征根=5.073,权向量(特征向量)w =(0.263,0.475,0.055,0.090,0.1
35、10)T,一致性指标,随机一致性指标 RI=1.12 (查表),一致性比率CR=0.018/1.12=0.0160.1,通过一致性检验,组合权向量,记第2层（准则）对第1层（目标）的权向量为,同样求第3层(方案)对第2层每一元素(准则)的权向量,方案层对C1(景色)的成对比较阵,方案层对C2(费用)的成对比较阵,最大特征根 1 2 n,权向量 w1(3) w2(3) wn(3),组合权向量,RI=0.58 (n=3), CIk 均可通过一致性检验,w(2) 0.2630.4750.0550.0900.110,方案P1对目标的组合权重为0.5950.263+ =0.300,方案层对目标的组合权向
36、量为 (0.300, 0.246, 0.456)T,组合 权向量,第2层对第1层的权向量,第3层对第2层各元素的权向量,构造矩阵,则第3层对第1层的组合权向量,第s层对第1层的组合权向量,其中W(p)是由第p层对第p-1层权向量组成的矩阵,层次分析法的基本步骤,1）建立层次分析结构模型,深入分析实际问题，将有关因素自上而下分层（目标准则或指标方案或对象），上层受下层影响，而层内各因素基本上相对独立。,2）构造成对比较阵,用成对比较法和19尺度，构造各层对上一层每一因素的成对比较阵。,3）计算权向量并作一致性检验,对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量
37、。,4）计算组合权向量（作组合一致性检验*）,组合权向量可作为决策的定量依据。,二. 层次分析法的广泛应用,应用领域：经济计划和管理，能源政策和分配，人才选拔和评价，生产决策，交通运输，科研选题，产业结构，教育，医疗，环境，军事等。,处理问题类型：决策、评价、分析、预测等。,建立层次分析结构模型是关键一步，要有主要决策层参与。,构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。,例1 国家实力分析,例2 工作选择,例3 横渡江河、海峡方案的抉择,例3 横渡江河、海峡方案的抉择,例4 科技成果的综合评价,三. 层次分析法的若干问题,正互反阵的最大特征根是否为正数？特征向量是否为正向量？
38、一致性指标能否反映正互反阵接近一致阵的程度？,怎样简化计算正互反阵的最大特征根和特征向量？,为什么用特征向量作为权向量？,当层次结构不完全或成对比较阵有空缺时怎样用层次分析法？,1. 正互反阵的最大特征根和特征向量的性质,定理1 正矩阵A 的最大特征根是正单根，对应正特征向量w，且,定理2 n阶正互反阵A的最大特征根 n , = n是A为一致阵的充要条件。,2. 正互反阵最大特征根和特征向量的简化计算,精确计算的复杂和不必要,简化计算的思路一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。,和法取列向量的算术平均,精确结果:w=(0.588,
39、0.322,0.090)T, =3.010,根法取列向量的几何平均,幂法迭代算法,1）任取初始向量w(0), k:=0，设置精度,2) 计算,3）归一化,5) 计算,简化计算,4）若 ，停止；否则，k:=k+1, 转2,3. 特征向量作为权向量成对比较的多步累积效应,问题,一致阵A, 权向量w=(w1,wn)T, aij=wi/wj,A不一致, 应选权向量w使wi/wj与 aij相差尽量小（对所有i,j)。,非线性 最小二乘,线性化 对数最小二乘,结果与根法相同,按不同准则确定的权向量不同，特征向量有什么优点。,成对比较,Ci:Cj (直接比较）,aij 1步强度,aisasj Ci通过Cs
40、与Cj的比较,aij(2) 2步强度,更能反映Ci对Cj 的强度,多步累积效应,体现多步累积效应,定理1,特征向量体现多步累积效应,4.不完全层次结构中组合权向量的计算,完全层次结构：上层每一元素与下层所有元素相关联,不完全层次结构,设第2层对第1层权向量w(2)=(w1(2),w2(2)T已定,第3层对第2层权向量w1(3)=(w11(3),w12(3),w13(3),0)T w2(3)=(0,0,w23(3),w24(3)T已得,讨论由w(2),W(3)=(w1(3), w2(3)计算第3层对第1层权向量w(3）的方法,例: 评价教师贡献的层次结构,P1,P2只作教学, P4只作科研, P
41、3兼作教学、科研。,C1,C2支配元素的数目不等,不考虑支配元素数目不等的影响,仍用 计算,支配元素越多权重越大,用支配元素数目n1,n2对w(2)加权修正,若C1,C2重要性相同, w(2)=(1/2,1/2)T, P1P4能力相同, w1(3)=(1/3,1/3,1/3,0)T,w2(3)=(0,0,1/2,1/2)T,公正的评价应为： P1:P2:P3:P4=1:1:2:1,再用 计算,支配元素越多权重越小,教学、科研任务由上级安排,教学、科研靠个人积极性,考察一个特例：,5. 残缺成对比较阵的处理,miA第i 行中的个数,为残缺元素,6. 更复杂的层次结构,递阶层次结构：层内各元素独立
42、，无相互影响和支配；层间自上而下、逐层传递，无反馈和循环。,更复杂的层次结构：层内各元素间存在相互影响或支配；层间存在反馈或循环。,例,层次分析法的优点,系统性将对象视作系统，按照分解、比较、判断、综合的思维方式进行决策系统分析（与机理分析、测试分析并列）；,实用性定性与定量相结合，能处理传统的优化方法不能解决的问题；,简洁性计算简便，结果明确，便于决策者直接了解和掌握。,层次分析法的局限,囿旧只能从原方案中选优，不能产生新方案；,粗略定性化为定量，结果粗糙；,主观主观因素作用大，结果可能难以服人。,2.2 循环比赛的名次,n支球队循环赛，每场比赛只计胜负，没有平局。,根据比赛结果排出各队名次
43、,方法1：寻找按箭头方向通过全部顶点的路径。,312456,146325,方法2：计算得分：1队胜4场，2, 3队各胜3场，4, 5队各胜2场， 6队胜1场。,2, 3队， 4, 5队无法排名,6支球队比赛结果,32，4 5,循环比赛的结果竞赛图 每对顶点间都有边相连的有向图,3个顶点的竞赛图,名次,1，2，3,(1,2,3)并列,1, 2, 3, 4,2,(1,3,4),(1,3,4), 2,4个顶点的竞赛图,名次,(1,2),(3,4),1, 2, 3, 4?,竞赛图的3种形式,具有唯一的完全路径，如(1)；,双向连通图任一对顶点存在两条有向路径相互连通，如(4)；,其他，如(2)， (3) 。,竞赛图的性质,必存在完全路径；,若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如(1) 。,双向连通竞赛图G=(V,E)的名次排序,邻接矩阵,得分向量,双向连通竞赛图的名次排序,对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A 满足Ar 0，A称素阵,素阵A的最大特征根为正单根，对应正特征向量s，且,排名为1，2，4，3,1, 2, 3, 4?,6支球队比赛结果,排名次序为1，3， 2，5，4，6,
