数学建模优化模型选讲

,数学建模培训系列讲座,最优化与离散模型,主讲,: (),数学建模：最优化问题,最优化问题大体分两类：,一类是求函数在一定约束条件下的极值,;,另一类是求泛函的极值,.,这里的函数我们称之为,目标函数,.,目标函数中的变量称之为,决策变量,.,约束条件,是指问题对决策变量的限制条件,即决策变量的取值范围,.,约束条件常用一组关于决策变量的等式与不等式给出,.,如果目标函数有明显的表达式,一般可用微分法,变分法或动态规划等分析方法来求解,(,间接求优,);,如果目标函数的表达式过于复杂甚至根本没有明显的表达式,则可用数值方法或“试验最优化”方法等直接方法来求解,(,直接求优,).,求函数极值的数值方法或试验化方法有时称为,数学规划,.,数学规划除了,线性规划,外统称为,非线性规划,.,求解数学规划的软件,: LINDO, LINGO,LINDO(Linear INteractive and Discrete Optimizer),交互式的线性和离散优化求解器,LINGO(Linear INteractive and General Optimizer),交互式的线性和通用优化求解器,模型实例,:,存贮模型,问 题,配件厂为装配线生产若干种产品，轮换产品时因更换设,备要付生产准备费，产量大于需求时要付贮存费。该厂,生产能力非常大，即所需数量可在很短时间内产出。,已知某产品日需求量,100,件，生产准备费,5000,元，贮存费,每日每件,1,元。试安排该产品的生产计划，即多少天生产,一次（生产周期），每次产量多少，使总费用最小。,要,求,不只是回答问题，而且要建立生产周期、产量与,需求量、准备费、贮存费之间的关系。,第一讲 简单的优化模型,问题分析与思考,每天生产一次,，每次,100,件，无贮存费，准备费,5000,元。,日需求,100,件，准备费,5000,元，贮存费每日每件,1,元。,10,天生产一次,，每次,1000,件，贮存费,900+800+100 =4500,元，准备费,5000,元，总计,9500,元。,20,天生产一次,，每次,2000,件，贮存费,2900+2800+100 =28500,元，准备费,5000,元，总计,33500,元。,平均每天费用,950,元,平均每天费用,1675,元,平均每天费用,5000,元,周期短，产量小,周期长，产量大,贮存费少，准备费多,准备费少，贮存费多,存在最佳的周期和产量，使平均费用（二者之和）最小,这是一个优化问题，关键在建立目标函数。,显然不能用一个周期的总费用作为目标函数,目标函数,每天总费用的平均值,模 型 假 设,1.,产品每天的需求量为常数,r,；,2.,每次生产准备费为,c,1,每天每件产品贮存费为,c,2,；,3.,T,天生产一次（周期）,每次生产,Q,件，当贮存量,为零时，,Q,件产品立即到来（生产时间不计）；,建 模 目 的,设,r, c,1,c,2,已知，求,T, Q,使每天总费用的平均值最小。,4.,为方便起见，时间和产量都作为连续量处理。,模 型 建 立,0,t,q,贮存量表示为时间的函数,q,(,t,),T,Q,r,t,=0,生产,Q,件，,q,(0)=,Q,q,(,t,),以,需求速率,r,递减，,q,(,T,)=0.,一周期,总费用,每天总费用平均值,（目标函数）,离散问题连续化,一周期贮存费为,A=QT,/2,模型求解,求,T,使,模型分析,模型应用,c,1,=5000,c,2,=1,，,r,=100,T,=10(,天,),Q,=1000(,件,),C,=1000(,元,),回答问题,经济批量订货公式,（,EOQ,公式,）,每天需求量,r,，每次订货费,c,1,每天每件贮存费,c,2,，,这就是经济学中著名的用于订货、供应、存贮情形的,以上讨论的是不允许缺货的存贮模型,问：为什么不考虑生产费用？在什么条件下才不考虑？,T,天订货一次,(,周期,),每次订货,Q,件，当贮存量,降到零时，,Q,件立即到货。,总结,则最优解为,:,允许缺货的存贮模型,A,B,0,q,Q,r,T,1,t,当贮存量降到零时仍有需求,r,出现缺货，造成损失,原模型假设：贮存量降到零时,Q,件立即生产出来,(,或立即到货,),现假设：允许缺货,每天每件缺货损失费,c,3,缺货需补足,T,一周期贮存费,一周期缺货费,周期,T, t=T,1,贮存量降到零,一周期总费用,每天总费用,平均值,（目标函数）,一周期总费用,求,T ,Q,使,为与,不允许缺货的存贮模型相比，,T,记作,T,Q,记作,Q,允许缺货模型,0,q,Q,r,T,1,t,T,注意：缺货需补足,Q,每周期初的存贮量,R,每周期的生产量,R,（或订货量）,Q,不允许缺货时的产量,(,或订货量,),不允许缺货模型,记,允许缺货模型,不允许缺货,下面将进入数学规划模型,数学规划模型,实际问题中,的优化模型,x,决策变量,f,(,x,),目标函数,g,i,(,x,),0,约束条件,多元函数条件极值,决策变量个数,n,和,约束条件个数,m,较大,最优解在可行域,的边界上取得,数学规划,线性规划,非线性规划,整数规划,重点在模型的建立和结果的分析,第二讲 数学规划模型,企业生产计划,2.1,奶制品的生产与销售,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订,单阶段生产计划,，否则应制订多阶段生产计划。,本节课题,例,1,加工奶制品的生产计划,问题,:,一奶制品加工厂用牛奶生产,A,1,A,2,两种奶制品,1,桶牛奶,可以在设备甲上用,12,小时加工成,3,公斤,A,1,或者地设备乙上加工成,4,公斤,A,2,.,根据市场需求,生产的,A,1,A,2,全部能售出,且每公斤,A,1,获利,24,元,每公斤,A,2,获利,16,元,.,现在加工厂每天能得到,50,桶牛奶的供应,每天正式工人总的劳动时间为,480,小时,并且设备甲每天最多能加工,100,公斤,A,1,设备乙的加工能力没有限制,.,试为该厂制定一个生产计划,使每天获利最大,并进一步讨论以下,3,个附加问题,:,1),若用,35,元可以买到一桶牛奶,应否作这项投资,?,若投资,每天最多能购买多少桶牛奶,?,2),若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元,?,3),由于市场需求变化,每公斤,A,1,的获利增加到,30,元,应否改变生产计划,?,例,1,加工奶制品的生产计划,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,公斤,A,1,50,桶牛奶,每天,模型分析与假设,比例性,可加性,连续性,x,i,对目标函数的“贡献”与,x,i,取值成正比,x,i,对约束条件的“贡献”与,x,i,取值成正比,x,i,对目标函数的“贡献”与,x,j,取值无关,x,i,对约束条件的“贡献”与,x,j,取值无关,x,i,取值连续,A,1,A,2,每公斤的获利是与各自产量无关的常数,每桶牛奶加工出,A,1,A,2,的数量和时间是与各自产量无关的常数,A,1,A,2,每公斤的获利是与相互产量无关的常数,每桶牛奶加工出,A,1,A,2,的数量和时间是与相互产量无关的常数,加工,A,1,A,2,的牛奶桶数是实数,线性规划模型,模型求解,图解法,x,1,x,2,0,A,B,C,D,l,1,l,2,l,3,l,4,l,5,约束条件,目标函数,Z,=0,Z,=2400,Z,=3600,z,=,c,(,常数,) ,等值线,c,在,B,(20,30),点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个极点取得。,模型求解,软件实现,LINDO 6.1,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,OBJECTIVE FUNCTION VALUE,1) 3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2) 0.000000 48.000000,3) 0.000000 2.000000,4) 40.000000 0.000000,NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20,桶牛奶生产,A,1, 30,桶生产,A,2,，利润,3360,元。,结果解释,OBJECTIVE FUNCTION VALUE,1) 3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW,SLACK OR SURPLUS,DUAL PRICES,2) 0.000000,48.000000,3) 0.000000,2.000000,4) 40.000000,0.000000,NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余,40,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,三种资源,“,资源” 剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE,1) 3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,NO. ITERATIONS= 2,最优解下“资源”增加,1,单位时“效益”的增量,原料增加,1,单位,利润增长,48,时间增加,1,单位,利润增长,2,加工能力增长不影响利润,影子价格,35,元可买到,1,桶牛奶，要买吗？,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2,元！,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 72.000000 24.000000 8.000000,X2 64.000000 8.000000 16.000000,RIGHTHAND SIDE RANGES,ROW CURRENT ALLOWABLE ALLOWABLE,RHS INCREASE DECREASE,2 50.000000 10.000000 6.666667,3 480.000000 53.333332 80.000000,4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x,1,系数范围,(64,96),x,2,系数范围,(48,72),A,1,获利增加到,30,元,/,千克，应否改变生产计划,x,1,系数由,24,3=72,增加,为,30,3=90,，在,允许范围内,不变！,(,约束条件不变,),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 72.000000 24.000000 8.000000,X2 64.000000 8.000000 16.000000,RIGHTHAND SIDE RANGES,ROW CURRENT ALLOWABLE ALLOWABLE,RHS INCREASE DECREASE,2 50.000000 10.000000 6.666667,3 480.000000 53.333332 80.000000,4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加,10,时间最多增加,53,35,元可买到,1,桶牛奶，每天最多买多少？,最多买,10,桶,!,(,目标函数不变,),问题,:,例,1,给出的生产条件,利润,资源均不变,.,为增加赢利,对,A,1,和,A,2,进行深加工,.,用,2,小时和,3,元加工费可将,A,1,加工成,0.8,公斤,B,1,也可将,1,公斤,A,2,加工成,0.75,公斤,B,2,.,每公斤,B,1,获利,44,元,每公斤,B,2,获利,32,元,.,试为该厂制定一个生产计划,使每天获利最大,并讨论以下问题,:,1),若用,30,元可以买到一桶牛奶,投资,3,元可增加,1,小时劳动时间,应否作这项投资,?,若每天投资,150,元,可赚回多少,?,2),每公斤,B,1,B,2,获利经常有,10%,的波动,对制定的计划有无影响,?,若每公斤,B,1,获利下降,10%,计划应变化吗,?,例,2,奶制品的生产销售计划,在例,1,基础上深加工,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,0.8,千克,B,1,2,小时,3,元,1,千克,获利,44,元,/,千克,0.75,千克,B,2,2,小时,3,元,1,千克,获利,32,元,/,千克,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,0.8,千克,B,1,2,小时,3,元,1,千克,获利,44,元,/,千克,0.75,千克,B,2,2,小时,3,元,1,千克,获利,32,元,/,千克,制订生产计划，使每天净利润最大,30,元可增加,1,桶牛奶，,3,元可增加,1,小时时间，应否投资？现投资,150,元，可赚回多少？,50,桶牛奶, 480,小时,至多,100,公斤,A,1,B,1,，,B,2,的获利经常有,10%,的波动，对计划有无影响？,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,获利,24,元,/,千克,获利,16,元,/,kg,0.8,千克,B,1,2,小时,3,元,1,千克,获利,44,元,/,千克,0.75,千克,B,2,2,小时,3,元,1,千克,获利,32,元,/,千克,出售,x,1,千克,A,1,x,2,千克,A,2,，,X,3,千克,B,1,x,4,千克,B,2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x,5,千克,A,1,加工,B,1,，,x,6,千克,A,2,加工,B,2,附加约束,模型求解,软件实现,LINDO 6.1,MAX 24x1+16x2 + 44x3 +32x4-3x5-3x6,st,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 VALUE,1) 3460.800,VARIABLE VALUE REDUCED COST,X1 0.000000 1.680000,X2 168.000000 0.000000,X3 19.200001 0.000000,X4 0.000000 0.000000,X5 24.000000 0.000000,X6 0.000000 1.520000,ROW SLACK OR SURPLUS DUAL PRICES,2) 0.000000 3.160000,3) 0.000000 3.260000,4) 76.000000 0.000000,5) 0.000000 44.000000,6) 0.000000 32.000000,NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,MAX 24x1+16x2 + 44x3 +32x4-3x5-3x6,st,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 VALUE,1) 3460.800,VARIABLE VALUE,REDUCED COST,X1 0.000000,1.680000,X2 168.000000,0.000000,X3 19.200001,0.000000,X4 0.000000,0.000000,X5 24.000000,0.000000,X6 0.000000,1.520000,ROW SLACK OR SURPLUS DUAL PRICES,2) 0.000000 3.160000,3) 0.000000 3.260000,4) 76.000000 0.000000,5) 0.000000 44.000000,6) 0.000000 32.000000,NO. ITERATIONS= 2,结果解释,每天销售,168,千克,A,2,和,19.2,千克,B,1,，,利润,3460.8,（元）,8,桶牛奶加工成,A,1,，,42,桶牛奶加工成,A,2,，,将得到的,24,千克,A,1,全部加工成,B,1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE,1) 3460.800,VARIABLE VALUE REDUCED COST,X1 0.000000 1.680000,X2 168.000000 0.000000,X3 19.200001 0.000000,X4 0.000000 0.000000,X5 24.000000 0.000000,X6 0.000000 1.520000,ROW SLACK OR SURPLUS,DUAL PRICES,2) 0.000000,3.160000,3) 0.000000,3.260000,4) 76.000000 0.000000,5) 0.000000 44.000000,6) 0.000000 32.000000,增加,1,桶牛奶使利润增长,3.16,12=37.92,增加,1,小时时间使利润增长,3.26,30,元可增加,1,桶牛奶，,3,元可增加,1,小时时间，应否投资？现投资,150,元，可赚回多少？,投资,150,元增加,5,桶牛奶，可赚回,189.6,元。（大于增加时间的利润增长）,结果解释,B,1,B,2,的获利有,10%,的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 24.000000 1.680000 INFINITY,X2 16.000000 8.150000 2.100000,X3 44.000000 19.750002 3.166667,X4 32.000000 2.026667 INFINITY,X5 -3.000000 15.800000 2.533334,X6 -3.000000 1.520000 INFINITY, ,DO RANGE (SENSITIVITY) ANALYSIS?,Yes,B,1,获利下降,10%,，超出,X3,系数允许范围,B,2,获利上升,10%,，超出,X4,系数允许范围,波动对计划有影响,生产计划应重新制订：如将,x,3,的系数改为,39.6,计算，,会发现结果有很大变化。,2.1,饮料厂的生产与检修,问题,:,某饮料厂确定了未来四周对该饮料的需求量,以及未来,四周本厂的生产能力和生产成本,(,如下表所示,).,每周满足需求后,周次,需求,(,千箱,),生产能力,(,千箱,),成本,(,千元,/,千箱,),1,15,30,5.0,2,25,40,5.1,3,35,45,5.4,4,25,20,5.5,合计,100,135,有剩余时,要支出存贮费,为每周每千箱,0.2,千元,.,问应如何安排生产,在满足市场需求的条件下,使四周总费用最小,?,单阶段生产计划,多阶段生产计划,企业生产计划,外部需求和内部资源随时间变化,问题分析,除第,4,周外每周的生产能力超过每周的需求；,生产成本逐周上升；,前几周应多生产一些。,周次,需求,能力,1,15,30,2,25,40,3,35,45,4,25,20,合计,100,135,成本,5.0,5.1,5.4,5.5,饮料厂在第,1,周开始时没有库存；,从费用最小考虑,第,4,周末不能有库存；,周末有库存时需支出一周的存贮费；,每周末的库存量等于下周初的库存量。,模型假设,目标函数,约束条件,产量、库存与需求平衡,决策变量,能力限制,非负限制,模型建立,x,1,x,4,：第,14,周,的生产量,y,1,y,3,：第,13,周末,库存量,周次,需求,能力,1,15,30,2,25,40,3,35,45,4,25,20,成本,5.0,5.1,5.4,5.5,存贮费,:,0.2,(,千元,/,周,千箱,),模型求解,4,周生产计划的总费用为,528 (,千元,),最优解：,x,1,x,4,：,15,，,40,，,25,，,20,；,y,1,y,3,：,0,，,15,，,5 .,周次,需求,能力,1,15,30,2,25,40,3,35,45,4,25,20,成本,5.0,5.1,5.4,5.5,产量,15,40,25,20,库存,0,15,5,0,LINDO,求解,检修计划,0-1,变量,w,t,：,w,t,=1,检修安排在第,t,周,(,t,=1,2,3,4,）,在,4,周内安排一次设备检修，占用当周,15,千箱生产能力，能使检修后每周增产,5,千箱，检修应排在哪一周,?,检修安排在任一周均可,:,周次,需求,能力,1,15,30,2,25,40,3,35,45,4,25,20,成本,5.0,5.1,5.4,5.5,能力限制,产量、库存与需求平衡约束条件不变,增加检修约束条件：,目标函数不变,LINDO,求解,总费用由,528,千元降,为,527,千元,检修所导致的生产能力提高的作用,需要更长的时间才能得到充分体现。,最优解：,w,1,=,1,w,2,w,3,w,4,=0;,x,1,x,4,：,15,45,15,25,；,y,1,y,3,：,0,20,0 .,min 5.0x1+5.1x2+5.4x3+5.5x4+0.2y1+0.2y2+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,周的需求量、生产能力和成本,周次,需求量,(,千箱,),生产能力,(,千箱,),成本,(,千元,/,千箱,),1,15,30,5.0,2,25,40,5.1,3,35,45,5.4,4,25,20,5.5,合计,100,135,问题,:,生产批量问题,考虑与产量无关的固定费用,给优化模型求解带来新的困难,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,最优解：,x,1,x,4,：,15,，,40,，,45,，,0,；,总费用：,554.0(,千元,),用,LINDO,求解,决策变量,x,1,x,4,：第,14,周,的生产量,y,1,y,3,：第,13,周末,库存量,0-1,变量,w,t,：,w,t,=1,第,t,周开工生产,(,t,=1,2,3,4,）,生产批量问题的一般提法,c,t,时段,t,生产费用,(,元,/,件,),；,h,t,时段,t,(,末,),库存费,(,元,/,件,),；,s,t,时段,t,生产准备费,(,元,),；,d,t,时段,t,市场需求,(,件,),；,M,t,时段,t,生产能力,(,件,),。,假设初始库存为,0,制订生产计划,满足需求,并使,T,个时段的总费用最小。,决策变量,x,t,时段,t,生产量；,y,t,时段,t,(,末,),库存量；,w,t,=1 ,时段,t,开工,生产,(,w,t,=0 ,不开工,),。,目标,约束,混合,0-1,规划模型,生产批量问题的一般提法,下面将进入离散模型,离散模型：差分方程、整数规划、图论、对策论、网络流、,分析社会经济系统的有力工具,只用到代数、集合及图论（少许）的知识,第三讲 离散模型,3.1,层次分析模型,背景,日常工作、生活中的决策问题,涉及经济、社会等方面的因素,作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化,Saaty,于,1970,年代提出层次分析法,AHP,(Analytic Hierarchy Process),AHP,一种,定性与定量相结合的、系统化、层次化,的分析方法,目标层,O(,选择旅游地,),P,2,黄山,P,1,桂林,P,3,北戴河,准则层,方案层,C,3,居住,C,1,景色,C,2,费用,C,4,饮食,C,5,旅途,一,.,层次分析法的基本步骤,例,.,选择旅游地,如何在,3,个目的地中按照景色、费用、居住条件等因素选择,.,“,选择旅游地,”,思维过程的归纳,将决策问题分为,3,个层次：目标层,O,，准则层,C,，方案层,P,；每层有若干元素， 各层元素间的关系用相连的直线表示。,通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。,将上述两组权重进行综合，确定各方案对目标的权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。,层次分析法的基本步骤,成对比较阵和权向量,元素之间两两对比，对比采用相对尺度,设要比较各准则,C,1,C,2, , C,n,对目标,O,的重要性,A,成对比较阵,A,是正互反阵,要由,A,确定,C,1, , C,n,对,O,的权向量,选择旅游地,成对比较的不一致情况,一致比较,不一致,允许不一致，但要确定不一致的允许范围,考察完全一致的情况,成对比较阵和权向量,成对比较完全一致的情况,满足,的正互反阵,A,称,一致阵,，如,A,的秩为,1,，,A,的唯一非零特征根为,n,A,的任一列向量是对应于,n,的特征向量,A,的归一化特征向量可作为权向量,对于不一致,(,但在允许范围内,),的成对比较阵,A,，建议用对应于最大特征根,的特征向量作为权向量,w,，即,一致阵性质,成对比较阵和权向量,2 4 6 8,比较尺度,a,ij,Saaty,等人提出,19,尺度,a,ij,取值,1,2, , 9,及其互反数,1,1/2, , 1/9,尺度,1 3 5 7 9,相同 稍强 强 明显强 绝对强,a,ij,=,1,1/2, ,1/9,的重要性与上面相反,心理学家认为成对比较的因素不宜超过,9,个,用,13,15,117,1,p,9,p,(,p,=2,3,4,5),d,+0.1,d,+0.9 (,d,=1,2,3,4),等,27,种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，,19,尺度较优。,便于定性到定量的转化：,成对比较阵和权向量,一致性检验,对,A,确定不一致的允许范围,已知：,n,阶一致阵的唯一非零特征根为,n,可证：,n,阶正互反阵最大特征根,n,且,=,n,时为一致阵,定义一致性指标,:,CI,越大，不一致越严重,RI,0,0,0.58,0.90,1.12,1.24,1.32,1.41,1.45,1.49,1.51,n,1,2,3,4,5,6,7,8,9,11,10,为衡量,CI,的大小，引入,随机一致性指标,RI,随机模拟得到,a,ij,形成,A,，计算,CI,即得,RI,。,定义一致性比率,CR = CI,/,RI,当,CR,0.1,时，通过一致性检验,Saaty,的结果如下,“,选择旅游地”中准则层对目标的权向量及一致性检验,准则层对目标的,成对比较阵,最大特征根,=5.073,权向量,(,特征向量,),w,=(0.263,0.475,0.055,0.090,0.110),T,一致性指标,随机一致性指标,RI=,1.12 (,查表,),一致性比率,CR,=0.018/1.12=0.0163),个顶点的双向连通竞赛图，存在正整数,r,，使邻接矩阵,A,满足,A,r,0,，,A,称,素阵,素阵,A,的最大特征根为正单根,，对应正特征向量,s,，,且,排名为,1,，,2,，,4,，,3,用,s,排名,1,2,3,4,(4),1, 2, 3, 4?,1