PROGRAMMAZIONE LINEARE

PROGRAMMAZIONE LINEARE

. 1. - Generalità e posizione del problema. - Sotto l'aspetto matematico, il termine p. l. indica una classe di problemi consistenti nella ricerca del massimo o del minimo di una funzione lineare di variabili non negative che sono soggette ad un certo numero di vincoli e condizioni (equazioni oppure disuguaglianze) parimenti lineari.

Senza perdere in generalità, si può, in pratica, particolarizzare maggiormente la definizione suddetta, nel senso di prendere in considerazione soltanto la ricerca del minimo (o del massimo) e di supporre tutti i vincoli espressi sotto forma di equazioni. Difatti, quanto al primo punto, i valori delle variabili che rendono massima una determinata funzione lineare, rendono minima la funzione avente gli stessi coefficienti con segno invertito, e il massimo della prima funzione è uguale al minimo della seconda, con segno invertito. Ci si può pertanto sempre limitare al caso della ricerca del minimo, anche se il problema, nella sua formulazione originaria, richiede la ricerca del massimo di una data funzione lineare.

Altrettanto semplice è la trasformazione delle disuguaglianze in equazioni: basta introdurre nel problema delle variabili ausiliarie, non negative, che, a seconda della disuguaglianza, avranno nell'equazione risultante coefficiente + 1 ovvero − 1. E precisamente, indicando con x₁, x₂, ..., x_n le variabili, la disuguaglianza:

si trasforma mediante l'introduzione della variabile ausiliaria x_n+1 nell'equazione:

dove le costanti date, a_ij (j = 1, 2, ..., n) e a_i0, rappresentano rispettivamente i coefficienti e il termine noto del vincolo i-esimo.

Analogamente, la disuguaglianza:

si trasforma nell'equazione

È opportuno precisare inoltre che la condizione di non-negatività delle variabili, pur costituendo un elemento essenziale della p. l. (senza una limitazione di questo tipo non si avrebbero, in generale, massimi e minimi finiti) non è così restrittiva come potrebbe sembrare a prima vista. Difatti, si possono fare rientrare, con qualche accorgimento, nello schema della p. l. anche problemi in cui compaiono un certo numero di variabili che possono assumere valori negativi: per es. si possono eliminare dette variabili esprimendole in funzione delle variabili non negative, o si può sostituire ad ognuna di esse la differenza fra due variabili ausiliarie, non negative.

Ciò premesso, ogni problema di p. l. può essere così rappresentato: data la funzione lineare:

ove x₁, x₂, ..., x_n sono le variabili, e c₁, c₂, ..., c_n sono costanti date, renderla minima, le variabili x₁, x₂, ..., x_n essendo soggette alle seguenti condizioni (dove m 〈 n):

Si assume, senza perdere in generalità, che le equazioni siano linearmente indipendenti; si assume poi che le condizioni [1] e [2] siano compatibili; altrimenti il problema non sarebbe solubile.

I problemi di p. l. non possono essere risolti col metodo dei moltiplicatori di Lagrange - di solito usato per la ricerca dei massimi e minimi vincolati - data appunto la linearità dei vincoli e della funzione da rendere minima. Sono stati perciò ideati, di recente, alcuni procedimenti di tipo iterativo che permettono di giungere alla soluzione con un numero limitato di operazioni elementari.

Prima di passare ad esporre brevemente il procedimento che è di gran lunga il più diffuso, cioè quello del "simplesso", dovuto a G. B. Dantzig, occorre premettere alcune definizioni che fanno parte della terminologia usata in tutti i trattati di p. l. Qualunque sistema di valori delle variabili x_j che soddisfa le condizioni [1] viene detto soluzione. Una soluzione che soddisfa anche le condizioni [2] dicesi soluzione accettabile. Ogni insieme di m variabili x_j linearmente indipendenti - cioè tali che il determinante dei loro coefficienti a_ij nelle equazioni [1] non sia nullo - dicesi base. Le variabili che formano una base data si dicono variabili-base, le altre vengono chiamate variabili non di base, o indipendenti. Data una base, la soluzione che si ottiene ponendo uguali a 0 le variabili non di base e risolvendo le equazioni [1] rispetto alle variabili-base è detta soluzione-base, se è accettabile si chiama soluzione-base accettabile.

Ciò premesso, si può enunciare il seguente teorema che è di importanza fondamentale per la p. l.: Se per un dato problema di p. l. esiste una sola soluzione accettabile ottima (che, cioè, rende minima la funzione C), questa è una soluzione-base; se ve ne sono più di una, ve ne sono infinite, fra cui almeno due soluzioni-base.

L'importanza del teorema - che in realtà non è che un corollario di un noto teorema più generale, riguardante la ricerca dei massimi e minimi vincolati - consiste nel fatto che, per trovare il minimo della funzione C, non è necessario prendere in considerazione tutte le soluzioni - il cui numero in generale è infinito - del sistema costituito dalle condizioni [1] e [2]; basta limitarsi alle soluzioni-base accettabili, il cui numero non può essere maggiore di

