动态规划求解线性规划问题的探索
余楠
提出问题
某企业生产产品A和产品B,产品A卖两万元,产品B卖一万元,每单位A产品消耗甲资源2单位,乙资源3单位。每单位B产品消耗甲资源3单位,乙资源2单位。假设企业拥有甲资源15单位,乙资源24单位,那么企业生产A产品和B产品各多少时利润最大?
问题求解
首先,设A产品生产产量为,B产品的生产产量为。求解如下线性规划问题:
现考虑使用动态规划方法求解该问题,建立动态规划模型如下:
阶段:K=1,2,3,表示, , 的过程
状态变量:表示第k阶段到第二阶段所拥有的第i种资源总量;
决策变量:求的值,即;
状态转移: ;
阶段效益: ;
基本方程:
有了以上动态规划模型所必需的一些前提条件,用逆序求解法计算,
当k=2时,有:
当k=1时,有:
易知在,则可判断该区间
,大括号内为增
函数,因此,有:
代回原式中求得。
,B产品0单位,企业最大利润15万元。
不妨推广至n个决策变量m个约束问题:
在此为方便讨论只针对和情况进行详细讨论
在此建立动态规划模型:
阶段: 表示的过程;
状态变量:表示第k阶段到第m阶段所拥有的第i种资源总量;
决策变量:求的值,即;
状态转移: ;
阶段效益:
基本方程:
当k=n时:
动态规划求解线性规划问题的探索 来自淘豆网m.daumloan.com转载请标明出处.
