OPERATIVA, RICERCA

OPERATIVA, RICERCA

(App. III, II, p. 315; IV, II, p. 669)

Premessa. − La r.o. è una disciplina che, a partire da radici culturali diversificate, ha acquisito soltanto negli anni recenti una precisa identità. Essa può essere definita come la disciplina che studia, su base quantitativa, i modelli concettuali dei processi decisionali connessi al funzionamento dei sistemi organizzati, i metodi per prevedere il comportamento di questi sistemi, in particolar modo al crescere della loro complessità, nonché gli strumenti per valutare a priori le conseguenze di determinate decisioni e per individuare le decisioni che ottimizzano le loro prestazioni. Pertanto il problema comune delle persone che operano in quest'area disciplinare è quello di dare una rappresentazione razionale dei problemi di analisi e decisione che occorre affrontare e di mettere a punto strumenti metodologici e applicativi per la loro risoluzione pratica. Gran parte di questi problemi sono formulati come problemi di ottimizzazione in cui, compatibilmente con certi vincoli, si vuole perseguire al meglio un determinato obiettivo.

Alcuni esempi di problemi di decisione, relativi ad ambienti molto diversi, possono servire a connotare meglio l'ambito di applicazione della r. operativa.

In un ambiente di produzione un problema tipico è quello della gestione dei magazzini. Un magazzino è sostanzialmente un insieme di risorse con un determinato valore che vengono accantonate per un impiego futuro in relazione alla dinamica delle esigenze produttive. Il problema che si pone è quello di determinare nel tempo quale debba essere il livello delle scorte che minimizzano i costi di produzione. Infatti, un basso livello di scorte significa un minore immobilizzo di capitali e un minor costo di gestione del magazzino. In questo caso occorre però effettuare ordini di approvvigionamento più frequenti, per cui i relativi costi (burocratici e operativi) sono più elevati. Un alto livello di scorte riduce ovviamente la frequenza degli ordini e quindi i relativi costi, ma fa aumentare i costi di magazzino. La risposta a questo problema può essere data come soluzione di un problema di ottimizzazione.

Nel campo della progettazione, un problema tipico è rappresentato dalla pianificazione e gestione delle attività. I tempi d'inizio delle attività devono essere scelti in funzione delle loro durate, dei vincoli di precedenza fra le diverse attività, delle risorse utilizzate, in modo da minimizzare i tempi di completamento del progetto e i costi di realizzazione.

Un problema caratteristico dell'ambiente finanziario è quello delle scelte di portafoglio. Data un'assegnata disponibilità di risorse finanziarie e un insieme di opportunità d'investimento con modalità e ritorni noti, decidere quanto e quando investire per le diverse alternative, in modo da massimizzare il guadagno complessivo e soddisfare, eventualmente, altri vincoli.

Un ulteriore esempio di problema, che s'incontra nella pianificazione territoriale, è la localizzazione di centri di servizio. Data la disponibilità di risorse finanziarie, i costi d'installazione, le richieste e le modalità di servizio, il problema è quello di determinare quanti centri attivare, di quali dimensioni e dove collocarli, in modo da ottimizzare le prestazioni del sistema di servizio.

Al di là della differenza fra i vari problemi citati, si può osservare come la metodologia di approccio sia relativamente simile: si cerca sempre d'individuare le informazioni e i dati disponibili, le decisioni da prendere, i vincoli da soddisfare e gli obiettivi da perseguire. La formalizzazione di questo modo di operare e la successiva risoluzione del problema di decisione sono tipici della r.o. e verranno esaminati più approfonditamente nel seguito.

