PROGRAMMAZIONE LINEARE

PROGRAMMAZIONE LINEARE (App. III, 11, p. 494)

LINEARE Tra gli argomenti che maggiormente hanno attirato l'attenzione degli studiosi di p. l. negli ultimi anni possono essere segnalati in particolare: le tecniche di decomposizione, la p. l. a variabili intere e la p. l. stocastica.

La "decomposizione". - Le tecniche di "decomposisione", sviluppate da L. Ford, R. Fulkerson, W. S. Jowell, G. B. Dantzig e Ph. Wolfe, sono intese a trattare problemi di p. l. di grandi dimensioni, ma con struttura a blocchi, quali non è difficile incontrare in pratica. La situazione, nella modalità più semplice, può essere schematizzata come segue: si tratta di minimizzare la funzione obiettivo C = c^TX + d^TY sotto i vincoli

dove i vettori X e Y hanno rispettivamente n₁ e n₂ componenti e i vettori b_i hanno m_i componenti (i =1, 2, 3).

Il significato dei simboli è il seguente: X ed Y sono vettori incogniti con n₁ e rispettivamente n₂ componenti; l'esponente T indica l'operazione di trasposizione; c e d sono vettori con n₁ ed n₂ componenti; i vettori b_i hanno m_i componenti (i = 1, 2, 3); infine le matrici A₁, Ā₁, A₂, Ā₂ hanno, rispettivamente, m₁, m₃, m₂, m₃ righe ed n₁, n₁, n₂, n₂ colonne.

Un problema siffatto può presentarsi, per es., quando si tratta di minimizzare i costi complessivi di due aziende appartenenti a una stessa impresa.

Il metodo della decomposizione si fonda sul principio di scindere il problema in subproblemi corrispondenti alle parti indipendenti e in un problema principale che collega fra di loro i subproblemi. Nel corso delle iterazioni sia i subproblemi sia il problema principale vengono modificati e vanno quindi risolti ripetutamente. Ogni soluzione del problema principale fornisce le funzioni obiettivo dei subproblemi e dalla soluzione di questi scaturiscono nuove colonne che vengono inserite nel problema principale. Supponendo, per semplicità, che gl'insiemi definiti dalle condizioni

siano limitati, ossia che nessuna variabile possa assumere valori indefinitamente grandi, si ha che tutte le soluzioni di tali sistemi possono essere espresse come combinazioni lineari convesse di un numero finito di soluzioni-base accettabili. Ogni soluzione X di [1] può quindi essere rappresentata come segue:

e ogni soluzione Y di [2] come:

dove X_i e Y_j sono le soluzioni-base accettabili rispettivamente di [1] e [2]. Ogni soluzione accettabile del sistema completo dei vincoli soddisfa pertanto, in termini delle λ_i e μ_j le seguenti condizioni:

dove si è posto:

Posto inoltre

il problema può essere riformulato come segue: minimizzare la funzione

sotto i vincoli [3].

In realtà, le soluzioni-base accettabili X_i e Y_j sono in generale troppo numerose per poter essere calcolate effettivamente: il metodo della decomposizione permette però di pervenire alla soluzione finale mediante la conoscenza di un numero molto ridotto di tali soluzioni -base.

Si supponga di aver determinato un numero sufficiente di vettori X_i e Y_j per poter trovare almeno una soluzione-base accettabile del sistema [3]. Siano questi i vettori X₁, ..., X_k1 e Y₁, ..., Y_l1. Si considera allora il "problema principale ridotto": minimizzare

sotto i vincoli

Siano λ₁, ..., λ_k, μ₁, ..., μ_l (k ≤ k₁, l ≤ l₁, k + l = m₃ + 2) le variabili-base di una soluzione-base ottima del problema principale ridotto. Si determinano i corrispondenti "moltiplicatori" π₁, ..., π_m3, s e t che soddisfano il sistema di equazioni:

dove p è il vettore con componenti π₁, ..., π_m3. Dalla teoria della dualità della p. l. si evince che la soluzione trovata è ottima per il problema originario se e soltanto se in corrispondenza di tutte le soluzioni-base accettabili X_i del problema [1] e Y_j del problema [2] risulta

ossia se e soltanto se

Ma

nell'insieme definito dalle condizioni [1], e analogamente

nell'insieme definito dalle condizioni [2]. Siamo quindi condotti a considerare i due subproblemi: minimizzare z₁(X) = (c^T −p^TĀ₁) X sotto le condizioni

e minimizzare

sotto le condizioni

