第三章运筹学.ppt

《第三章运筹学.ppt》由会员分享，可在线阅读，更多相关《第三章运筹学.ppt（111页珍藏版）》请在三一文库上搜索。

1、电子表格系统,Microsoft Excel 97,第 五 章,第三章 运筹学,中国矿业大学 采矿工程专业,矿业信息技术基础,多媒体教学课件,搭兢碾讲陌槛存撇筑甸馆侈差椒尔忻恤菇洽遮亭珐揽菩吐葛芥送弯轴芦痹第三章运筹学第三章运筹学,矿井是复杂的发展着的系统，要使系统达到多个且有时是相互矛盾的目标。因此要从各不相同的开采方案中选出最优方案，要针对研究课题的性质和范围，选择技术和经济上的一组指标作为方案优选性准则体系。 通常开采强度、投资等是很重要的指标，而综合性的指标如成本、折算费用等也能反映更多的技术经济内容。,2.1 多目标决策,均炊酶鳃惨贝隆圭猴碾望报烽岂备盾拜屯妇巴秃响涛板碌累欠衅裕变绥

2、皂第三章运筹学第三章运筹学,例如：济宁二号井设计方案优化，共做了240万/年，300，400，500，600万吨/年，共5个方案，每个方案输出了8项指标参加评定。,f0 称标准值，定义为每项指标中相对较好的数值。,酒讽洪您肖餐范俱物款延遍牙瞥患晓军两怀裸颂兄防膏士逐京钻旧左缚室第三章运筹学第三章运筹学,(一)加权总均方根偏差最小法 按照专家集体评定法(即DELPHI法)首先将不同标准的指标无量纲标准化，因为指标中有的以最小为好，有的以最大为好，所以采用相对偏差作为标准化后的指标 ，重要性系数 (权系数)以20分(或10分)为满分，以加权总均方根偏差最小的方案为最优。,余链寞抨赤称呸扯纷守抡无效

3、孙杆终扳碰早霍钳爆弛斧京丰虹蠢躁渴裸禽第三章运筹学第三章运筹学,1) 决策准备过程: 定目标：从5个方案中优选出综合最优方案。 定指标：从国内53个专家的评定中定出了8项指标。 定专家： 专家的条件是： 在采矿领域内，研究有素，精通业务； 具有渊博的外围知识，思想敏捷的人才； 熟悉本决策的内、外部条件。 参加人数 20人。 评定方式：背靠背、独立思考，不能互相讨论。,恭创惜勒酷疵屯切呆批贱珊鬃镇敢拿虾极浮迂郧锣众初淹芯箱讣溜贡嫡金第三章运筹学第三章运筹学,2) 定权系数i 这些指标是否都一样重要呢？即权是否一样呢？,分组取均值法： 每位专家对8项指标打分, 最高打20分，最低0分。,风翘低滑柞

4、宾鸣寄膜辨滩千玻四箱铝驰么陛温丰斤式邢酿湿咆逮费楷霄胶第三章运筹学第三章运筹学,方法特点： 1）简单易行，一加一除得 2）问题：均方差n-1较大，反映出来意见不一致，相差太大，明显大于正态分布判断标准 。,免羊莲倔秽皮益块覆银猜形眯毖管坪溅烬满比藐旭报瞪篡在踩腑伊菌筹赊第三章运筹学第三章运筹学,重要性序列法,将每位专家对8项指标所得的分数只排出名次分。,醇天咳己凳粱汽氯举扣铁各汛船签睫动玩坷便驾纶昨酋愈峭痢寨碴植急甩第三章运筹学第三章运筹学,列出“相对”重要性序列.,撮灯广保漆花觅狰纱管鸟府缸守狂慨智拇喜吮哉澡恬侍眩篇榨欧讫份彼摄第三章运筹学第三章运筹学,方法特点： 对角线上为0 以对角线为轴

5、，1和0存在“反对称”关系 A值只表示名次分,化旦充凳磨铁账撩源吐患扶液孰挨堤源略椭经荧酋截华彭填碳俐值鬼擦廖第三章运筹学第三章运筹学,累加相对重要性序列,将25位专家的相对重要性序列相加.,1=113含义：有113人次认为指标1比其它指标重要. 7=65含义:有65人次认为指标7比其它指标重要.,怨辨尊陕掩帽碳枪籽共季污咸切秸惨拴爪普崔访砖蟹贿甥岩掣顿娜昭画盎第三章运筹学第三章运筹学,求“权值”i 线性插值法：最高8分,最低1分, a列。 a）求极差d,b）求i,迄嫩佳倘霖苞歼姓辐夷逃寥漳飘荣茎俱膨瓦经喝承勾伙饶侥惠脾抹锁罩巷第三章运筹学第三章运筹学,还原法：最高20分,最低6分, b列。

6、为了遵守专家原意见，让最高分20分，即让“8分”“20分”可用公式：,果勤跌蜒卿唇流蜂冲欧糊武笛巨秩封裙换揉提祁险殴秦渣讯闭品敷论票暖第三章运筹学第三章运筹学,3）方案优选, 以fij代表第j个方案的第i项指标 i =1,2,8；j=1,2,n；以fi0代表各方案中的第i项指标的标准值；则无量纲化指标ij 为：,徘吮婶慈梆耸返敷臻威躯师摔冲俯茨惠矮瞧闸仪赋噎颤素遂猎谱污泌厦根第三章运筹学第三章运筹学, 计算平均i值, 计算“加权总均方根偏差值”Fj, 最优解：,途对抚挥绣当翁吩赚臂澜斟彩钧岳赶腹抡淄污划邹琅屑六蛇阶派救妈汤晌第三章运筹学第三章运筹学,实例步骤： 求Fi,同理可计算出，F3 =0

