08 02 12

Page 1

Nome: Cognome: Matricola : 1. Si consideri il seguente problema di programmazione lineare con vincoli di segno sulle variabili: max 4 x1 + 8x2 3x1−x2≤ 11 x1 +x2≤ 8 2x2≤ 11 x1,x 2≥ 0 Si scrivano il duale e le equazioni degli scarti complementari. Si verifichi l’ottimalit` a dei seguenti punti: ¯x1 = [ 19/4 13/4 ] ¯x2 = [ 5/2 11/2 ] ¯x3 = [ 4 1 ] Domanda aggiuntiva: Si consideri la funzione obiettivo parametrica max αx1 + 8x2. Specificare gli intervalli di appartenenza del parametro α per cui i punti specificati sopra siano ottimi. 2. Si consideri il seguente problema di Programmazione Lineare Intera: min 3 x1 + 4x2 −8x1− 12x2≤− 27 −x1 + 3x2≤ 33 4 x1,x 2∈ Z+ Dopo aver introdotto le opportune variabili di scarto, si consideri la soluzione ottima di base del rilassamento continuoB ={2, 4} uguale a x2 = 9 4,x 4 = 3 2.Si calcolino i tagli di Gomory relativi alle componenti frazionarie della soluzione. Si dia la rappresentazione grafica delle disuguaglianze trovate. 3. In una rete di telecomunicazione wireless vi ` e un insieme di trasmettitori N che possono trasmettere su vari canali scelti in un insieme F (ovviamente|F|≪| N|). `E inoltre noto l’insieme di coppie di trasmettitori interferenti A: se la coppia (i,j )∈A allora i e j non possono trasmettere sullo stesso canale. Si vuole pianificare l’assegnamento dei canali ai trasmettitori (al pi` u un canale per trasmettitore) con l’obiettivo di minimizzare il numero di trasmettitori a cui non viene assegnato nessun canale. Questo evento potrebbe presentarsi in caso di interferenza e indisponibiliit` a di canali. Descrivere un algoritmo greedy per risolvere il problema. 4. Si consideri la funzione in una variabile f(x) = max{x2−x,x 3−x} di cui si vuole cercare il minimo nell’intervallo [0, 2]. Si noti che in tale intervallo la…