glossario07 02 02ginex.indivia.net/ftp/pub/uni/algoritmi/glossarioAlgo.pdfalgoritmo 1-approssimato...

23
Glossario Accoppiamento perfetto: dato un grafo G=(N,E) un accoppiamento perfetto è un sottoinsieme M E tale che ogni nodo di N è toccato da esattamente un lato di M. [ Lezione 24 ] Albero: grafo connesso e senza cicli. Un albero di n vertici ha n - 1 lati. Un albero ammette per ogni coppia di vertici uno e un solo cammino che li connette. [ Lezione 3 ] Albero di branching: vedere Branch and Bound. [ Lezione 23 ] Albero di supporto: dato un grafo G = ( N, E ), un albero di supporto di G è un albero di G contenente tutti i suoi nodi. [ Lezione 3 ] Algoritmo: sequenza di istruzioni in grado di determinare per ogni istanza di un dato problema la corrispondente soluzione in un tempo finito. [Lezione 2] Algoritmo assolutamente approssimato: un algoritmo euristico A è detto assolutamente approssimato per un problema P se e solo se esiste una costante k > 0 tale che per ogni istanza I di P risulta |z opt (I)-z A (I)| k , dove z opt è il valore della soluzione ottima e z A il valore fornito dall’algoritmo A . [ Lezione 24 ] Algoritmo del doppio albero: algoritmo 1-approssimato per il problema del TSP simmetrico con costi che soddisfano la disuguaglianza triangolare. [ Lezione 24 ] 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 converge in un numero esponenziale di passi, nel caso medio converge in O( m 3 ) passi. [ Lezione 13 ] Algoritmo di Christofides: algoritmo ½-approssimato per il problema del TSP simmetrico con costi che soddisfano la disuguaglianza triangolare. [ Lezione 24 ] 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

Transcript of glossario07 02 02ginex.indivia.net/ftp/pub/uni/algoritmi/glossarioAlgo.pdfalgoritmo 1-approssimato...

Glossario

Accoppiamento perfetto:dato un grafo G=(N,E) un accoppiamento perfetto è un sottoinsieme M ⊆ Etale che ogni nodo di N è toccato da esattamente un lato di M. [Lezione 24]

Albero:grafo connesso e senza cicli. Un albero di n vertici ha n - 1 lati. Un alberoammette per ogni coppia di vertici uno e un solo cammino che li connette.[Lezione 3]

Albero di branching:vedere Branch and Bound. [Lezione 23]

Albero di supporto:dato un grafo G = ( N, E ), un albero di supporto di G è un albero di Gcontenente tutti i suoi nodi. [Lezione 3]

Algoritmo:sequenza di istruzioni in grado di determinare per ogni istanza di un datoproblema la corrispondente soluzione in un tempo finito. [Lezione 2]

Algoritmo assolutamente approssimato:un algoritmo euristico A è detto assolutamente approssimato per un problemaP 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 valorefornito dall’algoritmo A . [Lezione 24]

Algoritmo del doppio albero:algoritmo 1-approssimato per il problema del TSP simmetrico con costi chesoddisfano la disuguaglianza triangolare. [Lezione 24]

Algoritmo del simplesso:algoritmo evolutivo che determina la soluzione ottima di un PL in formacanonica passando da una soluzione ammissibile di base ad un’altra adiacentecon valore della f.o. non peggiore oppure stabilisce che il PL è illimitato.Sebbene nel caso peggiore l’algoritmo converge in un numero esponenzialedi passi, nel caso medio converge in O( m3 ) passi. [Lezione 13]

Algoritmo di Christofides:algoritmo ½-approssimato per il problema del TSP simmetrico con costi chesoddisfano la disuguaglianza triangolare. [Lezione 24]

Algoritmo di Dantzig-Hitchcock:algoritmo polinomiale di risoluzione del problema del trasporto. Inizialmentesi genera una soluzione ammissibile di base o con la regola di Nord-Ovest ocon la regola dei costi minimi o con la regola di Vogel. Si controlla se lasoluzione corrente è ottima verificando se i costi ridotti delle variabili fuoribase sono non negativi. In caso contrario si genera una soluzione ammissibiledi base di costo non maggiore risolvendo un problema di ricerca di cicli su ungrafo generato nel modo seguente. Il grafo ha un nodo in corrispondenza diogni variabile di base e un nodo in corrispondenza di una sola variabile fuoribase con costo ridotto negativo (variabile entrante). Si collegano i nodi conun arco se e solo se si trovano sulla stessa riga o colonna. Si cerca un cicloavente solo 2 nodi per ogni riga e per ogni colonna. Si aumenta di ε il valoredella variabile entrante e si cambiano in modo opportuno i valori dellevariabili del ciclo in modo da soddisfare tutti i vincoli. Si determina il

massimo valore di ε che non violi la condizione di non negatività sullevariabili. Si considera questa come la nuova soluzione corrente. [Lezione 17]

Algoritmo di Dijkstra:algoritmo polinomiale che determina il cammino minimo da un nodo s a tuttigli altri nodi in grafi con costi non negativi. La complessità è O(nm) o O(n2),a seconda della struttura dati utilizzata.[ Lezione 5]

Algoritmo di Floyd-Warshall:Algoritmo polinomiale che determina i cammini minimi tra tutte le coppie dinodi s e t anche in presenza di archi con costo negativo ma senza cicli dilunghezza totale negativa. La complessità è O(n3). [Lezione 5]

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 camminoaumentante. [Lezione 7]

Algoritmo di Kruskal:algoritmo che risolve il problema dell'albero di supporto di costo minimo inun grafo (anche non connesso). La complessità nel caso generale èO(mlogn+n2) ma può essere ridotta utilizzando una struttura dati piùsofisticata. [Lezione 4]

Algoritmo di Prim:algoritmo greedy che risolve in modo esatto il problema dell'albero disupporto di costo minimo in un grafo connesso. La complessità è O(n3) oO(n2) a seconda della struttura dati utilizzata. [Lezione 4]

Algoritmo di ricerca locale:algoritmo che consente di migliorare attraverso una procedura iterativa lesoluzioni ottenute con tecniche costruttive (ottenute ad es. con algoritmi ditipo greedy). L’algoritmo consiste nell’individuare modifiche (perturbazioni)alla struttura delle soluzioni ammissibili che ne preservino l’ammissibilità enell’applicare tali modifiche fintantoché il valore della funzione obiettivomigliora. [Lezione 25]

Algoritmo ε- approssimato:un algoritmo A è un algoritmo ε- approssimato per un problema P se e solo seesiste una costante ε > 0 tale che per ogni istanza I risulta|zopt(I)-zA(I)|≤ ε|zopt(I)|, dove zopt è il valore della soluzione ottima e zA ilvalore fornito dall’algoritmo A. [Lezione 24]

Algoritmo euristico:algoritmo euristico (dal greco scoprire): algoritmo che fornisce una soluzioneammissibile, non necessariamente ottima, di un problema di ottimizzazione.[Lezione 24]

Algoritmo evolutivo:vedere Metodo evolutivo. [Lezione 2]

Algoritmo g(n)-approssimato:un algoritmo A è un algoritmo g (n)-approssimato per un problema P se e solose 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’algoritmoA. [Lezione 24]

Algoritmo genetico:algoritmo ispirato dai meccanismi della genetica proposto per la prima voltanel 1973 da John Holland. Un algoritmo genetico richiede di specificare treoperazioni (generalmente di tipo probabilistico) su oggetti detti stringhe