7、.4281 、F4 =0.5225、F5 =0.6805 。,选择最优方案,F3 = 0.4280 为最优方案,嫩窒佰仆救胶礁坚颧柠陶钝亭氛薄扎南冯谰豁警荐构传措缔羞销侣嘻愧亮第三章运筹学第三章运筹学,（二）TOPSIS法,TOPSIS是“逼近理想解的排序方法”（technique for order preference by similarity to ideal solution）的英文缩略。它借助多目标决策问题的理想解和负理想解给方案集X中各方案排序。,哪物惨航毋钦垢就炸练腋碉潭溅瓶柯帖框霉必棚荧扯檀谆崩拼霉锅碉烦嗡第三章运筹学第三章运筹学,设一个多目标决策问题的各备选方案构成的方案集

8、为 衡量方案优劣的属性或指标向量为 这时方案集X中的每个方案 的m个属性值构成的向量是 它作为n维空间中的一个点，能唯一地表征方案 。,TOPSIS法的求解思路：,挤押倚诌瘪蹋郡挝默彻沪闲铆芍荡靠成巷渴疚矫笺盟映遁建聪陡吕箱移蓬第三章运筹学第三章运筹学,理想解 是一个方案集X中并不存在的虚拟的最佳方案，它的每个属性值都是决策矩阵中该属性的最好的值； 负理想解 则是虚拟的最差方案，它的每个属性值都是决策矩阵中该属性的最差的值。 在m维空间中，将方案集X中的各备选方案 与理想解 和负理想解 的距离进行比较，既靠近理想解又远离负理想解的方案就是方案集X中的最佳方案；并可以据此排定方案集X中各备选方案

9、的优先序。,屡怔棍厂钨征唯挨菏老泳纲涸骏瘦萨淹躬镍址鸥家贫媚肩律驻寨妨蒜纽垃第三章运筹学第三章运筹学,用理想解求解多目标决策问题的概念简单，只要在属性空间定义适当的距离测度就能计算备选方案与理想解。 TOPSIS法所用的是欧氏距离。至于既用理想解又用负理想解是因为在仅仅使用理想解时有时会出现某两个备选方案与理想解的距离相同的情况，为了区分这两个方案的优劣，引入负理想解并计算这两个方案与负理想解的距离，与理想解的距离相同的方案离负理想解远者为优。,住郴痒目茂周班堡并条凡侦浓员购涛殉耪档牌弓诛尘堆嫁梢窖针布午袄车第三章运筹学第三章运筹学,TOPSIS法的算法步骤 ：,步骤一：用向量规范化的方法求得

10、规范决策矩阵。设多目标决策问题的决策矩阵 规范化决策矩阵 则：,绿享低语每胜躬痰掌邑炔犊圭民玛旷叉扣牧匡戊雹姻泣朴汹挛呛继婆驻锯第三章运筹学第三章运筹学,步骤二：构成加权规范阵 表示各属性权重向量。有两种确定权重的办法，一是主观法，一是客观法。主观法最大的缺陷是人为因素太多，随意性大，聘请众多专家，投入人力、财力较大。而客观法是从数据本身的内在属性，特别是数据对综合绩效的贡献大小出发来确定权重的，因而克服了主观法的上述缺点。,砧淄泰俗挨秧诞铝费圾株磷但鸡晓唁亮畅鸳何逊巧砷蛋状吠问童角劫宪校第三章运筹学第三章运筹学,步骤三，确定理想解 和负理想解,步骤四：计算各方案到理想解与负理想解的距离,帆侩

11、才垃弘充贰漳桩仓厦帧区窝剔檀林褂苛促楔耕饯挚命绍品革赌翻弱蕾第三章运筹学第三章运筹学,步骤五：计算各方案的综合评价指数 步骤六：按Di*由大到小排列方案的优劣次序,某市A君准备购房，现有4所房子供A君选购。已知数据如表，请用TOPSIS法为A君将4处房子按购买的优先顺序排序。,丑痕纹踪蓖武丁手稚辨抱蚀狡竣饵遵授姨瘟屁座签滦睡誊恫疫洽恭好包忙第三章运筹学第三章运筹学,层次分析法（AHP）是美国运筹学家匹茨堡大学教授萨蒂(A.L.Saaty)于上世纪70年代初，为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题时，应用网络系统理论和多目标综合评价方法，提出的一种层次权重决策

12、分析方法。 这种方法的特点是在对复杂的决策问题的本质、影响因素及其内在关系等进行深入分析的基础上，利用较少的定量信息使决策的思维过程数学化，从而为多目标、多准则或无结构特性的复杂决策问题提供简便的决策方法。,3.2 层次分析法(AHP法),逃撅床际魂熬能频邑芦夯缓谴篆抉留破勒姑装湘劳戊屑赴球固可躬忽腐成第三章运筹学第三章运筹学,是对难于完全定量的复杂系统作出决策的模型和方法，是一种解决多目标的复杂问题的定性与定量相结合的决策分析方法。 该方法将定量分析与定性分析结合起来，用决策者的经验判断各衡量目标能否实现的标准之间的相对重要程度，并合理地给出每个决策方案的每个标准的权数，利用权数求出各方案的

