管理运筹学对策论课件

对策论由“齐王赛马”引入对策论由“齐王赛马”引入11.对策论的基本概念三个基本要素；1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略。某局中人的所有可能策略全体称为策略集；3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人的对策结果（量化）称为该局势对策的益损值）1.对策论的基本概念三个基本要素；2“齐王赛马”齐王在各局势中的益损值表（单位：千金）“齐王赛马”齐王在各局势中的益损值表（单位：千金）3其中：齐王的策略集:S1={1,2,3,4,5,6}田忌的策略集：S1={1,2,3,4,5,6}下列矩阵称齐王的赢得矩阵：

3111-1113111-1A=1-13111-111311111-13111-1113其中：41.基本概念（续）二人有限零和对策：（又称矩阵策略）局中人为2；每局中人的策略集中策略权目有限；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。1.基本概念（续）二人有限零和对策：（又称矩阵策略）51.基本概念（续）记矩阵对策为:

G={S1,S2,A}

甲的策略集甲的赢得矩阵乙的策略集“齐王赛马”即是一个矩阵策略.1.基本概念（续）记矩阵对策为:62.矩阵对策的最优纯策略在甲方赢得矩阵中：A=[aij]m*ni行代表甲方策略i=1,2…mJ列代表乙方策略j=1,2…naij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。2.矩阵对策的最优纯策略在甲方赢得矩阵中：72.矩阵对策的最优纯策略(续)例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值赢得矩阵。

-30-20A=2301-2-4-13问：甲公司应采取什么策略比较适合？2.矩阵对策的最优纯策略(续)例：有交易双方公司甲和乙，甲有8甲：采取1至少得益–3(损失3）203-4(损失4）乙：采取1甲最多得益2（乙最少得益-2）23（乙得益-3）30（乙得益0）43（乙得益-3）取大则取2maxminaij=0

ij取小则取3minmaxaij=0ji甲：取大则取2取小则取39甲采取策略2不管乙采取如何策略，都至少得益。乙采取策略3不管甲采取如何策略，都至少可以得益。（最多损失0）分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。存在前提：

maxminaij=minmaxaij=v

ijji又称（2，3）为对策G={s1,s2,A}的鞍点。值V为G的值。甲采取策略2不管乙采取如何策略，都至少得益。103.矩阵对策的混合策略设矩阵对策G={S1,S2,A}当maxminaijminmaxaij

ijji时，不存在最优纯策略求解混合策略。3.矩阵对策的混合策略设矩阵对策G={S1,S2,A}113.矩阵对策的混合策略例：设一个赢得矩阵如下:

min595A=max6策略2866imax89min8

策略1

j3.矩阵对策的混合策略例：设一个赢得矩阵如下:12矛盾：甲取2，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9…此时，甲，乙方没有一个双方均可接受的平衡局势。一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-----即混合策略矛盾：甲取2，乙取时1，甲实际赢得8比预期多2（乙就少13求解方法：线性规划法（其他方法：图解法，迭代法，线性方程法等略）例：59设在最坏的情况下，A=甲赢得的平均值为V.

86（未知）STEP11)设甲使用策略1的概率为X1′X1′+X2′=1设甲使用策略2的概率为X2′X1′,X2′0求解方法：线性规划法142)无论乙取何策略，甲的平均赢得应不少于V:对乙取1：5X1’+8X2’V对乙取2：9X1’+6X2’V注意V>0,因为A各元素为正。STEP2作变换：X1=X1’/V;X2=X2’/V得到上述关系式变为：X1+X2=1/V(V愈大愈好）待定5X1+8X219X1+6X21X1,X202)无论乙取何策略，甲的平均赢得应不少于V:15建立线性模型：

minX1+X2

s.t.5X1+8X21X1=1/21

9X1+6X21X2=2/21X1,X201/V=X1+X2=1/7所以：V=7

返回原问题：X1’=X1V=1/3