Per di più, tutte le soluzioni accettabili ottime - se ve ne è una pluralità - possono essere rappresentate come combinazioni lineari, con coefficienti non negativi, delle soluzioni-base ottime, purché (come generalmente avviene) le condizioni [1] e [2] siano tali da non ammettere valori infiniti delle variabili x_j. In questo caso, è quindi sufficiente conoscere tali soluzioni-base per ottenere tutte le soluzioni accettabili ottime.

Il teorema sopra riportato trova il suo complemento, ai fini dell'elaborazione di un algoritmo per la soluzione dei problemi di p. l., nel cosiddetto "criterio del simplesso", sul quale si fonda il metodo omonimo. Tale criterio, di per sé evidente, permette di stabilire se una data soluzione-base è ottima e, in caso contrario, indica il modo di giungere ad una soluzione-base migliore.

2. - Criterio del simplesso. - Con la terminologia precedente esso può essere così descritto: espresse le variabili-base in funzione delle variabili indipendenti e sostituite le espressioni così ricavate nella funzione C, la soluzione-base data è ottima se le variabili indipendenti figurano tutte nella funzione C, così trasformata, con coefficienti non negativi. Se, invece, una delle variabili indipendenti ha coefficiente negativo, si ottiene una soluzione-base migliore introducendola nella base, cioè facendole assumere un valore positivo.

In simboli, indicando con x_k1, x_k2, ..., x_km le variabili-base di una soluzione-base accettabile e con x_km+1, x_km+2, ..., x_kn le variabili indipendenti, si abbia, operate le sostituzioni:

C = b₀₀ + b_okm+1 x_km+1 + b_okm+2 x_km+2 + ... + b_okn x_kn, dove b₀₀, b_okm+1, b_okm+2, ..., b_okn sono delle costanti. Se nessuno dei coefficienti b_okm+j (j = 1, 2, ..., n − m) è negativo, b₀₀ è il valore minimo che la funzione C può assumere e la soluzione-base data è ottima, e precisamente è l'unica soluzione accettabile ottima se tutti i coefficienti b_okm+j sono positivi; se uno o alcuni di detti coefficienti sono nulli, vi sono altre soluzioni-base accettabili ottime che si ottengono introducendo nella base le variabili corrispondenti. Se, invece, uno dei coefficienti, p. es. b_okm+r è negativo, si ottiene una soluzione-base migliore rimpiazzando con x_km+r una delle variabili-base.

3. - Metodo del simplesso (simplex-method). - Tenendo presente quanto precede il metodo del simplesso può essere così schematizzato: si inizia con una soluzione-base accettabile e si verifica se essa è ottima. Se non lo è, si modifica la base, sostituendo una delle vecchie variabili-base con una variabile avente nella funzione C, trasformata nel modo sopraccennato, coefficiente negativo. (Il procedimento seguito per la determinazione delle due variabili, assicura che anche il nuovo insieme di variabili costituisce una base e che la soluzione corrispondente è accettabile). Si prosegue così, fino a quando in generale, dopo una successione finita di basi, alle quali corrispondono valori sempre minori della funzione C, si verifica una delle seguenti alternative: a) si giunge ad una soluzione-base ottima; oppure: b) risulta che la funzione C non ha un minimo finito, in quanto una variabile con coefficiente negativo può assumere valori comunque grandi.

La prima fase del metodo consiste pertanto nella ricerca di una base accettabile iniziale. Eccettuati i casi, piuttosto rari, in cui le equazioni [1] permettono d'individuare direttamente una base siffatta, si ricorre a tal fine a un espediente non privo d'inconvenienti, ma che ha il vantaggio di applicarsi a qualunque problema, quali che siano i coefficienti e i termini noti delle equazioni [1].

Supposto che i termini noti a_i0 delle [1] siano tutti non negativi (il che si può sempre ottenere, moltiplicando, se occorre, per −1 i coefficienti e il termine noto di una stessa equazione), l'espediente consiste nell'introduzione di nuove variabili artificiali, x_n+1, x_n+2, ..., x_n+m, mediante le quali le [1], [2] si trasformano come segue:

La base iniziale viene allora formata con le variabili x_n+1, x_n+2, ..., x_n+m, che assumono rispettivamente i valori a₁₀, a₂₀, ..., a_m0.

Per evitare che le variabili artificiali compaiano nella soluzione finale con valori positivi, col che non risulterebbero soddisfatte le condizioni originarie [1], si attribuisce ad esse nella funzione C il coefficiente w, numero positivo non precisato, ma tanto elevato da prevalere nei confronti di qualunque altro coefficiente. In tal modo si è certi che tutte le variabili artificiali vengano progressivamente eliminate dalla base o, per lo meno, ridotte a 0. Per ottenere lo stesso risultato si può anche risolvere preliminarmente il problema di p. l. che consiste nel rendere minima la somma delle variabili artificiali, subordinatamente alle condizioni [1′] e [2′].

Una volta eliminate dalla base, le variabili artificiali non vengono comunque più prese in considerazione.

Altre questioni che si presentano nel prosieguo del procedimento riguardano la scelta della variabile da introdurre nella base e, eventualmente, la scelta della variabile che deve essere eliminata dalla base. Riguardo alla prima questione, che si presenta solo quando nella funzione C vi sono, in una determinata fase, due o più variabili con coefficiente negativo, il criterio teoricamente migliore è quello di scegliere la variabile che, introdotta nella base, determina la maggiore diminuzione nel valore di C. Tuttavia, poiché tale criterio comporta una considerevole mole di calcoli supplementari, se le variabili in questione sono numerose, si preferisce in pratica scegliere la variabile che ha nella funzione C il coefficiente più piccolo in valore algebrico, ossia più grande in valore assoluto.

