运筹学模型与软件求解(第九章).ppt

1、运筹学模型与软件求解运筹学模型与软件求解中国科学院研究生院中国科学院研究生院 Models and Software Solutions of the Operations Research第九章第九章 对策模型与试验对策模型与试验对策论的基本概念对策论的基本概念 混合对策混合对策 线性规划方法解（线性规划方法解（m*nm*n）对策）对策 概概 论论 名称名称 Game Theory 博奕论博奕论发展历史发展历史对策论模型对策论模型例例 子子发发 展展 简简 史史早期工作早期工作1912年年E.Zermelo 关于集合论在象棋对策中的应用关于集合论在象棋对策中的应用1921年年E.Borel

2、引入最优策略引入最优策略1928年年J.V.Neumann证明了一些猜想证明了一些猜想产生标志产生标志1944年年J.V.Neumann和和O.Morgenstern”对策论与经济行为对策论与经济行为”发展成熟发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策均衡、经济博奕论、信息不对称对策和广义对策由由“齐王赛马齐王赛马”引入引入三个三个基本要素基本要素1.局中人：参与对抗的各方；局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人策略集：局中人选择对付其它局中人的行动方案称为的行动方案称为策略策略。某局中人的所有可能策略全体称某局中人的所有可能策略全体称为为策略集策略集；

3、3.局势对策的局势对策的益损值益损值：各局中人各自使用：各局中人各自使用一个对策就形成一个局势，一个局势决一个对策就形成一个局势，一个局势决定了个局众人定了个局众人 的对策结果（量化）称为的对策结果（量化）称为该局势对策的益损值）该局势对策的益损值）“齐王赛马齐王赛马”齐王在各局势中的齐王在各局势中的益损值表（单位：千金）益损值表（单位：千金）其中：其中：齐王的策略集齐王的策略集:S1=1,2,3,4,5,6田忌的策略集：田忌的策略集：S2=1,2,3,4,5,6 下列矩阵称下列矩阵称齐王的赢得矩阵齐王的赢得矩阵：3 1 1 1 -1 1 1 3 1 1 1 -1A=1 -1 3 1 1 1

4、-1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3 二人有限零和对策：（又称矩阵策略）二人有限零和对策：（又称矩阵策略）局中人为局中人为2；每局中人的策略集中策略个数有限；每局中人的策略集中策略个数有限；每一局势的对策均有确定的损益值，每一局势的对策均有确定的损益值，并且对并且对同一局势同一局势的两个局中人的益损的两个局中人的益损值之和为值之和为零零。记记矩阵对策为矩阵对策为:G=S1,S2,A 甲的策略集甲的策略集 甲的赢得矩阵甲的赢得矩阵 乙的策略集乙的策略集“齐王赛马齐王赛马”即是一个矩阵策略即是一个矩阵策略.在在甲方赢得矩阵中：甲方赢得矩阵中：A=aijm*n

5、i行代表甲方策略行代表甲方策略 i=1,2mJ列代表乙方策略列代表乙方策略 j=1,2naij代表甲方取策略代表甲方取策略i,乙方取策略乙方取策略j,这一局这一局势下甲方的益损值，此时乙方的益损值势下甲方的益损值，此时乙方的益损值为为-aij（零（零和性质）。和性质）。在讨论各方采用的策略是必须注意一个在讨论各方采用的策略是必须注意一个前提就是前提就是对方是理智的对方是理智的。这就是要从最。这就是要从最有把握取得的益损值情况考虑。有把握取得的益损值情况考虑。2.矩阵对策的最优纯策略矩阵对策的最优纯策略例：有交易双方公司甲和乙，甲有例：有交易双方公司甲和乙，甲有三个策略三个策略 1，2，3；乙有

