Ottimizzazione

Ottimizzazione

L'o. si basa sull'utilizzazione di un insieme di metodologie derivanti da diverse scienze, anche applicative, quali matematica, economia, ingegneria e informatica. A partire dagli anni Quaranta l'o. ha assunto una connotazione autonoma in simbiosi con la ricerca operativa (v. operativa, ricerca, App. V), da cui è difficilmente separabile, e poi con l'ingegneria gestionale (v. gestionale, ingegneria, in questa Appendice).

Fondamenti

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 e una serie di requisiti sul comportamento del sistema espressi sotto forma di vincoli, e da massimizzare l'utilità individuale o collettiva (ovvero minimizzare il costo complessivo) derivante dal comportamento del sistema e conseguenza quindi delle scelte fatte.

In base a questa 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 (v. simulazione, in questa Appendice) o anche, ove possibile, solo le sue prestazioni complessive, senza il dettaglio del suo funzionamento interno. 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 il funzionamento del sistema deve rispettare. In pratica, non sempre tutto ciò è disponibile fin dall'inizio e l'o. diventa generalmente 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.

Vi sono tre aspetti che caratterizzano il processo di o.: la formulazione del problema, la ricerca della soluzione ottima, l'uso del risultato.

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 di formulazione più o meno adattabili a vari casi.

Le metodologie per scegliere la soluzione migliore fra quelle possibili sono al centro degli interessi dell'o. e le più studiate; 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 solo di soddisfare assegnati criteri di bontà della soluzione, 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 negli ultimi anni sono stati gli aspetti computazionali, che, grazie anche alle crescenti potenze di calcolo disponibili, hanno permesso di risolvere problemi di dimensioni ritenute fino a poco tempo fa impraticabili.

Le metodologie per utilizzare in modo appropriato il risultato ottenuto, 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.

Applicazioni

I problemi di o. più antichi sono legati a questioni 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 è 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. Il punto fondamentale è 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à.

Modelli e algoritmi

I modelli di o. formano un insieme vasto e articolato; i più diffusi sono quelli in cui sono presenti 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 (v. giochi, teoria dei, App. IV). Il successo ottenuto da alcuni modelli dipende 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 (v. modellista matematica, in questa Appendice). 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. Per una classificazione dei modelli di interesse dell'o. e dei relativi algoritmi, v. operativa, ricerca, App. V.

Negli ultimi anni si è assistito a una diffusione dell'uso di strumenti di o., con lo sviluppo da un lato di modelli e algoritmi concepiti specificamente per alcune particolari classi di applicazione, dall'altro di programmi di calcolo di tipo generale sempre più potenti e personalizzabili per singole applicazioni. Parallelamente si sono sviluppate delle tecniche per la valutazione delle procedure di soluzione dei problemi di ottimizzazione. Per valutare gli algoritmi di o. bisogna tener conto di due aspetti: il tempo richiesto per trovare la soluzione (complessità computazionale; v. informatica, App. V) e la vicinanza della soluzione trovata a quella ottima (approssimazione). Complessità e approssimazione possono 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), essere valutate statisticamente (sulla base di assegnate distribuzioni di probabilità dei dati). La ricerca in o. degli ultimi anni 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.

Diventano aspetti significativi 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 di modelli) 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.

Ottimizzazione di processi decisionali multipolari

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 di 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 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 o da stazioni intermedie di raccolta e 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 dev'essere ottenibile con le risorse, generalmente limitate, del centro di decisione locale; deve inoltre essere orientata a produrre soluzioni globalmente accettabili, più che localmente ottime; deve infine corrispondere il più possibile alle modalità operative richieste localmente per raggiungere la soluzione.

Questa articolazione del processo di o. porta verso metodologie più vicine a quelle utilizzate nella progettazione in ambito tecnico, in cui l'obiettivo prevalente consiste nel mettere in piedi strutture operative in grado di gestire delle operazioni per soddisfare al meglio assegnate specifiche, piuttosto che verso le metodologie tipiche della ricerca matematica. In quest'ultimo caso, l'obiettivo prevalente è quello di una completa razionalizzazione del problema con l'individuazione di procedure di soluzione univocamente definite e coerenti con la razionalizzazione raggiunta.

bibliografia

L.A. Johnson, D.C. Montgomery, Operations research in production planning, scheduling and inventory control, New York 1974.

J.A. Bondy, U.S.R. Murty, Graph theory with applications, London 1976, New York 1979².

Computer and job-shop scheduling theory, ed. E.G. Coffman, New York 1976.

E.L. Lawler, Combinatorial optimization, networks and matroids, New York 1976.

Nonlinear programming, ed. R.W. Cottle, C.E. Lemke, Providence 1976.

S.P. Bradley, A.C. Hax, T.L. Magnanti, Applied mathematical programming, Reading (Mass.) 1977.

Design and implementation of optimization software, ed. H.J. Greenberg, Alphen aan den Rijn 1978.

V. Alexéev, V. Tikhomirov, S. Fomine, Commande optimale, Moscou 1979.

M.R. Garey, D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, San Francisco 1979.

M. Gondran, M. Minoux, Graphes et algorithmes, Paris 1979.

E.V. De Nardo, Dynamic programming, Englewood Cliffs (N.J.) 1982.

C.H. Papadimitiou, K. Steiglitz, Combinatorial optimization, Englewood Cliffs (N.J.) 1982.

H.A. Simon, Models of bounded rationality. Collected works from 1937 to 1979, Cambridge (Mass.) 1982.

D.G. Luenberger, Linear and nonlinear programming, New York 1984.

R.T. Rockafellar, Network flows and monotropic optimization, New York 1984.

G.L. Nemhauser, L.A. Wolsey, Integer and combinatorial optimization, New York 1988.

Optimization, ed. G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd, Amsterdam-New York 1989.

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

Paths, flows, and VLSI-Layout, ed. B. Korte, L. Lovász, H.J. Prömel et al., Berlin-New York 1990.

R.K. Ahuja, Th.L. Magnanti, J.B. Orlin, Network flows: theory, algorithms and applications, Englewood Cliffs (N.J.) 1993.

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

L. Woolsey, Integer programming, New York 1998.