《对策论_矩阵求解讲解》由会员分享,可在线阅读,更多相关《对策论_矩阵求解讲解(28页珍藏版)》请在金锄头文库上搜索。
1、2.6 矩阵对策的求解 矩阵求解的四种方法: 1、线性方程组法 2、线性规划方法 3、迭代法 4、图解法 一、线性方程组方法 又根据定理2.4.3,如果甲和乙的最优策略 中所有分量都大于0,那么上面的不等式组 可化成下面两个线性方程组。 注:如果上述两个方程组的分别存在非负解 x*,y*,则求得了 的一个解(x*,y*)和对策值 ; 如果x*,y*中有负的分量,则将方程组 (2.6.1),(2.6.2)中的某些等式改为不等式试算 。 例2.6.1 求解矩阵对策-田忌赛马问题。 解:已知田忌赛马问题中的支付矩阵 对策 没有鞍点。为了使A中元素尽可能多的变为 0,故令A中每个元素减1再乘以,得到
2、现在讨论 为支付矩阵的对策 的解。为此先 解方程组 和 例2.6.2 上述不等式组无解,根据计算下面两个不 等式组 二、线性规划方法 例2.6.3 用线性规划方法求解例2.6.2 解:先将A的每个元素加3,得到每个元素都是整 数的支付矩阵 转而讨论以A1为支付矩阵的矩阵对策 ,为此求 解两个互为对偶的线性规划问题 三、迭代法 迭代法是求矩阵对策的一种近似方法。 基本思想: 假设两个局中人反复进行对策多次,在每 一局中各局中人都从自己的策略集中选取 一个使对方获得最不利结果的策略,即第t 局对策纯策略的选择欲使对手在前t-1局中 累计所得(或累计所失)最少(或最多) 具体做法: 在第1局中,从两
3、个局中人中任选一个,如局中人 ,让他先采取任意一个策略,如i 。然后,局中 人随之采取策略 j ,使采取i的局中人的所得 最少。在第2局中,局中人还认为局中人采取 策略 j ,故采取某策略i使局中人的所失最多, 局中人又采取策略,使采取局中人在这两局中 累计赢得最少。在第3局中,局中人又采取某策 略使局中人在前两局的累计所失最多,然后局中 人又采取某策略, 局中人在这三局中累计赢得最少。以后各局均照此方 式对策下去,直到迭代的结果达到一定的满意程度为止 。 近似解: 若设在N局对策中局中人出1,2, ,m的次数 为k1,k2, ,km ,局中人出 1, 2, , n的次数 为l 1, l 2, , l n ,xN=(k1 /N ,k2 /N, ,km /N), yN=(l1/N ,l2/N, ,lm /N), 则(xN, yN )就是所求近似解。 令: 则VN是对策值VG的近似值。 xN的每一个收敛子列收敛于局中人的最优策略, yN的每一个收敛 子列收敛于局中人的最优策略。VN收敛于VG 。 j=1 n aijlj max 1 im VN =() N i=1 m aijki min 1 jn VN =() N VN=(VNVN+) 2 迭代算法的终止准则: 1、给定迭代次k 2、给定允许误差 ,当迭代次数k满足 时,迭代结束。 例2.6.4 用迭代法求解例2.6.2,允许误差