问题标签 [simplex]

I have a linear programming problem that has an optimal solution in its primal form, but I can't seem to find an optimal solution, or a solution in general, to its dual problem. Is that possible?

The primal is:

This gives optimal solution x=7/11, y=1/11.

The dual problem is:

This has no solution. Did I calculate the dual wrong or is this possible?

我正在使用 scipy.optimize.linprog 库使用单纯形法计算最小化。我有两种情况出现错误：

“ValueError：单纯形法的第 1 阶段未能找到可行的解决方案。伪目标函数的计算结果为 3.1e-12，超出了 1e-12 所需的容差，因为解决方案被认为“足够接近”到零一个基本的解决方案。考虑将容差增加到大于 3.1e-12。如果这个容差大到无法接受，问题可能是不可行的。“。

也许有人会发现问题出在哪里。

我写的代码：

这是第二个例子：

这是代码：

所以我有这个问题，我必须找到最好的分布，当通过一个函数时，它匹配一个已知的表面。我已经编写了一个脚本，该脚本在给定一些参数的情况下创建分布并吐出一个将给定表面与已知表面进行比较的度量，但是这个脚本需要的时间不可忽略，所以我不能只运行一个非常大的参数集找到最优的参数集。我研究了单纯形法，它似乎是正确的道路，但它并不是我所需要的，因为我不完全有一组线性方程，也不知道参数的约束，而是一种给出的方法单个输出（仅此而已）。谁能指出我如何解决这个问题的正确方向？谢谢！

为了再次快速回顾我的过程/问题，我有一组参数（此时为 2，但稍后将扩展为更多）定义分布。此分布用于创建一个表面，将其与已知表面进行比较，并生成一个误差度量。我想找到最优的参数集，但由于时间限制，无法遍历任意数量的参数。

我有一个容量车辆路线模型的线性模型。现在我想限制活动边的最大数量，这将导致并非每个节点都可以访问。但是，每条路线都应在站点（节点 0）开始和结束。我有以下模型：

输入：

模型：

为了实现最大活动边的约束，我添加了以下约束：

因此，我应该在约束 (1) 和 (2) 中将 '==' 运算符调整为 '<='。然而，结果是节点 0，即仓库，不再强制访问。任何人都可以进一步帮助我吗？先感谢您！

我正在使用网络 Simplex 来解决有向图中的最大流量问题。为了比较几种路由算法的执行时间，我需要使用 Dantzig 的单纯形方法 George 的实现。

我的问题是：单纯形法能否解决给定有向图中的最大流量问题？

是否有任何好的文档可以解释图论中的单纯形法？

我正在尝试解决零和游戏，为玩家 I 找到最佳概率分布。为此，我使用 scipy linprog simplex 方法。

我看过一个例子，我需要改造这个游戏：

进入这个线性优化问题：

这是我的实际代码：

这是我得到的分布： [5.87042987e-01 1.77606350e-10 2.79082859e-10 4.12957014e-01] 总和为 1，但我希望 [0 0.6 0.4 0]

我正在尝试一个带有 6 或 7 行（以及变量）的大型游戏，它甚至不等于 1.. 我做错了什么？

感谢您提供的任何帮助。

我的 MATLAB 代码存在问题，该代码使用两相单纯形法求解线性方程组。在某些示例中，它不起作用，我找不到问题所在。

工作示例和不工作示例如下图所示：

代码如下

如果您尝试解决这些问题，您会看到代码没有答案，我想知道为了工作而必须更改的内容。

我有一个包含 4 个变量的矩阵，而 3 个变量是参数，第 4 个变量给出了具有相应变量的模拟结果的均方和。现在我想用 R 创建一个三元图，其中对应于 3 个参数值的三角形应该用平方值的平均值着色。或者，我想在整个单纯形三角形中绘制插值均方和。

我已经在寻找一些功能或代码来满足我的需求。但我没有成功。

不过，这是我的数据集的示例代码（我想为此创建三元图）：

如果您提供可以创建我想要的情节的 R 代码，我将非常感激。也许在我还没有找到的包中甚至有一个预先实现的功能？！

非常感谢您的帮助！

假设单纯形算法的最坏情况时间复杂度为 O(2^n)。单纯形算法中最坏的情况是什么？为了计算时间复杂度，我想知道最坏的情况。

我目前正在使用 Python 中的单纯形算法来实现最优传输问题，用于原始和对偶。但是，我没有得到相同的原始值和对偶值。

我认为问题可能来自对偶，因为我还使用 Sinkhorn 算法解决了原始问题，它返回的值与基于单纯形的原始解决方案相同。

但是，我真的找不到哪里出了问题，而且我对问题可能来自哪里已经没有想法了。这是我的代码，我希望它很清楚！

感谢您抽出宝贵时间阅读，并提前感谢您提供的任何帮助！！！