一类动态规划问题的解法与算法

本文给出了终止段未知的离散动态规划问题的解法和算法，并且结合经济问题的实际应用以及解法。     

利用动态规划算法解决购物单问题

购物单问题是0-1背包问题的一种应用,解决购物单问题已有贪婪法,动态规划法,蚁群算法,回溯法等.动态规划算法是求解决策过程最优化的方法,通常用于求解具有某种最优性质的问题.根据动态规划原理解决购物单问题,说明了动态规划算法解决实际生活问题的高效性.     

森林砍伐策略优化的随机动态规划模型

本文用马尔可夫链描述了松树虫灾损失和木材价格波动两个随机因素的组合过程,并提出了以上两个随机因素影响下的森林砍伐策略优化的随机动态规划方法,该方法用于实际森林砍伐决策问题,取得了满意的结果。     

精确求解一类动态规划问题的神经网络

根据一类动态规划问题的特点，提出一种能够精确求解此问题的神经网络。ＬＤＰＮＮ具有结构简单、易于硬件实现、求解速度快并且能够求得精确最优解等优点，特点适合于大规模动态规划问题的求解。在复杂系统的实时优化与控制等方面具有广阔的应用前景。     

伪币问题的动态规划算法

本文在非常一般的情况下,讨论了著名的策略问题伪币问题,设计了解此问题的动态规划算法,并进一步对动态规划算法进行分析,给出了在一般情况下,伪币问题最优值的解析表达式,以及达到最优值的简洁的最优称量算法。     

基于行列双动态规划的立体匹配算法

提出一种基于行列双动态规划的立体匹配算法,采用能量最小化立体匹配模型,其中包含数据项和平滑项,在求解能量最小化过程中,在行方向上利用动态规划的方法给出视差图的能量最小化解,利用行动态规划的求解结果给予对应数据项一个奖励,同时在列方向上对视差图进行动态规划求解,并将其作为最终求解结果。实验结果表明,该算法能够取得较理想的效果。     

基于神经网络和遗传算法的机器人动态避障路径规划

文中提出了基于神经网络和遗传算法的动态环境下机器人动态避障路径规划方法,机器人工作空间动态环境信息的神经网络模型,并利用该模型建立机器人动态避障与神经网络输出的关系,然后将需规划路径的二维编码简化成一维编码,并把动态避障要求和最短路径要求融合成一个适应度函数.通过对算法进行实验仿真,结果表明提出的动态路径规划方法是正确和有效的.     

基于迭代式动态规划的影像密集匹配

针对动态规划影像密集匹配中因匹配的整体相关性导致的误匹配点连带扩散效应问题,提出了一种基于迭代式动态规划的影像密集匹配算法。该算法在影像密集匹配过程中引入了视差方向一致性、视差突变性作为迭代判定准则,通过对动态规划匹配结果中不满足迭代条件的候选匹配点子集进行分析,在候选匹配点子集中识别出误匹配点并去除之,反复迭代直至满足迭代准则,从而解决了误匹配点的连带扩散效应问题。该算法已成功应用于嫦娥三号遥操作项目,经在轨应用的检验表明,提出的基于迭代式动态规划的影像密集匹配算法能够极大地降低立体影像匹配中密集同名点的误匹配率。     

方块脉冲函数应用于线性时变二次型最优控制的动态规划解法

本文通过应用方块脉冲函数的一些基本性质，将线性时变二次型最优控制问题化成多段动态规划问题，通过求解得到的动态规划问题，可得原问题的分段常值解。文中给出了形式简单且易于计算机求解的递推算法，与参考文献中的方法比较，本文得到的递推算法简单，明了，且计算时间及存储空间极大地减少，文中给出了算法的具体算例，具有明显的优越性。     

找钱问题的动态规划解法

动态规划算法对许多实际问题是灵活和有效的。本文首先对一类找钱问题进行了分析和讨论,然后给出了谊问题的一种动态规划解法,最后对所给算法的复杂性进行了分析。实验结果验证了所提出算法的有效性。     

一种基于流演算的动态规划程序设计语言*

提出了一种基于流演算的动态规划程序设计语言DPPLFC(dynamic planning programming language based on fluent calculus)。通过定义动作表达式来描述顺序、并发、非确定选择等复杂动作,解决了FLUX不方便用户编程的问题。DPPLFC的动态规划算子是当在线执行的状态与前一次离线执行相对应的状态不同时才进行再次离线执行,改进了基于情景演算的动态规划算子。采用了一种新颖的离/在线执行方式,能够及时处理外部动作;并给出了DPPLFC语言的组成,程序语义及其     

Dynamic programming solution to the batching problem in just-in-time flow-shops

Mixed-model manufacturing systems are widely used by companies, in order to meet the customers’ demand for a variety of products, in an efficient way. This paper is concerned with a special class of mixed-model manufacturing systems: flow-shops. In a flow-shop, each product has to be processed by a number of machines, following a common route. We study the production smoothing problem under presence of non-zero setup and processing times which also vary among the products. We split the master problem into two sub-problems which are concerned with determining the batch sizes and production sequences, respectively. We develop a dynamic programming procedure to solve the batching problem, and suggest using an existing method from the current literature to solve the sequencing problem. We conduct a computational study and show that our solution approach is effective in meeting the JIT goals and efficient in its computational requirements.     

