清华大学-《运筹学》课程教学大纲

1、运筹学课程教学大纲 课程名称：运筹学 编号.20345144： 学时：72编者姓名：曾鸿能 单位：中山大学 职称：副教授主审姓名： 单位： 职称：教授对象：本科生 专业：资源与环境规划 年级：三年级编写日期：2001年9月课程目的与教学基本要求学习本课程后，使学生掌握运筹学有关分支的基本理论和方法，牢固掌握解题算法步骤，培养学生应用规划论、优化技术解决实际问题能力。为专业课在系统规划、最优设计、参数优选、最优管理与运行等数学方法及计算机算法打下必要的基础。在已学过微积分、初等集合论和线性代数基础上学习本课程，通过教授、自学、复习、作业练习、辅导、编程上机等教学环节达到上述目的。学习中要注意到学

2、科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。着重基本概念、基本思路、基本方法、算法步骤、几何直观解析。了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。应注重实际应用中建立模型，选择可行求解的理论方法，编制算法的计算机程序这三方面训练的有机结合。课程内容（含学时分配）绪言：运筹学简史、性质和特点、工作步骤、模型、分支及应用、运筹学展望（1学时）线性规划与目标规划（共30学时）1-1 线性规划问题及其数学模型 （2学时）一、应用实例 二、线性规划的数学模型 三、标准形式1-2 线性规划问题的图解法 （1学时）教学要求：1初步掌握建立线性规划模型方法 2掌

3、握线性规划模型特征；如何化线性规划模型为标准型 3掌握两个变量线性规划问题的图解法重点：通过图解法初步了解基本概念和求解思路1-3 线性规划的基本概念和基本定理 （4学时）教学要求：1掌握可行解、基、凸集、凸组合、顶点的概念 2了解线性规划理论依据-几个基本定理、求解线性规划问题基本思路重点：三个基本定理难点：基本定理的证明1-4 单纯形法 （4学时）单纯形法求解过程说明单纯形表单纯形表的结构和原理换基 确定换入变量 确定换出变量 旋转迭代教学要求：牢固掌握线性规划的单纯形求解方法重点：单纯形方法求解步骤和公式难点：单纯形表构成原理，换基迭代公式推导1-5 单纯形法进一步讨论 （2学时）（一）

4、大M单纯形法 （二）两阶段法 （三）退化问题 （四）检验数的几种表示法（五）单纯形法小结教学要求：1了解引入工人变量目的 2牢固掌握大M法和两阶段法求解过程、判别什么情况下无解 3牢固掌握单纯形法计算框图重点：两阶段法及单纯形法计算框图1-6 改进单纯形法 （2学时）教学要求：1了解改进单纯形方法的思想 2掌握改进单纯形法计算步骤重点：改进单纯形法计算步骤（主要用于计算机计算）难点：新基逆矩阵求解公式及其实质1-7 线性对偶规划 （4学时）一、对偶问题提出 二、对偶规则 三、线性对偶理论四、对偶问题的经济学解释影子价格 五、对偶单纯形法教学要求：1掌握对偶规则 2了解线性对偶理论、影子价格的意

5、义 3牢固掌握对偶单纯形法重点：对偶单纯形法计算步骤及对偶单纯形法应用范围难点：线性对偶理论的证明1-8 灵敏度分析与参数线性规划 （3学时）教学要求：1掌握系数变化范围的确定及增加新变量、新约束灵敏度分析 2掌握参数连续变化对最优解及最优值的影响重点：灵敏度分析与参数线性规划的应用。关键是判断最优方案的可行性和最优性是否被破坏，从而确定变化范围。1-9 运输问题 （4学时）一、运输问题的数学模型 二、初始基可行解的确定三、换基迭代，确定最优解 四、应用举例（包括习题课）教学要求：1掌握运输问题的数学模型、系数矩阵特殊形式 2掌握用西北角法、最小元素法求初始基可行解 3掌握位势法求解、牢固掌握

6、三合一表格求解运输问题过程重点：运输问题的求解过程。熟悉运输、作物布局、转运等问题的应用1-10 目标规划 （4学时）基本概念及数学模型目标规划的图解法目标规划的单纯形法应用举例教学要求：1熟悉目标规划有关的概念，正确建立目标规划数学模型 2牢固掌握目标规划的单纯形求解方法重点：对实际问题如何建立目标规划的数学模型，如何用目标规划的单纯形法求解，对各种满意解的分析。 整数规划 （共8学时）2-1 整数规划问题的提出 （2学时）2-2 割平面法2-3 分枝定界法 （2学时）2-4 0-1型整数规划 （2学时）2-5 指派问题 （2学时）教学要求：1了解割平面法的基本思路，掌握割平面约束的生成、割

7、平面法的求解步骤 2了解分枝定界法的基本思路，掌握两个分枝的求法、定界与剪枝的原则，掌握分枝定界法解题过程 3掌握0-1型整数规划求解过程 4掌握指派问题的匈牙利解法重点：分枝定界法求解，定界与剪枝原则难点：0-1型整数规划变量的不可行性指标计算 非线性规划 （全部授完需36学时）3-1 非线性规划的数学模型和基本概念 （4学时）教学要求：1了解非线性规划数学模型一般形式及其与线性规划的区别 2掌握基本概念：局部极值和全局极值、梯度、海赛矩阵、正定、负定、半正定、半负定矩阵、不定矩阵 3掌握凸函数的定义和性质，凸函数的判别（一阶条件和二阶条件定理） 4掌握凸规划的定义极其重要特性重点：凸函数、

