基于拉格朗日松弛的运输调度问题求解毕业论文
2020-04-04 12:51:58
摘 要
随着人民生活水平的日益提升，人们对产品的多样化、个性化需求不断提高，市场需求逐渐由计划驱动型转变为顾客拉动型，定制化生产的生产方式逐渐成为主流，导致了市场对物流服务的精细化和复杂化要求也越来越高。因此，物流部门慢慢开始独立成为一个第三方专业组织，依靠其对客户的快速响应速度和专业的服务品质逐渐成为了货物流通环节中一股不可或缺的重要力量。
现如今，产品运输已经成为了一个由制造商、供应商以及第三方物流组织共同参与完成的活动。在这样的背景下，在整个供应链环境下生产与库存的衔接以及供需双方的关系都将制约着物流运输的服务质量。因此传统意义上的局部成本最优已经无法同时满足三方的利益诉求。所以如何协调运输商与制造商的资源，合理规划调整运输方案，更好更快的完成运输活动并且实现成本的最优，成为了越来越多人的关注的焦点。
运输问题是指在一定的约束条件下，把货物从供应点送到需求点，使目标函数值取得最优，提高整条运输链路的客户服务水平并降低配送成本的过程。运输问题是运筹学中的一类经典的网络流问题，由数学家希契科克1941年首次提出，后来经过大量学者不断的研究，目前已经发现了6种不同类型运输问题。运输问题属于一种比较复杂的线性规划问题，通常可以通过表上作业法或图上作业法进行解决，但缺点是需要花费大量时间进行计算。
本文将基于经典运输调度问题进行拓展延伸，提出一个单产品闭环产-销环境下多成本构成的运输问题。问题的解将通过次梯度法使原问题的上界和下界逐步迭代逼近求得，其中下界通过拉格朗日松弛算法计算求出，上界则通过启发式算法使下界可行化得到。同时，为了验证优化算法的可行性和和有效性，还设计了数值仿真实验，将算法所求解同软件所求解进行比较分析，总结得出算法目前存在的优缺点，并提出其未来的研究发展方向。
关键字：运输问题、拉格朗日松弛、次梯度法、启发式算法
Abstract
With the improvement of the people's living standards, the demand for diversification and individualization of products is increasing, the market demand is gradually changed from plan driven to customer driven, and the production mode of customized production gradually becomes the mainstream, which leads to the higher demand for the refinement and complexity of logistics services. Therefore, the logistics department is gradually becoming a third party professional organization, which has gradually become an indispensable force in the circulation of goods depending on its fast response to customers and the quality of professional service.
Nowadays, product transportation has become a joint activity involving manufacturers, suppliers and third party logistics organizations. Under such a background, the link between production and inventory and the relationship between supply and demand in the whole supply chain environment will restrict the service quality of logistics transportation. Therefore, the traditional local cost optimization has been unable to satisfy the interests of the three parties at the same time. So it has become the focus of more and more people how to coordinate the resources of the carriers and manufacturers, to plan and adjust the transportation plan reasonably, to complete the transportation activities better and faster and to achieve the best cost.
Transportation problem refers to the process of bringing the goods from the supply point to the point of demand, making the target function optimal, improving the customer service level of the whole transport link and reducing the cost of distribution under certain constraint conditions. Transportation problem is a classical network flow problem in operational research, which was first proposed by mathematician Hitchcock in 1941. After a large number of scholars continue to study it, 6 different types of transportation problems have been found. Transportation problem is a complex linear programming problem, which can usually be solved by table method or graph operation method, but the disadvantage is that it takes a lot of time to calculate.
In this paper, we extend the classical transportation scheduling problem and propose a multi cost transportation problem under single product closed loop production and marketing environment. The solution of the problem will be solved by the subgradient method. The lower bound is calculated by the Lagrange relaxation algorithm, and the upper bound is feasible by the heuristic algorithm. At the same time, in order to verify the feasibility and effectiveness of the optimization algorithm, a numerical simulation experiment is designed, and the solution of the algorithm is compared with the solution of the software. The advantages and disadvantages of the algorithm are summarized, and the future research and development direction is put forward.
KEYWORD：Transportation problem, Lagrangian relaxation, Subgradient method, Heuristic algorithm
目录
摘要 I
Abstract II
1 绪论 1
1.1 研究背景和意义 1
1.2 本文的主要研究内容 2
2 国内外研究综述 3
2.1 运输调度问题研究综述 3
2.2 拉格朗日松弛算法研究综述 4
2.3 启发式算法研究综述 6
3 运输问题描述与建模 7
3.1 相关理论 7
3.2 问题描述和模型假设 7
3.3 数学模型 8
4 算法设计 9
4.1 拉格朗日松弛算法求下界 9
4.2 启发式算法求上界 10
4.3 次梯度法迭代最优下界 11
4.4 优化软件求解 13
5 仿真实验与分析 13
5.1 仿真实验 14
5.2 仿真实验结果分析 16
6 总结与展望 17
6.1 全文总结 17
6.2 经济性与环保性分析 18
6.3 研究展望 19
致谢 20
参考文献 21
附件：Matlab程序代码 22
绪论
研究背景和意义
随着国民经济的进一步发展，人民对生活质量的要求也在不断提高。因此，产品生产逐渐向多样化、定制化、个性化方向发展，市场需求逐渐由计划驱动型转变为顾客拉动型，因此定制化生产的生产方式逐渐成为主流，导致市场对物流服务的精细化和复杂化要求也越来越高，由此第三方物流应运而生。第三方物流是指不从属于供需双方中的任意一方，通过与供需双方的商业合作来提供以合同为约束的系列化、个性化、信息化的物流代理服务的专业组织。由于其专业、快捷的服务品质能够满足客户对响应时间的更高要求，目前第三方物流组织已逐渐成为货物运输中一股不可或缺的重要力量。
现如今，产品运输已经成为制造商、供应商以及第三方物流组织共同参与完成的活动，因此在整个供应链环境下生产与库存的衔接以及供需双方的关系都将制约着物流运输的服务质量。所以如何协调运输商与制造商的资源，合理规划调整运输方案，更好更快的完成运输活动并且实现成本的最优，成为了越来越多人的关注的焦点。
运输问题是指在一定的运输工具运载容量、运输时间、运输数量以及单位运输成本等条件限制下，把货物从供应点送到需求点，使整体的运输成本、车辆路径或出行时间取得最优的过程，运输问题的优化结果将最终影响着整条运输链路的客户服务水平和服务质量。运输问题是运筹学中的一类经典问题，也是著名的网络流问题之一，由数学家希契科克(Hitchcock)在1941年首次提出，后来经过大量学者不断的研究，目前已发现了6种不同类型的运输问题。运输问题有一般可以通过表上作业法或图上作业法进行解决，但通常比较复杂，需要花费大量的时间进行计算。
本文首先将依据目标运输问题，通过拉格朗日松弛算法松弛掉问题中的复杂约束，得出原问题的下界。但由于这个下界并不是问题的可行解，因此在其基础上设计了基于拉格朗日松弛算法的启发式算法，使这个下界可行化，得到了该问题的上界。最终通过次梯度法逐步迭代得到问题的最优下界，即为该问题的最优解。为了验证该算法求解运输问题的可行性、有效性及其优化质量，还利用了Lingo优化软件求得了问题的最优解，同所求解进行了比较分析。
本文的主要研究内容
本文首先介绍了文中涉及的相关理论及其研究现状，描述了运输问题的定义并建立了相应的数学模型。本文将在经典运输问题的基础上进行拓展和延伸，提出并建立问题对应的数学模型，并运用拉格朗日松弛思想解决问题。拉格朗日松弛算法的主要步骤为：首先利用拉格朗日松弛算法求解该问题的下界，由于通常情况下，求得的下界不能够满足被松弛掉的约束，所以该下界并不是可行解。因此本文还设计了基于拉格朗日松弛的启发式算法，使拉格朗日松弛算法得到的下界可行化，得出该问题的上界。并在此二者基础上根据次梯度法迭代求解该问题的最优解，最终通过优化软件进行求解验证。
基于以上所提到的研究内容，本文后续的部分将会根据提出问题，分析问题，解决问题三步走的思路展开，即定义本文的研究内容，深入分析目标问题，建立对应数学模型，设计优化算法，设计数值实验并进行结果分析。具体的各部分章节内容如下：
第一章在对运输问题的定义和发展进行了详细分析的基础上，结合目前物流运输行业的发展现状提出了本文的研究背景、意义和内容。
第二章介绍了运输问题、拉格朗日松弛算法、启发式算法及其他与本文研究相关理论的国内外研究现状。
第三章将对运输调度问题进行描述和建模。这一章中将介绍与本文研究相关的物流基础理论和术语，同时描述了问题所处的背景环境，列举了模型对应的条件假设，定义了模型包含的变量参数，提出了该问题相应的模型，并解释了模型目标函数及约束所表达的含义。
第四章介绍了目标运输问题的算法设计。首先利用拉格朗日松弛算法对导致原问题NP难的约束进行松弛，从而得到松弛问题的最优解，即为原运输问题的下界。再根据启发式算法将拉格朗日松弛算法得到的下界可行化，得到该问题的上界，进而利用次梯度法求得运输问题的精确解。
第五章中将对运输问题给出数值实例，根据第四章中提到的算法运用Matlab进行编程求解，对算法的效果进行验证。并将计算结果与Lingo计算结果进行比较验证，分析优化算法的可行性和有效性。
最后在第六章中对全文做出总结，并提出本文中存在的不足以及未来研究的目标方向。
全文整体框架结构如图1-1所示：
图1-1 本文研究框架
国内外研究综述
运输调度问题研究综述
运输作为物流流程中最重要的一个环节，其实质是满足需求、解决差异，即解决了货物在供应与需求中时间和空间两个维度上的差异问题。运输问题（Transportation Problem）是指在一定的运输工具运载容量、运输时间、运输数量或单位运输成本等条件限制下，把货物从供应点送到需求点，使整体的运输成本、车辆路径或出行时间取得最优的过程。运输问题是运筹学范畴中一类常见的线性规划问题，也是经典的网络流问题之一，更是制造和流通企业在实际工作中经常会面对的问题。
由于运输调度在实际工作中的复杂性，有关运输问题模型和算法的研究一直是国内外学者研究的焦点。1941年希契科克(Hitchcock)首次提出经典的运输问题，列出了经典运输问题的常用规划模型[1]。后来科普曼斯(Koopmans)于1947年对希契科克提出的经典运输问题进行了更深入的研究。之后又有大量的学者对运输问题进行了研究和探索，到如今，已发现的运输问题大致可以分为一般运输问题(H)、网络运输问题(T)、最大流量问题(F)、最短路径问题(S)、任务分配问题(A)、生产计划问题(CPS)这6类。
一般来说线性规划的求解方法也可以直接用来求解运输问题，但由于运输问题的复杂性，通过一般的线性规划方法进行求解需要花费很长的时间。结合运输问题的特性，人们发现了许多解决运输问题的方法，例如表上作业法可以很好的解决一般运输问题和任务分配问题，而图上作业则可以解决网络运输问题、最大流量问题以及最短路径问题等。近年来许多有关解决运输问题的人工智能方法如神经网络算法、禁忌搜索算法、遗传算法等也取得一定的研究成果[2,3,4]，其中尤其是遗传算法在解决运输问题方面已经得到了不错的效果。
费希尔(Fisher)总结了运输问题的解决方法，包括分支定界法、割平面法、松弛法、启发式算法、智能算法等，他将运输问题的研究分为了三个阶段：①古典运输问题研究阶段；②基于数学规划或网络分析的运输问题研究阶段；③基于智能算法的运输问题研究阶段[5]。但目前绝大部分的研究是完全基于运筹学范畴的，并没有考虑到运输与生产、库存之间的制约关系，因此将运输问题置于整个供应链环节下，综合考虑供应链中各个节点的协同关系，实现供应链整体绩效达到最优是目前国内外研究的发展方向。
拉格朗日松弛算法研究综述
拉格朗日松弛思想起源于上个世纪60年代，1970年Held. M最先成功的将拉格朗日松弛思想运用并计算解决了邮递员问题和最小树问题，并于1971年对其进行了进一步的优化[6,7]，直到1974年若弗里翁(Geoffrion)等人正式将这种基于拉格朗日松弛思想的算法命名为拉格朗日松弛算法（Lagrangian Relaxation）[8]。到如今，拉格朗日松弛算法已被证明可以很好的应用并解决很多大规模数学规划问题。
1974年Held.M发明了次梯度法，为拉格朗日乘子的计算提供了很好的解决方法[9]。1981年费希尔(Fisher)对拉格朗日松弛算法求解整数规划问题的方法进行了总结归纳[10]，即将一些困难的整数规划问题（NP难）通过松弛掉某些约束条件，使其可以很简单的得到原问题的一个下界，再通过求解松弛问题的对偶问题将这个下界可行化，求出原问题的上界，最终通过次梯度法进行迭代求得问题的精确解。这种方法已被证明可以很好的解决选址、调度、分配、邮递员等多种问题。他还详细介绍了拉格朗日松弛算法在松弛一个约束的求解步骤，以及如何通过次梯度法迭代求解拉格朗日乘子，分析了如何将这一算法运用到分支定界法中求出问题精确解。他还列举了1981年前拉格朗日松弛算法已经解决的各种优化问题以及对应优化结果的误差率（如表2-1）。
原问题 | 研究者 | 拉格朗日松弛问题 |
邮递员问题 | ||
对称 | Held amp; Karp | 最大生成树 |
非对称 | Bazarra amp; Goode | |
对称 | Balas amp; Christofides | |
非对称 | Balas amp; Christofides | 精确2型匹配 |
调度问题 | ||
并行机器的拖期调度 | Fisher | 伪多项式时间 动态规划问题 |
单机器的拖期调度 | Fisher | |
发电系统 | Muckstadt amp; Koenig | |
一般整数规划问题 | ||
无界变量 | Fisher amp; Shapiro
您需要先支付 80元 才能查看全部内容！立即支付
最新文档
| |
