求解线性不等式组的算法

Question

我在 n 个变量中有 k 个线性不等式（0 < k < n). I don't particularly care what the solution set is, I only want to test whether or not it's empty - i.e. whether any 对我的 n 个变量的赋值满足系统要求。有人知道解决这个问题的方法吗？

谢谢！

Answer 1

这可以使用具有恒定目标函数的线性规划来完成。也就是说，仅检查程序的可行性。

Answer 2

使用 SMT 求解器进行线性算术理论（Yices、Z3、...）。这些程序旨在查找您指定的输入的模型。当然，您还可以通过其他方式从现有算法中受益。

Answer 3

您可以使用傅里叶-莫茨金消除法来解决不等式系统。不过，您需要了解基本代数才能理解解决方案。

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Answer 4

您只需将范围相交即可。以下是伪代码的操作方法：

// 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 

Answer 5

计算相关矩阵的行列式；如果它不为零，则有唯一的解决方案；如果为零，则要么有无限多个解，要么没有解 - http://en.wikipedia.org/wiki/System_of_linear_equations

或者，使用高斯消除法 - http://en.wikipedia.org/wiki/Gaussian_elimination

Answer 6

参见“求解线性不等式系统和线性规划问题的单纯形法的一个版本”