rappresentabili come vettori di numeri reali: i) riproduzione: combinazione distringhe nella popolazione per crearne di nuove; ii) mutazione: alterazionespontanea di caratteri in una stringa; iii) crossover : combinazione di stringheper scambiare i valori creando al loro posto nuove stringhe. Questeoperazioni si possono anche combinare tra loro e inoltre la riproduzione e ilcrossover possono comprendere la competizione all’interno di popolazioni.I passi di un generico algoritmo genetico sono:0. Inizializza la popolazione1. Seleziona i genitori per la riproduzione e le operazioni da eseguire2. Esegui le operazioni per generare una popolazione intermedia e valuta la

capacità di sopravvivenza dei membri della popolazione3. Seleziona i membri della popolazione che resteranno nella nuova

generazioneRipetere i passi da 1 a 3 sino a quando non è verificato un qualche criterio diarresto. [Lezione 25]

Algoritmo greedy :algoritmo nel quale la costruzione della soluzione avviene per passi e ad ognipasso viene fatta la scelta più favorevole, compatibile con i vincoli delproblema (greedy=ingordo). [Lezione 24]

Algoritmo polinomiale:un algoritmo è polinomiale se richiede nel caso peggiore un numero dioperazioni elementari f(n )=O(nd), dove n è la dimensione dell'istanza e d èuna costante. [Lezione 9]

Analisi di postottimalità:in un problema di programmazione lineare valori entro cui è possibile farevariare un singolo dato (bj o cj) senza che cambi la composizione della base.[Lezione 16]

Analisi di sensitività:in un problema di programmazione lineare variazione della f.o. in seguito auna variazione infinitesima di un singolo dato (bj o cj). [Lezione 16]

Angolo di Nord-Ovest:vedere Regola dell’angolo di Nord-Ovest. [Lezione 17]

Ant system:metaeuristica basata su una popolazione di agenti (formiche) checostruiscono simultaneamente soluzioni di un problema applicando unalgoritmo greedy con scelte parzialmente casuali (queste ultime permettonoai diversi agenti di costruire soluzioni diverse). L’esecuzione viene ripetutapiù volte (ovvero per più generazioni); al termine di ognuna, ma in alcunevarianti anche durante l’esecuzione, gli agenti modificano i valori di unafunzione ausiliaria (traccia) che a sua volta influenza, insieme ai dati e alcaso, le scelte degli agenti. Le modifiche sono volte ad aumentare laprobabilità di compiere le scelte che nelle generazioni precedenti hannoportato ai risultati migliori.[Lezione 25]

Arco:vedere Grafo orientato. [Lezione 3]

Arco saturo:un arco (i,j) ∈ rete di flusso G=(N,A,k) si dice saturo se xij = kij .[Lezione 7]

Arco scarico: un arco (i,j) ∈ rete di flusso G=(N,A,k) si dice scarico se xij = 0 .[Lezione 7]

Assegnamento:vedere Problema dello assegnamento. [Lezione 20]

Attività critica:attività (i,j) per la quale lo slittamento è nullo, ovvero Tmax[j]-Tmin[i]-di,j=0dove Tmax[j] è l’istante di fine al più tardi di (i,j), Tmin[i] l’istante di inizio alpiù presto e di,j la durata di (i,j). [Lezione 6]

Balinski-Gomory:vedere Teorema di Balinski-Gomory. [Lezione 13]

Base:dato un PL in forma standard, si dice base ogni insieme di m colonnelinearmente indipendenti della matrice dei vincoli.[Lezione 11]

Bilanciamento della produzione:vedere Problema di bilanciamento della produzione e Problema dibilanciamento della produzione a multi-periodo. [Lezione 19]

Bound:il bound è una limitazione inferiore di un problema di minimizzazione o unalimitazione superiore di un problema di massimizzazione. [Lezione 14]

Bounds duali (dual bounds):Lower bounds e upper bounds di un PLI. [Lezione 22]

Branch and Bound:Metodo di risoluzione di un problema di ottimizzazione basato sullaenumerazione implicita di tutte le soluzioni. Il metodo comprende due fasi:(a) generazione di una partizione ricorsiva della regione ammissibile(branching)(b) risoluzione esplicita o implicita (bounding) dei sottoproblemi generatidalla partizione.La partizione viene rappresentata mediante una struttura ad albero (albero dibranching), mentre i bounds come etichette sui nodi. [Lezione 23]

Cammino critico:Cammino costituito solo da archi corrispondenti ad attività critichecongiungente il nodo associato all’inizio del progetto a quello associato allafine del progetto. [Lezione 6]

Cammino Hamiltoniano:cammino che passa una e una sola volta per ogni nodo del grafo.[Lezione 25]

Cammino non orientato:dato un grafo non orientato G = ( N, E ), un cammino non orientato dal nodov1 al nodo vk è una sequenza di lati consecutivi [ v1, v2 ], [ v2, v3 ],…, [ vk-1, vk ]appartenenti ad E. [Lezione 3]

Cammino orientato:dato un grafo orientato G = ( N, A ), un cammino dal nodo v1 al nodo vk è unasequenza di archi consecutivi ( v1, v2 ), ( v2, v3 ),… , ( vk-1, vk ) appartenenti adA. [Lezione 3]

Capacità della sezione :data una rete di flusso e una sezione S, si dice capacità della sezione laquantità k(S) = somma della capacità degli archi uscenti da S. [Lezione 7]

Capacità di un aeroporto:

in una rete di traffico aereo, è una quantità che può essere stimata con buonaapprossimazione in termini di movimenti all'ora, considerando una serie diparametri. [Lezione 26]

Capacità di un settore: in una rete di traffico aereo, è definita come il numero di aerei che icontrollori di volo possono monitorare simultaneamente nel settore.[Lezione 26]

Christofides:vedere Algoritmo di Christofides. [Lezione 24]

Ciclo:cammino chiuso in cui i due estremi coincidono. [Lezione 3]

Ciclo Euleriano:ciclo che passa una e una sola volta per ogni arco del grafo. [Lezione 25]

Ciclo Hamiltoniano:ciclo che passa una e una sola volta per ogni nodo del grafo. [Lezione 25]

Ciclo orientato:cammino orientato in cui i due estremi coincidono. [Lezione 3]

Circuito:vedere Ciclo orientato. [Lezione 3]

Classi di complessità:classi che permettono di catalogare i problemi di riconoscimento in base allaloro difficoltà ossia in base alla complessità degli algoritmi che li risolvono.Le classi di complessità più importanti sono P, NP, NP-completo eNP-difficile. [Lezione 9]

Combinazione convessa:una combinazione convessa di due vettori x e y∈ℜn è qualunque vettore deltipo: z=λx+(1-λ)y , ∀ λ∈[0,1]. [Lezione 11]

Convergenza globale:si dice che un metodo evolutivo converge globalmente se è in grado diarrivare alla soluzione ottima partendo da una qualunque soluzioneammissibile. [Lezione 28]

Convergenza lineare:si dice che un algoritmo evolutivo converge linearmente con velocità β se

[Lezione 28]

Convergenza locale:si dice che un metodo evolutivo converge localmente se è in grado di arrivarealla soluzione ottima solamente partendo da un intorno della soluzione stessa.[Lezione 28]

Coppie di soluzioni di base:data una coppia di PL primale-duale P e D, due soluzioni di base per P e perD, x e y, è definita coppia di soluzioni di base se soddisfano l’equazione delloscarto 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 è dettoche siano entrambe ammissibili. [Lezione 15]

dove * lim k

kx x→∞

=1| * |

| * |lim

k

kk

x x

x xβ

+

→∞

−=

Costi ridotti:in un problema di programmazione lineare in forma standard si definiscevettore dei costi ridotti il vettore:

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 lecomponenti in base e fuori base del vettore dei costi. [Lezione 16]

