共查询到17条相似文献,搜索用时 66 毫秒
1.
2.
基于拉格朗日松弛算法的分布式供应链优化 总被引:2,自引:0,他引:2
为解决分布环境下的无协调中心的供应链生产计划的协调问题,提出了一种基于拉格朗目松弛算法的折扣价格协调优化策略。针对企业计划只能基于本地信息的特点,利用拉格朗日松弛算法将企业之间的物料耦合约束松弛掉,从而把整个供应链计划问题分解为多个可利用本地信息求解的企业生产计划子问题。通过上下游企业之间对折扣价格(拉格朗目算子)的异步更新,可以逐步获取整个供应链生产计划的优化解,从而实现分布环境下的供应链生产计划的异步协调。仿真实验证明了该方案的可行性。 相似文献
3.
4.
5.
针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力, 所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起. 该指标一方面可以用来定 义MKP核问题, 降低问题规模; 另一方面, 可以用作ACO的启发因子, 引导算法在有希望的解区域中强化搜索. 在大量标准算例上的测试结果表明, 所提出算法的鲁棒性较好; 与其他已有算法相比, 在求解质量和求解效率方面均具有很强的竞争力.
相似文献6.
为了提高冷链物流的运输效率,解决越库在冷链物流中的应用问题,提出了基于拉格朗日松弛算法的冷链物流的越库调度方法.首先进行了问题域的描述并做出了具体假设,基于问题域以最小化卡车等待时间和越库内部运输成本为目标,建立越库调度的整数规划数学模型.然后,提出了针对越库调度模型的拉格朗日松弛算法,松弛复杂约束后根据决策变量将松弛问题分解为若干子问题,采用次梯度算法求解松弛模型.最后,对各种不同规模的越库模型进行仿真实验,并与传统的贪婪算法进行对比,结果表明,所提出的调度算法适用于问题的求解,并可以在较短时间内获得良好的近优解. 相似文献
7.
研究钢铁企业原料码头动态停泊计划问题,其动态特征主要体现在原料船动态到达并有两个或两个以上连续泊位且在停泊计划开始执行时每一泊位上仅有部分泊位长度可利用。针对这个问题,建立了一个数学模型并设计了改进拉格朗日算法在很短的时间内求得了近优解。在改进算法中使用了所提出的四个性质来分别加速求解子问题、乘子更新和获得可行解的过程。通过包含50个实际规模问题的算法性能实验表明改进的拉格朗日松弛算法相比未改进算法减少了80%的运行时间。 相似文献
8.
本文提出一种用于解决梯级水电系统的优化调度问题的拉格朗日松弛算法.算法对某些约束进行松弛,能有效地降低问题的难度,并快速解决问题.通过实际数据仿真证明了本算法的有效性. 相似文献
9.
10.
11.
Shih-Ho WangAuthor Vitae 《Computers & Electrical Engineering》2003,29(1):245-249
The Lagrangian relaxation approach has been successfully applied to many large-scale mathematical programming problems. The Lagrangian relaxation problem itself is a non-differentiable optimization problem. One of the methods for solving such problem is the subgradient algorithm. In this paper, we propose an improved stepsize of the subgradient algorithm for solving the Lagrangian relaxation problem. Our version of the algorithm may significantly improve the rate of convergence of subgradient algorithm when applied to the solution of Lagrangian relaxation problem. An illustrative numerical example is also given. 相似文献
12.
Shunji Tanaka 《Computers & Operations Research》2012,39(3):709-717
The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast. 相似文献
13.
14.
This paper addresses the problem of balancing assembly or fabrication lines. In order to achieve a given production rate or to optimize the use of workstations, one has to tackle the problem of balancing the production lines. It is well known that this problem belongs to the class of NP-hard problems. In this paper the polyhedron of the feasible solutions of the assembly line balancing problem is first studied. Then a Lagrangian relaxation algorithm that incorporates the set of cycle constraints in the objective function is proposed. These constraints are the complicating restrictions in the model. The relaxed problem has the interesting property that its linear programming relaxation always has integer optimal solutions. The subgradient algorithm is then used to maximize the Lagrangian dual. A heuristic is also used to find primal feasible solutions for the original line balancing integer program. These two bounds are then used to reduce the size of the branch-and-bound tree. 相似文献
15.
为提高汽车制造企业混流装配线的运行效益,提出了基于看板模型的多封闭循环路径多载量小车物料配送调度方法—–装配线物料配送调度的拉格朗日松弛算法.首先对问题域进行了描述并做出了具体假设,以最小化配送系统总成本为目标,建立了混合整数规划模型.在此基础上,针对该模型提出了两种算法—–次梯度和随机步长拉格朗日松弛算法,将松弛问题分解为两个决策子问题分别进行求解.仿真实验表明提出的两种调度算法均适用于该研究问题域,并在求解时间及稳定性上表现出良好的性能. 相似文献
16.
17.
研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能. 相似文献