8、凸规划的定义极其判别3-2 无约束问题最优性条件与下降迭代算法 （2学时）教学要求：1掌握用海赛矩阵判断驻点的性质 2掌握一阶必要条件，二阶必要条件，二阶充分条件和充要条件四个定理，了解定理的证明 3了解下降迭代算法的概念及下降迭代算法的一般步骤，了解收敛性及收敛速度（用收敛的阶或二次收敛性判别），掌握迭代终止判别准则3-3 一维搜索 （6学时）一进退法 二斐波那契法 三0618法（黄金分割法）四抛物线插值法 五三次插值法（作一般介绍）教学要求：1掌握各种方法的特点、优点与不足 2掌握各种方法计算步骤与算法框图重点：0618法，抛物线插值法3-4 无约束极值问题的解析法 （8学时）最速下降法牛

9、顿法共轭梯度法（F-R法）变尺度法（DFP、BFGS算法）教学要求：1掌握几种方法的基本原理和计算步骤 2掌握几种方法搜索方向构成：如负梯度方向、牛顿方向、共轭方向、拟牛顿方向 3了解各种方法优缺点重点：熟悉几种方法算法步骤。特别是目前认为较好的DFP、BFGS算法难点：DFP方法中变尺度矩阵的推导3-5 无约束极值问题的直接法 （6学时）一坐标轮换法 二步长加速法 三powell法 四单纯形调优法教学要求：1掌握几种方法的算法步骤 2了解几种方法的优缺点重点：powell方法及目前生产中常用的单纯形调优法3-6 等式约束条件下的非线性规划 （2学时）一等式约束下的消元法 二拉格朗日乘子法 三

10、罚函数法（外点法）教学要求：了解拉格朗日乘子法，掌握外点法3-7 不等式约束条件下的非线性规划 （8学时）可行方向和起作用的约束的概念库恩塔克条件非线性约束条件下的可行方向法罚函数法 1外罚函数法 2内罚函数法 3混合法（只作简单介绍）4乘子法（简单介绍）复合形法教学要求：1了解库恩塔克条件 2掌握Zoutendijk可行方向法以及Topkis-Veinott修正方法。了解下降可行方向满足条件。了解广义既约梯度法（GRG算法） 3了解化约束为无约束的惩罚法中最基本的两种方法：外罚函数法和内罚函数法。了解这两种方法适用范围及其优缺点。针对两种方法不足而改进的乘子法作一般的了解。 4掌握复合形法基

11、本思路及计算步骤重点：惩罚法，工程中常用的复合形法难点：方法定理的证明3-8 非线性规划问题的线性化 （6学时）用线性逼近法求解线性约束条件下的非线性规划（Frank-Wolfe方法）用线性逼近法求解非线性约束条件下的非线性规划（近似规划法，即MAP法）变量分割法可分规划法教学要求：1掌握几种方法适用范围及特点 2掌握非线性规划如何线性化 3掌握各种方法求解过程重点：近似规划法（MAP法）3-9 应用举例 （2学时）了解水资源规划中非线性规划如何作线性化求解动态规划 （共16学时）4-1 动态规划的基本方法与原理 （5学时）多阶段决策过程及实例动态规划的基本概念最优性原理动态规划的基本思想和基

12、本方程动态规划的数学模型及构成模型的条件动态规划的逆序解法和顺序解法4-2 动态规划的最优性定理 （1学时）4-3 不定期多阶段决策过程 （2学时）一函数迭代法 二策略迭代法4-4 多维动态规划 （3学时）拉格朗日乘数法逐次逼近法粗格子点法（疏密法）离散微分动态规划法（DDDP法）4-5 确定性动态规划应用举例 （2学时）4-6 随机性问题的动态规划法 （3学时）各阶段的随机状态变量相互独立时的动态规划问题相邻两阶段的随机状态变量具有简单的马尔可夫链关系时的动态规划问题教学要求：1掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线2了解动态规

13、划的基本理论：最优性定理和最优性原理3掌握动态规划基本思想和基本方程4牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系5了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等6了解多维动态规划降维方法和减少离散状态点数方法7了解随机性问题的动态规划求解方法重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧；离散微分动态规划法难点：最优性定理的证明，随机性问题的动态规划（3）使用说明每讲完一种方法，至少布置一道作业，作为基本训练、巩固和加深对方法的基本原理，算法的步骤的理解。 计划讲授两次习题课，介绍难懂和技巧性强或教材没有详细提到的问题。 每讲完一章，结合资源与环境专业的实际，介绍方法的应用。 每讲完一章，作个小结，并介绍新方法，发展动向，以及教材还没有涉及到的内容。 在时间和条件许可下，可适当选择一些方法的计算程序作介绍，学生自己上机实习。 按学时的多少，适当增减内容。（4）主要参考书目钱颂迪主编， 运筹学（增订版）， 清华大学出版社， 1990年管梅谷、郑汉鼎， 线性规划， 山东科学技术出版社， 1983张建中、许绍吉著，