《最优化技术》课程教学大纲

1、最优化技术课程教学大纲、课程基本信息开课单位课程类别专业核心课程名称最优化技术（Methods of Optimization课程编码开课对象信息与计算科学专业开课学期6学时/学分总64学时、理论课 52学时、实验课12学时/4学分先修课程数学分析，解析几何，高等代数，概率论与数理统计，常微分方程课程简介：本课程主要讲授线性规划、非线性规划、多目标规划、现代优化算法等的基本模型、方 法和应用。本课程是信息与计算科学专业的专业核心课，是培养数学建模能力的核心理论基 础之一。通过学习，使学生掌握最优化方法的基本概念和基本理论，使学生掌握整体优化的 基本思想，培养学生的逻辑思维能力和创新素质，培养应

2、用最优化方法解决实际问题的能力， 熟练掌握最优化方法的程序设计方法，培养学生运用模型和算法并借助计算机手段解决实际 问题的能力。二、课程教学目标本课程是信息与计算科学专业的专业核心课，是培养数学建模能力的核心理论基础之一。通过学习，使学生掌握最优化方法的基本概念和基本理论，使学生掌握整体优化的基本思想，培养学生的逻辑思维能力和创新素质，培养应用最优化方法解决实际问题的能力，练掌握最优化方法的程序设计方法，培养学生运用模型和算法并借助计算机手段解决实际问 题的能力。1 .掌握整体优化的基本思想，具有应用最优化方法解决实际问题的能力；2 .掌握最优化方法的程序设计方法；3 .掌握建立数学模型的基本

3、方法和应用计算机解决实际问题的能力；、教学学时分配最优化技术课程理论教学学时分配表章次主要内容学时分配教学方法或手段A章线性规划10讲授法、讨论法、案例教学第F对偶理论8讲授法、讨论法、案例教学第三章整数规划8讲授法、讨论法、案例教学第四章非线性规划10讲授法、讨论法、案例教学第五章图论8讲授法、讨论法、案例教学用八早智能优化算法简介8讲授法、讨论法、案例教学合计52夫 . . . . . . . .理论学时包括讨论、习题课等学时。最优化技术课程实验内容设置与教学要求一览表序号实验项目名称实验内容教学要求学时分配实验类别实验类型每组人数熟练掌握单纯形利用Matlab软件法的基本原理；掌必设1单

4、纯形程序设计编写通用的单纯握Matlab软件编2做计1形法程序性程的基本技巧和方法；编写出通用的单纯形法程序.2用Lingo解决线性规划问题利用Lingo求解线性规划问题，并进行灵敏度分析掌握Lingo解线性规划的基本方法；掌握 Lingo进行灵敏度分析 的方法.2必做验证性13用Lingo解整数规划问题利用Lingo解一般整数规划问题和指派问题掌握整数规划问题白L Lingo表述方法和编程技巧；会利用Lingo解一般整数规划问 题和指派问题.2必做综合性14无约束非线性规划问题的 Matlab程序实现利用Matlab编写无约束非线性规划问题的程序掌握 Matlab软件编程的基本技巧和方法；熟

5、练掌握 黄金分割法、牛顿 法等基本迭代算法的算法原理；编写出通用的黄金分割法或牛顿法的Matlab通用程序.2必做设计性15最短路问题程序设计利用Matlab软件 编写Floyd算法 或Dijkstra 算法的通用程序熟练掌握最短路算法的基本原理；掌握 Matlab软件编程的基本技巧和方法；编写出通用的Floyd算法2必做设计性1或Dijkstra 算法程序6智能优化算法设计利用Matlab软件编写遗传算法或模拟退火算法的撑血熟练掌握相关智能优化算法的基 本原理；掌握Matlab软件编程 的基本技巧和方 法；编写出实用的 遗传算法或模拟 退火算法算法程 序2必做设计性1四、教学内容和教学要求第

6、一章线性规划（10学时）（一）教学要求通过本章内容的学习， 了解线性规划模型的基本特征、 基本概念及基本理论； 理解单纯 形法的基本思想方法； 掌握单纯形法的基本步骤， 并能利用单纯形法求解线性规划问题； 理 解人工变量法和两阶段法的基本思想。（二）教学重点与难点教学重点：单纯形法的基本步骤教学难点：单纯形法的基本思想（三）教学内容第一节线性规划问题及其数学模型1 .线性规划问题的数学模型；2 .线性规划问题的标准形式。第二节图解法1 .图解法的步骤；2 .线性规划问题求解的几种可能结局；3.由图解法得到的启示。第三节 单纯形法原理1线性规划问题的解的概念；2单纯形法的迭代原理。第四节 单纯形

7、法计算步骤1单纯形法的步骤；2单纯形法求解举例。第五节 单纯形法的进一步讨论1人工变量法（大M 法）；2两阶段法。第六节 应用举例1生产计划问题；2混合配料问题。本章习题要点：1. 线性规划化为标准形式；2. 利用图解法求两个变量的线性规划问题；3. 利用单纯形法求解线性规划问题；4. 利用人工变量法或两阶段法求解线性规划问题；5. 建立实际问题的线性规划模型。第二章 对偶理论（ 8 学时）（一）教学要求通过本章内容的学习，掌握原 - 对偶问题的关系；理解对偶问题的基本性质；理解单纯形法计算的矩阵描述； 掌握对偶单纯形法的计算步骤； 掌握线性规划问题灵敏度分析的基本方法。（二）教学重点与难点教

