高级运筹学-第1章：对策论

《高级运筹学-第1章：对策论》由会员分享，可在线阅读，更多相关《高级运筹学-第1章：对策论（29页珍藏版）》请在金锄头文库上搜索。

1、1,第 1 章：对策论,1.1 基本概念一、竞争现象 各种比赛：体育、棋类等比赛。 政治方面：外交谈判。 经济方面：贸易谈判，争夺市场，各种经营竞争等。 工业生产方面：多创价值。例1-1.齐王与田忌赛马：他们各有上等、中等、下等马各一匹，且同级马，齐王比田忌强些。双方 约定：每局比赛三场，每负一场者应付1千金，且每匹马都应参加比赛。结果田忌以 O：3 输了后请教孙膑，则采用如下策略反败为胜，结果田忌二胜一负，实得1千金。,2,例1-2.两小孩玩石头、剪刀、布的游戏：甲、乙两小孩出的手势都有可能是石头、剪刀、布， 若他们三次出的手势如下图，则乙小孩二胜一负。,二、竞争现象的特点 双方均有理智：为

2、击败对手，可随机应变改变策略(多为保密)。 实力强者：稳扎稳打以优势取胜。 实力弱者：避开对方优势锋芒，打击对方弱点取胜。 在经济管理对策中：把非理智的客观世界设想为“理智人”，并与之斗争。三、对策论的概念 研究竞争现象的一种定量分析理论。三、对策论的起源 1 我国古代围棋比赛和17世纪欧洲国际象棋比赛 形成模拟模型。 2 1912年，数学家翟墨罗发表论文“把集合论应用于象棋的博奕理论”， 把对策从模拟模型抽象为数学模型。 3 第一次世界大战期间，产生了军事对策(战役、战略、军事装备等)。 4 1944年，冯诺意曼与经济学家摩根斯特恩合写“对策论与经济行为”,把对策论应用于经济管理。 5 我国

3、公元前六世纪(春秋)“孙子兵法”13篇。,3,四、对策 参加竞争的各方为了取胜，而研究出一组对付对方的策略。五、对策的三要素 1 局中人：参加竞争，并有决策权的各方(二人或多人)。 如：齐王和田忌。 2 策略：在一局竞争中，每一局中人均有供他选择的实际可行的完整行动方案。 如例1-1，齐王有6个策略：(上中下)，(上下中), (中上下), (中下上),(下上中), (下中上) 田忌有6个策略：(上中下)，(上下中), (中上下), (中下上),(下上中), (下中上) 如例1-2，甲小孩有3个策略：石头，剪刀，布 乙小孩有3个策略：石头，剪刀，布 3 一局对策的得失：局中人的得失。叫支付函数，

4、对有限策略集，叫支付矩阵。 如：齐王出策略(上中下)，田忌出策略(中上下)， 则齐王二胜一负，赢得1千金；田忌损失1千金。六、局势 每个局中人从各自的策略集合中选取一个策略参加对策，形成的一个处于竞争的策略组。 如：齐王选策略(上中下)，田忌选策略(中上下)，构成一个局势(上中下)，(中上下)。 局势的得失总和为0。七、对策的分类,4,对策,5,1.2 支付矩阵有鞍点的二人有限零和对策一、特点 1 策略公开。 2 得失确定且总和为零：一方所得必为另一方所失，局中人利益冲突(对抗对策)。 3 单局竞争决定胜负。 二、建模：建立支付函数，这里是支付矩阵(也叫矩阵对策问题) 设局中人甲有m个纯策略

5、S甲= 1,2,m，局中人乙有n个纯策略 S乙= 1,2,n。 纯局势(i,j)得失为aij：当aij0时，甲赢得aij，乙损失aij； 当aij0时，甲损失-aij，乙赢得-aij。 构成支付矩阵 A：,对策可写成 G = 甲，乙，S甲，S乙，A。,6,如例1-1.齐王与田忌赛马：,则支付矩阵为：,7,如例1-2.两小孩玩游戏：,则支付矩阵为：,8,例1-3.某单位秋季要决定冬季取暖用煤的贮量。冬季用煤贮量在较暖、正常和较冷情况下分为 10、15和20吨。设冬季煤价也随寒冷程度而变，在上述三种情况下分别为340、420和500元/吨， 已知秋季煤价为340元/吨，冬季气象未能予知，问秋季合理

6、贮煤量为多少？解：建模，设局中人甲为：贮煤量决策者； 局中人乙为：未来冬季气候。 费用总和=秋季贮煤量费用+冬季补购煤量费用,则支付矩阵为：,9,二、求解 1 稳妥性原则 局中人在公开对策的前提下，都从最坏处着想，在最坏的环境中争取最好的结果。 例1-4 某企业决定由职工代表大会选举行政负责人，经提名产生候选人甲和乙。他们根据企业的 发展战略和群众关心的事业各自提出了企业改革的方案。甲提出了四种：1,2,3,4； 乙提出了三种：1,2,3。他们的参谋人员为使竞争对本方有利，予先作了个民意抽样 测验。因各方提供的不同策略对选票吸引力不同。测验选票经比较后差额如下表 (单位:十张)：,问：甲和乙在

