algorithm - 多变量函数之和的优化

Question

想象一下，我是一家面包店，试图用有限数量的原料生产出最多的馅饼。

以下每个馅饼食谱 A、B、C 和 D 都恰好生产 1 个馅饼:

A = i + j + k
B = t + z
C = 2z
D = 2j + 2k

*食谱始终采用线性形式，如上所示。

我有以下成分:

4 of i
5 of z
4 of j
2 of k
1 of t

我想要一种算法，在我的原料数量有限的情况下最大化我的馅饼产量。

这些示例输入的最佳解决方案将产生以下数量的馅饼:

2 x A
1 x B
2 x C
0 x D
= a total of 5 pies

我可以很容易地通过取所有组合的最大生产者来解决这个问题，但是数量随着成分数量的增加，组合变得令人望而却步。我觉得必须有是这类优化问题的概括，我只是不知道从哪里开始。

虽然我只能烤整个馅饼，但我仍然有兴趣看到一种可能产生非整数结果的方法。

Answer 1

您可以定义 linear programming问题。我将在示例中展示用法，但它当然可以推广到任何数据。

将饼图表示为变量 (x1 = A, x2 = B, ...)，LP 问题如下:

maximize x1 + x2 + x3 + x4
s.t. x1 <= 4  (needed i's)
     x1 + 2x4 <= 4 (needed j's)
     x1 + 2x4 <= 2 (needed k's)
     x2 <= 1 (needed t's)
     x2 + 2x3 <= 5 (needed z's)
and x1,x2,x3,x4 >= 0

这个问题的分数阶解是多项式可解的，但整数线性规划是 NP 完全的。

问题确实是NP-Complete ，因为给定一个 integer linear programming问题，您可以使用相同的方法将问题简化为“最大化馅饼的数量”，其中每个约束都是馅饼中的一种成分，变量是馅饼的数量。

对于整数问题 - 如果您可以“接近某个界限”，那么文献中有很多近似技术来解决这个问题(例如经常使用 local ratio technique 或 primal-dual)或如果您需要一个精确的解决方案 - 指数解决方案可能是您最好的选择。 (当然，除非 P=NP )