Ottimizzazione

Ottimizzazione

L'o. costituisce un insieme di metodologie utilizzate nell'analisi e nella soluzione di molti complessi problemi di decisione, progettazione e allocazione di risorse. A partire dagli anni Quaranta del 20° sec., l'o. è divenuta una disciplina fortemente integrata con la ricerca operativa prima e con l'ingegneria gestionale poi. Inoltre, riveste un ruolo essenziale in molte altre branche dell'ingegneria, soprattutto quelle legate alla rappresentazione e progettazione di sistemi complessi, in informatica e in economia. Anche nelle scienze naturali ha assunto importanza come fondamento teorico di modelli descrittivi, comportamentali e di simulazione.

L'o. si riferisce a problemi in cui uno o più decisori, che sono 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 tale da soddisfare sia una serie di regole sul tipo di intervento possibile, sia una serie di requisiti sul comportamento del sistema espressi sotto forma di vincoli, e massimizzare l'utilità individuale o collettiva (ovvero minimizzare il costo complessivo) derivante dal comportamento del sistema e diretta conseguenza quindi delle scelte fatte.

In base a tale definizione, viene dato per scontato che sia disponibile una descrizione del comportamento del sistema in funzione degli interventi possibili. In altre parole, occorre poter simulare il funzionamento del sistema, eventualmente anche solo in termini di prestazioni complessive e di risposta alle decisioni, senza il dettaglio del suo funzionamento interno (approccio black-box). Inoltre, dev'essere disponibile una descrizione abbastanza precisa dell'evoluzione dell'ambiente in cui il sistema si trova a operare, una descrizione di tutti gli interventi possibili da parte dei decisori e di tutti i requisiti interni ed esterni che è necessario rispettare.

Le ragioni del progressivo affermarsi dei metodi di o. sono numerose. Per prima cosa è richiesta, in tutti i settori, una maggiore precisione nelle scelte; una volta, per es., era uso comune nell'ingegneria utilizzare drastiche approssimazioni nei complessi calcoli necessari per la progettazione strutturale. Il risultato veniva poi reso 'sicuro' applicando adeguati coefficienti moltiplicativi, a spese però dell'economicità dell'effettiva realizzazione del progetto. È evidente che l'individuazione di una soluzione 'ottimale' permette una riduzione di costi e quindi una maggiore competitività. Esistono peraltro settori in cui la proposizione di soluzioni approssimate non è neanche pensabile. È questo, per es., il caso della progettazione aerospaziale, in cui l'applicazione dei coefficienti di sicurezza in conseguenza di calcoli approssimati comporterebbe, tra le numerose conseguenze negative, il forte aumento del peso dei velivoli e quindi la necessità di propulsori più potenti e di maggior consumo.

Esiste quindi una reale necessità di sapere se si sta facendo il miglior uso possibile delle risorse disponibili, se è possibile sviluppare un progetto più economico, se i rischi sono contenuti entro limiti accettabili. Fortunatamente, dagli anni Cinquanta del 20° sec. in poi, i progressi metodologici nel campo delle tecniche di o. sono andati di pari passo con la disponibilità di sempre maggiori capacità di calcolo. Ciò ha permesso di fornire un supporto concreto tanto alla progettazione civile e industriale, quanto alle attività di decisione in tutti i settori, da quelli collegati alle imprese, al marketing e alle diverse aree di affari, a quelli connessi con il governo dei sistemi pubblici e sociali, fino al settore militare.

Tuttavia una soluzione 'ottima' non è solo una soluzione più 'precisa'. I metodi di o. comportano infatti la necessità di descrivere matematicamente i fenomeni di interesse e spingono quindi a una miglior comprensione della realtà. È evidente che, a seconda della complessità dei problemi, un certo grado di approssimazione sarà sempre presente; tuttavia, questo aspetto può essere valutato ex ante, ed eventualmente essere raffinato con elaborazioni successive. Inoltre, premesse e ipotesi devono essere esplicitate e quantificate, aumentando così anche il grado di trasparenza delle scelte.