Cenni storici. − Il termine r.o. (traduzione dall'inglese operations research, il cui significato attuale è sostanzialmente equivalente a management science) risale al periodo della seconda guerra mondiale durante la quale alcuni paesi decisero di affrontare con metodi scientifici problemi connessi a operazioni militari. Il governo britannico per primo riunì scienziati di diversi settori disciplinari con l'obiettivo di combinare ricerca tecnologica, organizzativa e relativa alle modalità di svolgimento delle operazioni, in modo da migliorare le prestazioni complessive dell'apparato bellico, non tanto sviluppando nuovi armamenti, quanto migliorando l'impiego di quelli esistenti. Un primo compito fu quello di usare in modo efficace le nuove tecnologie radar che si stavano affermando in quel periodo. Le attività che ne derivarono contribuirono in modo significativo ai successi degli eserciti alleati nella battaglia d'Inghilterra. Il gruppo preposto a tali attività, che aveva cominciato a operare già nel 1937, fu denominato, su proposta di due suoi membri, R. Watson Watt e A.P. Rowe, operational research section. Successivamente venne costituito un altro gruppo con caratteristiche simili, denominato Blackett circus dal nome del responsabile, il fisico P.M.S. Blackett. Il primo compito a esso assegnato fu la regolazione ottimale delle spolette a tempo delle bombe antisommergibile, che produsse un raddoppio della percentuale di bersagli colpiti. Anche negli Stati Uniti, a partire dal 1943, fu creata un'organizzazione simile per occuparsi della guerra sottomarina. L'ingresso degli scienziati statunitensi in quest'area di ricerca portò anche al cambiamento del nome in operations research.

Queste origini spiegano per quale ragione le radici culturali della r.o. affondino nella storia di differenti discipline e come essa si trovi all'incrocio fra diversi settori metodologici e applicativi, alcuni di consolidata tradizione, altri completamente nuovi.

Un primo filone, rilevante per i processi decisionali oggetto della r.o., è quello dell'ottimizzazione. Tale disciplina, originata da problemi di tipo geometrico e di fisica, verso la metà del Settecento cominciò a interessarsi, per merito di alcuni matematici fra cui L. Eulero, a problemi di determinazione di cammini ottimi su grafi e di teoria dei giochi. Nella seconda metà dell'Ottocento nacque la scienza economica come disciplina quantitativa, basata su modelli concettuali rigorosi. Nel tentativo di rappresentare il comportamento degli individui e dei diversi soggetti economici, era essenziale caratterizzare soluzioni efficienti o di equlibrio. Questo fu fatto, fra gli altri, da L. Walras e V. Pareto, supponendo che i soggetti economici ottimizzassero una qualche funzione utilità.

Tra la fine dell'Ottocento e l'inizio del Novecento si ebbe inoltre la nascita della grande industria manifatturiera. Questo fenomeno provocò naturalmente lo sviluppo di studi sistematici sui processi produttivi e sul modo più razionale ed efficiente di gestirli. L'esempio forse più significativo è la scuola creata da F.W. Taylor riguardante il management scientifico dei sistemi di produzione. In effetti la fabbrica è un tipico sistema organizzato, con informazioni relativamente certe e disponibili, e parametri di efficienza ben definiti. È quindi naturale che in tale ambito si siano affermati, in modo più o meno esplicito, i modelli della r. operativa.

Negli anni Trenta questi diversi sviluppi culturali si sono intersecati in modo sempre più organico, producendo nuovi risultati e nuovi filoni di ricerca. L'esempio forse più emblematico è quello di J.L. von Neumann che propose una serie di modelli concettuali per lo studio, fra l'altro, dei processi di crescita economica in condizioni di equilibrio competitivo, dei processi decisionali in ambiente multidecisore, delle modalità di esecuzione di programmi di calcolo. Una delle spinte forse più significative, derivanti da esigenze belliche e dalle esigenze della ricostruzione industriale del dopoguerra, è stata verso la messa a punto di modelli e algoritmi che, al di là dell'interesse teorico, fossero praticamente risolubili in tempi rapidi per i problemi urgenti a cui si doveva far fronte. La nascita di modelli per applicazioni logistiche, sviluppati da premi Nobel quali P.M.S. Blackett e T.C. Koopmans, della programmazione lineare con metodi di soluzione operativamente efficienti (tra i quali il famoso metodo del simplesso proposto da G.B. Dantzig), delle applicazioni industriali della programmazione lineare, sviluppate da una molteplicità di ricercatori e professionisti, fra i quali ricordiamo A. Charnes e V.W. Cooper, furono forse la risposta più immediata a tali esigenze.

Nel dopoguerra la r.o. diventò gradualmente anche un settore di ricerca accademica. Nel 1949 si tenne a Chicago la prima conferenza dal titolo ''Activity analysis of production and allocation'', interamente dedicata a processi decisionali tipici del settore. A tale conferenza, dove furono rappresentate solo alcune delle aree che contribuiranno poi a formare la r.o. moderna, parteciparono nomi prestigiosi fra cui quattro futuri premi Nobel per l'economia. Nel 1952, un gruppo di ricercatori, in una riunione presieduta da Ph.M. Morse, fondò negli Stati Uniti la prima società professionale di r. operativa.

A partire dagli anni Cinquanta i risultati teorici e le applicazioni nei più diversi ambienti applicativi cominciarono a moltiplicarsi. Si sviluppò, stimolato dalla diffusione delle reti di telecomunicazioni, il settore degli algoritmi di ottimizzazione su reti, a cui contribuirono, fra i tanti, L.R. Ford, D.R. Fulkerson e R. Gomory. Nacque inoltre la programmazione dinamica, per merito soprattutto di R.E. Bellman, e si misero a punto i primi metodi di soluzione di problemi discreti. Vennero via via studiati problemi di decisione ottima sempre più complessi, nel cui ambito si affrontarono aspetti multicriterio e multidecisore. Nel frattempo lo sviluppo dell'informatica e l'evoluzione dell'ambiente industriale, che si andava attrezzando per sfruttare le potenzialità di metodologie capaci di una più razionale allocazione e gestione delle risorse, spinsero verso una sempre più capillare presenza degli strumenti della r.o. in azienda (a volte designata con altri nomi: logistica, gestione progetti, ingegneria dei sistemi, ecc.) e verso una rapida crescita del settore disciplinare nel mondo accademico, prevalentemente nell'ambito delle scuole d'ingegneria e di business administration. Alla fine degli anni Sessanta il problema della valutazione dell'efficienza degli algoritmi di soluzione dei problemi di decisione divenne maturo per una trattazione sistematica. Tale maturazione avvenne nel settore dell'ottimizzazione combinatoria per merito soprattutto di S.A. Cook, J. Edmonds e R.M. Karp, ma presto i risultati ottenuti si diffusero in tutti i settori dell'ottimizzazione.

A partire dagli anni Settanta, l'esigenza di risolvere problemi sempre più complessi mise in luce i limiti degli strumenti di risoluzione di tipo generale. L'evoluzione del settore si caratterizzò sempre più per un'articolazione basata su classi di problemi e di metodi specifici per risolverli. Gli approcci tipici della r.o., sempre più specialistici, cominciarono a essere utilizzati nelle applicazioni più diverse, influenzando il modo stesso di affrontare i corrispondenti problemi. Un'ulteriore caratteristica, emersa in questi anni, è stata l'attenzione dedicata, oltre che all'analisi dei singoli problemi, alla possibilità di rappresentare uno stesso problema con modelli diversi in relazione ai diversi possibili punti di vista con cui si guarda il mondo reale. Grazie anche all'evoluzione dei mezzi di elaborazione, le dimensioni dei problemi risolubili sono cresciute rapidamente (insieme con la consapevolezza che il modello è solo un aspetto del processo decisionale) e i modelli della r.o. oggi sono divenuti un elemento abituale delle attività aziendali e della pubblica amministrazione.

Il processo decisionale. − La decisione è il momento conclusivo di un processo di scelta tra due o più possibili alternative di azione, che hanno come scopo il raggiungimento di un obiettivo. Quando i problemi da risolvere e le corrispondenti decisioni sono ben strutturate, allora il processo decisionale può essere gestito in modo scientifico, utilizzando le tecniche e i metodi della r. operativa.

In questo caso le decisioni vengono prese sulla base di una metodologia ben precisa, le cui fasi principali sono le seguenti: a) definizione del problema; b) ricerca di alternative di azione; c) valutazione delle alternative; d) scelta di un'alternativa e sua implementazione.

