2

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

以下每个馅饼配方都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

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

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

4

2 回答 2

3

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

将您的饼图表示为您的变量 (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-Complete。

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

对于整数问题 - 如果您可以使用“接近某个界限”（例如，经常使用局部比率技术或primal-dual ）或者如果您需要，那么文献中有很多近似技术可以解决该问题一个精确的解决方案——指数解决方案可能是你最好的选择。（当然，除非P=NP）

于 2012-10-24T23:05:44.413 回答
1

由于您的所有函数都是线性的，因此听起来您正在寻找线性规划（如果可以接受连续值）或整数规划（如果您要求变量是整数）。

线性规划是一种标准技术，并且可以有效地求解。执行此操作的传统算法是单纯形法。

整数规划通常是难以处理的，因为添加积分约束允许它描述难以处理的组合问题。似乎有大量的近似技术（例如，您可以尝试仅使用常规线性规划来查看结果），但当然它们取决于您的问题的具体性质。

于 2012-10-24T23:09:52.070 回答