Sia X₀ una soluzione-base ottima del primo subproblema e Y₀ del secondo. Se z₁(X₀) = s e z₂(Y₀) = t, la soluzione già trovata è ottima, altrimenti si torna al problema [3] introducendovi S₀ = Ā₁X₀ oppure T₀ = Ā₂Y₀ a seconda che z₁(X₀) − s ≶ z₂(y₀) − t. Il procedimento termina in un numero finito di iterazioni.

A titolo illustrativo si consideri il seguente problema.

Minimizzare C = − x₁ + 2x₂ + x₃ + y₁ + y₂ + y₃ sotto i vincoli:

Supponiamo d'iniziare con le soluzioni-base accettabili:

a cui corrispondono le quantità:

Il primo problema principale ridotto è quindi: minimizzare C = 8λ₁ + 8μ₁ + 4μ₂, sotto le condizioni

L'unica soluzione è data da:

I moltiplicatori π, s e t si ricavano dalle equazioni

che forniscono:

Si considera ora il primo subproblema:

minimizzare

sotto le condizioni

sotto i vincoli

La soluzione è data da:

Il secondo subproblema,

minimizzare

sotto i vincoli

ammette due soluzioni-base ottime che sono i vettori già individuati Y₁ e Y₂. Si ha:

Pertanto, soltanto l'introduzione di X₂ può portare a una diminuzione della funzione-obiettivo C. Si determina:

e si passa quindi a risolvere il problema principale nella seguente formulazione:

La soluzione-base ottima è:

I moltiplicatori corrispondenti sono:

Risulta ora: min z₁ = s e min z₁ = t e la soluzione ora trovata è quindi ottima per il problema originario. Il minimo cercato si ottiene pertanto ponendo:

e si ha:

L'estensione del metodo qui illustrato ai casi in cui non tutte le variabili sono limitate superiormente o a strutture con più di due subprogrammi non presenta difficoltà né pratiche, né teoriche. I principi su cui si fonda il metodo trovano applicazione anche in taluni problemi di p. l. a coefficienti variabili e in problemi di programmazione non lineare.

