博弈论模型和线性规划.pptxVIP

第07章 对策论模型;7.1 矩阵对策模型 ;对策模型的种类可以千差万别，但本质上都必须包括以下三个基本要素： ; 田忌的策略 齐王的策略;7.1.1 对策的基本策略—鞍点对策 ;从直观上来看，局中人 A 应该出策略 al，因为这样选择，他有可能得到9。但局中人 B 看到了这一点，他出策略 b1，这样局中人 A 不能得到9，而只能得到1。因此，局中人 A 也充分认识到这一点，他应当出策略 a3，这样做，就有可能得到8，而这种情况下局中人 B 就要出策略 b3，局中人 A也只能得到2。 这样做下来，局中人 A 只能选择策略 a2，???局中人 B 也只能选择策略 b2，大家达到平衡，最后局中人 A 赢得的值为5，局中人 B 输掉的值为5。;假设局中人 I 有m个策略 ，局中人 II 有n个策略 ，分别记为 ;例7.3 求解矩阵对策 ，其中 ;从例7.3可以看出，矩阵A的元素a22既是其所在行的最小元素又是其所在列的最大元素，即 。将这一事实推广到一般矩阵对策，可得如下定理。 ;当矩阵对策的最优解不惟一时，有如下定理。 定理7.2 (无差别性）若 和 是矩阵对策的两个解，则;解：直接在提供的支付矩阵上计算有;7.1.2 无鞍点的对策策略—混合对策 ;定义7.4 设 是 的混合扩充，若 ;;;定理7.7实际上给出了一个化简支付（赢得）矩阵 A 的原则，称为优超原则。根据此原则，当局中人 I 的某纯策略 被其他纯策略或纯策略的凸线性组合所优超时，可在矩阵 A 中划去第 i 行而得到一个与原对策 G 等价但赢得矩阵阶数较小的对策 G'，而 G' 的求解往往比 G 的求解容易些，通过求解 G' 而得到 G 的解。类似地，对于局中人II来说，可以在赢得矩阵 A 中划去被其他列或其他列的凸线性组合所优超的那些列。 ;7.1.3 混合对策的线性方程组求解方法 ;例7.5 设赢得矩阵为 A，求解此矩阵对策。;对于A3，易知无鞍点存在，应用定理7.5，求解以下两个不等式组 ;练习1：求解下列矩阵对策;练习2：求解下列矩阵对策;A3没有鞍点，故求解 ;7.1.4 混合对策的线性规划求解方法 ;类似地，求局中人 II 的最优策略转化为求解下列线性规划问题：;例：利用线性规划方法求解如下的矩阵对策;MODEL: sets: playerI/1..6/:x; playerII/1..6/; game(playerI,playerII):A; endsets data: A= 3 1 1 1 1 -1 1 3 1 1 -1 1 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 -1 1 3 1 1 1 1 -1 1 3; enddata max=vI; @free(vI); @for(playerII(j):@sum(playerI(i):A(i,j)*x(i))>=vI); @sum(playerI:x)=1; END; Global optimal solution found. Objective value: 1.000000 Total solver iterations: 3 Variable Value Reduced Cost VI 1.000000 0.000000 X( 1) 0.3333333 0.000000 X( 2) 0.000000 0.000000 X( 3