X2’=X2V=2/3于是甲的最优混合策略为：以1/3的概率选1；以2/3的概率选2最优值V=7.建立线性模型：16同样可求乙的最优混合策略：设乙使用策略1的概率为Y1′Y1′+Y2′=1设乙使用策略2的概率为Y2′Y1′,Y2′0设在最坏的情况下，甲赢得的平均值为V.这也是乙损失的平均值，越小越好作变换：Y1=Y1’/V;Y2=Y2’/V建立线性模型：

maxY1+Y2

s.t.5Y1+9Y21Y1=1/14

8Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7所以：V=7

同样可求乙的最优混合策略：17返回原问题：Y1’=Y1V=1/2

Y2’=Y2V=1/2于是乙的最优混合策略为：以1/2的概率选1；以1/2的概率选2最优值V=7.当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换：选一正数k，令矩阵中每一元素加上k得到新的正矩阵A’，其对应的矩阵对策G’={S1,S2,A’}与G={S1,S2,A}解相同，但VG=VG’-k返回原问题：Y1’=Y1V=1/218例：求解“齐王赛马”问题（见备课稿）优超原则：假设矩阵对策G={S1,S2,A}

甲方赢得矩阵A=[aij]mn--若存在两行（列），s行（列）的各元素均优于t行（列）的元素，即asjatjj=1,2…n(ais

aiti=1,2…m)称甲方策略s优超于t(s优超于t)3.矩阵对策的混合策略(续)例：求解“齐王赛马”问题（见备课稿）3.矩阵对策的混合策略(19--优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A’，其对应的矩阵对策

G’={S1,S2,A’}与G={S1,S2,A}等价，即解相同。3.矩阵对策的混合策略(续)--优超原则：当局中人甲方的策略t被其它策略所优超时，可20例设甲方的益损值赢得矩阵。

32030

被第3、4行所优超

50259

被第3行所优超A=7395946875.560883得到73959被第1列所优超A1=46875.5被第2列所优超608833.矩阵对策的混合策略(续)例设甲方的益损值赢得矩阵。3.矩阵对策的混合策略(续)21续例得到739A2=465.5

603

被第1行所优超得到739

被第1列所优超A3=465.573最终得到A4=463.矩阵对策的混合策略(续)续例得到3.矩阵对策的混合策略(续)22对A4计算，用线性规划方法得到：（注意：余下的策略为3，4，1，2）甲：X*=(0，0，1/15，2/15，0)TV=5X*’=(0，0，1/3，2/3，0)T

乙：Y*=(1/10，1/10，0，0，0)TV=5Y*’=(1/2，1/2，0，0，0)T

注：利用有超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；线性规划求解时有可能是多解问题。习题：P343-1，3，43.矩阵对策的混合策略(续)对A4计算，用线性规划方法得到：3.矩阵对策的混合策略(续)23对策论由“齐王赛马”引入对策论由“齐王赛马”引入241.对策论的基本概念三个基本要素；1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略。某局中人的所有可能策略全体称为策略集；3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人的对策结果（量化）称为该局势对策的益损值）1.对策论的基本概念三个基本要素；25“齐王赛马”齐王在各局势中的益损值表（单位：千金）“齐王赛马”齐王在各局势中的益损值表（单位：千金）26其中：齐王的策略集:S1={1,2,3,4,5,6}田忌的策略集：S1={1,2,3,4,5,6}下列矩阵称齐王的赢得矩阵：

3111-1113111-1A=1-13111-111311111-13111-1113其中：271.基本概念（续）二人有限零和对策：（又称矩阵策略）局中人为2；每局中人的策略集中策略权目有限；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。1.基本概念（续）二人有限零和对策：（又称矩阵策略）281.基本概念（续）记矩阵对策为:

G={S1,S2,A}

甲的策略集甲的赢得矩阵乙的策略集“齐王赛马”即是一个矩阵策略.1.基本概念（续）记矩阵对策为:292.矩阵对策的最优纯策略在甲方赢得矩阵中：A=[aij]m*ni行代表甲方策略i=1,2…mJ列代表乙方策略j=1,2…naij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。2.矩阵对策的最优纯策略在甲方赢得矩阵中：302.矩阵对策的最优纯策略(续)例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值赢得矩阵。

-30-20A=2301-2-4-13问：甲公司应采取什么策略比较适合？2.矩阵对策的最优纯策略(续)例：有交易双方公司甲和乙，甲有31甲：采取1至少得益–3(损失3）203-4(损失4）乙：采取1甲最多得益2（乙最少得益-2）23（乙得益-3）30（乙得益0）43（乙得益-3）取大则取2maxminaij=0

ij取小则取3minmaxaij=0ji甲：取大则取2取小则取332甲采取策略2不管乙采取如何策略，都至少得益。乙采取策略3不管甲采取如何策略，都至少可以得益。（最多损失0）分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。存在前提：

maxminaij=minmaxaij=v

ijji又称（2，3）为对策G={s1,s2,A}的鞍点。值V为G的值。甲采取策略2不管乙采取如何策略，都至少得益。333.矩阵对策的混合策略设矩阵对策G={S1,S2,A}当maxminaijminmaxaij

ijji时，不存在最优纯策略求解混合策略。3.矩阵对策的混合策略设矩阵对策G={S1,S2,A}343.矩阵对策的混合策略例：设一个赢得矩阵如下:

min595A=max6策略2866imax89min8

策略1

j3.矩阵对策的混合策略例：设一个赢得矩阵如下:35矛盾：甲取2，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9…此时，甲，乙方没有一个双方均可接受的平衡局势。一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-----即混合策略矛盾：甲取2，乙取时1，甲实际赢得8比预期多2（乙就少36求解方法：线性规划法（其他方法：图解法，迭代法，线性方程法等略）例：59设在最坏的情况下，A=甲赢得的平均值为V.

86（未知）STEP11)设甲使用策略1的概率为X1′X1′+X2′=1设甲使用策略2的概率为X2′X1′,X2′0求解方法：线性规划法372)无论乙取何策略，甲的平均赢得应不少于V:对乙取1：5X1’+8X2’V对乙取2：9X1’+6X2’V注意V>0,因为A各元素为正。STEP2作变换：X1=X1’/V;X2=X2’/V得到上述关系式变为：X1+X2=1/V(V愈大愈好）待定5X1+8X219X1+6X21X1,X202)无论乙取何策略，甲的平均赢得应不少于V:38建立线性模型：

minX1+X2

s.t.5X1+8X21X1=1/21

9X1+6X21X2=2/21X1,X201/V=X1+X2=1/7所以：V=7

返回原问题：X1’=X1V=1/3

X2’=X2V=2/3于是甲的最优混合策略为：以1/3的概率选1；以2/3的概率选2最优值V=7.建立线性模型：39同样可求乙的最优混合策略：设乙使用策略1的概率为Y1′Y1′+Y2′=1设乙使用策略2的概率为Y2′Y1′,Y2′0设在最坏的情况下，甲赢得的平均值为V.这也是乙损失的平均值，越小越好作变换：Y1=Y1’/V;Y2=Y2’/V建立线性模型：

maxY1+Y2

s.t.5Y1+9Y21Y1=1/14

8Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7所以：V=7

同样可求乙的最优混合策略：40返回原问题：Y1’=Y1V=1/2

Y2’=Y2V=1/2于是乙的最优混合策略为：以1/2的概率选1；以1/2的概率选2最优值V=7.当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换：选一正数k，令矩阵中每一元素加上k得到新的正矩阵A’，其对应的矩阵对策G’={S1,S2,A’}与G={S1,S2,A}解相同，但VG=VG’-k返回原问题：Y1’=Y1V=1/241例：求解“齐王赛马”问题（见备课稿）优超原则：假设矩阵对策G={S1,S2,A}

甲方赢得矩阵A=[aij]mn--若存在两行（列），s行（列）的各元素均优于t行（列）的元素，即asjatjj=1,2…n(ais

aiti=1,2…m)称甲方策略s优超于t(s优超于t)3.矩阵对策的混合策略(续)例：求解“齐王赛马”问题（见备课稿）3.矩阵对策的混合策略(42--优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同