Programmazione lineare a variabili intere. - La crescente importanza che sta assumendo la cosiddetta p. l. "a variabili intere" si spiega non soltanto col fatto che molti problemi economici richiedono per loro natura la condizione d'interezza di tutte o alcune variabili, ma anche perché l'impiego di tale condizione può essere un utile espediente per affrontare complicati problemi di p. l. (per es., problemi in cui dev'essere soddisfatto non un determinato sistema di vincoli ma uno fra diversi sistemi alternativi) e anche certi problemi di p. non lineare. Considereremo in primo luogo i problemi in cui tutte le variabili devono essere intere.

Si prenda il problema: minimizzare C = c₁x₁ + ... + c_nx_n sotto i vincoli

Si supponga di aver risolto, col metodo del simplesso, il problema di p. l. che si ottiene trascurando la condizione che le variabili debbano assumere valori interi. Siano x₁, ..., x_m le variabili-base della soluzione finale. Nella tabella finale del simplesso si leggono le relazioni:

Se tutte le ï_i sono intere, ovviamente il problema è risolto. Se alcuni valori ï_i non sono interi si può procedere, seguendo una proposta di R. Gomory, operando un "taglio", ossia introducendo nel problema un vincolo lineare che esclude dall'insieme delle soluzioni la soluzione-base trovata senza però escludere nessuna delle soluzioni intere del sistema dato. Se, per es., ï₁ è frazionario, posto: ï₁ = N₁ + f_i, ā_1j = N_1j + f_1j (j = m + 1, ..., n), con N₁ e N_1j interi e 0 〈 f₁ 〈 1, 0 ≤ f_1j 〈 1 (quindi, se, per es., ā_1j = 2, 3, N_1j = 2, f_1j = 0, 3; se ā_1j = − 2, 3, N_1j = − 0,7) si trae dalla [4] per i = 1:

Il primo membro della [5] dev'essere intero e quindi anche il secondo. Poiché f₁ è frazione propria, ne risulta la condizione:

che non è soddisfatta dalla soluzione corrente in cui x_j = 0 (j = m + 1, ..., n). Con l'introduzione della variabile intera non negativa xn+I la disequazione [6] viene trasformata nell'equazione:

e si aggiunge questo nuovo vincolo al sistema originario. Se la soluzione del nuovo problema ancora non soddisfa la condizione che tutte le variabili siano intere, si prosegue allo stesso modo. Se il problema è solubile si perviene alla soluzione finale in un numero finito di passaggi.

Si consideri il seguente problema a variabili intere:

minimizzare C = x₁ − 2x₂ + 3x₃ + 3x₄ − 4x₅, sotto i vincoli

Il corrispondente problema di p. l. fornisce le seguenti posizioni, desunte dalla tabella finale del simplesso:

La soluzione-base che si ottiene ponendo x₁ = x₂ = x₃ = o non soddisfa la condizione che tutte le variabili siano intere. Applicando la [7] alla seconda delle [8] s'introduce allora il vincolo:

con x₆ intero e non negativo. Il corrispondente problema di p. l. ancora non fornisce una soluzione accettabile. S'introdurranno pertanto successivamente i vincoli

per pervenire alla soluzione finale:

Un altro procedimento, dovuto allo stesso Gomory e a T. C. Hu, può essere delineato come segue, sulla scorta del nostro esempio. Le prime due righe delle [8] possono essere così riscritte:

Poiché i secondi membri devono risultare interi, se ne ricava la condizione:

dove

Lasciando cadere la condizione di non-negatività di x₄ e x₅, si ricercano allora i valori interi non negativi di x₁, x₂ e x₃ che verificano la [9] nel modo più economico, i costi essendo desunti dall'ultima riga delle [8]. Si tratta quindi di risolvere il seguente problema che non è, ovviamente, un problema di p. l.:

con x₁, x₂ e x₃ ≥ 0 e intere, sotto il vincolo [9].

Seguendo i principi della programmazione dinamica, si risolvono i problemi di questo tipo nel modo seguente: si genera una sequenza di vettori ottenuti mediante l'operazione di addizione vettoriale modulo 1, in ordine crescente dei costi, scegliendo per ogni vettore la rappresentazione più economica. Ciò viene attuato attribuendo dapprima ai vettori dati e poi ai vettori che via via si generano un'"etichetta", ossia un vettore di due componenti di cui la prima esprime il costo e la seconda l'indice più elevato delle variabili xi che concorrono effettivamente alla sua formazione. Le etichette sono dapprima provvisorie, e a ogni stadio l'etichetta provvisoria col minimo costo diventa definitiva. se g₁, ..., g_k-1 sono vettori con etichetta definitiva e se a questi si aggiunge g_k, si considerano i vettori g₁ + g_k, g₂ + g_k, ..., g_k + g_k (modulo 1). se tali vettori sono già stati generati (con etichetta provvisoria) si mantiene l'etichetta col minor costo. Il procedimento ha termine quando si attribuisce l'etichetta definitiva al vettore P₀. Con un procedimento a ritroso si ricostruisce poi, attraverso le etichette, la soluzione ottima corrispondente. Se la soluzione è tale che sia soddisfatto il vincolo di non-negatività delle variabili-base (nel nostro caso x₄ e x₅), il problema originario è risolto.

Nel nostro esempio, si comincia dando rispettivamente a P₁, P₂ e P₃ le etichette provvisorie

Il minimo costo si trova nell'etichetta di P₃ che quindi diventa definitiva. Posto: P₃ = g₁ si forma: P₄ = g₁ (mod 1) =

con etichetta provvisoria

Ora l etichetta di P₂ diviene definitiva e, posto P₂ = g₂, si formano i vettori: P₅ = g₁ + g₁ =

con etichetta

Poiché il costo precedentemente trovato è minore di quello che si ottiene con l'operazione g₂ + g₂, si conserva l'etichetta precedente. L'etichetta di P₄ ora diventa definitiva e si pone P₄ = g₃. Procedendo in questo modo si trova:

con etichetta (definitiva):

Poiché dalla seconda componente dell etichetta si trae che x₃ ha valore positivo, si considera ora, nel procedimento a ritroso: P₀ − P₂ (mod 1) =

Poiché g₉ reca ancora nella sua etichetta il 3, si calcola g₉ − P₃ (mod 1) = P₁. Pertanto, la soluzione è: x₁ = 1, x₃ = 2. Tale soluzione è accettabile, poiché sostituita nelle [8] fornisce, come già si è visto: x₄ = 2, x₅ = 6, e quindi risulta rispettata la condizione di non-negatività delle variabili-base.

Per i problemi di p. l. parzialmente a variabili intere, si usa prevalentemente l'algoritmo dei tagli, opportunamente modificato. Al posto della [7], infatti, supposto che x₁ dev'essere intera, ma non le altre x, viene introdotta la condizione:

che dev'essere soddisfatta da ogni soluzione con x₁ intera, ma che non è soddisfatta dalla soluzione corrente.

Programmazione lineare stocastica. - Il crescente interesse, che la "p. l. stocastica" sta suscitando, si spiega in primo luogo con la constatazione che nei problemi concreti spesso tutte o alcune delle costanti del modello lineare impiegato non sono note con esattezza o possono subire variazioni considerevoli anche in breve periodo.

Dato un problema di p. l., per es., minimizzare C = c^Tx, con le condizioni

esso è detto problema di "p. l. stocastica" se alcuni o tutti i parametri (A, b, c) sono variabili casuali. Una prima distinzione da fare riguarda le informazioni di cui si è in possesso. Quando è nota la distribuzione di probabilità dei parametri si parla di p. l. stocastica in "condizioni di rischio". Quando non è nota, si usa la denominazione di p. l. stocastica in "condizioni d'incertezza".

Un primo approccio ai problemi in condizioni di rischio consiste nella ricerca della distribuzione del minimo della funzione obiettivo C al variare dei parametri aleatori. Tale approccio ha portato finora solo a risultati parziali e frammentari.

Maggiore sviluppo ha assunto un approccio che si può definire "deterministico", in quanto, anziché cercare una distribuzione di probabilità si formula il problema in modo che la sua soluzione coincida con quella di un problema "equivalente" non contenente termini aleatori. Tale equivalente deterministico in generale non è lineare, ma comunque risolubile con metodi noti. Esempi sono dati da problemi del tipo "a vincoli probabilistici", in cui si richiede che la soluzione soddisfi la i-esima disequazione del sistema dei vincoli con probabilità non minore di un α_i prefissato. Si tratta pertanto di "ottimizzare" una certa funzione f (c, x) sotto i vincoli:

I vincoli di non-negatività possono qui essere inclusi nei vincoli probabilistici. Se c è un vettore aleatorio, si può formulare in vario modo il criterio di ottimalità; per es. si può porre:

oppure

Nel caso che le a_ij siano costanti, è facile trovare l'equivalente deterministico delle [10]: se F_i(b) è la funzione di ripartizione di b_i, indicato con b_αi il più piccolo valore di b_i tale che F_i(b_αi) = 1 − α_i, le [10] equivalgono al sistema deterministico:

Anziché determinare a priori i valori di x che soddisfano il criterio scelto di ottimalità è anche possibile, seguendo un indirizzo sviluppato in particolare da A. Charnes, e W. W. Cooper, impostare il problema come ricerca di una funzione di decisione sequenziale (in generale lineare), in cui si determina x₁ all'inizio del primo periodo, x₂ all'inizio del secondo periodo, dopo che è stata osservata b₁ ed è stata determinata x₁ e così via; tutto questo nel rispetto dei vincoli probabilistici e al fine di ottimizzare la f(c, x).

Un'altra impostazione interessante dei problemi di p. l. stocastica, in condizioni di rischio, elaborata da vari studiosi, fra cui A. Madansky, G. B. Dantzig e A. Prekopa, ispirata ai principi della programmazione dinamica, è detta "programmazione a due stadi".

Si consideri il problema: minimizzare C = c^Tx, sotto le condizioni

in cui il sistema dei vincoli è costituito da equazioni e il vettore b è l'unico vettore aleatorio, con distribuzione di probabilità nota. È evìdente che un vettore x⁰ ≥ 0, soluzione del sistema per una data realizzazione b, diciamo b⁰, in generale non sarà soluzione ammissibile per altri valori di b. Pertanto, per ogni x ≥ 0 la differenza Ax − b è una variabile casuale la cui distribuzione dipende da b e da x. Supponiamo che sia sempre possibile, dopo aver scelto x e dopo aver osservato la realizzazione di 6, "porre rimedio" alla discrepanza Ax − b (che può rappresentare, per es., la differenza, positiva o negativa, fra produzione e domanda) con un vettore y di compensazione, pagando per questo una penalità che nel caso più semplice sarà lineare in y, poniamo d^Ty. Evidentemente il vettore y che si sceglie è quello che, oltre a colmare la discrepanza Ax − b rende minima la penalità. Il problema consiste pertanto nella determinazione di un vettore x ≥ 0, da scegliere prima che si conosca la realizzazione di b che minimizzi la funzione: c^Tx + min E (d^Ty) sotto vincoli del tipo:

dove B è una matrice costante. A problemi più complessi, di cui si è iniziato lo studio, si perviene quando anche A e/o B si considerano stocastiche.

I problemi di p. l. stocastica in condizione d'incertezza sono stati affrontati finora in modo meno esteso, secondo un'impostazione che si riconduce alla teoria dei giochi nella forma di gioco a due persone a somma nulla tra un giocatore e la natura. La natura sceglie i parametri A e b e il giocatore sceglie la soluzione x, nell'ambito delle strategie pure o miste.

Bibl.: Autori vari, Recent advances in mathematical programming (a cura di L. Graves, Ph. Wolfe), New York 1963; G. B. Dantzig, Linear programming and extensions, Princeton 1963; Autori vari, Integer and nonlinear programming (a cura di J. Abadie), Amsterdam 1970; S. Vajda, Probabilistic programming, New York 1972.