CPLEX:(C-simPLEX) R. Bixby, ILOG, 1991-2001.Libreria in C con un solutore per la Programmazione Lineare (SimplessoPrimale e Duale, Metodi Barriera, Networksimplex) e ProgrammazioneLineare Intera sviluppata all’Università del Texas e dal 1997 acquisita esviluppata dalla ILOG è stata la più usata libreria per il calcolo di bound diproblemi di ottimizzazione in ambienti di ricerca dalla sua comparsa agliinizi degli anni Novanta. Tuttora è considerata lo stato dell’arte ed è usatacome benchmark di riferimento per molti algoritmi esatti ed euristici.[Lezione 18]

Critical Path Method (CPM):tecnica che permette di pianificare un progetto costituito da un insieme diattività con relazioni di precedenza. Il progetto è rappresentato mediante ungrafo orientato i cui archi rappresentano le attività, i costi le relative durate.Nella costruzione del grafo possono essere aggiunti archi corrispondenti adattività fittizie. Il minimo tempo di completamento del progetto corrispondeal valore del cammino di costo massimo del grafo. [Lezione 6]

Curva di deflusso:funzione crescente che in una rete di traffico lega il tempo di viaggio lungoun arco al numero di veicoli che passano per quell’arco. [Lezione 1]

Curva di livello:si definisce curva di livello di una funzione il luogo geometrico di punti incui la funzione assume uno stesso valore. [Lezione 11]

Curva di indifferenza:in un problema di programmazione a molti obiettivi le curve di indifferenzasono i luoghi di punti che il decisore reputa ugualmente soddisfacenti.[Lezione 29]

Dantzig-Hitchcock:vedere Algoritmo di Dantzig-Hitchcock. [Lezione 17]

Destinazione:in una rete di flusso vengono specificati due vertici s e t, detti sorgente edestinazione. [Lezione 7]

Diagramma di Gantt:diagramma a barre che permette di visualizzare la collocazione temporaledelle attività di un progetto. L’asse orizzontale rappresenta il tempo e lalunghezza 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] ).[Lezione 6]

Dijkstra:vedere Algoritmo di Dijkstra. [ Lezione 5]

Dilemma del prigioniero:

1N N Bc c c B N−= −

problema di teoria dei giochi nel quale si evidenzia che l’ottimo individuale èpeggiore dell’ottimo collettivo che è possibile ottenere cooperando.[ Lezione 1]

Dimensione di una istanza:la dimensione di un'istanza I, di un problema, indicata con |I| è il numero dibit necessari a codificarla. [Lezione 9]

Direzione ammissibile:dato un problema di programmazione matematica si definisce direzioneammissibile 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 delle direzioni ammissibiliè costituito daD=d∈ℜn : ∇hi⋅d=0, ∀ vincolo di uguaglianza hi (x)=0 e ∇gl⋅d≤0, ∀ vincolo di disuguaglianza gl (x)≤0 attivo in x .[Lezione 27]

Distanza di Hamming:si chiama distanza di Hamming dH(s1,s2) fra due vettori booleani ad ncomponenti s1 ed s2 il numero delle componenti in cui essi differiscono.[Lezione 25]

Disuguaglianza triangolare:dato un grafo G=(N,E) si dice che i costi cij , definiti per ogni arco (i,j)∈ E,soddisfano la disuguaglianza triangolare se per ogni terna di nodi i,j,k in Nvale la relazione cik≤cij+cik . [Lezione 24]

Dominanza:in un problema di programmazione a molti obiettivi si dice che una soluzionex domina la soluzione x se fh( x ) ≤ fh( x ) ∀ h e ∃ q: fq( x ) < fq( x ).[Lezione 29]

Doppio albero:vedere Algoritmo del doppio albero. [Lezione 24]

Dualità:una coppia di problemi di ottimizzazione, uno di massimo e l’altro diminimo, costituisce una coppia di problemi primale-duale se il valore di ognisoluzione ammissibile del problema di massimo è una limitazione inferiore alvalore ottimo del problema di minimo e, viceversa, il valore di ogni soluzioneammissibile del problema di minimo è una limitazione superiore al valoreottimo del problema di massimo. [Lezione 14]

Dualità debole:vedere Teorema della dualità debole . [Lezione 15]

Dualità forte:vedere Teorema della dualità forte. [Lezione 15]

Euristica:vedere Algoritmo euristico. [Lezione 24]

Euristica Nearest Neighbourhood:euristica greedy per il TSP. [Lezione 24]

Euristica Nearest Insertion:euristica greedy per il TSP. [Lezione 24]

Extraricavo:

in un problema di programmazione lineare l’extraricavo è il ricavo che si puòottenere per la vendita diretta di un fattore di produzione. Si dimostra che gliextraricavi coincidono con i valori ottimi delle variabili di slack del problemaduale. [Lezione 16]

Floyd-Warshall:vedere Algoritmo di Floyd-Warshall. [Lezione 5]

Flusso ammissibile:data una rete di flusso e due nodi s e t, detti sorgente e destinazione, si diceflusso ammissibile da s a t una funzione x: A→ℜ tale che:a) per ogni arco (i,j) ∈ A 0 ≤ xij ≤ k ij ;

b) (flusso uscente da h) – (flusso entrante in h) = 0, per ogni h ∈N\s,t .[Lezione 7]

Flusso attraverso una sezione :dato un flusso ammissibile x, si dice flusso attraverso una sezione (S,N\S) laquantità ϕ (S) = flusso x uscente da S - flusso x entrante in S. [Lezione 7]

Ford-Fulkerson:vedere Algoritmo di Ford-Fulkerson. [Lezione 7]

Forma canonica di un PL:un problema di PL si dice in forma canonica (forte) se è in forma standard ese soddisfa le condizioni:α) B = Iβ) cB = 0γ) b ≥ 0Si dice in forma canonica debole se soddisfa solo le condizioni α) e β).[Lezione 12]

Forma standard di un PL:un problema di PL si dice in forma standard se è della formamin z = cx + dAx = b ( m )x ≥ 0 ( n )rank ( A ) = m ≤ n[Lezione 11]

Formulazione di un PLI:si definiscono formulazioni di un problema (PLI) tutti i diversi modelli diprogrammazione lineare intera, che individuano lo stesso insieme di soluzioniammissibili. [Lezione 22]

Formulazione ideale:si dice formulazione ideale di un problema di programmazione lineare anumeri interi (PLI) quella formulazione per la quale il rilassamento continuo(RPL) ha tutti i vertici della regione ammissibile con coordinate intere.[Lezione 22]

Funzione convessa:sia S un insieme convesso, una funzione f:S→ℜ si dice convessa su S se ∀x,y ∈S risulta f(λx+(1-λ)y)≤λf(x)+(1-λ)f(y) , ∀ λ∈[0,1].[Lezione 11]

Funzione di utilità:per funzioni di utilità si intendono le funzioni matematiche nelle quali sonoconvertiti gli obiettivi di un problema di programmazione a molti obiettivi inmodo da riferirli ad una stessa scala di valori. [Lezione 29]

Funzione obiettivo (f.o.):

funzione matematica che esprime il criterio di scelta di un problema didecisione. [Lezione 2]

Funzione unimodale:una funzione di una variabile si dice unimodale su un intervallo senell'intervallo in esame ammette un solo minimo (o un solo massimo).[Lezione 28]

GAMS:(General Algebraic Modelling System), R.Rosenthal, 1985-1998.Ambiente di sviluppo di modelli di ottimizzazione. Il primo, il piùconosciuto, il più potente e flessibile (moltissimi solutori sono utilizzabili viaGAMS), ma il meno friendly per quanto riguarda l’editor e l’esportazione didati da un foglio elettronico o database. Nell’ultima versione del 1998 èutilizzabile come linguaggio di programmazione ad alto livello. [Lezione 18]