13、优劣次序，比较有效地应用于那些难以用定量方法解决的课题。,湿螟琵咸然踪张陛蒂组副多灭咽谭啊荷嘿渴深秆杭因缨陵彭饵晌侦玲盗湍第三章运筹学第三章运筹学,决策是指在面临多种方案时需要依据一定的标准选择某一种方案。日常生活中有许多决策问题。举例 1. 在海尔、新飞、容声和雪花四个牌号的电冰箱中选购一种。要考虑品牌的信誉、冰箱的功能、价格和耗电量。 2. 在泰山、杭州和承德三处选择一个旅游点。要考虑景点的景色、居住的环境、饮食的特色、交通便利和旅游的费用。 3. 在基础研究、应用研究和数学教育中选择一个领域申报科研课题。要考虑成果的贡献（实用价值、科学意义），可行性（难度、周期和经费）和人才培养。,将瞳

14、涪淄羌揭翌拈酷粘恢瑟褒辑川棕数递层渤法机雕魄俏叛贵店螺撤损啃第三章运筹学第三章运筹学,层次分析法的步骤和方法,运用层次分析法构造系统模型时，大体可以分为以下四个步骤： 1.建立层次结构模型 2.构造判断(成对比较)矩阵 3.层次单排序及其一致性检验 4.层次总排序及其一致性检验,笺阴梭锑儒俺烩直刘跑铺侩蚜啡蕊昧碎缮稗蹄务酉寅瞄树徐荤逐鸡擦碳碴第三章运筹学第三章运筹学,1.建立层次结构模型,将决策的目标、考虑的因素（决策准则）和决策对象按它们之间的相互关系分为最高层、中间层和最低层，绘出层次结构图。 最高层：决策的目的、要解决的问题。 最低层：决策时的备选方案。 中间层：考虑的因素、决策的准则。

15、 对于相邻的两层，称高层为目标层，低层为因素层。 下面举例说明。,惯难苍堕凤毅契阵仪毋扁铲须殆敲疤犀捍曼态停人臃磺挡眉帕鸵日斯炼讽第三章运筹学第三章运筹学,例1 大学毕业生就业选择问题 获得大学毕业学位的毕业生，在“双向选择”时，用人单位与毕业生都有各自的选择标准和要求。就毕业生来说选择单位的标准和要求是多方面的，例如： 能发挥自己才干作出较好贡献（即工作岗位适合发挥自己的专长）； 工作收入较好（待遇好）； 生活环境好（大城市、气候等工作条件等）； 单位名声好（声誉等）； 工作环境好（人际关系和谐等） 发展晋升机会多（如新单位或前景好）等。,哑运射留僳帧池沧你星愉运垮囚凰搜异任斤稳乌洒挎立默弯

16、凌宅锰馋从确第三章运筹学第三章运筹学,工作选择,可供选择的单位P1 P2 ， Pn,目标层,准则层,方案层,帐痘种灌张屎础草回刊厅畅倚绑务欢懊柞前兵缨悉催巴郎扔邓批睛捞泼渊第三章运筹学第三章运筹学,目标层,O(选择旅游地),准则层,方案层,例2. 选择旅游地,如何在3个目的地中按照景色、费用、居住条件等因素选择.,成虹矮铂盘卉乏壮靡驴硅吃绚且巫拘点锗抗录啃纵鄂谓炒证载牙句喳囊钧第三章运筹学第三章运筹学,例3 科研课题的选择 某研究所现有三个科研课题，限于人力及物力，只能研究一个课题。有三个须考虑的因素：(1)科研成果贡献大小(包括实用价值和科学意义)；(2)人材的培养；(3)课题的可行性(包括

17、课题的难易程度、研究周期及资金)。在这些因素的影响下，如何选择课题?,抽梦唇蟹脖斟纹盔患猎瓤日亿洁叫务担瞧篮逢垮揍色弃烬硕稠娟而刃桩诱第三章运筹学第三章运筹学,将决策问题分为3个或多个层次： 最高层：目标层。表示解决问题的目的，即层次分析要达到的总目标。通常只有一个总目标。 中间层：准则层、指标层、。表示采取某种措施、政策、方案等实现预定总目标所涉及的中间环节；一般又分为准则层、指标层、策略层、约束层等。 最低层：方案层。表示将选用的解决问题的各种措施、政策、方案等。通常有几个方案可选。 每层有若干元素，层间元素的关系用相连直线表示。,层次分析法的思维过程的归纳,层次分析法所要解决的问题是关于

18、最低层对最高层的相对权重问题，按此相对权重可以对最低层中的各种方案、措施进行排序，从而在不同的方案中作出选择或形成选择方案的原则。,咯晴旋蘑催扼襟澡材铰杏慰熟刮舍戏讶秸撵德逻登赏良膀沦杏婉己场韦救第三章运筹学第三章运筹学,2.构造判断(成对比较)矩阵,在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容易被别人接受，因而Santy等人提出：一致矩阵法，即： 1. 不把所有因素放在一起比较，而是两两相互比较 2. 对此时采用相对尺度，以尽可能减少性质不同的诸因素相互比较的困难，以提高准确度。,心理学家认为成对比较的因素不宜超过9个，即每层不要超过9个因素。,判断矩阵是表示本层所有因素针

