陈照辉，唐利明，任泽民

(1.重庆科技学院 数理学院，重庆 401331；2.湖北民族学院 理学院，湖北 恩施 445000)



最优化方法实践课程教学的一个案例

陈照辉1，唐利明2，任泽民1

(1.重庆科技学院 数理学院，重庆 401331；2.湖北民族学院 理学院，湖北 恩施 445000)

最优化方法课程具有较强的实用性，对该课程实践教学现状进行了分析，阐述了实践教学的必要性，提出案例教学的重要性和可行性。通过一个实践教学实例分析案例教学，说明独立设置上机实验，通过老师指导，以学生为主体的案例教学，能有效发挥学生学习的主观能动性。

最优化方法，案例教学，实践课程，应用型

最优化方法作为应用数学专业一门核心专业课程，具有较强的理论性和实用性。该课程的实践教学环节对培养大学生运用数学知识解决实际问题的能力起着十分重要的作用。为全面提高应用型、创新性人才培养质量，本文对最优化方法实践教学现状进行分析，阐述实践教学的重要性和案例教学的可行性，通过一个教学案例的实施过程探索改革实践教学内容和教学方法。

1 最优化方法实践课程教学的重要性

最优化方法是一门理论性和实用性很强的专业课程，它研究如何在所有可行方案中搜索出最优方案[1,2]。该课程中所涉及到的优化方法在诸多领域中得到了广泛的应用[3]。所以，不仅限于数学专业，其它以培养应用型人才为目标的工程技术和管理专业开设该课程，使学生掌握优化思想和对实际工程问题进行优化处理的能力，也是其需要具备的基本素质。

目前国内在最优化方法教学中，较注重一些经典的优化算法学习，在实践教学中也是算法验证性实验。但是，近些年随着科技的进步，实际工程中遇到的优化问题也越来越复杂，随之最优化方法也得到了迅速的发展，应用也越发灵活，课本中所列的经典优化方法已不能满足工程需要。现代优化算法如遗传算法、模拟退火法、粒子群算法、蚁群算法等发展已较为成熟，也在很多工程领域中得到了广泛的应用[4]。 但是，大多最优化方法教材并未列写这些相关内容，在实际教学中也很少涉及，一般在研究生课程中才会有所体现。为了顺应应用型人才培养目标，作者认为应在教学过程中适当补充一些现代优化方法的学习，侧重在实践教学中使学生掌握算法的应用方法和软件的使用。

实践教学是能够让学生从工程的角度理解优化思想的重要环节。实践教学不但能加深对所学理论知识的理解，而且能提高理论联系实际，解决工程问题的能力。另外，通过实践教学，用现代化技术手段将优化理论和问题解决一同展示，对提高学生学习兴趣和积极性无疑是有帮助的。实践教学要求学生熟练掌握一门高级语言，然而，语言是其面临的一大难题，这也正说明了实践课程教学的重要性。

面对解决工程中的优化问题，需要首先将现实问题模型化，这一点能够培养学生自主分析问题和将优化问题转化为数学模型的能力。所以，筛选合适的案例是实践教学的首要任务。为了让实践教学发挥出更好的效果，案例要突出较强的实战性，同时，要紧密结合所学优化方法。另外，案例要兼顾难易度适中，并具有挑战性，还要具有互动性，这样才能激发学生学习探索的积极性。

2 一个实践教学案例

车辆路径问题(Vehicle Routing Problem，VRP)是由Dantzig和 Ramser于1959年首次提出的，属于完全NP问题，该问题在最优化、物流管理、计算机等领域中得到了广泛的关注和研究[5]。该问题背景清晰、易懂且具有针对性和实战性，所以，在最优化方法实践教学过程中选择该问题作为一个案例。

2.1 车辆路径问题描述与模型

一般地，车辆路径问题可描述为：对一系列发货点或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件下，达到一定的目标。例如，有一个中心仓库，拥有K辆车，第k辆车的最大载重量或容量记为qk(k=1,2,…,K)，负责向L个需求点配送货物，第i个需求点的货物需求量为gi(i=1,2,…,L)，且maxgi≤maxqk；cij表示车辆从需求点i到需求点j的配送成本(距离、费用或时间)。求满足需求的成本最小的车辆行驶路径。

