Domanda con la dimostrazione di illimitatezza nella programmazione lineare

Question

Vorrei dimostrare quanto segue: "Per una programmazione lineare in forma standard con vincolo Ax = be tutte le variabili> = 0 mostrano che d è una direzione di illimitatezza se e solo se Ad = 0 e tutte le voci in d> = 0 . Per favore aiuto.

Answer 1

Consiglio vivamente Bertsekas - Introduction to Linear Optimization, poiché si occupa di Programmazione Lineare in modo grafico ed intuitivo. Contiene anche la prova che cerchi.

Alcuni suggerimenti:

• Se Ad = 0, e Ax = b, allora A(x + td) = bper t >= 0;
• Allora, se d >= 0, cosa dice questo x + td? Diventa mai più piccolo di 0?

Ora, al contrario:

• Se dè una direzione per l'illimitatezza, cosa succede se esiste d < 0?
• Allo stesso modo, cosa succede se Ad != 0?