Appunti Ricerca operativa

Il suo problema duale ha tre variabili vincolate in segno

 Il suo problema duale ha tre variabili di cui due vincolate in segno



14. il problema di flusso di costo minimo è:

il problema di determinare un flusso ammissibile cui corrisponda la minima

 somma delle domanda

il problema di determinare un flusso ammissibile a un costo minimo

 il problema di determinare un flusso ammissibile a capacità minima

 il problema di determinare un taglio di costo minimo sulla rete di flusso



15. Si consideri il seguente problema di programmazione Lineare.

Min x1 – 2x2 + x3

X1 + x2 = 1

X1 – x3 = 4

X1,x2,x3 >= 0

Il numero massimo di soluzioni di base per il problema è

6

 3

 4

 Nessuna delle precedenti opzioni



16. Si consideri un problema di PL in quattro variabili e la soluzione di base

ammissibile determinata dalla seguente forma tabellare

x1 x2 x3 x4 | -z

-3 0 1 0 | -3

2 1 -1 0 | 2

3 0 2 1 | 5

Il valore della soluzione di base ammissibile è 3

 Il valore della soluzione di base ammissibile è 0

 Non è possibile determinare il valore della soluzione di base ammissibile

 considerata

Il valore della soluzione di base ammissibile è il vettore (2,5)



17. Il teorema fondamentale della PL implica che:

Se il problema è vuoto o illimitato non può ammettere soluzione ottima

 Il problema è vuoto o illimitato

 Se il problema è illimitato è anche vuoto

 Il problema ammette sempre soluzione



18. Si consideri un problema di PL in cinque variabili e la soluzione di base ammissibile

indicata nella seguente forma tabellare

x1 x2 x3 x4 x5 | -z

-4 -2 0 0 0 | 0

1 0 1 0 0 | 2

0 3 0 1 0 | 0

1 0 0 0 1 | 4

Possiamo concludere che occorre effettuare un cambio di base

 Possiamo concludere che la soluzione di base corrente sia ottima

 Possiamo concludere che il problema sia illimitato

 Non è possibile concludere niente



19. Si consideri il seguente problema di Programmazione Lineare

Min x1 + x2

2x1 + 2x2 <= 4

3x1 + x2 >= 2

X1,x2 >= 0

Il suo problema duale ha sia variabili vincolate in segno che variabili libere in

 segno

Il suo problema duale ha tutte le variabili libere in segno

 Il suo problema duale ha tutte le variabili vincolate in segno

 Nessuna delle precedenti opzioni



20. Si consideri il seguente problema di programmazione lineare

Min x1 + x2

2x1 + 2x2 + x3 = 4

3x1 + x2 – x4 = 2

X1,x2,x3,x4 >= 0

Il numero massimo di soluzioni di base per il problema è:

6

 4

 3

 Nessuna delle precedenti opzioni



21. Si consideri il seguente problema di programmazione lineare (PL)

Min x1 + x2 – 3x3

4x1 – x2 + x3 >= 2

-2x1 + x3 >= 0

X1,x2,x3 >= 0

Il problema è in forma standard

 Il problema è sia in forma generale che in forma standard

 Il problema è in forma generale

 Nessuna delle precedenti opzioni



22. Nel problema del cammino di costo minimo da s a t:

La funzione obiettivo è una combinazione lineare a coefficienti pari al costo

 degli archi

La funzione obiettivo è una combinazione lineare a coefficienti pari alla capacità

 degli archi

La funzione obiettivo è una combinazione lineare a coefficienti pari alle

 domande dei nodi

La funzione obiettivo è una combinazione lineare a coefficienti pari alle

 domande degli archi

23. siano x e y soluzioni ammissibili per un problema di PL di minimizzazione e per il

suo problema duale:

Il valore della soluzione x è non maggiore del valore della soluzione y

 Il valore della soluzione x è maggiore del valore della soluzione y

 Il valore della soluzione x è non minore del valore della soluzione y

 Il valore della soluzione x è minore del valore della soluzione y



24. Si consideri il seguente problema di programmazione lineare

Min 5x1 + 5x2 + x3

2x1 + 3x2 + 2x3 <= 10

X1 + 4x3 <=5

X1,x2 >= 0

Il problema è sia in forma standard che in forma generale

 Il problema è in forma standard

 Il problema è in forma generale

 Nessuna delle precedenti opzioni



25. Il metodo branch and bound

E’ un metodo euristico di soluzione per problemi di PL01

 E’ un metodo euristico di soluzione per problemi di PL

 E’ un metodo esatto di soluzione per problemi PL01

 Si applica solo a problemi di minimizzazzione



26. Si consideri il seguente problema di Programmazione Lineare

Max -x1 + 3x2

X1 + x2 = 4

2x2 <= 1

X1 <= 7

X1,x2 >= 0

Il suo problema duale è un problema di minimizzazione e ha due vincoli di

 disuguaglianza

Il suo problema duale è un problema di massimizzazione e ha tre vincoli di

 uguaglianza

Il suo problema duale è un problema di minimizzazione e ha tre vincoli: uno di

 uguaglianza e due di disugiaglianza

Il suo problema duale è un problema di massimizzazione e ha due vincoli di

 disuguaglianza

27. Si consideri un problema di PL in quattro variabili e la soluzione di base

ammissibile indicata nella seguente forma tabellare

x1 x2 x3 x4 | -z