Fasi di ottimizzazione

Tutti i metodi di o. si basano sulla costruzione di un insieme di equazioni e disequazioni in grado di rappresentare il comportamento di un sistema, non necessariamente nella sua interezza, ma esclusivamente per ciò che riguarda gli elementi di interesse dal punto di vista delle scelte da effettuare. L'estensione della rappresentazione matematica dipenderà quindi anche dalla possibilità di isolare e studiare separatamente tali aspetti. In alcuni casi, ciò è impossibile ed è necessario includere nella formulazione un numero di variabili molto più elevato di quanto sarebbe desiderabile, proprio a causa delle forti interazioni tra le variabili stesse. Anche eventuali regole imposte dall'esterno dell'ambiente di decisione, o restrizioni che si ritiene opportuno porre all'evoluzione del sistema, devono essere formulate in termini di equazioni e disequazioni. Nel loro complesso, questo primo insieme definisce le equazioni di vincolo del problema. Esse ne rappresentano compiutamente il comportamento e le reazioni alle scelte, all'interno di uno spazio di decisione e di variabilità opportunamente delimitato (spazio delle soluzioni ammissibili). Altre equazioni vengono utilizzate per rappresentare tutti i costi e i benefici conseguenti alle diverse possibili scelte e alle conseguenti variazioni del sistema e del suo ambiente (funzioni obiettivo).

La costruzione della rappresentazione matematica (formulazione) è la prima delle tre fasi che caratterizzano il processo di ottimizzazione. Le metodologie per formulare correttamente un problema di decisione formano un corpo poco strutturato, in larga misura legato a specifici settori di interesse e basato generalmente su prototipi più o meno adattabili a vari casi. In questa fase un ruolo essenziale è giocato dalla preparazione ed esperienza dell'analista, ovvero dalla sua conoscenza del problema e dalla sua sensibilità rispetto ai diversi aspetti. La fase di formulazione è importante anche perché essa è condizionata e condiziona il tipo di metodologia da utilizzare per la soluzione del problema (seconda fase). È infatti molto delicato il raggiungimento del giusto equilibrio tra la costruzione di un modello capace di descrivere quanto più fedelmente possibile il problema effettivo e l'esigenza di mantenere complessità e struttura entro limiti trattabili con gli strumenti disponibili, tenendo anche conto dei tempi e dei costi connessi con la ricerca della soluzione (o delle soluzioni). In molti casi reali l'o. costituisce un processo interattivo in cui, partendo da un primo modello semplificato del problema, vengono sviluppati, in base ai risultati e a eventuali nuove informazioni ottenute, modelli con gradi di approssimazione crescenti, che forniscono un supporto via via migliore al processo decisionale effettivo.

Le metodologie per scegliere la soluzione migliore fra quelle possibili sono al centro degli interessi dell'o.; nel caso di decisore e funzione obiettivo unici, 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. Per estensione, spesso si utilizza il termine ottimizzazione anche per indicare situazioni in cui viene richiesto di individuare un insieme di soluzioni ammissibili che soddisfino assegnati criteri di bontà, senza necessariamente pretendere di trovare la migliore in assoluto, cosa che può essere priva di senso in presenza, per es., di dati affetti da errore o di incertezza sugli obiettivi. Particolarmente sviluppati sono stati gli aspetti computazionali, che, grazie anche alle crescenti potenze di calcolo disponibili, hanno permesso di risolvere problemi di dimensioni prima ritenute impraticabili.

Le metodologie per utilizzare in modo appropriato il risultato ottenuto (terza fase), trasformandolo in flussi informativi, regole di decisione, prescrizioni e procedure facilmente implementabili attraverso un'adeguata struttura organizzata e di elaborazione delle informazioni, sono oggetto di studio da parte di esperti con diverse competenze e formano un corpo vasto e in genere relativamente rigido, tale da condizionare il risultato e da determinare spesso modifiche significative alla soluzione ottenuta dal processo di ottimizzazione.

