RICERCA OPERATIVA GRUPPO A prova scritta del 14 luglio 2009
Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
Matricola: |__|__|__|__|__|__|
Esercizio 1
Si consideri la rete di trasmissione terrestre, riportata in figura, con due trasmettitori (A, B) e due ricevitori (1, 2). I segnali vengono trasmessi da ciascun trasmettitore ad entrambi i ricevitori nello stesso istante iniziale di trasmissione e il tempo di propagazione tra trasmettitori e ricevitori è riportato in tabella.
Tempi propagazione (µµµsec) µ
1 2
A 10 7
B 8 11
La differenza tj tra gli istanti di arrivo dei segnali provenienti dai due trasmettitori su un ricevitore j causa interferenza I, data dall’equazione I = 2 tj -3/2. L’attuale tecnologia permette di ritardare l’istante iniziale di trasmissione su ciascun trasmettitore.
1. Formulare come PL il problema di minimizzare il ritardo di trasmissione sul trasmettitore A garantendo che:
l’interferenza sul ricevitore 2non superi 6;
il ritardo di trasmissione imposto su ciascun trasmettitore non superi 2.
2. Formulare come PL il problema di minimizzare l’interferenza I sul ricevitore 1 con gli stessi vincoli del punto precedente.
Esercizio 2
Dato l’insieme X= − −
3 , 6 3 , 4 0
0 , determinare:
(a) un suo sottoinsieme (non necessariamente proprio) dipendente di cardinalità minima.
(a) un suo sottoinsieme (non necessariamente proprio) dipendente di cardinalità massima.
Esercizio 3 Dato il problema
0 ,
1 2
8 4 3
4 2 min
2 1
2 1
2 1
2 1
2 1
≥
≤
−
≥ +
≤ +
−
−
x x
x x
x x
x x
x x
a) Risolvere graficamente il problema.
b) Considerare il primo vincolo parametrico k x1 + x2 <= 4, con k reale e stabilire se esistono valori di k per cui la funzione obiettivo è illimitata inferiormente.
Esercizio 4
Risolvere il seguente problema di Programmazione Lineare mediante il Metodo del Simplesso, utilizzando l’implementazione Tableau:
0 0
7 5 3
4 3 2
3 2 3 max
2 1
3 2
3 1
3 2 1
≥
≥
≥ +
−
≤
− + +
−
x x
x x
x x
x x x
si richiede di indicare con chiarezza i vari passi del metodo.
Esercizio 5
Scrivere il problema duale del seguente problema di programmazione lineare:
0 ,
4 4
7 3 4 8
2 7 max
3 1
3 1
3 2 1
2 1
≥
−
≥ +
=
−
−
−
x x
x x
x x x
x x
