ottimizzazione

In matematica applicata, e in particolare nella teoria delle decisioni, problemi di o., le questioni attinenti alla ricerca dei criteri di scelta tra diverse opzioni o di determinazione del valore di particolari parametri, di solito riconducibile alla ricerca del massimo o del minimo di funzioni che costituiscono la rappresentazione matematica del problema

Soluzione dei problemi di ottimizzazione

La ricerca delle tecniche più adatte alla soluzione dei problemi di o. ha ricevuto un grande impulso, con l’avvento dei calcolatori, che permettono di risolvere numericamente, in modo esatto o approssimato, problemi che prima, per la loro complessità, o per il numero delle variabili e delle funzioni implicate si sottraevano a ogni trattazione.

Tipici problemi di o. vincolata, a variabili non negative e con vincoli che spesso sono approssimabili da funzioni lineari, sono i problemi della ricerca operativa; chimica, fisica e ingegneria, invece, danno spesso origine a problemi di o. libera, con funzioni obiettive molto lontane dalla linearità. I metodi più usati per la soluzione di problemi di o. libera o vincolata, che non si prestano ai procedimenti classici dell’analisi, sono iterativi. Se il problema consiste nella ricerca di un minimo locale di una funzione F(x) di n variabili x₁, x₂, …, x_n, tali metodi si fondano sulle iterazioni: x⁽ⁱ⁺¹⁾=x⁽ⁱ⁾+α_is⁽ⁱ⁾, dove s⁽ⁱ⁾ è un vettore correttivo e la costante α_i è determinata usualmente in modo tale da minimizzare la funzione F(x⁽ⁱ⁾+α_is⁽ⁱ⁾). Considerando x⁽ⁱ⁾ come punto in uno spazio n-dimensionale, s⁽ⁱ⁾ rappresenta la direzione dell’esplorazione e x⁽ⁱ⁺¹⁾ è il punto ottimale lungo tale direzione. Se F è differenziabile, s è in generale funzione del gradiente g(x), ossia del vettore le cui componenti sono date dalle derivate parziali ∂F/∂x_n.

Il più antico di questi metodi è il metodo di Cauchy, che consiste nel porre semplicemente s=−g. È stato però osservato che tale metodo, dopo le prime iterazioni, che conducono a rapidi miglioramenti, diventa presto insoddisfacente. Risultati migliori si ottengono con un metodo proposto da W.C. Davidon, in cui s⁽ⁱ⁾=−H⁽ⁱ⁾g⁽ⁱ⁾, dove le H⁽ⁱ⁾ sono matrici quadrate definite positive che approssimano l’inversa della matrice hessiana, cioè della matrice d’ordine n i cui elementi sono le derivate parziali seconde della F(x). Per quanto riguarda i problemi di o. vincolata (➔ programmazione), si cerca di ricondursi, mediante opportune trasformazioni, a problemi di o. libera.

Teoria delle decisioni

Nell’o., uno o più decisori, posti di fronte a un sistema sul quale possono intervenire e di cui si suppone noto il comportamento conseguente agli interventi, scelgono le proprie strategie di azione in modo da: soddisfare una serie di regole sul tipo di intervento possibile, soddisfare una serie di requisiti sul comportamento del sistema espressi sotto forma di vincoli, massimizzare l’utilità individuale o collettiva (ovvero minimizzare il costo complessivo) derivante dal comportamento del sistema e conseguenza quindi delle scelte fatte. Le metodologie per scegliere, fra le soluzioni possibili, la migliore sono al centro degli interessi dell’o.: la soluzione ottima (non necessariamente unica) corrisponde al massimo o al minimo di una funzione e le decisioni che producono tale valore sono dette decisioni ottime. Si tratta di una di;sciplina all’incrocio fra diversi settori metodologici e applicativi: matematica, economia, ingegneria, informatica, automazione. I problemi di o. più antichi sono legati a quesiti di geometria e di fisica (per es., trovare nel piano la linea di lunghezza assegnata che racchiude l’area massima). Solo in tempi più recenti lo studio si è diffuso, in modo sempre più formalizzato, a tutte le fasi della vita organizzata. Fra le sue applicazioni: organizzazione della produzione in un’industria manifatturiera; pianificazione dei lavori di costruzione di un edificio; controllo del traffico aereo; controllo ottimo integrato di un sistema di bacini idrici; gestione delle operazioni in un sistema di elaborazione; scelta di investimenti; progettazione di circuiti integrati con dimensioni minime; progettazione ottima di filtri analogici per le altissime frequenze.

