矩阵对策的最优纯策略.docx

矩阵对策的最优纯策略.docx

《矩阵对策的最优纯策略.docx》由会员分享，可在线阅读，更多相关《矩阵对策的最优纯策略.docx（8页珍藏版）》请在冰点文库上搜索。

矩阵对策的最优纯策略

授课时间

授课地点

实到人数

授课题目

矩阵对策的求解

授课专业班级

教学目的与教学要求

了解矩阵对策问题及其求解方法，以期对大家的工作、科研、学习和生活提供

帮助

主要内容

一、矩阵对策的数学模型

二、矩阵对策的最优纯策略

三、矩阵对策的最优混合策略

重点与难点

?

有鞍点的矩阵对策问题及求解？

没有鞍点的矩阵对策问题及求解

教学方法手段（教具）

案例教学

参考资料

韩伯棠《管理运筹学》咼等教育出版社

胡运权《运筹学》高等教育出版社刁在均、刘桂真《运筹学》咼教出版社

课后作业与思考题

教学后记

没有鞍点的矩阵对策的概念及求解的理解是一个难点，每个局中人米用每种策略的概率有何实际意义，用生活中的小故事引入使得学生更容易理解和认可。

时间

分配

教学过程

矩阵对策的求解

在众多的对策模型中，占有重要地位的是二人有限零和对策（finitetwo-personzero-sumgame），又称矩阵对策。

这类对策是到目前为止在理论研究和求解方法方面都比较完善的一个对策分支。

矩阵对策可以说是一类最简单的对策模型，其研究思想和方法十分具有代表性，体现了对策论的一般思想和方法，且矩阵对策的基本结果也是研究其他对策模型的基础。

（1）矩阵对策的数学模型

矩阵对策即为二人有限零和对策。

“二人”是指参加对策的局中人有两个；“有限"是指每个局中人的策略集均为有限集；“零和”是指在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。

“齐王赛马”就是一个矩阵对策的例子，齐王和田忌各有6个策略，一局对策后，齐王的所得必为田忌的所失。

一般，用I和U分别表示两个局中人，并设局中人I有m个纯策略g，局中人U

有n个纯策略■■/,■n；则局中人I和U的策略集分别为S」心,…/m〔和&。

当局中人I选定纯策略:

i和局中人U选定纯策略后，就形成了一个纯局势:

i,・j，这样的纯局势共有mn个。

对任一纯局势：

iS，记局中人I的赢得值为a「称

am1am2瞎门

为局中人I的赢得矩阵。

局中人U的赢得矩阵就是-A。

当局中人I,U的策略集S,5及局中人I的赢得矩阵A确定后，一个矩阵

对策也就给定了，记为G-S,S2,A1。

在齐王赛马的例子中，齐王的赢得矩阵

为：

广111-11

33111-1

1-13111

111311

-111-131

11113；

（二）矩阵对策的最优纯策略

当矩阵对策模型给定后，各局中人面临的问题便是：

如何选择对自己最有

利的纯策略以取得最大的赢得（或最少的损失）？

例1、甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。

比赛共赛三局，规定每局胜者得1分，输者得・1分，可知三赛三胜得3分，三赛

胜得1分，三赛一胜得-1分，三赛三负得-3分。

甲队的策略集为SJ，乙队的策略集为&=「：

1「2r3i。

根据以往比赛的资料，有甲队的赢得矩阵为A，

111

A=1-3

3-13_

请问这次比赛各队采用哪种阵容上场最为稳妥？

解：

由A可看出，局中人甲队的最大赢得为3,要得到这个赢得，他就应该选择策略：

3。

由于局中人乙队的理智，他考虑到甲队打算出：

3的心理，于是准备用：

2来对付甲队，这样使得甲队反而失掉1分，，双方都考虑到对方为使自己尽可能的少得分而所做的努力，所以双方都不存在侥幸心理，而是从各自可能出现的最不利的情形中选择一种最为有利的情况作为决策的依据，这就是所谓的“理智行为”，也就是对策双方实际上都能接受的一种稳妥方法。

甲队在各纯策略下可能得到的最少赢得，即矩阵A中每行的最小元素分别

为：

1,-3,-1,

其中最好的结果是1,即甲队应采取策略：

1，无论对手采用何策略，甲

队都能保证他得赢得不会少于1,而出其他策略，都有可能使甲队的赢得少于1甚至输给对方。

同理，对于乙队来说，各纯策略可能带来最不利的结果，即矩阵A中没列的最大元素分别为：

3，13，

其中最好的也是1,即乙队应采取策略匕，无论对手采用何种策略，乙队

j・air-aij

（2）

证明：

先证充分性，由

（2）有

maxaj,a「初a「j

而

m•nm^xam^xa

iaj・aj

mina：

i辽maxminaq

所以minmaxay

maxminay=minmaxaq=q寸..

且Vg工即厂

再证必要性

设有i,j,使得

呷冃厂呷乂呵naj

mxam[nmxa

ai「叫au

贝U由maxmina“=minmaxa..

有maxa「“jinaijg.j,mji

证毕。

定理1中

（2）式的对策意义是：

一个平衡局势应该具有这样的性

质：

当局中人I选择了纯策略、后，局中人U为了使其所失最少，只能选择纯策略

j,否则就可能失的更多；反之，当局中人U选择了纯策略冷后，局中人I为了得到最大的赢得也只能选择纯策略：

，•否则就会赢得更少，双方的竞争在局势下达到一个平衡状态。

【例2]某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的天气下要消耗10吨和20吨。

