Tutti i test autovalutativi Ricerca Operativa per ICT

F.O.

• -1

Siano dati la matrice ottima B Di un problema di PL e il vettore dei termini noti b

con riferimento alla variazione dei termini noti non comporta

una variazione della base B il vettore

• Dato il seguente tableau con riferimento alla

variazione dei costi e delle variabili fuori base non comporta un cambio della base ottima il vettore

• Dato il seguente tableau ottimo

Con riferimento alla variabile dei costi delle variabili in base non comporta un cambio della base

ottima il valore

21 dispensa

• Un problema di programmazione lineare intera è un problema di ottimizzazione in cui la funzione

obiettivo lineare e le variabili sono intere

• Il rilassamento continuo di un problema di PLI consiste in rimuovere il vincolo di incertezza delle

variabili

• Il valore ottimo della F.O. di un problema di PLI di massimizzazione rilassato è maggiore o uguale

del valore della F.O. all’ottimo intero

• Il guscio convesso di un insieme di punti interi è un insieme continuo con vertici interi

• Siano w e p rispettivamente peso e profitto associati ad una collezione di oggetti. Allora il seguente

problema di PLI è un knapsack binario

• Siano w e p rispettivamente peso e profitto associati ad una collezione di oggetti. Allora il seguente

problema di PLI è un knapsack intero non capacitato

• Una società vuole ridurre al minimo le spese attraverso la riorganizzazione aziendale che consiste

nell’assegnamento ottimo delle mansione ai dipenedenti. La società non vuole licenziare nessun

dipendente e vuole garantire che tutte le attività non rimangono scoperte. Sia x la variabile che

ij

associa il generico dipendente i alla generica mansione j, e sia c il corrispettivo che l’azienda paga

ij

al dipendente i per la mansione j. Considerando che ogni attività può essere fatta anche da più

addetti contemporaneamente ma che ogni addetto può essere assegnato ad una sola attività, il

problema che l’azienda deve risolvere è:

• Sia dato un insieme finito di oggetti E e una famiglia F costituita da sottoinsiemi A non vuoti di E. sia

inoltre “l” la matrice di incidenza della maglia F su E di componenti a la formula seguente indica

5 ij

un problema in cui la soluzione ottima è vettore nullo

• La mappa in figura rappresenta la città di Roma suddivisa per muncipi.

Ogni cittadino deve avere almeno un ospedale nella zona in cui risiede o in una zona adiacente.

L'obiettivo è dunque quello di minimizzare la cardinalità degli ospedali. La funzione obiettivo del

problema e il vincolo solo per il municipio 18 sono

22 dispensa

• Sia E un insieme di n oggetti con indice j e sia F una famiglia di m sottoinsiemi (non vuoti) di E con

indice i. Sia inoltre aij il generico elemento della matrice di incidenza della famiglia F su E. Allora un

problema di set covering è definito come:

• Sia dato un insieme di sette oggetti di indice j a cui è associato un costo cj e siano dati e i tre

sottoinsiemi A1 ={2,5,6}, A2={2,3,5,7}, A3={1,6,7}. Allora il problema di set covering è dato da:

• La seguente tabella riporta i dati di distanza media (espressa in km) tra 6 zone in cui è suddiviso il

territorio e 5 città (A,B,C,D,E) in cui si sta valutando l'apertura di un'azienda. La tabella riporta

anche i costi di apertura dell'azienda in ciascuna città.

Per gli utenti che vivono nelle sei zone sono accettabili le localizzazioni che distano non più di 50

km. 1. Con l'obiettivo di minimizzare i costi di avviamento dell'attività, la formulazione del

problema è

2. Con l’obbiettivo di minimazzare i costi di avviamento dell’attività, all’ottimola F.O. vale 215

3. Con l’obbiettivo di minimizzare i costi di avviamento dell’attività, all’ottimo possiamo dire

che nella città D verrà aperta una sede aziendale

• Risolvendo il seguente problema di PLI, all'ottimo la F.O. vale (utilizzare il risolutore di Excel)

all’ottimo la F.O. vale 9.5 ;

all’ottimo risulta che le variabili x2 e x5 sono nulle

• Risolvendo il seguente problema di PLI, all'ottimo la F.O. vale 12

• Risolvendo il seguente problema di PLI all’ottimo risulta che

le variabili x e x sono uguali a 1

2 5

• Risolvendo il seguente problema di PLI

All’ottimo la F.O. vale 4

23 dispensa

• Siano i e j una coppia di lavori da fare su una macchina a capacità unitaria. Un vincolo disgiuntivo

esprime la condizione: i precede j oppure j precede i

• Dato una coppia di lavoro i, j il vincolo seguente indica tj ≥ ti + pi: j precede i e il lavoro i ha durata

pi

• Data la seguente variabile decisionale disgiuntiva yij

i vincoli di sequenziamento utilizzando il big-M sono

• Date le seguenti funzioni, indicare quando vale =5/2

• Date le seguenti funzioni indicare quanto vale =0

• Sia data una macchina a capacità unitaria che deve effettuare tre lavori con tempi di

processamento: p1=3, p2=1, p3=1.Inoltre: se il primo lavoro precede il terzo, l'inizio del secondo

lavoro deve aspettare un tempo Δ2=3 dopo il termine del terzo lavoro; se il terzo lavoro precede il