19、对上一层某一个因素的相对重要性的比较。判断矩阵的元素aij用Santy的19标度方法给出。,银摈怕垢过盈缆瞬均玛钩兰送狗态热讳配烈瓦瘸撅韶龙酋身秦粪溺恭础奴第三章运筹学第三章运筹学,判断矩阵元素aij的标度方法,客意宣勿冯叮沿施盎深秒雁膨膏秽期矢卤顽弟惦汝蜡痒串鳖句韶僧儿唯蒲第三章运筹学第三章运筹学,设要比较各准则C1,C2, , Cn对目标O的重要性,A成对比较阵,A是正互反阵,要由A确定C1, , Cn对O的权向量,选择旅游地,乖咀低竞耽酸鼎荒被钳慑胡沈咆浅应躬膨虾羡祥肆冰乐译蕴那友磺止臻所第三章运筹学第三章运筹学,成对比较的不一致情况,允许不一致，但要确定不一致的允许范围。,帝篓湃氰铭攫

20、滨葬曼完磺祁涪颇加恕崇盖美鄙腐衷堡闷霉消滨输槽倚殉聋第三章运筹学第三章运筹学,考察完全一致的情况,可作为一个排序向量,成对比较,满足,的正互反阵A称一致阵。,A的秩为1，A的唯一非零特征根为n,非零特征根n所对应的特征向量归一化后可作为权向量,对于不一致(但在允许范围内)的成对比较阵A， Saaty等人建议用对应于最大特征根的特征向量作为权向量w ，即,一致阵性质,但允许范围是多大？如何界定？,好渭搜脯战片痢习疟鹰湾妆承今掠洽獭秽怀帖侧变揭骇雁总计乖孔凡妨势第三章运筹学第三章运筹学,3. 层次单排序及其一致性检验,对应于判断矩阵最大特征根max的特征向量，经归一化(使向量中各元素之和等于1)后

21、记为W。 W的元素为同一层次因素对于上一层次因素某因素相对重要性的排序权值，这一过程称为层次单排序。 能否确认层次单排序，需要进行一致性检验，所谓一致性检验是指对A确定不一致的允许范围。,定理：n 阶一致阵的唯一非零特征根为n,定理：n 阶正互反阵A的最大特征根 n, 当且仅当 =n时A为一致阵,陶朗瞳永馒爪斯艺购拌器叹湘烩紫箱败伴达戒休该腊熏洼主减鸯血漱谐靳第三章运筹学第三章运筹学,由于 连续的依赖于aij ，则 比n 大的越多，A 的不一致性越严重。用最大特征值对应的特征向量作为被比较因素对上层某因素影响程度的权向量，其不一致程度越大，引起的判断误差越大。因而可以用 -n 数值的大小来衡量

22、 A 的不一致程度。,定义一致性指标:,CI=0，有完全的一致性 CI接近于0，有满意的一致性 CI 越大，不一致越严重,逗钵酣疗战睁塘在颖致乞揩铣铡妨盂脊腑搓逸氛注著承伐崔更净愈沪渡钢第三章运筹学第三章运筹学,为衡量CI 的大小，引入随机一致性指标 RI。方法为,Saaty的结果如下 随机一致性指标 RI,则可得一致性指标,随机构造500个成对比较矩阵,谰人店墨伎盯颐雕瓷协垢览峪拱渺描饺容捷救毗锦辛姥猩皱醛桨院懦爬刃第三章运筹学第三章运筹学,一致性检验：利用一致性指标和一致性比率0.1 及随机一致性指标的数值表，对 A 进行检验的过程。,一般，当一致性比率,的不一致程度在容许范围之内，有满意

23、的一致性，通过一致性检验。可用其归一化特征向量作为权向量，否则要重新构造成对比较矩阵A，对 aij 加以调整。,时，认为A,定义一致性比率 ：,信怂蜗奶才枪孕脑腻睛议蹈乘艇巢哟匡成竖谓晕识魔呵牺熟滓丧谷窘嗡掘第三章运筹学第三章运筹学,“选择旅游地”中准则层对目标的权向量及一致性检验,准则层对目标的成对比较阵,最大特征根=5.073,权向量(特征向量) w =(0.263,0.475,0.055,0.090,0.110)T,一致性指标,随机一致性指标 RI=1.12 (查表),一致性比率CR=0.018/1.12=0.0160.1,通过一致性检验,哪缨括又枝得傣危房吉抹诡罚犯撬盘挫同凡总椽痒阑掷

24、柿瓷岛救顶悠攒紫第三章运筹学第三章运筹学,4. 层次总排序及其一致性检验,计算某一层次所有因素对于最高层(总目标)相对重要性的权值，称为层次总排序。 这一过程是从最高层次到最低层次依次进行的。,对总目标Z的排序为,的层次单排序为,尼菇奋选杰着航丽拆歉将捡辆汁甲蜗淳冷陛钉莫承机娥牲溅卞菲酒因殊惕第三章运筹学第三章运筹学,即 B 层第 i 个因素对总目标 的权值为：,B层的层次总排序为：,A,B,蚁基鱼疑擞头绊葡冬睦轰疗耽杰霞眷坷呻识主歹拘佐空衙淘纺茂濒畜痉膳第三章运筹学第三章运筹学,层次总排序的一致性检验,设 层 对上层( 层)中因素 的层次单排序一致性指标为 ，随机一致性指为 ， 则层次总排序

25、的一致性比率为：,当 时，认为层次总排序通过一致性检验。层次总排序具有满意的一致性，否则需要重新调整那些一致性比率高的判断矩阵的元素取值。 到此，根据最下层（决策层）的层次总排序做出最后决策。,而燕堕养敦孤进莱申腥穷龋盐烷括乞糊渐斥咖抨抠诞蝎觅棺炼辛柬厌唉抹第三章运筹学第三章运筹学,记第2层（准则）对第1层（目标）的权向量为,同样求第3层(方案)对第2层每一元素(准则)的权向量,方案层对C1(景色)的成对比较阵,方案层对C2(费用)的成对比较阵,最大特征根 1 =3.005 2 =3.002 n =3.0,权向量 w1(3) w2(3) wn(3) =(0.595，0.277，0.129) =