Queste fasi, anche se ben distinte concettualmente, interagiscono reciprocamente in maniera spesso determinante, per cui alla soluzione del problema si perviene, in genere, attraverso un procedimento iterativo i cui passi, rappresentati nella fig. 1, sono descritti qui di seguito. Nella fig. 2 è descritto il rapporto tra il processo decisionale e questo procedimento iterativo di soluzione.

Definizione del problema. In questa fase si prende coscienza che un problema esiste, se ne determinano le caratteristiche, se ne definiscono con precisione i limiti e la rilevanza nell'organizzazione in esame. Una volta completata l'analisi, il problema viene classificato in una determinata categoria.

Modellizzazione. La modellizzazione (detta anche formulazione) del problema implica la sua concettualizzazione e astrazione in forma matematica. Questa è una delle fasi più complesse e delicate ed è costituita da una serie di attività tra loro collegate. La prima è la determinazione degli obiettivi e consiste essenzialmente nel tradurre gli obiettivi espressi con formulazioni verbali qualitative, e spesso confuse, in precise formulazioni matematiche (funzione obiettivo) che ne chiariscano il reale significato. Ciò implica, in concreto, identificare le variabili d'interesse del problema ed esprimere alcune di esse (variabili dipendenti) in funzione di altre (variabili indipendenti o di decisione).

