多变量函数总和的优化

Question

想象一下，我是一家面包店，试图用我有限的原料数量来最大限度地提高我可以生产的馅饼的数量。

以下每个馅饼食谱A, B, C, and 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问题。我将在示例中显示用法，但它当然可以推广到任何数据。

记你的馅饼作为变量（X 1 = 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 

分数解决这个问题是solveable多项式，但整数线性规划是NP-Complete。

的问题确实NP-Complete，因为给定一个integer linear programming问题，可以减少的问题，以“最大化馅饼数量”使用同样的办法，其中每个约束是馅饼的成分和变量的数量馅饼。

对于整数问题 - 有在文献中，如果你可以做的问题了很多近似技术“接近到一定约束”，（例如local ratio technique或primal-dual经常使用），或者如果你需要一个确切的解决方案 - 指数解决方案可能是您最好的选择。 （当然，除非P=NP）

Answer 2

由于所有的函数是线性的，这听起来像你正在寻找任linear programming（如果连续值是可以接受的）或integer programming（如果你需要你的变量是整数）。

线性规划是一种标准技术，可以有效解决。传统的算法是simplex method。

整数编程通常是棘手的，因为添加积分约束允许它描述难处理的组合问题。似乎有大量的逼近技术（例如，你可能会尝试使用常规的线性规划来看看你得到了什么），但当然它们取决于你的问题的具体性质。