
第25卷第1期
2005年3月
数学理论与应用
MATHEMATICALTHEORYANDAPPLICATIONS
Vol.25No.1
Mar.2005
求动态规划最优解的一种简便新方法——图解法
林志红
(柳州职业技术学院,柳州,545005)
Ξ
摘 要 离散型确定性的动态规划问题,是运筹学规划论中一个重要的组成部分,其内容包含的问题比较多.求其最优解的方法,叫逆序法(又叫回推法).本文提出一种统一的解法——图解法.其优点是:方便简便,计算简单.
关键词 离散型 动态规划 图解法
Graphicalmethod:asolveoptimaling
LinZhihong
iucoofjobtechnology,LiuZhou,545005)
Abstract definitivedynamicprogrammingproblemisanimportantpartofoperationalresearch.Aunitedmethod,graphicalmethod,isdiscussedinthispaperItscalculationisverysimpleandeasytobemastered.
Keywords discretetype dynamicprogramming graphicalmethod
1 离散型确定性动态规划问题图解法的步骤
第一步 由于动态规划问题都含有几个“阶段”和各阶段的交点,而图解法是以阶段为“枝
干”,以阶段交点为“节点”,画出一个类同于运筹学决策论中的“树形图”;
第二步 树形图中,从起点到终点,每条相连接的杆枝”,便是规划问题的一个可行解(应用上叫可行方案),根据规划问题的性质和目标,计算出每个可行解的目标函数数值;
第三步 按照规划要求目标函数达到最大或最小,以求出最优解(最优方案).下面,用动态规划中的“最短路径问题”和“设备更新最佳年限问题”,叙述这一图解法.
2 最短路径问题
动态规划最短路径问题的一般提法是,从A地(起点)到Z地(终点),中间经过若干个站点,每个站点均有路径与其它站点相连接,构成一个网状交通图,两站点之间的各条路径长度已知,试求起点到终点的最短路径.
不失一般性,为了讨论方便,不妨设动态规划最短路径问题的交通图,如图1所示.
Ξ
李学全教授推荐
收稿日期:2004年10月10日
求解下列整数规划的最优解...同样可以 用动态规划方法求解,但这时是一个多维动态规划问题,解法上比较繁琐一些...
等问题,采 用动态规划法求解比用其他方法更为简便....最优子策略. " 动态规划解法的关键在于给出一种递...在每个阶段用经典求极 值的方法得到最优解.表格...
设计问 题的一 种图解方法观清楚避免了数 学求 解中的试差过程、 该 法直...段式和动态规划法 百想 J 所以 , 从这个特点 出发、 , 依据最优 设计 的...
谈一类简单线性规划问题最优解的发现_高二数学_数学_高中教育_教育专区。本文介绍了一种发现简单线性规划问题非负整数最优解的普适方法。它是在图解平移法基础上...
多目标动态规划分层解法与Pareto最优解_城乡/园林...第一个 目标 最 优值宽容范 围 内求 第二 个...
线性规划求最优解_金融/投资_经管营销_专业资料。...图形求解线性规划的一种几何解法 例1 求x1、x2的...的单纯形法的计算过程可以 使计算和检验更加简便。...
规划整点最优解的几种搜索方法,它们都是在图解平移...简单线性规划问题已经逐渐成为中学数学 教学的一个...本文将介绍利用平移法求整点最优解的几种具体的...
这种从终点逐段向始点寻找最短路 线的一种方法, 就是动态规划的方法, 是一... 用图解法求解: 得最优解:x3*=H, y3*= s3, f3(s3)=13s3+ 6H s...
图解法 2.LP标准形 3. LP基本定理 4. 单纯形法 5. 大M法 线性规划(LP)...18 第三节 LP基本定理将LP化为标准形后,如何求最优解呢? 有一个定理给出了...
A. 线性规划问题,若有最优解,则必是一个基 变量...正确 满分:4 分 9.图解法同单纯形法虽然求解的...8 分 4.下列方法中,不能用于求解整数规划的是 (...
热门文档