求解具有两个变量的线性不等式的算法

Question

我试图找到一种算法来确定一组具有两个变量和以下形式的线性不等式的严格正积分解的存在：

• 𝑎₁𝑥 + 𝑏₁𝑦 ≤ 𝑙₁
• 𝑎₂𝑥 + 𝑏₂𝑦 ≤ 𝑙₂
• 𝑎₃𝑥 + 𝑏₃𝑦 ≤ 𝑙₃
• ...

问题还涉及以下形式的最终不等式：

• 𝑥 + 𝑦 ≥ 𝑙_𝑛

一些线性规划技巧在这里应该行得通，我不太精通。我一直在寻找一个更临时的解决方案，也许是利用问题中给出的性质和约束（不平等的类型）。任何见解或算法都会受到欢迎，但就 𝑛 而言，确定性和线性的东西会特别有趣，其中 𝑛 是不等式的数量。

附加约束： 𝑎_𝑖, 𝑏_𝑖, 𝑙_𝑖 > 0

Answer 1

第一个 𝑛−1 不等式描述了具有负斜率的线。换句话说，它们的形式为 𝑦=𝑚𝑥+𝑐，其中 𝑚 是一个负有理数（从 𝑎_𝑖、𝑏_𝑖、𝑙_𝑖 > 0 得出），并且它们排除了“上方”的区域“他们。

最后一个不等式描述了一条 45° 的直线，斜率为负 (-1)，并且排除了它“下方”的区域。

我们可以想象这样一个示例问题：

白色区域包含解决方案点。黑色区域被 𝑛−1 第一个约束排除，紫色区域被最后一个约束排除，紫色区域排除负 𝑥 或 𝑦 的解决方案。

由于橙色线的斜率保证为负，我们可以得出结论，如果最后一条线（斜率为-1 的深红色线）上没有属于解的点，则也没有其他点。解决方案中不可能有另一个点，而最后一条（深红色）线上的点将 all 被排除。

所以，我们“只”需要检查最后一行上的整数点。换句话说，我们可以将最终约束替换为：

𝑥 + 𝑦 = 𝑙_𝑛

我们可以迭代所有其他约束并查看相应线的斜率与最后一条线的斜率相比如何：

• 如果小于：橙色线比最后一条线更“水平”。与最后一行的交叉点表示 𝑥 的下限（以及 𝑦 的上限）。
• 如果大于：橙色线比最后一行更“垂直”。与最后一行的交叉点表示 𝑥 的上限（以及 𝑦 的下限）。
• 如果相等：橙色线与最后一条线平行。如果它在最后一行之上（或等于它），则可以忽略它。它在最后一行下面，没有解决方案。

在此过程结束时，我们有 𝑥 的最大下限和最小上限。如果这些（有理）边界仍然允许正整数 𝑥 解决方案并且相应的 𝑦 也将为正，则报告成功。否则无解。

此算法具有 O(𝑛) 时间复杂度。