Dualit e post ottimalit Testo

Page 1

Esercitazione di riepilogo sulla dualità e postottimalità 1. Dire se le seguenti affermazioni sono vere o false: a) la matrice dei vincoli del duale è l’inversa di quella del primale; b) se il primale è inammissibile lo è anche il duale; c) se il primale è illimitato il duale è inammissibile; d) se il primale è ammissibile lo è anche il duale; e) le variabili duali associate a vincoli di uguaglianza sono non negative; f) i prezzi ombra di vincoli soddisfatti in modo stretto sono nulli g) se una soluzione è superottima è anche ammissibile h) le condizioni di scarto complementari sono sufficienti a garantire l’ottimalità del primale 2. Scrivere il duale del seguente PL max z = x1 + x2 -x1 + x2 = 1 -x1 + x2 = 0 x1, x2  0 Cosa si può dire del primale e del duale? 3. Si consideri il seguente problema di PL. max z = x1-2x3 con x1-x2 -3 x4 = 0 2x1+3x2 ≤ 6 x1 + 2x3 ≥ 13 x1, x2, x3,x4 ≥ 0 a) Se ne scriva il duale b) Si verifichi mediante il teorema degli scarti complementari se x = (3, 0, 5, 1) è la soluzione ottima. 4. Si consideri il seguente problema di PL: max z = x1+2x2 con x1 + x2 ≤ 4 -x1+ x2 ≤ 2 x2 ≤ 3 x1, x2 ≥ 0 a) Lo si risolva geometricamente e si dica che particolarità ha la soluzione ottima trovata b) Se ne scriva il duale e se ne determini la solu zione ottima mediante il teorema degli scarti complementari. Che particolarità ha il duale? 5. Dato il seguente PL lo si risolva con l’algoritmo del simplesso duale a partire dalla soluzione superottima (0,0) min z = x1 + 2 x2 x1 + x2 ≥ 4 x1 – x2 ≤ 2 x1 , x2 ≥ 0. Una volta trovata la soluzione ottima si riottimizzi il PL con l’aggiunta del vincolo x2 ≥ 2. 6. Il tableau finale di un problema di PL di minimo, con due variabili naturali, risolto con l’algoritmo del simplesso si presenta come indicato nella tabella che…