Formulazione dei problemi di ottimizzazione

I problemi di o. e i relativi metodi di soluzione si dividono in tre classi principali: programmazione lineare, programmazione non lineare e o. combinatoria. La formulazione più generale di un problema di o. può essere scritta come la minimizzazione di una funzione f(x) con i vincoli h_i(x)=0 e g_j(x)≤0, con i=1,2,…,m, j=1,2,…,r e x∈S.

In questa formulazione x costituisce un vettore n-dimensionale di incognite x=(x₁, x₂, …, x_n), mentre f, h_i e g_j sono funzioni reali delle variabili x₁, x₂, …, x_n; S è un sottoinsieme dello spazio a n dimensioni.

I problemi di programmazione lineare si pongono come casi particolari della suddetta formulazione e sono caratterizzati, come implica il termine stesso, da funzioni lineari. Anche se ciò può sembrare una seria limitazione, le formulazioni in tali termini sono le più utilizzate in pratica. In effetti una quota consistente di problemi reali sono rappresentabili da funzioni obiettivo e da vincoli che sono indiscutibilmente lineari. Per es., un vincolo di budget che rappresenta il limite superiore alla spesa per due o più attività prende la forma ∑_ix_i≤B, ove x_i, con i=1,2,…, costituisce l'ammontare destinato all'attività i-esima, mentre B è il budget. Intrinsecamente lineari sono molti problemi di allocazione di risorse, di o. della produzione, di gestione dei sistemi di trasporto. Inoltre, una funzione non lineare può essere approssimata da una successione di funzioni lineari; naturalmente, la 'linearizzazione' dei problemi ne aumenta fortemente la dimensione in termini di numero di variabili ed equazioni di vincolo da trattare, ma questo aspetto, critico fino a qualche decennio fa, non costituisce oggi una difficoltà considerate sia le enormi potenze di calcolo disponibili a basso costo, sia l'elevatissima efficienza computazionale degli algoritmi di soluzione. Per queste ragioni la classe della programmazione lineare comprende formulazioni e algoritmi adatti a risolvere una gamma vastissima di problemi caratteristici di molti diversi settori di applicazione. I padri della programmazione lineare sono i matematici G.B. Dantzig, L.V. Kantorovich e J. Von Neumann, i quali ne posero le basi di sviluppo teorico negli anni immediatamente successivi alla Seconda guerra mondiale, insieme a quelle di tutto il più ampio settore dell'ottimizzazione. Le loro idee hanno infatti ispirato molti dei concetti centrali della disciplina, come quelli di dualità, decomposizione e convessità.

I problemi di o. combinatoria costituiscono a loro volta un caso particolare, in cui S è un insieme discreto (per es., quello dei soli numeri interi), della formulazione generale sopra esposta. Molto importanti sono i problemi in cui S è costituito solo dai valori 0 e 1. Anche se questo può sembrare un caso estremamente specifico, sono numerose le applicazioni pratiche che rientrano in tale formulazione, soprattutto in campo logistico.

Alcuni modelli tengono conto dell'interazione strategica tra le scelte di decisori diversi che rispondono a diverse funzioni obiettivo. Al loro studio è dedicata la teoria dei giochi, che, oltre ad avere molti rilevanti campi di applicazione, costituisce anche uno dei principali riferimenti metodologici nelle moderne ricerche di economia industriale.