-2 0 0 1 | -3

0 1 0 2 | 3

-1 0 1 -1 | 1

Il criterio di illimitatezza è soddisfatto : il problema è illimitato

 Il criterio di ottimalità è soddisfatto: la soluzione di base corrente è ottima

 Il criterio di inammissibilità è soddisfatto: il problema è inammissibile

 Non è possibile concludere nulla.



28. Si consideri un problema di Programmazione Lineare in quattro variabili e la

soluzione di base ammissibile indicata nella seguente forma tabellare

x1 x2 x3 x4 | -z

-3 0 1 0 | -3

2 1 -1 0 | 2

3 0 2 1 | 5

La soluzione di base indicata ha le variabili x2 e x4 in base

 La soluzione di base indicata ha le variabili x1 e x2 in base

 La soluzione di base indicata ha le variabili x1 e x3 in base

 Non è possibile determinare le variabili in base della soluzione di base

 ammissibile considerata.

29. Si consideri un problema di PL in minella seguente forma tabellare

x1 x2 x3 x4 x5 | -z

-3 -1 0 0 0 | 0

1 0 1 0 0 | 1

0 4 0 1 0 | 1

2 0 0 0 1 | 2

Possiamo concludere che il problema sia illimitato

 Possiamo concludere che la soluzione di base sia ottima

 Possiamo concludere che occorre effettuare un cambio di base

 Non è possibile concludere nulla



30. Si consideri un problema di PL in quattro variabili e la soluzione di base

ammissibile indicata nella seguente forma tabellare

x1 x2 x3 x4 | -z

-3 0 1 0 | -3

2 1 -1 0 | 2

3 0 2 1 | 5

La soluzione di base ammissibile ha due variabili in base di valore 2 e 5 e due

 variabili fuori base

La soluzione di base ammissibile ha due variabili fuori base di valore 2 e 5 e due

 variabili in base di valore nullo

La soluzione di base ammissibile ha quattro variabili in base di valore -3,0,1 e 0

 Non è possibile determinare le componenti della soluzione di base ammissibile

 considerata

31. Nel problema del massimo flusso da s a t

La funzione obiettivo è lineare nelle componenti del flusso e va massimizzata

 I vincoli sono lineari tranne nel caso di somma delle domande non nulla

 La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata

 I vincoli sono lineari tranne nel caso di capacità nulle



32. Nella coppia prima/duale simmetrica

Primale e duale hanno lo stesso numero di vincoli di disuguaglianze e di variabili

 non negative

Sia il primale che il duale hanno vincoli di disuguaglianza e variabili non

 negative

Il primale ha variabili non negative, mentre il duale ha variabili libere in segno

 Sia il primale che il duale hanno vincoli di disuguaglianza e variabili libere in

 segno

33. data una rete di flusso, il taglio s-t di capacità minima:

Ha capacità data dalla somma delle capacità meno il valore del flusso a ogni

 arco

Ha capacità data dalla somma delle capacità dei nodi

 Ha capacità non inferiore al massimo flusso da s a t

 Ha capacità pari al valore del massimo flusso da s a t



34. Si consideri il seguente problema di Programmazione Lineare

Max -x1 + 3x2

X1 + x2 = 4

2x2 <= 1

X1 <= 7

X1,x2 >= 0

Il suo problema duale è un problema di minimizzazione e ha due variabili

 entrambe vincolate in segno

Il suo problema duale è un problema di minimizzazione e ha tre variabili: una

 libera e due vincolate in segno

Il suo problema duale è un problema di massimizzazione e ha tre variabili: due

 libere e una vincolata in segno

Il suo problema duale è un problema di massimizzazione e ha due variabili

 vincolate in segno

35. Si consideri il seguente problema di Programmazione Lineare {0,1}

Max 2x1 + x2 + 2x3

4x1 + x2 + x3 <= 4

X1,x2,x3 E {0,1}

Si puo risolvere solamente con il metodo branch and bound

 Il problema ammette al più 8 soluzioni ammissibili

 Il problema ammette al più 16 soluzioni ammissibili

 Nessuna delle precedenti opzioni



36. Dire quale delle seguenti affermazioni è falsa:

Se il primale ammette soluzione ottima allora il duale è illimitato

 Se il primale è inammissibile allora il duale è illimitato oppure inammissibile

 Il problema duale del duale è il problema primale

 Nessuna delle precedenti affermazioni è falsa



37. Si consideri il seguente problema di Programmazione Lineare (PL)

Min 3x1 + x2

X1 – x2 <= 2

-2X1 + x3 >= 0

X1 <= 2

X1,x2,x3 >= 0

Per poter scrivere il problema in forma standard

Non occorre far nulla: il problema è già in forma standard

 Occorre inserire due variabili di slack e una di surplus

 Occorre inserire due variabili di surplus e una di slack

 Occorre inserire 3 variabili di slack



38. il metodo grafico si può utilizzare per risolvere:

problemi di PL in due dimensioni

 qualsiasi tipo di problema di PL

 problemi di PL che ammettano almeno una soluzione ottima

 problemi di PL che ammettano almeno una soluzione



39. Nel problema di flusso di costo minimo:

I vincoli sono lineari tranne nel caso di somma delle domande non nulla

 La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata

 La funzione obiettivo è lineare nelle componenti del flusso e va massimizzata

 I vincoli sono lineari nel coso di costi nulli<