8、学重点：对偶单纯形法的计算步骤，线性规划问题的灵敏度分析方法教学难点：单纯形法计算的矩阵描述，灵敏度分析（三）教学内容第一节 线性规划问题的对偶问题1对称形式下对偶问题的一般形式；2非对称形式的原- 对偶问题的关系。第二节 对偶问题的基本性质1单纯形法计算的矩阵描述；2对偶问题的基本性质。第三节 对偶单纯形法1对偶单纯形法的基本思路；2对偶单纯形法的计算步骤。第四节 灵敏度分析1灵敏度分析的步骤；2几种不同情况的灵敏度分析。本章习题要点：6. 写出线性规划问题的对偶问题；7. 利用对偶问题的基本性质解决线性规划问题；8. 利用对偶单纯形法求解线性规划问题；9. 对线性规划问题进行灵敏度分析。第

9、三章 整数规划（ 8 学时）（一）教学要求通过本章内容的学习， 了解整数规划的分类及解的特点； 掌握整数规划的基本解法分支定界法和割平面法；掌握0-1 型整数规划的解法；掌握求解指派问题的匈牙利算法。（二）教学重点与难点教学重点：分支定界法，割平面法和匈牙利算法教学难点：割平面法（三）教学内容第一节 整数规划的数学模型及解的特点1整数规划问题的分类；2整数线性规划问题解的特点。第二节 解纯整数规划的割平面法1割平面法的原理；2割平面法的基本步骤。第三节 分支定界法1分支定界法的基本思想；2分支定界法的基本步骤。第四节0-1 型整数规划10. 0-1 变量及其应用；11. 0-1 型整数规划问题

10、的解法。第五节 指派问题1指派问题的标准形式及其数学模型；2匈牙利算法。本章习题要点：12. 利用割平面法求解整数规划问题；13. 利用分支定界法求解整数规划问题；14. 利用 0-1 变量建立实际问题的数学模型；15. 利用匈牙利算法解指派问题。第四章 非线性规划（ 10 学时）（一）教学要求通过本章内容的学习， 了解无约束非线性规划的最优性条件； 掌握凸函数及其性质； 了解凸规划及其性质；掌握常见的一维搜索方法（ 0.618 法和牛顿法）；掌握无约束问题的最优性条件；了解约束优化问题的最优性条件。（二）教学重点与难点教学重点：凸函数及其性质，一维搜索方法（ 0.618 法和牛顿法）教学难点

11、：约束优化问题的最优性条件（三）教学内容第一节 基本概念1非线性规划问题；2非线性规划方法概述。第二节 凸函数和凸规划1凸函数及其性质；2凸规划及其性质。第三节 一维搜索方法1 0.618 法（黄金分割法）；2牛顿法；3. 非精确一维搜索方法。第四节 无约束最优化方法1无约束问题的最优性条件；2最速下降法；4. 共轭方向法。第五节 约束最优化方法1约束最优化问题的最优性条件；2简约梯度法；3. 惩罚函数法。本章习题要点：1. 判别函数的凸性；2. 判别凸规划问题；3. 利用一维搜索方法求解无约束优化问题；4. 利用无约束优化问题的最优性条件判别解的最优性。第五章 图论（ 8 学时）（一）教学要

12、求通过本章内容的学习， 了解图与网络的基本概念； 掌握图的生成树及最小生成树的算法；掌握最短路问题的基本算法（ Dijkstra 算法和 Floyd 算法）；掌握最大流问题的求解方法。（二）教学重点与难点教学重点：最小生成树算法，最短路问题的相关算法教学难点：可行流，最大流- 最小割定理（三）教学内容第一节 图与网络的基本知识1图与网络的基本概念；2图的矩阵表示。第二节 树1树的概念和性质；2图的生成树；3. 最小生成树问题。第三节 最短路问题1 Dijkstra 算法；2 Floyd 算法。第四节 最大流问题1最大流问题有关概念；2最大流- 最小割定理；3 求最大流的标号算法。本章习题要点：

13、1. 求图的最小生成树；2. 利用 Dijkstra 算法或 Floyd 算法求图上两点的最短路；3. 利用矩阵表示图或网络；4. 利用标号算法求网络的最大流。第六章 智能优化算法简介（ 8 学时）（一）教学要求通过本章内容的学习， 了解智能优化算法的发展现状； 理解遗传算法的设计思路； 理解神经网络学习算法的设计思路。（二）教学重点与难点教学重点：遗传算法，神经网络学习算法教学难点：遗传算法，神经网络学习算法（三）教学内容第一节 遗传算法1遗传算法基本原理；2模板理论；3. 遗传算法的改进。第二节 神经网络学习算法1神经网络学习算法的基本原理；2. BP神经网络模型。第三节 应用举例本章习题

14、要点：1. 利用遗传算法求解实际问题；2. 利用神经网络学习算法求解实际问题。五、教学方法或手段1、教学方法方面，主要采用讲授法、启发式、案例式、网上助学式等方法。逐步采用课堂讲授与网络 MOOC1结合的教学方法，多角度、多方式教学。2、教学手段方面，采用多媒体教学为主、网络MOOC!频教学为辅的手段。逐步推动本课程的网络 MOOC!频教学建设。六、考核方式及评价要求本课程考核方式及评价要求如下：1. 平时成绩15%：理论课课堂考勤、课堂练习完成情况，课堂笔记等；2. 实验成绩15%：实验课课堂考勤，实验项目完成情况，实验报告撰写；3. 期中考试20%：学期中间将安排一次期中测验，闭卷（考查前四章）；4. 期末考试50%：综合考查本课程的理论教学内容。七、教材及教学主要参考书推荐教材：运筹学教程，胡运权主编，清华大学出版社， 2012 年 11 月第 4 版。最优化方法，孙文瑜主编，高等教育出版社， 20