Ricerca operativa

Start Studying!

Glossario di ricerca operativa

Terms

undefined, object

copy deck

Programmazione a molti criteri: Programmazione a molti obiettivi con variabili discrete.
Ciclo Euleriano: Ciclo che passa una e una sola volta per ogni arco del grafo.
Grado di un nodo: Dato un grafo, è il numero di lati ad esso incidenti.
P: Classe dei problemi di riconoscimento che si possono risolvere in tempo polinomiale.
Grafo connesso: Un grafo in cui tutte le coppie di nodi sono connesse.
Coppie di soluzioni di base: Data una coppia di PL primale-duale P e D, due soluzioni di base per P e per D, x e y, se soddisfano l'equazione dello scarto complementare xi * yi = 0, per ogni xi, yi >= 0. Ciò assicura che z(x)=w(x), ma non assicura che x e y siano soluzioni ottime poiché non è detto che siano entrambe ammissibili.
Teoremi di corrispondenza: Sono l'insieme del teorema della dualità forte, della dualità debole e dello scarto complementare.
Variabile: In un modello matematico le variabili rappresentano quantità di cui non è noto a priori il valore e di cui si vuole tenere conto nella rappresentazione
Punto di minimo (massimo) globale: Punto nel quale la funzione obiettivo assume valori non maggiori (non minori) di quelli assunti in tutto il suo dominio.
Metodo di scomposizione: Metodo di risoluzione di un problema basato sulla risoluzione di sottoproblemi più semplici.
Sottospazio tangente: Dato un problema di programmazione matematica si è in un punto ammissibile x l'intersezione degli iperpiani tangenti ai vincoli attivi in x. Operativamente se il punto x è regolare può essere determinato come l'insieme delle direzioni ortogonali ai gradienti dei vincoli attivi in x.
Distanza di Hamming: Fra due vettori booleani ad n componenti s1 ed s2 è il numero delle componenti in cui essi differiscono.
Metodo del gradiente: Metodo evolutivo per problemi di ottimizzazione n-dimensionali non vincolati con f.o. derivabile.
Strategia di branching: Scelta delle variabili sulle quali fare branching nell'algoritmo di Branch and Bound.
Algoritmo assolutamente approssimato: Un algoritmo euristico A per un problema P se e solo se esiste una costante k > 0 tale che per ogni istanza I di P risulta |zopt(I)-zA(I)|<=k, dove zopt è il valore della soluzione ottima e zA il valore fornito dall'algoritmo A
Rete di flusso: È un grafo orientato G=(N,A,k) in cui ad ogni arco (i,j) che appartiene ad A è associata una quantità reale detta capacità kij>=0.
Teorema della dualità forte: Se entrambi i problemi di programmazione lineare di una coppia primale-duale sono dotati di soluzioni ammissibili allora entrambi ammettono soluzione ottima e i valori delle soluzioni ottime coincidono.
LINGO: Ambiente di sviluppo di modelli di ottimizzazione. Deve il suo successo al fatto di essere commercializzato unitamente a LINDO.
Algoritmo di Ford-Fulkerson: Algoritmo per il problema in una rete di flusso del massimo flusso (Max flow) da s a t, basato sul teorema del Max flow- Min cut e sull'idea del cammino aumentante.
Forma canonica forte di un PL: Se un problema di PL è in forma standard e soddisfa le condizioni: α) B=I; β) cB=0; γ) b>=0.
Grafo (non orientato): Struttura matematica costituita dalla coppia ( N, E ), dove N è un insieme di nodi (o vertici) ed E è una famiglia di coppie non ordinate di nodi dette lati.
Problema di pianificazione della produzione con più impianti: Problema della distribuzione della forza produttiva tra i prodotti che possono essere fabbricati da più impianti con costi e quote di produzione diversi.
Teorema dello scarto complementare: Data una coppia di PL primale-duale P e D, due soluzioni ammissibili per P e per D, x* e y*, risultano ottime se e solo se xi*, yi* = 0 per ogni xi*, yi*>= 0. (N.B.: Si sta usando la convenzione di indicare nel duale con y1, ... , yn le variabili di slack e con yn+1,...yn+m le variabili naturali ).
GAMS: Ambiente di sviluppo di modelli di ottimizzazione. Il primo, il più conosciuto, il più potente e flessibile, ma il meno friendly per quanto riguarda l'editor e l'esportazione di dati da un foglio elettronico o database. Nell'ultima versione del 1998 è utilizzabile come linguaggio di programmazione ad alto livello.
Algoritmo: Sequenza di istruzioni in grado di determinare per ogni istanza di un dato problema la corrispondente soluzione in un tempo finito.
Ordine di complessità: E' il massimo numero di operazioni elementari necessarie per risolvere qualunque istanza di dimensione n.
Problema di bilanciamento della produzione a multi-periodo: Risolve il problema di distribuzione della forza produttiva in più periodi di produzione tra i prodotti, con una domanda differenziata per ogni prodotto e ogni mese. Si può tenere in magazzino la merce pagando un costo per ogni prodotto conservato: spesso c'è un vincolo di bilancio del magazzino.
Nodi adiacenti: Due nodi di un grafo quando esiste un lato che li collega.
Grafo orientato: Struttura matematica costituita dalla coppia (N, A), dove N è un insieme di nodi ed A è una famiglia di coppie ordinate di nodi dette archi.
Base: Dato un PL in forma standard, si dice di ogni insieme di m colonne linearmente indipendenti della matrice dei vincoli.
Sezione: In una rete di flusso si definisce come una partizione (S,N\S) dell'insieme dei nodi tale che s appartenga ad S e t apparteng a N\S.
Paradosso di Braess: Paradosso del problema del traffico nel quale aggiungendo una strada alla rete si ottiene una situazione di equilibrio con tempo di viaggio peggiore a quello in assenza di tale strada.
Ordine topologico: I nodi di un grafo G=(N,A) numerati in modo che risulta i
Modello matematico: Schematizzazione di un problema attraverso un insieme di simboli, operazioni e relazioni che definiscono i legami tra le variabili e i dati del problema.
Convergenza lineare: Si dice di un algoritmo evolutivo con velocità b se il limite per k->inf. di |x^(k+1)-x*|/|x^k-x*|=b dove x* è il lim->inf. di x^k
Problema del TSP simmetrico: Problema del commesso viaggiatore con matrice dei costi Cij simmetrica, cioè andare dalla città i alla città j ha lo stesso costo che andare dalla città j alla città i, per ogni coppia di città.
Curva di indifferenza: In un problema di programmazione a molti obiettivi sono i luoghi di punti che il decisore reputa ugualmente soddisfacenti.
Problema di teoria delle decisoni: Un problema decisionale si dice problema di teoria delle decisioni se c'è un solo decisore un solo obiettivo, informazioni incerte sui dati ma il decisore può compiere degli esperimenti per aumentare la sua informazione sullo stato di natura.
Destinazione: Punto terminale di una rete di flusso.
Taglio non orientato: Dato un grafo non orientato G = ( N, E ), si definisce taglio indotto da S sottoinsieme di N, e si indica con δ(S), il sottoinsieme di lati di E con un estremo in S e l'altro in N\S (i nodi di S non apparteneti ad N).
Algoritmo g(n)-approssimato: Un algoritmo A per un problema P se e solo se per ogni istanza I di dimensione n risulta |zopt(I)-zA(I)|<=g(n)|zopt(I)| dove zopt è il valore della soluzione ottima e zA il valore fornito dall'algoritmo A.
Massimo flusso (Max flow): In una rete di flusso si definisce come max{j = flusso x uscente da s tale che x sia un flusso ammissibile}.
Pivot: Dato un tableau di un PL è l'operazione fatta attorno all'elemento ahk consistente in: i) dividere la riga h per ahk; ii) combinare linearmente ogni riga i<>h con α (riga h) in modo che aik = 0 per i=0,..., m, i <> h. Permette il cambiamento di base.
Variabile naturale: Si dice di qualunque variabile presente nella formulazione originale di un PL.
Arco scarico: Un arco (i,j) che appartiene ad una rete di flusso G=(N,A,k) dove xij=0.
Slittamento di una attività: In un problema di pianificazione di progetti è definito come Tmax[j]-Tmin[i]-di,j , cioè come l'istante di fine al più tardi di (i,j) meno l'istante di inizio al più presto, meno la durata di (i,j).
Algoritmo di Christofides: Algoritmo ½-approssimato per il problema del TSP simmetrico con costi che soddisfano la disuguaglianza triangolare.
Problema di trasporto e localizzazione di impianti: In un sistema di produzione e distribuzione monoprodotto ci sono n siti candidati ad ospitare unità produttive, ognuna con capacità massima ai, per i=1,...,n. Vi sono m magazzini, ognuno con una domanda bj da soddisfare, per j=1,...,m. Indichiamo con cij >=0 il costo di trasporto di una unità di prodotto dal sito i al magazzino j. L'attivazione di un'unità produttiva nel sito i ha un costo fisso fi>0. Decidere dove aprire le unità produttive e come trasportare il prodotto dalle unità produttive aperte ai magazzini in modo da soddisfare la domanda e da minimizzare i costi di apertura e di trasporto.
Ant system: Metaeuristica basata su una popolazione di agenti che costruiscono simultaneamente soluzioni di un problema applicando un algoritmo greedy con scelte parzialmente casuali (queste ultime permettono ai diversi agenti di costruire soluzioni diverse). L'esecuzione viene ripetuta più volte (ovvero per più generazioni); al termine di ognuna, ma in alcune varianti anche durante l'esecuzione, gli agenti modificano i valori di una funzione ausiliaria (traccia) che a sua volta influenza, insieme ai dati e al caso, le scelte degli agenti. Le modifiche sono volte ad aumentare la probabilità di compiere le scelte che nelle generazioni precedenti hanno portato ai risultati migliori.
Algoritmo di Kruskal: Algoritmo che risolve il problema dell'albero di supporto di costo minimo in un grafo (anche non connesso). La complessità nel caso generale è O(m*logn+n^2) ma può essere ridotta utilizzando una struttura dati più sofisticata.
Problema di sequenziamento ottimale: Ci sono m macchine, k=1,...,m, ed n lavorazioni, j=1,...,n. Ogni lavorazione j richiede l'attraversamento delle macchine nell'ordine 1,2,..., m, ed un tempo di processamento ininterrotto Sjk su ciascuna macchina k. Ogni macchina processa una sola lavorazione alla volta. Decidere in quale ordine processare le lavorazioni su ciascuna macchina in modo da minimizzare il tempo di completamento di tutte le lavorazioni.
Algoritmo di Dantzig-Hitchcock: Algoritmo polinomiale di risoluzione del problema del trasporto. Inizialmente si genera una soluzione ammissibile di base o con la regola di Nord-Ovest o con la regola dei costi minimi o con la regola di Vogel. Si controlla se la soluzione corrente è ottima verificando se i costi ridotti delle variabili fuori base sono non negativi. In caso contrario si genera una soluzione ammissibile di base di costo non maggiore risolvendo un problema di ricerca di cicli su un grafo generato nel modo seguente. Il grafo ha un nodo in corrispondenza di ogni variabile di base e un nodo in corrispondenza di una sola variabile fuori base con costo ridotto negativo (variabile entrante). Si collegano i nodi con un arco se e solo se si trovano sulla stessa riga o colonna. Si cerca un ciclo avente solo 2 nodi per ogni riga e per ogni colonna. Si aumenta di e il valore della variabile entrante e si cambiano in modo opportuno i valori delle variabili del ciclo in modo da soddisfare tutti i vincoli. Si determina il massimo valore di e che non violi la condizione di non negatività sulle variabili. Si considera questa come la nuova soluzione corrente.
Regola triangolare: Regola che consente di calcolare il nuovo valore di un elemento δ del tableau a seguito di un'operazione di pivot sull'elemento α. Indicando con β l'elemento nella stessa colonna di α e riga di γ e con g l'elemento nella stessa colonna di δ e riga di α, il nuovo valore di δ è δ' = δ - βγ/α.
Ciclo orientato: Cammino orientato in cui i due estremi coincidono.
Soluzione di base: Dato un PL in forma standard si dice soluzione con n-m variabili nulle. Notare che può anche non essere ammissibile.
Punto di minimo (massimo) locale: Punto nel quale la funzione obiettivo assume valore non maggiori (non minori) di quelli assunti in un intorno.
Soluzione di un PL: Dato un PL in forma standard si dice ogni vettore x t.c. Ax=b.
Soluzione ottima di un PL: Dato un PL in forma standard si dice di un vettore x* t.c. Ax*=b, x*>=0 e cx*<=cx, per ogni x ammissibile.
Problema del cammino minimo: Dato un grafo orientato G=(N, A) con una funzione di costo c:A->Z, consiste nel determinare un cammino orientato da s a t in modo tale che sia minima la somma degli archi che lo compongono.
Variabile di base: Dato un PL in forma standard, si di una variabile corrispondente ad un elemento della base.
LINDO: Libreria in Fortran con un solutore per la Programmazione Lineare e Programmazione Lineare Intera: è stato molto usato in ambienti di ricerca dagli anni Ottanta per il calcolo di bound di problemi di ottimizzazione.
Convergenza locale: Si dice di un metodo evolutivo se è in grado di arrivare alla soluzione ottima solamente partendo da un intorno della soluzione stessa.
Ciclo: Cammino chiuso in cui i due estremi coincidono.
Problema secondario: Analisi della velocità di convergenza o della complessità computazionale per un metodo di risoluzione di un problema di decisione.
Metodo evolutivo: Metodo di risoluzione di un problema attraverso iterazioni successive a partire da una data soluzione iniziale.
Branch and Bound: Metodo di risoluzione di un problema di ottimizzazione basato sulla enumerazione implicita di tutte le soluzioni. Il metodo comprende due fasi: (a) generazione di una partizione ricorsiva della regione ammissibile (b) risoluzione esplicita o implicita dei sottoproblemi generati dalla partizione.
Rete incrementale: Data una rete di flusso G=(N,A,k) e un flusso ammissibile x è la rete di flusso G=(N,A) ottenuta dalla rete originale G sostituendo ogni arco (i,j) che appartiene ad A con due archi un arco diretto (i,j) di capacità kij =kij -xij >=0, cioè la capacità residua e un arco inverso (j,i) di capacità kji =xij >=0, cioè il flusso su (i,j).
Algoritmo del doppio albero: Algoritmo 1-approssimato per il problema del TSP simmetrico con costi che soddisfano la disuguaglianza triangolare
Problema di localizzazione: Problema di minimizzare il numero di centri di servizio da attivare con il vincolo che ogni utente deve essere "comodamente" collegato ad almeno un centro di servizio; è un particolare problema di set covering.
Problema a molti obiettivi: Problema di decisione con un solo decisore rispetto a più di un obiettivo in presenza di dati certi.
Rilassamento: Un problema (RP) zR=max{f(x): x che appartiene T} si definisce come (PLI) z*=max{cTx: x che appartiene ad S} se (a) S è un sottoinsieme di T (b) cTx <= f(x) per ogni x che appartiene ad S.
Sistema di indipendenza: E' una coppia di insiemi (E,W) dove E è un insieme finito e W è una famiglia di sottoinsiemi di E tale che se I,J sono sottoinsiemi di E e J è sottoinsime di I ed I appartiene ad W allora anche J appartiene a W.
Forma standard di un PL: Un problema di PL della forma min z=cx+d; Ax=b(m); x>=0(n); rank(A)=m<=n.
L-intorno: L'insieme di tutte le soluzioni ammissibili che si trovano ad una distanza al più pari a l dalla soluzione s.
Tableau: Dato un PL in forma standard, è una matrice con m+ 1 righe e n+ 1 colonne in cui la riga 0 contiene, dalla posizione 1 alla posizione n, i coefficienti della f.o. e nella posizione 0 l'opposto del termine noto della f.o., le righe dalla riga 1 alla riga m contengono la matrice dei vincoli e infine la colonna 0 dalla posizione 1 alla posizione m contiene il vettore dei termini noti dei vincoli.
Attività critica: Attività (i,j) per la quale lo slittamento è nullo, ovvero Tmax[j]-Tmin[i]-di,j=0 dove Tmax[j] è l'istante di fine al più tardi di (i,j), Tmin[i] l'istante di inizio al più presto e di,j la durata di (i,j).
Nodi connessi: Due nodi di un grafo quando esiste un cammino che li collega.
Metodo monodimensionale: Metodo evolutivo per funzioni di una sola variabile.
NP-difficile: Un problema che non appartiene a NP ma ogni altro problema in NP è riducibile ad esso in tempo polinomiale.
XPRESS: Libreria in C con un solutore per la Programmazione Lineare e Programmazione Lineare Intera è stata usata in ambienti di ricerca da metà anni Novanta per il calcolo di bound di problemi di ottimizzazione.
Taglio orientato entrante (uscente): Dato un grafo orientato G = (N, A) si definisce taglio entrante indotto da S sottoinsieme di N, e si indica con δ-(S), il sottoinsieme di archi di A con il primo estremo in N\S e il secondo estremo in S. Viceversa si definisce taglio uscente indotto da S sottoinsieme di N, e si indica con δ+(S), il sottoinsieme di archi di A con il primo estremo in S e il secondo estremo in N\S.
Teorema di Balinski-Gomory: Dato un PL in forma canonica debole dopo un numero finito di operazioni di pivot si ha che: i) si è raggiunta la condizione γ) della forma canonica forte; oppure ii) si è ottenuta una riga con il termine noto negativo e tutti gli altri termini non negativi (problema inammissibile).
Gradiente di funzione: Data una funzione, derivabile, è il vettore dato dalle derivate parziali di ogni componente preso singolarmente.
Algoritmo di Floyd-Warshall: Algoritmo polinomiale che determina i cammini minimi tra tutte le coppie di nodi s e t anche in presenza di archi con costo negativo ma senza cicli di lunghezza totale negativa. La complessità è O(n^3).
Istanza: Problema a cui è assegnato un insieme di valori.
Variabile fuori base: Dato un PL in forma standard, si dice di una variabile che non corrisponde ad un elemento della base.
Soluzione ammissibile di un PL: Dato un PL in forma standard si dice ogni vettore x t.c. Ax=b, x>=0.
Problema del trasporto: Risolve il problema del trasferimento a costo minimo delle merci da magazzini sorgenti a clienti destinazione con differenti disponibilità e richieste di merce. Di solito, i costi sono proporzionali alla distanza.
Intorno: Data una soluzione s si definisce come l'insieme di tutte le soluzioni ammissibili che si possono ottenere applicando ad s tutte le mosse possibili (di un certo tipo).
Teorema fondamentale della dualità: Data una coppia di PL primale-duale P e D (zmax e wmin) si può presentare solo uno dei seguenti quattro casi: i) P e D entrambi con soluzioni ottime e i loro valori coincidono; ii) z -> ∞, D inammissibile; iii) w -> -∞, P inammissibile; iv) P e D entrambi inammissibili.
Forma canonica debole di un PL: Se un problema di PL è in forma standard e soddisfa le condizioni: α) B=I; β) cB=0.
Albero: Grafo connesso e senza cicli. Per n vertici ha n- 1 lati. Ammette per ogni coppia di vertici uno e un solo cammino che li connette.
Problema di programmazione matematica: Problema di decisione con un solo decisore rispetto a un solo obiettivo in presenza di dati certi.
Problema di localizzazione di p mediane: Data una rete in cui utenti utilizzano dei centri di servizio si vogliono minimizzare i costi di collegamento utente-centro e di installazione dei centri, con i vincoli che ogni utente deve essere collegato ad un centro, l'utente è collegato ad un centro se e solo se il centro è attivo, vi è un numero massimo di centri da attivare (p), ed ogni centro può servire un numero massimo di utenti.
Stato di natura: Dato un problema decisionale in ambiente incerto lo stato di natura è il vettore delle condizioni ambientali (indicato con ω che appartiene ad Ω) che non sono sotto il controllo del decisore.
Grafo Euleriano: Grafo che possiede un ciclo Euleriano.
Funzione obiettivo (f.o.): Funzione matematica che esprime il criterio di scelta di un problema di decisione.
NP: Indica la classe dei problemi di riconoscimento per i quali esiste una prova del fatto che un'istanza abbia risposta "si" verificabile in tempo polinomiale.
Punto di equilibrio (di Nash): In un problema di teoria dei giochi è una soluzione nella quale nessuno dei decisori ha interesse a cambiare la sua scelta singolarmente cioè a meno che anche gli altri decisori non cambino le proprie scelte.
Algoritmo greedy: Algoritmo nel quale la costruzione della soluzione avviene per passi e ad ogni passo viene fatta la scelta più favorevole, compatibile con i vincoli del problema.
NP-completo: Un problema P se e solo se P appartiene ad NP e P' è proporzionale a P, per ogni P' che appartiene a NP cioè ogni altro problema in NP si riduce ad esso in tempo polinomiale.
Algoritmo ε-approssimato: Un algoritmo A per un problema P se e solo se esiste una costante e > 0 tale che per ogni istanza I risulta |zopt(I)-zA(I)|<=ε|zopt(I)|, dove zopt è il valore della soluzione ottima e zA il valore fornito dall'algoritmo A.
Metodo di bisezione: Metodo evolutivo monodimensionale con velocità di convergenza lineare (1/2) per problemi di ottimizzazione non vincolati che hanno funzione obiettivo derivabile. Il metodo consiste nell'applicare alla derivata della f.o. il metodo del dimezzamento per la determinazione degli zeri di una funzione.
Lato incidente: Dato un grafo non orientato, un lato collagato ad un dato nodo.
Funzione unimodale: Una funzione di una variabile se nell'intervallo in esame ammette un solo minimo (o un solo massimo).
XMP (eXperimental Mathematical Programming): Libreria in Fortran con un solutore per la Programmazione Lineare (Simplesso Primale e Duale) e la Programmazione Lineare Binaria è stato molto usato in ambienti di ricerca negli anni Ottanta e inizi Novanta per il calcolo di bound di problemi di ottimizzazione.
Vincolo attivo: Dato un problema di programmazione matematica si dice quando in un punto ammissibile x è soddisfatto con il segno di uguaglianza.
Regola dei minimi costi: Metodo per trovare una soluzione ammissibile di base per il problema del trasporto che consiste nel considerare nella tabella delle allocazioni corrente la posizione corrispondente all'elemento di costo minimo, nel saturare il vincolo più restrittivo tra quello di riga e quello di colonna e nell'aggiornare l'altro vincolo. Si ripete il procedimento aggiornando la tabella dei costi, finchè tutti i vincoli non sono saturi.
Flusso ammissibile: Data una rete di flusso e due nodi s e t, detti sorgente e destinazione, si dice di una funzione x: A->R tale che: a) per ogni arco (i,j) di A si ha 0<=xij<=kij; b) (flusso uscente da h) - (flusso entrante in h) = 0, per ogni h di N\{s,t}
Problema di trasporto: Problema di trasportare i prodotti di m impianti, ognuno con capacità produttiva ai, i=1,...,m ad n clienti, ognuno con domanda bj da soddisfare, attraverso una rete nella quale cij >=0 è il costo di trasporto di una unità di prodotto dall'impianto i al cliente j. Il problema si risolve in modo efficiente attraverso l'algoritmo di Dantzig-Hitchcock.
Curva di livello: Il luogo geometrico di punti in cui la funzione assume uno stesso valore.
Algoritmo di Dijkstra: Algoritmo polinomiale che determina il cammino minimo da un nodo s a tutti gli altri nodi in grafi con costi non negativi. La complessità è O(n*m) o O(n^2), a seconda della struttura dati utilizzata.
Simulated annealing: Metodo euristico ispirato dall'analogia tra i problemi di ottimizzazione combinatoria e i problemi di meccanica statistica. L'idea di base consiste nel generare uno spostamento casuale a partire dal punto della regione ammissibile analizzato per ultimo accettando di esaminare il nuovo punto non solo se la funzione obiettivo migliora, ma anche quando peggiora. Ciò non avviene sempre, ma con una probabilità data da una legge simile a quella di Boltzmann, dove la "temperatura" diventa un parametro di controllo della procedura.
Dilemma del prigioniero: Problema di teoria dei giochi nel quale si evidenzia che l'ottimo individuale è peggiore dell'ottimo collettivo che è possibile ottenere cooperando.
Soluzione di base degenere: Dato un PL in forma standard, è una soluzione di base con almeno una componente nulla.
Capacità di un settore: In una rete di traffico aereo, è definita come il numero di aerei che i controllori di volo possono monitorare simultaneamente nel settore.
Rilassamento combinatorico: Quando il rilassamento di un problema (PLI) dà luogo ad un problema (RP) di tipo combinatorico.
Flusso attraverso una sezione: Dato un flusso ammissibile x, si dice la quantità j (S) = flusso x uscente da S -flusso x entrante in S.
Matroide: E' un sistema di indipendenza (E,F), con l'ulteriore proprietà che per ogni coppia di insiemi indipendenti I e J tali che |I|=|J|+1, esiste e in I : J unito{e} appartiene ad F.
Programmazione lineare (PL): E' un problema di programmazione matematica con funzione obiettivo e vincoli lineari.
Politica di slot allocation: Spesso è prevedibile che un aeromobile, il cui piano di volo prevede il transito attraverso aree congestionate, incorra in un ritardo in aria prima di arrivare a destinazione se parte in orario. Talora un adeguato ritardo in fase di partenza consente di evitare la congestione ed il conseguente ritardo in aria. Questo riduce i costi delle compagnie aeree e garantisce la sicurezza dello spazio aereo.
Riduzione polinomiale: Dati due problemi P1 e P2 che appartengono ad NP, si dice se esiste un algoritmo per risolvere P1 che chiama un certo numero di volte un ipotetico algoritmo per P2 e risulta polinomiale se si suppone che quello per P2 richieda un'unica unità di tempo.
Problema di assegnamento e sequenziamento: Ci sono m macchine identiche ed n lavorazioni. Ogni lavorazione j, con j=1,...,n, richiede di essere processata da una qualsiasi delle m macchine per un tempo di processamento ininterrotto pj. Ogni macchina processa una sola lavorazione alla volta. Decidere come assegnare le lavorazioni alle macchine in modo da minimizzare il tempo di completamento di tutte le lavorazioni.
Problema illimitato: Un problema di programmazione matematica quando la funzione obiettivo può assumere valori arbitrariamente grandi (per problemi di massimo) o arbitrariamente piccoli (per problemi di minimo) in corrispondenza di soluzioni ammissibili.
Dominanza: In un problema di programmazione a molti obiettivi si dice quando una soluzione è migliore o al più uguale ad un'altra per ogni componente.
Grafo completo: Grafo che contiene un lato per ogni coppia di nodi.
Problema dell'assegnamento: Ci sono n persone in grado di svolgere n attività. Ad ogni persona deve essere assegnata una sola attività ed ogni attività deve venir svolta da una sola persona. Ad ogni coppia (persona i, attività j) è associato un costo cij che esprime le maggiori o minori attitudini di ciascuna persona a svolgere le diverse attività. Decidere come assegnare le attività alle persone in modo tale da minimizzare il costo complessivo.
Accoppiamento perfetto: Dato un grafo G=(N,E) è un sottoinsieme M di E tale che ogni nodo di N è toccato da esattamente un lato di M.
Problema di produzione con lotto minimo: Si vuole determinare un piano di produzione di un singolo prodotto su un orizzonte temporale di n periodi. Per ciascun periodo t=1,...,n sono noti la domanda da soddisfare Dt ed il costo di produzione Ct e di magazzino It, per unità di prodotto. La dimensione del lotto minimo di produzione è pari a L, mentre la capacità massima di produzione è C. Pianficare la produzione in modo da soddisfare la domanda prevista, minimizzando i costi di produzione e magazzino.
Rank reversal: In un problema di programmazione multicriterio il rank reversal consiste nel cambiamento di ordinamento sulla prima posizione dell'ordinamento stesso in seguito alla variazione di un peso.
Funzione di utilità: Per funzioni di utilità si intendono le funzioni matematiche nelle quali sono convertiti gli obiettivi di un problema di programmazione a molti obiettivi in modo da riferirli ad una stessa scala di valori.
Sorgente: In una rete di flusso vengono specificati due vertici s e t. Il nodo iniziale è detto...
Problema della rete di traffico aereo: E' una rete costituita da aeroporti, aerovie e settori (sottoinsiemi dello spazio aereo). Ciascuno di questi elementi ha una capacità limitata.
Direzione ammissibile: Dato un problema di programmazione matematica in un punto ammissibile x, ogni direzione lungo la quale è consentito uno spostamento infinitesimo nel rispetto dei vincoli. Operativamente se il punto x è regolare l'insieme è costituito da D={d appartenente ad R^n: gradiente hi*d=0, per ogni vincolo di uguaglianza hi (x)=0 e gradiente gi*d<=0, per ogni vincolo di disuguaglianza gl(x)<=0 attivo in x }.
Regione paretiana: Insieme delle soluzioni efficienti.
Combinazione convessa: Di due vettori x e y reali è qualunque vettore del tipo: z=λx+(1-λ)y , per ogni λ in [0,1].
Sottografo: Un grafo G'=(N', E') si dice quando N' sottoinsieme di N e il sottoinsieme E' sottoinsieme di E contiene solo lati con entrambi i nodi in N'.
Extraricavo: In un problema di programmazione lineare è il ricavo che si può ottenere per la vendita diretta di un fattore di produzione. Si dimostra che coincidono con i valori ottimi delle variabili di slack del problema duale.
Grafo bipartito: Grafo in cui esiste una partizione (N1,N2) dell'insieme di nodi N t.c. nessun lato collega nodi dello stesso Ni ( i = 1, 2 )
Problema del commesso viaggiatore (Travelling Salesman Problem): Un commesso viaggiatore deve visitare n città esattamente una volta e ritornare al punto di partenza. Il tempo necessario per andare dalla città i alla città j è Cij. Determinare la sequenza di visita delle città in modo da completare il ciclo nel minore tempo possibile.
Euristica Nearest Insertion: Euristica greedy per il TSP in cui viene inserito il nodo più vicino.
Teorema della dualità debole: Data una coppia primale-duale di PL entrambi dotati di soluzioni ammissibili, x per il problema zmax e y per il problema wmin risulta sempre zmax(x) <= wmin(y).
1-albero: Dato un grafo G=(N,E) con N={1,2,..., n}, è un sottografo di G formato da due lati adiacenti al nodo 1 e da un albero sui nodi rimanenti {2,3,...,n}.
Tabu search: E' una metaeuristica per risolvere problemi di ottimizzazione globale, in particolare di ottimizzazione combinatoria. Il metodo consiste nello spostarsi da una soluzione ad un'altra scegliendo la migliore soluzione non proibita nell'intorno della soluzione corrente. Le soluzioni vengono proibite sulla base di certi attributi con lo scopo di evitare cicli e di guidare la ricerca verso regioni inesplorate. Se non ci fossero soluzioni proibite una volta giunti ad un punto di ottimo locale non sarebbe più possibile spostarsi.
Valore del flusso: Data una rete di flusso si dice di j0 = j(s).
Rosa dei venti: Rappresentazione di un problema multicriterio mediante un poligono di k vertici (dove k è il numero di criteri) ognuno dei quali è unito al centro del poligono mediante un raggio. Ogni alternativa è rappresentata da una spezzata che unisce k punti, ognuno su un raggio diverso, in modo tale che la distanza dell' h-mo punto dal centro del poligono sia proporzionale al valore del criterio h per l'alternativa considerata.
Problema di decisione: Problema di scegliere una soluzione in un insieme di soluzioni possibili rispetto ad un determinato criterio.
Rilassamento lineare (o continuo): Dato un programma lineare a numeri interi (PLI) z*=max{cTx: x appartiene a P unito Zn} con P={x spazio reale ad n dimensioni: Ax <= b } indichiamo con ..., il problema (RPL) z=max{cTx: x appartiene a P}.
Regola di Vogel: Metodo per trovare una soluzione ammissibile di base per il problema del trasporto. In corrispondenza ad ogni vincolo (riga e colonna) si determinano i valori assoluti degli scarti tra i due costi migliori. Si seleziona il vincolo (riga o colonna) di scarto massimo e si sceglie la posizione relativa al costo minimo della riga o colonna così selezionata. Viene saturato il vincolo più restrittivo tra quello di riga e quello di colonna e si aggiorna l'altro vincolo. Si ripete il procedimento aggiornando la tabella dei costi, finchè tutti i vincoli non sono saturi.
Formulazione di un PLI: Tutti i diversi modelli di programmazione lineare intera, che individuano lo stesso insieme di soluzioni ammissibili.
CPLEX: Libreria in C con un solutore per la Programmazione Lineare (Simplesso Primale e Duale, Metodi Barriera, Networksimplex) e Programmazione Lineare Intera sviluppata all'Università del Texas e dal 1997 acquisita e sviluppata dalla ILOG, è stata la più usata libreria per il calcolo di bound di problemi di ottimizzazione in ambienti di ricerca dalla sua comparsa agli inizi degli anni Novanta. Tuttora è considerata lo stato dell'arte ed è usata come benchmark di riferimento per molti algoritmi esatti ed euristici.
Problema in ambiente incerto: Problema di decisione con informazioni non certe sui dati.
OSL: Libreria in Fortran con un solutore per la Programmazione Lineare (Simplesso Primale e Duale) e Programmazione Lineare Intera è stato usato in ambienti di ricerca a fine anni Ottanta e inizi Novanta per il calcolo di bound di problemi di ottimizzazione.
Analisi di postottimalità: In un problema di programmazione lineare valori entro cui è possibile fare variare un singolo dato (bj o cj) senza che cambi la composizione della base.
Regione ammissibile: Insieme di tutte le possibili soluzioni di un problema di decisione. Data una formulazione matematica del problema la regione ammissibile è costituita dall'insieme dei punti soddisfacenti tutti i vincoli ed eventuali condizioni di segno o interezza sulle variabili.
Classi di complessità: Permettono di catalogare i problemi di riconoscimento in base alla loro difficoltà ossia in base alla complessità degli algoritmi che li risolvono. Le più importanti sono P, NP, NP-completo e NP-difficile.
Problema inammissibile: Un problema di programmazione matematica quando la sua regione ammissibile è vuota.
Ordine di una funzione: Si dice che una funzione f(n) è dell'ordine di g(n) e si scrive f(n) = O(g(n)) se esiste una costante c > 0 t.c. f(n)<=cg(n), per n sufficientemente grande.
Punto regolare: Un punto ammissibile x si dice se i gradienti dei vincoli attivi in x sono linearmente indipendenti.
Metaeuristica: Struttura generale di euristica per problemi NP -difficili. Esempi sono tabu search, simulated annealing, algoritmi genetici, ant system, reti neurali.
Insieme convesso: Un insieme S sottoinsieme di R dove per ogni x,y di S, z=λx+(1-λ)y in S, con λ in [0,1].
Arco saturo: Un arco (i,j) che appartiene ad una rete di flusso G=(N,A,k) con xij=kij.
MPL: Ambiente di sviluppo di modelli di ottimizzazione. Molto diffuso nella seconda metà degli anni 90 per la facilità con cui si può interfacciare a database tipo Ms Access o fogli elettronici tipo Ms Excel e per il fatto di offrire gratuitamente la versione demo.
Variabile libera: Si dice se non è ristretta in segno.
Metodo delle direzioni ammissibili: Metodo evolutivo che estende il metodo del gradiente a problemi di ottimizzazione n-dimensionali vincolati.
Convergenza globale: Si dice di un metodo evolutivo se è in grado di arrivare alla soluzione ottima partendo da una qualunque soluzione ammissibile.
Dualità: Una coppia di problemi di ottimizzazione, uno di massimo e l'altro di minimo, costituisce una coppia di problemi primale-duale se il valore di ogni soluzione ammissibile del problema di massimo è una limitazione inferiore al valore ottimo del problema di minimo e, viceversa, il valore di ogni soluzione ammissibile del problema di minimo è una limitazione superiore al valore ottimo del problema di massimo.
Intorno 2-opt: Nel problema del TSP è l'intorno nel quale la mossa è lo scambio di una coppia di archi non adiacenti con un'altra coppia e l'inversione degli archi di un tratto del percorso corrente.
Vincolo: Equazione o disequazione che deve essere soddisfatta da ogni soluzione ammissibile di un problema di decisione.
Lower bound: Limite inferiore al valore della soluzione ottima di un problema di ottimizzazione.
Problema dello zaino (knapsack): Dato un contenitore di capacità massima b e n oggetti con valore pj e ingombro wj, j=1,...,n decidere quali oggetti inserire nel contenitore in modo tale da massimizzare il valore totale degli oggetti inseriti rispettando il limite di capacità del contenitore.
Algoritmo polinomiale: Un algoritmo che richiede nel caso peggiore un numero di operazioni elementari f(n)=O(n^d), dove n è la dimensione dell'istanza e d è una costante.
Algoritmo di ricerca locale: Algoritmo che consente di migliorare attraverso una procedura iterativa le soluzioni ottenute con tecniche costruttive (ottenute ad es. con algoritmi di tipo greedy). L'algoritmo consiste nell'individuare modifiche (perturbazioni) alla struttura delle soluzioni ammissibili che ne preservino l'ammissibilità e nell'applicare tali modifiche fintantoché il valore della funzione obiettivo migliora.
Grafo Hamiltoniano: Grafo che possiede un ciclo Hamiltoniano.
Livelli di aspirazione: Nella programmazione a molti criteri sono il massimo o il minimo valore che un certo criterio deve assumere nella soluzione finale secondo il decisore.
Ciclo Hamiltoniano: Ciclo che passa una e una sola volta per ogni nodo del grafo.
Diagramma di Gantt: Diagramma a barre che permette di visualizzare la collocazione temporale delle attività di un progetto. L'asse orizzontale rappresenta il tempo e la lunghezza della barra associata a ogni attività la durata. Nel diagramma al più presto (al più tardi) ogni attività (i,j) inizia all'istante Tmin[i] (Tmax[i]).
Problema di gestione del personale: Dato un insieme di possibili turni di lavoro del personale, si assegna ad ogni lavoratore un turno in modo da soddisfare le esigenze di forza lavoro nell'azienda: è un problema di set covering particolare.
Regola dell'angolo di Nord-Ovest: Metodo per trovare una soluzione ammissibile di base per il problema del trasporto che consiste nel considerare la posizione più in alto a sinistra della tabella delle allocazioni corrente, nel saturare il vincolo più restrittivo tra quello di riga e quello di colonna , nell'aggiornare l'altro vincolo e nel ripetere il procedimento finchè tutti i vincoli non sono saturi.
Upper bound: Limite superiore al valore della soluzione ottima di un problema di ottimizzazione.
Problema dello slot allocation: E' il problema di determinare, in una rete aerea che connette più aeroporti, quanto ciascun volo debba essere ritardato a terra in modo da minimizzare un'opportuna funzione che misura la penalità complessiva associata ai ritardi (a terra e in aria) della rete. La soluzione del problema è il vettore degli slot di partenza ed arrivo assegnati ai voli che utilizzano la rete in esame.
Dimensione di una istanza: E' il numero di bit necessari a codificare un'istanza di un problema.
Programmazione dinamica: Tecnica di risoluzione di un problema di ottimizzazione attraverso la quale una soluzione ottima composta da una sequenza di decisioni elementari viene calcolata in modo ricorsivo (ad es. per risolvere il problema del cammino minimo).
Problema a molti decisori: Problema di decisione con più di un decisore rispetto a un solo obiettivo in presenza di dati certi.
Soluzioni supportate: In un problema di programmazione multicriterio è l'insieme di tutte le soluzioni che si possono ottenere facendo variare i pesi.
Ottimizzazione combinatoria: Problema di programmazione matematica con un numero finito di soluzioni ammissibili.
Capacità di un aeroporto: In una rete di traffico aereo, è una quantità che può essere stimata con buona approssimazione in termini di movimenti all'ora, considerando una serie di parametri.
Mossa: In un algoritmo di ricerca locale un operatore del tipo m: S -> S, dove S è l'insieme delle soluzioni ammissibili.
Problema dello zaino multidimensionale: Sono dati n oggetti, j=1,...,n, ed m risorse, i=1,...,m. Per ogni oggetto j è noto il profitto pj e l'assorbimento unitario wij di risorsa i e per ogni risorsa i è nota la disponibilità totale bi. Stabilire quali oggetti scegliere in modo tale da massimizzare il valore totale degli oggetti scelti rispettando il limite di ciascuna risorsa.
Bound: È una limitazione inferiore di un problema di minimizzazione o una limitazione superiore di un problema di massimizzazione.
Lato di diminuzione: E' un lato che se aggiunto ad un albero di supporto T crea un ciclo in cui esiste un alto lato (diverso) di costo superiore ad esso.
Costi ridotti: In un problema di programmazione lineare in forma standard è il vettore vettore cn=cn-cbB^(-1)N dove la matrice B è formata dalle colonne in base della matrice A dei vincoli, N è l'insieme delle colonne fuori base di A, cB e cN sono rispettivamente le componenti in base e fuori base del vettore dei costi.
Algoritmo genetico: Richiede di specificare tre operazioni (generalmente di tipo probabilistico) su oggetti detti stringhe rappresentabili come vettori di numeri reali: i) riproduzione: combinazione di stringhe nella popolazione per crearne di nuove; ii) mutazione: alterazione spontanea di caratteri in una stringa; iii) crossover: combinazione di stringhe per scambiare i valori creando al loro posto nuove stringhe. Queste operazioni si possono anche combinare tra loro e inoltre la riproduzione e il crossover possono comprendere la competizione all'interno di popolazioni. I passi di un generico algoritmo di questo tipo sono: Inizializza la popolazione; Seleziona i genitori per la riproduzione e le operazioni da eseguire; Esegui le operazioni per generare una popolazione intermedia e valuta la capacità di sopravvivenza dei membri della popolazione Seleziona i membri della popolazione che resteranno nella nuova generazione Ripetere i passi da 1 a 3 sino a quando non è verificato un qualche criterio di arresto.
Curva di deflusso: Funzione crescente che in una rete di traffico lega il tempo di viaggio lungo un arco al numero di veicoli che passano per quell'arco.
Cammino critico: Cammino costituito solo da archi corrispondenti ad attività critiche congiungente il nodo associato all'inizio del progetto a quello associato alla fine del progetto.
Teorema fondamentale della PL: Dato un PL in forma standard: 1) se esiste una soluzione ammissibile, esiste anche una soluzione ammissibile di base; 2) se esiste una soluzione ottima di valore finito, esiste anche una soluzione ottima di base.
Albero di supporto: Dato un grafo G = (N, E), è un albero di G contenente tutti i suoi nodi.
Metodo analitico: Metodo di risoluzione di un problema basato sulla risoluzione di un sistema di equazioni e\o disequazioni.
Formulazione ideale: Di un problema di programmazione lineare a numeri interi (PLI) quella formulazione per la quale il rilassamento continuo (RPL) ha tutti i vertici della regione ammissibile con coordinate intere.
Tasso di sostituzione: Nella programmazione a molti obiettivi variazione di un obiettivo che in corrispondenza ad una variazione unitaria di un altro obiettivo produce una soluzione indifferente.
Cammino non orientato: Dato un grafo non orientato G=(N,E), è una sequenza di lati consecutivi [v1,v2], [v2,v3 ],..., [vk-1, vk] dal nodo v1 al nodo vk appartenenti ad E.
Algoritmo di Prim: Algoritmo greedy che risolve in modo esatto il problema dell'albero di supporto di costo minimo in un grafo connesso. La complessità è O(n^3) o O(n^2) a seconda della struttura dati utilizzata.
Euristica Nearest Neighbourhood: Euristica greedy per il TSP in cui viene aggiunto il nodo più vicino.
Algoritmo euristico: Algoritmo che fornisce una soluzione ammissibile, non necessariamente ottima, di un problema di ottimizzazione.
Problema di teoria dei giochi: Problema di decisione con più di un decisore rispetto a più obiettivi in presenza di dati certi.
Analisi di sensitività: In un problema di programmazione lineare variazione della f.o. in seguito a una variazione infinitesima di un singolo dato (bj o cj).
Cammino Hamiltoniano: Cammino che passa una e una sola volta per ogni nodo del grafo.
Funzione convessa: Sia S un insieme convesso, una funzione f:S->R si dice convessa su S se per ogni x,y di S risulta f(λx+(1-λ)y)<=λf(x)+(1-λ)f(y), per ogni λ in [0,1].
Soluzioni efficienti (o paretiane): In un problema di programmazione a molti obiettivi sono le soluzioni non dominate da nessuna altra. Sono così chiamate dal nome dell'economista svizzero che per primo le studiò alla fine dell'800.
Teorema di convergenza del simplesso: Dato un PL in forma canonica forte si può verificare una e una sola delle seguenti tre possibilità: i) la soluzione di base è ottima (nel tableau i costi ridotti sono non negativi); ii) il problema è illimitato (nel tableau un costo ridotto è negativo e la colonna corrispondente è non positiva); iii) la soluzione è transitoria e dopo un numero finito di passi di pivot ci si riconduce al caso i) o al caso ii).
Problema di copertura con insiemi (set covering): Sono dati un insieme M={1,2,..., m} ed una famiglia di n suoi sottoinsiemi Sj che appartengono ad M, con j in N={1,...,n}. Ad ogni sottoinsieme Sj è associato un costo cj. Si vuole trovare un insieme T sottoinsieme di N tale che l'unione dei sottoinsiemi scelti copra tutti gli elementi di M ed inoltre sia minimo il loro costo totale.
Metodo enumerativo: Metodo di risoluzione di un problema basato sull'enumerazione di tutte le soluzioni possibili.
Algoritmo del simplesso: Algoritmo evolutivo che determina la soluzione ottima di un PL in forma canonica passando da una soluzione ammissibile di base ad un'altra adiacente con valore della f.o. non peggiore oppure stabilisce che il PL è illimitato. Sebbene nel caso peggiore l'algoritmo converga in un numero esponenziale di passi, nel caso medio converge in O(m^3) passi.
Prezzo ombra: In un problema di programmazione lineare è il prezzo che il decisore è disposto a pagare per una unità aggiuntiva della risorsa. Nella teoria della dualità si dimostra che coincide con il valore ottimo della corrispondente variabile duale.
Problema di bilanciamento della produzione: Problema di distribuire la forza produttiva tra i prodotti, con lo scopo di determinare il livello di produzione di ogni singolo prodotto per soddisfare una data domanda.
Cammino orientato: Dato un grafo orientato G=(N,A), è una sequenza di archi consecutivi (v1, v2), (v2, v3),... , (vk-1, vk) dal nodo v1 al nodo vk appartenenti ad A.
Programmazione lineare intera (PLI): Un PLI è un problema di programmazione lineare in cui alcune variabili sono vincolate a essere intere.
Disuguaglianza triangolare: Se, dato un grafo G=(N,E) e i costi cij definiti per ogni arco (i,j) che appartiene ad E, per ogni terna di nodi i,j,k in N vale la relazione cik<=cij+cik.
Critical Path Method (CPM): Tecnica che permette di pianificare un progetto costituito da un insieme di attività con relazioni di precedenza. Il progetto è rappresentato mediante un grafo orientato i cui archi rappresentano le attività, i costi le relative durate. Nella costruzione del grafo possono essere aggiunti archi corrispondenti ad attività fittizie. Il minimo tempo di completamento del progetto corrisponde al valore del cammino di costo massimo del grafo.
Capacità della sezione: Data una rete di flusso e una sezione S, è la quantità k(S) = somma della capacità degli archi uscenti da S.
Problema di riconoscimento: Problema che ammette risposta "si" o "no".
Intorno 3-opt: Nel problema del TSP si definisce l'intorno nel quale la mossa è lo scambio di una terna di archi con un'altra terna con l'accortezza di mantenere l'orientazione prevalente.
Variabile di slack (scarto): Variabile non negativa aggiunta o sottratta ad un vincolo di disuguaglianza per trasformarlo in uno di uguaglianza. La variabile è aggiunta al primo membro del vincolo se è della forma ax <= b, sottratta se è della forma ax >= b.

Start Studying!

Deck Info

Number of cards 223