Scelta così la variabile da introdurre nella base, risulta in generale determinata anche la variabile che viene eliminata dalla base stessa: si tratta della variabile che per prima si annulla al crescere della nuova variabile-base; diversamente non sarebbe soddisfatta la condizione di non-negatività, dato che si attribuisce ovviamente alla nuova variabile-base il valore più alto possibile. Può tuttavia avvenire che si annullino simultaneamente due o più variabili della vecchia base. In tal caso si giunge ad una "base degenerata", caratterizzata dall'esistenza di variabili-base nulle. Questa eventualità ha importanti riflessi, peraltro di ordine esclusivamente teorico, in quanto allora, anche con l'applicazione del "criterio del simplesso" il valore della funzione C rimane invariato nell'ipotesi che una variabile introdotta nella base ex-novo vi assume il valore 0, come avviene ovviamente se era nulla la variabile che viene sostituita nella base. Con ciò viene meno la certezza di giungere alla soluzione ottima con una successione finita di basi e quindi con un numero finito di operazioni, certezza che si fonda proprio sulla progressiva diminuzione di C. In tal caso, quindi, non si può, teoricamente, escludere la possibilità che il procedimento iterativo si risolva in una ripetizione infinita di cicli identici. A questo inconveniente che, però, nei casi concreti non si è mai presentato, si può ovviare, aggiungendo fittiziamente ai coefficienti a_ij delle [1] potenze diverse di una quantità infinitesima, ξ, che poi, a soluzione raggiunta, viene posta uguale a 0. In tal modo, la variabile da eliminare dalla base è sempre univocamente determinata ed è esclusa la possibilità di cicli.

Aspetto algebrico del metodo del simplesso. - Siano x_k1, x_k2, ..., x_km le varabili-base di una soluzione-base accettabile, x_km+1, x_km+2, ..., x_km+n le variabili indipendenti. Riscritte le equazioni [1′] nella forma:

dove a_i,n+h vale 1 per h = i, e vale 0 per h ??? i (h = 1, 2, .., m), si risolvano rispetto alle variabili-base:

dove d_si è l'elemento della riga s-esima e della colonna i-esima della matrice reciproca a quella formata dai coefficienti delle variabili-base che appaiono a primo membro delle [1″].

Posto:

le [3] assumono la forma:

Se si sostituiscono le [3′] nella funzione

dove c_n+1 = c_n+2 = ... = c_n+m = w, si ottiene, a calcoli fatti:

avendo posto:

Come già esposto in precedenza, se uno o alcuni dei coefficienti b_okm+h sono negativi e se

la variabile che deve essere portata nella base è x_km+r. Si considerano allora i rapporti b_ks0/b_kskm+r limitatamente a quei valori dell'indice s per i quali b_kskm+r > 0. Solo le corrispondenti variabili-base, infatti, decrescono al crescere di x_km+r (se tutti i coefficienti b_kskm+r (s = 1, 2, ..., m) sono negativi o nulli, C non ha un minimo finito).

Se allora:

la variabile x_kt viene eliminata dalla base. A questo punto si comprende come possa iterarsi il procedimento, applicandolo alla nuova base e così via; anzi sarà possibile costruire delle formule ricorrenti che diano i valori delle costanti b_ks0, b_kskm+h, b₀₀, b_0km+h relativi ad una qualunque base successiva, noti che siano i loro valori relativi alle basi precedenti e, naturalmente, i dati del problema.

Partendo allora dalla base iniziale si passerà da una base alla base successiva con l'uso di dette formule ricorrenti, che per semplicità non riportiamo; e così via fino al raggiungimento di una soluzione-base ottima, se C è limitata, senza dovere di volta in volta risolvere il sistema [1′] rispetto alle diverse basi. In pratica, come già si è detto, le variabili artificiali, una volta eliminate dalla base, non vengono più prese in considerazione.

L'efficienza pratica del metodo viene accresciuta dall'uso delle cosiddette "tavole del simplesso" che facilitano lo svolgimento ordinato dei calcoli. Queste tavole possono essere così schematizzate:

Si sono posti in parentesi i termini che compaiono soltanto nelle fasi iniziali.

Esempio. - A titolo di esempio, si consideri il problema di rendere minima la funzione

subordinatamente alle seguenti condizioni:

Introdotte le variabili artificiali, il problema si modifica come segue: rendere minima la funzione

sotto le condizioni

Le tavole del simplesso corrispondenti a tale problema sono quelle riportate nella tabella in basso (sono rispettivamente sottolineati e racchiusi in parentesi quadra i coefficienti b_0ks e b_kskm+h i cui valori risultano determinati per la trasformazione delle basi). Nell'ultima riga dell'ultima tabella non compaiono coefficienti b_0km+h negativi o nulli, quindi la corrispondente soluzione-base (x₁=53/5, x₄=8/5, x₅=41/10, x₂=x₃=0) è l'unica soluzione ottima, per la vuale C raggiunge il minimo, pari a −164/5.