secondo, l'inizio del primo lavoro deve aspettare un tempo Δ1=2 dopo il termine del secondo. La

corretta formulazione del porblema di sequenziamento è:

• Con a(x),b(x),c(x) lineari continue e non parallele la formulazione della F.O. del tipo min max {a(x),

b(x), c(x)} è lineare a tratti

• Con a(x),b(x) lineari continue e parallele, una funzione del tipo min max {a(x), b(x)} è lineare

• Siano A e B una coppia origine-destinazione e siano k=1,2,…n i vagoni di convoglio. Sia inoltre xk il

numero di passeggeri assegnato a ciascun vagone e sia B il totale dei passeggeri che vuole spostarsi

da A a B. Deve essere sempre garantito che:

Siano A e B una coppia origine-destinazione e siano k=1,2,…n i vagoni di convoglio. Sia inoltre xk il

numero di passeggeri assegnato a ciascun vagone e sia B il totale dei passeggeri che vuole spostarsi

da A a B, e Q la capacità massima del treno. Affinchè il numero dei passeggeri sia equamente

distribuito tra i vagoni (è ammessa approsimazione) deve risultare che:

24 dispensa

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, la variabile c= a

∨ b assume il valore vero (pari ad 1) se: almeno una tra a e b è vera

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, la variabile c= a

∧ b assume il valore vero (pari ad 1) se: sia a che b vere

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, la variabile c=a

⊕ b assume il valore vero (pari ad 1) se: se esattamente una tra a e b è vera

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, e sia data la

∨

variabile c= a b. Deve risultare che: c ≥ (a+b)/2

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, e sia data la

∧

variabile c= a b. Deve risultare che: c ≤ (a+b)/2

• Date due variabili proposizionali a e b a cui si associa il valore 1 se vere e 0 se false, e sia data la

⊕

variabile c=a b. Deve risultare che: c ≤ 2 - (a+b)

• Sia x la quantità di un generico bene prodotta da una fabbrica e sia c(x) il costo di produzione.

L'andamento della c(x) in presenza di costi fissi è del tipo:

• Sia x la quantità di un generico bene prodotta da una fabbrica e sia c(x) il costo di produzione. Sia

inoltre δ il costo unitario di produzione. La funzione c(x) in presenza di costi fissi (A) è del tipo:

c(x)=A + δx

• Sia xki,j una variabile che indica il numero di ore settimali di lezione che il professore i fa alla classe j

per la materia k; sia inoltre yi una variabile binaria che vale 1 se il professore è assunto e 0

altrimenti. La normativa prevede che ciascun professore non faccia più di un certo numero H di ore

di lezione a settimana. Infine, si indichi con mkj il numero di ore che la classe j deve fare per la

materia k. Allora il vincolo a tutela dei professori assunti è:

• Sia xki,j una variabile che indica il numero di ore settimali di lezione che il professore i fa alla classe j

per la materia k; sia inoltre yi una variabile binaria che vale 1 se il professore è assunto e 0

altrimenti. La normativa prevede che ciascun professore non faccia più di un certo numero H di ore

di lezione a settimana. Infine, si indichi con il numero mkj di ore che la classe j deve fare per la

materia k. Allora il vincolo che garantisce che le classi facciano un numero sufficiente di ore delle

materie è:

25 dispensa

• Se rilassando i vincoli di interezza di un problema di PLI otteniamo un soluzione intera, allora

possiamo dire che: abbiamo trovato l’ottimo del problema intero

• Ad un generico nodo dell'albero di enumerazione otteniamo una soluzione rilassata che ha una sola

variabile frazionaria (x1=8/3). I figli di quel nodo avaranno i vincoli aggiuntivi:

• Dato un problema di PLI espresso in termini di massimizzazione supponiamo di aver chiuso il

generico nodo i per interezza. Se otteniamo dal rilassamento di un altro generico nodo j che LBi ≤

UBj , allora possiamo dire che: i figli del nodo j devono essere visitati

• Dato un problema di PLI espresso in termini di minimizzazione supponiamo di aver chiuso il

generico nodo i per interezza. Se otteniamo dal rilassamento di un altro generico nodo j che UBi ≤

LBj , allora possiamo dire che: il nodo j viene chiuso per bounding

• Il criterio di visita dei nodi di tipo FIFO indica che: i nodi vengono gestiti come una coda

• Il criterio di visita dei nodi di tipo LIFO indica che i nodi vengono gestiti come una pila

• Dato il seguente problema di PLI l'UB dato dal rilassameno lineare al

nodo radice vale 9

• Dato il seguente problema di PLI all'ottimo intero x2 vale 0

• Dato il seguente albero decisionale di un problema di massimizzazione,

≤ 28

il nodo 4 può essere chiuso se

• Dato il seguente albero decisionale di un problema di massimizzazione,

la F.O all' ottimo è compresa tra i valori 28 ≤ z* ≤ 34

26 dispensa

• Dato il seguente knapsack 0-1, la variabile a cui è associato il rapporto

profitto/peso più alto è x

4

• Dato il seguente knapsack 0-1 , il valore della F.O. all' ottimo è 25

• Dato il seguente knapsack 0-1 , la soluzione fornisce un LB

• Dato il seguente knapsack 0-1 la soluzione non è ammissibile

• Dato il seguente knapsack 0-1, l' UB fornito dal