Una volta definiti in modo formale gli obiettivi, si esprimono mediante relazioni matematiche i legami d'interdipendenza esistenti fra le grandezze in gioco, che talvolta sono note solo parzialmente o date in forma implicita. Si costruisce così un modello matematico del sistema che si sta studiando, sia esso un'impresa, un sistema territoriale o un servizio pubblico. Occorre comunque sottolineare che la costruzione del modello è un'operazione complessa in quanto essa dipende dagli scopi dello studio, dalle caratteristiche della funzione obiettivo e dalle variabili scelte per rappresentare il sistema. Inoltre, una volta costruito il modello, è necessario verificare la precisione con cui esso approssima il comportamento del sistema reale ed eventualmente aggiustare i valori numerici dei suoi parametri fino a ottenere una buona corrispondenza (calibrazione del modello).

Soluzione del modello. Una volta calibrato il modello, per determinare gli interventi da effettuare sul sistema onde conseguire gli obiettivi fissati, occorre trovarne le soluzioni. In taluni casi il modello può dare soluzioni ottime, in altri casi, per l'impossibilità di una formalizzazione completa in termini matematici di obiettivi e vincoli, ci si deve accontentare di soluzioni sub-ottime o comunque ritenute soddisfacenti.

Valutazione della soluzione. Quando i cambiamenti che intervengono nel sistema reale sono tali da richiedere una modifica del modello che lo rappresenta, allora occorre sviluppare procedure atte a determinare rapidamente nuove soluzioni. A tal fine è importante individuare i parametri critici del modello, cioè quelli le cui variazioni danno luogo a differenti soluzioni. Questa operazione, che si chiama analisi di sensibilità del modello, permette di valutare a priori le soluzioni migliori corrispondenti ai differenti valori che i parametri in gioco possono assumere.

Le principali aree applicative. − Anche se, come abbiamo già accennato, i modelli della r.o. si ritrovano nei campi più disparati e possono riguardare i problemi più diversi, vi sono tuttavia alcuni settori che tradizionalmente sono stati e sono ambienti di riferimento tipici.