A lungo si sono occupati di o. persone che si collocavano in altri settori di attività; a partire dagli anni 1940 si è sviluppato un settore disciplinare autonomo, in simbiosi con la ricerca operativa, da cui è difficilmente separabile, nata anch’essa come disciplina autonoma negli stessi anni. Il problema è sia quello di dare una rappresentazione razionale di problemi di decisione, formalizzando la struttura intrinseca del processo in esame, sia quello di mettere a punto strumenti per la risoluzione pratica di tali problemi e lo studio delle loro proprietà. I modelli di o. formano un insieme vasto e articolato; i più diffusi sono quelli in cui è presente un solo decisore e una sola funzione rispetto a cui ottimizzare. Sono però largamente studiati anche modelli con obiettivi multipli e con decisori multipli. Particolarmente importanti, in quest’ultima classe di modelli, sono quelli basati sulla teoria dei giochi. Nel caso ricorrente in cui le variabili decisionali siano controllate da diversi centri di decisione autonomi, i relativi modelli di o. sono articolati in più livelli. Bisogna individuare innanzitutto l’insieme dei problemi di decisione locali che caratterizzano i singoli centri di decisione, ciascuno con propri vincoli e obiettivi (tutti da determinare), in modo tale che l’insieme delle decisioni ottime locali produca una soluzione che soddisfi i vincoli globali e sia globalmente buona. Come molti e diversificati sono i problemi affrontati, altrettanto numerosi e differenziati sono gli algoritmi di soluzione utilizzati.

Tra i modelli con singolo decisore e singolo obiettivo grande diffusione hanno avuto, in particolare, quelli relativi a problemi lineari, a problemi differenziabili e a problemi discreti. I modelli lineari sono i modelli che hanno segnato, verso la fine degli anni 1940, la nascita dell’o. come disciplina autonoma. Si tratta essenzialmente di problemi con variabili che possono assumere valori reali qualsiasi, funzione obiettivo espressa da una equazione lineare, vincoli espressi da equazioni o disequazioni lineari. Una delle caratteristiche di questi problemi, dovuta alla presenza delle disequazioni, è che l’ottimo si trova in un punto non differenziabile. Per questi problemi esistono metodi di soluzione particolarmente efficienti e affidabili. Per quanto riguarda la complessità, i modelli lineari sono generalmente polinomiali (lo è per es. il metodo degli ellissoidi, un algoritmo proposto dal matematico sovietico L.G. Chačjan nel 1979), anche se gli algoritmi più diffusi sono basati sul metodo del simplesso, che ha un comportamento nel caso peggiore esponenziale. I modelli differenziabili sono i modelli più antichi, strettamente legati alla risoluzione di equazioni. Si tratta essenzialmente di modelli con variabili che possono assumere valori reali qualsiasi, funzione obiettivo espressa da una equazione (tipicamente non lineare), non vincolati, oppure con vincoli espressi da equazioni o disequazioni (lineari o non lineari). Un caso di particolare significato è quello dei problemi convessi, in cui ottimi locali e globali coincidono. Gli eventuali punti non differenziabili sono tali da consentire comunque l’uso delle derivate nella ricerca dell’ottimo, che è, tipicamente, un ottimo locale. I modelli discreti sono un insieme molto articolato, con origini e campo di applicazione diversificato. Si tratta essenzialmente di problemi con variabili che possono assumere solo valori in un insieme discreto (spesso finito, per es. formato dai soli valori 0 e 1), funzione obiettivo espressa da una equazione (in genere lineare), vincoli espressi da equazioni e disequazioni (in genere lineari). Spesso questi problemi si presentano in un formato in cui, oltre a equazioni e disequazioni, sono presenti relazioni logiche, relazioni topologiche, relazioni di appartenenza a insiemi variamente definiti. Una trasformazione efficiente in un formato basato su equazioni e disequazioni non è sempre immediata e non è detto sia conveniente in termini di algoritmo risolutivo. La soluzione è normalmente affrontata caso per caso, può essere anche molto complessa e viene spesso affrontata con euristiche e metodi approssimati. I problemi combinatori, di ottimo su grafi e a numeri interi, hanno avuto un notevole sviluppo con l’affermarsi dell’informatica, le cui funzioni sono essenzialmente di tipo binario, e con l’evoluzione dei modelli gestionali, in cui vengono affrontati problemi relativi a processi decisionali complessi nei sistemi organizzati.

