部分方法对策论建模.doc

《部分方法对策论建模.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对策论建模引例：随机游动最优停止问题——暑期第五次作业一模型适用范围对对策问题进行分析，可以采用对策论建模。对策论亦称博弈论或竞赛论，是研究具有对抗或竞争性质现象的数学理论和方法。如：随机游动比赛，田纪赛马型比赛，囚犯问题，市场竞争的决策问题……等二游动问题的模型的建立1．模型准备1．1两人有限零和对策问题1）局中人2）策略集3）赢得函数[3]1．2鞍点引入鞍点的定义如下：设两人零和对策问题的赢得矩阵为（这里m=n=k），若存在正整数、，，使得成立，则称局势（，）为对策问题的鞍点或平衡点，为对策的最优值，、分别称为局中人Ⅰ和Ⅱ的最优纯策略。2．游戏平衡状态的分

2、析3．两人零和对策模型的建立3．1确定赢得矩阵3．2寻找游戏的平衡点4．平衡点稳定性的判断模型求解结果分析模型检验三对策论模型名词解释：1局中人——一个对策中，有权决定自己行动方案的对策参加者称为局中人，用I表示局中人的集合。如果有n个局中人，则。2策略——对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人i的策略集记为3赢得函数——一个对策中，每一局中人所出策略形成的策略组称为一个局势。即设是第i个局中人的一个策略，则n个局中人的策略形成的策略组，s就是一个局势。若记S为全部局势的集合，则，当一个局势s出现后，应该为每一局

3、中人i规定一个赢得值（或损失值）。则是定义在S上的函数，称为局中人i的赢得函数。·根据所研究的问题的不同性质，所建立的对策论的模型是不同的。如其他的比赛的对策论模型就和随机游动的模型不一样。但是不论对策模型在形式上有何不同，都必须包括三个要素：1局中人2策略3赢得函数四对策论模型的分类1）根据局中人的个数，分为二人对策和多人对策2）根据各局中人的赢得函数代数和是否为零，分为零和对策与非零和对策3）根据各局中人间是否允许合作，分为合作对策和非合作对策4）根据局中人的策略集中的策略个数，分为有限对策和无限对策等五矩阵对策模型（也称二人有限零和对策模型）步骤一：赢得

4、矩阵的确定局中人Ⅰ有m个纯策略，局中人Ⅱ有n个纯策略，则局中人Ⅰ和Ⅱ的策略集分别为和。当局中人Ⅰ选定纯策略和局中人Ⅱ选定纯策略后，就形成了一个纯局势,这样的纯局势共有个。对任一纯局势，记局中人Ⅰ的赢得值为，称（5.1）为局中人Ⅰ的赢得矩阵。由于对策是零和的，故局中人Ⅱ的赢得矩阵就是-A。步骤二：最优纯决策的确定由步骤一得到了赢得矩阵，所以我们可以用为一矩阵对策，其中，，，。若（5.2）成立，记其值为，则称为对策的值，称使（5.2）成立的纯局势为G在纯策略意义下的解（或平衡局势），称和分别为局中人Ⅰ和Ⅱ的最优纯策略。定理1：矩阵对策在纯策略意义下有解的充要条件是

5、：存在纯局势，使得对任意i和j，有。（证明见《运筹学》390页）最优纯决策如此选择的意义是：一个平衡局势应具有这样的性质：当局中人Ⅰ选择了纯策略后，局中人Ⅱ为了使其所失最少，只能选择纯策略，否则就可能失的更多；反之，当局中人Ⅱ选择了纯策略后，局中人为了得到最大的赢得也只能选择纯策略，否则就会赢得更少，双方的竞争在局势下达到一个平衡状态。六矩阵对策模型的改进Ⅰ（矩阵对策的混合策略）1模型提出由五可知，在一个矩阵对策中，局中人Ⅰ能保证的至少赢得是局中人Ⅱ能保证的至多所失是一般，局中人Ⅰ的赢得不会多于局中人Ⅱ的所失，故总有，当时，矩阵对策在纯策略意义下有解，且。然而

6、，实际中出现的更多情形是，这时，对策不存在纯策略意义下的解。所以提出了矩阵对策的混合策略来解决此问题。2模型建立步骤一赢得函数的确定定义：矩阵对策，其中，，，，记：则分别称和为局中人Ⅰ和Ⅱ的混合策略集；对，，称x和y为混合策略，（x,y）为混合局势。局中人Ⅰ的赢得函数记为（6.1）称为对策G的混合扩充。不难看出，纯策略是混合策略的一个特殊情形，一个混合策略可以理解为：如果进行多局对策G的话，局中人Ⅰ分别选取纯策略的频率；若只进行一次对策，则反映了局中人Ⅰ对各纯策略的偏爱程度。步骤二最优混合策略的确定对于（6.1），如果（6.2）记其值为，则称为对策G的值，称使

7、（6.2）成立的混合局势为G在混合策略意义下的解（平衡局势），称和分别为局中人Ⅰ和Ⅱ的最优混合策略。七矩阵对策的求解——线性规划方法定理2矩阵对策G在混合策略意义下有解的充要条件是：存在，，使得对任意和，有（7.1）定理3为G在混合策略意义下的解的充要条件是：对任意和，有（7.2）证明见见《运筹学》395页线性规划求解方法见《运筹学》395页程序见作业五八矩阵对策模型扩展（二人无限零和对策）矩阵对策中局中人的策略集是有限的，而有些竞赛等的策略集确是无限的。对于这种情况，我们可以采用二人无限零和对策来解决此问题。用表示一个二人无限零和对策，其中，和中至少有一个是

8、无限集合，H为局中人Ⅰ的赢得函数。记则