第11讲：对策论(一)+(LP作业).ppt
第第1111讲：对策论讲：对策论(一一)浙江工业大学经贸管理学院 曹柬1 1、对策现象及其三个要素、对策现象及其三个要素（以（以“田忌赛马田忌赛马”为例）为例）运筹学 第11讲：对策论（一）一、对策论的基本概念一、对策论的基本概念u 局中人局中人：与对策有：与对策有直接直接效用关系的实体（人、集体等）效用关系的实体（人、集体等）齐王、田忌、孙膑、马齐王、田忌、孙膑、马XXu 策略策略：一个局中人对付其他局中人的方法或措施：一个局中人对付其他局中人的方法或措施田忌的策略共有田忌的策略共有 3！=61 1=(=(上上,中中,下下)；2 2=(=(上上,下下,中中)；3 3=(=(中中,上上,下下)；4 4=(=(中中,下下,上上)；5 5=(=(下下,上上,中中)；6 6=(=(下下,中中,上上)。同理，齐王的策略分别为：同理，齐王的策略分别为：1 1=(=(上上,中中,下下)；2 2=(=(上上,下下,中中)；3 3=(=(中中,上上,下下)；4 4=(=(中中,下下,上上)；5 5=(=(下下,上上,中中)；6 6=(=(下下,中中,上上)。XX策略集策略集：局中人：局中人i 所有策略的集合，用所有策略的集合，用Si 表示表示例如：设田忌为第例如：设田忌为第1人，人，i=1；齐王为第；齐王为第2人，人，i=2。则田忌的策略集为：则田忌的策略集为：S11,2,3,4,5,6；齐王的策略集为：齐王的策略集为：S21,2,3,4,5,6。局势局势：每个局中人各从其策略集中取一个策略参与对策，则：每个局中人各从其策略集中取一个策略参与对策，则这些策略的组合称为局势，用这些策略的组合称为局势，用s表示。表示。例如：田忌和齐王的某个局势为：例如：田忌和齐王的某个局势为：s s5151或或(5 5,1 1)，即，即s s51 51=(=(5 5,1 1)U U1 1(s s5151)=)=u 赢得函数赢得函数：局中人：局中人i 在局势在局势s下的所得，用下的所得，用Ui(s)表示表示U U2 2(s s5151)=)=U U1 1(s s1111)=)=U U2 2(2 2,5 5)=)=1-1-31已知：已知：1 1=(=(上上,中中,下下)；2 2=(=(上上,下下,中中)；3 3=(=(中中,上上,下下)；4 4=(=(中中,下下,上上)；5 5=(=(下下,上上,中中)；6 6=(=(下下,中中,上上)。i ij j,i i=j j=1,6=1,6。运筹学 第11讲：对策论（一）2 2、矩阵对策的基本模型、矩阵对策的基本模型h 赢得矩阵：局中人赢得矩阵：局中人i 在不同局势下的赢得所组成的矩阵，用在不同局势下的赢得所组成的矩阵，用Ai 表示。表示。例如：田忌的赢得矩阵为：例如：田忌的赢得矩阵为：1A123456123456齐王的赢得矩阵为：齐王的赢得矩阵为：A2A1，A1 也可称为齐王的损失矩阵也可称为齐王的损失矩阵运筹学 第11讲：对策论（一）h 矩阵对策矩阵对策 两个局中人的对策表述两个局中人的对策表述 G（S1,S2,A1）（S1，S2，A）本节中我们仅研究二人有限零和对策，即本节中我们仅研究二人有限零和对策，即A A1 1+A A2 2=0=0运筹学 第11讲：对策论（一）3 3、对策的分类、对策的分类 按局中人的数目分类：二人对策，多人对策（诸侯争霸）按局中人的数目分类：二人对策，多人对策（诸侯争霸）按策略的数目分类：有限对策，无限对策（警察抓罪犯）按策略的数目分类：有限对策，无限对策（警察抓罪犯）按赢得矩阵之和是否为零分类：零和对策，非零和对策（囚按赢得矩阵之和是否为零分类：零和对策，非零和对策（囚徒困境）徒困境）按局中人是否合作分类：非合作对策（同类企业竞争），合按局中人是否合作分类：非合作对策（同类企业竞争），合作对策（供应链成员，作对策（供应链成员，OPEC等）等）综上所述，田忌赛马为二人有限零和不合作对策。综上所述，田忌赛马为二人有限零和不合作对策。运筹学 第11讲：对策论（一）例例1二、纯策略二、纯策略如果甲、乙都是理性的人，应各选什么策略？如果甲、乙都是理性的人，应各选什么策略？设对策设对策G（S1，S2，A），其中），其中1231234A运筹学 第11讲：对策论（一）设有对策设有对策G（S1，S2，A），其中），其中S11 1,2 2,，m m，S21,2,n，A=(aij)mn。如果如果A中存在一个元素中存在一个元素ark满足：满足：则局势（则局势（r,k）称为）称为G G 的解或鞍点。的解或鞍点。*=r r,*=k k称称为甲、乙的为甲、乙的最优纯策略最优纯策略。设。设G G 的值为的值为v vG G，v vG G =a arkrk 。运筹学 第11讲：对策论（一）例例2求解求解G（S1，S2，A），其中），其中1231234A运筹学 第11讲：对策论（一）例例3 某单位采购员在秋天时要决定冬季取暖用煤的采购量。某单位采购员在秋天时要决定冬季取暖用煤的采购量。已知在正常气温条件下需要煤已知在正常气温条件下需要煤15吨，在较暖和较冷气温条吨，在较暖和较冷气温条件下需要煤件下需要煤10吨和吨和20吨。假定冬季的煤价随天气寒冷程吨。假定冬季的煤价随天气寒冷程度而变化，在较暖、正常、较冷气温条件下每吨煤的价格度而变化，在较暖、正常、较冷气温条件下每吨煤的价格分别为分别为100元、元、150元和元和200元。又设秋季时每吨煤的价元。又设秋季时每吨煤的价格为格为100元，在没有关于当年冬季气温情况准确预报的条元，在没有关于当年冬季气温情况准确预报的条件下，秋季应采购多少吨煤能使总支出最少？件下，秋季应采购多少吨煤能使总支出最少？运筹学 第11讲：对策论（一）三、混合策略三、混合策略设有对策设有对策G（S1，S2，A），其中），其中 S11 1,2 2,，m m，S21,2,n，A=(aij)mn。记：记：则分别称则分别称S1*和和S2*为局中人甲、乙的混合策略集；对于为局中人甲、乙的混合策略集；对于称称x和和y为混合策略，（为混合策略，（x,y）为混合局势。）为混合局势。运筹学 第11讲：对策论（一）例例4求解求解G（S1，S2，A），），S11,2，S2 1,2，求甲乙两人应采取的策略？，求甲乙两人应采取的策略？如果双方进行一次对策，则甲随机选择，乙选如果双方进行一次对策，则甲随机选择，乙选2的概率大一点；的概率大一点；如果双方进行六次对策，甲分别取如果双方进行六次对策，甲分别取3次次1 1和和2 2，乙选，乙选2 2次次1 1，4 4次次2 2运筹学 第11讲：对策论（一）例例5求解下列矩阵对策，其中：求解下列矩阵对策，其中：作业：作业：12.112.1，12.212.2，12.312.3，12.412.4运筹学 第11讲：对策论（一）习题习题习题习题2-32-32-32-3解：解：设设 xij采用采用第第 i(i=1,2，对应于甲，对应于甲,乙乙)种机床加工第种机床加工第 j 种工件的种工件的数量数量(j=1,2,3)，z为总加工费用，则该问题的线性规划模型可写为：为总加工费用，则该问题的线性规划模型可写为：min z=13x11+9x12+10 x13+11x21+12x22+8x23 s.t.0.4x11+1.1x12+x13 700 0.5x21+1.2x22+1.3x23 800 x11+x21 =()300 x12+x22 =()500 x13+x23 =()400 xij 0 (i=1,2，j=1,2,3）这两台机床的可用这两台机床的可用台时数分别为台时数分别为700和和800，三种工件的待，三种工件的待加工数量分别为加工数量分别为300、500和和400 u LP作业讲解作业讲解运筹学 LP作业讲解 1.11.1 (1)(1)多重最优解多重最优解 (2)(2)无可行解无可行解 (3)(3)惟一最优解惟一最优解 (4)(4)无界解无界解 1.71.7 (1)(1)无界解无界解 (3)(3)极点解极点解X X*=2/5,9/5,1,0*=2/5,9/5,1,0T T，Z Z*=17/5*=17/5 习题习题2-62-6 Z Z*=9000,*=9000,多重最优解多重最优解运筹学 LP作业讲解习题习题习题习题2-72-72-72-7解：解：设需要甲、乙、丙、丁肥料各设需要甲、乙、丙、丁肥料各x1 1，x2 2，x3 3，x4 4千克，则该问题的线性规千克，则该问题的线性规划模型可写为：划模型可写为：min z=0.04x1+0.15x2 +0.10 x3+0.13x4 s.t.0.03x1+0.30 x2+0.15x4 32 0.05x1+0.20 x3+0.10 x4 24 0.14x1+0.07x4 42 xi 0 (i=1,2,3,4）该问题存在两个极点解：该问题存在两个极点解：则此题有多重最优解：则此题有多重最优解：运筹学 LP作业讲解max 1000 x11+1000 x12+1000 x13+700 x21+700 x22+700 x23+600 x31+600 x32+600 x33st8x11+6x21+5x31=20008x12+6x22+5x32=30008x13+6x23+5x33=150010 x11+5x21+7x31=400010 x12+5x22+7x32=540010 x13+5x23+7x33=1500 x11+x12+x13=600 x21+x22+x23=1000 x31+x32+x33=0240 x11+180 x21+150 x31-136x12-102x22-85x33=0184x12+138x22+115x33-320 x13-240 x23-200 x33=0320 x13+240 x23+200 x33-136x12-102x22-85x33=0176x13+132x23+110 x33-120 x11-90 x21-75x31=0120 x11+90 x21+75x31-144x13-108x23-90 x33=0end附：附：附：附：1.15 1.15 LindoLindo语句语句语句语句最优值最优值:Z*=801000最优解：最优解：x11=150,x12=375,x13=75,x23=150,x31=160,其余其余xij=0运筹学 LP作业讲解n 求解求解求解求解LPLPLPLP模型，注意答题的规范性：模型，注意答题的规范性：模型，注意答题的规范性：模型，注意答题的规范性：X X X X*=*=*=*=，Z Z Z Z*=*=*=*=n 如果是求解实际问题，或模型有多重解，尽可能如果是求解实际问题，或模型有多重解，尽可能如果是求解实际问题，或模型有多重解，尽可能如果是求解实际问题，或模型有多重解，尽可能 采用极点解来表示问题的解，对多重解需作说明采用极点解来表示问题的解，对多重解需作说明采用极点解来表示问题的解，对多重解需作说明采用极点解来表示问题的解，对多重解需作说明Q作业说明作业说明运筹学 LP作业讲解习题习题2-5有机会再讲！有机会再讲！
