高级运筹学(中南大学_徐选华)

1高级运筹学商学院管理科学与信息管理系AdvanceOperationResearchTel：13974812313主讲：徐选华E-mail：[e-mail]@public.cs.hn.cn2目录第1章：对策论第2章：模糊集合第3章：模糊关系第4章：模糊综合评判第5章：模糊模式识别第6章：模糊聚类分析第8章：数据包络分析第9章：非线性规划（选讲）第7章：层次分析法3第1章：对策论1.1基本概念一、竞争现象各种比赛：体育、棋类等比赛。政治方面：外交谈判。经济方面：贸易谈判，争夺市场，各种经营竞争等。工业生产方面：多创价值。例1-1.齐王与田忌赛马：他们各有上等、中等、下等马各一匹，且同级马，齐王比田忌强些。双方约定：每局比赛三场，每负一场者应付1千金，且每匹马都应参加比赛。结果田忌以O：3输了后请教孙膑，则采用如下策略反败为胜，结果田忌二胜一负，实得1千金。齐王田忌上等马上等马中等马中等马下等马下等马败胜胜4例1-2.两小孩玩石头、剪刀、布的游戏：甲、乙两小孩出的手势都有可能是石头、剪刀、布，若他们三次出的手势如下图，则乙小孩二胜一负。甲小孩乙小孩石头石头剪刀剪刀布布败胜胜二、竞争现象的特点双方均有理智：为击败对手，可随机应变改变策略(多为保密)。实力强者：稳扎稳打以优势取胜。实力弱者：避开对方优势锋芒，打击对方弱点取胜。在经济管理对策中：把非理智的客观世界设想为“理智人”，并与之斗争。三、对策论的概念研究竞争现象的一种定量分析理论。三、对策论的起源1·我国古代围棋比赛和17世纪欧洲国际象棋比赛—形成模拟模型。2·1912年，数学家翟墨罗发表论文“把集合论应用于象棋的博奕理论”，把对策从模拟模型抽象为数学模型。3·第一次世界大战期间，产生了军事对策(战役、战略、军事装备等)。4·1944年，冯·诺意曼与经济学家摩根斯特恩合写“对策论与经济行为”,把对策论应用于经济管理。5·我国公元前六世纪(春秋)“孙子兵法”13篇。5四、对策参加竞争的各方为了取胜，而研究出一组对付对方的策略。五、对策的三要素1·局中人：参加竞争，并有决策权的各方(二人或多人)。如：齐王和田忌。2·策略：在一局竞争中，每一局中人均有供他选择的实际可行的完整行动方案。如例1-1，齐王有6个策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}田忌有6个策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}如例1-2，甲小孩有3个策略：{石头，剪刀，布}乙小孩有3个策略：{石头，剪刀，布}3·一局对策的得失：局中人的得失。叫支付函数，对有限策略集，叫支付矩阵。如：齐王出策略(上中下)，田忌出策略(中上下)，则齐王二胜一负，赢得1千金；田忌损失1千金。六、局势每个局中人从各自的策略集合中选取一个策略参加对策，形成的一个处于竞争的策略组。如：齐王选策略(上中下)，田忌选策略(中上下)，构成一个局势{(上中下)，(中上下)}。局势的得失总和为0。七、对策的分类6对策动态对策静态对策结盟对策不结盟对策微分对策联合对策合作对策有限无限二人多人二人多人零和非零和零和非零和零和非零和零和非零和71.2支付矩阵有鞍点的二人有限零和对策一、特点1·策略公开。2·得失确定且总和为零：一方所得必为另一方所失，局中人利益冲突(对抗对策)。3·单局竞争决定胜负。二、建模：建立支付函数，这里是支付矩阵(也叫矩阵对策问题)设局中人甲有m个纯策略S甲={1,2,…,m}，局中人乙有n个纯策略S乙={1,2,…,n}。纯局势(i,j)得失为aij：当aij＞0时，甲赢得aij，乙损失aij；当aij＜0时，甲损失-aij，乙赢得-aij。构成支付矩阵A：mnmmnnaaaaaaaaaA212222111211对策可写成G={甲，乙，S甲，S乙，A}。8如例1-1.齐王与田忌赛马：1(上中下)2(上下中)3(中上下)4(中下上)5(下上中)6(下中上)1(上中下)31111-12(上下中)1311-113(中上下)1-131114(中下上)-1113115(下上中)11-11316(下中上)111-113齐王田忌aij则支付矩阵为：311111131111113111111311111131111113A9如例1-2.两小孩玩游戏：1(石头)2(剪刀)3(布)1(石头)01-12(剪刀)-1013(布)1-10甲乙aij则支付矩阵为：011101110A10例1-3.某单位秋季要决定冬季取暖用煤的贮量。冬季用煤贮量在较暖、正常和较冷情况下分为10、15和20吨。设冬季煤价也随寒冷程度而变，在上述三种情况下分别为340、420和500元/吨，已知秋季煤价为340元/吨，冬季气象未能予知，问秋季合理贮煤量为多少？解：建模，设局中人甲为：贮煤量决策者；局中人乙为：未来冬季气候。费用总和=秋季贮煤量费用+冬季补购煤量费用1(较暖)2(正常)3(较冷)1(10吨)-(10×340)=-3400-(10×340+5×420)=-5500-(10×340+10×500)=-84002(15吨)-(15×340)=-5100-(15×340)=-5100-(15×340+5×500)=-76003(20吨)-(20×340)=-6800-(20×340)=-6800-(20×340)=-6800甲乙aij则支付矩阵为：680068006800760051005100840055003400A11二、求解1·稳妥性原则局中人在公开对策的前提下，都从最坏处着想，在最坏的环境中争取最好的结果。例1-4某企业决定由职工代表大会选举行政负责人，经提名产生候选人甲和乙。他们根据企业的发展战略和群众关心的事业各自提出了企业改革的方案。甲提出了四种：1,2,3,4；乙提出了三种：1,2,3。他们的参谋人员为使竞争对本方有利，予先作了个民意抽样测验。因各方提供的不同策略对选票吸引力不同。测验选票经比较后差额如下表(单位:十张)：1231-40-623243161-94-117甲乙aij问：甲和乙在竞选中应采用何种策略？解：对策时，双方均理智，且发挥主动性。最后，甲用2竞选，领先2O票优势；乙只能用2竞选，缩短票数差距。双方均认为只能如此，为双方妥协结果。支付矩阵中：每行选最小值，这些最小值中选最大值V1；-62-9-1每列选最大值，这些最大值中选最小值V2；1627若V1=V2，则得最优解。122·稳妥性原则数学表达：①对甲而言是最小最大原则：从支付矩阵每行元素中取最小数，再从这些最小数中取最大数，得1minmaxvaijji②对乙而言是最大最小原则：从支付矩阵每列元素中取最大数，再从这些最大数中取最小数，得2maxminvaijij若V1=V2=VG，则稳妥原则实现，VG为支付矩阵的稳定值—即鞍点值，对应的纯策略i*,j*为甲、乙的最优纯策略，局势(i*,j*)为对策的最优解，即：jijiijaaa****鞍点行元素变化趋势列元素变化趋势如例1-3.680068006800760051005100840055003400A-8400-7600-6800-3400-5100-6800甲用策略3，乙用策略3，即秋季购进煤2O吨，总费用最低为68OO元。13例1-5某厂工程师设计了三个矿石冶炼(或选矿)流程，考虑到它们的所用设备和工艺环节等因素，若付诸实施可会遇上生产正常和生产不正常两种情况,这两种情况的出现及其概率未能予知，但三个流程在这两种情况下的单位支付费用已算出，如下表，问：选用哪个流程较好?1(生产正常)2(生产不正常)1(流程1)-1.5-1.72(流程2)-1.4-1.83(流程3)-1.4-1.7甲乙aij解：有二个鞍点局势(1,2)和(3,2)甲用1，乙用2；甲用3，乙用2最小支付费用为：1.7(百元/吨)。所以应选“流程1”或“流程3”。-1.7-1.8-1.7-1.4-1.7三、鞍点对策问题两个性质1·解的稳定性对策的最终结局可在支付矩阵中得到双方均认可的妥协，双方均认识到在原有策略中存在最优策略。2·对策的公开性双方均明确并可公开申明参加对策的最优策略，最优局势是双方妥协的结果，反映双方策略的实力。141.3支付矩阵无鞍点的二人有限零和对策一、特点1·策略保密性：图谋出奇制胜。2·得失随机性：某局竞争的胜败难于予料，强者可败，弱者可胜。3·多局竞争性：多局竞争后决定胜负。二、建模：建立得失期望值函数1·混合策略设局中人甲有m个纯策略S甲={1,2,…,m}，局中人乙有n个纯策略S乙={1,2,…,n}。纯局势(i,j)得失为aij，构成的支付矩阵A无鞍点。G={甲，乙，S甲，S乙，A}。设甲以x1,x2,…,xm的概率取纯策略1,2,…,m，则称概率向量X=(x1,x2,…,xm)为甲的一个混合策略，xi≥0，x1+x2+…+xm=1，甲的混合策略集记为S(m)；设乙以y1,y2,…,yn的概率取纯策略1,2,…,n，则称概率向量Y=(y1,y2,…,yn)为乙的一个混合策略，yi≥0，y1+y2+…+yn=1，乙的混合策略集记为T(n)。2·混合局势(X,Y)称为混合局势。3·得失期望值nmnmmnnmTYSXTyyyaaaaaaaaaxxxXAYYXEnm2121222211121121),,,(),()()(jijminjiyax1115如例1-2.两小孩共玩了10局游戏对策，最后总计谁胜谁负，设这10次游戏中：甲随机出了3次石头、3次剪刀、4次布，即甲采用混合策略X=(0.3,0.3,0.4)；乙随机出了0次石头、5次剪刀、5次布，即乙采用混合策略Y=(0,0.5,0.5)。1(石头)2(剪刀)3(布)1(石头)01-12(剪刀)-1013(布)1-10甲乙aij支付矩阵为(无鞍点)：011101110A得失期望值为：05.05.05.00011101110)4.0,3.0,3.0(),()()(nmSYSXTXAYYXE所以，甲平均要输0.05。164·最优混合策略⑴定义:若X*S(m),Y*T(n)，使对所有XS(m),YT(n),都有E(X,Y*)≤E(X*,Y*)≤E(X*,Y),则X*、Y*分别称为甲、乙的最优混合策略，(X*,Y*)为对策的解，E(X*,Y*)为对策值V。例1-6给定一个矩阵对策G={甲,乙,S甲,S乙,A}，S甲={1,2},S乙={1,2}，设甲以x,1-x的概率取纯策略1,2；乙以y,1-y的概率取纯策略1,2。得失期望值为：,2671A求甲、乙的最优混合策略。解：2671A1267ijijijjiaamaxmin62minmaxG无鞍点，两局中人无纯策略稳定解，斗争转入策略保密，即求最优混合策略。)21)(52(10412671)1,(),(yxyyxxYXE①当甲以x=2/5=0.4的概率选1时，其赢利期望值E(X,Y)=4，是甲从稳妥原则出发能达到的最大期望赢利值,而{x,1-x}={0.4,0.6}=X*是甲的最优混合策略，当x取一值时，y可取另外一值与其对抗，但当x=2/5时，y无论取何值都无法与其对抗；②当乙以y=1/2=0.5的概率选1时，其损失期望值E(X,Y)=4，是乙从稳妥原则