Modelling a nationwide crop planning problem using a multiple criteria decision making tool

Multiple criteria decision making (MCDM) tools have been used in recent years to solve a wide variety of problems. In this paper we consider a nation-wide crop-planning problem and show how an MCDM tool can be used efficiently and effectively for these types of problems. A crop-planning problem is usually formulated as a single objective linear programming model. The objective is either the maximization of return from cultivated land or the minimization of cost of cultivation. This type of problem, however, normally involves more than one goal. We thus formulate a crop-planning problem as a goal program (an MCDM tool) and discuss the importance of three different goals for a case problem. We solve the goal program with a real world data set, and compare the solution with that of linear program. We argue that the goal program provides better insights to the problem and thus allows better decision support.     

动态规划算法在基于子区间消除的随机点定位问题中的应用

针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时,运行时间呈平方次增长的问题,本文提出了一种全新的基于动态规划的子区间消除算法。新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决。文中证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度。为了检验新算法的性能,本文从理论和实验两种维度,进行了新旧两种算法的对比。实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度。     

一种改进的综合生产计划动态规划优化方法

提出了一种改进的综合生产计划动态规划优化方法。以1999年甘应爱主编的《运筹学》第227~230页给出的一类综合生产计划问题为研究对象,深入分析了原综合生产计划问题、数学优化模型、动态规划求解过程、计算方法存在的不足并提出了相应的改进措施。通过案例分析验证了所提方法的有效性。     

AHP and multichoice goal programming integration for course planning

Course planning is one of the important problems in the education systems of universities. The processes cannot continue efficiently without planning, and various interruptions can appear in the system. This way decisions concerning which courses, when, how, and for what purposes should be answered by considering the available resources and stakeholders’ preferences. Besides, universities aiming to be in the European Higher Education Area (EHEA) have to adapt their systems to the Bologna process in order to create a lifelong student‐centered, learning‐oriented area based on quality assurance. In this study, an integrated approach based on the analytic hierarchy process (AHP) and multichoice goal programming (MCGP) model was proposed to construct an efficient course plan following the Bologna process. The proposed approach was applied in an industrial engineering department.     

A dynamic programming approach to solving the assortment planning problem with multiple quality levels

While the assortment planning problem, in which a firm selects a set of products to offer, has been widely studied, several problem instances exist which have not yet been solved to optimality. In particular, we consider an assortment planning problem under a locational choice model for consumer choice with both vertical and horizontal differentiation. We present a combined dynamic programming/line search approach which finds an optimal solution when customer preference for the horizontal attributes are distributed according to a unimodal distribution. The dynamic program makes use of new analytical results, which show that high quality products will be distributed near the mode. This enables significant state reduction and therefore efficient solution times. Efficient computation times allow us to study the solution for a wide range of system parameters and thereby draw several managerial conclusions.     

On stochastic dynamic programming for solving large-scale planning problems under uncertainty

The stochastic dynamic programming approach outlined here, makes use of the scenario tree in a back-to-front scheme. The multi-period stochastic problems, related to the subtrees whose root nodes are the starting nodes (i.e., scenario groups), are solved at each given stage along the time horizon. Each subproblem considers the effect of the stochasticity of the uncertain parameters from the periods of the given stage, by using curves that estimate the expected future value (EFV) of the objective function. Each subproblem is solved for a set of reference levels of the variables that also have nonzero elements in any of the previous stages besides the given stage. An appropriate sensitivity analysis of the objective function for each reference level of the linking variables allows us to estimate the EFV curves applicable to the scenario groups from the previous stages, until the curves for the first stage have been computed. An application of the scheme to the problem of production planning with logical constraints is presented. The aim of the problem consists of obtaining the planning of tactical production over the scenarios along the time horizon. The expected total cost is minimized to satisfy the product demand. Some computational experience is reported. The proposed approach compares favorably with a state-of-the-art optimization engine in instances on a very large scale.     

Multi-choice multi-objective mathematical programming model for integrated production planning: a case study

This article develops a multi-choice multi-objective linear programming model in order to solve an integrated production planning problem of a steel plant. The aim of the integrated production planning problem is to integrate the planning sub-functions into a single planning operation. The sub-functions are formulated by considering the capacity of different units of the plant, cost of raw materials from various territories, demands of customers in different geographical locations, time constraint for delivery the products, production cost and production rate at different stages of production process. Departure cost is also considered in the formulation of mathematical programming model. Some of the parameters are decided from a set of possible choices, therefore such parameters are considered as multi-choice type. Multi-choice mathematical programming problem cannot be solved directly. Therefore an equivalent multi-objective mathematical programming model is established in order to find the optimal solution of the problem. Computation of the mathematical programming model is performed with the practical production data of a plant to study the methodology.