Infine, si usa spesso l'espressione controllo ottimo quando nella formulazione si tiene esplicitamente conto del tempo e quindi della dinamica del sistema nello spazio delle soluzioni ammissibili. Il successo ottenuto dalle diverse classi di modelli dipende essenzialmente dalla loro capacità di soddisfare due requisiti: da un lato, rappresentare adeguatamente il problema; dall'altro, fornire risposte utili al relativo problema di decisione per un insieme significativo di applicazioni. Il tipo di modello effettivamente utilizzato dipende dalle caratteristiche del sistema che si sta analizzando, dagli obiettivi che si stanno perseguendo e dalle tecnologie modellistiche di cui si dispone.

Lo studio teorico delle proprietà strutturali di queste formulazioni viene indicato in generale come programmazione matematica, espressione usata ormai come sinonimo di ottimizzazione, anche se quest'ultimo termine è evidentemente più generale. La programmazione matematica include i teoremi sull'esistenza e le caratteristiche delle soluzioni, lo sviluppo di algoritmi per la ricerca delle soluzioni stesse, lo studio dell'efficienza e delle proprietà di convergenza dei vari algoritmi, l'analisi di aspetti specifici dell'implementazione degli algoritmi su calcolatore, come, per es., quelli del tempo richiesto per l'individuazione di una soluzione (complessità computazionale) e della vicinanza della soluzione trovata a quella ottima (approssimazione). Si assiste sempre più, in particolare, allo sviluppo da un lato di modelli e algoritmi concepiti specificamente per alcune particolari classi di applicazione e, dall'altro, di programmi di calcolo di tipo generale sempre più potenti e personalizzabili per singole applicazioni. Parallelamente si sono sviluppate tecniche per la valutazione delle procedure di soluzione. Complessità e approssimazione possono infatti essere dimostrate a priori (ossia valere per ogni problema di un dato tipo), essere calcolate a posteriori (per l'approssimazione, sulla base di limiti di variazione ricavati per il valore della funzione obiettivo), oppure essere valutate statisticamente (sulla base di assegnate distribuzioni di probabilità dei dati). La ricerca non si limita ai problemi di analisi strutturale del modello e di costruzione di algoritmi di soluzione, ma affronta tutti gli aspetti rilevanti per un uso effettivo dell'o. nei diversi settori applicativi. Sono così divenuti significativi i seguenti aspetti di ricerca: a) i sistemi automatici o interattivi, con l'ausilio dell'elaboratore, di generazione del modello e delle relative procedure di soluzione per specifiche classi di applicazioni; si tratta di facilitare attraverso supporti informatici di vario tipo la formulazione del problema da parte di un utente, anche non specialista di modelli, in un formato adatto alla sua risoluzione, e di guidarlo quindi verso la scelta degli algoritmi più idonei; b) l'integrazione con data-base e sistemi informativi da un lato e con l'intero processo decisionale dall'altro, per la realizzazione di sistemi di supporto alle decisioni e alla gestione; si tratta di facilitare l'uso di modelli (sia sviluppati ad hoc, sia scelti in una 'libreria' continuamente aggiornata) consentendo all'utente di definire solo alcune caratteristiche dei dati necessari, che vengono poi reperiti (e almeno parzialmente verificati) automaticamente dal sistema, sulla base del particolare processo decisionale in esame, e di poter quindi effettuare rapidamente prove ripetute con scenari di riferimento modificati; c) l'individuazione di strutture organizzative in grado di implementare e rendere operative le soluzioni ottenute in specifici ambienti applicativi; si tratta di tradurre i risultati ottenuti attraverso il processo di o. in procedure effettivamente utilizzabili in un particolare contesto organizzativo, anch'esso almeno parzialmente da definire, da parte di operatori anche non specialisti di modelli, senza degradare significativamente la soluzione. Dalla classica formulazione del processo di o. come ricerca di un valore per un assegnato insieme di variabili di decisione, in modo da soddisfare un insieme assegnato di vincoli e ottimizzare un'assegnata funzione obiettivo, si passa a formulazioni più articolate, direttamente legate agli aspetti implementativi.

