1、数模考试复习重点一、纳什均衡-理性的 书P188（1）（概念、特征、思想（可实施性解-互为最优）、意义概念：在N人参与的标准式博奕G=S1,S2,.Sn,U1,U2Un中,对每一个人Si*Si是他针对其他N-1个参与者的策略S*-i=(S1*,S*i-1,S*i+1,Sn*)的最佳组合,则称策略组合为(S1*,S2*,Si*,Sn*)为G的一个纳什均衡,即Ui(S1*,S2*,Si*,Sn*)Ui(S1*,S2*S*i-1,Si,S*i+1Sn*)或 Ui(Si*,S*-i) Ui(Si,S*-i),S-i指扣除Si的其他策略. 从定义可以看出: A、它是博弈结果的一致预测,NE具有稳定性、可
2、自动实施性，从第（1）式看出，i人没有单独改变Si的积极性B、NE是在独立决策下，自己组织产生的，而非它组织的（自下而上，非自上而下的，下-微观，上-宏观）（分散/集中）C、局中人是个人理性的，以追求自身利益最大化为目标，但NE更强调（突出）一种公平性、无排它性核心思想：寻求的是最优化可实施性，互为最优的解。用决策分析方法去解决第i人的预测（除i人之外其他参与者的付出策略行为）（2）精炼的纳什均衡：序贯的理性策略（反向逆推）（多阶段）概念:子博奕精炼纳 什均衡:原博奕中的纳什均衡, 如果它在任何子博奕中仍然是纳什均衡, 则称它为子博奕精炼纳什均衡.它排除了不可置信的威胁.二、动态规划的最优性原
3、理、启示 书P107答：动态规划的最优性原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，一个最优策略的子策略都是最优的。 长期以来最优性原理被作为动态规划的理论基础，解决了许多类型决策过程的优化问题。然而，“最优性原理”与动态规划基本方程并不是无条件等价，而动态规划的基本方程在动态规划的理论和方法中起着更重要的作用。反映动态规划基本方程的是最优性原理，它是策略最优性的重要条件，而最优性原理仅仅是策略最优性的必要条件，所以可将动态规划的基本方法或者最优性定理作为动态规划的理论基础。最优定理：对：min
4、L=Lk(Xk, Uk)(1)S.T. Xk+1= ( Xk, Uk) X1已知 Xk X, Uk U若， Uk 为最优控制序列，那么，任意一个后子控制序列 Uk 一定是以Xj为状态经过n-i步控制后使Lk(Xk, Uk)取极小，即：minL=Lk(Xk, Uk)(1)S.T. Xk+1= ( Xk, Uk) K=Jn Xk已知三、多目标规划和单目标规划的区别：都用单纯形答：相同点：1、都可用单纯形表解。2、都是对目标进行规划优化。不同点：单目标规划（传统OR模型）存在以下特点：1、目标的单一性。2、线性规划的约束是刚性的。3、过分强调最优性。希望建立一种模型：能分析多目标的决策问题，允许目标
5、之间存在冲突性，能够表达目标的偏好结构以表达决策者的主观判断、经验，能克服硬约束的局限性，充分体现柔性的决策理念。多目标规划（现代OR模型）的特点：1、研究多目标决策问题，这些目标具有不可比性和冲突性2、相互冲突的目标构成一个体系，决策者对目标系统有个主观判断，称为偏好结构。偏好结构反映了决策者的知识、经验和他对问题的理解。3、各个目标具有确定的期望值，决策者的任务是极小化目标的偏差值。4、目标规划中只有软约束，体现了柔性的决策理念。四、线性规划的目标规划线性规划的目标指所要达到的最优结果（最大或最小）。约束条件指所能产生结果的限制。线性规划是一种解决带有约束条件的最优化问题的方法。解决线性规
6、划问题的过程分为三个步骤：第一步，定义问题和收集数据。必须向管理者咨询所要考虑问题涉及到的数据以及确定研究的合理目标。第二步，建立模型，用恰当的数学式表示问题。第三步，求出问题的最优解。第四步，进行敏感性分析，检查条件发生变化时可能发生的情况。五、 学过几种模型的构成：（1） 多目标规划模型的要素：约束条件，决策变量、偏差变量、目标函数、偏好次序约束条件是对可能产生结果的限制，线性等式或不等式。目标约束是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束。决策变量是向量（X1Xn）T决策人要考虑和控制的因素非负
7、.目标函数: Z=(X1Xn)线性式,求Z极大或极小正负偏差变量d+表示决策值超过目标值的部分:负偏差变量d-表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目标值，故恒有d+ x d- =0。偏好次序：主观性的喜好的先后排序（2） 多目标函数为线性等式，有目标的优先级，化刚性为柔性六、 动态规划（1） 目标函数是多阶段性能指标的加总（2） 决策变量、状态变量、状态方程的约束条件决策变量：描述决策的变量，常用Uk（Sk）表示第K阶段，当状态处于Sk时的决策变量，它与一个决策相对应状态变量：描述过程状态通常用状态变量。它可用一个数、一组数或一向量（多维情形）来描述。常用Sk表示
8、第K阶段的状态变量集。状态方程的约束条件：状态转移方程是确定过程由一个状态到另一个状态的演变规律的描述方式。若给定第K阶段状态变量Sk的值，如果该阶段的决策变量Uk一经确定，第K+1阶段的状态变量Sk+1的值也就完全确定。即Sk+1的值随Sk和Uk变化而变化。这种确定的对应关系，记为Sk+1=Tk（Sk，Uk）（3） 目标函数：约束函数和状态函数指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数；指标函数的最优值，称为最优值函数。七、 重要定义、原理法则（1）博弈论：又称对策论，是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题。决策论（最优解）与对策论
9、（均衡解）的联系与区别单人与多人，多人中无相互影响的不是对策集中与分散的决策模式，如计划经济就是集中的决策模式博弈的构成要素1、参与人；2、行动；3、信息；4、策略；5、支付；6、结果；7、均衡纳什均衡的定义：在一个n个参与者标准博弈G= S1，S2， Sn ； U1（）， U2（）， Un（），中，如果战略组合（S1，S2， Sn ）满足：对每个参与者i， Si是它针对其他参与者所选的战略S-i的最优反应战略。即Ui（si ，s-i ） Ui（si ，s-i ）纳什均衡解意义：它是博弈结果的一致预测，这种结果具有内在的稳定性和可自动实施性。完全信息静态博弈：参与者、参与者的策略或策略集、支付
10、函数/扩展式：战略式完全信息动态博弈的扩展式：博弈树定义：参与人行动有先后顺序，且后行方在自己行动之前能观察到先行方的行动。 构成要素：1.参与者集合；2.参与者行动的顺序；3.参与者行动集；4.参与者的信息集；5.参与者的支付函数子博弈定义：一个扩展式博弈的子博弈G是由一个决策结（X）和所有的该决策结的后续决策结（T（X）组成，它满足如下条件：1. x是单结的信息集。2. 后续结点的所有信息集上的结点都属于后续结集合。子博弈精炼的纳什均衡的求法：反向递推算法（2）线性规划：变量：基变量、非基变量、基解-令非基变量=0的基解，最优解：最优基 基变量可以被非基变量表示，它线性无关，基变量前的序数
11、矩阵为非奇异/线性无关，一般 （3）目标规则：A、单纯型法：B、终止条件：检验数法则（即回答什么时候从这个目标集跳到另一个目标集）：检验数达到最优（一），上一级已最优，本级优化不能破坏上级优化，自身的检验数符号法则与列消除规则（4）静态博奕与动态博弈的区别所谓静态博弈是指各参与人同时行动且只行动一次，而动态博弈是指各参与人行动有先后，是序贯行动，后行动者根据先行动者所作的所有策略来决定自己的选择，无最优要求，而先行方要考虑后行方的最优方法做出反应。八、线性规划：（1）图解法 例：MAXZ=40X1+50X2 X1+2 X230 3 X1+2 X260 2 X224 X1,X20解: (1)确定
12、可行域 X10, X1=0(纵) X20, X2=0(横) X1 + 2 X230 X1 + 2 X2 =30 (0,15) (30,0) 3X1 + 2 X2 = 60 (0,30) (20,0) 2 X2=24 X2=12 (2)求最优解 Z=40 X1+50 X2 0=40 X1+ 50 X2 (0,0), (10,-8) X1+2 X2=30 C点 3X1 + 2 X2=60 解: X*=(15, 7.5), Z(max)=975最优解：BC线段B点 C点X(1)=(6,12) X(2)=(15,7.5)X= X(1)+(1-) X(2) (0 1)无界无有限最优解例4、 maxZ=3
13、X1+2X2 -X1 -X2 1X1 , X2 0无解 无可行解（2）单纯形法（初始的单纯形表，换基迭代一次） 题目同上(一) 化为标准形 X1+ 2 X2 + S1=30S.T. 3 X1 + 2 X2+S2=60 X2 + S3=12 X1, X2, S1, S2, S30(二) 引入松弛变量MAX=40X1+50X2+0*S1+0*S2+0*S3 X1+ 2 X2 + S1=30S.T. 3 X1 + 2 X2+S2=60 X2 + S3=12 X1, X2, S1, S2, S30(三) 画出单纯形表构造单纯初始形表 X1 X2 S1 S2 S3 MS1 1 2 1 0 0 30 S2
14、 3 2 0 1 0 60 S3 0 1* 0 0 1 12 -40 -50 0 0 0 0(四) 换基迭代一次 X1 X2 S1 S2 S3 MS1 1 0 1 0 -2 6 S2 3 0 0 1 -2 36 S3 0 1* 0 0 1 12 -40 0 0 0 50 600（3）人工变量、惩罚项（不考）九、多目标规划的建模（不需计算）多目标规划模型结构要素：决策变量，目标和约束条件，偏好次序，正负偏差变量；等式的约束方程；目标达成向量建立目标规划模型的步骤：1.设立决策变量。 2.找出目标和所有阻碍目标实现的约束条件。3.确定目标的优先级，p1的优先级最高，p2次之，依次类推。4.建立一个
15、基础模型。5.将基础模型改写为目标规划模型。5.1为每一个理想化目标设置一个满意的目标期望值，化为现实目标。5.2对所有的现实目标多增加一对正负偏差变量，化为等式。5.3写出目标达成向量。决策要求约束类型软约束形势达成函数准确地达到g(x)=g0g(x)+ d- -d1+=g0min(d- + d1+)不准小于g(x) g0g(x)+ d- -d1+=g0min(d-)不准大于g(x) g0g(x)+ d- -d1+=g0min(d+)极大化max g(x)g(x)+ d- -d1+=g0min(d-)极小化min g(x)g(x)+ d- -d1+=g0min(d+) 例1: 生产计划决策问
16、题 某企业生产甲、乙两种产品，由加工和装配两个车间完成，如表1所示。现经营管理部门提出下列目标：1、 在制品生产储备资金占用每月不超过4600元；2、 产品甲销售数量实现50件；3、 尽量减少两个车间的剩余工时；4、 加工车间加班时间每月不超过20小时；5、 产品乙销售数量80件。问题：如何规则企业下月的生产计划？ 表：生产管理、成本核算及市场营销数据表 工时项目产品工时定额每月可用工时 （小时/月） 甲 乙加工车间（18元/时） 2 1 120装配车间 （9元/时） 4 3 150生产储备资金（元/件） 50 30 市场销售量（件/月） 50 80单件利润值（元件） 100 76 （一）设立
17、决策变量：X1：甲产品的计划产量X2：乙产品的计划月产量（二）目标和约束条件：50 X1+ 30 X2 4600 P1X1 50 P2MIN120-（2X1 + X2） P3MIN150-（4X1 + 3X2） P32X1 + X2140 P4X280 P5 x1，x20（三）将基础模型改写为目标规划模型 MINd1+ ,d2- , (d3+ + d4+) , d5+ , d6- 50 X1+ 30 X2 d1+ +d1- = 4600 P1X1 d2+ +d2- = 50 P22X1 + X2 d3+ +d3- =120 P34X1 + 3X2 d4+ +d4- =150 P32X1 + X
18、2 d5+ +d5- =140 P4X2 d6+ +d6- =80 P5x1，x2 ， di+ ， di- ，i=160例： 工资及人员调整问题 某研究所现有研究人员37名，额定满员人数42名，各级人员的工资级别与满足额定人数规定如表2所示。现计划进行工资及人员调整，调整的目标要求如下：1、 年工资总额不超过6万元；2、 调整后各级人员不超过额定满员人数；3、 升级调整面不少于额定满员人数的20%；4、 三级要保持满员额定人数； 并规定三级人员的空缺由外调或招聘增补，其余各级人员均从原有级别人员中晋升，一级人自然减员率为10%。问题：如何确定各级人员的调整人数？ 表2：各级人员的工资级别及满足
19、额定人数表级别年工资数（元/年）现有人数额定满足人数 三级 1000 15 15 二级 1500 12 15 一级 2000 10 12设立决策变量： X1：为晋升到一级人员数；X2：为晋升到二级人员数：X3：为三级人员增补数目标和约束条件： 1000（15-X2+X3）+1500（12-X1+X2）+2000（10-10*10%+X1）60000 P115-X2+X315 P2 12-X1+X215 P210-10*10%+X112 P2X115*20% P3X215*20% P315-X2+X3=15 P4X1，X2 0MINd1+ , (d2+ + d3+ + d4+), (d5- +
20、d6-),(d7+ + d7-)X1+X2+2X3-d1+ + d1=18-X2+X3d2+ + d2- =0 -X1+X2d3+ + d3- =3 X1d4+ + d4- =3X1d5+ + d5- =3 X2d6+ + d6- =3-X2+X3d7+ + d7-=0 X1，X2 0 ，di+ ， di- ，i=170十、动态规划-计算1、划分阶段；2、确定状态变量及允许状态集合；3、确定决策变量及决策空间；4、确定状态转移方程；5、确定转移指标函数并建立递归方程 Bellman最优性原理 “作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决
21、策必然形成最优子策略”（1）连续型：机器设备使用100台。设某厂有同种机器100台，这种机器可以做2种工作，用这种机器作第一种工作一周，将损坏1/3，所得利润为10，用这种机器作第二种工作二周，将损坏1/10，所得利润为7，问：如何分配100台机器做上述两件工作，做4周内总利润最大？解：设Xk表示第K周可使用的机器数 Uk表示第K周可使用的第一种机器数 可见XkUk表示第K周可使用的第二种机器数 4MAXJ=（10Uk+7（Xk-Uk） K=1 0UkXk ST k+1= 2/3Uk +9/10（Xk-Uk）（K=1，2，3，4） X1=100 （一）反向逆推基本方程，确定最优控制序列 （1）
22、K=4J4*=MAX3U4+7X4 0U4X4 U4=X4， J4*=10X4 （2）K=3 J3*=MAX3U3+7X3+J4* 0U3X3 =MAX3U3+7X3+10（2/3U3+9/10（X3-U3） 0U3X3 U3*=X3，J3*=16*2/3*X3 （3） K=2 J2*=MAX3U2+7X2+J3* 0U2X2 =MAX3U2+7X2+16*2/3*X3 0U2X2=MAX3U2+7X2+16*2/3*（2/3U2+9/10（X2-U2） 0U2X2 =MAX22X2-8/9U2 0U2X2U2=0，J2*=22X2（4） K=1 J1*= MAX3U1+7X2+J1* 0U1
23、X1 = MAX3U1+7X2+22（2/3U1+9/10（X1-U1） 0U1X1 =MAX（134X1-32/15U1）U1*=0，J*=134/5X1最优决策序列：0，0，X3，X4（二）顺向递推，确定最优状态序列K=1，X1*=100，U1*=0K=2，X2*=2/3U1+9/10（X1-U1）=90，U2*=0K=3，X3*=2/3U2+9/10（X2-U2）=81，U3=81K=4，X4*=2/3U3+9/10（X3-U3）=54，U4=54 所以，最优的决策结果为0，0，81，54（2）离散型（表格式）：3个车间，5台设备。要求：建模、计算：（1）反向逆推求 （2）顺向逆推 （过
24、程要）某工厂拟将某种设备5台分配给甲、乙、丙3个工厂，各工厂获得设备后可盈利如下表。问这5台设备应如何分配使其利润最大？ 工厂台数甲乙丙000013542710439111141211125131112解：Xk为分配给第K个工厂的设备台数；Sk为分配给第K个工厂到第3个工厂的设备台数 Sk+1=Sk-Xk S（1）=5台 3性能指标函数： MAXJ= Pk（Xk） 这里Pk（.）是以表格形式表示,本例与Sk无关 K=1用f(Sk)表示将Sk台设备分配到第K工厂到第3个工厂所得的最大盈利值(后子阶段的性能函数最优值. Fk*(Sk)=MAXPk(Xk,Sk)+Fk+1(Sk+1) F4(S4)=
25、0 K=3,2,1K=3 X3S3 P3*(X3)F3(S3)X3* 0 1 2 3 4 5 0000 1 0441 204441或2 304411113 4 0441112124 5044111212124或5K=2 X2S2 P2(X2)+F3(S2-X2)F2(S2)X2* 0 1 2 3 4 5 0000 1 0+4551 20+45+410102 30+115+410+411142 4 0+125+1110+411+411161 50+125+1210+1111+411+411212K=1 X1S1 P1(X1)+F2(S1-X1)F1(S1)X1* 0 1 2 3 4 5 50+2
26、13+167+149+1012+513+0210或23、顺向递求最优分配方案 K=1, S1*=5, X1*=0 或 S1*=5,X1*=2 K=2, S2*=5, X2*=2 或 S2*=3,X2*=2 K=3, S3*=3, X3*=3 或 S3*=1,X3*=1 K=4, S4*=0 总结: 最优设备方案是(0、2、3)或（2、2、1），最优利润为21。十一、对策纯策略/混合策略的NE（1）划线法（矩阵纯策略） （2）等支付原则（混合策略的纳什均衡） （1）划线法 A B C2，0，12，0，12，0，12，0，11，2，02，0，12，0，12，0，10，1，2 A B CA B C2
27、，0，11，2，02，0，11，2，01，2，01，2，02，0，11，2，00，1，2AB C A B C2，0，12，0，10，1，22，0，11，2，00，1，20，1，20，1，20，1，2A B C NE为（AAA，ABA，BBB，ACC，CCC） （2）等支付原则 乙 C P2 D 1-P2 甲A P1 2，35，2B 1-P1 3，11，5 1、 甲选择混合策略（P1，1-P1） 乙的纯策略期望支付=3P1+1（1-P1） =2P1+5（1-P1）即 3P1+1-P1=2P1+5-5P1 P1*=0.8 2、乙选择混合策略（P2，1-P2）甲的纯策略期望支付=2P2+5（1-P2
28、） =3P2+1（1-P2） P2*=0.8这个博奕的混合策略纳什均衡: 甲(0.8,0.2), 乙(0.8,0.2)*将纯策略化为混合策略-矩阵博奕-联合决策，独立决策（静态，动态） 两家企业产出为Qi（i=1，2） 价格P=a -（q1+q2） 两家企业的成本系数为C PROFIT1=q1a-（q1+q2）-q1C PROFIT2=q2a-（q1+q2）-q2C 两家企业的决策方式可以有：（一）联合决策 （二）独立决策（对策论分析）1、静态对策 2、动态对策1、 静态对策（两家同时进行）MaxPROFIT1=a-（q1+q2）-Cq1 ，q2 q2|q20 q1 MaxPROFIT2=a-（q1+q2）-C
