algorithm - 如何从给定的产品及其属性中找到最小的成本？

Question

我的熔化材料应该达到所需的性能。将有 2 套材料 1) 废料 2) 铁合金 目标：以最低成本达到每个元素的目标值 For Ex. 经过 1000 Kg 混合后，我们希望达到以下特性 Carbon - 2.4% Silicon - 2.1 % p - 0.015% S - 0.015%

现在，从给定的一组材料中，我们已经定义了我们可以从 CRC（即废料）中获得多少碳，我们可以从增碳剂（铁合金）中获得 78% 的碳。这意味着如果我们使用 100 公斤 CRC，我们可以获得 1.1 碳，但我们使用 5 公斤增碳剂我们可以获得 3.9 碳。所以我们拥有每种材料的所有元素值。此外，我们有每种材料的价格。像CRC是25卢比/公斤。增碳剂为1500 / kg。所以相应地我们需要以这样的方式混合材料，它应该以最低成本达到目标值，比如达到 2.4% 的碳，如果我们使用 100 公斤废料，我们可以获得 1.1% 的碳，需要 1.4 我们可以从 1.8 公斤的增碳剂中获得花费 2500 + 2700 = 5200 卢比。可以是任意数量的组合，我们需要从中找到可能的成本最低的解决方案，但条件是要求材料应该是可数的，就像答案应该是 701.5 一样，但它不应该是 701.115，因为在实际混合时没有人会测量 115 克。所以我们需要找到尽可能低的成本，为此应该使用多少公斤的材料？这是一个元素的示例，但我们应该实现所有目标元素。

输入数据：废料及其元素值及其成本

CRC 废料 C% - 1.5 Si% - 0.9 成本：25 / kg

生铁 C% - 1.9 Si% - 1.1 成本：28 / kg

MS 废料 C% - 1.4 Si% - 0.9 成本：23.5 / kg

废钢 c% - 1.8 Si% - 1.5 成本：29 / kg

铁合金

增碳剂 C% - 80 Si% 0 成本：1000 / kg

硅铁 C% - 0 Si %- 65 S% 10 成本：1200 / kg

锰铁 c% - 0 S% - 20 P% - 15 成本：500 / kg

铜 cu% - 98 成本：1500 / kg

所需值在上面定义。现在，我们需要找到 1000 公斤的废料混合物，并以成本最佳的方式实现铁合金的属性使用。

是否有任何算法可用于此类问题？或者有什么方法可以帮助我找到租赁成本？

谢谢你。

标签： algorithmdynamic-programming

Answer 1

所有这些都可以描述为一个线性程序。一旦你有了这个，你可以把它插入你最喜欢的求解器，如果可行的话，你可以得到一个解决方案。

您要最小化的优化目标是总成本：

f = w_CRC * cost_CRC + w_pigIron * cost_pigIron + ...

w_...是每种材料的权重，代表优化变量。成本是常数。

然后添加以下约束来模拟您的需求：

w_CRC + w_pigIron + w_MS + ... = totalWeight
w_CRC >= 0, w_pigIron >=0, w_MS >= 0 ...
w_CRC * C_CRC + w_pigIron * C_pigIron + ... = desiredCWeight
w_CRC * Si_CRC + w_pigIron * Si_pigIron + ... = desiredSiWeight

C_和Si_是元素在相应材料中的比例，desiredXWeight = totalWeight * desiredXProportion。

如果您想确保您的结果是“不错”的数字，您可以添加完整性约束并使其成为整数线性程序。例如，如果您想允许权重到小数点后一位，您可以将权重替换w_X为0.1 * u_X整数权重因子并求解u_X。然后，您得到实际重量w_X = 0.1 * u_X。但是，我假设原始公式已经为您提供了足够好的数字，其中大多数权重可能为零。此外，通过施加完整性约束，您可能会使问题变得不可行。因此，可能有必要使这些完整性约束变软。您可以通过将优化目标更改为

f = (... what we had before...) + a * ((w_CRC - 0.1 * u_CRC)^2 + (w_pigIron - 0.1 * u_pigIron)^2 + ...)

在这里，您将添加整数变量u_X并使您的权重w_X接近表示的权重。该常数a表示您希望执行此约束的程度。