Gantt:vedere Diagramma di Gantt. [Lezione 9]

Gradiente di funzione:data una funzione f: ℜn → ℜ, derivabile, si definisce gradiente di f il vettore

∇f=

∂∂

∂∂

∂∂

nxf

xf

xf

,...,,21

. [Lezione 27]

Grado di un nodo:dato un grafo, il grado di un nodo è il numero di lati ad esso incidenti.[Lezione 3]

Grafo (non orientato):struttura matematica costituita dalla coppia ( N, E ), dove N è un insieme dinodi (o vertici) ed E è una famiglia di coppie non ordinate di nodi dette lati.[Lezione 3]

Grafo bipartito:grafo in cui esiste una partizione ( N1, N2 ) dell’insieme di nodi N t.c. nessunlato collega nodi dello stesso Ni ( i = 1, 2 ) [Lezione 3]

Grafo completo:grafo che contiene un lato per ogni coppia di nodi. [Lezione 3]

Grafo connesso:un grafo si dice connesso se tutte le coppie di nodi sono connesse.[Lezione 3]

Grafo Euleriano:grafo che possiede un ciclo Euleriano. [Lezione 25]

Grafo Hamiltoniano:grafo che possiede un ciclo Hamiltoniano. [Lezione 25]

Grafo orientato:struttura matematica costituita dalla coppia ( N, A ), dove N è un insieme dinodi ed A è una famiglia di coppie ordinate di nodi dette archi. [Lezione 3]

Greedy:vedere Algoritmo greedy. [Lezione 24]

Hamming:vedere Distanza di Hamming. [Lezione 25]

Insieme convesso:

un insieme S⊆ℜn si dice convesso se ∀x,y∈S, z=λx+(1-λ)y ∈ S, ∀ λ∈[0,1].[Lezione 1]

Intorno:data una soluzione s si definisce intorno N(s) l’insieme di tutte le soluzioniammissibili che si possono ottenere applicando ad s tutte le mosse possibili(di un certo tipo). [Lezione 25]

Intorno 2-opt:nel problema del TSP si definisce intorno 2-opt l’intorno nel quale la mossa èlo scambio di una coppia di archi non adiacenti con un’altra coppia el’inversione degli archi di un tratto del percorso corrente. [Lezione 25]

Intorno 3-opt:nel problema del TSP si definisce intorno 2-opt l’intorno nel quale la mossa èlo scambio di una terna di archi con un’altra terna con l’accortezza dimantenere l’orientazione prevalente. [Lezione 25]

Istanza:si ha una istanza di un problema tutte le volte che ai parametri del problemavengono assegnati dei valori.[Lezione 1]

Knapsack:vedere Problema dello zaino. [Lezione 20]

Kruskal:vedere Algoritmo di Kruskal. [Lezione 4]

Kuhn-Tucker:vedere Teorema di Kuhn-Tucker. [Lezione 27]

L-intorno:chiamiamo l-intorno di una soluzione s l’insieme Nl(s) = s : d(s, s )≤l doved: S×S àℜ+ definisce una funzione distanza in S. Nl(s) è quindi l’insieme ditutte le soluzioni ammissibili che si trovano ad una distanza al più pari a ldalla soluzione s. [Lezione 25]

Lato di diminuzione:sia T un albero di supporto, un lato e ∉ T è detto di diminuzione seaggiungendolo a T si crea un ciclo C ⊆ T ∪ e ed esiste un lato f ∈ C\econ ce < cf. [Lezione 4]

Lato incidente:dato un grafo non orientato, un lato si dice incidente un dato nodo sequest’ultimo è uno dei suoi estremi. [Lezione 3]

Localizzazione:vedere Problema di localizzazione. [Lezione 26]

LINDO:(Linear, INteractive, and Discrete Optimizer) Lindo Inc, 79-98.Libreria in Fortran con un solutore per la Programmazione Lineare eProgrammazione Lineare Intera: è stato molto usato in ambienti di ricercadagli anni Ottanta per il calcolo di bound di problemi di ottimizzazione.[Lezione 18]

LINGO:Lindo Inc, 1996-2001.Ambiente di sviluppo di modelli di ottimizzazione. Deve il suo successo alfatto di essere commercializzato unitamente a LINDO. [Lezione 18]

Livelli di aspirazione:nella programmazione a molti criteri i livelli di aspirazione sono il massimo oil minimo valore che un certo criterio deve assumere nella soluzione finalesecondo il decisore. [Lezione 29]

Lower bound:limite inferiore al valore della soluzione ottima di un problema diottimizzazione. [Lezione 22]

Massimo flusso (Max flow): in una rete di flusso si definisce problema del massimo flusso da s a t, maxϕ= flusso x uscente da s tale che x sia un flusso ammissibile. [Lezione 7]

Matroide:un matroide è un sistema di indipendenza (E,ℑ), con l'ulteriore proprietà cheper ogni coppia di insiemi indipendenti I e J tali che |I|=|J |+1, ∃ e∈I :J∪e∈ℑ. [Lezione 24]

Metaeuristica:struttura generale di euristica per problemi NP –difficili. Esempi dimetaeuristiche sono tabu search, simulated annealing, algoritmi genetici, antsystem, reti neurali. [Lezione 25]

Metodo analitico:metodo di risoluzione di un problema basato sulla risoluzione di un sistemadi equazioni e\o disequazioni. [Lezione 2]