La produzione e la logistica industriale sono stati fin dall'inizio un ambiente applicativo favorevole; i principali problemi affrontati vanno dalla pianificazione della produzione ai problemi di trasporto, distribuzione e gestione dei materiali, dai problemi di manutenzione di macchine e apparati a quelli di gestione delle risorse umane, dai problemi di scelta dell'architettura di produzione a quelli d'instradamento e sequenziamento delle lavorazioni (v. logistica, in questa Appendice). La progettazione e la valutazione delle prestazioni di sistemi complessi, in cui diversi elementi interagiscono e concorrono a determinare le prestazioni complessive, sono stati un'altra importante area di applicazione. Vengono infatti usate tecniche di r.o. per la progettazione di prodotti industriali, sistemi di servizio, circuiti integrati, reti di telecomunicazione, sistemi di elaborazione, ecc. Inoltre, tali tecniche vengono largamente usate anche per la gestione razionale del processo di progettazione al fine di minimizzare tempi e costi di realizzazione del progetto.

Un settore trasversale ai due ora citati e di crescente interesse è quello della qualità di prodotti, sistemi e servizi, sia per scopi di valutazione, confronto e certificazione, sia per il miglioramento stesso della qualità il cui processo è spesso formulabile in termini di ottimizzazione.

Un'ulteriore area significativa per applicazioni tipiche di r.o. è quella della pubblica amministrazione. In particolare il problema di effettuare scelte economiche efficienti ed efficaci è stato al centro dell'attenzione tanto nelle economie pianificate quanto in quelle di mercato; naturalmente le indicazioni ottenute dai modelli, per l'indeterminatezza di molti obiettivi e vincoli, sono state in genere solo parziali, mentre le difficoltà di monitoraggio del sistema e d'implementazione delle decisioni è spesso rimasto il problema da risolvere. Analoga situazione si è verificata per l'ambiente e il territorio. I problemi affrontati vanno dalla gestione del territorio alla pianificazione degli interventi, al controllo dell'inquinamento, alla gestione del traffico. Anche in questo caso la complessità, l'indeterminatezza e le dimensioni del problema hanno posto limiti pesanti all'uso effettivo dei modelli. Pur tuttavia la loro adozione ha portato, sia pure in ambiti particolari e per problemi specifici, al miglioramento delle soluzioni adottate in precedenza.

In conclusione si può affermare che, in generale, la r.o. è sempre più presente in tutte le fasi del processo di direzione e gestione delle risorse aziendali. Solo attraverso l'uso di strumenti di supporto alle decisioni e alla gestione sempre più sofisticati è oggi possibile controllare in modo efficace la complessa rete di interazioni presente nei moderni sistemi di produzione e di servizio.

I modelli fondamentali. − Come molti e diversificati sono i problemi affrontati, così altrettanto numerosi e differenziati sono i modelli e gli algoritmi utilizzati. Una classificazione dei modelli d'interesse della r.o. può essere fatta in vari modi: rispetto agli obiettivi (previsione, pianificazione, gestione, controllo in tempo reale, ecc.); rispetto all'ambiente (completamente noto con certezza, incerto, con elementi di rischio, con informazione limitata, ecc.); rispetto all'arco di tempo preso in considerazione (decisioni strategiche, decisioni tattiche, decisioni operative); rispetto alle tecniche note (deterministiche, probabilistiche, combinatorie, non lineari, ecc.); rispetto all'uso che se ne intende fare (simulazione, ottimizzazione, definizione di regole di decisione a fini normativi, ecc.); rispetto alla tipologia del problema e del settore applicativo (allocazione di risorse, trasporto, logistica, produzione, progettazione, ecc.).

Il successo ottenuto da alcuni modelli dipende dalla loro capacità di soddisfare due requisiti: da un lato la capacità di rappresentare adeguatamente il problema, dall'altro la capacità di 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.

Qui di seguito viene presentata una possibile classificazione che cerca di cogliere alcuni degli aspetti sopra menzionati.

