Questão com prova de ilimitação na Programação Linear

Question

Eu gostaria de provar o seguinte: "Para uma Programação Linear na forma padrão com restrição Ax = b e todas as variáveis> = 0 mostram que d é uma direção de ilimitação se e somente se Ad = 0 e todas as entradas em d> = 0 . Por favor ajude.

Answer 1

Recomendo fortemente Bertsekas - Introduction to Linear Optimization, pois trata da Programação Linear de forma gráfica e intuitiva. Ele também contém a prova que você procura.

Algumas dicas:

• Se Ad = 0, e Ax = b, então A(x + td) = bpara t >= 0;
• Então, se d >= 0, o que isso diz sobre x + td? Ele sempre se torna menor que 0?

Agora, ao contrário:

• Se dfor uma direção para o ilimitado, o que acontecerá se houver d < 0?
• Da mesma forma, o que acontece se Ad != 0?