Computer Knowledge and Technology
电脑知识与技术
第 10 卷第 4 期 (2014 年 2 月)
软件设计开发
本栏目责任编辑:谢媛媛
基于 LINGO 的优化问题动态规划法求解
度巍,曾飞
(南通大学 交通学院,江苏 南通 226019)
摘要:介绍了 LINGO 优化软件的使用,指出 LINGO 在求解动态规划问题时可以不需要目标函数。基于 LINGO 分别对最
短路问题和生产批量计划问题使用动态规划法进行了求解,给出了相应的 LINGO 求解代码,增强了学生对动态规划法的
理解同时提高了使用优化软件编程解决问题的能力。
关键词:LINGO;动态规划;最短路问题;生产批量计划问题
中图分类号:G642 文献标识码:A 文章编号:1009-3044(2014)04-0743-04
Solving Optimization Problem by Dynamic Programming Method Using LINGO
DU Wei, ZENG Fei
(School of Transportation Nantong University, Nantong 226019, China)
Abstract: The paper describes the use of LINGO,pointing outing that LINGO can solve dynamic programming problems with⁃
out the objective function。The shortest path problem and lotsizing problem are solved by dynamic programming method, Cor⁃
responding LINGO codes are provided. The teaching of LINGO enhances the students' understanding of the dynamic program⁃
ming while increasing the ability to use optimization software programming to solve the problem.
Key words: LINGO;dynamic programming;shortest path problem;lotsizing problem
在交通专业课程如《交通运筹学》、《交通系统分析方法》等的教学过程中,大量涉及到可划分为多阶段的优化问题求解,这些
问题的求解一般使用动态规划(dynamic programming)方法。动态规划将决策问题的全过程划分为若干个相互联系的子过程(每个
子过程为一个阶段),然后按照一定的次序来求解。当划分的阶段个数较多时,手工求解动态规划问题相当麻烦。由于在实际的
交通工程规划实践中,涉及到的动态规划优化问题规模往往较大,指导学生掌握相应的优化软件求解动态规划问题一方面能增进
学生对动态规划法的理解掌握,另一方面能锻炼学生的编程能力,是一项十分有意义的教学工作。
美国 LINDO系统公司开发的 LINGO 由其求解问题的高效性和稳定性,成为目前广泛使用的优化软件。LINGO 是一套专门用
于求解最优化问题的软件包,其内置了一种建立最优化模型的的语言,可以简便表达出问题,同时利用 LINGO 高效的求解器可快
速求解并分析结果。LINGO 在处理含有大量变量和约束条件的优化问题时,一般使用数组和矩阵的输入方法:LINGO程序首先定
义集合段,确定需要的集合及其属性,然后定义数据段,用于输入已知原始数据,最后使用函数对集合进行操作。在通常介绍 LIN⁃
GO 使用的文献中[1][2],一般着重于叙述其如何求解线性规划和非线性规划等具有明确目标函数的优化问题,很少关注如何用
LINGO 求解复杂的动态规划问题,该文通过分析交通运输中常见的最短路问题和生产批量计划问题,给出用动态规划方法求解的
LINGO代码,指出 LINGO 可以在不需要目标函数的情况同样很好地求解多阶段优化问题。
1 动态规划法求解实例
实例 1 最短路问题
在纵横交错的公路网中(图 1 所示),货车司机希望找到一条从一个城市到另一个城市的最短路。图中节点 1—8 代表货车可
以停靠的城市,弧旁的数字表示两个城市之间的距离(百公里)。若货车要从城市1出发到达城市 8,问如何选择行驶路线使所经过
的路程最短。
问题分析:该最短路问题满足动态规划的最优性原理,即“从节点 1 到节点 8 的最短路的子路径仍然是相应节点间的最短路”,
用
D(i,j)
表示从节点
i
和
j
有弧相连时相应的距离,
L(i)
表示从节点 1 到节点 i 的最短路程数。则不难得到以下的动态规划由前向
后递推方程:
ì
í
î
L( j) = min
i
{L(i) + D(i,j)},j = 2,⋯,8
L(1) = 0
(1)
收稿日期:2013-12-23
基金项目:南通大学校级教学改革课题(2013B119、2013B037);中国交通教育研究会教育科学研究课题(交教研 1202-171);江苏省
现代教育技术研究课题(2013-R-25411、2011-R-19039)
作者简介:度巍(1982-),男,南通大学交通学院讲师,博士,从事交通系统工程方面的研究。
E-mail: xsjl@dnzs.net.cn
http://www.dnzs.net.cn
Tel:+86-551-65690963 65690964
ISSN 1009-3044
Computer Knowledge and Technology
电脑知识与技术
Vol.10, No.4, February 2014
743
评论0