6、四个策；乙有四个策略略 1，2，3，4，根据获利情况建，根据获利情况建立甲方的益损值立甲方的益损值 赢得矩阵。赢得矩阵。-3 0 -2 0 A=2 3 0 1 -2 -4 -1 3问：甲公司应采取什么策略比较适问：甲公司应采取什么策略比较适合？合？甲甲：采取采取 1至少至少得益得益3(损失损失 3）2 0 3 -4(损失损失 4）乙乙：采取采取 1甲甲最多最多得益得益2 （乙最少得益（乙最少得益-2）2 3（乙得益（乙得益-3）3 0（乙得益（乙得益 0）4 3（乙得益（乙得益-3）取大则取取大则取 2 2 max min max min a aijij=0=0 i ji j取小则取取小则取

7、3 3 min max amin max aijij=0=0 j j i i甲甲采取策略采取策略 2 不管乙采取如何策略，都不管乙采取如何策略，都至少得益。至少得益。乙采取策略乙采取策略 3 不管甲采取如何策略，不管甲采取如何策略，都至少可以得益。（最多损失都至少可以得益。（最多损失0）分别称甲，乙公司的最优策略，由唯一性分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。又称最优纯策略。存在前提：存在前提：max min aij=min max aij=v i j j i又称（又称（2，3）为对策）为对策G=s1,s2,A的鞍点。值的鞍点。值V为为G的值。的值。实际应用问题实际应用问题3.矩

8、阵对策的混合策略矩阵对策的混合策略设设矩阵对策矩阵对策 G=S1,S2,A当当 max min aij min max aij i j j i 时，不存在最优纯策略时，不存在最优纯策略 求解求解混合策略。混合策略。例：设一个赢得矩阵如下例：设一个赢得矩阵如下:min 5 9 5 A =max 6 策略策略 2 8 6 6 i max 8 9 min 8 策略策略 1 j矛盾：甲取矛盾：甲取 2，乙取时，乙取时 1，甲实际赢得，甲实际赢得8比预期多比预期多2（乙就少（乙就少2）这对乙讲是不满意）这对乙讲是不满意的，考虑这一点，乙采取策略的，考虑这一点，乙采取策略 2，若甲分若甲分析到这一点，取策

9、略析到这一点，取策略 1，则赢得更多为则赢得更多为9此时，甲，乙方没有一个双方均可接受的此时，甲，乙方没有一个双方均可接受的平衡局势平衡局势。一个思路：对甲（乙）给出一个选取不同一个思路：对甲（乙）给出一个选取不同策略的策略的概率分布概率分布，以使甲（乙）在各种情，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。况下的平均赢得（损失）最多（最少）。-即混合策略即混合策略求解方法：求解方法：线性规划法线性规划法（其他方法：图解法，迭代法，线性方程法等（其他方法：图解法，迭代法，线性方程法等略）略）例：例：5 9 5 9 设在最坏的情况下，设在最坏的情况下，A=A=甲赢得的平均值为甲赢得的

10、平均值为V.V.8 6 8 6 （未知未知）STEP 1STEP 11)1)设甲使用策略设甲使用策略 1 1的概率为的概率为X X1 1 X X1 1+X+X2 2=1=1 设甲使用策略设甲使用策略 2 2的概率为的概率为X X2 2 X X1 1,X,X2 2 0 02)无论乙取何策略，甲的平均赢得应不少于无论乙取何策略，甲的平均赢得应不少于V:对乙取对乙取 1：5X1+8X2 V对乙取对乙取 2：9X1+6X2 V 注意注意 V0,因为因为A各元素为正各元素为正。STEP 2 作变换：作变换：X1=X1/V ;X2=X2/V得到上述关系式变为：得到上述关系式变为：X1+X2=1/V (V愈

11、大愈好）待定愈大愈好）待定 5X1+8X2 1 9X1+6X2 1 X1,X2 0建立线性模型：建立线性模型：min X1+X2 s.t.5X1+8X2 1 X1=1/21 9X1+6X2 1 X2=2/21 X1,X2 0 1/V=X1+X2=1/7 所以：所以：V=7 返回原问题：返回原问题：X1=X1V=1/3 X2=X2V=2/3 于是甲的最优混合策略为：于是甲的最优混合策略为：以以1/3的概率选的概率选 1；以以2/3的概率选的概率选 2 最优值最优值V=7.同样可求乙的最优混合策略：同样可求乙的最优混合策略：设乙使用策略设乙使用策略 1的概率为的概率为Y1 Y1+Y2=1 设乙使用

12、策略设乙使用策略 2的概率为的概率为Y2 Y1,Y2 0设在最坏的情况下，甲赢得的平均值为设在最坏的情况下，甲赢得的平均值为V.这也是乙损失的平均值，越小越好这也是乙损失的平均值，越小越好 作变换：作变换：Y1=Y1/V ;Y2=Y2/V建立线性模型：建立线性模型：max Y1+Y2 s.t.5Y1+9Y2 1 Y1=1/14 8Y1+6Y2 1 Y2=1/14 Y1,Y2 0 1/V=Y1+Y2=1/7 所以：所以：V=7 返回原问题：返回原问题：Y1=Y1V=1/2 Y2=Y2V=1/2 于是乙的最优混合策略为：于是乙的最优混合策略为：以以1/2的概率选的概率选 1；以以1/2的概率选的概率选 2 最优值最优值V=7.当赢得矩阵中有非正元素时，当赢得矩阵中有非正元素时，V 0的条件的条件不一定成立，可以作下列变换：不一定成立，可以作下列变换：选一正数选一正数k，令矩阵中每一元素加上令矩阵中每一元素加上k得到得到新的正矩阵新的正矩阵A，其对应的矩阵对策其对应的矩阵对策 G=S1,S2,A与与 G=S1,S2,A 解相同，但解相同，但VG=VG-k首先判断是否有纯策略解？首先判断是否有纯策略解？采用采用WinQSB软件求解对策模型软件求解对策模型输入相关的对策矩阵输入相关的对策矩阵