这是从计算机科学中扩展一个想法的尝试。基于动态规划的杆切割问题的解决方案(给定一个整数长度的杆和长度的每个整数值的价格数组,找到最大化的最优切割利润)。想到它让我想知道.. 如果我们不被限制以整数值切割杆,而是可以在我们喜欢的任何地方切割它(分数长度是可能的)。此外,假设我们没有给出与整数长度相对应的价格表,而是给出了一个连续(单调递增,逐渐变细)的函数,该函数表示不同长度的杆的价值。例如,对于长度为 1 的杆,价值函数可能由 beta 分布的 CDF 给出。现在,我们想找到我们应该进行的削减次数以及优化总价值的值。有没有人听说过这样的问题(我在网上找不到任何东西)?
连续版棒材切割问题
计算科学
优化
2021-12-07 03:57:48
1个回答
如果函数是单调递增和递减的(即正导数、负二阶导数),那么最佳解决方案是进行无限多的切割并看到杆的无限小块。
当然,如果您假设价格函数随着正二阶导数单调增加,那么您的最佳解决方案是出售单件。
最后,如果您假设一个价格函数随着零二阶导数单调递增(即线性函数),那么任何细分都是最优的。
这表明原始问题的整数约束确实是问题的重要组成部分,并且删除它们会使问题退化为具有平凡解决方案(凸成本函数)或无解决方案(凹成本函数,其中有限多次削减没有最大收入,只有一个上限)。当然,您可以假设成本函数在其部分域中既是凸的又是凹的,但在这种情况下,您可能会遇到一个不再是凸的问题并且可能有多个局部最优值。
其它你可能感兴趣的问题