10-矩阵对策(ppt文档).ppt

第第 10 章章Games Theory矩矩 阵阵 对对 策策对策论对策论的第一扇大门的第一扇大门1第10章 矩阵对策10.1 基本概念基本概念10.2 特殊方法特殊方法10.3 线性规划法线性规划法第第10章章 矩阵对策矩阵对策2第10章 矩阵对策10.1 基本概念基本概念 10.1.10.1.1 1 引言引言引言引言一一、对策现象及其三个要素对策现象及其三个要素 对策对策对策对策：就是竞争或斗争中的决策。就是竞争或斗争中的决策。对策现象的对策现象的三个要素三个要素三个要素三个要素：局中人、策略、得失局中人、策略、得失局中人、策略、得失局中人、策略、得失。（1 1）局中人局中人局中人局中人：参与对策并有切身利益关系与决策权的个人或集体。参与对策并有切身利益关系与决策权的个人或集体。假设假设假设假设：局中人都是局中人都是聪明的聪明的聪明的聪明的。（2 2）策略策略策略策略：每个局中人为了自身利益所能采取的对付其他局中人的每个局中人为了自身利益所能采取的对付其他局中人的 办法或措施，称为该局中人的办法或措施，称为该局中人的策略策略策略策略。一个策略应是在一局对策中，从始至终采取的所有行动的一个策略应是在一局对策中，从始至终采取的所有行动的 一套完整方案。一套完整方案。（3 3）得失得失得失得失：一局对策一局对策一局对策一局对策的的结果结果结果结果，诸如，诸如胜负、名次、损益、效用胜负、名次、损益、效用胜负、名次、损益、效用胜负、名次、损益、效用，等等，等等,统称为统称为得失得失得失得失。3第10章 矩阵对策10.1 基本概念基本概念 例例1 田忌赛马田忌赛马（1 1）局中人局中人局中人局中人：田忌、齐王；田忌、齐王；（2 2）策策策策 略略略略：3 匹马参赛的顺序：匹马参赛的顺序：（上，中，下），上，中，下），（上，下，中）上，下，中）（中，下，上），中，下，上），（中，上，下）中，上，下）（下，上，中），下，上，中），（下，中，上）下，中，上）策略集策略集策略集策略集：每个每个局中人局中人局中人局中人所有策略构成的集合。所有策略构成的集合。局势局势局势局势：（下，上，中下，上，中），（上，中，下上，中，下）（3 3）得得得得 失失失失：一局千金。一局千金。二、二、对策的分类对策的分类 局中人数局中人数：二人二人二人二人对策对策 多人多人多人多人对策对策 策略数：策略数：有限有限有限有限对策对策 无限无限无限无限对策对策 得失总和：得失总和：零和零和零和零和对策对策 非零和非零和非零和非零和对策对策 4第10章 矩阵对策10.1 基本概念基本概念 二、二、对策的分类（续）对策的分类（续）按按相互关系相互关系相互关系相互关系：平等平等对策对策 主从主从对策对策协商协商协商协商对策对策对抗对抗对抗对抗对策对策结结结结 盟盟盟盟对策对策不结盟不结盟不结盟不结盟对策对策 多人多人对策对策联合联合联合联合对策对策合作合作合作合作对策对策 按按数学模型数学模型数学模型数学模型：矩阵矩阵矩阵矩阵对策对策、树图树图树图树图对策对策、微分微分微分微分对策。对策。5第10章 矩阵对策10.1 基本概念基本概念 三、矩阵对策的基本模型三、矩阵对策的基本模型 在二人有限零和对策中，设以在二人有限零和对策中，设以甲方甲方、乙方乙方表示两个表示两个 局中人局中人局中人局中人，以以 S1=1,2,m S2=1,2,n 分别表示分别表示甲方甲方、乙方乙方的的策略集策略集策略集策略集，其中：其中：i(i=1,2,m)甲方甲方的的策略策略策略策略 j (j=1,2,n)乙方乙方的的策略策略策略策略6第10章 矩阵对策10.1 基本概念基本概念 则则 S1 与与 S2 构成构成 mn 个局势个局势 (i,j),i=1,2,m;j=1,2,n令令 aij 甲方甲方甲方甲方关于局势关于局势(i,j)的赢得的赢得则所有则所有 aij 构成一个矩阵构成一个矩阵A=(aij)mn称为称为甲方甲方甲方甲方的的赢得矩阵赢得矩阵。由于甲、乙双方得失总和恒为零，所以由于甲、乙双方得失总和恒为零，所以A还可称为还可称为乙方乙方乙方乙方的的损失矩阵损失矩阵，而，而 A 即乙方的赢得矩阵。即乙方的赢得矩阵。7第10章 矩阵对策10.1 基本概念基本概念 由此可见，在由此可见，在二人有限零和二人有限零和二人有限零和二人有限零和对策中，给定一个局中人的对策中，给定一个局中人的赢得矩阵，则另一个局中人的赢得矩阵也就唯一确定了，而赢得矩阵，则另一个局中人的赢得矩阵也就唯一确定了，而且双方的策略数目也就唯一确定了。这意味着二人有限零和且双方的策略数目也就唯一确定了。这意味着二人有限零和对策总可以由一个局中人的赢得矩阵来刻画，故称这种对策对策总可以由一个局中人的赢得矩阵来刻画，故称这种对策为为矩阵对策矩阵对策矩阵对策矩阵对策。其其基本模型基本模型记为记为 G=S1,S2,A 其中其中 A=(aij)mn 规定为规定为甲方甲方甲方甲方的的赢得矩阵赢得矩阵赢得矩阵赢得矩阵。8第10章 矩阵对策10.1 基本概念基本概念例例1 田忌赛马田忌赛马 设以设以 S S1 1=1 1,2 2,3 3,4 4,5 5,6 6 表示表示田忌田忌田忌田忌的策略集，的策略集，其中：其中：1 1 =(上、中、下上、中、下上、中、下上、中、下)，2 2=(上、下、中上、下、中上、下、中上、下、中)3 3=(中、下、上中、下、上中、下、上中、下、上)，4 4=(中、上、下中、上、下中、上、下中、上、下)5 5=(下、上、中下、上、中下、上、中下、上、中)，6 6=(下、中、上下、中、上下、中、上下、中、上)以以 S2=1,2,3,4,5,6 表示表示齐王齐王的策略集，的策略集，其中：其中：1=(上、中、下上、中、下上、中、下上、中、下),),2=(上、下、中上、下、中上、下、中上、下、中)3=(中、下、上中、下、上中、下、上中、下、上)，4=(中、上、下中、上、下中、上、下中、上、下)5=(下、上、中下、上、中下、上、中下、上、中)，6=(下、中、上下、中、上下、中、上下、中、上)9第10章 矩阵对策10.1 基本概念基本概念则则田忌的赢得矩阵田忌的赢得矩阵田忌的赢得矩阵田忌的赢得矩阵为：为：1 2 3 4 5 6 1 -3 -1 1 -1 -1 -1 2 -1 -3 -1 1 -1 -1 3 -1 -1 -3 -1 1 -1 4 -1 -1 -1 -3 -1 1 5 1 -1 -1 -1 -3 -1 6 -1 1 -1 -1 -1 -3A=10第10章 矩阵对策10.1 基本概念基本概念10.1.10.1.2 2 纯策略纯策略纯策略纯策略 一、一、鞍点鞍点 例例2 设有对策设有对策G=S1,S2,A,其中其中:1 2 3 4 1 7 -8 -2 3 2 3 6 1 2 3 9 2 -3 -5A=-81-5(max)min aij9613max aij(min)111(2,3)为为最优纯局势最优纯局势。坏坏中求中求好好11第10章 矩阵对策10.1 基本概念基本概念 设有对策设有对策G=S1,S2,A,其中其中 S1=1,2,m,S2=1,2,n A=(aij)mn如果如果A中存在一个元素中存在一个元素a arkrk，满足，满足:a arkrk=max min aij=min max aijijji则把则把 a arkrk 所对应的局势所对应的局势 (r,k)称为对策称为对策G的的解解或或鞍点鞍点,分别称分别称r 甲方甲方的的最优纯策略最优纯策略，记为，记为*=r k 乙方乙方的的最优纯策略最优纯策略，记为，记为*=k a arkrk 对策对策G的的值值，记为，记为v v即即v v=max min aij=min max aij=a arkrk iijj(11-2)12第10章 矩阵对策10.1 基本概念基本概念二、二、鞍点属性鞍点属性 定理定理定理定理1 1 对策对策G=S1,S2,A 在纯策略意义下有解的在纯策略意义下有解的充要条件充要条件充要条件充要条件是：矩阵是：矩阵A中存在一个元素中存在一个元素 a ark rk，它对一切它对一切 i、j 都满足：都满足：上式意味着：上式意味着：a arkrk 是它所在是它所在行行的诸元素中的的诸元素中的最小最小者者,同时又是它所在同时又是它所在列列的诸元素中的的诸元素中的最大最大者者。(11-3)aikarkarj,i=1,2,m;j=1,2,n 13第10章 矩阵对策10.1 基本概念基本概念最优纯策略最优纯策略具有下述具有下述性质性质性质性质：(1)若甲方采用若甲方采用*=r r,则他的赢得至少是则他的赢得至少是v v,即便即便事先公开这一点事先公开这一点,乙方也无法利用这一信息使甲方的赢得乙方也无法利用这一信息使甲方的赢得比比 v v 更少。更少。(2)若乙方采用若乙方采用*=k k,则他的损失至多是则他的损失至多是v v,即便即便事先公开这一点事先公开这一点,甲方也无法利用这一信息使乙方的损失甲方也无法利用这一信息使乙方的损失比比 v v 更多。更多。14第10章 矩阵对策10.1 基本概念基本概念例例3 求解对策求解对策G=S1,S2,A,其中其中:(max)(max)(min)(min)解解 4 3 6 3-2 2 0 -6 5 3 4 3A=4 3 6 3-2 2 0 -6 5 3 4 3 5 3 6 31 2 3 4 3-6 3123A=jmin aijimax aij333315第10章 矩阵对策10.1 基本概念基本概念1010.1 1.3 3 混合策略混合策略一、矩阵对策的解一、矩阵对策的解 如前所述如前所述,有些矩阵对策在纯策略下无解。那么在这种有些矩阵对策在纯策略下无解。那么在这种 情况下，双方应如何决策呢？情况下，双方应如何决策呢？例例4 已知对策已知对策G=S1,S2,A,其中其中:S S1 1=1 1,2 2,S2=1,2 A=7 43 616第10章 矩阵对策10.1 基本概念基本概念 局中人甲的局中人甲的期望赢得期望赢得为为:E(x,y)=aijP(ij)=aijP(i)P(j)=7xy+4x(1-y)+3(1-x)y+6(1-x)(1-y)=6 xy-3y-2 x+6 X=(x1,x2 )T =(x,1-x)TY=(y1,y2)T =(y,1-y)TX*=(1/2,1/2)TY*Y*=(1 1/3 3,2 2/3 3)TE E(X*,Y*Y*)=5 5-2(x-1/2)+5=6(x-1/2)(y-1/3)+5x=1/2 1-x=1/2 y=1/3 1-y=2/3=6y(x-1/2)P(j)7 43 61 12 2P(i)1 2aijjix1-x y 1-y17第10章 矩阵对策10.1 基本概念基本概念 (1)把把S1上的概率分布上的概率分布 X=(x1,x2,xm)T 称为称为甲方的混合策略甲方的混合策略,把把S2上的概率分布上的概率分布 Y=(y1,y2,yn)T 称为称为乙方的混合策略乙方的混合策略，称称(X,Y)为对策为对策G的一个的一个混合局势混合局势。(2)称数学期望称数学期望i=1j=1 m nE E(X,Y)=aij xi yj=XTAY 为甲方的为甲方的期望赢得期望赢得，简称为甲的，简称为甲的赢得赢得,同时又称为同时又称为乙方的乙方的损失损失,而而-E E(X,Y)为乙方的为乙方的赢得赢得。18第10章 矩阵对策10.1 基本概念基本概念 (3)记记 S1*=X=(x1,x2,xm)T|xi0，i=1,2,m,xi=1 甲方甲方的的混合策略集混合策略集，S2*=Y=(y1,y2,yn)T|yj0，j=1,2,n,yj=1 乙方乙方的的混合策略集混合策略集，G*G*=S1*,S2*,E E G=S1,S2,A 的的混合扩充混合扩充。19第10章 矩阵对策10.1 基本概念基本概念 (4)若有若有X*S1*,Y*Y*S2*,使使XX Y YE E(X*,Y*Y*)=max min E E(X,Y)=min max E E(X,Y)XX YYv*v*=max min E E(X,Y)=min max E E(X,Y)=E E(X*,Y*Y*)则则这样，这样，对策对策在纯策略意义下的解在纯策略意义下的解(*,*)就成为就成为(X*,Y*Y*)的一种特殊情况。的一种特殊情况。X*甲甲方的方的最优混合策略最优混合策略 Y*Y*乙乙方的方的最优混合策略最优混合策略 简称简称最优策略最优策略；而；而 (X*,Y*Y*)对策对策G在在混合策略意义下的混合策略意义下的解解 E E(X*,Y*Y*)对策对策G的的值值，记为，记为 v*v*，即，即如如例例例例2 2 2 2 :X*=(0,1,0)T Y*Y*=(0 0,0 0,1 1,0 0)T 2320第10章 矩阵对策10.1 基本概念基本概念二、基本定理二、基本定理 定理定理定理定理2 2 2 2 混合局势混合局势(X*,Y*Y*)是矩阵对策是矩阵对策G的解的的解的充要充要充要充要条件条件 是：对一切是：对一切XS1*和和YS2*,都有都有 E E(X,Y*Y*)E E(X*,Y*Y*)E E(X*,Y)定理定理定理定理3 3 3 3 若存在实数若存在实数v0以及以及 X*S1*,Y*Y*S2*，则，则(X*,Y*Y*)是是G的解，且的解，且v*v*=v0 的的充要充要充要充要条件是：对任意条件是：对任意 iI 和和 jJ，都有都有 E E(ei,Y*Y*)v0 E E(X*,ej)21第10章 矩阵对策10.1 基本概念基本概念推论推论推论推论 设设v*v*是是对策对策G=S1,S2,A 的的值，则方程组值，则方程组的的解解 X X*=(x x1 1*,x x2 2*,x xmm*)T 是是甲甲方的最优策略方的最优策略;而而的的解解 Y*=(y1*,y2*,yn*)T 是是乙乙方的最优策略方的最优策略;aij xi v*v*,j=1,2,ni=1 m xi=1j=1nxi 0,i=1,2,m()aij yj v*v*,i=1,2,mi=1 m yj=1j=1nyj 0,j=1,2,n()22第10章 矩阵对策 定理定理定理定理4 4 4 4 若若(X*,Y*Y*)是矩阵对策是矩阵对策G的解的解,v*v*是是G的值的值,则对每一个则对每一个 iI 或或 jJ,都有都有 (1)若若 xi*0,则则 aij y yj j*=v*v*(2)若若 y yj j*0,则则 aij xi*=v*v*(3)若若aij y yj j*v*v*,则则 y yi i*=0 定理定理定理定理5 5 5 5 矩阵对策的基本定理矩阵对策的基本定理 任何矩阵对策任何矩阵对策G=S1,S2,A 在混合策略意义下在混合策略意义下 一定有解。一定有解。10.1 基本概念基本概念23第10章 矩阵对策10.2 特殊方法特殊方法10.2.10.2.1 1 矩阵对策的矩阵对策的矩阵对策的矩阵对策的特殊解法特殊解法特殊解法特殊解法 如前所述，矩阵对策总能用线性规划求解，但求解较繁如前所述，矩阵对策总能用线性规划求解，但求解较繁.而有些特殊的矩阵对策可能有一些更简单的特殊解法。而有些特殊的矩阵对策可能有一些更简单的特殊解法。一、特殊不等式方程组解法一、特殊不等式方程组解法 例例5 甲、乙二人一起玩甲、乙二人一起玩“锤子、剪子、袱子锤子、剪子、袱子”的游戏，的游戏，每人都可从每人都可从 锤、剪、袱锤、剪、袱 中选择一个出法中选择一个出法(纯策略纯策略)从而从而构成一个纯局势。该游戏规定：锤胜剪构成一个纯局势。该游戏规定：锤胜剪,剪胜袱剪胜袱,袱胜锤。袱胜锤。又若规定：胜则得又若规定：胜则得1分分,负则得负则得-1分，平手时双方各得分，平手时双方各得0分分,则甲方的赢得矩阵为：则甲方的赢得矩阵为：24第10章 矩阵对策 -x2+x3 v*v*x1 -x3 v*v*-x1+x2 v*v*x1+x2+x3=1 x1,x2,x3 010.2 特殊方法特殊方法A=()()y2 -y3 v*v*-y1 +y3 v*v*y1 -y2 v*v*y1+y2 +y3 =1 1y1,y2,y3 0 x1x2x30 1 -1-1 0 11 -1 0y1 y2 y3锤锤剪剪袱袱 锤锤 剪剪 袱袱25第10章 矩阵对策10.2 特殊方法特殊方法每组的前三式相加每组的前三式相加 131313131313X*=(,)T,Y*=(,)T -x2+x3 v*v*x1 -x3 v*v*-x1+x2 v*v*x1+x2+x3=1 x1,x2,x3 0()0 0 0再结合再结合 x1+x2+x3=1 y1+y2 +y3=1 1得得0 3v*v*0 3v*v*v*v*=0由每组前三式有由每组前三式有 x1 x2 x3 x1 y1 y2 y3 y1 则则 x1=x2=x3 y1=y2=y3()y2 -y3 v*v*-y1 +y3 v*v*y1-y2 v*v*y1+y2 +y3 =1 1y1,y2,y3 0 0 0 026第10章 矩阵对策10.2 特殊方法特殊方法二、取等式试解法二、取等式试解法 例例6 求解田忌赛马的对策问题求解田忌赛马的对策问题 -3x1-x2 -x3 -x4 +x5 -x6=v*-x1-3x2 -x3 -x4 -x5 +x6=v*x1 -x2-3x3 -x4-x5 -x6=v*-x1 +x2 -x3-3x4-x5 -x6=v*-x1 -x2 +x3 -x4-3x5 -x6=v*-x1 -x2 -x3 +x4 -x5-3x6=v*x1 +x2 +x3 +x4 +x5 +x6=1 x1,x2,x3,x4,x5,x6 0()-1 1-1 1-1 1-1 1-1 1-1 127第10章 矩阵对策10.2 特殊方法特殊方法 相加得相加得 -6(x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6)=6v*结合结合式式 x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6=1 1 得得 v*=-1代入代入,分别与分别与相加相加,得得 x x1 1=x x3 3=x x5 5 x x2 2=x x4 4=x x6 6有有X*()=(,1-,1-,1-)T/3,0,1 类似有类似有Y*()=(,1-,1-,1-)T/3,0,1 28第10章 矩阵对策10.2 特殊方法特殊方法三、无鞍点的二阶矩阵对策的三、无鞍点的二阶矩阵对策的通解公式通解公式通解公式通解公式y1 y2x1x2 1 21 2 a a bc d dA=D D=(a a +d d )-(b +c )x1*=d d-c D Dx2*=a a -b D Dy y1 1*=y y2 2*=d d-b D Da a-c D Dv*=adad-bc D D(8a a)(8b)(8c c)(8d d)29第10章 矩阵对策10.2 特殊方法特殊方法例例4A=7 47 43 63 6D D=(a a +d d )-(b +c )=(7 7 +6 6 )-(4 +3 )=6 6x x1*=d d-c D Dx x2*=a a -b D Dy y1*=y y2*=d d-b D Da a-c D Dv*=adad-bcbc D D6 6-3 6 6=12=7 7-4 6 6=12=6 6-4 6 6=13=7 7 -3 6 6=23=4242-1212 6 6=530第10章 矩阵对策10.2 特殊方法特殊方法3 3 4 4 7 7 6 3 26 3 21 21 2 3 x1-x y1 y2 y30 6 63 32 27 74 43 3v11x123M6-3x=v*v*3 +x=v*v*x*=34v*v*=3 34 43 334123y1+4y2=6y1+3y2=3 34 43 33 34 43 3X*=(,)T Y*Y*=(,0 0)T1:2:3:v1=3 3 x+6 6(1-x)v1=4 4 x+3 3(1-x)v1=7 7 x+2 2(1-x)y3=0例例7四、图解法四、图解法31第10章 矩阵对策10.2 特殊方法特殊方法10.2.10.2.2 2 特殊特殊特殊特殊矩阵对策的矩阵对策的矩阵对策的矩阵对策的化简化简化简化简一、降阶化一、降阶化汰劣准则汰劣准则 设对策设对策G=S1,S2,A,其中其中S1=1,2,m,S2=1,2,n,A=(aij)mn。记以记以 a(i)A阵的第阵的第 i 行行,iI aj A阵的第阵的第 j 列列,jJ (1)若若 a(l)a(k),则则l k,称称l 为为甲方的劣策略甲方的劣策略;(2)若若 as ar ,则则s r,称称s 为为乙方的劣策略乙方的劣策略.32第10章 矩阵对策 定理定理6 汰劣准则汰劣准则 设对策设对策 G=S1,S2,A,其中其中 S1=1 1,2,m ,S2=1,2,n,A=(aij)mn。若若 1 1 k,kI 且且 k1 1,从而可由从而可由G得到一个新对策得到一个新对策G=S1,S2,A,其中其中 S1=2,m,A=(aij)(m-1)n,且有且有 aij=aij i=2,3,m;j=1,2,n 则则G与与G之间有下述关系：之间有下述关系：(1)(1)G中乙方的最优策略与中乙方的最优策略与G中乙方的最优策略相同中乙方的最优策略相同;(2)(2)若若X*=(x2*,x3*,xm*)T是是G中甲方的最优策略，则中甲方的最优策略，则 X*X*=(0,x2*,x3*,xm*)T 就是就是G中甲方的最优策略；中甲方的最优策略；(3)(3)G的值的值 v*与与G的值的值 v*相等相等:v*=v*10.2 特殊方法特殊方法33第10章 矩阵对策10.2 特殊方法特殊方法例例82 1 4 2 33 5 1 4 22 6 3 2 42 3 4 3 6 3 4 0 5 2A=1 2 3451 2 3 4 54113243124D=(3+4)-(2+1)=4 4x2=4-24 4x4=3-14 4y1=4-14 4y3=3-24 4X*=(0,0,0)TY*=(,0,0,0)Tv v*=34-214 4=2 21 12 234第10章 矩阵对策10.2 特殊方法特殊方法 2 4 5 35 6 3 44 5 6 26 5 4 6 A=1 2 341 2 3 4 a(1)a(2)a(3)a(4)a1 a2 a3 a4a2 a1+a3a(1)a(3)+a(4)a(2)a(3)+a(4)4D=(6+6)-(2+4)=6 66624x3=6-46 6x4=6-26 6y3=6-26 6y4=6-46 6X*=(0,0,1/3,2/3)TY*=(0,0,2/3,1/3)Tv*=66-246 6=4 42 23 3 例例935第10章 矩阵对策10.2 特殊方法特殊方法二、稀疏化二、稀疏化同解变换同解变换 例例10 2 2 54 2 22 8 2A=0 0 32 0 00 6 0A=-2 定理定理7 设有两个矩阵对策：设有两个矩阵对策：GG =S1,S2,A A=(aij)mn GG=S1,S2,A A =(aijc c)mn 其中其中 c c 0 为一个常数。则为一个常数。则 (1)GG与与GG同解同解;(2)GG的值的值v*v*与与GG 的值的值v v*之间有下述关系：之间有下述关系：v*v*=v*v*c c+(9)36第10章 矩阵对策10.2 特殊方法特殊方法3x1 v 2x2 v 6x3 v x1 +x2 +x3=1 x1,x2,x3 0()()x1 v/3x2 v/2 x3 v/6 x1+x2+x3 v+)v 11112 2 54 2 22 8 2A=0 0 32 0 00 6 0A=-2x1 x2 x3由由()()：v 1故故 v =1x1 1/3x2 1/2x3 1/6y1 1/2y2 1/6y3 1/3由由定理定理4 4：、均取等式均取等式,得得X*=(1/3,1/2 ,1/6)TY*Y*=(1/21/2,1/61/6 ,1/31/3)Tv*v*=1+2=3 3例例1037第10章 矩阵对策10.2 特殊方法特殊方法例例11 田忌赛马田忌赛马田忌赛马田忌赛马-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 -3A=[phone] -2 0 2 0 0 0 0 -2 0 2 2 0 0 0 -2 0 0 2 0 0 0 -2A=x x1 1=x x3 3=x x5 5x x2 2=x x4 4=x x6 6v*=v*=-1 1v*=0 x x1 1 x x2 2x x3 3 x x4 4x x5 5x x6 638第10章 矩阵对策10.3 线性规划法线性规划法10.3.10.3.1 1 基本方法基本方法基本方法基本方法 由由定理定理定理定理5 5 5 5的证明知，的证明知，线性规划法线性规划法是矩阵对策的一种通用解法，是矩阵对策的一种通用解法，任何对策任何对策G=S1，S2，A的解（的解（X*，Y*Y*）与值）与值v*v*，都可由求解下面都可由求解下面两个两个互为对偶的互为对偶的互为对偶的互为对偶的 线性规划之一而得到：线性规划之一而得到：s.t.s.t.(P1 1 )：max v aij xi v，j=1，2，n （1）xi =1 （2）xi 0，i=1，2，m （3）(D1)：min v aij yj v，i=1，2，m （1）yj =1 （2）yj 0，j=1，2，n （3）i=1i=1j=1 j=1 n nmm39第10章 矩阵对策10.3 线性规划法线性规划法 例例12 试用线性规划方法求解对策试用线性规划方法求解对策G=S1，S2，A，其中：其中：1 2 -3 3 3 x1A=2 -2 3 1 1 x2 3 1 1 5 5 x3 y1 y2 y3 1 2 3解解 先建立其先建立其 LP 模型：模型：(P1 1 )：max v 2x1-2x2 +x3 v -3x1+3x2+x3 v 3 3x1 +x2+5 5x3 v x1+x2+x3 =1 x1,x2,x3 0s.t.40第10章 矩阵对策10.3 线性规划法线性规划法先标准化，再引进人工变量先标准化，再引进人工变量 x7，构造排列阵作初始基：构造排列阵作初始基：max v=v1-v2-Mx7 v1-v2-2x1+2x2-x3+x4 =0 v1-v2+3x1-3x2 -x3 +x5 =0 v1-v2-3x1 -x2-5x3 +x6 =0 x1+x2 +x3 +x7=1 v1,v2,x1,x2,x3,x4,x5,x6,x7 0s.t.max v 2x1-2x2 +x3 v -3x1+3x2 +x3 v 3x1 +x2+5x3 v x1+x2+x3 =1 x1,x2,x3 0s.t.(P1 1 )：41第10章 矩阵对策34/310.3 线性规划法线性规划法42第10章 矩阵对策5/31/210.3 线性规划法线性规划法 主元主元1/2是如何确定的？是如何确定的？43第10章 矩阵对策10.3 线性规划法线性规划法 -1 y1*y2*y3*表（表（e）已得最优解已得最优解X*X*，但由于有一个基变量但由于有一个基变量x1*=0，这时可让这时可让x1离基，改用对离基，改用对偶单纯形法继续迭代，以便求出偶单纯形法继续迭代，以便求出对偶问题对偶问题的的另一个另一个最优基本解最优基本解。44第10章 矩阵对策 由由 表表（e）、（f）可知：可知：X*=(0，0，1)T 10.3 线性规划法线性规划法 0,1Y*=(2/5+2/5，3/5-2/5，0)Tv*=1 4/5 2/5 2/5+2/5 Y*=1/5 +(1-)3/5 =3/5-2/5 0 0 0 45第10章 矩阵对策10.3 线性规划法线性规划法 对于对于LP问题（问题（P1）、（）、（D1），），也可以通过适当的变换使其化简，然也可以通过适当的变换使其化简，然后再求解。对后再求解。对（D1）：10.3.10.3.2 2 化简方法化简方法化简方法化简方法 由于总能采用由于总能采用同解变换同解变换 aij=aij+c，i=1,2,m;j=1,2,n使使A=（aij）m n化成化成A=（aij）m n;这是因为（这是因为（2）、（）、（3）成立，所以由（）成立，所以由（1）可得）可得 因此只要取因此只要取c 0充分大充分大，就能保证一切，就能保证一切 aij 0，从而保证变量从而保证变量v 0。min v aijyj v，i=1，2，m（1）yj =1 （2）yj 0，j=1，2，n （3）s.t.j=1 j=1 n nyj=vyj，j=1，2，n因此，为便于叙述，不妨假定（因此，为便于叙述，不妨假定（D1）中的）中的 v 0。这样通过变量代换。这样通过变量代换v aijyj 0 j=1 nyj 1 1yj=1/v1/vyj46第10章 矩阵对策 （D）：max z z=yj aijyj 1，i=1，2，m yj 0，j=1，2，n （D）：min v v aijyj 1，i=1，2，m yj=1/v v yj 0，j=1，2，n10.3 线性规划法线性规划法可将（可将（D1）化为：化为：则（则（D1）可等价化为）可等价化为由于目标要求由于目标要求 v v 最小化，故最小化，故 1/v v 应最大化。记应最大化。记s.t.j=1 j=1 n ns.t.j=1j=1n n z z=1/v v=yjj=1 n47第10章 矩阵对策 5 0 6 1 6 4 4 4 8x1 x2 x310.3 线性规划法线性规划法 类似地，可将（类似地，可将（P1）等价化为等价化为 A=仍就仍就例例12说明。先用同解变换把说明。先用同解变换把A阵中所有元素都加上阵中所有元素都加上3,化为非负，得：化为非负，得：v*v*=1/z*,X*=v*v*X*，Y*=v*v*Y*(10)z*=w*并且有并且有 s.t.（P）：min w=xi aij xi 1，j=1,2,n xi 0，i=1,2,mi=1i=1 m my1 y2 y348第10章 矩阵对策10.3 线性规划法线性规划法 从而有从而有 s.t.s.t.5y1 +6y3+y4 =1 y1+6y2+4y3 +y5 =14y1+4y2+8y3 +y6 =1 y1，y2，y3，y4，y5，y6 0max z=y1+y2+y3引入松弛变量引入松弛变量y4，y5，y6，标准化得：，标准化得：5y1 +6y3 1 y1+6y2+4y3 14y1+4y2+8y3 1 y1，y2，y3 0max z=y1+y2+y3（D）：49第10章 矩阵对策5410.3 线性规划法线性规划法50第10章 矩阵对策10.3 线性规划法线性规划法151第10章 矩阵对策由上表得由上表得（D）的解：的解：z*z*=1/41/4 Y*=(1/5，1/20，0)T 或或 (1/10，3/20，0)T X*=(0，0，1/4)T故按故按(10)式得式得 v*v*=1/z*z*=4 4 X*=4 4X*=(0，0，1)T Y*Y*=4 4Y*=(4/54/5，1/51/5，0 0)T 或或(2/5 2/5，3/53/5，0 0)T再按再按(9)式得式得 v*v*=v*v*-3 3=4 4-3 3=1 110.3 线性规划法线性规划法52第10章 矩阵对策10.3 线性规划法线性规划法 定理定理8 矩阵对策值的矩阵对策值的取值范围取值范围取值范围取值范围 设对策设对策G=S1，S2，A，其中，其中A=(aij)m n。记记(11b)(11a a)即即v v*v-，v+则则G的值的值v-=max min aijijv+=min max aijij 这样这样,当我们用线性规划法求解当我们用线性规划法求解（P）或或（D）时，可时，可先根据先根据定理定理 8 估计一下对策值估计一下对策值 v*v*的取值范围，若的取值范围，若 v v*的下界的下界 v-0，则，则不必不必不必不必对矩阵对矩阵A实施实施同解变换同解变换同解变换同解变换；仅当；仅当 v-0 时才须时才须实行同解变换。实行同解变换。(12)max min aijv v*min max aij iijj53第10章 矩阵对策10.3 线性规划法线性规划法 如如 例例12：min aij-3-2 1max由于由于 v-=max min aij=1 0所以在该例的化简解法中，实际上不须将所以在该例的化简解法中，实际上不须将 A 阵中每个元素都阵中每个元素都加上加上3，而可直接由，而可直接由A阵构造问题阵构造问题（D）并根据其求解并根据其求解G。1 2 -3 3 3A=2 -2 3 1 1 3 1 1 5 5 1 2 354第10章 矩阵对策10.3 线性规划法线性规划法 但若赢得矩阵为但若赢得矩阵为min aij-4-3 0max因因v-=max min aij=0 0A=1 -4 2-3 2 0 0 0 4则则不能由不能由此矩阵此矩阵此矩阵此矩阵直接构造直接构造化简的化简的LP模型模型。55第10章 矩阵对策 故此时不能直接由故此时不能直接由 A A 构成问题构成问题(D)或或 (P)，而而必须先实行必须先实行同解变换同解变换同解变换同解变换，将，将 A A 中每个元素都加上同一个中每个元素都加上同一个正数正数 c c(如如1 1)，化为化为A A ，然后才能由然后才能由A A 构成问题构成问题 (D)并求解之并求解之。由于这样得到的对策由于这样得到的对策 G 的值的值v*=v v*+c c v-+c c=c c 0 0故问题故问题 (D)肯定有最优解肯定有最优解。否则，若直接由否则，若直接由 A A 阵阵构成问题构成问题 (D)，则不难验证此时则不难验证此时 (D)为为解无界解无界。10.3 线性规划法线性规划法56第10章 矩阵对策