《运筹学》课程教学大纲
课程名称：运筹学
编号.20345144：
学时：72 编者姓名：曾鸿能
单位：中山大学
职称：副教授
主审姓名：
单位：
职称： 教授对象：本科生
专业：资源与环境规划
年级：三年级
编写日期：2001年9月
一、课程目的与教学基本要求 学习本课程后，使学生掌握运筹学有关分支的基本理论和方法，牢固掌握解题算法步骤，培养学生应用规划论、优化技术解决实际问题能力。为专业课在系统规划、最优设计、参数优选、最优管理与运行等数学方法及计算机算法打下必要的基础。
在已学过微积分、初等集合论和线性代数基础上学习本课程，通过教授、自学、复习、作业练习、辅导、编程上机等教学环节达到上述目的。学习中要注意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。着重基本概念、基本思路、基本方法、算法步骤、几何直观解析。了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。应注重实际应用中建立模型，选择可行求解的理论方法，编制算法的计算机程序这三方面训练的有机结合。
二、课程内容（含学时分配）
绪言：运筹学简史、性质和特点、工作步骤、模型、分支及应用、运筹学展望（1学时）
i.线性规划与目标规划（共30学时）
1-1 线性规划问题及其数学模型
（2学时）
一、应用实例
二、线性规划的数学模型
三、标准形式
1-2 线性规划问题的图解法
（1学时）
教学要求：1．初步掌握建立线性规划模型方法
2．掌握线性规划模型特征；如何化线性规划模型为标准型
3．掌握两个变量线性规划问题的图解法 重点：通过图解法初步了解基本概念和求解思路
1-3 线性规划的基本概念和基本定理
（4学时）
教学要求：1．掌握可行解、基、凸集、凸组合、顶点的概念
2．了解线性规划理论依据---几个基本定理、求解线性规划问题基本思路
重点：三个基本定理 难点：基本定理的证明
1-4 单纯形法
（4学时） 1．单纯形法求解过程说明 2．单纯形表
（1） 单纯形表的结构和原理
（2） 换基
Ⅰ确定换入变量
Ⅱ确定换出变量
Ⅲ旋转迭代 教学要求：牢固掌握线性规划的单纯形求解方法 重点：单纯形方法求解步骤和公式
难点：单纯形表构成原理，换基迭代公式推导
1-5 单纯形法进一步讨论
（2学时）
（一）大M单纯形法
（二）两阶段法
（三）退化问题
（四）检验数的几种表示法
（五）单纯形法小结
教学要求：1．了解引入工人变量目的
2．牢固掌握大M法和两阶段法求解过程、判别什么情况下无解
3．牢固掌握单纯形法计算框图 重点：两阶段法及单纯形法计算框图
1-6 改进单纯形法
（2学时）
教学要求：1．了解改进单纯形方法的思想
2．掌握改进单纯形法计算步骤
重点：改进单纯形法计算步骤（主要用于计算机计算） 难点：新基逆矩阵求解公式及其实质
1-7 线性对偶规划
（4学时）
一、对偶问题提出
二、对偶规则
三、线性对偶理论
四、对偶问题的经济学解释——影子价格
五、对偶单纯形法
教学要求：1．掌握对偶规则
2．了解线性对偶理论、影子价格的意义
3．牢固掌握对偶单纯形法
重点：对偶单纯形法计算步骤及对偶单纯形法应用范围 难点：线性对偶理论的证明
1-8 灵敏度分析与参数线性规划
（3学时）
教学要求：1．掌握系数变化范围的确定及增加新变量、新约束灵敏度分析
2．掌握参数连续变化对最优解及最优值的影响 重点：灵敏度分析与参数线性规划的应用。关键是判断最优方案的可行性和最优性是否被破坏，从而确定变化范围。
1-9 运输问题
（4学时）
一、运输问题的数学模型
二、初始基可行解的确定
三、换基迭代，确定最优解
四、应用举例（包括习题课） 教学要求：1．掌握运输问题的数学模型、系数矩阵特殊形式
2．掌握用西北角法、最小元素法求初始基可行解
3．掌握位势法求解、牢固掌握三合一表格求解运输问题过程 重点：运输问题的求解过程。熟悉运输、作物布局、转运等问题的应用
1-10 目标规划
（4学时） 一． 基本概念及数学模型 二． 目标规划的图解法 三． 目标规划的单纯形法 四． 应用举例
教学要求：1．熟悉目标规划有关的概念，正确建立目标规划数学模型
2．牢固掌握目标规划的单纯形求解方法 重点：对实际问题如何建立目标规划的数学模型，如何用目标规划的单纯形法求解，对各种满意解的分析。
ii.整数规划
（共8学时）
2-1 整数规划问题的提出
（2学时） 2-2 割平面法
2-3 分枝定界法
（2学时） 2-4 0-1型整数规划
（2学时） 2-5 指派问题
（2学时）
教学要求：1．了解割平面法的基本思路，掌握割平面约束的生成、割平面法的求解步骤
2．了解分枝定界法的基本思路，掌握两个分枝的求法、定界与剪枝的原则，掌
握分枝定界法解题过程
3．掌握0-1型整数规划求解过程
4．掌握指派问题的匈牙利解法 重点：分枝定界法求解，定界与剪枝原则
难点：0-1型整数规划变量的不可行性指标计算
iii.非线性规划
（全部授完需36学时）
3-1 非线性规划的数学模型和基本概念
（4学时）
教学要求：1．了解非线性规划数学模型一般形式及其与线性规划的区别
2．掌握基本概念：局部极值和全局极值、梯度、海赛矩阵、正定、负定、半正 定、半负定矩阵、不定矩阵
3．掌握凸函数的定义和性质，凸函数的判别（一阶条件和二阶条件定理）
4．掌握凸规划的定义极其重要特性 重点：凸函数、凸规划的定义极其判别
3-2 无约束问题最优性条件与下降迭代算法
（2学时） 教学要求：1．掌握用海赛矩阵判断驻点的性质
2．掌握一阶必要条件，二阶必要条件，二阶充分条件和充要条件四个定理，了
解定理的证明
3．了解下降迭代算法的概念及下降迭代算法的一般步骤，了解收敛性及收敛速
度（用收敛的阶或二次收敛性判别），掌握迭代终止判别准则
3-3 一维搜索
（6学时） 一．进退法
二．斐波那契法
三．0．618法（黄金分割法）
四．抛物线插值法
五．三次插值法（作一般介绍） 教学要求：1．掌握各种方法的特点、优点与不足
2．掌握各种方法计算步骤与算法框图 重点：0．618法，抛物线插值法
3-4 无约束极值问题的解析法
（8学时） 一． 最速下降法 二． 牛顿法
三． 共轭梯度法（F-R法）
四． 变尺度法（DFP、BFGS算法）
教学要求：1．掌握几种方法的基本原理和计算步骤
2．掌握几种方法搜索方向构成：如负梯度方向、牛顿方向、共轭方向、拟牛顿
方向
3．了解各种方法优缺点
重点：熟悉几种方法算法步骤。特别是目前认为较好的DFP、BFGS算法 难点：DFP方法中变尺度矩阵的推导
3-5 无约束极值问题的直接法
（6学时）
一．坐标轮换法
二．步长加速法
三．powell法
四．单纯形调优法
教学要求：1．掌握几种方法的算法步骤
2．了解几种方法的优缺点
重点：powell方法及目前生产中常用的单纯形调优法
3-6 等式约束条件下的非线性规划
（2学时） 一．等式约束下的消元法
二．拉格朗日乘子法
三．罚函数法（外点法）
教学要求：了解拉格朗日乘子法，掌握外点法
3-7 不等式约束条件下的非线性规划
（8学时） 一． 可行方向和起作用的约束的概念 二． 库恩——塔克条件
三． 非线性约束条件下的可行方向法 四． 罚函数法
1．外罚函数法
2．内罚函数法
3．混合法（只作简单介绍）
4．乘子法（简单介绍）
五． 复合形法
教学要求：1．了解库恩——塔克条件
2．掌握Zoutendijk可行方向法以及Topkis-Veinott修正方法。了解下降可行方向
满足条件。了解广义既约梯度法（GRG算法）
3．了解化约束为无约束的惩罚法中最基本的两种方法：外罚函数法和内罚函数
法。了解这两种方法适用范围及其优缺点。针对两种方法不足而改进的乘子
法作一般的了解。
4．掌握复合形法基本思路及计算步骤 重点：惩罚法，工程中常用的复合形法 难点：方法定理的证明
3-8 非线性规划问题的线性化
（6学时）
一． 用线性逼近法求解线性约束条件下的非线性规划（Frank-Wolfe方法） 二． 用线性逼近法求解非线性约束条件下的非线性规划（近似规划法，即MAP法）
三． 变量分割法 四． 可分规划法
教学要求：1．掌握几种方法适用范围及特点
2．掌握非线性规划如何线性化
3．掌握各种方法求解过程 重点：近似规划法（MAP法）
3-9 应用举例
（2学时）
了解水资源规划中非线性规划如何作线性化求解
第四章 动态规划
（共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．了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分
配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商
问题等
6．了解多维动态规划降维方法和减少离散状态点数方法 7．了解随机性问题的动态规划求解方法
重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧；离散微分动
态规划法
难点：最优性定理的证明，随机性问题的动态规划
（3）使用说明
每讲完一种方法，至少布置一道作业，作为基本训练、巩固和加深对方法的基本原理，算法的步骤的理解。
计划讲授两次习题课，介绍难懂和技巧性强或教材没有详细提到的问题。
每讲完一章，结合资源与环境专业的实际，介绍方法的应用。
每讲完一章，作个小结，并介绍新方法，发展动向，以及教材还没有涉及到的内容。
在时间和条件许可下，可适当选择一些方法的计算程序作介绍，学生自己上机实习。
按学时的多少，适当增减内容。
（4）主要参考书目
钱颂迪主编， 《运筹学》（增订版），
清华大学出版社， 1990年 管梅谷、郑汉鼎， 《线性规划》， 山东科学技术出版社， 1983 张建中、许绍吉著， 《线性规划》， 科学出版社， 1990 魏国华、王芬编著， 《线性规划》， 高等教育出版社， 1989 陈开明编著， 《非线性规划》， 复旦大学出版社， 1991 袁亚湘、孙文瑜编著， 《最优化理论与方法》， 科学出版社， 1999 韦鹤平编著， 《最优化技术应用》， 同济大学出版社， 1987 张莹编著， 《运筹学》， 清华大学出版社， 1994 周学勤等编著， 《数学规划及其应用》， 中山大学出版社， 1991 胡运权主编， 《运筹学习题集》， 清华大学出版社， 1995
