求解两个变量线性不等式的算法
Fut*_*tor 3 algorithm math linear-programming numerical-methods
我试图找到一种算法来确定一组具有两个变量和以下形式的线性不等式的严格正积分解的存在性：
\n- \n
- 1 + 1 \xe2\x89\xa4 1 \n
- 2 + 2 \xe2\x89\xa4 2 \n
- 3 + 3 \xe2\x89\xa4 3 \n
- ... \n
该问题还涉及以下形式的最终不等式：
\n- \n
- + \xe2\x89\xa5 \n
一些线性编程技术应该在这里起作用，但我不太熟悉它们。我一直在寻找一种更临时的解决方案，也许可以利用问题中给出的性质和约束（不平等类型）。任何见解或算法都会受到欢迎，但就 而言（其中 是不等式的数量）而言，确定性和线性的东西会特别有趣。
\n附加约束： ,,> 0
\n第一个 \xe2\x88\x921 不等式描述具有负斜率的线。换句话说，它们的形式为=+，其中 是负有理数（这可以从,,> 0)，并且排除它们“上方”的区域。
\n最后一个不等式描述了 45\xc2\xb0 处的一条斜率为负 (-1) 的线，并且不包括其“下方”的区域。
\n我们可以想象这样一个示例问题：\n
白色区域包含解点。深色区域被 \xe2\x88\x921 第一个约束排除，紫色区域被最后一个约束排除，紫色区域排除带负数或 的解。
\n由于橙色线的斜率保证为负值，因此我们可以得出结论，如果最后一条线（斜率为 -1 的深红色线）上没有点属于解，则也没有其他点。当最后一条（深红色）线上的点全部被排除时，解决方案中不可能有另一个点。
\n因此，我们“只”需要检查最后一行的整数点。换句话说，我们可以将最终约束替换为：
\n\xc2\xa0 \xc2\xa0 \xc2\xa0 + =
\n我们可以迭代所有其他约束，并查看相应线的斜率与最后一条线的斜率相比如何：
\n- \n
- 如果小于：橙色线比最后一行更“水平”。与最后一条线的交叉点代表 的下限（以及 的上限）。 \n
- 如果大于：橙色线比最后一行更“垂直”。与最后一条线的交叉点代表 的上限（以及 的下限）。 \n
- 如果相等：橙色线与最后一条线平行。如果它位于最后一行之上（或等于它），则可以忽略它。如果低于最后一行，则无解。 \n
在此过程结束时，我们得到 的最大下限和最小上限。如果这些（有理）边界仍然允许正整数解，并且相应的解也为正，则报告成功。否则没有办法解决。
\n该算法的时间复杂度为 O()。
\n