Metodo del gradiente:metodo evolutivo per problemi di ottimizzazione n-dimensionali nonvincolati con f.o. derivabile. La formula iterativa è data da

)(1 kk

kk xfxx ∇−=+ α . Scegliendo il passo kα in modo da minimizzare

( ))( kk xfxf ∇−α rispetto ad α≥0, il metodo converge globalmente.[Lezione 28]

Metodo delle direzioni ammissibili:metodo evolutivo che estende il metodo del gradiente a problemi diottimizzazione n-dimensionali vincolati. La formula iterativa è data da

Il passo αk è determinato minimizzando f(xk+αdk) nel rispetto di tutti i vincolidel problema di partenza. [Lezione 28]

Metodo di bisezione:metodo evolutivo monodimensionale con velocità di convergenza lineare(1/2) per problemi di ottimizzazione non vincolati che hanno funzioneobiettivo derivabile. Il metodo consiste nell'applicare alla derivata della f.o.il metodo di bisezione (o del dimezzamento) per la determinazione degli zeridi una funzione. [Lezione 28]

Metodo di scomposizione:metodo di risoluzione di un problema basato sulla risoluzione disottoproblemi più semplici. [Lezione 2]

1 , dove è soluzione di: k k k kkx x d dα+ = +

m i n ( )

( ) 0 v i n c o l o d i u g u a g l i a n z a ( ) 0

( ) 0 v i n c o l o d i d i s u g u a g l i a n z a ( ) 0 a t t i v o i n

k k

i ik k k

l l

f x d

h x d h x

g x d g x x

∇ = ∀ =

∇ ≤ ∀ ≤

min ( )

( ) 0 vincolo di uguaglianza ( ) 0

( ) 0 vincolo di disuguaglianza ( ) 0

attivo in

k k

k ki i

k kl l

k

f x d

h x d h x

g x d g x

x

∇ = ∀ =

∇ ≤ ∀ ≤

Metodo enumerativo:metodo di risoluzione di un problema basato sulla enumerazione di tutte lesoluzioni possibili. [Lezione 2]

Metodo euristico:vedere Algoritmo euristico. [Lezione 24]

Metodo evolutivo:metodo di risoluzione di un problema attraverso iterazioni successive apartire da una data soluzione iniziale. [Lezione 2]

Metodo monodimensionale:metodo evolutivo per funzioni di una sola variabile.[Lezione 28]

Modello matematico:schematizzazione di un problema attraverso un insieme di simboli, operazionie relazioni che definiscono i legami tra le variabili e i dati del problema.[Lezione 1]

Mossa:in un algoritmo di ricerca locale si definisce mossa m da una soluzione adun’altra un operatore del tipo m: S à S, dove S è l’insieme delle soluzioniammissibili. [Lezione 25]

MPL:(Model Development Environment), Maximal Inc, 1996-2001.Ambiente di sviluppo di modelli di ottimizzazione. Molto diffuso nellaseconda metà degli anni 90 per la facilità con cui si può interfacciare adatabase tipo Ms Access o fogli elettronic tipo Ms Excell e per il fatto dioffrire gratuitamente la versione demo. [Lezione 18]

Nodi adiacenti:due nodi di un grafo si dicono adiacenti se esiste un lato che li collega.[Lezione 3]

Nodi connessi:due nodi di un grafo si dicono connessi se esiste un cammino che li collega.[Lezione 3]

Nord-Ovest:vedere Regola dell’angolo di Nord-Ovest. [Lezione 17]

NP :indica la classe dei problemi di riconoscimento per i quali esiste una provadel fatto che una istanza abbia risposta "si" verificabile in tempo polinomiale.[Lezione 9]

NP-completo:un problema P è NP-completo se e solo se P ∈ NP e P' ∝ P, ∀ P'∈NP cioèogni altro problema in NP si riduce ad esso in tempo polinomiale.[Lezione 9]

NP-difficile:un problema è NP-difficile se non appartiene a NP ma ogni altro problemain NP è riducibile ad esso in tempo polinomiale. [Lezione 9]

Ordine di complessità:l’ordine di complessità di un algoritmo è il massimo numero di operazionielementari necessarie per risolvere qualunque istanza di dimensione n.

L’ordine di complessità viene indicato mediante l’ordine di funzione.[Lezione 3]

Ordine di una funzione:si dice che una funzione f ( n ) è dell’ordine di g( n ) e si scrivef ( n ) = O( g ( n ) ) se esiste una costante c > 0 t.c. f ( n ) <= cg( n ), per nsufficientemente grande. [Lezione 3]

Ordine topologico:si dice che i nodi di un grafo G=(N,A) sono numerati in ordine topologico serisulta i <j per ogni (i,j) ∈ A. [Lezione 6]

OSL:(Optimization Solution Library) J. Forrester, IBM, 87-92.Libreria in Fortran con un solutore per la Programmazione Lineare(Simplesso Primale e Duale) e Programmazione Lineare Intera è stato usatoin ambienti di ricerca a fine anni Ottanta e inizi Novanta per il calcolo dibound di problemi di ottimizzazione. [Lezione 18]

Ottimizzazione combinatoria:problema di programmazione matematica con un numero finito di soluzioniammissibili. [Lezione 2]

P :indica la classe dei problemi di riconoscimento che si possono risolvere intempo polinomiale. [Lezione 9]

Paradosso di Braess:paradosso del problema del traffico nel quale aggiungendo una strada allarete si ottiene una situazione di equilibrio con tempo di viaggio peggiore aquello in assenza di tale strada. [Lezione 1]

Pianificazione della produzione con più impianti:vedere Problema di pianificazione della produzione con più impianti.[Lezione 19]

Pivot:dato un tableau di un PL si definisce pivot ( perno ) attorno all’elemento ahkl’operazione consistente in:i) dividere la riga h per ahk;ii) combinare linearmente ogni riga i ≠ h con α⋅ (riga h) in modo che aik = 0per i = 0, … , m, i ≠ h.L’operazione di pivot permette il cambiamento di base. [Lezione 13]

Politica di slot allocation:spesso è prevedibile che un aeromobile, il cui piano di volo prevede iltransito attraverso aree congestionate, incorra in un ritardo in aria prima diarrivare a destinazione se parte in orario. Talora un adeguato ritardo in fase dipartenza consente di evitare la congestione ed il conseguente ritardo in aria.Questa politica riduce i costi delle compagnie aeree e garantisce la sicurezzadello spazio aereo. [Lezione 26]

Postottimalità:vedere Analisi di postottimalità. [Lezione 16]

Prezzo ombra:in un problema di programmazione lineare il prezzo ombra di una risorsa è ilprezzo che il decisore è disposto a pagare per una unità aggiuntiva dellarisorsa. Nella teoria della dualità si dimostra che il prezzo ombra di unarisorsa coincide con il valore ottimo della corrispondente variabile duale.[Lezione 16]

Prim:vedere Algoritmo di Prim. [Lezione 4]

Problema a molti decisori:problema di decisione con più di un decisore rispetto a un solo obiettivo inpresenza di dati certi. [Lezione 2]

Problema a molti obiettivi:problema di decisione con un solo decisore rispetto a più di un obiettivo inpresenza di dati certi. [Lezione 2]

Problema del cammino minimo:dato un grafo orientato G=(N, A) con una funzione di costo c: A→Z, ilproblema del cammino minimo dal nodo s al nodo t consiste nel determinareun cammino orientato da s a t in modo tale che sia minima la somma degliarchi che lo compongono. [Lezione 5]

Problema del commesso viaggiatore (Travelling Salesman Problem):un commesso viaggiatore deve visitare n città esattamente una volta eritornare al punto di partenza. Il tempo necessario per andare dalla città i allacittà j è Cij. Determinare la sequenza di visita delle città in modo dacompletare il ciclo nel minore tempo possibile. [Lezione 21]

Problema del trasporto:risolve il problema del trasferimento a costo minimo delle merci damagazzini sorgenti a clienti destinazione con differenti disponibilità erichieste di merce. Di solito, i costi sono proporzionali alla distanza.[Lezione 18]

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 allacittà i, per ogni coppia di città.[Lezione 21]

Problema della rete di traffico aereo:è una rete costituita da aeroporti, aerovie e settori (sottoinsiemi dello spazioaereo). Ciascuno di questi elementi ha una capacità limitata. [Lezione 26]

Problema dello assegnamento:ci sono n persone in grado di svolgere n attività. Ad ogni persona deve essereassegnata una sola attività ed ogni attività deve venir svolta da una solapersona. Ad ogni coppia (persona i, attività j) è associato un costo cij cheesprime le maggiori o minori attitudini di ciascuna persona a svolgere lediverse attività. Decidere come assegnare le attività alle persone in modo taleda minimizzare il costo complessivo dell’assegnamento. [Lezione 20]

Problema dello slot allocation:è il problema di determinare, in una rete aerea che connette più aeroporti,quanto ciascun volo debba essere ritardato a terra in modo da minimizzareun’opportuna funzione che misura la penalità complessiva associata ai ritardi(a terra e in aria) della rete. La soluzione del problema è il vettore degli slotdi partenza ed arrivo assegnati ai voli che utilizzano la rete in esame.[Lezione 26]

Problema dello zaino (knapsack):dato un contenitore di capacità massima b e n oggetti con valore pj eingombro wj, j=1,…,n decidere quali oggetti inserire nel contenitore in modotale da massimizzare il valore totale degli oggetti inseriti rispettando il limitedi capacità del contenitore. [Lezione 20]

