13 01 20sol

Pagina 1

Metodi di ottimizzazione della ricerca operativa Appello d’esame - 13.01.20 Domanda 1 Si consideri il seguente problema di ottimizzazione lineare: c t min (P) .sa cx Ax b x0 Quesito 1 (2 punti) Si formuli il problema ausiliario associato a P e si enuncino le condizioni di ammissibilità per P. Condizioni di ammissibilità: (vedi teoria) Problema ausiliario: (vedi teoria) ______________________________________________________ ______________________________________________________ ______________________________________________________ ______________________________________________________ ______________________________________________________ Quesito 2 (3 punti) Si supponga di conoscere una soluzione di base ammissibile iniziale 1,,BD  xx x B b 0 n o n o t t i m a l e e d i a v e r e scelto wx come variabile entrante. Si descriva per via algebrica il calcolo del valore di wx nella nuova soluzione di base a partire dal sistema di vincoli di P in forma canonica (riportato di seguito). Si enuncino, inoltre, le condizioni di illimitatezza del problema. Calcolo del valore della variabile entrante: (vedi teoria) 11 BD   ŸxB b B D x Condizioni di illimitatezza: _______________________________________________________________________________ Quesito 3 (1 punto) Si supponga che P sia il rilasciamento continuo di un problema intero. Quali delle seguenti affermazioni sono corrette? ౙ Se la soluzione ottimale di P è intera, allora essa è anche la soluzione ottimale del problema intero ප Il valore ottimo di P è maggiore o uguale del valore ottimo del problema intero ප Se la soluzione ottimale di P è intera, il problema intero è posto nella sua formulazione ideale ප La regione ammissibile di P è contenuta nella regione ammissibile del problema intero Metodi di ottimizzazione della…