动态规划求解线性规划问题探索.pptVIP

动态规划求解线性规划问题的探索 提出问题 某企业生产产品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时，有： 易知在 ，则可判断该区间 ，大括号内 为增 函数，因此 ，有： 代回原式中求得 。 用动态规划的求得A产品7.5单位，B产品0单位，企业最大利润15万元。 不妨推广至n个决策变量m个约束问题： 在此为方便讨论只针对 和 情况进行详细讨论 在此建立动态规划模型： 阶段： 表示 的过程； 状态变量 ：表示第k阶段到第m阶段所拥有的第i种资源总量； 决策变量 ：求 的值，即 ； 状态转移： ； 阶段效益： 基本方程： 当k=n时： 中间步骤与（1）类似，省略中间步骤 当k=1时： 将状态转移方程依次代入： 则 此时可根据（2）式大括号中的算式判断其增减性，然后判断各资源对于 的稀缺性并由此可求出 ，把 带入前一阶段的方程式，可求出 ，依次带入可求出所有决策变量。 以上只是对 的情况进行了讨论；由以上分析过程易知，当 时， ；当 时，求 解无界。此类问题解决的关键是确定i阶段决策变量的取值范围，然后确定 中式子的单调增减性从而确定该阶段的最优值。 论文总结 本文通过用动态规划模型对一个简单的线性规划问题进行求解并推广，可以得出结论，动态规划求解线性规划问题考虑到了各个环节资源的收益，具有一定优越性。 解法缺陷：当n值较大时，状态转移方程依次代入所得到的算式很复杂，而根据大括号决策变量的范围判断其增减性也不易。所以用动态规划方法求解线性规划问题只有在决策变量和约束问题都较少时才是可取的。 谢谢观看 *