Problema dello zaino multidimensionale:sono dati n oggetti, j=1,…,n , ed m risorse, i=1,…,m. Per ogni oggetto j è notoil profitto pj e l’assorbimento unitario wij di risorsa i e per ogni risorsa i è notala disponibilità totale bi. Stabilire quali oggetti scegliere in modo tale damassimizzare il valore totale degli oggetti scelti rispettando il limite diciascuna risorsa. [Lezione 20]

Problema di assegnamento e sequenziamento:ci sono m macchine identiche ed n lavorazioni. Ogni lavorazione j, conj=1,…,n, richiede di essere processata da una qualsiasi delle m macchine perun tempo di processamento ininterrotto pj. Ogni macchina processa una solalavorazione alla volta. Decidere come assegnare le lavorazioni alle macchinein modo da minimizzare il tempo di completamento di tutte le lavorazioni.[Lezione 20]

Problema di bilanciamento della produzione:problema di distribuire la forza produttiva tra i prodotti, con lo scopo dideterminare il livello di produzione di ogni singolo prodotto per soddisfareuna data domanda. [Lezione 19]

Problema di bilanciamento della produzione a multi-periodo:risolve il problema di distribuzione della forza produttiva in più periodi diproduzione tra i prodotti, con una domanda differenziata per ogni prodotto eogni mese. Si può tenere in magazzino la merce pagando un costo per ogniprodotto conservato: spesso c’è un vincolo di bilancio del magazzino.[Lezione 19]

Problema di copertura con insiemi (set covering):sono dati un insieme M=1,2,…, m ed una famiglia di n suoi sottoinsiemi Sj

⊆ M, con j ∈ N=1,…,n. Ad ogni sottoinsieme Sj è associato un costo cj.Si vuole trovare un insieme T⊆ N tale che MS

Tjj =

∈∪ , cioè tale che

l’unione dei sottoinsiemi scelti copra tutti gli elementi di M ed inoltre siaminimo il loro costo totale. [Lezione 21]

Problema di decisione:problema di scegliere una soluzione in un insieme di soluzioni possibilirispetto ad un determinato criterio. [Lezione 2]

Problema di gestione del personale:dato un insieme di possibili turni di lavoro del personale, si assegna ad ognilavoratore un turno in modo da soddisfare le esigenze di forza lavoronell’azienda: è un problema di set covering particolare. [Lezione 26]

Problema di localizzazione :problema di minimizzare il numero di centri di servizio da attivare con ilvincolo che ogni utente deve essere “comodamente” collegato ad almeno uncentro di servizio; è un particolare problema di set covering. [Lezione 26]

Problema di localizzazione di p mediane:data una rete in cui utenti utilizzano dei centri di servizio si voglionominimizzare 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 massimodi centri da attivare (p), ed ogni centro può servire un numero massimo diutenti. [Lezione 26]

Problema di ottimizzazione:vedere Problema di programmazione matematica. [Lezione 2]

Problema di pianificazione della produzione con più impianti:

problema della distribuzione della forza produttiva tra i prodotti che possonoessere fabbricati da più impianti con costi e quote di produzione diversi.[Lezione 19]

Problema di programmazione matematica:problema di decisione con un solo decisore rispetto a un solo obiettivo inpresenza di dati certi. [Lezione 2]

Problema di produzione con lotto minimo:si vuole determinare un piano di produzione di un singolo prodotto su unorizzonte temporale di n periodi. Per ciascun periodo t=1,…,n sono noti ladomanda da soddisfare Dt ed il costo di produzione Ct e di magazzino It, perunità di prodotto. La dimensione del lotto minimo di produzione è pari a L,mentre la capacità massima di produzione è C. Pianficare la produzione inmodo da soddisfare la domanda prevista, minimizzando i costi di produzionee magazzino. [Lezione 20]

Problema di riconoscimento:problema che ammette risposta "si" o "no". [Lezione 9]

Problema di sequenziamento ottimale:ci sono m macchine, k=1,…,m, ed n lavorazioni, j=1,…,n. Ogni lavorazione jrichiede l’attraversamento delle macchine nell’ordine 1,2,…, m, ed un tempodi processamento ininterrotto Sjk su ciascuna macchina k . Ogni macchinaprocessa una sola lavorazione alla volta. Decidere in quale ordine processarele lavorazioni su ciascuna macchina in modo da minimizzare il tempo dicompletamento di tutte le lavorazioni. [Lezione 20]

Problema di teoria dei giochi:problema di decisione con più di un decisore rispetto a più obiettivi inpresenza di dati certi. [Lezione 2]

Problema di teoria delle decisoni:un problema decisionale si dice problema di teoria delle decisioni se c’è unsolo decisore un solo obiettivo, informazioni incerte sui dati ma il decisorepuò compiere degli esperimenti per aumentare la sua informazione sullo statodi natura. [Lezione 2]

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à diprodotto dall’impianto i al cliente j. Il problema si risolve in modo efficienteattraverso l’algoritmo di Dantzig-Hitchcock. [Lezione 17]

Problema di trasporto e localizzazione di impianti:in un sistema di produzione e distribuzione monoprodotto ci sono n siticandidati ad ospitare unità produttive, ognuna con capacità massima ai, peri=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à diprodotto dal sito i al magazzino j. L’attivazione di una unità produttiva nelsito i ha un costo fisso fi>0. Decidere dove aprire le unità produttive e cometrasportare il prodotto dalle unità produttive aperte ai magazzini in modo dasoddisfare la domanda e da minimizzare i costi di apertura e di trasporto.[Lezione 21]

Problema duale:vedere Dualità. [Lezione 14]

Problema illimitato:

un problema di programmazione matematica si dice illimitato se la funzioneobiettivo può assumere valori arbitrariamente grandi (per problemi dimassimo) o arbitrariamente piccoli (per problemi di minimo) incorrispondenza di soluzioni ammissibili. [Lezione 12]

Problema in ambiente incerto:problema di decisione con informazioni non certe sui dati. [Lezione 2]

Problema inammissibile:un problema di programmazione matematica si dice inammissibile se la suaregione ammissibile è vuota. [Lezione 12]

Problema primale:vedere Dualità. [Lezione 14]

Problema secondario:analisi della velocità di convergenza o della complessità computazionaleper un metodo di risoluzione di un problema di decisione. [Lezione 2]

Produzione con lotto minimo:vedere Problema di produzione con lotto minimo. [Lezione 20]

Programmazione a molti criteri:programmazione a molti obiettivi con variabili discrete. [Lezione 29]

Programmazione dinamica:tecnica di risoluzione di un problema di ottimizzazione attraverso la qualeuna soluzione ottima composta da una sequenza di decisioni elementari vienecalcolata in modo ricorsivo (ad es. per risolvere il problema del camminominimo). [Lezione 6]

Programmazione lineare (PL):un problema di programmazione lineare (o programma lineare) è unproblema di programmazione matematica con funzione obiettivo e vincolilineari. [Lezione 10]

Programmazione lineare intera (PLI):un PLI è un problema di programmazione lineare in cui alcune variabili sonovincolate a essere intere. [Lezione 10]

Punto di equilibrio (di Nash):in un problema di teoria dei giochi un punto di equilibrio è una soluzionenella quale nessuno dei decisori ha interessa a cambiare la sua sceltasingolarmente cioè a meno che anche gli altri decisori non cambino le propriescelte. [Lezione 1]

Punto di minimo (massimo) globale:punto nel quale la funzione obiettivo assume valori non maggiori (nonminori) di quelli assunti in tutto il suo dominio. [Lezione 2]

Punto di minimo (massimo) locale:punto nel quale la funzione obiettivo assume valore non maggiori (nonminori) di quelli assunti in un intorno. [Lezione 2]