a) Analisi di scenario: è l'insieme di tecniche per la quantizzazione di situazioni complesse, generalmente in condizioni d'informazione limitata, frammentaria e di tipo prevalentemente qualitativo, in cui il problema di delimitare, anche in modo approssimativo, l'ambito di esistenza di soluzioni ammissibili è prevalente rispetto a quello di definire precise relazioni causa-effetto. Un esempio di questo tipo di tecniche, largamente diffuso, è il metodo Delphi.

b) Rappresentazione: è l'insieme di strumenti logico-matematici, quali equazioni e disequazioni algebriche, grafi, schemi entità-relazione, equazioni booleane, catene di Markov, modelli probabilistici e statistici, alberi e tavole di decisione, matrici risorse-attività, ecc., che permettono di rappresentare in modo quantitativo e rigoroso le relazioni tra le grandezze significative del sistema in esame e il problema di decisione da affrontare.

c) Simulazione: è l'insieme di strumenti e tecniche, prevalentemente di tipo statistico, utilizzati tipicamente per la valutazione delle prestazioni di sistemi complessi, in cui si cerca di simulare l'evoluzione complessiva del sistema, a partire da un insieme di relazioni logico-matematiche che modellano le funzioni dei diversi sottosistemi, e da un insieme di regole di decisione predefinite che permettono di risolvere eventuali problemi di scelta. Con tale strumento, l'utente potrà ottenere indirettamente risposta ad alcuni problemi decisionali; infatti potrà provare sul sistema simulato diverse strategie decisionali o regole di decisione e valutare le conseguenti prestazioni del sistema.

d) Ottimizzazione: è l'insieme, molto vasto e articolato, di modelli, nel quale si cerca di formalizzare la struttura intrinseca del processo di decisione. I modelli di ottimizzazione più diffusi sono quelli nei quali è 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 che si basano sulla teoria dei giochi.

Nell'ambito della classificazione ora illustrata, il filone che ha avuto il maggiore sviluppo dal punto di vista modellistico, ovvero che ha prodotto i risultati più profondi in termini di analisi dei rapporti causa-effetto esistenti nel sistema sotto analisi e quindi delle sue caratteristiche intrinseche, è rappresentato dai modelli di ottimizzazione con singolo decisore e singolo obiettivo. Tra di essi grande diffusione hanno avuto, in particolare, i modelli relativi ai problemi lineari, ai problemi differenziabili e ai problemi discreti.

Modelli lineari. Sono i modelli che hanno segnato, verso la fine degli anni Quaranta, la nascita dell'ottimizzazione come disciplina autonoma. Si tratta essenzialmente di problemi con variabili che possono assumere valori reali qualsiasi, funzione obiettivo espressa da un'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. Un caso particolare, molto significativo, di problemi lineari è quello di flusso su reti. Si tratta essenzialmente di problemi con variabili relative a valori dei flussi in una rete assegnata (per es., una rete stradale, una rete telefonica, una rete di elaboratori, ecc.), funzione obiettivo espressa da un'equazione lineare, vincoli espressi da equazioni e disequazioni lineari relative al bilancio dei flussi nei nodi della rete o a valori minimi e massimi dei flussi lungo gli archi della rete. Sfruttando la particolarità del problema si possono ottenere risultati d'interesse sia teorico che applicativo e costruire algoritmi di soluzione di particolare efficienza.

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 un'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.

Modelli discreti. I modelli discreti sono un insieme molto articolato, con origini e campi di applicazione diversificati. 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 un'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. Anche per questo tipo di modelli, si possono sfruttare le particolarità del problema per ottenere, in molti casi significativi, risultati teorici e applicativi e algoritmi di soluzione particolarmente efficienti. 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.