A proposito del metodo del simplesso accenniamo ad una variante di esso, il "revised simplex method", conveniente soprattutto quando si opera con calcolatrici elettroniche e quando numerosi coefficienti a_ij sono nulli. Esso utilizza le costanti d_sj, innanzi definite, e impiega opportune formule ricorrenti. La successione delle basi è identica a quella del metodo originario del simplesso.

Osservazione. - Nei trattati di p. l. si fa spesso uso della terminologia e del simbolismo del calcolo vettoriale e matriciale, con vantaggi di concisione ed eleganza, ma spesso con la perdita di chiarezza intuitiva del problema e dei metodì di soluzione. Si ricorre anche spesso ad una terminologia geometrica che costituisce un efficace ausilio, soprattutto per la trattazione di problemi teorici, come quelli dell'esistenza o meno di un minimo finito, della compatibilità delle condizioni o dei casi di "degenerazione" delle basi. Secondo tale terminologia, le equazioni [1] rappresentano m iperpiani nello spazio n-dimensionale. Le condizioni

definiscono un "cono poliedrico convesso" il quale taglia l'intersezione degli iperpiani, a condizione che le variabili risultino limitate, secondo un "poliedro convesso". Le soluzioni-base accettabili corrispondono ai vertici del poliedro.

4. - Problema duale. - Al problema, sopra trattato, definito dalle [1] e [2], può esserne associato un altro, così definito: rendere massima la funzione

coi seguenti vincoli:

Questo secondo problema viene chiamato duale del primo. Fra i due problemi vi sono delle relazioni notevoli. Anzitutto, si può dimostrare che se uno dei due problemi ha una soluzione ottima finita, anche l'altro ha una soluzione ottima finita, e gli estremi delle due funzioni lineari sono uguali, cioè min C = max A. Inoltre, se per uno dei due problemi non esiste una soluzione ottima finita, per l'altro non esiste una soluzione accettabile.

Per di più, se x_k1, x_k22, ..., x_km sono le variabili-base che nella soluzione-base ottima del primo problema assumono rispettivamente i valori b_k10, b_k20, ..., b_km0, e x_km+1, x_km+2, ..., x_kn le variabili indipendenti che nell'espressione finale della funzione C hanno rispettivamente i coefficienti b_0km+1, b_0km+2, ..., b_0kn, le variabili-base del problema duale (dopo l'eliminazione delle variabili y_n+1, y_n+2, ..., y_n+m che possono assumere valori negativi, e dopo aver moltiplicato per −1 i coefficienti della funzione lineare A, al fine di trasformare il problema di massimo in problema di minimo), sono y_km+1, y_km+2, ..., y_kn, ed i loro valori sono dati rispettivamente da b_0km+1, b_0km+2, ..., b_0kn, mentre i coefficienti delle variabili indipendenti y_k1, y_k2, ..., y_km, nella A trasformata sono rispettivamente b_k10, b_k20, ..., b_km0. Relazioni simili valgono per le quantità b_kskm+h nelle tavole finali del simplesso.

Esempio. - A titolo illustrativo riportiamo qui il problema duale di quello trattato prima:

Rendere minima la funzione

le variabili essendo soggette alle seguenti condizioni:

Dopo l'eliminazione delle variabili y₆, y₇, y₈ dalle equazioni precedenti, il problema si presenta come segue

Rende minima la funzione:

sotto le condizioni:

La tavola finale del simplesso è la seguente:

Il fenomeno della dualità, suscettibile di suggestive interpretazioni in campo economico, è importante sotto diversi aspetti, teorici e pratici. Anzitutto, esso permette di scegliere fra un problema dato e quello duale. In linea di massima conviene risolvere il problema avente il minor numero di equazioni: l'esperienza dimostra infatti che un problema contenente p equazioni richiede in media da p a 2p iterazioni. Poiché le equazioni sono in numero di m per il problema originario e di n − m per il problema duale (dopo l'eliminazione delle variabili che possono assumere valori negativi), è in generale preferibile risolvere il problema originario se m ≤ n/2 e il problema duale se vale la disuguaglianza inversa.

Inoltre, l'osservazione delle situazioni che si determinano se ad ogni operazione del metodo del simplesso sul problema originario si fa corrispondere un'operazione analoga sul problema duale, ha portato alla scoperta di un altro metodo, denominato "metodo duale", nelle fasi intermedie del quale le variabili-base possono assumere anche valori negativi, mentre i coefficienti delle variabili indipendenti nella funzione da minimizzare devono essere tutti positivi o nulli. Questo metodo può talvolta essere combinato vantaggiosamente con quello del simplesso.

5. - Problemi particolari di p. l. - Un caso particolare, molto importante, di p. l., è costituito dal cosiddetto "problema dei trasporti" o "di Hitchcock", in cui si tratta di rendere minima la funzione lineare

le variabili x_ij essendo soggette alle seguenti condizioni:

dove le c_ij, a_i0 e a_0j sono costanti date e

Le equazioni indipendenti sono qui in numero di h + h − 1, anziché di k + h, e quindi anche le basi sono composte di h + k − 1 variabili.

Per la soluzione del problema dei trasporti - che ammette sempre una soluzione, per di più in termini di valori interi delle variabili, se le a_i0 e le a_0j sono intere - sono stati ideati alcuni algoritmi particolari che sono più semplici del metodo del simplesso.