Punto regolare:un punto ammissibile x si dice regolare se i gradienti dei vincoli attiviin x sono linearmente indipendenti. [Lezione 27]

Rank reversal:

in un problema di programmazione multicriterio il rank reversal consiste nelcambiamento di ordinamento sulla prima posizione dell'ordinamento stesso inseguito alla variazione di un peso. [Lezione 30]

Regione ammissibile:insieme di tutte le possibili soluzioni di un problema di decisione. Data unaformulazione matematica del problema la regione ammissibile è costituitadall’insieme dei punti soddisfacenti tutti i vincoli ed eventuali condizioni disegno o interezza sulle variabili. [Lezione 2]

Regione paretiana:insieme delle soluzioni efficienti (o paretiane).[Lezione 29]

Regola dei minimi costi:metodo per trovare una soluzione ammissibile di base per il problema deltrasporto che consiste nel considerare nella tabella delle allocazioni correntela posizione corrispondente all’elemento di costo minimo, nel saturare ilvincolo più restrittivo tra quello di riga e quello di colonna e nell’aggiornarel’altro vincolo. Si ripete il procedimento aggiornando la tabella dei costi,finchè tutti i vincoli non sono saturi. [Lezione 17]

Regola dell’angolo di Nord-Ovest:metodo per trovare una soluzione ammissibile di base per il problema deltrasporto che consiste nel considerare la posizione più in alto a sinistra (Nord-Ovest) della tabella delle allocazioni corrente, nel saturare il vincolo piùrestrittivo tra quello di riga e quello di colonna , nell’aggiornare l’altrovincolo e nel ripetere il procedimento finchè tutti i vincoli non sono saturi.[Lezione 17]

Regola di Vogel:metodo per trovare una soluzione ammissibile di base per il problema deltrasporto. In corrispondenza ad ogni vincolo (riga e colonna) si determinano ivalori assoluti degli scarti tra i due costi migliori. Si seleziona il vincolo (rigao colonna) di scarto massimo e si sceglie la posizione relativa al costominimo 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 vincolinon sono saturi. [Lezione 17]

Regola triangolare:regola che consente di calcolare il nuovo valore di un elemento δ del tableaua seguito di una operazione di pivot sull’elemento α. Indicando con βl’elemento nella stessa colonna di α e riga di δ e con γ l’elemento nella stessa

colonna di δ e riga di α, il nuovo valore di δ è αβγ

δδ −=ˆ . [Lezione 13]

Rete di flusso:è un grafo orientato G=(N,A,k) in cui ad ogni arco (i,j) ∈ A è associata unaquantità reale detta capacità kij≥0 . [Lezione 7]

Rete incrementale:data una rete di flusso G=(N,A,k) e un flusso ammissibile x si definisce reteincrementale associata ad x, la rete di flusso G=(N,A) ottenuta dalla reteoriginale G sostituendo ogni arco (i,j) ∈ 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) dicapacità kji =xij ≥0, cioè il flusso su (i,j). [Lezione 7]

Ricerca locale:vedere Algoritmo di ricerca locale. [Lezione 25]

Riduzione polinomiale:dati due problemi P1 e P2 ∈ NP, si dice che P1 si riduce in tempo polinomialea P2 (e si indica con P1 ∝ P2) se esiste un algoritmo per risolvere P1 chechiama un certo numero di volte un ipotetico algoritmo per P2 e risulta polinomiale se si suppone che quello per P2 richieda un’unica unità ditempo. [Lezione 9]

Rilassamento:un problema (RP) zR=maxf(x): x∈T si definisce rilassamentodel problema (PLI) z*=maxcTx: x∈S se:(a) S⊆T(b) cTx ≤ f(x) ∀ x∈S [Lezione 22]

Rilassamento combinatorico:quando il rilassamento di un problema (PLI) dà luogo ad un problema (RP) ditipo combinatorico si parla di rilassamento combinatorico. [Lezione 22]

Rilassamento lineare (o continuo):dato un programma lineare a numeri interi (PLI)z*=maxcTx: x∈P∩ Zn con P=x∈ℜn : Ax ≤ b indichiamo con rilassamentolineare, o continuo, il problema (RPL) zLP=maxcTx: x∈P. [Lezione 22]

Rosa dei venti:rappresentazione di un problema multicriterio mediante un poligono di kvertici (dove k è il numero di criteri) ognuno dei quali è unito al centro delpoligono mediante un raggio. Ogni alternativa è rappresentata da unaspezzata che unisce k punti, ognuno su un raggio diverso, in modo tale che ladistanza dell' h-mo punto dal centro del poligono sia proporzionale al valoredel criterio h per l'alternativa considerata. [Lezione 30]

Scarto complementare:vedere Teorema dello scarto complementare. [Lezione 15]

Set covering:vedere Problema di copertura con insiemi. [Lezione 21]

Sezione:in una rete di flusso si definisce sezione una partizione (S,N \S) dell’insiemedei nodi tale che s ∈S e t ∈ N \S. [Lezione 7]

Simplesso:vedere Algoritmo del simplesso. [Lezione 13]

Simulated annealing:metodo euristico ispirato dall'analogia tra i problemi di ottimizzazionecombinatoria e i problemi di meccanica statistica (simulatedannealing=ricottura simulata). L'idea di base consiste nel generare unospostamento casuale a partire dal punto della regione ammissibile analizzatoper ultimo accettando di esaminare il nuovo punto non solo se la funzioneobiettivo migliora, ma anche quando peggiora. Ciò non avviene sempre macon una probabilità data da una legge simile a quella di Boltzmann, dove la"temperatura" diventa un parametro di controllo della procedura.[Lezione 25]

Sistema di indipendenza:Un sistema di indipendenza è una coppia di insiemi (E,ℑ) dove E è uninsieme finito e ℑ è una famiglia di sottoinsiemi di E tale che se I,J ⊆ E eJ⊆I∈ℑ allora anche J∈ℑ. [Lezione 24]

Slittamento di una attività:

in un problema di pianificazione di progetti lo slittamento di un’attività (i,j) èdefinito come Tmax[j]- Tmin[i]-d i,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). [Lezione 6]

Slot allocation:vedere Problema dello slot allocation. [Lezione 26]

Soluzione ammissibile di un PL:dato un PL in forma standard si dice soluzione ammissibile ogni vettore x t.c.Ax = b, x ≥ 0 . [Lezione 11]

Soluzione di base:dato un PL in forma standard si dice soluzione di base una soluzione con n-mvariabili nulle. Notare che una soluzione di base può anche non essereammissibile. [Lezione 11]

Soluzione di base degenere:dato un PL in forma standard, una soluzione di base degenere è una soluzionedi base con almeno una componente nulla. [Lezione 12]

Soluzione di un PL:dato un PL in forma standard si dice soluzione ogni vettore x t.c. Ax = b .[Lezione 11]

Soluzione ottima di un PL:dato un PL in forma standard si dice soluzione ottima un vettore x* t.c. Ax* =b, x* ≥ 0 e cx* ≤ cx, per ogni x ammissibile. [Lezione 11]

Soluzioni efficienti (o paretiane):in un problema di programmazione a molti obiettivi sono le soluzioni nondominate da nessuna altra. Sono chiamate anche paretiane dal nomedell'economista svizzero Alfredo Pareto che per primo le studiò alla finedell'800. [Lezione 29]

Soluzioni supportate:in un problema di programmazione multicriterio l'insieme delle soluzionisupportate è l'insieme di tutte le soluzioni che si possono ottenere facendovariare i pesi. [Lezione 30]

Sorgente:in una rete di flusso vengono specificati due vertici s e t, detti sorgente edestinazione. [Lezione 7]

