Dualit e post ottimalit Soluzione

Page 1

Soluzioni esercitazione di riepilogo sulla dualità e postottimalità 1. F/F/V/V/F/V/F/F 2. Il duale è min y1 –y1-y2  1 y1+y2  1 y1, y2 libere Il primale è inammissibile dato che i due vincoli di uguaglianza hanno lo stesso primo membro ma termini noti diversi. Anche il duale è inammissibile perché il primo vincolo può essere riscritto come y1+y2 ≤ -1 contraddicendo il secondo vincolo. 3. a) Il duale è min 6y2 +13y3 y1 +2y2 + y3  1 -y1 +3y2  -1 2y3  0 -3y1  -3 y1libera, y2  0, y3 ≤ 0 b) La soluzione data x=(3,0,5,1) è ammissibile per il primale e le equazioni di scarto complementare forniscono la corrispondente soluzione duale: 3(y1 +2y2 + y3 - 1) = 0 10y3 = 0 1(-3y1 + 3) = 0 implicano y= (1,0,0) e poiché questa soluzione è ammissibile per il duale si ha che x=(3,0,5,1) è soluzione ottima del primale. 4. a) La soluzione ottima è (1,3) e risulta essere degenere dato che c’è un vincolo ridondante e perciò la variabile di slack di un vincolo risulta essere in base con valore 0. b) Ci sono infinite soluzioni ottime. 5. Il PL ha soluzione ottima (3,1) e riottimizzato con l’aggiunta del vincolo x2 ≥ 2 la soluzione diventa (2,2). 6. Poiché il tableau ha 4 righe il problema ha quattro vincoli che assumiamo essere originariamente di ≤, perciò le prime due colonne del tableau sono associate alle variabili naturali x1 e x2 mentre le restanti quattro alle variabili di slack. Per quanto riguarda la postottimalità sui costi delle variabili naturali poiché queste sono entrambe in base si ha: 0 ≤ Δ𝑐1 ≤ − 1 −1 2 = 2 −∞ ≤ Δ𝑐2 ≤ 1 Per quanto riguarda la postottimalità dei termini noti dei vincoli poiché le variabili di slack del secondo e quarto vincolo sono in base, si ha −1 ≤ Δ𝑏2 ≤ +∞ 0 ≤ Δ𝑏4 ≤ +∞ mentre siccome le variabili di slack del primo e terzo vincolo sono fuori base, si…