假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元。

又设冬季时煤炭价格为每吨10元。

在没有尖于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？

解：

这个问题可看成一个对策问题，局中人I为采购员，局中人II为大自

然，采购员有三个策略，在秋天时买10吨、15吨、20吨煤，分别记为：

“一宀。

大自然也有三个策略：

暖、正常、冷，分别记为：

1,：

2厂3。

通过计算冬季取暖用煤实际费用（为秋季购煤费用和冬季不够时再补购得费用总和），作为局中人I采购员的赢得，得赢得矩阵为

f-1OOO-1750£000、

■1500・1500-2500

1一2000・2000・2000丿

卞-]maxmina”=minmaxa=a33=-2000ijj「j

知该对策的解为：

3「3,即秋季购煤20吨较好。

（三）矩阵对策的混合策略

1混合策略的定义

从以上的讨论可知，对矩阵对策G='S,S2,Af来说，局中人I有把握的至少赢得是丫=maxmina”，局中人U有把握的至多损失的是VAminmaxao。

局订“中人I赢得的值不会多于局中人U所失值，即总有V1Wv2。

当v仁v2时，矩阵对策G存在纯策略意义下的解，且VgH，实际中出现的更多的情形是vl

『59）

例如,赢得矩阵A=,y=6,i=2;V2=8,j=2；y

方根

电&丿

据从最不利情形中选取最有利的结果的原则选择纯策略时，应分别选取：

2和冷，

此时局中人I贏得8,比其预期赢得6还多，原因就在于局中人U选择了S，使其对

手多得原来不该得的赢得，故“对局中人U来说并不是最优，因而它会考虑取徉

2。

局中人I亦会采取相应的办法，改取：

i以使赢得为9,而局中人U又可能仍取策略1来对付局中人I的策略。

这样，局中人I取或〉2的可能性以及局中人U取或二的可能性都不能排除，对两个局中人来说，不存在一个双方均可以接受的平衡局势，或者说当V,：

v时，矩阵对策G不存在纯策略意义下的解。

在这种情况下，一个比较合乎实际的想法是，既然各局中人没有最优纯策略

可取，是否可以给出一个选取不同策略的概率分布？

如在上的例子中，局中人

I可以制定如下一^中策略：

分别以概率1/4和3/4选取纯策略・■，或〉2，这种策略是局中人I的策略集上的一个概率分布，称之为混合策略。

同样局中人U也

可以制定这样一中混合策略，分别以概率1/2和1/2选取纯策略或-2。

F面给出矩阵对策混合策略的定义。

定义：

设G-SnSz,Al为矩阵对策，其中S,=（7）宀,…J，&二二「2,…,\?

，A二

[aj。

记

|mn—

S“=、x・E”Xi亠0,i=1,2,...,m,二Xi=1/

S2=yEyj-0,j=1,2,,n,、屮二1：

则S”和5分别称为局中人i和u的混合策略集（或策略集）；S”和

yS?

分别称为局中人I和U的混合策略（或策略），对x•S,*S2称（x,y），为一个混合局势（或混合扩充）。

一个混合策略X=x>,Xs・・・可设想成当两个局中人多次重复进行对策时，局中人I分别采取纯策略J,■，…的频率。

若只进行一次时对策，混合对策可设想成局中人I对各纯策略的偏爱程度。

2、混合策略的求解

求解混合策略的问题有图解法，迭代法、线性方程组法和线性规划法，在此我们用线性规划解法。

以赢得矩阵/b‘°〕为例来建立此混合策略的线性规划模型。

<86丿

首先，设局中人I使用的概率为X/，使用：

・2的概率X2，并设在最坏的情况下（即为乙出对其最有利的策略情况下），甲的赢得的平均值等于V。

建立下面的数学尖系:

XiX2=1

X/-0,X2-0

5xi8x2_V

9X16X2-V

其次，考虑V的值，V与赢得矩阵A中各元素的值有尖，如果A中各元素的值都大于0,即不管局中人U采用什么策略，局中人I的赢得都是正的。

本例中A得所有元素都取正值，显然V.0。

X

再次，做变量替换，令XJi」,2‘以上五个数量尖系式变为

畑」

2V

%_0,X2-0

5xr8x2一1

9x「6x21

1

对于局中人I来说，他希望V越大越好，也就是希望1的值越小越好。

建

V

立局中人I的最优混合策略的线性规划模型如下：

minX-iX2

5为8x2-1

9Xi6X2-1

xi-0,x2-0

求解该模型得到

为=0.048

X2=0.095

V7

%+X20.048+0.095

Xi=VX1=70.048:

—0.336

x?

=V应-70.0950.664

即：

局中人I的最优混合策略是以0.336的概率出、策略，以0.664的概

率出勺策略'简记为X*=（0.336,0.664\Vg=7。

同样可以求出局中人U的最优混合策略。

建立的线性规划模型如下：

maxyiy2

5%9y2乞18xi6x2_1

yi-0,y?

-0

求解略。

上述例题中，V.0，若没有办法判断出V大于零，或者在一些问题中V本来就小于零或者等于零，此时，可以把A中的每一个元素都加上一个足够大的正数k使得所得的新赢得矩阵A•的每一个元素都大于零。

有定理保证这两个矩阵对策G」.S,S2,A1

G-SsS2,A］的最优混合策略是相同的。

而且有VG=VG