技术标签： 资源分配问题 一维连续型 # 运筹学 动态规划 一维离散型 管理运筹学考研
【管理运筹学】第 8 章 | 动态规划（1，多阶段决策过程与动态规划基本概念）
【管理运筹学】第 8 章 | 动态规划（2，动态规划的基本思想与模型求解）
【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）
【管理运筹学】第 8 章 | 动态规划（4，生产与储存问题）
【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）
承接系列前文，有了对动态规划的基本认识，我们接下来就来对资源分配问题进行动态规划具体建模分析。
所谓资源分配问题，就是将数量一定的一种或若干资源（例如原材料、资金、机器设备、劳力、食品等），恰当地分配给若干个使用者，使得目标函数达到最优。
设有某种原料，总数量为 a a a ，用于生产 n n n 种产品。若分配数量 x i x_i xi 用于生产第 i i i 种产品，其收益为 g i ( x i ) g_i(x_i) gi(xi) 。问应如何分配，能使得生产这 n n n 种产品的总收入最大？
易得此问题可以写成如下规划问题： max z = g 1 ( x 1 ) + g 2 ( x 2 ) + ⋯ + g n ( x n ) \max z=g_1(x_1)+g_2(x_2)+\cdots+g_n(x_n) maxz=g1(x1)+g2(x2)+⋯+gn(xn) s . t . { x 1 + x 2 + ⋯ + x n = a x i ≥ 0 ， i = 1 , 2 , ⋯ , n s.t.\begin{cases} x_1+x_2+\cdots+x_n=a \\ x_i \geq 0，i=1,2,\cdots,n \end{cases} s.t.{ x1+x2+⋯+xn=axi≥0，i=1,2,⋯,n 当收益函数 g i ( x i ) g_i(x_i) gi(xi) 均为线性函数时，该问题是一个线性规划问题，可以利用单纯形法进行求解；当收益函数为非线性函数时，问题变为一个非线性规划问题，我们并没有要求掌握其解法。
由于这类问题的特殊结构，可以将它看作是一个多阶段决策问题，利用我们刚学习的动态规划方法进行求解。对于此类资源分配问题，通常以把资源分配给一个或几个使用者的过程作为一个阶段，将问题中的 x i x_i xi 作为决策变量，将累计的量或随递推过程变化的量选为状态变量。
此题中，可设状态变量 s k s_k sk 表示分配用于生产第 k k k 种至第 n n n 种产品的原料总数量（也即此时剩余的总可用资源数量），决策变量 u k u_k uk 表示分配给生产第 k k k 种产品的原料数，有 u k = x k u_k=x_k uk=xk 。则可得到状态转移方程为： s k + 1 = s k − u k = s k − x k s_{k+1}=s_k-u_k=s_k-x_k sk+1=sk−uk=sk−xk ，允许决策集合： D k ( s k ) = { u k ∣ 0 ≤ u k = x k ≤ s k } D_k(s_k)=\{u_k|0\leq u_k=x_k \leq s_k\} Dk(sk)={ uk∣0≤uk=xk≤sk} 令最优值函数 f k ( s k ) f_k(s_k) fk(sk) 表示以数量 s k s_k sk 的原料分配给第 k k k 种产品至第 n n n 种产品所得到的最大总收入，可写出动态规划的逆推关系式为： { f k ( s k ) = max { g k ( s k ) + f k + 1 ( s k − x k ) } ， k = n − 1 , ⋯ , 2 , 1 f n ( s n ) = m a x { g n ( s n ) } f n + 1 ( s n + 1 ) = 0 ，边界条件 \begin{cases} f_k(s_k)=\max\{g_k(s_k)+f_{k+1}(s_k-x_k)\}，k=n-1,\cdots,2,1 \\ f_n(s_n)=max\{g_n(s_n)\} \\ f_{n+1}(s_{n+1})=0，边界条件 \end{cases} ⎩ ⎨ ⎧fk(sk)=max{ gk(sk)+fk+1(sk−xk)}，k=n−1,⋯,2,1fn(sn)=max{ gn(sn)}fn+1(sn+1)=0，边界条件 最后求得的 f 1 ( a ) f_1(a) f1(a) 即为问题所求的最大总收入，具体最优生产计划可以按照 x 1 ∗ x_1^* x1∗ 进行推算，第一阶段采用 x 1 ∗ x_1* x1∗ ，则第二阶段 s 2 = s 1 − x 1 ∗ s_2=s_1-x_1^* s2=s1−x1∗ ，可找出 s 2 ∗ s_2^* s2∗ ，依次类推。
利用动态规划解法还有一个好处就是，当资源数量减少后，不用重新计算，只需修改最后一个阶段的分配情况即可。
这种指将资源合理分配，而不进行回收的问题，又被称为资源平行分配问题。
在资源分配中考虑资源回收利用，决策变量为连续值的问题称为资源连续分配问题，其一般叙述如下：
设有数量为 s 1 s_1 s1 的某种资源，可投入 A , B A,B A,B 两种生产。第 1 年若以数量 u 1 u_1 u1 投入生产 A A A ，剩下的量 s 1 − u 1 s_1-u_1 s1−u1 就投入生产 B B B ，则可得收入为 g ( u 1 ) + h ( s 1 − u 1 ) g(u_1)+h(s_1-u_1) g(u1)+h(s1−u1) ，其中 g , h g,h g,h 为已知收益函数，且 g ( 0 ) = h ( 0 ) = 0 g(0)=h(0)=0 g(0)=h(0)=0 。这种资源在投入 A , B A,B A,B 生产后，年终还可回收再投入生产。
设年回收率分别为 a , b ( a , b ∈ ( 0 , 1 ) ) a,b(a,b\in(0,1)) a,b(a,b∈(0,1)) ，则在第 1 年生产后，回收的资源量合计为 s 2 = a u 1 + b ( s 1 − u 1 ) s_2=au_1+b(s_1-u_1) s2=au1+b(s1−u1) 。第二年可将 s 2 s_2 s2 中的 u 2 u_2 u2 和 s 2 − u 2 s_2-u_2 s2−u2 分别再投入 A , B A,B A,B 两种生产，年末又可以得到收入 g ( u 2 ) + h ( s 2 − u 2 ) g(u_2)+h(s_2-u_2) g(u2)+h(s2−u2) 。如此继续进行 n n n 年，问：应该如何决定每年投入 A A A 生产的资源量 u 1 , u 2 , ⋯ , u n u_1,u_2,\cdots,u_n u1,u2,⋯,un ，使得总的收入最大？
类比离散资源分配问题的处理手法进行处理，记 s k s_k sk 为状态变量，表示第 k k k 阶段（第 k k k 年）可用于投入两种生产的资源总量。 u k u_k uk 为决策变量，表示第 k k k 阶段（第 k k k 年）用于 A A A 生产的资源量，则 s k − u k s_k-u_k sk−uk 表示用于 B B B 生产的资源量。状态转移方程为： s k + 1 = a u k + b ( s k − u k ) s_{k+1}=au_k+b(s_k-u_k) sk+1=auk+b(sk−uk) 最优值函数 f k ( s k ) f_k(s_k) fk(sk) 表示第 k k k 阶段至第 n n n 阶段采取最优分配方案进行生产后所得到的最大总收入。则逆推关系式为： { f k ( s k ) = max { g ( u k ) + h ( s k − u k ) + f k + 1 ( s k + 1 ) } ， k = n , n − 1 , ⋯ , 2 , 1 f n + 1 ( s n + 1 ) = 0 ，边界条件 \begin{cases} f_k(s_k)=\max\{g(u_k)+h(s_k-u_k)+f_{k+1}(s_{k+1})\}，k=n,n-1,\cdots,2,1 \\ f_{n+1}(s_{n+1})=0，边界条件 \end{cases} { fk(sk)=max{ g(uk)+h(sk−uk)+fk+1(sk+1)}，k=n,n−1,⋯,2,1fn+1(sn+1)=0，边界条件 最后所求 f 1 ( s 1 ) f_1(s_1) f1(s1) 即为所求问题最大总收入。
看了下书，没有算例，难度应该不小，很可能考试是不涉及的，我就先留着吧。
如果能从实际问题中，找到适合建立动态规划模型的状态量、转移方程和指标函数，那么，按照我们前面的动态规划模型求解办法，是可以按部就班顺利解决的。
对于连续和离散两种类型的资源分配问题，它们的建模思想很类似，但是要注意一些细节。下一篇文章，我们来说一说生产与储存问题。
文章浏览阅读3.2k次。Webots初学者入门教程--3D视窗_如何在webots中给球体施加一个力
文章浏览阅读1.3w次，点赞1.5k次，收藏631次。js拿到接口数据 处理成三级或者四级结构再进行渲染_js 数组数据3级
文章浏览阅读7k次，点赞36次，收藏177次。vue3已经出了好长一段时间了，最近闲来无事简单学习了一下，新增的东西还是挺多的，写一篇文章来记录一下。谈到vue3，首先想到的就是组合式api，很大程度的解决了vue2选项式api的缺点，那有啥缺点？当文件中的业务代码非常多的时候，阅读修改代码的时候是非常痛苦的，data,method，watch还有计算属性之间来回跳转, 我已经准备拔刀了。下面这些图被疯转，很形象的展现了vue2和vue3的区别，可以看到。_vue3
文章浏览阅读1k次。在命令行中运行下面这行代码：（引号里面要改为自己的stanford-corenlp所在目录）java -mx4g -cp "F:\资源\stanford-corenlp-full-2018-10-05/*" edu.stanford.nlp.pipeline.StanfordCoreNLPServer -port 9000 -timeout 15000或java -Xmx4g -cp "F..._stanford corenlp 标注结果没有依存关系
文章浏览阅读7.8k次，点赞5次，收藏43次。目录基础概念快速入门进阶设置基础概念 Sequencer 编辑器使用户能够用专业的多轨迹编辑器（类似于Matinee ）创建游戏内过场动画。通过创建 关卡序列（Level Sequences） 和添加 轨迹（Tracks），用户可以定义各个轨迹的组成，轨迹可以包含动画（Animation）（用于将角色动画化）、变形（Transformation）（在场景中移动各个东西）、音频（Audio）（用于包括音乐或音效）和数个其他轨迹（Track）类型等 Sequencer通过添加关键_ue sequencer
文章浏览阅读5.6k次，点赞2次，收藏5次。函数被多次定义的问题总是一直困扰着我，每次都耗费我大量的时间和精力去处理，实在令我头疼解决办法：编写一个头文件（里面放置你的一些函数和变量的声明），在你的.cpp文件中#include “XX.h”这样使得你的工程能通过编译，最后编译器在XX.h寻找其中函数定义时，会去每个文件中查找相关的函数定义。出现问题的原因另外函数重定义的原因是，在多个文件中直接包含了有同一个函数定义的文件，这样链接的时候就会出问题，就会报告多个函数定义，原因不用我细说也懂..._被多次定义
文章浏览阅读3.1k次。如果需要在图的边中加上边的权重可以通过在函数中设置参数来实现在拓扑图的每条边上加上权重。具体来说，需要先用函数获取边权重的字典形式，然后将该字典传递给函数来在图中显示权重标签。= 0:plt.show()这段代码中，函数用于计算节点在圆形拓扑上的位置，函数用于获取边权重的字典形式，函数用于在图中显示权重标签。nx.draw()函数用于画出节点和边的拓扑图，其中参数用于显示节点标签。最后，用plt.show()函数显示图形。运行后显示的图形为。_python绘制网络拓扑图
文章浏览阅读1.1w次，点赞4次，收藏29次。Apache+PHP环境搭建保姆级教程1.安装和配置Apache下载并安装Apache首先从apache官网下载[Download - The Apache HTTP Server Project]:可以看到有个Stable Release - Latest Version（稳定版 - 最新版本），进入链接选择Files for MIcrosoft Windos选择ApacheHaus选择你想要安装的Apache版本，VC是Visual Studio的一种对应开发环境，要注意这里选择的版_aparch + php
文章浏览阅读4.9k次，点赞7次，收藏23次。工具类的名称：EncryptionUtil工具类的功能：提供常用的加密解密方法，包括对称加密、非对称加密、哈希算法等。_java加密解密工具类
文章浏览阅读428次。转载请联系作者并注明出处 http://www.jianshu.com/p/b6b9bd1fba4d目前发现有少量情况没有hold住，具体可能出现问题的场景与解决方案见github有空会看看上述问题能否集成到sdk中来处理一、现状由于Android碎片化严重，屏幕适配一直是开发中较为头疼的问题。面对市面上五花八门的屏幕大小与分辨率，��Android基于dp与res目录名称来适配的方案已无..._meta-inf/androidx.customview_customview.versi
文章浏览阅读1.3k次。一. 编码器 MediaCodecMediaCodec 是 Android 提供的用于对音频进行编解码的类，属于硬编解。MediaCodec 在编解码的过程中使用了一组缓冲区来处理数据。如下图所示:基本使用流程如下：// 1 创建编解码器MediaCodec.createByCodecName() // createEncoderByType , createDecoderByType// 2 配置编解码器configure(@Nullable MediaFormat format, @Nu_编码后的aac数据如何保存
文章浏览阅读2.5k次。问题描述在以jpa的方式访问oracle数据库时发现关联表的数据查询不到解决方法大体意思是：hibernate的懒加载出现异常，由于seesion被释放了。自己调试了发现是在找下一级关系的时候，无法找到目标实体类导致的。网上找过一些方法都是让你把hibernate实体映射的由fetch=FetchType.LAZY改为这种FetchType.EAGER但是也是无补于事。看到stackoverflow上一个解决方案在service层的方法添加@Transactional开启事务，最后完美解决了_unable to evaluate the expression method threw 'org.hibernate.lazyinitializa