Question with proving unboundedness in Linear Programming

Question

I would like to prove the following: "For a Linear Programming in standard form with constraint Ax = b and all variables >= 0 show that d is a direction of unboundedness if and only if Ad = 0 and all entries in d >= 0. Please help.

Answer 1

I highly recommend Bertsekas - Introduction to Linear Optimization, since it deals with Linear Programming in a graphical and intuitive way. It also contains the proof you seek.

A few hints:

• If Ad = 0, and Ax = b, then A(x + td) = b for t >= 0;
• Then, if d >= 0, what does this say about x + td? Does it ever become smaller than 0?

Now, the other way around:

• If d is a direction for unboundedness, what happens if any d < 0?
• Similarly, what happens if Ad != 0?