《高级运筹学-第1章：对策论》.ppt

第 1 章：对策论 1.1 基本概念 一、竞争现象 ? 各种比赛：体育、棋类等比赛。 ? 政治方面：外交谈判。 ? 经济方面：贸易谈判，争夺市场，各种经营竞争等。 ? 工业生产方面：多创价值。 例1-1.齐王与田忌赛马：他们各有上等、中等、下等马各一匹，且同级马，齐王比田忌强些。双方 约定：每局比赛三场，每负一场者应付1千金，且每匹马都应参加比赛。结果田忌以 O：3 输了后请教孙膑，则采用如下策略反败为胜，结果田忌二胜一负，实得1千金。 例1-2.两小孩玩石头、剪刀、布的游戏：甲、乙两小孩出的手势都有可能是石头、剪刀、布， 若他们三次出的手势如下图，则乙小孩二胜一负。 1.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： 如例1-1.齐王与田忌赛马： 如例1-2.两小孩玩游戏： 二、求解 1· 稳妥性原则 局中人在公开对策的前提下，都从最坏处着想，在最坏的环境中争取最好的结果。 例1-4 某企业决定由职工代表大会选举行政负责人，经提名产生候选人甲和乙。他们根据企业的 发展战略和群众关心的事业各自提出了企业改革的方案。甲提出了四种：?1,?2,?3,?4； 乙提出了三种：?1,?2,?3。他们的参谋人员为使竞争对本方有利，予先作了个民意抽样 测验。因各方提供的不同策略对选票吸引力不同。测验选票经比较后差额如下表 (单位:十张)： 例1-5 某厂工程师设计了三个矿石冶炼(或选矿)流程，考虑到它们的所用设备和工艺环节等因素， 若付诸实施可会遇上生产正常和生产不正常两种情况,这两种情况的出现及其概率未能予知， 但三个流程在这两种情况下的单位支付费用已算出，如下表，问：选用哪个流程较好? 1.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· 得失期望值 如例1-2.两小孩共玩了10局游戏对策，最后总计谁胜谁负，设这10次游戏中： 甲随机出了 3次石头、3次剪刀、4次布，即甲采用混合策略 X = (0.3,0.3,0.4)； 乙随机出了 0次石头、5次剪刀、5次布，即乙采用混合策略 Y = (0,0.5,0.5)。 4· 最优混合策略 ⑴ 定义:若 ? 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}