(1)

2.2 有时间窗的车辆路径问题描述与模型

如果在上述车辆路径问题中，增加一种约束，即完成需求点i的货物配送必须在时间窗口[ETi,LTi]需完成，且需要的时间为Ti，其中ETi表示为需求点i配送的最早开始时间，LTi表示为需求点i配送的最迟开始时间。如果车辆到达需求点i的时间早于ETi，则车辆需要等待，增加了时间成本；如果晚于LTi到达，则需支付一定的罚金，增加了配送成本。那么，这种考虑了配送时间约束的车辆路径问题为具有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows，VRPTW)。

以ti表示车辆到达第i个需求点的时间，pE表示提前到达的单位时间等待成本，pL表示延迟到达的单位时间惩罚成本，则具有时间窗约束的车辆路径问题模型中目标函数为

(2)

约束条件与(1)相同。从模型(1)(2)易知，当ETi=0，LTi→∞时，(2)等价于(1)。

3 教学分析

在最优化方法理论教学内容中，我们补充学习了现代优化算法(粒子群算法，遗传算法)，并且熟悉了这两种算法的用于求解无约束优化问题的软件操作和编程实现。然后，提出车辆路径问题，作为单独的上机实验环节要求用粒子群算法进行解决。具体操作如下：

a. 编码

b. 构造适应值函数

(3)

其中M是充分大的数。显然，(3)中令pE=0,pL=0便是VRP的适应值函数，其完全可用Lingo解决。

c. 算法步骤

第1步：初始化参数K,L,N,w,c1,c2,M，最大迭代次数Nmax，粒子群Xi=(xi1,xi2,…,xi,K+L-1)和初始速度Vi=(vi1,vi2,…,vi,K+L-1)，i=1, 2, …,N，其中-1≤xij≤1；

第2步：按照a中的编码方法将Xi映射到Yi∈B,i=1, 2, … ,N；

第3步：根据(3)计算Yi点的适应值；

第4步：根据Yi的适应值，修改个体最优Pi和全局最优Pg；

第5步： 根据粒子群算法迭代式更新粒子的位置；

第6步：判断终止条件是否满足，是，停止迭代并输出Pg；否，返回到第2步。

解决该问题具有挑战性，首先需要编码，这一步能加深学生了解相应算法；然后需要构造适应值函数，这一步能促使学生深入了解罚函数法处理约束条件；最后需要按照算法的步骤构建解决VRPTW的算法，这一步骤能够使得学生进一步深入熟悉算法的结构和在组合优化问题中的使用方法。

在教学过程中，有的学生利用Lingo 软件解决了VRP，在解决VRPTW中遇到了困难。大多数同学能够在实验中通过团队协作，完成基本粒子群算法程序的修改，从而成功解决该问题。

4 结语

最优化方法课程中应用案例进行教学，取得非常好的效果。以学生为主体，通过对问题分析、建模、解决实现的过程，进行了师生间的互动。在老师的引导下，使得学生充分发挥其主观能动性，不但能提高分析问题，建立模型，解决问题和编程的能力，而且能够充分发掘学生的创新潜能。本文首先分析最优化方法实践课程教学现状，说明实践教学在提高学生分析问题和解决问题能力中扮演重要角色，列举一个案例旨在阐述最优化方法实践课程教学的一个可操作方法。

[1] 袁亚湘，孙文瑜.最优化理论与方法[M].北京：科学出版社，1997.

[2] 郭科，陈聆，魏友华.最优化方法及其应用[M].北京：高等教育出版社，2007.

[3] 何坚勇.最优化方法[M].清华大学出版社，2007.

[4] 张火明，陆萍蓝，王强.“讲座式”教学方法在最优化方法课程教学中的实践与效果分析[J].技术监督教育学刊，2009(2):6-9.

[5] 李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践，2004(4):130-135.

(责任校对 谢宜辰)

10.13582/j.cnki.1674-5884.2016.11.011

20160628

重庆科技学院教改项目(201245)；湖北民族学院教学研究项目(2015JY008)

陈照辉(1980- )，男，河南周口人，副教授，博士，主要从事智能优化、系统稳定控制研究。

G642.0

A

1674-5884(2016)11-0034-03