0

我想在 Matlab 中求解一个线性不等式系统，其中未知数为x(1), x(2), x(3), x(4). 我想要一整套解决方案x(1), x(2), x(3), x(4)。因此，我不能使用linprog，因为它只给了我一个可行的点。

澄清：这个问题https://stackoverflow.com/questions/37258835/how-to-set-the-objective-function-when-using-linprog-in-matlab-to-solve-a-system是关于linprogr哪个但是给出只有一种可能的解决方案。在这里，我要问如何找到整套解决方案。

这是一组不等式。有什么建议吗？

5x(1)+3x(2)+3x(3)+5x(4)<5
-5x(1)-3x(2)-3x(3)-5x(4)<-3
-x(2)-x(3)<0
x(2)+x(3)<1
-x(1)-x(4)<0
x(1)+x(4)<1
-3x(3)-5x(4)<-1
3x(3)+5x(4)>3
x(3)<1
-x(3)<0
x(4)<1
-x(4)<0
-5x(1)-3x(2)<0
5x(1)+3x(2)<2
x(2)<1
-x(2)<0
x(1)<1
-x(1)<0
4

1 回答 1

1

对于连续变量，我们基本上有零个、一个或无限多个解。当然，为此不可能显示所有解决方案。但是，线性规划中有一个角点的概念，我们可以枚举这些点，尽管需要付出很多努力。

以下是一些可以执行此操作的工具的链接：

另一种方法是使用额外的二进制变量枚举最佳碱基。（您的目标为零，因此这变得有效：枚举所有可行的 LP 基）。这种方法使问题成为 MIP。我们可以通过如下算法来枚举：

  1. 解决mip
  2. 如果不可行：停止
  3. 添加约束以禁止当前点
  4. 转到第 1 步

这是一个链接，说明了这种枚举（连续）LP 问题的所有最优基的方法。

请注意，枚举不等式系统的所有整数解更容易。许多约束编程工具会自动为您执行此操作。此外，我们可以使用上面描述的“切割平面”技术。

于 2016-05-16T20:09:20.583 回答