《运筹学》教案 (2014年2月) 授课班级: 2010级农林经济管理 教材:《运筹学》,熊伟,机械工业出版社 学分:4学分 学时:64学时 学时安排 学时数 内容2绪论 14 第1章 线性规划 建模,图解法,有关概念, 单纯形法,单纯形法的计算公式 12 第2章 对偶理论 对偶模型,对偶性质,影子价格及经济应用 8 第3章 整数规划 8 第4章 目标规划 整数规划模型 求解整数规划的分支定界法、割平面法、隐枚举法 8 第5章 运输与指派问题 运输与指派问题的数学模型 运输问题的表上作业法,指派问题的匈牙利法 6 第8章 动态规划 6 第12章 博弈论 第1次课 2 学时 授课章节 绪论 授课方式 理论课 课堂教学 目的及要求 1.知识目标:了解运筹学的概况、含义、特点、应用、解题步骤 2.能力目标:能够将运筹学运用于实际,根据实际问题建立模型并求解,从而解决实际问题. 课堂教学 重点及难点 重点: 运筹学的应用: 市场销售 生产计划 库存管理 运输问题 财政和会计 人事管理 设备维修 工程的优化设计 计算机和信息系统 城市管理 教学过程 教学过程 一、运筹学概况 到20 世纪60 年代, 除军事方面的应用研究以外, 相继在工业、农业、经济和社会问题等各领域都有应用.并形成了运筹学的许多分支.如数学规划(线性规划、非线性规则、整数规划、目标规划、动态规划、随机规划等)、图论与网络、排队论( 随机服务系统理论)、存储论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等. 在20 世纪50 年代中期钱学森、许国志等教授将运筹学由西方引入我国, 并结合我国的特点在国内推广应用 二、运筹学的含义 在资源不足的情况下,如何最好地分配资源,为决策者提供最佳解决方案的一门应用性学科. 三、运筹学的特点 是一门以数学为主要工具、寻求各种实际问题最优解决方案的学科;是从系统的角度,用科学方法研究寻求整体行、全局性的最优解决方案;是一门实践性和应用性强烈的学科;是一门多学科交叉的学科; 四、运筹学的应用 市场销售、生产计划、库存管理、运输问题、财政和会计、人事管理、设备维修、工程的优化设计、计算机和信息系统、城市管理. 五、运筹学的解题步骤 ①提出问题;②搜集数据、③建立模型;④求解;⑤验证;⑥实施 第2次课 2 学时 授课章节 第一章 第一节 线性规划数学模型 授课方式 理论课 课堂教学 目的及要求 掌握线性规划的基本概念、线性规划模型背景和基本建模方法. 课堂教学 重点及难点 重点:1.什么是线性规划,掌握线性规划在管理中的几个应用例子. 2. 线性规划数学模型的组成及其特征. 3. 线性规划数学模型的一般表达式. 教学过程 教学过程 1. 运筹学与线性规划基本概念( 10分钟) 2.应用模型举例 (60分钟) 生产计划问题、人员安排问题、合理用料问题、配料问题、投资问题 3.线性规划的一般模型(10分钟) 4.课堂练习(10分钟) 5.课堂小结(5分钟) 6.布置作业 第3次课 2 学时 授课章节 第一章 第二节图解法 第三节 线性规划的标准型 授课方式 理论课 课堂教学 目的及要求 1.通过图解法求解线性规划问题. 2.通过图解法了解线性规划有几种解的情况. 3.线性规划的标准型 课堂教学 重点及难点 重点: 作图的关键有三点 (1)可行解区域要画正确 (2)梯度方向(目标函数增加的方向)不能画错 (3)目标函数的等值线怎样平行移动 能够将线性规划模型转换为标准型 教学过程 教学过程 结合例题学习图解法(70分钟) 图解法步骤: (1)用决策变量建立直角坐标系; (2)对于每一个约束条件,先取等式画出直线,然后取一已知点(一般取原点)的坐标代入该直线方程的左边,由其值是否满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域. (3)令Z等于任一常数,画出目标函数的直线,平移该直线,直至它与凸多边形可行域最右边的角点相切,切点坐标则为最优解. 线性规划问题的标准型(20分钟) 课堂小结,布置作业 第4次课 2 学时 授课章节 第一章 第四节 线性规划的有关概念 授课方式 理论课 课堂教学 目的及要求 1.掌握线性规划常用的概念:可行解、基本解、基本可行解、最优解、基本最优解、基、可行基、最优基、凸集、极点(顶点)、凸组合 2. 掌握线性规划的三个基本定理. 课堂教学 重点及难点 重点:基、基变量、基解、基可行解和可行基等概念 难点:基本解、可行解、基本可行解、基本最优解、最优解的关系;和图形的对应关系 教学过程 教学过程 基、可行解、基本解、基本可行解、最优解、基本最优解、可行基、最优基、凸集、极点(顶点)、凸组合等相关概念(70分钟) 结合例题求所有的基、基本解,并指出哪些是基本可行解(20分钟) 相关概念和图解法中对应顶点之间的关系(10分钟) 课堂小结,布置作业 第5、6 次课 4 学时 授课章节 第一章 第五节 单纯形法(普通单纯形法、大M法和两阶段法) 授课方式 理论课 课堂教学 目的及要求 掌握单纯形法思想以及具体操作过程 课堂教学 重点及难点 重点: 单纯形法迭代过程:(1)换入基变量的确定; (2)换出基变量的确定;(3)判定当前解已经最优 难点:单纯形法原理 教学过程 教学过程 1.单纯形法(80分钟) 单纯形数表的构造,要注意代数形式和表格形式的一一对应性. 单纯形法迭代过程:(1)换入基变量的确定;(2)换出基变量的确定;(3)判定当前解已经最优. 2.用单纯形法求解时解的判断(20分钟) 唯一最优解的判断:最优表中所有非基变量的检验数为负, 则线性规划具有唯一最优解. 多重最优解的判断: 最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解. 无界解的判断: 某个λk>0 且aik≤0(i=1,2,…,m)则线性规划具有无界解. 退化基本可行解的判断: 存在某个基变量为零的基本可行解. 3.大M和两阶段单纯形法(40分钟) 人工变量是过度变量,当原问题有可行解时,人工变量最终会退出基变量.如果原问题没有可行解,人工变量就不会退出基变量. 4.例题(40分钟) 5.课堂小结、布置作业 第7次课 2 学时 授课章节 第一章 第五节 有关单纯形法的计算公式 授课方式 理论课 课堂教学 目的及要求 掌握5个单纯形法的基本公式. 已知基矩阵,能够利用公式计算出我们所需要的结果 课堂教学 重点及难点 重点:5个单纯形法的基本公式 难点:公式推导,改进单纯形法 教学过程 教学过程 公式推导过程 结合例题能够利用公式计算有关结果 第8次课 2 学时 授课章节 第一章 第五节 退化与循环 习题 授课方式 理论课 习题课 课堂教学 目的及要求 了解退化的原因,基本可行解中存在基变量等于零时,称为退化基本可行解 课堂教学 重点及难点 重点: 解的退化 教学过程 教学过程 1.退化与循环(40分钟) 退化解:按最小比值法确定出基变量时,有时同时出现两个以上的最小值,从而使下一个表的基可行解中出现一个或多个基变量等于零的情况,这种现象称为退化,此时的解称为退化解. 循环:当存在退化解时,就有可能出现迭代计算的循环(为零的基变量在备选出基变量中,此时迭代后入基变量也将为零,因而迭代前后的目标函数值相等).计算出现了循环,如果仍按原定规则迭代,计算永远不会结束.如P40-例14 出现退化的原因:模型中存在多余的约束,使多个基础可行解对应同一个极点 2.习题讲解(60分钟) 第9次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第一节 对偶线性规划模型 授课方式 理论课 课堂教学 目的及要求 理解线性规划的对偶问题及其经济意义,掌握原问题和对偶问题模型的对应关系,会写出原问题的对偶问题. 课堂教学 重点及难点 重点: 正确写出原问题的对偶问题 教学过程 教学过程 1.引例:(P41) 两个模型的对应关系:(20分钟) 2.线性规划的规范形式(10分钟) 3.对偶模型(5分钟) 4.对称型对偶关系的一般形式(5分钟) 5.对称型对偶关系的一般形式(三个特点)(10分钟) 非对称型对偶关系 对于非对称型且具有对偶关系的两个PL问题,总结得出: 定理: 互为对偶的两个PL问题,如果原问题中第k个约束条件是等式,则它的对偶规划中的第k个变量无非负限制,反之亦然. 线性规划的原始问题和对偶问题的对应关系可归纳为下表 对偶关系对应表 原始问题 对偶问题 目标函数类型 max min 目标函数系数与 右边常数项的对应关系 目标函数系数 右边常数项 右边常数项 目标函数系数 变量数与约束数的 对应关系 变量数 n 约束数 m 约束数 n 变量数 m 变量类型与 约束类型的对应关系 约束 ≤ = 变量 ≥0 无限制 变量 ≥0 无限制 约束 原始问题与对偶问题的转换 课堂小结,布置作业 第10 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第二节 对偶问题的性质 授课方式 理论课 课堂教学 目的及要求 了解对偶关系的基本性质,并能够利用基本性质求解相关问题 课堂教学 重点及难点 重点: 性质5和性质6可用来已知一个问题的最优解求另一个问题的最优解 教学过程 教学过程 【性质1】 ( 对称性)对偶问题的对偶是原问题.(5分钟) 【性质2】 (弱对偶性)设X°、Y°分别为LP(max)与DP(min)的可行解,则(10分钟) 由性质2可得到下面几个推论: 推论1: (LP)的任一可行解的目标值是(DP)的最优值下界; (DP)任一可行解的目标是(LP)的最优值的上界; 推论2: 在互为对偶的两个问题中,若一个问题具有无界解,则另一个问题无可行解; 推论3: 若原问题可行且另一个问题不可行,则原问题具有无界解. 【性质3】(最优性)设X0与Y0分别是(LP)与(DP)的可行解,则X0、Y0是(LP)与(DP)的最优解当且仅当C X 0 = Y 0b(10分钟) 【性质4】(对偶性)若互为对偶的两个问题其中一个有优解,则另一个也有最优解,且最优值相同.(20分钟) 由性质4还可推出另一结论: 若(LP)与(DP)都有可行解,则两者都有最优解;若一个问题无最优解,则另一问题也无最优解. 【性质5】(互补松弛定理)X 0、Y 0分别为(LP)与(DP)的可行解,XS 和YS是它的松弛变量的可行解,则X 0和Y 0是最优解当且仅当YSX 0 = 0和Y 0 XS = 0(30分钟) 性质5表明: 在线性规划的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之,如果约束条件取严格不等式,则其对应的对偶变量一定为零. 【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解.其中第 j 个决策变量 xj 的检验数的相反数对应于(DP)中第 j 个松弛变量的解,第i个松弛变量检验数的相反数对应于第 i 个对偶变量 yi 的解.反之,(DP)的检验数(注意:不乘负号)对应于(LP)的一组基本解.(20分钟) 课堂小结,布置作业 第11 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第二节 影子价格 授课方式 理论课 课堂教学 目的及要求 了解资源的影子价格在经济分析中的应用 课堂教学 重点及难点 重点: 深刻领会影子价格的含义,学会用影子价格作经济活动分析. 教学过程 教学过程 1.影子价格(Shadow price): 原始线性规划问题考虑的是充分利用现有资源,以产品的数量和单位产品的收益来决定企业的总收益,没有考虑到资源的价格,但实际在构成产品的收益中,不同的资源对收益的贡献也不同,它是企业生产过程中一种隐含的潜在价值,经济学中称为影子价格.影子价格是对偶问题最优解中决策变量 yi 的值.(10分钟) 2.影子价格的经济意义(20分钟) 在最优利用条件下,每单位资源对目标函数的贡献.是对单位资源所带来的经济效益的一种估计. 影子价格不是资源的实际价格,而是资源配置结构的反映,是根据资源在生产中作出的贡献而作出的估价,是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化. 3.影子价格与市场价格的区别(10分钟) 4.利用影子价格可作经济活动分析(20分钟) 5.例题(40分钟) 6.课堂小结,布置作业 第12 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第三节 对偶单纯形法 授课方式 理论课 课堂教学 目的及要求 掌握对偶单纯形法的应用条件和对偶单纯形法求解过程 课堂教学 重点及难点 重点: 1.对偶单纯形法的应用条件; 2.出基与进基的顺序; 3.如何求最小比值; 4.最优解、无可行解的判断. 教学过程 教学过程 一、对偶单纯形法的原理(15分钟) LP与DP在求解迭代过程中有三种情形: LP DP 结论或继续计算的步骤 可行解 可行解 表中解仍为最优解 可行解 非可行解 单纯形法 非可行解 可行解 对偶单纯形法 非可行解 非可行解 引进人工变量 二、对偶单纯形法求解过程(50分钟) 1.用实例引入: 2.总结对偶单纯形法求解过程: (1)将线性规划的约束化为等式,取对偶可行基B(全部检验数λj≤0(max)或λj≥0(min),模型为典式)建立初始单纯形表; (2)检验:当基本解可行时,即常数项列B-1b≥0, 达到最优解;若基本解不可行,即B-1b中有负数,则要进行换基迭代; (3)换基迭代:先确定出基变量. l 行对应的变量xl出基,l 行称为主行; 再选进基变量.求最小比值: θk所在列对应的变量xk出基,第k列称为主列. 若第 l 行所有元素aij ≥0, 说明线性规划无可行解;用初等变换将主元素alk化为 l,主列的其它元素化为零,得到新的单纯形表; 重复(2)、(3),直到得出最优解或判断无可行解. 三、课堂练习(30分钟) 四、课堂小结,作业布置(5分钟) 第13、14 次课 4 学时 授课章节 第二章 对偶理论与灵敏度分析 第四节 灵敏度分析 授课方式 理论课 课堂教学 目的及要求 1.知识目标:理解求解线性规划的单纯形法中灵敏度分析的基本原理;2.能力目标:分析cj,bi,aij的变化;增加一个变量Xi的分析: (1)参数在什么范围内变化时,原最优解或最优基不变; (2)当参数已经变化时,最优解或最优基有何变化. 当模型的参数发生变化后,可以不必对线性规划问题重新求解,而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解. 课堂教学 重点及难点 重点: 1. 注意最优解与最优基不变的区别; 2. 掌握某个参数变化后,最优表中哪些数据会发生变化,如何变化; 3. 模型发生变化后不是重新求解,而是在原模型的最优表中求出变化后的数据,根据变化条件,选择合适的方法继续计算. 4.了解参数分析的思路. 5. 利用WinQSB软件中的修改( Modify problem )和Perform Parametric Analysis功能,进行灵敏度分析和参数分析. 难点: 1.灵敏度的基本概念; 2.增加一个变量的分析. 教学过程 教学过程 1.举例引入灵敏度( 10分钟) 2.举例讲解新课 (120分钟) (1)灵敏度的基本概念;(30分钟) (2)分析的变化;(30分钟) (3)分析的变化;(30分钟) (4)增加一个变量的分析.(30分钟) (5)综合例题(30分钟) 3.课堂练习(穿插在例题讲解过程中) 4.课堂小结,布置作业(5分钟) 第15、16 次课 4 学时 授课章节 第三章 整数规划 第一节 整数规划的数学模型 授课方式 理论课 课堂教学 目的及要求 1.知识目标:掌握整数规划的概念、类型和作用; 2.能力目标:掌握整数规划的建模方法; 课堂教学 重点及难点 重点: 1.整数规划模型的特征 2.什么是纯(混合)整数规划 3.0-1规划模型的应用 难点: 0-1规划的数学模型 教学过程 教学过程 整数规划的概念、类型和作用(30分钟) (1)整数规划的数学模型 纯整数规划(IP):xj全部取整数 分类 混合整数规划(MIP):xj部分取整数 0-1整数规划(BIP):整数变量只能取0或1 (2)整数规划数学模型的一般形式 松弛问题 每一个整数规划都对应一个松弛问题,整数规划比它的松弛问题约束得更紧. 结合例题讲解整数规划的模型建立(120分钟) 例3-1、例3-2、例3-3、例3-4 3. 习题(30分钟) 4. 课堂小结、作业布置 第17、18 次课 4 学时 授课章节 第三章 整数规划 第一节 整数规划的求解方法 授课方式 理论课 课堂教学 目的及要求 掌握分枝定界法、割平面法、0-1规划的隐枚举法 课堂教学 重点及难点 重点: 整数规划求解方法 教学过程 教学过程 一、整数规划的求解 整数规划解的特点(20分钟): 1.整数规划(Ⅰ)的可行解集是其松弛问题(Ⅱ)的可行解集的子集.线性规划问题的可行解集是一个凸集(稠密的),但整数规划的可行解集不是凸集(离散型). 2.如果松弛问题(Ⅱ)的最优解是整数解,则一定是整数规划(Ⅰ)的优解. 3.整数规划(Ⅰ)的最优值不会优于松弛问题(Ⅱ)的最优值. (二)分支定界法(纯整数规划和混合整数规划)(50分钟) (三)割平面法(纯整数规划)(50分钟) (四)0-1规划的隐枚举法(30分钟) 课堂小结,布置作业 第19、20 次课 4 学时 授课章节 第四章 目标规划 第一节 目标规划的数学模型 授课方式 理论课 课堂教学 目的及要求 了解目标规划的定义,特点与分类;掌握目标偏差变量的概念和目标规划的模型 课堂教学 重点及难点 重点: 1.目标规划由哪些要素构成,与线性规划有哪些不同之处 2.偏差变量的含义及其作用 3.目标函数的表达方法 4.优先级别的含义 难点: 建立目标规划模型 教学过程 教学过程 1、目标规划的数学模型特征(40分钟) (1)对于决策目标来说,它允许一定的偏差,这直接表现为决策变量可以有某种偏差或;为正偏差变量,表示决策超过目标值的部分,为负偏差变量,表示决策未达到目标值的部分.考虑到决策值不可能超过同时又未达到目标值,所以, (2)绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束,如线性规划中的约束,不能满足这些条件的即为非可行解.目标约束则可将右端项视为要达到的目标,但允许发生证或负的偏差,因此在这些约束中加入正、负偏差变量. 在线性规划的硬约束中加入正负偏差变量(加上负偏差变量、减去正偏差变量),将符号变为等号就转变为目标约束. (3)优先因子(优先等级)与权系数 在现实的决策背景下,决策者往往具有多个目标,但这些目标是有主次轻重的不同.赋予优先因子,规定,表示级目标比级具有绝对的优先权,在优先保证级目标时可不考虑级目标.权系数可区别同级目标中两个目标的差异. (4)目标规划的目标函数 目标规划的目标函数由各目标约束的正负偏差变量和赋予相应的优先因子构造而成.当每一目标给定后,决策者的要求是尽可能地缩小偏离目标值.因此,目标规划的目标函数只能是,其基本形式有三种: 要求恰好达到目标值,即正负偏差都要求尽可能地小,此时 ②要求不超过目标值,即允许达不到目标值,就是正偏差要尽可能地小,即 ③要求超过目标值,即超过量不限,就是负偏差要尽可能地小,此时 2.目标规划模型的建立、例题及习题讲解(60分钟) 3、目标函数:只有min一种,不含决策变量 不同目标的重要程度有两种差别: 绝对差别: 用优先因子Pj表示,P1》P2》…》Pk, 即Pl对应的目标绝对优先于Pl+1对应的目标. 相对差别: 具有同一级别优先因子的多个目标,可根据目标的相对重要程度,分别赋予它们不同的权值,以区别不同的偏差变量在同一优先级内的相对重要程度. 目标规划的解:往往不能满足所有的目标约束,但一定满足系统约束,故称为满意解. 目标规划没有系统约束时,一定存在满意解. 目标规划模型与线性规划模型的区别 第21、22 次课 4 学时 授课章节 第四章 目标规划 第二节 目标规划的图解法及单纯形法 授课方式 理论课 课堂教学 目的及要求 掌握目标规划的规划求解法.重点要求是图解法. 能够运用WinQSB软件求解目标规划 课堂教学 重点及难点 重点: 目标规划图解法 教学过程 教学过程 第21次课: 1.目标规划的图解法的思路(20分钟) 首先是在可行域 R 内寻找一个使P1级各目标均满足的区域R1; 然后再在R1 中寻找一个使P2 级各目标均满足的区域R2 ; 接着再在R2 中寻找一个满足P3 级各目标的区域R3 ; 如此继续直到寻找到一个区域Rk 满足Pk 级各目标,而不保证满足其后的各级目标,这时Rk即为这个目标规划的最优解空间,其中的任一点均为这个目标规划的满意解. 2.例题4-4,4-5(70分钟) 3.总结目标规划图解法步骤(10分钟) (1)按照绝对约束画出可行域(满足系统约束和决策变量非负的解的集合); (2)不考虑正负偏差变量,画出目标约束的边界线,并标出偏差变量变化时的直线平移方向; (3)按优先级别和权重依次分析各级目标. 第22次课: 1.目标规划单纯形法(30分钟) 单纯形法求解目标规划可参照第1章的步骤,只是目标规划的检验要按优先级顺序逐级进行,不同的是: (1)首先使得检验数中P1的系数非负,再使得P2的系数非负,依次进行; (2)(最优解判别准则)当P1、P2、…、Pk对应的系数全部非负时得到满意解; (3)如果P1,…,Pi行系数非负,而Pi+1行存在负数,并且负数所在列上面P1,…,Pi行中存在正数时,得到满意解,计算结束. 2.习题(70分钟) 第23 次课 2 学时 授课章节 第五章 运输与指派问题 第一节 运输问题的数学模型及特征 授课方式 理论课 课堂教学 目的及要求 正确理解运输问题的数学模型、解的性质和基的特征; 课堂教学 重点及难点 重点: 具有m个产地n个销地的平衡运输问题 1.具有m+n-1个基变量 2.闭回路的概念 3.怎样判断m+n-1个变量是否构成一组基变量 难点: 不平衡的运输问题 教学过程 教学过程 一、运输问题的一般数学模型(40分钟) 三种情况(从总产量与总销量是否平衡考虑) 1、供求平衡时 具备运输问题模型特征的还有布局问题等,统称为"康希问题" 特点:(1)有m*n个变量,m+n个约束条件,可证其中任何m+n-1个都是相互独立的,即A中任何m+n-1个行向量线性无关,故基本可行解中基变量的个数为m+n-1 (2)运输问题一定有最优解 由于运输问题模型的特殊性,用单纯形法求解很不方便,可采用特殊的方法求解,常用的有:表上作业法,图上作业法. 2、供过于求时 3、供不应求时 后两类不平衡的运输问题,可通过设置虚拟"销地"或"产地",化为平衡运输问题求解. 二、结合例题讲解运输问题模型(20分钟) 三、定理5.1:设m有个产地n个销地且产销平衡的运输问题,则基变量数为m+n-1.(15分钟) 定理5.3:m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路.(15分钟) 课堂小结,布置作业 第24、25 次课 4 学时 授课章节 第五章 运输与指派问题 第二节 运输单纯形法(表上作业法)第三节运输模型的应用 授课方式 理论课 课堂教学 目的及要求 掌握平衡运输问题的求解方法:表上作业法 1.求初始运输方案,用最小元素法、元素差额法(Vogel近似法) 2.求检验数,用闭回路法和位势法 3.调整运量,用闭回路法 4.极大值问题的求解方法、不平衡问题、需求量不确定问题 5.掌握运输问题模型的应用 课堂教学 重点及难点 重点: 表上作业法的求解步骤 难点: 极大值问题的求解方法、不平衡问题、需求量不确定问题 教学过程 教学过程 第24次课(100分钟) 1.求初始运输方案,用最小元素法、元素差额法(Vogel近似法) 2.求检验数,用闭回路法和位势法 3.调整运量,用闭回路法 第25次课(100分钟) 4.极大值问题的求解方法 5.不平衡问题 6.需求量不确定问题 7.例5-14运输问题模型的应用:多时期的综合生产计划问题 8.课堂小结,布置作业 结合例题讲解: 1.确定初始方案(最小元素法) 按通常习惯,运费最小的优先供应,在运价表中不断的选择最小元素格,给予优先安排,得表4.8 B1 B2 B3 B4 产量 A1 4 1 8 8 5 4 6 A2 9 5 2 6 2 3 4 A3 3 5 11 4 2 7 12 销量 6 2 7 7 22 (基变量个数m+n-1) 初始方案对应运输问题的一个基本可行解 x11=1,x13=5,x22=2,x23=2,x31=5,x34=7,其余xij=0 相应的总运费=95(万元) 2.最优解检验 求检验数(位势法): (1)列位势方程组,并求解:(数子格)cij=ui+vj (2)求空格检验数:初始方案中,调运量不为零的格子的检验数为零,故只需求空格的检验数. λij=cij-(ui+vj) λ12=1,λ14=1,λ21=7,λ24=2,λ32=5,λ33=-3 判别准则:若检验数中没有负数,则该方案为最优方案,否则,要进行调整. 在实际中,只要从上到下,从左到右,依次求每个空格的检验数,当一出现负检验数,就表明方案非最优,需要调整,其它空格的检验数就不必再求了. B1 B2 B3 B4 行A1 4 + 1 8 8 - 5 4 u1=0 A2 9 5 2 6 2 3 u2=-2 A3 3 - 5 11 4 + 2 7 u3=-1 列v1=4 v2=7 v3=8 v4=3 3. 方案的调整(闭回路法) 思路:根据单纯形法的思想,由一个基础可行解求得另一个基础可行解,要进行换基迭代,其关键是求主元素.对于运输问题,这一过程可在表上进行.其方法是:选取最小负检验数作为主元素,作该空格的闭回路,对闭回路拐角点上的货运量作相应的调整,目的是把该非基变量变为基变量,即使这个非基变量的值由零增大到一适当的数值,并保持横向、纵向的平衡,因此,要使拐角点上一基变量的值为零(即成为非基变量),同时还必须使改变后的各基变量保持非负,故非基变量增大的值(调整量)应为闭回路中第奇数次拐角点中最小的货运量. (1)确定进基变量:选取最小负检验数对应的变量为进基变量.该例λ33=-3最小,故x33 为进基变量. (2)确定出基变量:作x33对应格的闭回路.并依次对拐角点赋予"+","-"相间的符号. 可以证明:过每一个空格可以作并且只可以作一条闭回路 取调整量 θ=min{"-"拐角点的运量},θ=min{5,5}=5 出基变量为x13或x31 (3)调整规则:"+"格(调运量)+θ,"-"格(调运量)-θ 调整后的新方案如表所示 B1 B2 B3 B4 产量 A1 4 6 8 8 4 6 A2 9 5 2 6 2 3 4 A3 3 0 11 4 5 2 7 12 销量 6 2 7 7 22 新方案对应的运费=80(万元) 下降了 95-80=15=θ*|λ33|=5*3; 再检验、调整 B1 B2 B3 B4 行A1 4 6 8 8 4 u1=0 A2 9 5 2 6 - 2 3 + u2= 1 A3 3 0 11 4 + 5 2 - 7 u3=--1 列v1=4 v2=4 v3=5 v4= 3 λ12=4, λ13=3, λ14=1, λ21=4, λ24= -1, λ32=8 θ=min{2,7}=2 x24进基,x23出基 调整后,得最优方案(描述) B1 B2 B3 B4 产量 A1 4 6 8 8 4 6 A2 9 5 2 6 3 2 4 A3 3 0 11 4 7 2 5 12 销量 6 2 7 7 22 最小运费z=78(万元) 检验: B1 B2 B3 B4 行A1 4 6 8 8 4 U1=0 A2 9 5 2 6 3 2 U2=0 A3 3 0 11 4 7 2 5 U3=-1 列V1=4 V2=5 V3=5 V4=3 λ12=3,λ13=3,λ14=1,λ21=5,λ23=1,λ32=7 第26 次课 2 学时 授课章节 第四章 运输与指派问题 第四节指派问题 授课方式 理论课 课堂教学 目的及要求 将生产计划问题转化为运输问题求解 掌握指派问题的数学模型,求解指派问题的匈牙利算法及其他变异问题 课堂教学 重点及难点 重点: 指派问题的匈牙利算法 难点: 变异问题如何转换为平衡运输问题并求解 教学过程 教学过程 指派问题数学模型(20分钟) 假设m个人恰好做m项工作,第i个人做第j项工作的效率为cij≥0,效率矩阵为[cij] , 如何分配工作使效率最佳(min或max)的数学模型为 2.匈牙利算法(50分钟) 【定理5.4】如果从分配问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势),从每一列分别减去(或加上)一个常数vj(称为该列的位势),得到一个新的效率矩阵[bij],其中bij=cij-ui-vj,则[bij]的最优解等价于[cij]的最优解,这里cij、bij均非负. 【定理5.5】若矩阵A的元素可分成"0"与非"0"两部分,则覆盖"0"元素的最少直线数等于位于不同行不同列的"0"元素(称为独立元素)的最大个数. 如果覆盖"0"元素的最少直线数等于m,则存在m个独立的"0"元素,令这些零元素对应的xij等于1,其余变量等于0,这时目标函数值等于零,得到最优解. 匈牙利法的条件: (1)问题是求最小值 (2)人数与工作数相等,即m=n (3)效率非负,即cij≥0. 3.其它变异问题(30分钟) 最大化指派问题应转化为最小化问题求解.效益矩阵C=(cij),其中最大元素为m.令矩阵 B=(bij)= (m-cij),则以B为效益矩阵的最小化指派问题和以C为效益矩阵的原最大化指派问题有相同最优解. 人数和事数不等的指派问题,可添加虚拟的人或事,其系数取0,化为平衡指派问题. 一个人可做几件事的指派问题,可将一个人视为相同的几个人,化为平衡指派问题. 某事一定不能由某人做的指派问题,可将某人做某事所用的时间设为充分大的正数M . 4.课堂小结,布置作业 第27、28 次课 4 学时 授课章节 第八章 动态规划 第一节 动态规划的数学模型 第二节 资源分配问题 授课方式 理论课 课堂教学 目的及要求 一、掌握动态规划的概念、原理、分类、基本概念,能够建立动态规划模型并求解; 动态规划模型的建立一般包含以下内容: 明确阶段划分 明确状态变量sk的含义及取值范围 明确决策变量xk的含义及取值范围 正确写出状态转移方程sk+1=Tk(sk,xk) 明确阶段指标函数rk(sk,xk)和最优指标函数fk(sk) 正确写出基本方程 二、了解资源分配问题模型的建立及求解 课堂教学 重点及难点 重点: 动态规划的基本概念、建立动态规划模型 难点: 1.能够正确写出状态转移方程sk+1=Tk(sk,xk) 2.明确阶段指标函数rk(sk,xk)和最优指标函数fk(sk) 3.正确写出基本方程 教学过程 第27次课(100分钟) 动态规划的原理及能够解决的几类问题(10分钟) 引例:最短路径问题(20分钟) 动态规划的基本概念(70分钟) (1)阶段和阶段变量 将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序去求每阶段的解.阶段变量用k表示. (2)状态和状态变量 状态:各阶段开始时的自然位置或客观条件叫做状态. 状态的选取要具有无后效性.即某阶段的状态给定后,则过程未来发展不受该阶段以前各阶段状态的影响. 状态(state)变量sk:描述各阶段状态的变量称为状态变量. 状态集合Sk:sk的取值范围称为状态集合,sk∈Sk (3)决策与策略 决策(decision):当状态给定后,为过渡到下一阶段所作出的决定. 决策变量xk:描述决策的变量.第k阶段的决策变量只与当前状态sk有关,既xk=xk(sk). 决策集合Xk(sk):决策变量的允许值范围称为决策集合,用Xk(sk)(或Dk(sk))表示第k阶段状态sk的决策集合. 策略(policy):各阶段决策确定后,整个问题的决策序列就构成一个策略,记作p1,N(x1,x2,…,xn) (4)状态转移方程:由一个阶段的状态到下一阶段的状态的变化叫做状态转移.第k阶段的状态为sk, 采用决策xk,则第k+1阶段的状态sk+1就完全确定,它们的关系表示为sk+1=Tk(sk,xk)称为状态转移方程 (5)指标函数 阶段指标函数rk(sk,xk):第k阶段的状态为sk,执行决策xk时产生的效果值,叫做阶段效益.它表示在第k阶段,状态为sk采用决策xk时的收益. 子过程指标函数Vk,n(sk,pk,n):表示在第k阶段,状态为sk采用策略pk,n时,后部子过程的效益值. 策略不同,指标函数值也不同 从k阶段状态sk出发,对所有的子策略,最优的过程指标函数称为最优指标函数,记为fk(sk),通常取Vk的最大值或最小值. 最优指标函数:是指从第k阶段状态sk采用最优子策略p*k,n到过程终止时的最佳效益值.记做fk(sk) 初始状态s1的最优指标函数 是原过程的最佳效益值,所对应的策略(x*1,x*2,…,x*n)就是最优策略.最优指标函数: 称为贝尔曼函数 第28次课(100分钟) 1.动态规划模型由递归方程、边界条件及状态转移方程构成(10) 2.用动态规划递推方法求解例8-1(40分钟) 3.资源分配问题例8-2(50分钟) 第29 次课 2 学时 授课章节 第八章 动态规划 第三节 生产与存储问题 第四节 背包问题 授课方式 理论课 课堂教学 目的及要求 掌握生产与存储问题以及背包问题的动态规划模型,能够用WinQSB软件求解这两类问题 课堂教学 重点及难点 重点及难点: 生产与存储问题以及背包问题的动态规划模型 教学过程 教学过程 1.生产与存储问题动态规划模型(例8-4)(50分钟) 阶段k:月份,k=1,2,…,6 状态变量sk:第k月初的库存量,0≤sk≤50 决策变量xk:第k月的生产量 状态转移方程:sk+1=sk+xk-dk 决策允许集合: 阶段指标 终端条件f7(s7)=0 递推方程: 背包问题(30分钟) 一维背包问题数学模型为 ck为第k种物品的单位价值,wk是第k种物品的单位重量或体积,W是背包的重量或体积限制.动态规划的有关要素如下: 阶段k:第k次装载第k种物品(k=1,2,…,n) 状态变量sk:第k次装载时背包还可以装载的重量(或体积) 决策变量xk:装载第k种物品的件数 决策允许集合:Dk(sk)={dk|0( xk(sk/wk,xk为整数} 状态转移方程:sk+1=sk-wkxk 阶段指标:vk=ckxk 递推方程: 终端条件; fn+1(sn+1)=0 3.用WinQSB求以上两类问题(20分钟) 4.课堂小结,布置作业 第30 次课 2 学时 授课章节 第十二章 博弈论 第一节 引言 授课方式 理论课 课堂教学 目的及要求 了解博弈论的发展、应用领域,几个经典的博弈模型,掌握博弈三要素、博弈的结构和分类 课堂教学 重点及难点 重点: 博弈的基本要素和分类 教学过程 教学过程 引言(20分钟) 几个经典博弈模型(齐王田忌赛马、囚徒困境) 总结博弈特征(5分钟) 有一定的规则 有一个确定的结果:赢、输或平局 参与者的策略或计谋,在其中有举足轻重的的作用 策略和利益有相互依存性 3. 博弈论历史和发展(30分钟) 4. 博弈的基本要素(10分钟) 5. 博弈的分类(10分钟) 6. 博弈论在我国经济中的应用(20分钟) 7. 课堂小结,布置作业 第31、32 次课 4 学时 授课章节 第十二章 博弈论 第二节 纳什均衡 第三节 矩阵博弈 授课方式 理论课 课堂教学 目的及要求 掌握博弈行为、纳什均衡、纯策略、混合策略等概念;会用"囚徒困境"分析社会经济生活中的竞争现象;理解博弈模型的基本要素:局中人、策略集、赢得函数;熟练掌握矩阵博弈的求解 课堂教学 重点及难点 重点:1、博弈的有关概念及相关理论 2、矩阵博弈的解法 难点:纳什均衡的概念 教学过程 教学过程 第31次课(100分钟) 纳什均衡的定义 纳什均衡(Nash Equilibrium): 假定有n个博弈方参加博弈,在给定其他博弈方策略的条件下,每个人选择自己的最优策略(个人最优策略可能依赖也可能不依赖他人策略),从而使自己利益最大化,所有局中人的策略一起构成一个策略组合.而Nash均衡是这样一种策略组合,由所有参与人的最优策略组成,给定别人策略的条件下,没有任何单个参与人有积极性选择其他策略,从而没有任何人有积极性打破这种均衡,Nash均衡是一种" 僵局":给定别人不动的情况下,没有人有兴趣动. 矩阵博弈的概念及模型 定义:两人有限零和博弈 模型:G={S1,S2;A} S1={α1,α2,…,αm}——局中人Ⅰ的纯策略集 S2={β1,β2,…,βn}——局中人Ⅱ的纯策略集 ——局中人Ⅰ的赢得矩阵 αi j——局中人Ⅰ在局势(αi,βj)下的赢得值 3.求解矩阵博弈 (1)纯策略解(鞍点解):最小最大原则 (2)混合策略解:代数法、方程组法、线性规划法、优超原则
下载该文档
文档格式：DOC
更新时间：2014-08-28
下载次数：0
点击次数：1
《运筹学》教案 (2014年2月) 授课班级: 2010级农林经济管理 教材:《运筹学》,熊伟,机械工业出版社 学分:4学分 学时:64学时 学时安排 学时数 内容2绪论 14 第1章 线性规划 建模,图解法,有关概念, 单纯形法,单纯形法的计算公式 12 第2章 对偶理论 对偶模型,对偶性质,影子价格及经济应用 8 第3章 整数规划 8 第4章 目标规划 整数规划模型 求解整数规划的分支定界法、割平面法、隐枚举法 8 第5章 运输与指派问题 运输与指派问题的数学模型 运输问题的表上作业法,指派问题的匈牙利法 6 第8章 动态规划 6 第12章 博弈论 第1次课 2 学时 授课章节 绪论 授课方式 理论课 课堂教学 目的及要求 1.知识目标:了解运筹学的概况、含义、特点、应用、解题步骤 2.能力目标:能够将运筹学运用于实际,根据实际问题建立模型并求解,从而解决实际问题. 课堂教学 重点及难点 重点: 运筹学的应用: 市场销售 生产计划 库存管理 运输问题 财政和会计 人事管理 设备维修 工程的优化设计 计算机和信息系统 城市管理 教学过程 教学过程 一、运筹学概况 到20 世纪60 年代, 除军事方面的应用研究以外, 相继在工业、农业、经济和社会问题等各领域都有应用.并形成了运筹学的许多分支.如数学规划(线性规划、非线性规则、整数规划、目标规划、动态规划、随机规划等)、图论与网络、排队论( 随机服务系统理论)、存储论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等. 在20 世纪50 年代中期钱学森、许国志等教授将运筹学由西方引入我国, 并结合我国的特点在国内推广应用 二、运筹学的含义 在资源不足的情况下,如何最好地分配资源,为决策者提供最佳解决方案的一门应用性学科. 三、运筹学的特点 是一门以数学为主要工具、寻求各种实际问题最优解决方案的学科;是从系统的角度,用科学方法研究寻求整体行、全局性的最优解决方案;是一门实践性和应用性强烈的学科;是一门多学科交叉的学科; 四、运筹学的应用 市场销售、生产计划、库存管理、运输问题、财政和会计、人事管理、设备维修、工程的优化设计、计算机和信息系统、城市管理. 五、运筹学的解题步骤 ①提出问题;②搜集数据、③建立模型;④求解;⑤验证;⑥实施 第2次课 2 学时 授课章节 第一章 第一节 线性规划数学模型 授课方式 理论课 课堂教学 目的及要求 掌握线性规划的基本概念、线性规划模型背景和基本建模方法. 课堂教学 重点及难点 重点:1.什么是线性规划,掌握线性规划在管理中的几个应用例子. 2. 线性规划数学模型的组成及其特征. 3. 线性规划数学模型的一般表达式. 教学过程 教学过程 1. 运筹学与线性规划基本概念( 10分钟) 2.应用模型举例 (60分钟) 生产计划问题、人员安排问题、合理用料问题、配料问题、投资问题 3.线性规划的一般模型(10分钟) 4.课堂练习(10分钟) 5.课堂小结(5分钟) 6.布置作业 第3次课 2 学时 授课章节 第一章 第二节图解法 第三节 线性规划的标准型 授课方式 理论课 课堂教学 目的及要求 1.通过图解法求解线性规划问题. 2.通过图解法了解线性规划有几种解的情况. 3.线性规划的标准型 课堂教学 重点及难点 重点: 作图的关键有三点 (1)可行解区域要画正确 (2)梯度方向(目标函数增加的方向)不能画错 (3)目标函数的等值线怎样平行移动 能够将线性规划模型转换为标准型 教学过程 教学过程 结合例题学习图解法(70分钟) 图解法步骤: (1)用决策变量建立直角坐标系; (2)对于每一个约束条件,先取等式画出直线,然后取一已知点(一般取原点)的坐标代入该直线方程的左边,由其值是否满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域. (3)令Z等于任一常数,画出目标函数的直线,平移该直线,直至它与凸多边形可行域最右边的角点相切,切点坐标则为最优解. 线性规划问题的标准型(20分钟) 课堂小结,布置作业 第4次课 2 学时 授课章节 第一章 第四节 线性规划的有关概念 授课方式 理论课 课堂教学 目的及要求 1.掌握线性规划常用的概念:可行解、基本解、基本可行解、最优解、基本最优解、基、可行基、最优基、凸集、极点(顶点)、凸组合 2. 掌握线性规划的三个基本定理. 课堂教学 重点及难点 重点:基、基变量、基解、基可行解和可行基等概念 难点:基本解、可行解、基本可行解、基本最优解、最优解的关系;和图形的对应关系 教学过程 教学过程 基、可行解、基本解、基本可行解、最优解、基本最优解、可行基、最优基、凸集、极点(顶点)、凸组合等相关概念(70分钟) 结合例题求所有的基、基本解,并指出哪些是基本可行解(20分钟) 相关概念和图解法中对应顶点之间的关系(10分钟) 课堂小结,布置作业 第5、6 次课 4 学时 授课章节 第一章 第五节 单纯形法(普通单纯形法、大M法和两阶段法) 授课方式 理论课 课堂教学 目的及要求 掌握单纯形法思想以及具体操作过程 课堂教学 重点及难点 重点: 单纯形法迭代过程:(1)换入基变量的确定; (2)换出基变量的确定;(3)判定当前解已经最优 难点:单纯形法原理 教学过程 教学过程 1.单纯形法(80分钟) 单纯形数表的构造,要注意代数形式和表格形式的一一对应性. 单纯形法迭代过程:(1)换入基变量的确定;(2)换出基变量的确定;(3)判定当前解已经最优. 2.用单纯形法求解时解的判断(20分钟) 唯一最优解的判断:最优表中所有非基变量的检验数为负, 则线性规划具有唯一最优解. 多重最优解的判断: 最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解. 无界解的判断: 某个λk>0 且aik≤0(i=1,2,…,m)则线性规划具有无界解. 退化基本可行解的判断: 存在某个基变量为零的基本可行解. 3.大M和两阶段单纯形法(40分钟) 人工变量是过度变量,当原问题有可行解时,人工变量最终会退出基变量.如果原问题没有可行解,人工变量就不会退出基变量. 4.例题(40分钟) 5.课堂小结、布置作业 第7次课 2 学时 授课章节 第一章 第五节 有关单纯形法的计算公式 授课方式 理论课 课堂教学 目的及要求 掌握5个单纯形法的基本公式. 已知基矩阵,能够利用公式计算出我们所需要的结果 课堂教学 重点及难点 重点:5个单纯形法的基本公式 难点:公式推导,改进单纯形法 教学过程 教学过程 公式推导过程 结合例题能够利用公式计算有关结果 第8次课 2 学时 授课章节 第一章 第五节 退化与循环 习题 授课方式 理论课 习题课 课堂教学 目的及要求 了解退化的原因,基本可行解中存在基变量等于零时,称为退化基本可行解 课堂教学 重点及难点 重点: 解的退化 教学过程 教学过程 1.退化与循环(40分钟) 退化解:按最小比值法确定出基变量时,有时同时出现两个以上的最小值,从而使下一个表的基可行解中出现一个或多个基变量等于零的情况,这种现象称为退化,此时的解称为退化解. 循环:当存在退化解时,就有可能出现迭代计算的循环(为零的基变量在备选出基变量中,此时迭代后入基变量也将为零,因而迭代前后的目标函数值相等).计算出现了循环,如果仍按原定规则迭代,计算永远不会结束.如P40-例14 出现退化的原因:模型中存在多余的约束,使多个基础可行解对应同一个极点 2.习题讲解(60分钟) 第9次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第一节 对偶线性规划模型 授课方式 理论课 课堂教学 目的及要求 理解线性规划的对偶问题及其经济意义,掌握原问题和对偶问题模型的对应关系,会写出原问题的对偶问题. 课堂教学 重点及难点 重点: 正确写出原问题的对偶问题 教学过程 教学过程 1.引例:(P41) 两个模型的对应关系:(20分钟) 2.线性规划的规范形式(10分钟) 3.对偶模型(5分钟) 4.对称型对偶关系的一般形式(5分钟) 5.对称型对偶关系的一般形式(三个特点)(10分钟) 非对称型对偶关系 对于非对称型且具有对偶关系的两个PL问题,总结得出: 定理: 互为对偶的两个PL问题,如果原问题中第k个约束条件是等式,则它的对偶规划中的第k个变量无非负限制,反之亦然. 线性规划的原始问题和对偶问题的对应关系可归纳为下表 对偶关系对应表 原始问题 对偶问题 目标函数类型 max min 目标函数系数与 右边常数项的对应关系 目标函数系数 右边常数项 右边常数项 目标函数系数 变量数与约束数的 对应关系 变量数 n 约束数 m 约束数 n 变量数 m 变量类型与 约束类型的对应关系 约束 ≤ = 变量 ≥0 无限制 变量 ≥0 无限制 约束 原始问题与对偶问题的转换 课堂小结,布置作业 第10 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第二节 对偶问题的性质 授课方式 理论课 课堂教学 目的及要求 了解对偶关系的基本性质,并能够利用基本性质求解相关问题 课堂教学 重点及难点 重点: 性质5和性质6可用来已知一个问题的最优解求另一个问题的最优解 教学过程 教学过程 【性质1】 ( 对称性)对偶问题的对偶是原问题.(5分钟) 【性质2】 (弱对偶性)设X°、Y°分别为LP(max)与DP(min)的可行解,则(10分钟) 由性质2可得到下面几个推论: 推论1: (LP)的任一可行解的目标值是(DP)的最优值下界; (DP)任一可行解的目标是(LP)的最优值的上界; 推论2: 在互为对偶的两个问题中,若一个问题具有无界解,则另一个问题无可行解; 推论3: 若原问题可行且另一个问题不可行,则原问题具有无界解. 【性质3】(最优性)设X0与Y0分别是(LP)与(DP)的可行解,则X0、Y0是(LP)与(DP)的最优解当且仅当C X 0 = Y 0b(10分钟) 【性质4】(对偶性)若互为对偶的两个问题其中一个有优解,则另一个也有最优解,且最优值相同.(20分钟) 由性质4还可推出另一结论: 若(LP)与(DP)都有可行解,则两者都有最优解;若一个问题无最优解,则另一问题也无最优解. 【性质5】(互补松弛定理)X 0、Y 0分别为(LP)与(DP)的可行解,XS 和YS是它的松弛变量的可行解,则X 0和Y 0是最优解当且仅当YSX 0 = 0和Y 0 XS = 0(30分钟) 性质5表明: 在线性规划的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之,如果约束条件取严格不等式,则其对应的对偶变量一定为零. 【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解.其中第 j 个决策变量 xj 的检验数的相反数对应于(DP)中第 j 个松弛变量的解,第i个松弛变量检验数的相反数对应于第 i 个对偶变量 yi 的解.反之,(DP)的检验数(注意:不乘负号)对应于(LP)的一组基本解.(20分钟) 课堂小结,布置作业 第11 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第二节 影子价格 授课方式 理论课 课堂教学 目的及要求 了解资源的影子价格在经济分析中的应用 课堂教学 重点及难点 重点: 深刻领会影子价格的含义,学会用影子价格作经济活动分析. 教学过程 教学过程 1.影子价格(Shadow price): 原始线性规划问题考虑的是充分利用现有资源,以产品的数量和单位产品的收益来决定企业的总收益,没有考虑到资源的价格,但实际在构成产品的收益中,不同的资源对收益的贡献也不同,它是企业生产过程中一种隐含的潜在价值,经济学中称为影子价格.影子价格是对偶问题最优解中决策变量 yi 的值.(10分钟) 2.影子价格的经济意义(20分钟) 在最优利用条件下,每单位资源对目标函数的贡献.是对单位资源所带来的经济效益的一种估计. 影子价格不是资源的实际价格,而是资源配置结构的反映,是根据资源在生产中作出的贡献而作出的估价,是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化. 3.影子价格与市场价格的区别(10分钟) 4.利用影子价格可作经济活动分析(20分钟) 5.例题(40分钟) 6.课堂小结,布置作业 第12 次课 2 学时 授课章节 第二章 对偶理论与灵敏度分析 第三节 对偶单纯形法 授课方式 理论课 课堂教学 目的及要求 掌握对偶单纯形法的应用条件和对偶单纯形法求解过程 课堂教学 重点及难点 重点: 1.对偶单纯形法的应用条件; 2.出基与进基的顺序; 3.如何求最小比值; 4.最优解、无可行解的判断. 教学过程 教学过程 一、对偶单纯形法的原理(15分钟) LP与DP在求解迭代过程中有三种情形: LP DP 结论或继续计算的步骤 可行解 可行解 表中解仍为最优解 可行解 非可行解 单纯形法 非可行解 可行解 对偶单纯形法 非可行解 非可行解 引进人工变量 二、对偶单纯形法求解过程(50分钟) 1.用实例引入: 2.总结对偶单纯形法求解过程: (1)将线性规划的约束化为等式,取对偶可行基B(全部检验数λj≤0(max)或λj≥0(min),模型为典式)建立初始单纯形表; (2)检验:当基本解可行时,即常数项列B-1b≥0, 达到最优解;若基本解不可行,即B-1b中有负数,则要进行换基迭代; (3)换基迭代:先确定出基变量. l 行对应的变量xl出基,l 行称为主行; 再选进基变量.求最小比值: θk所在列对应的变量xk出基,第k列称为主列. 若第 l 行所有元素aij ≥0, 说明线性规划无可行解;用初等变换将主元素alk化为 l,主列的其它元素化为零,得到新的单纯形表; 重复(2)、(3),直到得出最优解或判断无可行解. 三、课堂练习(30分钟) 四、课堂小结,作业布置(5分钟) 第13、14 次课 4 学时 授课章节 第二章 对偶理论与灵敏度分析 第四节 灵敏度分析 授课方式 理论课 课堂教学 目的及要求 1.知识目标:理解求解线性规划的单纯形法中灵敏度分析的基本原理;2.能力目标:分析cj,bi,aij的变化;增加一个变量Xi的分析: (1)参数在什么范围内变化时,原最优解或最优基不变; (2)当参数已经变化时,最优解或最优基有何变化. 当模型的参数发生变化后,可以不必对线性规划问题重新求解,而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解. 课堂教学 重点及难点 重点: 1. 注意最优解与最优基不变的区别; 2. 掌握某个参数变化后,最优表中哪些数据会发生变化,如何变化; 3. 模型发生变化后不是重新求解,而是在原模型的最优表中求出变化后的数据,根据变化条件,选择合适的方法继续计算. 4.了解参数分析的思路. 5. 利用WinQSB软件中的修改( Modify problem )和Perform Parametric Analysis功能,进行灵敏度分析和参数分析. 难点: 1.灵敏度的基本概念; 2.增加一个变量的分析. 教学过程 教学过程 1.举例引入灵敏度( 10分钟) 2.举例讲解新课 (120分钟) (1)灵敏度的基本概念;(30分钟) (2)分析的变化;(30分钟) (3)分析的变化;(30分钟) (4)增加一个变量的分析.(30分钟) (5)综合例题(30分钟) 3.课堂练习(穿插在例题讲解过程中) 4.课堂小结,布置作业(5分钟) 第15、16 次课 4 学时 授课章节 第三章 整数规划 第一节 整数规划的数学模型 授课方式 理论课 课堂教学 目的及要求 1.知识目标:掌握整数规划的概念、类型和作用; 2.能力目标:掌握整数规划的建模方法; 课堂教学 重点及难点 重点: 1.整数规划模型的特征 2.什么是纯(混合)整数规划 3.0-1规划模型的应用 难点: 0-1规划的数学模型 教学过程 教学过程 整数规划的概念、类型和作用(30分钟) (1)整数规划的数学模型 纯整数规划(IP):xj全部取整数 分类 混合整数规划(MIP):xj部分取整数 0-1整数规划(BIP):整数变量只能取0或1 (2)整数规划数学模型的一般形式 松弛问题 每一个整数规划都对应一个松弛问题,整数规划比它的松弛问题约束得更紧. 结合例题讲解整数规划的模型建立(120分钟) 例3-1、例3-2、例3-3、例3-4 3. 习题(30分钟) 4. 课堂小结、作业布置 第17、18 次课 4 学时 授课章节 第三章 整数规划 第一节 整数规划的求解方法 授课方式 理论课 课堂教学 目的及要求 掌握分枝定界法、割平面法、0-1规划的隐枚举法 课堂教学 重点及难点 重点: 整数规划求解方法 教学过程 教学过程 一、整数规划的求解 整数规划解的特点(20分钟): 1.整数规划(Ⅰ)的可行解集是其松弛问题(Ⅱ)的可行解集的子集.线性规划问题的可行解集是一个凸集(稠密的),但整数规划的可行解集不是凸集(离散型). 2.如果松弛问题(Ⅱ)的最优解是整数解,则一定是整数规划(Ⅰ)的优解. 3.整数规划(Ⅰ)的最优值不会优于松弛问题(Ⅱ)的最优值. (二)分支定界法(纯整数规划和混合整数规划)(50分钟) (三)割平面法(纯整数规划)(50分钟) (四)0-1规划的隐枚举法(30分钟) 课堂小结,布置作业 第19、20 次课 4 学时 授课章节 第四章 目标规划 第一节 目标规划的数学模型 授课方式 理论课 课堂教学 目的及要求 了解目标规划的定义,特点与分类;掌握目标偏差变量的概念和目标规划的模型 课堂教学 重点及难点 重点: 1.目标规划由哪些要素构成,与线性规划有哪些不同之处 2.偏差变量的含义及其作用 3.目标函数的表达方法 4.优先级别的含义 难点: 建立目标规划模型 教学过程 教学过程 1、目标规划的数学模型特征(40分钟) (1)对于决策目标来说,它允许一定的偏差,这直接表现为决策变量可以有某种偏差或;为正偏差变量,表示决策超过目标值的部分,为负偏差变量,表示决策未达到目标值的部分.考虑到决策值不可能超过同时又未达到目标值,所以, (2)绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束,如线性规划中的约束,不能满足这些条件的即为非可行解.目标约束则可将右端项视为要达到的目标,但允许发生证或负的偏差,因此在这些约束中加入正、负偏差变量. 在线性规划的硬约束中加入正负偏差变量(加上负偏差变量、减去正偏差变量),将符号变为等号就转变为目标约束. (3)优先因子(优先等级)与权系数 在现实的决策背景下,决策者往往具有多个目标,但这些目标是有主次轻重的不同.赋予优先因子,规定,表示级目标比级具有绝对的优先权,在优先保证级目标时可不考虑级目标.权系数可区别同级目标中两个目标的差异. (4)目标规划的目标函数 目标规划的目标函数由各目标约束的正负偏差变量和赋予相应的优先因子构造而成.当每一目标给定后,决策者的要求是尽可能地缩小偏离目标值.因此,目标规划的目标函数只能是,其基本形式有三种: 要求恰好达到目标值,即正负偏差都要求尽可能地小,此时 ②要求不超过目标值,即允许达不到目标值,就是正偏差要尽可能地小,即 ③要求超过目标值,即超过量不限,就是负偏差要尽可能地小,此时 2.目标规划模型的建立、例题及习题讲解(60分钟) 3、目标函数:只有min一种,不含决策变量 不同目标的重要程度有两种差别: 绝对差别: 用优先因子Pj表示,P1》P2》…》Pk, 即Pl对应的目标绝对优先于Pl+1对应的目标. 相对差别: 具有同一级别优先因子的多个目标,可根据目标的相对重要程度,分别赋予它们不同的权值,以区别不同的偏差变量在同一优先级内的相对重要程度. 目标规划的解:往往不能满足所有的目标约束,但一定满足系统约束,故称为满意解. 目标规划没有系统约束时,一定存在满意解. 目标规划模型与线性规划模型的区别 第21、22 次课 4 学时 授课章节 第四章 目标规划 第二节 目标规划的图解法及单纯形法 授课方式 理论课 课堂教学 目的及要求 掌握目标规划的规划求解法.重点要求是图解法. 能够运用WinQSB软件求解目标规划 课堂教学 重点及难点 重点: 目标规划图解法 教学过程 教学过程 第21次课: 1.目标规划的图解法的思路(20分钟) 首先是在可行域 R 内寻找一个使P1级各目标均满足的区域R1; 然后再在R1 中寻找一个使P2 级各目标均满足的区域R2 ; 接着再在R2 中寻找一个满足P3 级各目标的区域R3 ; 如此继续直到寻找到一个区域Rk 满足Pk 级各目标,而不保证满足其后的各级目标,这时Rk即为这个目标规划的最优解空间,其中的任一点均为这个目标规划的满意解. 2.例题4-4,4-5(70分钟) 3.总结目标规划图解法步骤(10分钟) (1)按照绝对约束画出可行域(满足系统约束和决策变量非负的解的集合); (2)不考虑正负偏差变量,画出目标约束的边界线,并标出偏差变量变化时的直线平移方向; (3)按优先级别和权重依次分析各级目标. 第22次课: 1.目标规划单纯形法(30分钟) 单纯形法求解目标规划可参照第1章的步骤,只是目标规划的检验要按优先级顺序逐级进行,不同的是: (1)首先使得检验数中P1的系数非负,再使得P2的系数非负,依次进行; (2)(最优解判别准则)当P1、P2、…、Pk对应的系数全部非负时得到满意解; (3)如果P1,…,Pi行系数非负,而Pi+1行存在负数,并且负数所在列上面P1,…,Pi行中存在正数时,得到满意解,计算结束. 2.习题(70分钟) 第23 次课 2 学时 授课章节 第五章 运输与指派问题 第一节 运输问题的数学模型及特征 授课方式 理论课 课堂教学 目的及要求 正确理解运输问题的数学模型、解的性质和基的特征; 课堂教学 重点及难点 重点: 具有m个产地n个销地的平衡运输问题 1.具有m+n-1个基变量 2.闭回路的概念 3.怎样判断m+n-1个变量是否构成一组基变量 难点: 不平衡的运输问题 教学过程 教学过程 一、运输问题的一般数学模型(40分钟) 三种情况(从总产量与总销量是否平衡考虑) 1、供求平衡时 具备运输问题模型特征的还有布局问题等,统称为"康希问题" 特点:(1)有m*n个变量,m+n个约束条件,可证其中任何m+n-1个都是相互独立的,即A中任何m+n-1个行向量线性无关,故基本可行解中基变量的个数为m+n-1 (2)运输问题一定有最优解 由于运输问题模型的特殊性,用单纯形法求解很不方便,可采用特殊的方法求解,常用的有:表上作业法,图上作业法. 2、供过于求时 3、供不应求时 后两类不平衡的运输问题,可通过设置虚拟"销地"或"产地",化为平衡运输问题求解. 二、结合例题讲解运输问题模型(20分钟) 三、定理5.1:设m有个产地n个销地且产销平衡的运输问题,则基变量数为m+n-1.(15分钟) 定理5.3:m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路.(15分钟) 课堂小结,布置作业 第24、25 次课 4 学时 授课章节 第五章 运输与指派问题 第二节 运输单纯形法(表上作业法)第三节运输模型的应用 授课方式 理论课 课堂教学 目的及要求 掌握平衡运输问题的求解方法:表上作业法 1.求初始运输方案,用最小元素法、元素差额法(Vogel近似法) 2.求检验数,用闭回路法和位势法 3.调整运量,用闭回路法 4.极大值问题的求解方法、不平衡问题、需求量不确定问题 5.掌握运输问题模型的应用 课堂教学 重点及难点 重点: 表上作业法的求解步骤 难点: 极大值问题的求解方法、不平衡问题、需求量不确定问题 教学过程 教学过程 第24次课(100分钟) 1.求初始运输方案,用最小元素法、元素差额法(Vogel近似法) 2.求检验数,用闭回路法和位势法 3.调整运量,用闭回路法 第25次课(100分钟) 4.极大值问题的求解方法 5.不平衡问题 6.需求量不确定问题 7.例5-14运输问题模型的应用:多时期的综合生产计划问题 8.课堂小结,布置作业 结合例题讲解: 1.确定初始方案(最小元素法) 按通常习惯,运费最小的优先供应,在运价表中不断的选择最小元素格,给予优先安排,得表4.8 B1 B2 B3 B4 产量 A1 4 1 8 8 5 4 6 A2 9 5 2 6 2 3 4 A3 3 5 11 4 2 7 12 销量 6 2 7 7 22 (基变量个数m+n-1) 初始方案对应运输问题的一个基本可行解 x11=1,x13=5,x22=2,x23=2,x31=5,x34=7,其余xij=0 相应的总运费=95(万元) 2.最优解检验 求检验数(位势法): (1)列位势方程组,并求解:(数子格)cij=ui+vj (2)求空格检验数:初始方案中,调运量不为零的格子的检验数为零,故只需求空格的检验数. λij=cij-(ui+vj) λ12=1,λ14=1,λ21=7,λ24=2,λ32=5,λ33=-3 判别准则:若检验数中没有负数,则该方案为最优方案,否则,要进行调整. 在实际中,只要从上到下,从左到右,依次求每个空格的检验数,当一出现负检验数,就表明方案非最优,需要调整,其它空格的检验数就不必再求了. B1 B2 B3 B4 行A1 4 + 1 8 8 - 5 4 u1=0 A2 9 5 2 6 2 3 u2=-2 A3 3 - 5 11 4 + 2 7 u3=-1 列v1=4 v2=7 v3=8 v4=3 3. 方案的调整(闭回路法) 思路:根据单纯形法的思想,由一个基础可行解求得另一个基础可行解,要进行换基迭代,其关键是求主元素.对于运输问题,这一过程可在表上进行.其方法是:选取最小负检验数作为主元素,作该空格的闭回路,对闭回路拐角点上的货运量作相应的调整,目的是把该非基变量变为基变量,即使这个非基变量的值由零增大到一适当的数值,并保持横向、纵向的平衡,因此,要使拐角点上一基变量的值为零(即成为非基变量),同时还必须使改变后的各基变量保持非负,故非基变量增大的值(调整量)应为闭回路中第奇数次拐角点中最小的货运量. (1)确定进基变量:选取最小负检验数对应的变量为进基变量.该例λ33=-3最小,故x33 为进基变量. (2)确定出基变量:作x33对应格的闭回路.并依次对拐角点赋予"+","-"相间的符号. 可以证明:过每一个空格可以作并且只可以作一条闭回路 取调整量 θ=min{"-"拐角点的运量},θ=min{5,5}=5 出基变量为x13或x31 (3)调整规则:"+"格(调运量)+θ,"-"格(调运量)-θ 调整后的新方案如表所示 B1 B2 B3 B4 产量 A1 4 6 8 8 4 6 A2 9 5 2 6 2 3 4 A3 3 0 11 4 5 2 7 12 销量 6 2 7 7 22 新方案对应的运费=80(万元) 下降了 95-80=15=θ*|λ33|=5*3; 再检验、调整 B1 B2 B3 B4 行A1 4 6 8 8 4 u1=0 A2 9 5 2 6 - 2 3 + u2= 1 A3 3 0 11 4 + 5 2 - 7 u3=--1 列v1=4 v2=4 v3=5 v4= 3 λ12=4, λ13=3, λ14=1, λ21=4, λ24= -1, λ32=8 θ=min{2,7}=2 x24进基,x23出基 调整后,得最优方案(描述) B1 B2 B3 B4 产量 A1 4 6 8 8 4 6 A2 9 5 2 6 3 2 4 A3 3 0 11 4 7 2 5 12 销量 6 2 7 7 22 最小运费z=78(万元) 检验: B1 B2 B3 B4 行A1 4 6 8 8 4 U1=0 A2 9 5 2 6 3 2 U2=0 A3 3 0 11 4 7 2 5 U3=-1 列V1=4 V2=5 V3=5 V4=3 λ12=3,λ13=3,λ14=1,λ21=5,λ23=1,λ32=7 第26 次课 2 学时 授课章节 第四章 运输与指派问题 第四节指派问题 授课方式 理论课 课堂教学 目的及要求 将生产计划问题转化为运输问题求解 掌握指派问题的数学模型,求解指派问题的匈牙利算法及其他变异问题 课堂教学 重点及难点 重点: 指派问题的匈牙利算法 难点: 变异问题如何转换为平衡运输问题并求解 教学过程 教学过程 指派问题数学模型(20分钟) 假设m个人恰好做m项工作,第i个人做第j项工作的效率为cij≥0,效率矩阵为[cij] , 如何分配工作使效率最佳(min或max)的数学模型为 2.匈牙利算法(50分钟) 【定理5.4】如果从分配问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势),从每一列分别减去(或加上)一个常数vj(称为该列的位势),得到一个新的效率矩阵[bij],其中bij=cij-ui-vj,则[bij]的最优解等价于[cij]的最优解,这里cij、bij均非负. 【定理5.5】若矩阵A的元素可分成"0"与非"0"两部分,则覆盖"0"元素的最少直线数等于位于不同行不同列的"0"元素(称为独立元素)的最大个数. 如果覆盖"0"元素的最少直线数等于m,则存在m个独立的"0"元素,令这些零元素对应的xij等于1,其余变量等于0,这时目标函数值等于零,得到最优解. 匈牙利法的条件: (1)问题是求最小值 (2)人数与工作数相等,即m=n (3)效率非负,即cij≥0. 3.其它变异问题(30分钟) 最大化指派问题应转化为最小化问题求解.效益矩阵C=(cij),其中最大元素为m.令矩阵 B=(bij)= (m-cij),则以B为效益矩阵的最小化指派问题和以C为效益矩阵的原最大化指派问题有相同最优解. 人数和事数不等的指派问题,可添加虚拟的人或事,其系数取0,化为平衡指派问题. 一个人可做几件事的指派问题,可将一个人视为相同的几个人,化为平衡指派问题. 某事一定不能由某人做的指派问题,可将某人做某事所用的时间设为充分大的正数M . 4.课堂小结,布置作业 第27、28 次课 4 学时 授课章节 第八章 动态规划 第一节 动态规划的数学模型 第二节 资源分配问题 授课方式 理论课 课堂教学 目的及要求 一、掌握动态规划的概念、原理、分类、基本概念,能够建立动态规划模型并求解; 动态规划模型的建立一般包含以下内容: 明确阶段划分 明确状态变量sk的含义及取值范围 明确决策变量xk的含义及取值范围 正确写出状态转移方程sk+1=Tk(sk,xk) 明确阶段指标函数rk(sk,xk)和最优指标函数fk(sk) 正确写出基本方程 二、了解资源分配问题模型的建立及求解 课堂教学 重点及难点 重点: 动态规划的基本概念、建立动态规划模型 难点: 1.能够正确写出状态转移方程sk+1=Tk(sk,xk) 2.明确阶段指标函数rk(sk,xk)和最优指标函数fk(sk) 3.正确写出基本方程 教学过程 第27次课(100分钟) 动态规划的原理及能够解决的几类问题(10分钟) 引例:最短路径问题(20分钟) 动态规划的基本概念(70分钟) (1)阶段和阶段变量 将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序去求每阶段的解.阶段变量用k表示. (2)状态和状态变量 状态:各阶段开始时的自然位置或客观条件叫做状态. 状态的选取要具有无后效性.即某阶段的状态给定后,则过程未来发展不受该阶段以前各阶段状态的影响. 状态(state)变量sk:描述各阶段状态的变量称为状态变量. 状态集合Sk:sk的取值范围称为状态集合,sk∈Sk (3)决策与策略 决策(decision):当状态给定后,为过渡到下一阶段所作出的决定. 决策变量xk:描述决策的变量.第k阶段的决策变量只与当前状态sk有关,既xk=xk(sk). 决策集合Xk(sk):决策变量的允许值范围称为决策集合,用Xk(sk)(或Dk(sk))表示第k阶段状态sk的决策集合. 策略(policy):各阶段决策确定后,整个问题的决策序列就构成一个策略,记作p1,N(x1,x2,…,xn) (4)状态转移方程:由一个阶段的状态到下一阶段的状态的变化叫做状态转移.第k阶段的状态为sk, 采用决策xk,则第k+1阶段的状态sk+1就完全确定,它们的关系表示为sk+1=Tk(sk,xk)称为状态转移方程 (5)指标函数 阶段指标函数rk(sk,xk):第k阶段的状态为sk,执行决策xk时产生的效果值,叫做阶段效益.它表示在第k阶段,状态为sk采用决策xk时的收益. 子过程指标函数Vk,n(sk,pk,n):表示在第k阶段,状态为sk采用策略pk,n时,后部子过程的效益值. 策略不同,指标函数值也不同 从k阶段状态sk出发,对所有的子策略,最优的过程指标函数称为最优指标函数,记为fk(sk),通常取Vk的最大值或最小值. 最优指标函数:是指从第k阶段状态sk采用最优子策略p*k,n到过程终止时的最佳效益值.记做fk(sk) 初始状态s1的最优指标函数 是原过程的最佳效益值,所对应的策略(x*1,x*2,…,x*n)就是最优策略.最优指标函数: 称为贝尔曼函数 第28次课(100分钟) 1.动态规划模型由递归方程、边界条件及状态转移方程构成(10) 2.用动态规划递推方法求解例8-1(40分钟) 3.资源分配问题例8-2(50分钟) 第29 次课 2 学时 授课章节 第八章 动态规划 第三节 生产与存储问题 第四节 背包问题 授课方式 理论课 课堂教学 目的及要求 掌握生产与存储问题以及背包问题的动态规划模型,能够用WinQSB软件求解这两类问题 课堂教学 重点及难点 重点及难点: 生产与存储问题以及背包问题的动态规划模型 教学过程 教学过程 1.生产与存储问题动态规划模型(例8-4)(50分钟) 阶段k:月份,k=1,2,…,6 状态变量sk:第k月初的库存量,0≤sk≤50 决策变量xk:第k月的生产量 状态转移方程:sk+1=sk+xk-dk 决策允许集合: 阶段指标 终端条件f7(s7)=0 递推方程: 背包问题(30分钟) 一维背包问题数学模型为 ck为第k种物品的单位价值,wk是第k种物品的单位重量或体积,W是背包的重量或体积限制.动态规划的有关要素如下: 阶段k:第k次装载第k种物品(k=1,2,…,n) 状态变量sk:第k次装载时背包还可以装载的重量(或体积) 决策变量xk:装载第k种物品的件数 决策允许集合:Dk(sk)={dk|0( xk(sk/wk,xk为整数} 状态转移方程:sk+1=sk-wkxk 阶段指标:vk=ckxk 递推方程: 终端条件; fn+1(sn+1)=0 3.用WinQSB求以上两类问题(20分钟) 4.课堂小结,布置作业 第30 次课 2 学时 授课章节 第十二章 博弈论 第一节 引言 授课方式 理论课 课堂教学 目的及要求 了解博弈论的发展、应用领域,几个经典的博弈模型,掌握博弈三要素、博弈的结构和分类 课堂教学 重点及难点 重点: 博弈的基本要素和分类 教学过程 教学过程 引言(20分钟) 几个经典博弈模型(齐王田忌赛马、囚徒困境) 总结博弈特征(5分钟) 有一定的规则 有一个确定的结果:赢、输或平局 参与者的策略或计谋,在其中有举足轻重的的作用 策略和利益有相互依存性 3. 博弈论历史和发展(30分钟) 4. 博弈的基本要素(10分钟) 5. 博弈的分类(10分钟) 6. 博弈论在我国经济中的应用(20分钟) 7. 课堂小结,布置作业 第31、32 次课 4 学时 授课章节 第十二章 博弈论 第二节 纳什均衡 第三节 矩阵博弈 授课方式 理论课 课堂教学 目的及要求 掌握博弈行为、纳什均衡、纯策略、混合策略等概念;会用"囚徒困境"分析社会经济生活中的竞争现象;理解博弈模型的基本要素:局中人、策略集、赢得函数;熟练掌握矩阵博弈的求解 课堂教学 重点及难点 重点:1、博弈的有关概念及相关理论 2、矩阵博弈的解法 难点:纳什均衡的概念 教学过程 教学过程 第31次课(100分钟) 纳什均衡的定义 纳什均衡(Nash Equilibrium): 假定有n个博弈方参加博弈,在给定其他博弈方策略的条件下,每个人选择自己的最优策略(个人最优策略可能依赖也可能不依赖他人策略),从而使自己利益最大化,所有局中人的策略一起构成一个策略组合.而Nash均衡是这样一种策略组合,由所有参与人的最优策略组成,给定别人策略的条件下,没有任何单个参与人有积极性选择其他策略,从而没有任何人有积极性打破这种均衡,Nash均衡是一种" 僵局":给定别人不动的情况下,没有人有兴趣动. 矩阵博弈的概念及模型 定义:两人有限零和博弈 模型:G={S1,S2;A} S1={α1,α2,…,αm}——局中人Ⅰ的纯策略集 S2={β1,β2,…,βn}——局中人Ⅱ的纯策略集 ——局中人Ⅰ的赢得矩阵 αi j——局中人Ⅰ在局势(αi,βj)下的赢得值 3.求解矩阵博弈 (1)纯策略解(鞍点解):最小最大原则 (2)混合策略解:代数法、方程组法、线性规划法、优超原则