问题标签 [simplex-algorithm]

这是 SO 问题的后续问题：手动编写线性编程练习。我对出于教学目的实施单纯形算法（线性规划）也有类似的兴趣。我知道单纯形算法的简单实现可能有许多改进。但我有兴趣开发一个最小的完整单工代码。

到目前为止，我发现的最接近的实现是在这个答案中，由于@Pii 对上述 matlab 中的问题，为了完整起见，在下面复制。从相对较短的代码中，我可以看到涉及旋转的单纯形的基本逻辑是如何实现的（正如@RamNarasimhan 的回答中所指出的那样）。但我不知道如何处理线性规划问题的特殊情况，包括：

1. 不可行问题，其中可行域是空的。

2. 无界问题，其中目标函数值不受上述约束（对于标准 LP 格式：即最大化问题）

我想通过处理这两种情况，一个单纯形实现将是完整的，因为它可以处理任何 LP 问题。

我的问题是如何修改代码来处理这两种特殊情况。

注意：我不是在寻找完整的代码，只是描述处理上述两种极端情况的具体逻辑。我还查看了寻找“简单”整数线性编程源代码/伪代码，但没有找到答案。

-- @Pii 提供的代码 --

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

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

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

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

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

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

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

我在 Matlab 中使用一个基于lp_solve. 就我而言，lp_solve其结构如下：

但是当我运行它时，我得到了这个错误：

我查看了文档，它说，在“矩阵”一章下：

[...] 如果提供了密集矩阵，则该维度必须与 mxlpsolve 预期的维度完全匹配。元素太少或太多的矩阵会给出“无效向量”。错误。稀疏矩阵当然可以提供更少的元素（未提供的元素被视为零）。但是，如果提供的元素太多或索引太大的元素，又是一个“无效向量”。引发错误。

当他们说尺寸“必须与 mxlpsolve 预期的尺寸完全匹配”时，我不明白他们的意思。无论如何，因为他们说“如果提供了太多元素”也会发生错误，我试图将我的输入从 13336 个元素“减少”到 50 个（我确信它适用于 58，我很确定它也适用于2000），但也这样我收到了同样的错误。问题可能是什么？

我正在运行一个代码，该代码需要计算构成动物食品的适当成分百分比。为了做到这一点，我正在使用 MS 求解器基础。我将模型设置为传递成分和营养素的最小值和最大值（成分百分比会干扰或多或少的营养素）。我需要组成动物食品的最便宜（最小化）成本。这是我的代码。

结果，我得到了它所设置的决定的最小值，这意味着没有找到解决方案。我的问题是：为什么求解器要考虑决策中设置的最小值，而不是为每个决策计算适当的值？

我是世界生成和用于它们的算法的新手，所以我希望有人能给我一些有用的解释或代码或两者兼有，或链接到我在寻找解决方案时错过的一些资源。

如何使用 OpenSimplexNoise 获得更高的细节级别？

我知道在像 PerlinNoise 这样的算法中，它可以通过频率和相加倍频来完成。那么如何使用 OpenSimplexNoise 实现这样的目标呢？

这是我已经得到的：

我怎样才能实现它以获得更平坦的森林等结果？

是否有任何可靠的工具或源代码（最好是 C++）通过单纯形法求解有界变量的 LP？在我的问题中，所有变量都限制为 1。

我实际上在 StackOverflow 帖子中找到了一些工具：SoPlex、CLP 和 lpsolve。

其中，我想 SoPlex 更广泛。在文档中，据说 SoPlex 考虑变量边界。然后它说：

“如果所有原始变量都在其范围内，则称单纯形基是原始可行的。类似地，如果所有对偶变量都在其范围内，则称为对偶可行。如果一个基础既原始可行又对偶可行，则最优已经找到解决方案。”

我的印象是它不会强制基础在变量范围内，而是检查解决方案的变量是否在范围内。如果是这样，它认为解决方案是最优的。

是否有任何工具可以找到考虑变量界限的可行解决方案？

早上好，我有一个优化问题的问题，我无法在 R 中解决但在 Excel 中：

我想优化以下情况（物资和人员的运输）：
航空公司 x1 可以运输 50 吨物资和 500 人
航空公司 x2 可以运输 150 吨物资和 250 人

50x1 + 150x2 >= 900 -> 材料运输最小。900
500x1 + 250x2 >= 2500 -> 人员运输 2500

x1 是一家航空公司，每次航班的航班费用为 2500 x2 是一家航空公司，每次航班的航班费用为 3500 费用应该最小化！

x1>=0
x2>=0

这是我在 R 中的解决方案（来自包“boot”的函数单工）：

我收到以下错误：
Fehler in pivot(tableau, prow, pcol) : NAs nicht zugelassen in Teilbereichszuweisungen

Excels Solver 为我提供了精确的解决方案：x1 = 2.4 和 x2 = 5.2

我在 R 中的错​​误在哪里？我必须使用参数 A2 和 b2 因为 >= ...感谢您的帮助！

只是一个简短的扩展：我使用以下语法使用包“linprog”中的函数“solveLP”解决了给定的问题：

和：

仍然想知道为什么函数 simplex 会给我这个错误？

我有一个线性规划问题，我试图在R. 我用过lpSolve包。lpSolve 默认使用原始单纯形算法来获得解决方案。如果我想将算法更改为对偶单纯形怎么办？两种算法的结果差异很大。是否有任何其他软件包可以帮助使用对偶单纯形算法解决以下问题。

使用 lpSolve 的 Primal SimplexR如下：

使用 Lingo 软件和 SAS 的 Dual Simplex 如下：

两种算法的目标函数相同2.14839

我试图做一个普通的单纯形（三角形或四面体的概念到任意尺寸）来开始一组优化实验。Optimsimplex包通过使用 Spendley 方法提供了一种简单而有用的方法来实现这一点：

结果Ultra是一个包含空间维度 (n) 的 optimsimplex 类对象，并且每个 (n+1) 顶点的 (n) 坐标。可以使用 len 选项指定单纯形的维度（长度）：

len：单纯形的维度。如果长度是一个值，则在所有方向上都使用该唯一长度。如果 length 是具有 n 个值的向量，则每个长度都与相应的方向一起使用。仅在方法设置为 'axes' 或 'spendley' 时使用</p>

但是这个结果出现了一个我无法理解的错误：

错误：optimsimplex：len 向量应为行矩阵，但当前形状为 1 x 4

那么，1 x 4 不是 {optimsimplex} 预期的行矩阵吗？这可能对应于包中的某种错误吗？提前致谢。

我的任务是创建一个基于 Web 的机器，用于使用线性规划技术解决现实世界的问题，特别是目前，Danzig 的单纯形法。考虑到这一点，我发现了一段相当漂亮的 C++ 代码来计算结果，即使在这台特别低端的机器上也有相当大的速度。

但是，我目前只有控制台输出本身证明结果接近给定问题的正确解决方案。如果人们被要求相信结果表明任何比某些数字可以在计算机屏幕上闪烁更重要的东西，那么这是一个问题。

整个程序的全部细节我就不说了，因为它相当长，但这里是负责获取数据的函数，仅供参考：

如果需要，我还可以包括数据透视表、公式化和优化函数。

我想询问可以采用的具体技术，以确保在给定一组系数和约束的情况下，C++ 程序正确返回经济函数（稍后当数据输出到网络，但当我来到它时，我会越过那座桥）。

（出于归属原因，我注意到上面的代码是让-皮埃尔·莫罗（Jean-Pierre Moreau）在 1982 年创建的。巧合的是，1982 年恰好是我的出生年份，但现在这可能并不重要。）