Sottografo:un grafo G’ = ( N’, E’ ) si dice sottografo di G = ( N, E ) se N’ ⊆ N e ilsottoinsieme E’ ⊆ E contiene solo lati con entrambi i nodi in N’. [Lezione 3]

Sottospazio tangente:dato un problema di programmazione matematica si definisce sottospaziotangente in un punto ammissibile x l'intersezione degli iperpiani tangenti aivincoli attivi in x . Operativamente se il punto x è regolare il sottospaziotangente può essere determinato come l'insieme delle direzioni ortogonali aigradienti dei vincoli attivi in x , ossiaM=d∈ℜn : ∇hi⋅d=0, ∀ vincolo di uguaglianza hi (x)=0 ∇gl⋅d=0, ∀ vincolo di disuguaglianza gl (x)≤0 attivo in x .[Lezione 27]

Stato di natura:dato un problema decisionale in ambiento incerto lo stato di natura è ilvettore delle condizioni ambientali (indicato con ω∈Ω) che non sono sotto ilcontrollo del decisore. [Lezione 2]

Strategia di branching:scelta delle variabili sulle quali fare branching nell’algoritmo di Branch andBound. [Lezione 23]

Tableau:dato un PL in forma standard, si definisce tableau una matrice con m + 1righe e n + 1 colonne in cui la riga 0 contiene, dalla posizione 1 allaposizione n, i coefficienti della f.o. e nella posizione 0 l’opposto del terminenoto della f.o., le righe dalla riga 1 alla riga m contengono la matrice deivincoli e infine la colonna 0 dalla posizione 1 alla posizione m contiene ilvettore dei termini noti dei vincoli. [Lezione 13]

Tabu search:la tabu search (=ricerca con tabu) è una metaeuristica per risolvere problemidi ottimizzazione globale, in particolare di ottimizzazione combinatoria. Ilmetodo consiste nello spostarsi da una soluzione ad un’altra scegliendo lamigliore soluzione non proibita nell’intorno della soluzione corrente. Lesoluzioni vengono proibite sulla base di certi attributi con lo scopo di evitarecicli e di guidare la ricerca verso regioni inesplorate. Se non ci fosserosoluzioni proibite una volta giunti ad un punto di ottimo locale non sarebbepiù possibile spostarsi. [Lezione 25]

Taglio non orientato:dato un grafo non orientato G = ( N, E ), si definisce taglio indotto da S ⊆ N,e si indica con δ( S ), il sottoinsieme di lati di E con un estremo in S e l’altroin N \ S. [Lezione 3]

Taglio orientato entrante ( uscente ):dato un grafo orientato G = ( N, A ) si definisce taglio entrante indotto daS ⊆ N, e si indica con δ-( S ), il sottoinsieme di archi di A con il primoestremo in N \ S e il secondo estremo in S. Viceversa si definisce tagliouscente indotto da S ⊆ N, e si indica con δ+( S ), il sottoinsieme di archi di Acon il primo estremo in S e il secondo estremo in N \ S. [Lezione 3]

Tasso di sostituzione:nella programmazione a molti obiettivi variazione di un obiettivo che incorrispondenza ad una variazione unitaria di un altro obiettivo produce unasoluzione indifferente. [Lezione 29]

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). [Lezione 15]

Teorema della dualità forte:se entrambi i problemi di programmazione lineare di una coppia primale-duale sono dotati di soluzioni ammissibili allora entrambi ammettonosoluzione ottima e i valori delle soluzioni ottime coincidono. [Lezione 15]

Teorema dello scarto complementare:data una coppia di PL primale-duale P e D, due soluzioni ammissibili per P eper 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 levariabili di slack e con yn+1,…yn+m le variabili naturali ). [Lezione 15]

Teorema di Balinski-Gomory:dato un PL in forma canonica debole dopo un numero finito di operazioni dipivot 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 termininon negativi (problema inammissibile). [Lezione 13]

Teorema di convergenza del simplesso:dato un PL in forma canonica forte si può verificare una e una sola delleseguenti 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 lacolonna corrispondente è non positiva);iii) la soluzione è transitoria e dopo un numero finito di passi di pivot ci siriconduce al caso i) o al caso ii). [Lezione 13]

Teorema di Kuhn-Tucker:sia x un punto di minimo locale per f(x) nella regione ammissibile X esia x punto regolare allora ∃ m coefficienti λi e p coefficientiµl ≥0 t.c.

∑∑==

=∇+∇+∇p

lll

m

iii xgxhxf

11

0)()()( µλ

0)( =xhi

0)( =xg llµ . [Lezione 27]

Teorema fondamentale della dualità:data una coppia di PL primale-duale P e D ( zmax e wmin ) si può presentaresolo 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. [Lezione 15]

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. [Lezione 11]

Teoremi di corrispondenza:sono l’insieme del teorema della dualità forte, della dualità debole e delloscarto complementare. [Lezione 15]

Teoria dei giochi:vedere Problema di teoria dei giochi. [Lezione 2]

Teoria delle decisioni:vedere Problema di teoria delle decisioni. [Lezione 2]

Trasporto e localizzazione di impianti:vedere Problema di trasporto e localizzazione di impianti. [Lezione 21]

Travelling Salesman Problem (TSP):vedere Problema del commesso viaggiatore. [Lezione 21]

1-albero:dato un grafo G=(N,E) con N=1,2,…, n, un 1-albero è un sottografo di Gformato da due lati adiacenti al nodo 1 e da un albero sui nodi rimanenti2,3,…,n. [Lezione 22]

Upper bound:limite superiore al valore della soluzione ottima di un problema diottimizzazione. [Lezione 22]

Valore del flusso: data una rete di flusso si dice valore del flusso ϕ0 = ϕ(s). [Lezione 7]

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.[Lezione 1]

Variabile di base:dato un PL in forma standard, si dice variabile di base una variabilecorrispondente ad un elemento della base. [Lezione 11]

Variabile di slack (scarto):variabile non negativa aggiunta o sottratta ad un vincolo di disuguaglianzaper trasformarlo in uno di uguaglianza. La variabile è aggiunta al primomembro del vincolo se è della forma ax ≤ b, sottratta se è della forma ax ≥ b.[Lezione 11]

Variabile fuori base:dato un PL in forma standard, si dice variabile fuori base una variabile chenon corrisponde ad un elemento della base.[Lezione 11]

Variabile libera:una variabile si dice libera se non è ristretta in segno. [Lezione 11]

Variabile naturale:si dice variabile naturale qualunque variabile presente nella formulazioneoriginale di un PL. [Lezione 11]

Vincolo:equazione o disequazione che deve essere soddisfatta da ogni soluzioneammissibile di un problema di decisione. [Lezione 2]

Vincolo attivo:dato un problema di programmazione matematica un vincolo si dice attivo inun punto ammissibile x se è soddisfatto con il segno di uguaglianza.[Lezione 27]

Vogel:vedere Regola di Vogel. [Lezione 17]

XMP:(eXperimental Mathematical Programming) R. Marsten, U. Arizona, 79-87.Libreria in Fortran con un solutore per la Programmazione Lineare(Simplesso Primale e Duale) e la Programmazione Lineare Binaria è statomolto usato in ambienti di ricerca negli anni Ottanta e inizi Novanta per ilcalcolo di bound di problemi di ottimizzazione. [Lezione 18]

XPRESS, B. Daniels, Dash, 1997-2001.Libreria in C con un solutore per la Programmazione Lineare eProgrammazione Lineare Intera è stata usata in ambienti di ricerca da metàanni Novanta per il calcolo di bound di problemi di ottimizzazione.[Lezione 18]

Zaino:vedere Problema dello zaino. [Lezione 20]