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

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

为全面提高应用型、创新性人才培养质量，本文对最优化方 法实践教学现状进行分析，阐述实践教学的重要性和案例教 学的可行性，通过一个教学案例的实施过程探索改革实践教 学内容和教学方法。

1最优化方法实践课程教学的重要性 最优化方法是一门理论性和实用性很强的专业课程，它 研究如何在所有可行方案中搜索出最优方案[1,2]。该课程 中所涉及到的优化方法在诸多领域中得到了广泛的应用[3]。

所以，不仅限于数学专业，其它以培养应用型人才为目标的 工程技术和管理专业开设该课程，使学生掌握优化思想和对 实际工程问题进行优化处理的能力，也是其需要具备的基本 素质。

实践教学是能够让学生从工程的角度理解优化思想的 重要环节。实践教学不但能加深对所学理论知识的理解，而 且能提高理论联系实际，解决工程问题的能力。另外，通过 实践教学，用现代化技术手段将优化理论和问题解决一同展 示，对提高学生学习兴趣和积极性无疑是有帮助的。实践教 学要求学生熟练掌握一门高级语言，然而，语言是其面临的 一大难题，这也正说明了实践课程教学的重要性。面对解决工程中的优化问题，需要首先将现实问题模型 化，这一点能够培养学生自主分析问题和将优化问题转化为 数学模型的能力。所以，筛选合适的案例是实践教学的首要 任务。为了让实践教学发挥出更好的效果，案例要突出较强 的实战性，同时，要紧密结合所学优化方法。另外，案例要 兼顾难易度适中，并具有挑战性，还要具有互动性，这样才 能激发学生学习探索的积极性。

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的配送成本（距离、费用或时间）。

求满足需求的成本最小的车辆行驶路径。2.2有时间窗的车辆路径问题描述与模型 如果在上述车辆路径问题中，增加一种约束，即完成需 求点i的货物配送必须在时间窗口[ETi,LTi]需完成，且需要 的时间为Ti，其中ETi表示为需求点i配送的最早开始时间， LTi表示为需求点i配送的最迟开始时间。如果车辆到达需求 点i的时间早于ETi，则车辆需要等待，增加了时间成本；
如 果晚于LTi到达，则需支付一定的罚金，增加了配送成本。

那么，这种考虑了配送时间约束的车辆路径问题为具有时间 窗的车辆路径问题(Vehicle Routing Problem with Time Windows，VRPTW)。

以ti表示车辆到达第i个需求点的时间，pE表示提前到 达的单位时间等待成本，pL表示延迟到达的单位时间惩罚成 本，则具有时间窗约束的车辆路径问题模型中目标函数为 3教学分析 在最优化方法理论教学内容中，我们补充学习了现代优 化算法（粒子群算法，遗传算法），并且熟悉了这两种算法 的用于求解无约束优化问题的软件操作和编程实现。然后， 提出车辆路径问题，作为单独的上机实验环节要求用粒子群 算法进行解决。具体操作如下：
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.