Per risolvere problemi di decisione nel formato di problemi di ottimo, è stata messa a punto nel corso del tempo una grande varietà di algoritmi, essenzialmente riconducibili ad alcune idee fondamentali relativamente semplici: greedy, ricerca locale e ricerca globale. Gli algoritmi di tipo greedy («ghiotto») sono basati su un ordinamento del processo decisionale complessivo in una sequenza di decisioni elementari, che sono relativamente semplici da prendere una volta prese tutte le decisioni precedenti, e che non vengono più modificate. Questi algoritmi sono tipicamente molto efficienti e vi sono importanti casi in cui essi trovano la soluzione ottima. Le tecniche di programmazione dinamica per problemi di decisione sequenziali e gli algoritmi di determinazione di cammini o alberi ottimi su grafi rientrano in genere in questa categoria. Gli algoritmi di ricerca locale sono basati sulla definizione di una funzione intorno, che, a ogni soluzione ammissibile del problema di decisione, associa un insieme di soluzioni ammissibili, fra cui sia semplice trovare quella ottima. L’algoritmo procede quindi, a partire da una soluzione ammissibile, per passi successivi, associando alla soluzione corrente tale insieme, cercando l’ottimo, spostandosi sulla nuova soluzione e così via, fino a quando l’ottimo trovato non coincide con la soluzione che lo ha generato. Questi algoritmi sono tipicamente abbastanza efficienti e vi sono importanti casi in cui essi trovano la soluzione ottima. Il metodo del simplesso per la programmazione lineare e il metodo del gradiente per l’o. differenziabile sono casi di algoritmi di ricerca locale. Gli algoritmi di ricerca globale sono basati sull’idea di controllare sempre l’intera regione ammissibile del problema di ottimo, eventualmente decomponendola in parti di più semplice gestione, sempre però considerate nel loro insieme. In questa categoria rientrano gli algoritmi branch and bound («dividi e limita») per i problemi discreti (in cui la regione ammissibile viene via via suddivisa in parti sempre più piccole), gli algoritmi poliedrali per la programmazione lineare a numeri interi (in cui la regione ammissibile viene via via ristretta all’inviluppo convesso delle soluzioni intere) e gli algoritmi probabilistici (basati sulla generazione casuale o pseudocasuale di valori).

Gli studi successivi

Gli sviluppi di maggiore rilevanza degli anni 1990 hanno riguardato sostanzialmente tre aspetti: i principi ispiratori, gli sviluppi teorici e la pratica applicativa. Per quanto riguarda il primo aspetto, una caratteristica è quella di ricercare nuovi approcci utilizzando le analogie con altri processi presenti in natura e studiati in altri settori disciplinari quali la fisica, la biologia, la neuropsicologia, le scienze naturali. Ciò ha prodotto nuovi paradigmi che si sono tradotti in nuovi algoritmi. Esempi significativi sono le tecniche di simulate annealing (ispirate al meccanismo con cui attraverso successivi riscaldamenti e raffreddamenti di un materiale si riescono a raggiungere livelli energetici più bassi), gli algoritmi genetici (basati su meccanismi di ricombinazione più o meno casuale di soluzioni, del tipo di quelli operanti nei processi biologici evolutivi), le reti neurali (il cui principio ispiratore è quello del funzionamento del sistema nervoso umano e del cervello), gli algoritmi comportamentali (che cercano di riprodurre il comportamento di animali, come per es. le formiche, o altre entità biologiche nella ricerca di un cammino).

Per quanto riguarda il secondo aspetto, vi sono state significative evoluzioni teoriche in molti settori dell’o., in particolare sviluppando contesti metodologici in grado di includere aspetti implementativi tradizionalmente al di fuori degli interessi dell’o. e di recepire obiettivi e modi di operare più articolati di quelli generalmente utilizzati. Esempi di questi risultati sono la modellazione degli algoritmi di simulate annealing come catene di Markov e la teoria della complessità computazionale sviluppata per gli algoritmi di ricerca locale, che hanno permesso di studiare in modo più approfondito la struttura combinatoria di molti problemi di o. discreta.

Per quanto riguarda il terzo aspetto, la capacità di risolvere problemi applicativi di grandi dimensioni è aumentata in modo rilevante, grazie al progresso dei sistemi informatici e delle procedure di calcolo. Inoltre, sono migliorate la qualità delle interfacce utente e la capacità di integrare il modello di o. in contesti di vario tipo, rendendo lo strumento modellistico più flessibile e affidabile (➔ linguaggio; algoritmo).