La classificazione appena introdotta corrisponde abbastanza bene ai diversi filoni in cui si è articolato, nel corso degli anni, lo sviluppo dell'ottimizzazione e ai diversi ambienti scientifici e applicativi di riferimento. I filoni relativi all'ottimizzazione nel continuo hanno avuto tradizionalmente forti legami con l'analisi matematica, il calcolo numerico, la teoria del controllo e, sul versante applicativo, con la modellistica economica e con alcuni settori dell'ingegneria relativi alla progettazione di componenti, strutture e sistemi di controllo. I filoni relativi all'ottimizzazione nel discreto hanno avuto tradizionalmente forti legami con l'informatica teorica, la logica, la teoria delle decisioni, la matematica del discreto e, sul versante applicativo, con le applicazioni dell'informatica, con alcuni settori dell'ingegneria relativi alla progettazione di sistema e agli aspetti di decisione e gestione in ambiente tecnologico, con alcuni settori della modellistica economica interessati ai problemi d'indivisibilità e agli aspetti di decisione.

Bisogna però tener presente che i confini fra le diverse classi non sono così netti, i rispettivi metodi di soluzione hanno avuto sostanziali influenze reciproche e molte applicazioni hanno una struttura mista, nella quale le diverse tipologie sono presenti in modo difficilmente separabile.

I principali algoritmi di soluzione. − Per risolvere problemi di decisione nel formato di problemi di ottimo, sono stati messi 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.

Greedy. Gli algoritmi di tipo greedy (in inglese "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.

Ricerca locale. 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 le quali 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'ottimizzazione differenziabile sono casi di algoritmi di ricerca locale.

Ricerca globale. 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. Gli algoritmi branch and bound 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) rientrano tipicamente in questa categoria.

Bibl.: Activity analysis of production and allocation, a cura di T.C. Koopmans, New York 1951; D. Luce, H. Raiffa, Games and decisions, ivi 1957; R. Bellman, Dynamic programming, Princeton 1957; R. Dorfman, P. Samuelson, R. Solow, Linear programming and economic analysis, New York 1958; C. Berge, Théorie des graphes et ses applications, Parigi 1958; Studies in linear and nonlinear programming, a cura di K.J. Arrow, L. Hurwicz e H. Uzawa, Stanford 1958; A.H. Land, A.G. Doig, An automatic method of solving discrete programming problems, in Econometrica, 28 (1960), pp. 497-520; A. Charnes, W.W. Cooper, Management models and industrial applications of linear programming, New York 1961; L.R. Ford, D.R. Fulkerson, Flows in networks, Princeton 1962; G.B. Dantzig, Linear programming and extensions, ivi 1963; J. von Neumann, Collected works, New York 1963; R. Gomory, On the relations between integer and non integer solutions to linear programs, in Proc. Nat. Acad. Sci., 53 (1965), pp. 260-65; A.F. Fiacco, G.P. Mc Cormick, Nonlinear programming: sequential unconstrained minimization techniques, New York 1968; 1967 Princeton Symp. on Mathematical programming, a cura di H.W. Kuhn, Princeton 1970; J. Edmonds, Matroids and the greedy algorithm, in Math. Progr., 1 (1971), pp. 127-36; R. Karp, Reducibility among combinatorial problems, in Complexity of computer computations, a cura di R. Miller, J. Thatcher, New York 1972, pp. 85-103; L.A. Johnson, D.C. Montgomery, Operations research in production planning, scheduling and inventory control, ivi 1974; L. Kleinrock, Queueing systems (2 vol.), ivi 1976; S.P. Bradley, A.C. Hax, T.L. Magnanti, Applied mathematical programming, ivi 1977; G.S. Fishman, Principles of discrete event simulation, ivi 1978; M.R. Garey, D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, San Francisco 1979; C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization, Prentice Hall 1982; G.D. Eppen, F.J. Gould, C.P. Schmidt, Introductory management science, ivi 1987; G.L. Nemhauser, L.A. Wolsey, Integer and combinatorial optimization, New York 1988; Optimization, a cura di G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd, Amsterdam 1989; Functional analysis, optimization and mathematical economics: a collection of papers dedicated to the memory of Leonid Vital'evich Kantorovich, a cura di L.J. Leifman, Oxford 1990.