基于LINGO的优化问题动态规划法求解

摘要：介绍了LINGO优化软件的使用，指出LINGO在求解动态规划问题时可以不需要目标函数。基于LINGO分别对最短路问题和生产批量计划问题使用动态规划法进行了求解，给出了相应的LINGO求解代码，增强了学生对动态规划法的理解同时提高了使用优化软件编程解决问题的能力。

关键词：LINGO；动态规划； 最短路问题； 生产批量计划问题

中图分类号：G642 文献标识码：A 文章编号：1009-3044（2014）04-0743-04

在交通专业课程如《交通运筹学》、《交通系统分析方法》等的教学过程中，大量涉及到可划分为多阶段的优化问题求解，这些问题的求解一般使用动态规划（dynamic programming）方法。动态规划将决策问题的全过程划分为若干个相互联系的子过程（每个子过程为一个阶段），然后按照一定的次序来求解。当划分的阶段个数较多时，手工求解动态规划问题相当麻烦。由于在实际的交通工程规划实践中，涉及到的动态规划优化问题规模往往较大，指导学生掌握相应的优化软件求解动态规划问题一方面能增进学生对动态规划法的理解掌握，另一方面能锻炼学生的编程能力，是一项十分有意义的教学工作。

美国LINDO系统公司开发的LINGO由其求解问题的高效性和稳定性，成为目前广泛使用的优化软件。LINGO是一套专门用于求解最优化问题的软件包，其内置了一种建立最优化模型的的语言，可以简便表达出问题，同时利用LINGO高效的求解器可快速求解并分析结果。LINGO在处理含有大量变量和约束条件的优化问题时，一般使用数组和矩阵的输入方法：LINGO程序首先定义集合段，确定需要的集合及其属性，然后定义数据段，用于输入已知原始数据，最后使用函数对集合进行操作。在通常介绍LINGO使用的文献中[1][2]，一般着重于叙述其如何求解线性规划和非线性规划等具有明确目标函数的优化问题，很少关注如何用LINGO求解复杂的动态规划问题，该文通过分析交通运输中常见的最短路问题和生产批量计划问题，给出用动态规划方法求解的LINGO代码，指出LINGO可以在不需要目标函数的情况同样很好地求解多阶段优化问题。

1 动态规划法求解实例

实例1 最短路问题

在纵横交错的公路网中（图1所示），货车司机希望找到一条从一个城市到另一个城市的最短路。图中节点1—8代表货车可以停靠的城市，弧旁的数字表示两个城市之间的距离（百公里）。若货车要从城市1出发到达城市8，问如何选择行驶路线使所经过的路程最短。

问题分析：该最短路问题满足动态规划的最优性原理，即“从节点1到节点8的最短路的子路径仍然是相应节点间的最短路”，用[D（i，j）]表示从节点[i]和[j]有弧相连时相应的距离，[L（i）]表示从节点1到节点i的最短路程数。则不难得到以下的动态规划由前向后递推方程：

根据式（1），再进一步定义当节点[i]在从节点1到节点[j]的最短路径上时，[P（i，j）=1]，否则[P（i，j）=0]，编写如下LINGO求解代码：

运行LINGO得到如图1所示的最优解报告。

从报告中可以看到，最短路径找到，由[L（8）]的值可以得出，从城市1到城市8的最短路程数为14，由各个[P（i，j）]的值分析可知，从城市1到城市8的最短路线为[1→2→5→8]。

实例2（生产批量计划问题）

某企业生产某种产品用以满足市场需求。通过统计，该产品今后[T]4周的外部需求（订货量）分别是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要开工生产，则第[t]周开工所需的生产准备费为[st]千元（与生产的数量无关），每件产品的生产费为[ct]千元。如果在满足需求后周末有产品剩余，每千件产品的存储费为[ht]千元。设第[t]周末的库存量为[It]，假设开始没有库存，记为[I0=0]且不考虑生产能力限制，问工厂应如何安排生产，在按时满足需求的条件下，使总费用最小？

问题分析：对于生产批量计划问题，分析可知有如下两条性质成立：

由于以上两个性质，只有当上一时段库存[It-1=0]时，本时段才考虑进行生产，且一旦生产，其生产量一定为某些后续时段需求量的总和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。这样如用[ft]表示当[t]时段初始库存为0时，从[t]时段到[T]时段的子问题的最优费用值，可以建立如下的递推关系：

运行LINGO得到如下最优解报告：

从报告可以看到，[F（1）=561]，即从第1周到第4周末的最优费用为561（千元），分析其它[F]值得到，最优的生产批量计划为第1周生产2（千件），第2周生产5（千件），第3周不生产，第4周生产4（千件）。

2 结束语

本文针对用动态规划方法手工求解多阶段优化决策问题十分繁琐的特点，利用LINGO软件将各个动态规划递推方程简洁明确地编程实现，帮助学生更好的理解了各阶段决策变量之间相互递进的关系，同时更重要的是交通专业学生熟练地掌握了软件的使用，才能解决实际工程规划中的大规模复杂优化问题，LINGO软件的教学实践促进了《交通运筹学》、《交通系统分析方法》与《交通规划》等课程的融合。

参考文献：

[1] 李晓川，朱晓敏，赵乃东. 基于Lingo的运输优化系统设计与开发[J]. 物流技术，2010（Z1）.

[2] 洪文，朱云鹃. 利用LINGO建立最优化模型[C].第六届（2011）中国管理学年会——管理科学与工程分会场，2011.

[3] 姜启源，谢金星，邢文训，等.大学数学实验[M].北京：清华大学出版社，2005.

推荐访问： 求解 优化 规划 动态 LINGO

---