[哲学]运筹学9.ppt

二、矩阵对策的混合策略 第三节 矩阵对策的求解 第四节 两人有限非零和对策 无限策略博弈分析 又由： 可得： 定理5的证明是构造性的证明，同时给出了求解方法。 定理6：设（x*， y*）是矩阵对策G解，v =VG，则 矩阵对策G＝{S1，S2；A}。 （1）若 （即A中第k行的每个元素≥ A中第 l 行的每个元素） 称局中人I的策略αk优超于策略 αl ；则可在A中去掉第 l 行，矩阵对策G的解不变。 （2）如果： （即A中第k列的每个元素≤ A中第l列的每个元素） 称局中人II的策略βk 优超于策略βl 。则可在A中去掉第第 l 列，矩阵对策G的解不变。 优超定理： 一、2×2对策的方程法 则称G为2×2对策。 若G没有纯策略下的解，则G的最优混合策略x*= ( x1, x2 )T , y* = ( y1, y2 )T 满足下列方程组： 且其中v =VG . 例1：求解求解矩阵对策G＝{S1，S2；A} ，其中： 解：在A中由于：第3行≥第2行， 第4行≥第1行， 因此从A中划去1，2两行，得： 在A1中由于：第1列≤第3列， 第2列≤第4列， 因此从A1中划去3，4两列，得： 在A2中由于：第1行≥第3行， 因此从A2中划去第3行，得： 在A3中由于：第1列≤第3列， 因此从A3中划去第3列，得： 分别求解方程组得： 得 x3=1/3 , x4 =2/3, y1=1/2 , y2 =1/2 ,v = 5. 由此对于原问题A而言，最优解为： 二、2×n和m×2对策的图解法 解：设局中人I 的混合策略为( x, 1－x )T , 局中人I 的最少得益为如下图中由局中人II 选择β1,β2,β3 时所确定的三条直线2 x ＋7(1－x)＝v， 3 x ＋5(1－x)＝v，11x ＋2(1－x)＝v在x处纵坐标的最小者，即如图中折线B1BB2B3。 例2：求解求解矩阵对策G＝{S1，S2；A} ，其中： 0 1 2 5 11 2 3 7 x V V β3 β1 β2 B1 B B2 B3 A 所以对局中人I来说，他的策略就是确定x使他的得益达到最大。按最大最小原则应选择x＝OA，而AB即为对策的值。为求出x和对策的值 VG ，可联立过B点的两条直线β2和β3所确定的方程。 解得： x ＝3/11， VG=49/11。 此外从图中可看出，局中人II的最优策略只由β2和β3组成（不选β1），可由方程组所确定： 解得： y2=9/11，y3 =2/11。 所以最优解为： 例3：求解矩阵对策G＝{S1，S2；A}，其中： 解：设局中人II 的混合策略为( y, 1－y )T , 局中人II 的最大支付为如下图中由局中人 I选择α1,α2, α3 时所确定的三条直线2y＋7(1－y)＝v，9y＋6(1－y)＝v，11y＋2(1－y)＝v在y处纵坐标的最小者，即如图中折线上的B点。 0 1 2 6 11 2 9 7 y V V B A α1 α2 α3 对局中人II来说，他的策略就是确定y使他的支付达到最小。按最小最大原则应选择y ＝OA，为求出y和对策的值 VG ，可联立过B 点的两条直线α1和α2所确定的方程。 解得： y ＝1/8， VG=51/8。 此外从图中可看出，局中人II的最优策略只由α1和α2组成（不选α3），可由方程组所确定： 解得： x1=3/8，x2 =5/8。 所以最优解为： 三、线性规划法 由前面定理可知，对策G的解满足下列线性规划： 作变量替换： 则 于是上述线性规划等价于下面的线性规划问题。 由此求解一个对策问题，就相当于求解上面的对偶问题： 例4：利用线性规划法求解矩阵对策G＝{S1,S2；A}. 【注】如果ai j不满足非负性，则存在一个正数k，使得ai j +k≥0 令B =(bi j ) =(ai j +k)，求解对策问题 {S1，S2；B} ，可以证明：问题{S1，S2；B}与问题{S1，S2；A}的最优策略相同，且有： 其中： 解： 建立相应的线性规划模型 及 用单纯形法求解后一个问题，先标准化为： 用单纯形表求解如下： 由此最优解为： 例1：“囚徒困境” 甲乙是同案囚犯，被隔离审讯。如果两个都抵赖，因为证据不充分，两人都只能判1年。如果只有一方坦白，则无罪释放；而另一方则属抗拒从严，判10年。但如果两人都坦白，则各判5年。 下表给出了“囚徒困境”博弈问题的战略式表述，为了实现各自的效用最大化，双方格采取何种策略呢? (－1,－1 ) (－10，0 ) 抵赖α2 ( 0, －10 ) ( －5 , －5 ) 坦白α1 抵赖β2 坦