7、竞选中应采用何种策略？,解：对策时，双方均理智，且发挥主动性。最后，甲用2竞选，领先2O票优势； 乙只能用2竞选，缩短票数差距。双方均认为只能如此，为双方妥协结果。,支付矩阵中：每行选最小值，这些最小值中选最大值V1；,每列选最大值，这些最大值中选最小值V2；,若 V1 = V2 ，则得最优解。,10,2 稳妥性原则数学表达： 对甲而言是最小最大原则：从支付矩阵每行元素中取最小数，再从这些最小数中取最大数，得,对乙而言是最大最小原则：从支付矩阵每列元素中取最大数，再从这些最大数中取最小数，得,若V1=V2=VG，则稳妥原则实现，VG为支付矩阵的稳定值即鞍点值，对应的纯策略i*,j*为 甲、乙的

8、最优纯策略，局势(i*,j*)为对策的最优解，即：,如例1-3.,甲用策略3，乙用策略3， 即 秋季购进煤2O吨，总费用最低为68OO元。,11,例1-5 某厂工程师设计了三个矿石冶炼(或选矿)流程，考虑到它们的所用设备和工艺环节等因素， 若付诸实施可会遇上生产正常和生产不正常两种情况,这两种情况的出现及其概率未能予知， 但三个流程在这两种情况下的单位支付费用已算出，如下表，问：选用哪个流程较好?,解：有二个鞍点局势(1,2)和(3,2) 甲用1，乙用2；甲用3，乙用2 最小支付费用为：1.7(百元/吨)。 所以应选“流程1” 或“流程3” 。,三、鞍点对策问题两个性质 1 解的稳定性 对策的

9、最终结局可在支付矩阵中得到双方均认可的妥协， 双方均认识到在原有策略中存在最优策略。 2 对策的公开性 双方均明确并可公开申明参加对策的最优策略，最优局势是双方妥协的结果， 反映双方策略的实力。,12,1.3 支付矩阵无鞍点的二人有限零和对策一、特点 1 策略保密性：图谋出奇制胜。 2 得失随机性：某局竞争的胜败难于予料，强者可败，弱者可胜。 3 多局竞争性：多局竞争后决定胜负。 二、建模：建立得失期望值函数 1 混合策略 设局中人甲有m个纯策略 S甲=1,2,m，局中人乙有n个纯策略 S乙=1,2,n。 纯局势(i,j)得失为aij，构成的支付矩阵A无鞍点。G = 甲，乙，S甲，S乙，A。

10、设甲以 x1,x2,xm 的概率取纯策略 1,2,m ， 则称概率向量 X = (x1,x2,xm)为甲的一个混合策略，xi0，x1+x2+xm=1， 甲的混合策略集记为 S(m)； 设乙以 y1,y2,yn 的概率取纯策略 1,2,n ， 则称概率向量 Y = (y1,y2,yn )为乙的一个混合策略，yi0，y1+y2+yn=1， 乙的混合策略集记为 T(n) 。 2 混合局势 (X,Y)称为混合局势。 3 得失期望值,13,如例1-2.两小孩共玩了10局游戏对策，最后总计谁胜谁负，设这10次游戏中： 甲随机出了 3次石头、3次剪刀、4次布，即甲采用混合策略 X = (0.3,0.3,0.

11、4)； 乙随机出了 0次石头、5次剪刀、5次布，即乙采用混合策略 Y = (0,0.5,0.5)。,支付矩阵为(无鞍点)：,得失期望值为：,所以，甲平均要输 0.05。,14,4 最优混合策略 定义:若 X*S(m),Y*T(n)，使对所有 XS(m),YT(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

12、。得失期望值为：,求甲、乙的最优混合策略。,解：, G无鞍点，两局中人无纯策略稳定解，斗争转入策略保密， 即求最优混合策略。, 当甲以 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， 是乙从稳妥原则出发能达到的最小期望损失值,而y,1-y=0.5,0.5=Y*是乙的最优混合策略， 当y取一值时，x可取另

13、外一值与其对抗，但当y=1/2时，x无论取何值都无法与其对抗。 故 X*=0.4,0.6，Y*=0.5,0.5 ，E(X*，Y*)=4 就是双方都感到只能如此的最好结果。,15, 存在性定理：任意一个给定的矩阵对策一定有解，局中人双方总有一个最优混合策略，即：,则 X*、Y* 为甲、乙的最优混合策略，(X*,Y*)为对策的解，对策值 V=V1=V2。, 定理1：若矩阵对策值为V，则下面两组不等式的解是局中人甲、乙的最优混合策略：, 定理2：若 X*、Y* 为甲、乙的最优混合策略，则对某一个i或j，有,16,5 支付矩阵的缩减：若存在优势策略，则支付矩阵阶数可降低 对局中人甲，他希望对策的局势值

14、 aij 越大越好： 若 第 i 行所有元素 第 L 行所有元素，即 aij aLj，j=1,2,n， 则甲理智，必采用 i 纯策略而舍去 L 纯策略，不影响最优混合策略和策略鞍点值。 此时称 i 策略为对 L 策略的优势策略。 对局中人乙，他希望对策的局势值 aij 越小越好： 若 第 j 列所有元素 第 K 列所有元素，即 aij aiK，i=1,2,m， 则乙理智，必采用 j 纯策略而舍去 K 纯策略，不影响最优混合策略和策略鞍点值。 此时称 j 策略为对 K 策略的优势策略。,例1-7 设有矩阵对策,注：无鞍点对策时，要求决策的不是每次局中人应选那个纯策略，而是决定用多大的概率选择 每一种纯策略，以期达到能平均反映各方纯策略实力的稳妥结果。,17,三、最优混合策略的求解方法 1 图解法：适用于缩减后的支付矩阵为2n或m2的无鞍点对策问题。,