运筹与优化--对策论.ppt

运筹与优化对策论第一节对策论的基本概念对策三要素第二节对策论的基本定理田忌齐王最优策略:有利于自己获得最大赢得(或最少损失)的策略.选择最优策略的原则:牢记对方总是以最不利于你的行动方案来对付你.例2.设矩阵对策G={S1,S2;A},其中S1={α1,α2,α3,α4},S2={β1,β2,β3},试求双方的最优策略和赢得.理智行为:双方各按最不利于自己的情形中选择最为利己的结果作为决策的依据.定义1.设矩阵对策G={S1,S2；A},若等式(1)成立,记,则称VG为对策G的值,称使(1)成立的纯局势为G在纯策略下的解(或平衡局势、双赢局势).定理1.矩阵对策G={S1,S2；A}在纯策略中有解的充要条件是:存在纯局势使得(2)(i=1,2,…,m,j=1,2,…,n).既是其所在行的最小元素,又是其所在列的最大元素.定义2.设实函数f(x,y)定义在x∈A,y∈B上,若存在x*∈A,y*∈B,使得对x∈A,y∈B,有f(x,y*)≤f(x*,y*)≤f(x*,y)(3)则称(x*,y*)为f(x,y)的一个鞍点.矩阵对策G在纯策略意义下有解,且的充要条件是:是矩阵A的一个鞍点.例3.确定p和q的取值范围,使矩阵A在(α2,β2)处存在鞍点.其中例4.设矩阵对策G={S1,S2;A},其中S1={α1,α2,α3,α4},S2={β1,β2,β3},试求双方的最优策略和赢得.性质2(可交换性).若(αk,βr)和(αp,βq)是对策G的两个解,则(αk,βq)和(αp,βr)也是对策G的解.由aiq≤apq=akr≤akq≤apq=akr≤akj得aiq≤akq≤akj,即akq是鞍点.故(αk,βq)是解.同理，(αp,βr)是解.性质1、2表明,矩阵对策的值是唯一的.例5.P385例题.定义3.设矩阵对策G={S1,S2;A},A=(aij)m×n.若局中人I以概率xi≥0取纯策略αi,局中人Ⅱ以概率yj≥0取纯策略βj,且.记则S1*,S2*分别称为局中人I和Ⅱ的混合策略集.称x∈S1*,y∈S2*为局中人I和Ⅱ的混合策略,(x,y)为混合局势,局中人I的赢得函数为称G*={S1*,S2*,E}为对策G的混合扩充.设则有定义4.设G*={S1*,S2*;E}是矩阵对策G={S1,S2;A}的混合扩充,若定理2.矩阵对策G={S1,S2;A}在混合策略中有解的充要条件是:(x*,y*)为E(x,y)的一个鞍点,即对一切x∈S1*,y∈S2*,有E(x,y*)≤E(x*,y*)≤E(x*,y)(4)注意:G在纯策略下解存在时,定义4中的;G在混合策略意义下的解(x*,y*)存在时,VG=E(x*,y*).例4.解矩阵对策G={S1,S2;A},其中局中人I取纯策略αi时,其赢得函数为E(i,y)=∑aijyj,局中人Ⅱ取纯策略βj时,其赢得函数为E(x,j)=∑aijxi.由上两式得E(x,y)=∑E(i,y)xi(5)E(x,y)=∑E(x,j)yj.(6)定理3.设x∈S1*,y∈S2*,则(x*,y*)是G的解的充要条件是:对任意i=1,2,…,m和j=1,2,…,n,有E(i,y*)≤E(x*,y*)≤E(x*,j)(7)定理3.设x∈S1*,y∈S2*,则(x*,y*)是G的解的充要条件是:对任意i=1,2,…,m和j=1,2,…,n,有E(i,y*)≤E(x*,y*)≤E(x*,j)(7)证明:设(x*,y*)是G的解,则由定理2,有E(x,y*)≤E(x*,y*)≤E(x*,y)(4)由于纯策略是混合策略的特例,故(7)式成立.反之,设(7)式成立,由(5)、(6)有E(x,y*)=∑E(i,y*)xi≤E(x*,y*)∑xi=E(x*,y*)E(x*,y)=∑E(x*,j)yj≥E(x*,y*)∑yj=E(x*,y*)可知(4)式成立，故(x*,y*)是G的解定理4.设x*∈S1*,y*∈S2*,则(x*,y*)是G的解的充要条件是:存在数v,使得x*,y*分别是不等式组(8)(9)的解,且v=VG.定理4.证明:“”因G有解,(7)式成立.取v=E(x*,y*)就有(8),(9).“”因对任意x∈S1*,y∈S2*,有E(x,y*)=∑E(i,y*)xi≤∑vxi=vE(x*,y)=∑E(x*,j)yj≥∑vyj=v于是E(x,y*)≤v≤E(x*,y).特别有E(x*,y*)≤v≤E(x*,y*).故v=E(x*,y*)=VG.定理5.任意矩阵对策G={S1,S2;A}一定存在混合策略意义下的解.证明:由定理4,只要证明存在数v*和x*∈S1*,y*∈S2*,使得(10)为此,考虑下列两个线性规划问题:易知(P)和(D)互为对偶,x=(1,0,…,0)T∈Em,w=mina1j是(P)的可行解,y=(1