算法求解線性不等式

的系統我有K的n個變量（0 <ķ< n）的線性不等式。我並不特別在意解集是什麼，我只是想測試它是否是空的 - 即是否任何分配到我的n個變量滿足系統。任何人都知道解決這個問題的方法？算法求解線性不等式

謝謝！

2012-03-01 GMB

使用傅里葉Motzkin的eliminaion解決不平等...... http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination – 2012-09-16 23:13:54

的系統由雙定理，我認爲，你的問題在尋找線性規劃問題的最優解時遇到困難。所以，我期待線性規劃求解器的解決方案。 – nneonneo 2013-02-05 13:34:13

這可以使用linear programming以恆定的目標函數來完成。也就是說，只檢查程序的可行性。

來源

2013-02-05 12:49:25 Shai

你只需要交叉範圍。以下是如何僞代碼：

// An array that has the ranges (inequalities) to test: 
fromToArray = [[0, 10], [5, 20], [-5, Infinity]] 

currentRange = [-Infinity, Infinity]; 
for each pair myRange in fromToArray 
    if currentRange[0] < myRange[0] 
      then currentRange[0] = myRange[0] 
    if currentRange[1] > myRange[1] 
     then currentRange[1] = myRange[1] 
    if currentRange[0] >= currentRange[1] // from greater than to, so set is empty. 
     then return "NO SOLUTION" 
end for each 

return "Solution is: " + currentRange

來源

2012-03-01 00:31:28 Diego

計算相關矩陣的行列式;如果它不爲零，則有一個獨特的解決方案;如果是零，有兩種無窮多解或無 - http://en.wikipedia.org/wiki/System_of_linear_equations

另外，使用高斯消元法 - http://en.wikipedia.org/wiki/Gaussian_elimination

來源

2012-03-01 00:31:47 scibuff

不幸的是，矩陣不是正方形的，所以行列式方法將不起作用。我不確定高斯消元是否在傳統意義上的不平等中起作用 - 行減法和乘負值標量都會變成非法的，因爲它們會翻轉不平等。 – GMB 2012-03-01 00:46:32

行列式方法_將工作。你只需要用零填充矩陣。 – 2012-04-16 19:04:31

使用SMT求解線性運算的理論（Yices，Z3，...）。這些程序旨在爲您指定的輸入找到模型。當然，您也可以通過其他方式從現有算法中受益。

來源

2013-02-05 13:24:11

嗨，C-Otto，你的回答聽起來更有趣，你可以舉個例子來做這件事（電子郵件：[email protected]）？ – Frank 2015-07-16 19:23:26