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