Connesso al "problema dei trasporti", ma molto più difficile a maneggiarsi, è il cosiddetto "problema del commesso viaggiatore" che negli ultimi tempi è stato fatto oggetto di numerosi studî, senza peraltro trovare una soluzione generale soddisfacente. Il problema consiste nel trovare il percorso chiuso più breve che tocchi n punti, senza, beninteso, che si debba calcolare la lunghezza di tutti i percorsi possibili, il cui numero è (n − 1)! /2. Sono date le distanze fra tutte le coppie di punti. Diversi problemi specifici sono stati risolti; l'esempio più notevole è dato da quello relativo a 49 città americane, risolto da G. B. Dantzig e altri con l'impiego prevalente, ma non esclusivo, di metodi di p. l. La difficoltà principale di tale approccio sta nella possibilità che la soluzione ottima contenga dei sub-percorsi chiusi o che le variabili-base vi figurino con valori frazionarî.

6. - Possibili sviluppi della p.l. - Le più recenti ricerche nel campo della p. l. si svolgono secondo varie direttrici. Da un lato si cerca di perfezionare i procedimenti, soprattutto nel senso di evitare il ricorso alle variabili artificiali che spesso rendono sterili le prime fasi del "simplesso" ai fini della ricerca di una buona soluzione-base o nel senso di trovare procedimenti più rapidi per problemi di grande mole. A quest'ultimo proposito sono da segnalare le ricerche, peraltro non ancora conclusive, condotte da R. Frisch. Dall'altro lato, si cerca di estendere, in varî modi, la sfera di applicazione della p. l. Così, si cerca, finora senza grandi risultati, un metodo per risolvere i problemi in cui le variabili possono assumere solo valori interi. Poco fruttuosi sono stati finora anche i tentativi di affrontare il problema della cosiddetta "programmazione non lineare", quei problemi, cioè, in cui o la funzione da rendere minima o i vincoli non sono lineari. Appare peraltro facile prevedere che gli sforzi in quella direzione proseguiranno, poiché l'esigenza di uscire dall'ambito, alquanto ristretto e limitato, delle sole funzioni lineari, è viva e reale.

Un altro indirizzo di studî tende ad indagare la connessione della p. l. con altri settori della "ricerca operativa", e segnatamente con la teoria dei giochi (v. operativa, ricerca, in questa App.). In tale campo si sono avuti risultati interessanti che mettono in luce una stretta corrispondenza fra la p. l. e una certa classe di giochi.

Risultati ancora incompleti, ma abbastanza incoraggianti, si sono avuti anche per i problemi in cui le costanti dipendono dal valore assunto da qualche parametro. Anche in tale campo di ricerche, la cui importanza è evidente, appare lecito attendersi altri successi. Indagini più ambiziose si propongono di studiare le distribuzioni delle soluzioni dei problemi di p. l. nel caso che le costanti siano affette da errori di osservazione. I risultati finora conseguiti appaiono dubbî; tali ricerche incontrano difatti notevoli difficoltà, dovute soprattutto alla condizione di non-negatività delle variabili che introduce delle discontinuità nei valori delle variabili nelle soluzioni ottime al variare delle costanti.

Bibl.: Directorate of management analysis, Symposium on linear inequalities and programming, Washington 1952; A. Charnes, W. W. Cooper, A. Henderson, Introduction to linear programming, New York 1953; G. B. Dantzig e W. Orchard-Hays, Alternate algorithm for the revised simplex method, Santa Monica, California, 1953; A. Hoffman, Cycling in the simplex algorithm, Washington 1953; A. Charnes e C. E. Lemke, Minimization of non-linear separable functions, Pittsburgh 1954; G. B. Dantzig, Computational algorithm of the revised simplex method, Santa Monica, California, 1954; id., The dual simplex algorithm, ivi 1954; id., Composite simplex-dual simplex algorithm, ivi 1954; id., Linear programming under uncertainty, ivi 1954; B. Giardina, A. Longo, S. Ricossa, La programmazione lineare nell'industria, Torino 1954; C. E. Lemke, The dual method of solving the linear programming problem, in Naval Research Logistics Quarterly, I, 1954; J. von Neumann, A numerical method to determine optimum strategy, ibidem, I, 1954; G. B. Dantzig, Discrete-variable extremum problems, Santa Monica, California, 1956; id., L. R. Ford jr., D. R. Fulkerson, A primal-dual algorithm, ivi 1956; M. Gerstenhaber e J. E. Kelley jr., Threshold methods in linear programming, Philadelphia 1956; S. Vaida, The theory of games and linear programming, New York 1956; I. Cutolo, Programmazione lineare, Napoli 1957; R. P. Dorfman, P. A. Samuelson, R. Solow, Linear programming and economic analysis, New York 1958; S. I. Gass, Linear programming, ivi 1958; A. Herzel, Le tabelle di co- e contrograduazione e la programmazione lineare, Roma 1958; id., Nuovi contributi alla programmazione lineare, ivi 1958; L. Savino, La programmazione lineare, Milano 1958; S. Vajda, Readings in linear programming, Londra 1958.

Economia.