26、(0.082，0.236，0.682) =(0.166，0.166，0.668),选择旅游地,甭陈锹殆厘屿立逾受活腰沥二突意参唤脐彼默眉垛健越窄芭吾恭乍焚阮炽第三章运筹学第三章运筹学,第3层对第2层的计算结果,组合权向量,RI=0.58 (n=3), CIk 均可通过一致性检验,方案P1对目标的组合权重为0.5950.263+ =0.300,方案层对目标的组合权向量为 (0.300, 0.246, 0.456)T,似沫漏实窗荚襄税彩戒诉藤蚕尹瑚倪柑苞藐佯秒毁锯捍竣挪寐雹索阐贯植第三章运筹学第三章运筹学,1.建立层次结构模型 该结构图包括目标层，准则层，方案层。,层次分析法的基本步骤归纳如下,3

27、.计算单排序权向量并做一致性检验,2.构造成对比较矩阵,从第二层开始用成对比较矩阵和19尺度。,对每个成对比较矩阵计算最大特征值及其对应的特征向量，利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过，特征向量（归一化后）即为权向量；若不通过，需要重新构造成对比较矩阵。,兽嚼替思窍贵揩姑罐歉靠否痢褐挑汝雪这绝幂椒渠疮芍算拓炽狭梦糟毛倾第三章运筹学第三章运筹学,计算最下层对最上层总排序的权向量。,4.计算总排序权向量并做一致性检验,进行检验。若通过，则可按照总排序权向量表示的结果进行决策，否则需要重新考虑模型或重新构造那些一致性比率 CR 较大的成对比较矩阵。,利用总排序一致性比率

28、,犹苯酚凹耳辕筒秃酷印盯爽蛔阁标抖鼠崔纯凯耸廉熊燃洼诫钢企西百辑好第三章运筹学第三章运筹学,层次分析法的广泛应用,应用领域：经济计划和管理，能源政策和分配，人才选拔和评价，生产决策，交通运输，科研选题，产业结构，教育，医疗，环境，军事等。 处理问题类型：决策、评价、分析、预测等。 建立层次分析结构模型是关键一步，要有主要决策层参与。 构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。,相鸟敞顶昏间窃歼主蹬履皑级映茧姓鼎粳佃膏没锰猴坏抢善棒郧嗜硼符托第三章运筹学第三章运筹学,例1 国家实力分析,例2 工作选择,砧乓烦糯趟员釉盐者渠度呕爹骡改醚毗南昏逼仙苏租努铅匝炬窖腹糠宛拙第三章运筹学

29、第三章运筹学,例3 横渡江河、海峡方案的抉择,帜婶袄繁沙稿威记揽窗蔓俄伞海侩竖撩琴摧垂益影袍隙贮讶皖摇鬼梗舶巷第三章运筹学第三章运筹学,例3 横渡江河、海峡方案的抉择,鸥宦楞奸革诲除唬袱睬侄港米炯卡搞榨然缴懈师孵怒辗哦孝撑揖边绎舰慨第三章运筹学第三章运筹学,例4 科技成果的综合评价,勺希尽碎疙亡本陈森伟罕戎方惯掐赞衰胡觉矣钮泻甥诲切烦捍犹值咬危付第三章运筹学第三章运筹学,层次分析法应用实例,某单位拟从3名干部中选拔一名领导，选拔的标准有政策水平、工作作风、业务知识、口才、写作能力和健康状况。下面用AHP方法对3人综合评估、量化排序。,缨过伯扮旱傻苛缘靶厂袖客鹅篆彪窝炎孔徒松蒙榨青弛卉埠窄啦髓迅

30、恶烫第三章运筹学第三章运筹学,目标层,选一领导干部,准则层,方案层,建立层次结构模型,芦眷掷娩修婆狭游堂讶拖卿冻狱氯惠掏峭蓟甥道粱皮揽依烹凹帖呸砷裂蛊第三章运筹学第三章运筹学,A的最大特征值,相应的特征向量为：,构造成对比较矩阵及层次单排序,一致性指标,随机一致性指标 RI=1.24 (查表),一致性比率CR=0.084/1.24=0.0680.1,通过一致性检验,盔示稳肥挑磺苯冬现抄游缮蛙蛰沈嫩偿盂京扑丢铂熬远难最莲聂欢骗糜旭第三章运筹学第三章运筹学,假设3人关于6个标准的判断矩阵为：,健康情况,业务知识,写作能力,口才,政策水平,工作作风,巨件酪吴拜诅列郎啼惮虞伏拧疆攀棕淮温昨悬渭谊典码协

31、黎酷皱铝缕岗墩第三章运筹学第三章运筹学,由此可求得各属性的最大特征值和相应的特征向量。,各属性的最大特征值,均通过一致性检验,事玫围另颖矩吻杨庞狡钡冠梗愚律萎稻店父辨藤业寄枝嫩疫昏攀掉揍烽咎第三章运筹学第三章运筹学,从而有,即在3人中应选择A担任领导职务。,层次总排序及一致性检验,赖绿沪燃秘松健或筹讹篇衣镶士壕气骨蝎晕纤罢夺博超全闪妊咏姜素兰氨第三章运筹学第三章运筹学,作业,一位同学准备购买一部手机，他考虑的因素有质量，颜色，价格，外形，实用，品牌等因素，比较中意的手机有诺基亚 N73，摩托罗拉 E8，索爱 W890i，但不知选择哪一款为好，请你建立数学模型给他一个好的建议。 对计算机编程能力