Dal punto di vista applicativo, i problemi di o. più antichi sono legati a questioni di geometria e di fisica. Non a caso i fondamenti del calcolo variazionale sono stati posti, tra gli altri, da J. Kepler nella Nova stereometria doliorum vinarorum (1615), stimolato dall'imprecisione con cui veniva calcolata la capacità delle botti di vino. Solo in tempi più recenti lo studio si è esteso, in modo sempre più formalizzato, a tutte le fasi della vita organizzata: organizzazione della produzione in un'industria manifatturiera, gestione dei flussi di traffico in una rete di trasporto, dimensionamento e gestione del traffico in una rete di trasmissione dati, pianificazione dei lavori di costruzione di un edificio, attribuzione di compiti al personale in una struttura alberghiera, controllo del traffico aereo, controllo ottimo integrato di un sistema di bacini idrici, gestione delle operazioni in un sistema di elaborazione dell'informazione, progettazione di un profilo alare che produca il compromesso ottimo tra resistenza dell'aria e portanza, scelta di investimenti, localizzazione sul territorio di impianti di produzione e loro dimensionamento, instradamento di messaggi in un sistema informativo, progettazione di circuiti integrati con dimensioni minime, progettazione ottima di filtri analogici per le altissime frequenze, pianificazione ottima delle attività di un'azienda, sequenziamento di compiti su una macchina utensile o in un centro servizi, determinazione della soddisfacibilità o meno di un insieme di relazioni logiche. In campo gestionale e produttivo ha acquistato crescente rilevanza il problema degli agenti autonomi, in cui le variabili sono controllate da diversi centri di decisione. Si utilizzano in questo caso modelli di o. articolati in più livelli. Bisogna individuare innanzi tutto l'insieme di problemi che caratterizzano i singoli centri di decisione, ciascuno con propri vincoli e obiettivi, in modo tale che l'insieme delle decisioni ottime locali produca una soluzione complessiva che soddisfi i vincoli globali e sia globalmente buona. In generale, vincoli e obiettivi locali dipenderanno dalle informazioni disponibili localmente riguardo allo stato del sistema o alle decisioni di altri, ottenute o direttamente dagli altri centri oppure da stazioni intermedie di raccolta e di diffusione dell'informazione. Il costo/tempo di gestione dei flussi informativi e decisionali può diventare facilmente un elemento critico del funzionamento dell'intero sistema e risulta così a sua volta un aspetto da ottimizzare. La questione della soluzione locale dei diversi problemi di o. è di secondo livello e ha caratteristiche diverse rispetto a quella della soluzione del problema globale; la soluzione del problema locale deve essere ammissibile rispetto alle risorse, generalmente limitate, del corrispondente centro di decisione; deve inoltre essere orientata a produrre soluzioni globalmente accettabili, piuttosto che localmente ottime; deve infine corrispondere il più possibile alle modalità operative richieste localmente per raggiungere la soluzione. Le articolazioni multilivello del processo di o. hanno portato allo sviluppo di metodologie più vicine a quelle utilizzate nella progettazione in ambito tecnico, in cui l'obiettivo prevalente consiste nella realizzazione di strutture operative in grado di gestire operazioni per soddisfare al meglio assegnate specifiche, piuttosto che a quelle tipiche della programmazione matematica.

bibliografia

Functional analysis, optimization and mathematical economics: a collection of papers dedicated to the memory of Leonid Vitalevich Kantorovich, ed. L.J. Leifman, New York 1990.

A. Sassano, Modelli e algoritmi della ricerca operativa, Milano 1998.

R. Fletcher, Practical methods of optimization, New York 2000.

M.D. Intriligator, Mathematical optimization and economic theory, Philadelphia 2002.

D. Ashlock, Evolutionary computation for modeling and optimization, New York, 2005.

C.R. Bector, S. Chandra, J. Dutta, Principles of optimization theory, Oxford 2005.

Recent advances in optimization, ed. A. Seeger, New York, 2006.