Paniere svolto ricerca operativa 2 ordinato

Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le

disequazioni a due partizioni P'' è strettamente contenuto in P'

Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le

disequazioni a due partizioni P'' è una formulazione migliore di P'

Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le

disequazioni a due partizioni, il problema di separazione si può esprimere come Data una soluzione x in

P', verificare che x appartenga a P'' o, se non vi appartiene, determinare due sottoinsiemi disgiunti e non

vuoti S e T tali che la disequazione a due partizioni associata ai sottoinsiemi S e T sia violata da x

Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le

disequazioni a due partizioni, per il problema di separazione conosciamo Una procedura euristica

Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c A

ogni formulazione lineare corrisponde un diverso rilassamento lineare e un diverso lower bound per il

problema

Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c È

possibile determinare un criterio di preferenza (independente dalla funzione obiettivo) per stabile se una

formulazione è migliore di un'altra

Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Il

problema ammette sempre formulazione ottima

Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Una

formulazione è tanto migliore quanto più alto è il valore del lower bound

Data una disquazione triangolo relativa ai nodi i, j e k L'ordine in cui compaiono i nodi i, j e k nella

disequazione è importante

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c Il valore ottimo del rilassamento lineare fornisce una limitazione inferiore

del problema di PL01 solo nel caso in cui di minimizzazione

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c Se esiste una soluzione ammissibile x' in S che valore maggiore della

soluzione ottima del rilassamento lineare allora possiamo concludere che x' è soluzione ottima del

problema di PL01

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c Se la soluzione ottima del rilassamento lineare ha tutte componenti intere

allora è una soluzione ottima del problema di PL01

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c Se la soluzione ottima del rilassamento lineare ha tutte componenti intere

allora è una soluzione ottima del problema di PL01

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c Se P=conv(S) allora la soluzione ottima del rilassamento lineare è una

soluzione ottima del problema di PL01

Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e

vettore dei costi elementari c, si definisce rilassamento lineare del problema Il problema di PL ottenuto

rimuovendo i vincoli di interezza sulle componenti intere del vettore delle variabili di decisione

Data una rete di flusso, il taglio s-t di capacità minima Ha capacità non inferiore al massimo flusso da s a

t

Data una rete di flusso, ogni taglio s-t Ha capacità non inferiore al massimo flusso da s a t ⊂P2

Date due formulazioni lineari P1 e P2 di un problema di PL01 P1 è migliore di P2 se e solo se P1

Date due formulazioni lineari P1 e P2 di un problema di PL01 P1 è migliore di P2 se e solo se P1⊂P2

Dato il grafo di localizzazione in figura, il costo della soluzione ottima del problema di localizzazione

degli impianti in cui sono attivati gli impianti A e B è 18

Dato il grafo di localizzazione in figura, nella formulazione del problema di PLI associato al problema di

localizzazione degli impianti Il numero di variabili binarie è pari a 10

Dato il grafo di localizzazione in figura, nella formulazione del problema di PLI associato al problema di

localizzazione degli impianti Il numero di variabili è pari a 15

Dato il grafo in figura, per il problema di localizzazione Il costo della soluzione ottima in cui sono attivi

gli impianti A e B è 22

Dato un limite inferiore LB per un problema di PL01 di minimizzazione La differenza (gap) tra valore di

una soluzione ammissibile e limite inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia

lontana dalla soluzione ottima del problema PL01

Dato un limite inferiore LB per un problema di PL01 di minimizzazione Tanto più il valore di una

soluzione ammissibile è vicino a LB, tanto migliore è la soluzione

Dato un problema della pianificazione degli investimenti Se il problema è di piccole dimensioni

possiamo risolverlo con il Risolutore di Excel

Dato un problema di localizzazione degli impianti con i seguenti dati Il costo totale è memorizzato nella

cella F13

Dato un problema di localizzazione degli impianti con i seguenti dati Le variabili del problema sono

rappresentate dalle celle H5:J5 e H8:J11

Dato un problema di localizzazione degli impianti con i seguenti dati Nel foglio Excel definiamo le celle

C14:E18 in cui memorizzare il termine a sinistra della disuguaglianza che definisce il vincolo che un

cliente non può essere servito da un impianto non attivo

Dato un problema di localizzazione degli impianti con i seguenti dati Nella cella F12 va inserita la

formula

D8*H8+E8*I8+F8*J8+D9*H9+E9*I9+F9*J9+D10*H10+E10*I10+F10*J10+D11*H11+E11*I11+F11*J11

Dato un problema di localizzazione degli impianti con i seguenti dati Nella cella F12 va inserita la

formula

D8*H8+E8*I8+F8*J8+D9*H9+E9*I9+F9*J9+D10*H10+E10*I10+F10*J10+D11*H11+E11*I11+F11*J11

Dato un problema di localizzazione degli impianti con i seguenti dati Nella cella J12 va inserita la

formula D5*H5+E5*I5+F5*J5

Dato un problema di localizzazione degli impianti Se il problema è di piccole dimensioni possiamo

risolverlo con il Risolutore di Excel

Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del

problema Consente sempre di separare i vettori a componenti {0,1} corrispondenti a soluzioni

ammissibili in S dai vettori a componenti {0,1} che non appartengono a S

Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del

problema È tale che l'intersezione di P con l'ipercubo unitario è uguale a S

Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del

problema È tale che l'intersezione di P con l'ipercubo unitario è uguale a S

Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del

problema Esiste sempre

Dato un problema di PL01 di minimizzazione con insieme delle soluzioni S a n componenti e vettore dei

costi c L'insieme delle soluzioni ammissibili è incluso in {0,1}n

Dato un problema di PL01 si definisce iperpiano di separazione L'iperpiano restituito da un oracolo di

separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle

soluzioni intere ammissibili per il problema di PL01

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 0

esprime il fatto che Nessuno dei due progetti può essere selezionato

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 1

esprime il fatto che Uno solo dei due progetti deve essere selezionato

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 2

esprime il fatto che Entrambi i progetti devono essere selezionati

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≤ 1

esprime il fatto che Al più uno solo dei due progetti deve essere selezionato

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≥ 1

esprime il fatto che Almeno uno dei due progetto deve essere selezionato

Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≥ 3

esprime il fatto che Il problema è inammissibile

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme A {A}

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme B {i in B}

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme differenza A/B {i in A: i not in B}

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme differenza B/A {i in B: i not in A}

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme intersezione di A e di B {i in A: i in B}

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi

dell'insieme unione di A e di B A union B

Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni non identifica tutti gli elementi

dell'insieme intersezione di A e di B {A,B}

Determinare la soluzione ottima del problema di PL01 è Sempre possibile attraverso la costruzione di

una sequenza di Gomory

Determinare la soluzione ottima della formulazione del problema di localizzazione degli impianti

Dipende dalla dimensione del problema

Determinare un lower bound per un problema di PL01 significa determinare un valore LB tale che LB ≤

cTx per ogni x in S

Dire quali tra le seguenti applicazioni non si rivolve tramite tecniche di clustering Segmentazione delle

immagini

Gli elementi principali del metodo branch and bound sono Decomposizione ricorsiva del problema

corrente e soluzione approssimata dei sottoproblemi

Greedy e Ricerca locale Sono due tecniche euristiche che si possono applicare al problema di

localizzazione degli impianti

Greedy e Ricerca locale Sono due tecniche euristiche che si possono applicare al problema di

localizzazione degli impianti

I metodi di soluzione euristici per un problema di PLI Sono particolarmente utili quando il problema è di

grandi dimensioni e si dispone di un bound di ottimalità per misurare la qualità della soluzione trovata

I metodi di soluzione euristi