1. - In economia la p. l. si usa per la risoluzione di problemi relativi all'utilizzo economico di risorse scarse utilizzabili per il perseguimento di fini alternativi. Tradizionalmente questi problemi sono stati trattati nella scienza economica mediante l'applicazione del calcolo differenziale (ricerca dei valori estremi di una funzione di più variabili subordinatamente a vincoli imposti alle variabili stesse); questa trattazione tradizionale, se ha avuto il grande merito di porre in luce, con tutto rigore, l'essenza stessa dei problemi in questione, presenta però gravi difficoltà dal punto di vista delle applicazioni pratiche, giacché le funzioni da estremare ed i vincoli vi appaiono quasi sempre in forma generica, il che ne impedisce sia la esatta verifica statistica sia l'utilizzazione sul terreno del calcolo. La p. l. è nata dal tentativo di superare questa separazione tra teoria e pratica, mediante la sostituzione delle generiche funzioni della teoria tradizionale con funzioni ben determinate: specificamente, come il nome stesso suggerisce, si tratta di operare con forme lineari sia per quanto riguarda le funzioni di cui si cerca il massimo o il minimo, sia per quanto riguarda i vincoli cui le variabili sono sottoposte. Matematicamente il problema si presenta in questi termini: data una Z funzione lineare (omogenea) delle n variabili x, x₂, ..., x_n:

trovare, se esistono, le n-ple di valori non negativi delle x che diano alla Z il massimo (o il minimo) valore possibile, subordinatamente agli m vincoli compatibili e indipendenti:

dove m 〈 n ed i b non sono tutti nulli. La risoluzione di siffatto problema si esegue con varî metodi, di cui il più noto è quello detto del simplesso, che viene illustrato nella parte matematica di questa voce. La rilevanza di questo problema matematico (e quindi dei relativi metodi di risoluzione) per le questioni economiche dipende dalla possibilità di formulare queste ultime in modo ad esso conforme. Tale formulazione viene indicata col termine di "analisi delle attività" (activity analysis, dal titolo di un'opera di T. C. Koopmans del 1951), che costituisce, appunto, la parte più propriamente economica della p. l. Per attività o processo s'intende la trasformazione di certi beni (fattori, inputs) in altri beni (prodotti, outputs), essendo fissi i rapporti tra ogni bene e ciascuno degli altri; l'unica cosa che può variare in un'attività è perciò il livello al quale essa è esercitata; non possono invece variare le proporzioni nelle quali in essa intervengono fattori e prodotti. L'attività è perciò rappresentabile mediante un insieme di numeri, ciascuno dei quali, nelle opportune unità, misura la quantità in cui un certo bene (fattore o prodotto) interviene nell'attività in corrispondenza di un livello definito unitario. Simbolicamente un'attività A_i si rappresenta nella forma: A_i ⊄ (a_1i, a_2i, ..., a_mi), dove il primo indice delle a indica un bene e il secondo indice l'attività. Per distinguere i fattori dai prodotti s'introduce qualche opportuna convenzione circa i segni delle a; generalmente si conviene che le a che si riferiscono a prodotti siano positive e quelle che si riferiscono a fattori siano negative. Se x_i è il livello a cui l'attività A_i viene esercitata, le quantità dei beni che in essa intervengono sono evidentemente: (a_1ix_i, a_2ix_i, ..., a_mix_i). Si assume che le x possano avere qualsiasi valore non negativo (ipotesi della divisibilità). Se il soggetto economico può esercitare un numero s finito di attività A₁, A₂, ..., A_s, la sua situazione è descritta dalla seguente matrice:

Ogni colonna della matrice si riferisce ad un'attività ed ogni riga a un bene. In generale ogni bene può intervenire nelle varie attività o come prodotto o come fattore o può non intervenire affatto; quindi le a possono essere positive, negative o nulle. La situazione che corrisponde all'esercizio delle attività rispetto ai livelli x₁, x₂, ..., x_s è descritta dalla matrice:

Una s-pla di valori (evidentemente non negativi) per le x costituisce un programma. La conseguibilità o meno di un programma dipende dal fatto che esso rispetti, o meno, certi vincoli imposti ai livelli dell'attività. La natura di tali vincoli dipende, a sua volta, dai tipi di beni che intervengono nelle attività considerate. All'uopo si può procedere alla seguente classificazione: a) risorse "originarie"; b) beni intermedî; c) beni "finali". Rispetto ad un dato insieme di attività, sono risorse "originarie" quei fattori della produzione che non sono prodotti da qualcuna delle attività dell'insieme e si assumono quindi come disponibili in quantità date; sono beni intermedî quei beni che, prodotti in alcune attività, sono interamente usati come fattori in altre; sono beni "finali" quei beni che, prodotti da alcune attività, sono interamente destinati all'esterno, seno cioè utilizzati al di fuori dell'insieme di attività che si considera.

