问题标签 [simplex]

我正在尝试在 java 中编写一个单纯形算法来进行分配。我的代码适用于某些输入，但算法经常陷入循环，从状态 A 重新计算到状态 B，然后返回到状态 A。进入无限循环。

起初我认为这是一个退化问题。但我实际上是在使用 Bland 的规则，进一步的头脑风暴和尝试调试让我意识到这是导致循环的约束不等式中的负系数。

所以我想我明白为什么会发生错误。但我不确定我应该如何改变我的算法来解决这个问题。

这是我的整个代码...

（我本来希望只发布相关的代码片段，这样你们就不会那么费力地试图破译这个，我认为你们无论如何都需要整个代码来找到我的错误在哪里。我试图尽可能具体地发表评论。）

我将此视频用作理解单纯形法的参考：https ://www.youtube.com/watch?v=gRgsT9BB5-8

input.txt 如下所示：

这个有效

给出解决方案

这个不行

任何帮助或建议将不胜感激。非常感谢！

二进制整数规划问题的单纯形算法的复杂度是多少？对于最坏的情况或平均情况？

我正在解决分配问题。

参考：

https://en.wikipedia.org/wiki/Integer_programming

https://en.wikipedia.org/wiki/Simplex_algorithm

我试图打印一个帕斯卡三角形，但对我的整数要求非常高，即超过 的最大值long，所以我使用了 BigInteger。但是我在 PascalsTriangle 类中添加 BigIntegers 的部分得到了 NullPointerException。这是添加二维 BigInteger 数组的正确方法吗？

我需要在网站页面上使用 JavaScript 优化布局图像，以便最大限度地减少空白量。

优化问题基本上是最小化以下内容：

但是，没有图像可以重叠，因此对于每个图像，约束是：

此外，还有一个约束，任何图像的最右边坐标不能大于页面的宽度，并且任何图像的最左边坐标必须> 0。

首先我想把它表述为一个线性规划问题，但是我看到的所有 JavaScript 的线性规划库都不允许这样复杂的约束，所以我认为这可能不是一个线性问题。

然后我开始认为这是一个动态编程问题，但如果不尝试每种布局组合，我不确定如何解决它，这会非常慢。

有谁知道如何有效地解决这类问题？

我想找到一个由一些方程确定的对象的顶点。例如。

它受到以下限制

它给出了一个六面体。我想知道创建此对象的顶点的位置。

做到这一点的唯一方法是编写一个代码来检查这个方程的所有可能变化吗？

我创建了一个单纯形方法求解器，但最后我需要检查最终表是否有负值，如果它返回负数，则重新运行求解器。我做了一个 for 循环，但由于某种原因，它输出了原始数组，甚至没有解决这个问题。

以下是我的 for 循环，用于检查最后一行中的任何负值：

数组的输出是递归的，但对 [-1.33...] 数组没有任何作用。：

我不知道是否需要我的其余功能。但如果需要，我可以附上它。

我正在使用包的nerldermead()功能，nolptr例如，我想找到 50 个最有可能的解决方案。在这个例子中：

我只会获得solution=12，但我会获得这个最佳解决方案和其他 49 个解决方案。有没有办法提取nerldermead()函数的这些信息？

非常感谢 ！

我使用 Matlab 的fminsearch函数来找到 Nelder-Mead 的最小值。fminsearch 自动计算初始单纯形的大小。就我而言，初始单纯形太小，因此性能不佳。

fminsearch 使用长度为每个变量大小 5% 的边，对于零变量，其值为 0.00025。但是，我已阅读以下内容（来源）：

但是，以单纯形几乎涵盖整个可能范围的方式设置点可能是一个合理的策略。Nelder-Mead 算法会自动收缩单纯形并逼近最优。该策略的实际优势是您将对响应函数有更好的全面了解。

我必须选择多长（百分比）才能接受这项政策？

请记住，第一个单纯形运算是一种反射。如果起始单纯形覆盖了整个允许范围，则反射必然会给出一个限制点。但是 HillStormer 允许使用线性约束并且可以避免这个问题。

我必须使用哪些线性约束来避免这个问题？我正在使用允许此类约束的fminsearchbnd 和 fminsearchcon 。

最后但并非最不重要的一点是，我在 Numerical Recipes 中读到，当算法卡在局部最小值时，它有助于在卡住的点重新初始化单纯形。当然，如果 fminsearch 终止，我可以以新点作为起点重新运行它。在这种情况下，我应该将初始单纯形大小设置为什么值？

编辑（改写问题）：我将如何使用提供的 smoothstep 函数在相邻二维数组之间创建渐变？每个数组的大小相同，包含范围在 0 和 1 之间的值，通过单纯形噪声从边缘到边缘平滑过渡。结果，我希望相邻数组值之间的差异最大为 0.04

我有 6 个二维数组，其中包含 0 到 1 之间的值来表示球体表面的高度。要遍历数组的所有值，我有这个：

但是，我在使面孔匹配时遇到了一些麻烦。调查这个我发现了一个名为“smoothstep”的函数，这似乎正是我所需要的。我不知道如何实现它，我还没有找到对我有用的解释。

以下页面是我了解这种方法的地方，但我无法理解要说的内容。如果有人有时间，您能解释一下我如何将其实施到我的情况中吗？链接到相关问题

我正在解决一个优化问题。该问题具有二元约束。求解器（在迭代期间）将这些二进制约束设置为 0 到 1 之间的小数（近似于宽松的梯度搜索）。我希望向求解器表明它应该只搜索 0..1 的不连续值。

有没有办法做到这一点？

或者，OpenSolver 中是否有一种算法可以做到这一点，它模仿 simplex-lp，并提供全局最优？

便宜的方法是纠正一个for循环，并迭代这些值。我想知道是否有一种方法可以使非线性问题变成线性问题。

谢谢。