ottimizzazione

ottimizzazione

Problemi e metodi di ottimizzazione

Tutti i metodi di ottimizzazione 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. Anche eventuali regole imposte dall’esterno o restrizioni che si ritiene opportuno porre all’evoluzione del sistema, devono essere formulate in termini di equazioni e disequazioni. Nel 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 opzioni e alle conseguenti variazioni del sistema e del suo ambiente (funzioni obiettivo). 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.

I problemi di ottimizzazione e i relativi metodi di soluzione si dividono in 3 classi principali: programmazione lineare, programmazione non lineare e ottimizzazione combinatoria. La formulazione più generale di un problema di ottimizzazione 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.

Programmazione lineare e non lineare.

I problemi di programmazione lineare si pongono come casi particolari della suddetta formulazione e sono caratterizzati, come implica la parola stessa, 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, dove 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 più 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à.

Ottimizzazione combinatoria

I problemi di ottimizzazione combinatoria costituiscono a loro volta un caso particolare, in cui S è un insieme discreto (per es., quello dei soli numeri interi), della trattazione 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 differenti funzioni obiettivo. Al loro studio è dedicata la teoria dei giochi (➔ giochi, teoria dei), che, oltre ad avere molti rilevanti campi di applicazione, costituisce anche uno dei principali riferimenti metodologici nelle moderne ricerche di economia industriale. Un esempio di ottimizzazione, che deriva dalla teoria dei giochi, è il cosiddetto metodo minimax, o maximin, che consiste nel minimizzare la massima perdita possibile, ovvero massimizzare il minimo guadagno, scontando cioè la risposta ottima dell’avversario, quando essa consiste nella scelta peggiore per il giocatore che decide per primo (come nel caso dei giochi a somma zero). Questo metodo è stato esteso alla teoria delle decisioni in condizioni di estrema incertezza, tali che gli agenti non sono in grado di assegnare una data probabilità alle possibili realizzazioni di un evento e preferiscono quindi minimizzare i danni nel peggiore dei casi possibili.

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.

Le proprietà strutturali delle diverse classi di modelli

Il successo ottenuto dalle diverse classi di modelli dipende essenzialmente dalla loro capacità di soddisfare due requisiti: da un lato, rappresentare adeguatamente il problema delle decisioni da affrontare; dall’altro, fornire risposte utili per un insieme significativo di applicazioni. Il tipo di modello effettivamente utilizzato dipende dalle caratteristiche del sistema da analizzare, 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, l’analisi dell’efficienza e delle proprietà di convergenza dei vari algoritmi, l’approfondimento su 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, in particolare, all’elaborazione 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 (in riferimento ad assegnate distribuzioni di probabilità dei dati).