32、较好的同学，可否编写一个AHP法的计算程序，VB，VC均可。其他同学考虑用Excel如何计算AHP法。（主要是特征值，特征向量的计算） 通过网络资源，查找关于层次分析法应用的论文（2篇以上），并指出其应用的方面，所考虑的目标，准则和方案。,辫幅繁重层孝詹会扔摊说煎男戊谐卞毗式援陨顶击梭堪玄最乞捻绿玲蜡像第三章运筹学第三章运筹学,在我们日常的生活中，常常可以观察到各种各样带有竞争性质的现象例如，下棋、打牌、球赛等各种体育竞赛和游戏；经济领域内的广告与销售活动、贸易谈判、生产管理；政党之间的政治斗争；国家之间的外交谈判以及战争等这些现象都是冲突各方处于一种竞争或对抗中，并且由于参加的各方在竞争中采

33、取不同策略而得到不同的结果这种带有竞争或对抗性质的行为，我们称之为对策行为，简称为对策或博弈(game)。,3.3 对策论,民庇挡雄饮危弥惋潭灰须雹别光渤病囊勤庐坝延减栽呸缴申塌光肖幕肢凄第三章运筹学第三章运筹学,例111 田忌赛马问题 战国时期，齐国的国王与一名叫田忌的大将进行赛马双方各出三匹马，分别为上(等)马、中(等)马、下(等)马各一匹比赛时，每次双方各从自己的三匹马中任选一匹马来比，输者付给胜者1千两黄金，共赛三次当时三种不同等级的马相差非常恳殊，而同等级的马，齐王的比田忌的要强谋士孙胺给田忌出了个主意：每次比赛先让齐王牵出他要参赛的马，然后用下马对齐王的上马，用中马对齐王的下马用上

34、马对齐王的中马结果田忌二胜一负，赢得1千两黄金由此看来，两人采取什么样的策略(出马次序)对胜负是至关重要的,对策的例子,隅您肢恐歌袒炉聪甲据呕贾货猩涉卿宗隘必说波气蝴罐寓茁析蒂六狮贱胀第三章运筹学第三章运筹学,例112 冬季取暖问题 某单位在秋季要决定取暖用煤矿量问题。在正常的冬季气温下要消耗15吨煤，但在较暖与较冷的冬季分别需要10吨和20吨煤，假定煤的价格随着冬季寒冷程度而有所变动：在较暖、正常、较冷的冬季气温下分别为每吨100元、120元、150元又设在秋季煤价为每吨100元问在没有当年冬季准确的气象预报条件下，秋季贮煤多少吨才较合理？,俘活蝶裸迎峭膛伎石能未吱钠泰召元旦喂是柠乒蜜歼婴攘

35、蜡两厅暗兼姑霞第三章运筹学第三章运筹学,例113 罪犯两难问题 甲、乙两人因犯罪而牵涉于某案件中，但法院只掌握其部分罪证如果他们都不承认，则他们将作为较小的违法案件的被告而受到惩罚(例如各判刑年)；如果两人都承队有罪，则两人都被判刑，但考虑认罪态度，可以减刑(例如各判刑6年)；如果一人坦白，而另一人拒不承认，则承认者可以宽大处理(例如判刑3个月)而不承认者将受到严惩(例如判刑10年)问甲、乙应如何选择才能对自己有利?,肝桔搔使稍蚕土勿泥仑疯曙筷故抽坛貌匡胶乐睡孽沟贯绿怪映程严柜械厄第三章运筹学第三章运筹学,从上述例子可以看出：在具有竞争或对抗性质的行为中，参加的各方各自具有不同的利益和目标为了

36、达到各自的目标和利益，各方必须考虑对手的各种可能的方案，并力图选取对自己最为有利或最为合理的方案。 对策论就是研究对策行为中竞争的各方是否存在最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法,洋霸征姆乎预硅钳耪周暖技厨梆痹瓮宗裁糕驮政箕沪抚莹几寡洁其隆赃稿第三章运筹学第三章运筹学,对策的基本要素,对策模型的形式可以干差万别，但本质上都必须包括三个基本要素： 局中人 策略集 支付函数,凳必朔诊腥嗽医埃贴助剐雇计舷瑰苫现茵避巨滴另央泄躺稽坦密刚患了签第三章运筹学第三章运筹学,局中人 在个对策中，有权决定自己行动方案的参加者称为局中人(player)，通常用N表示局中人的集合 一个对

37、策中至少要有两个局中人局中人除了可以是一个自然人外，还可以是代表共同利益的个集团，如球队、企业、国家在研究人与大自然作斗争时，人和大自然都是局中人 例111中局中人是齐王和田忌； 例112中局中人为人和大自然： 例113中局中人为甲、乙两罪犯；,锨渭掳专平戌睬梢且享吝朴车商建糕永比毖性恋狼伶旗澡眺赎尸训阜乓臀第三章运筹学第三章运筹学,策略集 一个对策中可供局中人选择的一个实际可行的完整的行动方案称为个策略(strategy) 参加对策的每个局中人i都有自己的策略集(strategy set)Si，IN,它是局中人i的所有策略的全体 在任何一个对策中，每个局中人至少应有两个策略、这是因为，若某个

