证明线性规划中无限性的问题

Question

我想证明以下内容：“对于具有约束 Ax = b 且所有变量 >= 0 的标准形式的线性规划，表明当且仅当 Ad = 0 且所有条目时 d 是无界方向在 d >= 0。请帮助。

Answer 1

我强烈推荐 Bertsekas - Introduction to Linear Optimization，因为它以图形和直观的方式处理线性规划。它还包含您寻求的证明。

一些提示：

• 如果 Ad = 0，并且 Ax = b，则 A(x + td) = b 对于 t >= 0；
• 那么，如果 d >= 0，这对 x + td 意味着什么？它会变得小于 0 吗？

现在，反过来：

• 如果d是一个无界的方向，如果有d < 0会怎样？
• 同样，如果Ad != 0会怎样？