Programmazione lineare Soluzione

Pagina 1

Soluzioni esercitazione di riepilogo sulla PL 1. V/ F/ F/ F/ F/ V/F/V 2. Sono in base x1, x2, s3. 3. [b] 4. [c] 5. [d] 6. a) (0,0), (0,2), (2,0); b) (1/2, 1)=1/4(0,0)+1/2(0,2)+1/4(2,0) 7. Poiché la variabile x2 è libera si può ricavare dal vincolo di uguaglianza e sostituirlo in tutte le sue occorrenze ottenendo un PL con una variabile in meno. Si noti che se x2 non fosse stata una variabile libera, ma ad es. non negativa, sarebbe stato necessario aggiungere il vincolo che la q uantità sostituita fosse non negativa. La s oluzione ottima è x=(0,-1) con valore ottimo z=-1. 8. Inammissibile 9. Nella fase 1 la variabile artificiale y2 è in base con valore 0 (caso degenere): forzando la sua entrata in base si ottiene una soluzione ottima equivalente (ossia di valore 0) per la fase 1. La soluzione ottima finale è x=……. con valore z=… 10. Una volta scritto il PL in forma standard dato c he la variabile x3 è libera è possibile ricavarla ad es. dal secondo vincolo e sostituirla in tutte le sue occorrenze ottenendo un PL nelle sole variabili x1, x2 che risulta essere illimitato. Si noti che se x3 non fosse stata una variabile libera, ma ad es. non negativa, sarebbe stato necessario aggiungere il vincolo che la quantità sostituita fosse non negativa. 11. a) Poiché i costi ridotti sono non negativi il PL (assunto in forma standard e quindi come problema di minimo) risulta essere ottimo. Una soluzione ottima è data da x=(1,3,0,1,0,0). Poiché la variabile x3 è fuori base con costo ridotto nullo essa può essere fatta entrare in base ottenendo una soluzione ottima di pari valore. La seconda soluzione ottima si ottiene facendo pivot sull’elemento ½ della riga 3 colonna 3. b) Si otterrebbe una seconda soluzione ottima x=(2,3,2,0,0,1). 12. i) α qualsiasi, β ≥ 0, γ > 0; ii) α qualsiasi, β…