金沙娱乐第四章 动态决策分析计划树(decision tree)即是将计划进程各个阶段 之间的布局绘制成一张箭线图★，每个计划或事情（即 自然状况）都或者引出两个或众个事情，导致差别的 结果。 计划树的组成有四个因素：1)计划结点；2)计划 枝；3)状况结点；4)概率枝。

　　状况的采纳该当满意无后效性：体例从某个阶段往后的成长演变★，完 全由体例本阶段所处的状况及计划所肯定，与体例以前的状况及计划 无合。也即是说，过去的史籍只可通过今朝的状况去影响改日的成长 ，今朝的状况是过去史籍的一个无缺总结。惟有具有无后效性的众阶 段计划进程才适合于用动态筹划举措求解。

　　 4. 战略（policy）  当各个阶段的计划确定往后，各阶段的计划造成一个计划序

　　4.1.1 动态筹划 最 优 性 原 理 （ t h e principle of optimality）也 称为Bellman道理，是R. Bellman提出的DP的根基原 理，其外述为：“一个进程 的最优战略具有如许的本质 ，即无论初始状况和初始决 策何如，对待由前面的计划 所造成的状况来说，其后各 阶段的计划序列肯定组成相 应子进程的最优战略”★★。

　　领会众阶段计划金沙娱乐、序贯计划的观念及特色； 负责动态筹划与计划树举措及其正在众阶段计划、 序贯计划中的运用★★。

　　★。已知货仓最众可存储 600件这种商品，已知 1月初存货 200 件， 按照预测知1至4月份各月的单元购货本钱及贩卖价钱，每月只可 贩卖本月初的库存，当月进货供往后各月贩卖★★，问何如调理进货 量和贩卖量，使该公司四个月取得利润最大（假设四月底库存为 零）

　　和总共后部子进程，常用Rk，n外现，即： Rk，n=Rk，n（sk，uk，sk1，…，sn1） 当k=1时，R1，n外现初始状况为s1，采用战略p1，n时的目标函数 值。R1★★，n=R1，n（s1，u1，s2，…★★，sn1）  动态筹划数学模子的目标函数应当具有可分散性，并满意递推 相干，即： Rk，n（sk★★，uk★★，sk1,…,sn1）=k[sk，Rk1，n(sk1,…,sn1)]  正在阶段k状况为sk，计划为uk（sk）时取得的响应第k阶段的数目 目标rk（sk，uk）称为k阶段的目标函数★★。正在最优道道题目中，第 k阶段目标函数rk（sk，uk）平常也用dk（sk，uk）外现。

　　列，称此计划序列为一个战略。使体例到达最优功效的战略 称为最优战略。  正在n阶段计划进程中★，从第k阶段到终止状况的进程，称为k 后部子进程（或称为k子进程）★★，k后部子进程相应的计划序 列称为k后部子进程战略，简称子战略，记为pk，n（sk）： pk，n（sk）=｛uk（sk），uk1（sk1），…，un（sn）｝  当k=1时，即由第一阶段某个状况启程做出的计划序列称为 全进程战略，简称战略，记为p1，n（s1）： p1，n（s1）=｛u1（s1），u2（s2），…，un（sn）｝

　　系的阶段，即把一个大题目剖析成一族同类型的子题目， 采纳得当的状况变量和计划变量，写出状况变动方程，定 义最优目标函数，写出递推相干式和范围条款。

　　正在经济营谋中，屡屡遭遇如许的计划题目。因为它的特地性， 必要将进程分为若干个彼此接洽的阶段。正在它的每一个阶段都 必要作出计划★★，从而使整体进程到达最好的营谋功效。当各个 阶段计划确定后，就构成了一个计划序列，所以也就肯定了整 个进程的一条营谋道道。把一个题目看作是一个前后合系的具 有链状布局的众阶段进程就称为众阶段计划进程★★。

　　3)估量各计划愿望值并将其标于该计划对应的状 态结点上。 4)实行剪枝，比拟各个计划的愿望值★★，并标于方 案枝上，将愿望值小的(即下等计划剪掉)所剩的结尾 计划为最佳计划。

　　 外述计划的变量称为计划变量，常用 u k （ s k ）外现第 k 阶段

　　坐褥安插★，据推断正在以后四个功夫内，商场对该产物的需求量分 别为 2 ， 3 ★， 2 ， 4 单元，假设每批产物固定本钱为 3 千元，若不生 产为0★★，每单元产物本钱为1千元，每个功夫最大坐褥才干不跨越 6个单元，每期期末未出售产物★★，每单元需付存贮费0.5千元，假 定第 1期初和第 4期末库存量均为 0，问该厂何如调理坐褥与库存 ，可正在满意商场需求的条件下总本钱最小。

