Programmazione matematica

Programmazione matematica

Numerosissimi problemi, sia teorici che pratici, si traducono nella massimizzazione o minimizzazione di una determinata espressione. Sono i cosiddetti problemi di ottimizzazione, che è possibile distinguere tra problemi di ottimizzazione statica e di ottimizzazione dinamica. Questi ultimi sono caratterizzati da un’evoluzione temporale delle quantità considerate, che viene a far parte integrante della struttura del problema. Noi qui ci occuperemo esclusivamente dei primi. All’ottimizzazione statica si riferisce il termine programmazione matematica, introdotto da Robert Dorfman nel 1949 per indicare problemi in cui occorre trovare i valori ottimali di una funzione obiettivo mentre le sue variabili indipendenti, o decisionali, sono soggette a determinati vincoli. Questi vengono espressi (classicamente) da uguaglianze oppure scritti, in termini più moderni e più generali, sotto forma di disuguaglianze o di appartenenza a un insieme assegnato. Si parla di programmazione matematica non lineare quando le funzioni obiettivo e di vincolo sono arbitrarie e dunque non necessariamente lineari o affini.

Il primo riferimento storico si trova nell’opera di Joseph-Louis Lagrange, che nella Mécanique Analytique (1788) introduce i moltiplicatori che portano il suo nome come strumento per determinare la configurazione di equilibrio stabile di un sistema meccanico. Nella Théorie des fonctions analytiques (1797) egli presenta il metodo dei moltiplicatori in tutta la sua generalità, per trattare problemi di ottimizzazione dove tra le variabili sussistono relazioni e semplificarne la soluzione senza ricorrere ogni volta all’eliminazione di alcune delle variabili stesse utilizzando le equazioni di vincolo.

Negli stesso periodo, sempre con vincoli scritti sotto forma di uguaglianza, i primi problemi lineari vengono affrontati da Laplace e da Gaspard François Clair Marie de Prony. Un altro contributo importante viene dato da Jean-Baptiste Joseph Fourier con una significativa apertura nella direzione della programmazione moderna, che troverà una caratterizzazione – rispetto ai problemi di ottimo vincolato classico – nell’uso delle disuguaglianze (anziché delle uguaglianze) per definire i vincoli. La trattazione del problema veniva così portata su un terreno matematico completamente nuovo.

Nel contesto lagrangiano dei principi variazionali della meccanica, Fourier pubblica nel 1798 una memoria in cui intende provare quello che oggi è chiamato principio dei lavori virtuali. La ricerca delle condizioni di equilibrio conduce ancora alla minimizzazione della funzione potenziale e la discussione del problema fisico prevede appunto che le variabili del sistema possano essere condizionate da vincoli rappresentati da disuguaglianze. Due suoi successivi articoli, del 1826 e del 1827, presentano un metodo di soluzione di un sistema di disuguaglianze lineari (che viene oggi chiamato metodo di eliminazione di Fourier-Motzkin) e la discussione di alcuni problemi di programmazione lineare in due e in tre variabili, affrontati geometricamente con una prima rudimentale versione del metodo del simplesso.

Le idee di Fourier vengono riprese da Claude-Louis Navier e Antoine Auguste Cournot, che nel 1827 assegna la condizione necessaria per il problema di minimo con cui Fourier aveva formalizzato la ricerca della posizione di equilibrio. Lo stesso teorema compare – in termini più generali, anche se privo di una dimostrazione completa – in un articolo del 1838 di Mikhail V. Ostrogradsky che, da studente, aveva seguito i corsi di Fourier a Parigi. L’interesse verso la programmazione matematica riprende con gli studi di Paul Gordan (1873), che per primo assegna condizioni necessarie e sufficienti per le soluzioni di un sistema di disequazioni lineari, e soprattutto con alcuni articoli del matematico ungherese Julius Farkas. Quasi contemporaneamente, un enunciato simile a quello oggi chiamato lemma di Farkas compare nel libro di Hermann Minkowski, Geometrie der Zahlen (1896). Nel periodo tra le due guerre mondiali un altro matematico ungherese, Alfred Haar, generalizzerà il risultato di Farkas ai sistemi non omogenei (1924). Ma il primo effettivo riconoscimento dell’importanza del lavoro di Farkas per i problemi lineari verrà qualche anno dopo con la tesi di dottorato di Theodore Motzkin (1933), alla vigilia della nascita della programmazione, lineare e non. Nei paragrafi successivi utilizzeremo a volte, come sinonimo, il termine di ottimizzazione, mentre altri autori riservano l’espressione programmazione matematica ai problemi di ottimizzazione in spazi di dimensione finita.

Bibliografia

Arrow 1961: Arrow, Kenneth J. - Hurwicz, Leonid - Uzawa, Hirofumi, Constraint qualifications in maximization problems, “Naval research logistics quarterly”, 8, 1961, pp. 175-191.

Avriel 1987: Avriel, Mordechai e altri, Generalized concavity, New York, Plenum, 1987.

Bazaraa, Shetty 1976: Bazaraa, Mokhtar S. - Shetty, Chitharanjan M., Foundations of optimization, Berlin, Springer, 1976.

Clarke 1983: Clarke, Frank H., Optimization and nonsmooth analysis, New York, Wiley, 1983.

Dantzig 1983: Dantzig, George B., Reminescences about the origin of linear programming, in: Mathematical programming. The state of the art, edited by Achim Bachem, Martin Grötschel, Bernhard Korte, Berlin, Springer, 1983.

Giorgi 2004: Giorgi, Giorgio - Guerraggio, Angelo - Thierfelder, Jörg, Mathematics of optimization: smooth and nonsmooth case, Amsterdam, Elsevier, 2004.

Kuhn 1956: Linear inequalities and related systems, edited by Harold W. Kuhn, Princeton (N.J.), Princeton University Press, 1956.

Roberts, Varberg 1973: Roberts, Arthur W. - Varberg, Dale E., Convex functions, New York, Academic Press, 1973.

Rockafellar 1970: Rockafellar, Tyrrell R., Convex analysis, Princeton, Princeton University Press, 1970.