Alcuni beni possono naturalmente apparire sia come beni "finali" sia come beni intermedî: di tale circostanza si può tener conto fondendo le categorie b) e c); ogni bene non originario viene ad avere due destinazioni, intermedia e finale, una delle quali può, come caso particolare, essere assente. Da ognuna delle risorse originarie deriva il vincolo secondo cui l'uso complessivo di tale risorsa nell'insieme delle attività non può essere maggiore della sua disponibilità. Da ognuno dei beni non originarî possono derivare due specie di vincoli. Se dall'"esterno" viene una data domanda, occorre che ciò che resta del bene dopo aver soddisfatto tutti gli usi intermedî sia non minore di tale domanda finale. Se non c'è questo dato "esterno", tra le s attività ve ne saranno alcune puramente "consumatrici" ed il vincolo richiederà allora che la somma del "consumo" e degli usi intermedî sia non minore della produzione. Per tradurre matematicamente i varî tipi di vincoli, s'introduce l'ipotesi - fondamentale in questa analisi - detta dell'additività, secondo la quale la produzione di un bene o l'uso di un fattore da parte dell'insieme delle attività simultaneamente esercitate è uguale alla somma delle produzioni o degli usi da parte di ciascuna attività separatamente considerata. Come, entro una data attività, l'ipotesi di perfetta proporzionalità tra fattori e prodotti esclude l'esistenza di economie e diseconomie interne, così, tra le varie attività, l'ipotesi dell'additività esclude l'esistenza di economie e diseconomie esterne. Ciò posto, e tenendo presenti i segni che accompagnano le a secondo che si tratti di outputs o di inputs, i suddetti vincoli possono, in ogni caso, scriversi:

dove le costanti b sono negative se misurano la disponibilità delle risorse "originarie", positive se misurano l'ammontare delle domande "finali", o nulle nel caso di quei beni il cui "consumo" è incluso tra le attività. Questi vincoli possono essere ricondotti alla forma tipica dei vincoli di un problema di p. l. (quali sono stati esposti all'inizio) introducendo, una per ogni vincolo, m nuove variabili non negative x_s+1, ..., x_s+m, dette variabili ausiliarie, tutte con coefficiente −1, in modo che:

Ciò equivale ad introdurre m nuove attività sui generis, che consistono o nel lasciare inutilizzata parte della disponibilità di una risorsa, o nel soddisfare in misura maggiore del richiesto una certa domanda "finale" o nel consentire un'eccedenza di qualche produzione sulla somma dei suoi usi nel complesso delle attività. I vincoli [4] sono esattamente del tipo dei vincoli [2]: in essi il numero delle incognite (livelli) è maggiore del numero delle equazioni; esistono quindi generalmente infiniti programmi che rispettano i vincoli. La scelta del programma ottimo può farsi non appena venga assegnato un criterio, cioè una funzione lineare dei livelli delle attività che si voglia rendere massima o minima. I coefficienti di tale funzione (detti pesi) rappresentano, per ogni attività, talvolta un valore unitario, talvolta un costo unitario. Il problema si presenta dunque come quello di trovare la s-pla o le s-ple di valori non negativi per i livelli x delle attività, in modo che la funzione:

(dove le variabili ausiliarie appaiono con pesi nulli) abbia il massimo (o il minimo) valore possibile col rispetto dei vincoli [4]. Esempio di problema di massimo è quello di un'azienda che disponga di un certo numero di impianti, ciascuno dotato di una data capacità annua e che possa esercitare, mediante tali impianti, un insieme (finito) di attività, ciascuna producente certi beni, e utilizzante come fattori sia le suddette capacità sia, come beni intermedî, prodotti di altre attività. Gli altri elementi di costo (lavoro per es.) siano disponibili in quantità "illimitata", cioè possano essere ottenuti nella quantità richiesta ad un prezzo dato indipendente dai livelli delle attività. Sono inoltre presenti, una per ogni bene, altre attività "consumatrici" (in questo caso attività di vendita). I pesi p rappresentano, per le attività di produzione, il costo diretto unitario (costante) e, per le attività di vendita, il ricavo unitario (costante). La funzione da massimizzare è dunque il valore netto della produzione, definito come differenza tra ricavi e costi diretti unitarî; i vincoli sono dati sia dalla condizione che ogni impianto non può essere sfruttato al di sopra della sua capacità, sia dalla condizione che la quantità di ciascun bene utilizzata come bene intermedio o venduta non può essere maggiore di quella prodotta.

2. - Dato il problema di p. l.: massimizzare la [5] con i vincoli [3] - che si può sempre ridurre, come s'è detto, a forma normale -, si chiama suo duale il seguente: minimizzare la funzione:

subordinatamente ai vincoli:

Si hanno le seguenti notevoli proprietà: a) se tanto i vincoli del problema diretto che quelli del duale hanno soluzioni, esiste il massimo di Z subordinatamente a [3] e il minimo di W subordinatamente a [7]; b) Z^max = W^min; c) se un vincolo [3] è, nella soluzione ottima del diretto, soddisfatto come disuguaglianza, la variabile u, che, nel duale, corrisponde a tale vincolo, è nulla, e viceversa. Dato un problema (diretto) di p. l. è quasi sempre possibile attribuire un significato economico al suo duale. Per esempio, se il problema diretto si presenta come ricerca dell'ottima utilizzazione di risorse date, il duale appare come un problema d'imputazione a tali risorse del valore (Z = W) conseguito mediante il loro utilizzo; le u sono allora interpretabili come prezzi delle risorse, e ciascuno dei vincoli [7] appare come una relazione tra costo e valore. La proprietà c) significa che se una delle risorse è parzialmente inutilizzata il suo prezzo è zero, e se il costo di un'attività è maggiore (si tengano presenti i segni delle a) del suo valore, essa è esercitata a livello nullo. Alla luce delle proprietà del problema duale, i metodi matematici di risoluzione, e in particolare il metodo del simplesso, sono suscettibili d'interessanti interpretazioni economiche; per es., si dimostra che il procedimento del simplesso si risolve essenzialmente nel confronto tra la profittabilità delle attività esercitate e quella delle attività non esercitate, essendo la soluzione caratterizzata da profitti nulli per le attività esercitate a livelli positivi e da profitti negativi per le attività esercitate a livelli nulli.

