运筹学建模与算法2021

1. 课程信息

Location:三教3304

Time: Friday, 14:00-16:30

Teacher:Yongcai Wang

Office:Wing building of Science and Technology, 105A

Email:ycw@ruc.edu.cn


2. 评分标准

平时作业,占总成绩的30%

课程实验,占总成绩20%

期中考试,占总成绩20%

课程论文,占总成绩的30%。


3. 内容简介

课程目的:

课程侧重于优化问题的建模与算法设计,希望学生通过学习本课程,掌握运筹学的基础知识,理解算法和原理,掌握算法的基本步骤,尤其要掌握优化的思想,能够根据实际问题建立运筹学模型,并应用算法进行求解。

课程简介:

运筹学,又称为operations research,是优化与决策方面的一门重要学科。 课程主要向学生系统地讲授规划论、网络分析与网络计划、存储论、排队论、决策论、对策论等运筹学方法模型,包括模型条件、结构特点、基本方法步骤及应用范围等;使学生认识优化方法、运筹方法在经济、金融、计算机网络、经营管理等学科决策中的作用。课程侧重于优化问题的建模与算法设计,希望学生通过学习本课程,掌握运筹学的基础知识,理解算法和原理,掌握算法的基本步骤,尤其要掌握优化的思想,能够根据实际问题建立运筹学模型,并应用算法进行求解。


4. 教学安排

教学周
章节名称
教学内容与教学要求
课外学习内容与要求
第1周

运筹学概论

运筹学与计算机与人工智能的关系,建模方法

作业练习几个建模问题

第2周

线性规划与单纯型法

线性规划的理论与算法推导

线性规划随堂作业

第3周

线性规划与单纯型法

单纯形法的详细介绍

单纯形法随堂作业

第4周

对偶理论与灵敏度分析基础

对偶理论、对偶定理

对偶理论随堂作业

第5周

对偶理论与灵敏度分析算法与应用

对偶单纯形法,灵敏度分析

灵敏度分析随堂作业,单纯形法实验

第6周

优化问题基础,模型与约束

求解约束优化的方法

约束优化随堂作业

第7周

目标规划,整数规划建模

整数规划的建模与目标规划方法

整数规划随堂作业

第8周

整数规划求解方法、求解工具,应用

分枝定界法、割平面法

分枝定界法随堂作业,分枝定界法实验

第9周

非线性规划的基础与方法

非线性规划最优解存在条件,KT定理等

非线性规划随堂作业

第10周

非线性规划算法与应用

牛顿法、随机梯度下降、ADAM算法

非线性规划算法实验

第11周

动态规划理论与方法

Bellman方程,动态规划建模方法

动态规划随堂作业

第12周

动态规划的算法与应用

前向迭代,后向迭代,动态规划求解算法

最短路、最大流算法实验

第13周

网络优化理网络优化理论与方法及应用

网络、图的基本理论模型,最短路算法

最短路课堂作业

第14周

网络优化理论与方法及应用

最大流,最小费用流,最小费用最大流算法

最小费用最大流课堂作业

第15周

博弈论

矩阵博弈论建模与线性规划求解算法

矩阵博弈论随堂作业

第16周

随堂论文报告

进行课堂报告

 


5. 参考书目

1. Introduction to Operations Research, Ecker,Joseph G & Ku… 著
2. 《运筹学教程》,第四版,胡运权主编,清华大学出版社
3. 《运筹学习题集》,第四版,胡运权主编,清华大学出版社
4. 《运筹学》,Ronald L. Rardin,肖勇波等译,机械工业出版社


6. 课程实验

课程5,8,10,12周,共有四次实验课:
1)手写单纯形法:深入理解用矩阵操作实现的单纯形法。
2)手写分枝定界法:实现分枝定界法,主要调用单纯形法进行整数规划的求解。
3)非线性规划实验:梯度下降,随机梯度下降,牛顿法,AdaGrad, ADAM等机器学习深度学习的基础算法的深入理解与设计实现。
4)网络算法实验:设计和实现网络K最短路算法,最大流算法,以及在K-disjoint path中的应用。


7. 课程论文

1. 课程论文选题

2. 课程论文报告打分表Score Metrics