尧图网站建设 )
上接机器学习系列:动态规划(1) 。三、经典应用场景例 4 资源分配问题资源分配问题是运筹学与算法领域的经典优化问题核心是在资源总量有限的约束下将资源分配给多个使用者/项目/阶段实现总收益最大化或总成本最小化。动态规划是求解这类问题的核心方法之一尤其适合具有最优子结构和重叠子问题特性的多阶段分配场景。根据资源特性和分配规则常见的资源分配问题可分为三类1一维离散资源分配: 资源按整数单位分配不可无限细分收益函数可为线性/非线性。典型应用场景设备分配、人员调度、整数单位的项目投资。2一维连续资源分配 资源可无限细分常伴随资源回收/折损的跨阶段转移。典型应用场景年度生产负荷安排、可循环资金分配、能源调度。3多维资源分配 同时分配多种有限资源如资金人力设备约束条件更复杂。典型应用场景多资源约束的项目组合管理、综合生产计划。1. 一维离散资源分配问题描述 设有总量为S的某类离散资源如设备台数、整数单位的资金、物资等需要分配给N个使用者工厂、项目、生产线等。若分配单位资源给第k个使用者可获得收益其中为非负整数且满足。目标是找到一组分配方案使得总收益最大, 即求解如下数学模型解这里将静态的资源分配问题引入阶段顺序转化为多阶段决策过程按如下步骤建立动态规划模型。1 阶段划分 将资源分配给第k个使用者作为第k阶段共划分为N个阶段即。2状态变量表示第k阶段初拥有的、待分配给N个使用者的资源总量的取值范围为0,1,2,…,S。3决策变量表示第k阶段分配给第k个使用者的资源量 允许决策范围为。4状态转移方程分配完第k个使用者后剩余设备进入下一阶段即。5指标函数: 表示将个资源分配给第k至第N个使用者时能获取的最大总收益。这里采样逆序递推关系边界条件为, 即所有资源分配完成后无额外收益。总收益最大的值为, 再通过反向回溯即可得到各阶段的最优分配方案。以下给个具体案例并在MATLAB下实现求解算法。设备分配问题: 将5台设备分配给A、B、C三个工厂各工厂获得不同数量设备时的利润如下表求总利润最大的分配方案 。设备台数012345A厂利润万元03791213B厂利润万元0510111111C厂利润万元046111213为便于程序实现这里用矩阵存储各个工厂获得不同设备时的利润即表示第k个工厂获得j-1个设备时的利润。用矩阵存储各个阶段的指标函数即记录。 于是指标函数的递推关系可以转化为这里对应。引入一个决策路径记录矩阵 其中记录节点处下一阶段的决策。 于是最优值的最佳决策可按如下算法回溯这里是路径下标是最佳决策。完整程序如下%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %用动态规划求解资源分配问题(一维离散资源分配) %一维离散资源分配 %资源按整数单位分配不可无限细分收益函数可为线性/非线性。典型应用场景 %设备分配、人员调度、整数单位的项目投资。 %2026.8.28 MiaoZhh %RecourceAllocation1.m %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear all clc %% 案例1 数据 N3; %工厂数 S5; %总设备数 %% 不同数量设备时的利润表 G[0 3 7 9 12 13; 0 5 10 11 11 11; 0 4 6 11 12 12]; %% 变量定义 %目标函数存储矩阵 dpzeros(N1,S1); %最优路径记录矩阵 pathzeros(N,S1); %path(k,j)记录第k1行上的列标 %% 目标函数递推过程 for kN:(-1):1 for i1:S1 MaxfG(k,1)dp(k1,i); path(k,i)i; for j1:i if Maxf(G(k,j)dp(k1,i-j1)) Maxf(G(k,j)dp(k1,i-j1)); path(k,i)i-j1; end end dp(k,i)Maxf; end end %% 回溯 %(1) 找出最佳路径 optCurrzeros(N,1); uzeros(N,1); optCurr(1)path(1,S1); u(1)S1-optCurr(1); for k2:N optCurr(k) path(k,optCurr(k-1)); u(k)optCurr(k-1)-optCurr(k); end %(2) 各个阶段最佳资源分配 for k1:N disp([Factory , char(65k-1), is allocated num2str(u(k)), devices]); end disp([The total income is:,num2str(dp(1,S1))])2. 一维连续资源分配 一维连续资源分配是动态规划在运筹优化中的经典应用场景核心是将可无限细分的单种有限资源分配给多个使用者/项目实现总收益最大化典型场景包括资金投资分配、机器负荷分配、能源/原材料连续分配等。问题描述设有待分配的资源为单一类型如资金、原材料、能源、机器工时等总数量固定为S资源可连续拆分分配量可取任意非负实数例如可分配3.75吨原料、126.8万元资金区别于必须取整数单位的离散资源分配问题。共N个相互独立的活动/使用者如投资项目、生产线、生产周期每个活动的收益仅与分配到的资源量相关。对第k个活动投入单位资源时可获得对应收益收益函数通常为非线性函数常见为边际收益递减的凹函数且为已知确定条件。在总资源约束下确定每个活动的资源分配量使得所有活动的总收益最大化。数学模型为解同样地这里将静态的资源分配问题引入阶段顺序转化为多阶段决策过程按如下步骤建立动态规划模型。1 阶段划分 将资源分配给第k个活动(或使用者)的过程作为第k个N个阶段。2状态变量表示第k阶段初拥有的、待分配给N个使用者的资源总量的取值范围为。3决策变量表示第k阶段分配给第k个活动(使用者)的资源量 允许决策范围为。4状态转移方程分配完第k个活动(使用者)后剩余设备进入下一阶段即。5指标函数: 表示将个资源分配给第k至第N个活动(使用者)时能获取的最大总收益。这里采样逆序递推关系边界条件为, 即所有资源分配完成后无额外收益。总收益最大的值为, 再通过反向回溯即可得到各阶段的最优分配方案。以下给个具体案例。机器负荷分配问题某工厂初始有1000台机器高负荷生产年单台产量8、年完好率0.7年折损30%低负荷生产年单台产量5、年完好率0.9年折损10%。安排5年的生产计划使5年总产量最大。此时,,。 对该问题这里设决策变量表示第k年高负荷生产的设备数量则该年低负荷生产的设备数量为。允许决策集合为。这里由于设备逐年有折损情况故状态转移方程 第k1年年初的完好设备 高负荷留存设备 低负荷留存设备即这里阶段指标应为第k年的产量为高、低负荷产量之和即。指标函数表示第k年年初有台完好机床时从第k年到第5年末的最大总收益。,边界条件第5年年末生产结束无后续收益即。以下做逆序递推求解。1 第5阶段即时由于是关于的线性函数因此最大值在区间端点处取得即2 第4阶段即时这里将代入上式得同样由于是关于的线性函数因此最大值在区间端点处取得即3 第3阶段即时将代入上式得由于是关于的线性函数因此最大值在区间端点处取得即4 第2阶段即时将代入上式得由于是关于的线性递减函数因此最大值在区间端点处取得即5 第1阶段即时将代入上式得由于是关于的线性递减函数于是此时的最优决策为。以下回溯推导的最优决策1第1年 剩余设备数, 最优决策即高负荷0台低负荷1000台 年末留存。2第2年剩余设备数 最优决策即高负荷0台低负荷900台 年末留存。3第3年剩余设备数 最优决策即高负荷810台低负荷0台 年末留存。4第4年剩余设备数 最优决策即高负荷567台低负荷0台 年末留存。5第5年剩余设备 最优决策即高负荷396.9台低负荷0台。对应的最大总产量。未完下接机器学习系列动态规划(3)。 机器学习系列：动态规划 (2)
上接机器学习系列:动态规划(1) 。三、经典应用场景例 4 资源分配问题资源分配问题是运筹学与算法领域的经典优化问题核心是在资源总量有限的约束下将资源分配给多个使用者/项目/阶段实现总收益最大化或总成本最小化。动态规划是求解这类问题的核心方法之一尤其适合具有最优子结构和重叠子问题特性的多阶段分配场景。根据资源特性和分配规则常见的资源分配问题可分为三类1一维离散资源分配: 资源按整数单位分配不可无限细分收益函数可为线性/非线性。典型应用场景设备分配、人员调度、整数单位的项目投资。2一维连续资源分配 资源可无限细分常伴随资源回收/折损的跨阶段转移。典型应用场景年度生产负荷安排、可循环资金分配、能源调度。3多维资源分配 同时分配多种有限资源如资金人力设备约束条件更复杂。典型应用场景多资源约束的项目组合管理、综合生产计划。1. 一维离散资源分配问题描述 设有总量为S的某类离散资源如设备台数、整数单位的资金、物资等需要分配给N个使用者工厂、项目、生产线等。若分配单位资源给第k个使用者可获得收益其中为非负整数且满足。目标是找到一组分配方案使得总收益最大, 即求解如下数学模型解这里将静态的资源分配问题引入阶段顺序转化为多阶段决策过程按如下步骤建立动态规划模型。1 阶段划分 将资源分配给第k个使用者作为第k阶段共划分为N个阶段即。2状态变量表示第k阶段初拥有的、待分配给N个使用者的资源总量的取值范围为0,1,2,…,S。3决策变量表示第k阶段分配给第k个使用者的资源量 允许决策范围为。4状态转移方程分配完第k个使用者后剩余设备进入下一阶段即。5指标函数: 表示将个资源分配给第k至第N个使用者时能获取的最大总收益。这里采样逆序递推关系边界条件为, 即所有资源分配完成后无额外收益。总收益最大的值为, 再通过反向回溯即可得到各阶段的最优分配方案。以下给个具体案例并在MATLAB下实现求解算法。设备分配问题: 将5台设备分配给A、B、C三个工厂各工厂获得不同数量设备时的利润如下表求总利润最大的分配方案 。设备台数012345A厂利润万元03791213B厂利润万元0510111111C厂利润万元046111213为便于程序实现这里用矩阵存储各个工厂获得不同设备时的利润即表示第k个工厂获得j-1个设备时的利润。用矩阵存储各个阶段的指标函数即记录。 于是指标函数的递推关系可以转化为这里对应。引入一个决策路径记录矩阵 其中记录节点处下一阶段的决策。 于是最优值的最佳决策可按如下算法回溯这里是路径下标是最佳决策。完整程序如下%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %用动态规划求解资源分配问题(一维离散资源分配) %一维离散资源分配 %资源按整数单位分配不可无限细分收益函数可为线性/非线性。典型应用场景 %设备分配、人员调度、整数单位的项目投资。 %2026.8.28 MiaoZhh %RecourceAllocation1.m %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear all clc %% 案例1 数据 N3; %工厂数 S5; %总设备数 %% 不同数量设备时的利润表 G[0 3 7 9 12 13; 0 5 10 11 11 11; 0 4 6 11 12 12]; %% 变量定义 %目标函数存储矩阵 dpzeros(N1,S1); %最优路径记录矩阵 pathzeros(N,S1); %path(k,j)记录第k1行上的列标 %% 目标函数递推过程 for kN:(-1):1 for i1:S1 MaxfG(k,1)dp(k1,i); path(k,i)i; for j1:i if Maxf(G(k,j)dp(k1,i-j1)) Maxf(G(k,j)dp(k1,i-j1)); path(k,i)i-j1; end end dp(k,i)Maxf; end end %% 回溯 %(1) 找出最佳路径 optCurrzeros(N,1); uzeros(N,1); optCurr(1)path(1,S1); u(1)S1-optCurr(1); for k2:N optCurr(k) path(k,optCurr(k-1)); u(k)optCurr(k-1)-optCurr(k); end %(2) 各个阶段最佳资源分配 for k1:N disp([Factory , char(65k-1), is allocated num2str(u(k)), devices]); end disp([The total income is:,num2str(dp(1,S1))])2. 一维连续资源分配 一维连续资源分配是动态规划在运筹优化中的经典应用场景核心是将可无限细分的单种有限资源分配给多个使用者/项目实现总收益最大化典型场景包括资金投资分配、机器负荷分配、能源/原材料连续分配等。问题描述设有待分配的资源为单一类型如资金、原材料、能源、机器工时等总数量固定为S资源可连续拆分分配量可取任意非负实数例如可分配3.75吨原料、126.8万元资金区别于必须取整数单位的离散资源分配问题。共N个相互独立的活动/使用者如投资项目、生产线、生产周期每个活动的收益仅与分配到的资源量相关。对第k个活动投入单位资源时可获得对应收益收益函数通常为非线性函数常见为边际收益递减的凹函数且为已知确定条件。在总资源约束下确定每个活动的资源分配量使得所有活动的总收益最大化。数学模型为解同样地这里将静态的资源分配问题引入阶段顺序转化为多阶段决策过程按如下步骤建立动态规划模型。1 阶段划分 将资源分配给第k个活动(或使用者)的过程作为第k个N个阶段。2状态变量表示第k阶段初拥有的、待分配给N个使用者的资源总量的取值范围为。3决策变量表示第k阶段分配给第k个活动(使用者)的资源量 允许决策范围为。4状态转移方程分配完第k个活动(使用者)后剩余设备进入下一阶段即。5指标函数: 表示将个资源分配给第k至第N个活动(使用者)时能获取的最大总收益。这里采样逆序递推关系边界条件为, 即所有资源分配完成后无额外收益。总收益最大的值为, 再通过反向回溯即可得到各阶段的最优分配方案。以下给个具体案例。机器负荷分配问题某工厂初始有1000台机器高负荷生产年单台产量8、年完好率0.7年折损30%低负荷生产年单台产量5、年完好率0.9年折损10%。安排5年的生产计划使5年总产量最大。此时,,。 对该问题这里设决策变量表示第k年高负荷生产的设备数量则该年低负荷生产的设备数量为。允许决策集合为。这里由于设备逐年有折损情况故状态转移方程 第k1年年初的完好设备 高负荷留存设备 低负荷留存设备即这里阶段指标应为第k年的产量为高、低负荷产量之和即。指标函数表示第k年年初有台完好机床时从第k年到第5年末的最大总收益。,边界条件第5年年末生产结束无后续收益即。以下做逆序递推求解。1 第5阶段即时由于是关于的线性函数因此最大值在区间端点处取得即2 第4阶段即时这里将代入上式得同样由于是关于的线性函数因此最大值在区间端点处取得即3 第3阶段即时将代入上式得由于是关于的线性函数因此最大值在区间端点处取得即4 第2阶段即时将代入上式得由于是关于的线性递减函数因此最大值在区间端点处取得即5 第1阶段即时将代入上式得由于是关于的线性递减函数于是此时的最优决策为。以下回溯推导的最优决策1第1年 剩余设备数, 最优决策即高负荷0台低负荷1000台 年末留存。2第2年剩余设备数 最优决策即高负荷0台低负荷900台 年末留存。3第3年剩余设备数 最优决策即高负荷810台低负荷0台 年末留存。4第4年剩余设备数 最优决策即高负荷567台低负荷0台 年末留存。5第5年剩余设备 最优决策即高负荷396.9台低负荷0台。对应的最大总产量。未完下接机器学习系列动态规划(3)。