使用 Excel 求解器生成多个最优解

Question

当您使用 Excel 求解器（Simplex LP 方法）解决问题时，是否有办法获得所有最优解？

如果不是，什么是最好的 way/add-in 到 Excel 来解决它并转换现有的 VBA 代码以使用这种新方法？

Answer 1

虽然这道题看起来很简单，但实际上并不是一道简单的题。连"all possible optimal solutions"的定义都不清楚。可能有无数个。要求 "all basic feasible solutions"（即角点）听起来更好。据我所知，没有提供此功能的求解器。我也不知道有一种非常简单的技术来枚举所有最佳碱基。

一种有趣的方法是使用 MIP 公式来枚举所有最优碱基：

Sangbum Lee, Chan Phalakornkule, Michael M. Domach, Ignacio E. Grossmann, "Recursive MILP model for finding all the alternate optima in LP models for metabolic networks," Computers and Chemical Engineering 24 (2000) 711-716. (link)

Answer 2

实际上，我已经找到了一种使用 Excel 求解器来执行此操作的方法，虽然它在时间消耗方面不是最优的，但这对我来说不是问题。

如果您可以通过某种方式为每个可能的解决方案分配唯一的 id，这在我的情况下是正确的，那么对于您发现的每个解决方案，您可以通过以下方式检查是否存在具有相同值但 id 不同的解决方案：

1. 找到第一个最优解并保存解id和结果。我将这个 origID 称为 origRes

2. 检查是否有 id < origID 且 res = origRes

的解决方案

3. 如果是，则将newId作为初始id，继续第2步，直到找不到满足条件的解决方案

4. 之后，对条件id > origID 和res = origRes

做同样的事情

5. 在你确定你找到了所有的最优解origRes之后，我们就可以去寻找不是最优的origRes的解。我这样做是为了添加新解决方案需要 <= (origRes - 0.01) 的条件，因为我知道所有解决方案都将保留 2 位小数。

6. 再次转到步骤2

我知道这不是最好的方法，但我通常不需要超过 100 个解决方案，目前我可以在 2 分钟内完成，这对我来说是可以接受的。