在Matlab中求解一个线性不等式系统并得到整套解决方案

Question

我想在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 

Answer 1

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

下面是工具，可以做到这一些链接：

• cdd
• ppl

一种不同的方法是枚举使用额外的二元变量的最佳基地。 （你有一个零目标，所以这变得有效：列举所有可行的LP基地）。这种方法使问题成为MIP。我们可以通过类似的算法列举如下：

1. 解决MIP
2. 如果不可行：停止
3. 加约束，禁止当前点
4. 转至步骤1

这里是一个link是说明了这种方法来枚举（连续）LP问题的所有最优基础。

请注意，列举不等式系统的所有整数解更容易。许多约束编程工具将自动为您完成。另外，我们可以使用上述的“切割平面”技术。