3. - Le applicazioni della p. l. hanno luogo sia nella programmazione a livello aziendale, di gruppo o di settore, sia nella pianificazione riferita all'intero sistema economico. Nel primo caso si tratta di specificazioni del problema già indicato alla fine del n. 1; si sono avute applicazioni alla produzione chimica, alla raffinazione degli olî minerali, alla produzione automobilistica, ai trasporti, alla politica delle scorte, ecc. Nel secondo caso si tratta spesso di generalizzazioni del modello input-output di W. Leontief (H. B. Chenery e P. G. Clark, 1959), in cui il problema della scelta s'introduce per esempio, ammettendo più alternative tecnologiche nella produzione dei varî beni oppure diverse fonti d'offerta (come: produzione interna o importazioni). Le applicazioni sono comunque sempre subordinate alla legittimità delle già viste ipotesi di linearità, divisibilità, additività e numero finito, delle attività.

La p. l. inoltre è utilizzata proficuamente in sede di teoria economica pura, dove ha, per esempio, consentito una più rigorosa formulazione dell'equilibrio statico walrasiano (mettendo in nuova evidenza lo stretto legame tra il problema della destinazione delle risorse ai varî usi produttivi e il problema della formazione dei prezzi) e delle sue proprietà ottimali (R. Dorfman, P. . Samuelson. R. M. Solow, 1958). A quest'ultimo riguardo, definita l'efficienza produttiva nel senso paretiano (una configurazione è efficiente quando, date le risorse a disposizione, non è possibile aumentare la produzione di un bene senza diminuirne qualche altra, né diminuire l'impiego d'un fattore senza aumentare l'impiego di qualche altro), si dimostra che la soluzione di un problema di p. l., nel quale si voglia massimizzare il valore complessivo della produzione subordinatamente ai vincoli imposti dalla disponibilità delle risorse, individua una configurazione efficiente, e, viceversa, che, data una configurazione efficiente, essa può sempre essere pensata come la soluzione di un problema di p. l. È sempre possibile, cioè, trovare almeno un sistema di pesi per i beni prodotti tale che quella configurazione risulti come soluzione del problema di p. l. che consiste nel massimizzare la forma lineare che si ottiene sommando le quantità dei beni prodotti, ciascuna moltiplicata pel suo peso, subordinatamente alla disponibilità delle risorse. Interpretando tali pesi come prezzi (relativi), ad ogni configurazione efficiente risulta associato (almeno) un sistema di prezzi, dove i prezzi dei prodotti sono i suddetti pesi ed i prezzi delle risorse sono i valori delle variabili che appaiono nel duale del problema considerato. In conseguenza delle proprietà esposte al n. 2, questo sistema di prezzi è tale che: a) il profitto delle attività esercitate a livello positivo è nullo e quello delle attività esercitate a livello nullo è negativo; b) i prezzi delle risorse impiegate pienamente sono positivi e quelli delle risorse impiegate parzialmente sono nulli. Si dimostra ora che in un sistema concorrenziale walrasiano (a coeificienti tecnici fissi) il valore della produzione è massimizzato rispetto alle risorse disponibili e che perciò tale sistema è efficiente; d'altra parte, poiché le proprietà a) e b) di un sistema di prezzi associato a una configurazione efficiente sono proprio le proprietà d'un mercato concorrenziale, si deve anche dire che ogni configurazione efficiente può essere considerata come il risultato di un possibile processo concorrenziale. La p. l. serve dunque a dimostrare, nel caso di tecnologia lineare. una delle proposizioni fondamentali dell'economia del benessere": ogni equilibrio concorrenziale è una configurazione efficiente, e viceversa.

Va infine ricordato come la p. l. presenti notevoli analogie con la teoria dei giochi, se non per la natura dei problemi, per i metodi con cui si perviene alla loro soluzione; al riguardo si dimostra che ogni problema di p. l. può tramutarsi in un gioco di due persone a somma nulla, e viceversa.

Bibl.: Oltre quella citata nel paragrafo precedente, v. G. B. Dantzig, The programming of interdipendent activities: mathematical model, in Econometrica, 1949; T. C. Koopmans (cur.), Activity analysis of production and allocation, New York 1951; A. Charnes, Optimality and degeneracy in linear programming, in Econometrica, 1952; G. B. Dantzig, A. Orden e P. Wolfe, The generalized simplex method for minimazing a linear form under linear inequality restraints, in Pacific Journal of mathematics, 1955; P. Pagani, Programmazione lineare, in Dizionario di economia politica, Milano 1956; H. B. Chenery e P. G. Clark, Interindustry economics, New York 1959.