《清华大学-《运筹学》课程教学大纲》由会员分享，可在线阅读，更多相关《清华大学-《运筹学》课程教学大纲（7页珍藏版）》请在金锄头文库上搜索。
1、运筹学课程教学大纲 课程名称：运筹学 编号.20345144： 学时：72编者姓名：曾鸿能 单位：中山大学 职称：副教授主审姓名： 单位： 职称：教授对象：本科生 专业：资源与环境规划 年级：三年级编写日期：2001年9月一、 课程目的与教学基本要求学习本课程后，使学生掌握运筹学有关分支的基本理论和方法，牢固掌握解题算法步骤，培养学生应用规划论、优化技术解决实际问题能力。为专业课在系统规划、最优设计、参数优选、最优管理与运行等数学方法及计算机算法打下必要的基础。在已学过微积分、初等集合论和线性代数基础上学习本课程，通过教授、自学、复习、作业练习、辅导、编程上机等教学环节达到上述目的。学习中要注
2、意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。着重基本概念、基本思路、基本方法、算法步骤、几何直观解析。了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。应注重实际应用中建立模型，选择可行求解的理论方法，编制算法的计算机程序这三方面训练的有机结合。二、 课程内容（含学时分配）绪言：运筹学简史、性质和特点、工作步骤、模型、分支及应用、运筹学展望（1学时）i. 线性规划与目标规划（共30学时）1-1 线性规划问题及其数学模型 （2学时）一、应用实例 二、线性规划的数学模型 三、标准形式1-2 线性规划问题的图解法 （1学时）教学要求：1初步掌握建立线性
3、规划模型方法 2掌握线性规划模型特征；如何化线性规划模型为标准型 3掌握两个变量线性规划问题的图解法重点：通过图解法初步了解基本概念和求解思路1-3 线性规划的基本概念和基本定理 （4学时）教学要求：1掌握可行解、基、凸集、凸组合、顶点的概念 2了解线性规划理论依据-几个基本定理、求解线性规划问题基本思路重点：三个基本定理难点：基本定理的证明1-4 单纯形法 （4学时）1 单纯形法求解过程说明2 单纯形表（1） 单纯形表的结构和原理（2） 换基 确定换入变量 确定换出变量 旋转迭代教学要求：牢固掌握线性规划的单纯形求解方法重点：单纯形方法求解步骤和公式难点：单纯形表构成原理，换基迭代公式推导1
4、-5 单纯形法进一步讨论 （2学时）（一）大M单纯形法 （二）两阶段法 （三）退化问题 （四）检验数的几种表示法（五）单纯形法小结教学要求：1了解引入工人变量目的 2牢固掌握大M法和两阶段法求解过程、判别什么情况下无解 3牢固掌握单纯形法计算框图重点：两阶段法及单纯形法计算框图1-6 改进单纯形法 （2学时）教学要求：1了解改进单纯形方法的思想 2掌握改进单纯形法计算步骤重点：改进单纯形法计算步骤（主要用于计算机计算）难点：新基逆矩阵求解公式及其实质1-7 线性对偶规划 （4学时）一、对偶问题提出 二、对偶规则 三、线性对偶理论四、对偶问题的经济学解释影子价格 五、对偶单纯形法教学要求：1掌握
5、对偶规则 2了解线性对偶理论、影子价格的意义 3牢固掌握对偶单纯形法重点：对偶单纯形法计算步骤及对偶单纯形法应用范围难点：线性对偶理论的证明1-8 灵敏度分析与参数线性规划 （3学时）教学要求：1掌握系数变化范围的确定及增加新变量、新约束灵敏度分析 2掌握参数连续变化对最优解及最优值的影响重点：灵敏度分析与参数线性规划的应用。关键是判断最优方案的可行性和最优性是否被破坏，从而确定变化范围。1-9 运输问题 （4学时）一、运输问题的数学模型 二、初始基可行解的确定三、换基迭代，确定最优解 四、应用举例（包括习题课）教学要求：1掌握运输问题的数学模型、系数矩阵特殊形式 2掌握用西北角法、最小元素法
6、求初始基可行解 3掌握位势法求解、牢固掌握三合一表格求解运输问题过程重点：运输问题的求解过程。熟悉运输、作物布局、转运等问题的应用1-10 目标规划 （4学时）一 基本概念及数学模型二 目标规划的图解法三 目标规划的单纯形法四 应用举例教学要求：1熟悉目标规划有关的概念，正确建立目标规划数学模型 2牢固掌握目标规划的单纯形求解方法重点：对实际问题如何建立目标规划的数学模型，如何用目标规划的单纯形法求解，对各种满意解的分析。ii. 整数规划 （共8学时）2-1 整数规划问题的提出 （2学时）2-2 割平面法2-3 分枝定界法 （2学时）2-4 0-1型整数规划 （2学时）2-5 指派问题 （2学
7、时）教学要求：1了解割平面法的基本思路，掌握割平面约束的生成、割平面法的求解步骤 2了解分枝定界法的基本思路，掌握两个分枝的求法、定界与剪枝的原则，掌握分枝定界法解题过程 3掌握0-1型整数规划求解过程 4掌握指派问题的匈牙利解法重点：分枝定界法求解，定界与剪枝原则难点：0-1型整数规划变量的不可行性指标计算 iii. 非线性规划 （全部授完需36学时）3-1 非线性规划的数学模型和基本概念 （4学时）教学要求：1了解非线性规划数学模型一般形式及其与线性规划的区别 2掌握基本概念：局部极值和全局极值、梯度、海赛矩阵、正定、负定、半正定、半负定矩阵、不定矩阵 3掌握凸函数的定义和性质，凸函数的判
8、别（一阶条件和二阶条件定理） 4掌握凸规划的定义极其重要特性重点：凸函数、凸规划的定义极其判别3-2 无约束问题最优性条件与下降迭代算法 （2学时）教学要求：1掌握用海赛矩阵判断驻点的性质 2掌握一阶必要条件，二阶必要条件，二阶充分条件和充要条件四个定理，了解定理的证明 3了解下降迭代算法的概念及下降迭代算法的一般步骤，了解收敛性及收敛速度（用收敛的阶或二次收敛性判别），掌握迭代终止判别准则3-3 一维搜索 （6学时）一进退法 二斐波那契法 三0618法（黄金分割法）四抛物线插值法 五三次插值法（作一般介绍）教学要求：1掌握各种方法的特点、优点与不足 2掌握各种方法计算步骤与算法框图重点：06
9、18法，抛物线插值法3-4 无约束极值问题的解析法 （8学时）一 最速下降法二 牛顿法三 共轭梯度法（F-R法）四 变尺度法（DFP、BFGS算法）教学要求：1掌握几种方法的基本原理和计算步骤 2掌握几种方法搜索方向构成：如负梯度方向、牛顿方向、共轭方向、拟牛顿方向 3了解各种方法优缺点重点：熟悉几种方法算法步骤。特别是目前认为较好的DFP、BFGS算法难点：DFP方法中变尺度矩阵的推导3-5 无约束极值问题的直接法 （6学时）一坐标轮换法 二步长加速法 三powell法 四单纯形调优法教学要求：1掌握几种方法的算法步骤 2了解几种方法的优缺点重点：powell方法及目前生产中常用的单纯形调优
10、法3-6 等式约束条件下的非线性规划 （2学时）一等式约束下的消元法 二拉格朗日乘子法 三罚函数法（外点法）教学要求：了解拉格朗日乘子法，掌握外点法3-7 不等式约束条件下的非线性规划 （8学时）一 可行方向和起作用的约束的概念二 库恩塔克条件三 非线性约束条件下的可行方向法四 罚函数法 1外罚函数法 2内罚函数法 3混合法（只作简单介绍）4乘子法（简单介绍）五 复合形法教学要求：1了解库恩塔克条件 2掌握Zoutendijk可行方向法以及Topkis-Veinott修正方法。了解下降可行方向满足条件。了解广义既约梯度法（GRG算法） 3了解化约束为无约束的惩罚法中最基本的两种方法：外罚函数法
11、和内罚函数法。了解这两种方法适用范围及其优缺点。针对两种方法不足而改进的乘子法作一般的了解。 4掌握复合形法基本思路及计算步骤重点：惩罚法，工程中常用的复合形法难点：方法定理的证明3-8 非线性规划问题的线性化 （6学时）一 用线性逼近法求解线性约束条件下的非线性规划（Frank-Wolfe方法）二 用线性逼近法求解非线性约束条件下的非线性规划（近似规划法，即MAP法）三 变量分割法四 可分规划法教学要求：1掌握几种方法适用范围及特点 2掌握非线性规划如何线性化 3掌握各种方法求解过程重点：近似规划法（MAP法）3-9 应用举例 （2学时）了解水资源规划中非线性规划如何作线性化求解第四章 动态
12、规划 （共16学时）4-1 动态规划的基本方法与原理 （5学时）一 多阶段决策过程及实例二 动态规划的基本概念三 最优性原理四 动态规划的基本思想和基本方程五 动态规划的数学模型及构成模型的条件六 动态规划的逆序解法和顺序解法4-2 动态规划的最优性定理 （1学时）4-3 不定期多阶段决策过程 （2学时）一函数迭代法 二策略迭代法4-4 多维动态规划 （3学时）一 拉格朗日乘数法二 逐次逼近法三 粗格子点法（疏密法）四 离散微分动态规划法（DDDP法）4-5 确定性动态规划应用举例 （2学时）4-6 随机性问题的动态规划法 （3学时）一 各阶段的随机状态变量相互独立时的动态规划问题二 相邻两阶段的随机状态变量具有简单的马尔可夫链关系时的动态规划问题教学要求：1掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线2了解动态规划的基本理论：最优性定理和最优性原理3掌握动态规划基本思想和基本方程4牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系5了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线
