在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問題的所有最優基礎。

請注意，列舉不等式系統的所有整數解更容易。許多約束編程工具將自動爲您完成。另外，我們可以使用上述的「切割平面」技術。