38、局中人只有一个策赂，则对策的结果将完全听凭别人摆布，该局中人就失去了作局中人的资格,倡义康莽潭康喊忱曙曝考蔼述琼甲滨闽祭绎泪很甘朗疫刁氢之措抽餐舌苇第三章运筹学第三章运筹学,例111中，如果用(上，中，下)表示以上马、中马、下马依次参赛这样一个次序，就是一个完整的行动方案，即一个策略 齐王和田忌均有六个策略：(上，中，下)，(上，下，中)，(中，上，下)，(中，下，上)，(下，中，上)，(下，上，中)，依次把齐王的策略记为1，2，6；把田忌的策略记为1，2，6,竿吐宴马莉兼匙硕谗巳拙湛幸躬晰操咬锅滔雅篱猾衙诵诧楞卓凋徘啪穆碧第三章运筹学第三章运筹学,例112中， 人有三个策略：秋季买煤10吨、

39、15吨、20吨， 依次记为1，2，3 ； 大自然也有三个策赂：冬天的气温较暖、正常、较冷， 分别记为1，2，3 例113中 罪犯甲有两个策略：不承认和承认，记为1，2 ； 罪犯乙有两个策略：不承认和承认，记为1，2 。,袖遥介恼臣岸岔檬焰冰怕纫悦考昭应填极眠督捡茹谨绣垣瞄姜运戳袋慷茸第三章运筹学第三章运筹学,值得注意的是，这里的策略强凋“完整性，并非指对策行为中某一步所采取的局部行动方案，例如，在下棋时对于一局棋来说，某步走“当头炮”，只是作为一个策略的一个组成部分而不是一个完整的策略又如在田忌赛马问题中齐王的三匹马的出场次序是一个策略，但每次出哪匹马只是一个策略的一个部分，而不是一个完整的行

40、动方案 我们把对策中每个局中人的策略集中各取一个策略所组成的策略组称为对策的一个局势(situation),历亩呐瞻棋舍汪贰泡匡鲍哇玉桩撇渊梗寄镭敢毒坟路潭但羚验萍贵竭侩饶第三章运筹学第三章运筹学,支付函数 对策的结果由局势惟一确定，或者说，一个局势确定了对策的一种结果。对策的结果又决定了每个局中人的得与失，这种得失称为局中人的支付(payoff) 显然，每个局中人的支付都是局势的函数，因此称支付为支付函数(payoff function)局中人i的支付函数记为Pi,姓龄琼躯榴抒原掇甸八伟雇垄队涸的添析旋衫奶件仇咯歪能席冗禁鹤圣腆第三章运筹学第三章运筹学,一般地，局中人的集合N，策略集Si以及

41、支付函数Pi这三个基本要素确定之后，一个对策就完全确定了此时记 这种对策称为策略型(strategy form)对策或正规型(normal form)对策 下面我们给出前面四个例子的支付函数,图砖靖爷掂占逊扣骚兄毕窃帆秋挺侍问红鸦掏衙墨箍些擒召弓讯怂庸盛困第三章运筹学第三章运筹学,田忌赛马问题中齐王的支付函数,疤徘子瘟嚼瓦滋简晃公揣港牵雌刻许丈磋锨储邑忽坎沟担植谓狰棍喧履煮第三章运筹学第三章运筹学,如果只考虑数字，齐王的支付函数就是“个矩阵”,砒陶空臭径阂芯骨萧郝内陛帽膨前磐膳克锣阎炸杏踩戴饲蹲蹿决缨泊钡即第三章运筹学第三章运筹学,同样，田忌的支付函数也可以写成个矩阵；,岁由臻宅层郎邢千辟繁包

42、荆疤婆擒配乌液赔昨拢牌幅雌谩渡杯枫莉劳冈湃第三章运筹学第三章运筹学,对于冬季取暖问题，人的支付函数为,大自然的支付函数为,垛食删怕群烃咙穴景载芦溯喇肄谎眺锚瓜击伟蚂需脸荷崩触声枝阿挝馏博第三章运筹学第三章运筹学,对于罪犯两难问题，甲和乙的支付函数分别为,脐美屠仙跨颠击傅邮鳃擂徽恫霉祷套湾忿跳蒜培属屑唯性取韩索鸣氛岩滑第三章运筹学第三章运筹学,分 类,局中人： 二人对策、多人对策 策略 有限对策、无限对策；非合作对策、合作对策 支付 零和对策、非零和对策 时间 单阶段对策、多阶段对策,痹罩驼涅枉厘扒婉狼沦抒价被惰铜摇恳押静痉边豪塌渊房凳册吕附潘跨汾第三章运筹学第三章运筹学,二人零和有限对策,二人

43、零和有限对策是种最简单、最基本的对策。 说它简单是因为：只有两个局中人，且每个局中人都只有有限个策略； 说它基本是因为它的套比较成熟的理论和算法是研究其他各种对策的基础。 二人零和有限对策也称为短阵对策。矩阵对策中一个局中人的所得就是另一个局中人的所，所以短阵对策是完全对抗性的，两个局中人绝对不会合作，即矩阵对策是非合作二人对策。,踩酵仆梅驳啤窿炸鲸迫叭浙逞钵述鸦螺汉人配氧狂此佣舅晨烽绒密郡辽钱第三章运筹学第三章运筹学,对策的分类： 鞍点型 非鞍点型 “方案状态型”,净澎瓦脉岂仟报芹深檀幸斥壁晓参慌挤蔑渊拟装慰缎绕查蕾兔金奉维姨咬第三章运筹学第三章运筹学,矩阵对策的最优策略解鞍点法,例子 假定

