问题标签 [simplex-algorithm]

我开始使用 R 来使用库中的单纯形函数（“boot”）来解决 LP 问题。当我尝试以下代码时，我只将目标向量作为字符串而不是作为向量。

由此得到以下输出

但是，这不是矢量对象，因此我无法使用x[1]. 你能帮我得到一个向量的结果吗？

我已将这张表制作成具有营养价值的菜单中的食物项目。然后，我得到了另一个表格，其中每个项目都在一行中，每个项目的消耗量在下​​面的行中。然后，我使用 excel 中的求解器工具来优化膳食选择，并对一顿饭的卡路里量设置限制，并对我使用的营养价值进行某些限制。

当我通过求解器工具运行单纯形算法时，发生的是表中消耗量的值变化，以反映在给定约束条件下你应该吃什么。

我想让它变得灵活，以便我可以更改约束并获得不同的结果，但我想要的是一种简单的方法来显示所做的选择。目前我所拥有的是另一个选项卡上的索引匹配表和值，然后我对其应用过滤器并删除所有消耗量为“0”的项目，但是每次运行求解器时都必须这样做。

有什么方法可以拉出非零并显示这些所指的项目，而不必每次都重做过滤器？

我正在研究具有以下内容的算法

我正在执行以下操作以根据上面给定的信息创建 BlockMatrix。

我期待mat3如下，

我得到的结果是，

理想情况下，如果它是 3X3 矩阵或 nxm，其中 n=m，那么我会使用 mat3 =mat3.transpose()。

在这里，如果我这样做，那么 2X3 矩阵将变为 3X2，这会在我的算法中进一步产生问题。任何人都可以提出一个简单的解决方案。

我正在使用linprogMatlab 中的函数来解决一组大型线性规划问题。我有 2601 个决策变量、51 个不等式约束、71 个等式约束以及所有变量的下限 0。

目标函数和约束中的系数在不同的问题中有所不同。我正在使用单纯形法（当我尝试活动集和内部点时，只要我等待了超过几个小时，程序就永远不会停止运行）。

对于某些问题，单纯形法很快收敛，并且对于其中一些问题（也很快）显示以下消息：

退出：约束过于严格；没有找到可行的起点。

然而，即使对于那些有该消息的人，它仍然提供了一个满足约束的解决方案。我可以忽略该消息并使用解决方案还是该消息很重要而解决方案可能不是最佳的？

更新：事实证明，内点方法解决了其中一些问题，但没有解决其他问题。所以在下面的代码中，我使用了内点法来处理它，而单纯形法和其余的一起使用。

这些是我的文件，这是我的代码：

我正在寻找一个可以解决 LP 问题的带有公式（没有 VBA，没有求解器）的 Excel 表：

轴=b

0<=x

cx->min

使用 Solver 和 VBA，我可以做到，但我想要一个仅基于 Excel 公式的解决方案。或者证明不可能有这样的由公式组成的系统。效率并不重要。

根据我在这里、YouTube 和其他网站上所做的研究，我目前正在研究一个可以使用线性规划解决的问题。我已经熟悉了所谓的 Simplex Method 及其变体，例如 - Big M、Dual SM，但我仍然找不到任何类似于我的问题的表述及其解决方案的示例。

我的问题是：如何将程序转换为标准格式？

我认为最小化和最大化都应该起作用，但让我们用最小化来做。

我使用'n'作为输入可能有'n'个变量的表示，即。有时会有 10 个，有时 - 60 个，是的 .. 那么多。但如果有办法解决它，我猜它应该适用于任意数量的变量。

最小化：
Z = a1*x1 + a2*x2 + .. + an*xn,其中a1 .. an只是随机系数，都是正数。

受制于：（这是我不确定是否可以这样做的部分）

• 自然数在哪里N1, N2, M1, M2, O1 & O2，> 0，例如 101、155、6433 等
  ，当然还有N1 < N2, M1 < M2, O1 < O2
• 其中b1 .. bn, c1 .. cn, d1 .. dn只是随机系数，都是正数

此外，每个未知变量 –x1, x2 .. xn的边界如下：

当然，所有最小值和最大值都是已知的，正数，其中 Xmin < Xmax 并且 >
0。X1..n 必须始终 > 0 并且介于其最小值/最大值之间。

我知道添加松弛、盈余、人为变量，但我不能 100% 确定它是否就这么简单。我最初的想法是将每个不等式分成两部分，并根据其符号添加松弛或盈余+人工变量，然后继续使用表格。

希望我设法很好地解释了我的问题，尽管我对如何解决它仍然有些困惑。

提前致谢！希望你们有美好的一天！

我正在尝试使用 linprog 来优化以下问题（在 Google Drive 中上传）。数据集本身在此处上传

到目前为止，我已经用 Python 编写了以下实现：

优化方法返回找不到可行的起点。我相信我在使用该方法时有一个主要错误，但到目前为止我无法理解它。

一些帮助 ？

提前致谢！

编辑：目标函数的期望值为 371724

预期的解向量 [0,0,240,0,15.8,0,0,0,126.3,109.7,108.2]

我有 841 个变量和 23382 个约束的问题（对于 LP 来说不是特别大）。

不过，在使用 Apache SimplexSolver 时，我得到了 OutOfMemoryError，即使堆大小为 1GB。

根据错误跟踪，这是在创建 Tableau 时发生的。该矩阵非常稀疏，因为大多数约束仅涉及两个或三个变量。对于 LinearConstraints 我使用的是 SparseRealVector （虽然不确定它是否带来任何东西）。

我可以在求解器上配置什么来克服这个问题吗？或者这仅仅是单纯形求解器的限制？

谢谢

下面的一个例子：

下面是一个常见的线性规划问题

最小 c'x

st 轴<=b

（A为m*n，m小于n）

据我所知，单纯形法中的旋转过程让极值点跳到另一个极值点，直到找到最优解。

极值点最多有 m 个（约束的数量）非零变量。极值点变量可分为基本变量（非零项）和非基本变量（零项）两部分。

在正常情况下，Pivoting 在每次迭代中将一个非基本变量变为基本变量，而一个基本变量变为非基本变量。

我的问题是以前基本的非基本变量可以再次变为基本变量吗？如果是，是否有至少一个变量存在的明确或特殊示例。

我需要大数据集来测试我正在编写的单纯形算法的并行版本。我能找到的唯一数据集是一种名为 MPS 的格式，但我在 Python 或 C 中找不到 MPS 解析器。

如果可能的话，我希望它们直接包含矩阵 A 以及向量 b 和 c（以易于解析的格式）。

或者是否有任何易于使用的 C、Python、Java 或 Javascript 中的 MPS 解析器？

谢谢！