线性规划可行性检查

计算科学 线性代数 线性规划
2021-11-27 21:31:52

是否存在任何充分必要条件来检验线性约束的可行性

Ax=b,x≥0

没有求解具有恒定目标函数的 LP？x是变量并且A∈Rm×n已给出并具有完整的行等级。b也给出了。

Farka 引理可能是一种选择。但这不是我要寻找的，因为 if 具有“如果存在一组等式和不等式的解决方案”的味道，但没有提供确定解决方案是否存在的直接方法。

是否有更直接的方法来进行可行性检查，例如仅查看增广矩阵和系数矩阵的秩，类似于 Rouché-Capelli 定理所做的那样？

1个回答

对您的问题的简短回答是：有点。

有一些称为“预处理”或“预求解”的方法，它们会处理约束问题bl≤Ax≤bu和l≤x≤u作为输入。使用通常是线性时间的测试，您可以检查不可行的充分条件（但不是必要条件）。这些方法通常用于转换问题以减少线性规划标准算法的运行时间。你应该看看Savelsbergh 1994 年的一篇论文，Andersen 和 Andersen 的一篇论文，以及Ashutosh Mahajan 的一篇调查论文。这些论文都涵盖了更普遍的转换，这些转换也很有趣。Mahajan 论文可能具有最现代和最易读的符号。

然而，在一般情况下，正如 Arnold Neumaier 在 ChristianClason 的 SciComp 链接中指出的那样，线性规划可行性检查是多项式时间可简化为线性规划，反之亦然。

其它你可能感兴趣的问题
上一篇RAMdisk 和有限元计算 下一篇如何评估一组可达到的随机排列的“质量”