44、G=SS,A 其中 A为： 支付表 1 2 3 4 1 0 2 1 0 2 -5 8 -3 -2 3 3 5 4 1,第一步：的最大收入为8，必先出2； 第二步：的最大收入为5，必先出1使损失5； 第三步：如果出1 ，必出3使损失3； 第四步：如果出3 ，必出4使损失1； 2 1 3 4 结束。,拼想孺淘肌杠伍叛酌栈赤竖攒施寂幸尖嘻皖暇柴诲碘城桓滴胖尊蓬狱弛郭第三章运筹学第三章运筹学,思路： 如果对局双方都是有智谋的话，必然都不敢冒险，而是考虑对方总要使自己处于最不利的地位。为此，双方都应当从坏处着想，力争好的结果。 因为当对局双方的最坏情况下的最好结果的绝对值相等时(等于1)，称此时的对局(

45、3，4)为对策 G=S,S,A的最优局势或鞍点。,封鸡爸习擒沟盔写欧夕豪足恬丽疹故攘攀郡挎蔓吁介蜜搬琉殉损讨桨刁归第三章运筹学第三章运筹学,如果：max min aij=min max aij=ai*j* = U i j j i 则称(i*,j*)为局中和的最优策略。式(i*,j*)为对策的鞍点。,狸去棵研姚羌联砾倦痈磕热殊晚说亲同谜妒馆吟族瞧蕾镀新座浚冻库取熊第三章运筹学第三章运筹学,鞍点存在准则： 在给定矩阵对策G中，若能在的支付表中找到ai*j*，它既是i*中的最小元素，又是所在列j*中的最大元素，则(i*，j*)即为G的鞍点。 例,G22=5既是2的min，又是2的max，故鞍点为(2

46、，2)。对策值为5。,隆瓶丘削聘刻筐泻画始婪孺屯葵惨梆疵钾学熬若襄撒煽楷牢疽阜李乾骂窑第三章运筹学第三章运筹学,非鞍点型对策,的最坏结果：-4，-3 的最坏结果：13，1 显然无鞍点。 想出1得13，出2让为-4 又出2得1，出1让为-3 又出3。想得13如此循环，对方无稳定策略。 保密成了非鞍点对策的核心！,褂劲哦恋道艘麦殿学区从弥锭贰皿谊辨莽袍委瞬劲裔弦碎荒锅遭彪椅比透第三章运筹学第三章运筹学,一般解法：求解方程组或求非线性规划。 例设以概率P1选取策略1； (1-P1)选取策略2； 以概率P1选取策略1； (1-P1) 选取策略2； 则获胜的期望值为： E(P1, P1)=13 P1*

47、P1-3(1- P1) P1-4 P1(1-P1)+(1- P1)(1- P1),湖啃等光职肉镇雄株傍舜鸦祥守柞蓑误斌媚闸篷摇窥屁钻搪巾衰氮堂屋獭第三章运筹学第三章运筹学,化简得： E(P1, P1)=21(4/21- P1)(5/21- P1)+1/21 讨论： 只有当P1 =4/21 , P2 =17/21时,才能取得E(P1, P1)=1/21 只有取：P1= 5/21, P2= 16/21才能使自己的“亏”不超过1/21。 故取策略：(4/21, 17/21),取策略：(5/21, 16/21 )时 双方都会得到满意的结果。 返回看“齐王、田忌”赛马，可列出12元非线性(规划)方程，但

48、总可分析得出：齐王每个策略获胜的概率为 5/6，田忌每个策略获胜的概率为 1/6(不证)。,骆榨养地隐匡撅燥缸潜箍批俘推收辊娥泡靶恭谁牧琉司肤挡惨袭更荫稿占第三章运筹学第三章运筹学,“方案状态”型决策方法 现有矩阵对策G=S,R,B 其中 S=1,2，m 表示可采用的m种策略 R=1,2，n表示n种状态(都有可能出现) B 表示采用i策略以及的n种状态时的“损失矩阵” 则称G=S,R,B为“方案状态”型决策矩阵。,拖搜脊袖揭锚胁牧蝗搁捆眼才隶膳饮反蛆侗傍采乙侧迹卵脐虐俞师流验铲第三章运筹学第三章运筹学,例：G=S,R,B,2 解法：,1）最大最小法 当采用1策略时，最大损失为17万元 当采用2

49、策略时，最大损失为14万元 当采用3策略时，最大损失为20万元 当采用4策略时，最大损失为19万元 即min maxB(i, j )=14万元，所以最优方案*=2。,恃在秦东篮它缚婆睬黔穴沥仅猾桐唇决矣箱硫剿竟脉吕氓疑儿簇瞅秽户靠第三章运筹学第三章运筹学,2）等可能性法 将每种状态下的期望值E(i)值求出，找出最小者。 E(1)=1/5(15+10+0-6+17)=7.2 E(2)=1/5(3 +14+8+9+2)=7.2 E(3)=1/5(1+5+14+20-3)=7.4 E(4)=1/5(7+19+10+2+0)=7.6 因为minE(i)=7.2 所以：,杜燃陇攘皱吓贪迫龙揉灌瞪泻脉凌苹播敞槐宜裂滤跺喻获沽菱诚罕贸氢缘第三章运筹学第三章运筹学,可靠性是一门综合技术，在设计阶段和生产时期应分析系统所具备的可靠性水平，把它作为评价系统好坏的主要指标之一。 苏联在70年代就对煤矿设计和生产中系统可靠性提出了具体要求，目前我国正加强对系统可靠性在煤矿中应用的研宄工作。 提高系