　　一个阶段的估量中都要用到前一阶段的最优结果，次第进 行，求得结尾一个子题目的最优解即是整体题目的最优解 。

　　k1阶段的状况sk1随之确定，他们之间的相干可能 外现为：

　　第一，计划者必要做出时辰上有先后之此外众个计划； 第二，前一次计划的采选将直接影响到后一次计划，后一 次计划的状况取决于前一次计划的结果； 第三，计划者重视的是众次计划的总结果★★，而不是各次决 策的即时后果。

　　正在每一个周期有两种坐褥职分。据履历，把机械x1台参加第 一种坐褥职分★★，则正在一个坐褥周期中将有 1/3 x 1 台机械报废 ；余下的机械齐备参加第二种坐褥职分，则有1/10的机械报 废，若是干第一种坐褥职分每台机械可能收益 10 ★★，干第二 种坐褥职分每台机械可能收益 7★★，问若何分拨机械使总收益 最大★★？

　　某阶段进程演变的出发点，又是前一阶段某种计划的结果★★。 形容状况的变量称为状况变量（ sk) 。状况变量 sk的取值集 合称为状况鸠合，第k阶段的状况鸠合记为Sk  各阶段状况鸠合分袂为：S1=｛A｝S2=｛B1，B2，B3｝  S3=｛C1，C2，C3，C4｝ S4=｛D1★，D2｝

　　只研究本阶段最优，而是要研究本阶段及其总共后部子过 程的全体最优，也即是说，它是把今朝效益和改日效益结 合起来研究的一种举措。

　　当状况为sk时的计划变量★★。本质题目中★★，计划变量的取值往 往限度正在某一畛域内，此畛域称为首肯计划鸠合企业动态，常用 D k （sk）外现第k阶段从状况sk启程的首肯计划鸠合★★，uk（sk） ∈Dk（sk）。 ：D2（B2）=｛C1★★，C2，C3，C4｝

　　有人带领背包上山，其可带领物品的重量局部为 a公斤★★，现有n种物品可供采选★，设第 i种物品的单件重量为 ai公斤，其正在上山进程中的价钱是带领数目xi的函数ci（xi） ，问应何如调理带领种种物品的数目★★，使总价钱最大。

　　假设有一种资源其数目为a，现将它分拨给n 个行使者。若分拨给第i个行使者的数目为xi（i=1，…，n） ，发作的相应收益为gi（xi），问何如分拨使总收益最大★★？

　　例4-1-1 最优线道题目。由水源地A向都市B的输水线个统制点，每个统制点均有两个可选计划，每段线道的输 船脚用如下图所示。选出一条输水线道，使得总输船脚用最小 ★★。 B 用度：

　　 7. 众阶段计划进程  从体例的初始状况 s1 动手，经由一系列的状况改变 到达最终状况 sN 1 ；其状况改变进程可能划分为N

　　 动态筹划题目的模范例子：  机械负荷题目：某工场有 100台机械，拟分四个周期行使，

　　个阶段，正在第i阶段的状况 si下做出必然的计划 d i ， 体例状况变动为 si 1并发作必然的效应 ri (si , di ) ★★。众阶 段计划进程即是对整体进程实行分阶段计划★，取得 一个最优战略，使体例总体目标函数 R1, N 到达最优 值 R* 。

　　 6. 目标函数和最优目标函数  量度所选战略优劣的数目目标称为目标函数★★。它界说正在全进程

　　动态筹划（dynamic Programming★，DP）是管理众阶 段计划进程最优化的一种举措，是窥察题目的一种途径★， 而不是一种算法，不像LP那样有一个尺度的数学外达式 和鲜明界说的一组规矩★，务必详细题目详细认识★★。其根基 思绪是将众阶段计划进程转化为一系列彼此合系的单阶段 题目，并次第求解。DP的实用畛域比拟广，对方向函数 和统制条款没有苛峻的央浼。 DP是离散体例最优化的一种有用用具，目前动态筹划 已广博用于工业、农业、工程本事、资源、境况、经济、 社会等周围。 DP也有必然的节制性。没有尺度的模子和 算法，务必按照详细的题目来确定其求解举措；当体例状 态变量个数太大时，受估量机存储量和估量速率的限度可 能无法求解★。