Programmazione lineare
Programmazione lineare
di Robert Dorfman
Programmazione lineare
Introduzione
La programmazione lineare è una famiglia di metodi matematici per individuare i modi più redditizi o in altro modo ottimali di impiegare le risorse in un'impresa o in altri tipi di organizzazione. Il metodo di base fu inventato nel 1947 da G.B. Dantzig per consentire all'aviazione militare statunitense la programmazione dell'addestramento e dell'approvvigionamento, e per l'attuazione di altri programmi atti a conseguire determinati obiettivi nel modo più efficiente ed economico. A partire dalle originarie applicazioni militari, l'ambito della programmazione lineare si è successivamente allargato a una gamma pressoché illimitata di problemi economici, aziendali, sociali e scientifici. Nonostante questa notevole estensione del campo di applicazione, e sebbene le iniziali restrizioni matematiche siano in larga misura venute a cadere, il metodo continua a conservare la denominazione originaria.Il concetto chiave della programmazione lineare è quello di attività. Si definiscono come 'attività' tutte le operazioni di un'organizzazione o delle sue componenti che comportano l'uso di quantità specifiche di risorse e la produzione di risultati esattamente proporzionali alle risorse impiegate.In base a questa definizione, anche una ricetta culinaria è un'attività, in quanto specifica le proporzioni in cui devono essere usati i diversi ingredienti e la quantità che verrà prodotta della pietanza così ottenuta. Se la ricetta è usata per produrre quantità maggiori o minori della pietanza in questione, gli inputs e gli outputs dovranno variare in proporzioni esattamente stabilite. Se si cambiano le dosi, si avrà, per definizione, una ricetta diversa.
Chiaramente, sono numerosissime le operazioni e i fenomeni che possono essere definiti come attività. Nel caso di una raffineria di petrolio, ogni miscela di prodotto grezzo da cui si ottiene un barile di combustibile raffinato costituisce un'attività. Nel caso di una ferrovia, ogni treno passeggeri composto di un certo numero di carrozze con un'origine e una destinazione precisa costituisce un'attività, e via dicendo. Quando si interpretano le operazioni di un'organizzazione in termini di insiemi di attività vengono presupposti implicitamente alcuni importanti assunti. Due di essi sono particolarmente importanti. Il primo è che il livello al quale un'attività viene esercitata può variare entro un continuum piuttosto ampio di valori. Ad esempio, l'attività consistente nel preparare un dolce secondo una determinata ricetta può essere esercitata per produrre qualsivoglia numero non negativo di dolci - due, oppure cento, oppure un valore qualunque π pari a 3,1415927 - e la quantità di ciascun ingrediente richiesto sarà strettamente proporzionale al numero di dolci prodotti. Sul piano pratico, naturalmente, molte attività - come la preparazione di un dolce dell'esempio citato - non soddisfano alla lettera questo assunto (non si può impastare un numero di dolci pari a π), ma l'assunto di un'estensione continua di livelli di attività può costituire un'approssimazione adeguata alla gamma di scelte di una pasticceria che produce centinaia di dolci al giorno.Il secondo assunto è che un'organizzazione possa esercitare numerose attività contemporaneamente, e che i livelli ai quali sono esercitate le singole attività possano variare senza influenzarsi reciprocamente. Ciò significa escludere che le attività possano interagire o influenzarsi reciprocamente in qualsiasi modo, ossia escludere ciò che gli economisti chiamano economie di scala e di varietà (scope economies), e i biologi simbiosi e antagonismo. Nondimeno, tale assunto può essere una buona approssimazione rispetto agli effetti delle scelte in molte situazioni pratiche.
Per illustrare l'utilità del concetto di attività prenderemo come esempio una versione ridotta del primo problema risolto con la programmazione lineare, il cosiddetto 'problema dietetico'. Nella versione originaria il problema era quello di determinare il menù più economico in grado di soddisfare il fabbisogno quotidiano di nove sostanze nutritive partendo da una lista di quindici alimenti con un valore nutritivo noto. Il problema era formulato in termini di programmazione lineare in quanto considerava la somministrazione di ciascun alimento come un'attività che fornisce un determinato apporto di calorie, proteine, vitamine, ecc.; l'obiettivo era quello di identificare le combinazioni di alimenti - o di attività - in grado di soddisfare tutti i requisiti alimentari specificati, per poi scegliere la combinazione 'ammissibile' più economica. Questo problema fu risolto prima che fossero inventati i computer elettronici, e richiese una notevole mole di lavoro con i calcolatori meccanici. Attualmente lo stesso problema potrebbe essere risolto in meno di tre minuti con un moderno computer da tavolo.
Il nostro esempio si basa su una versione notevolmente ridotta di tale problema.
Supponiamo che un individuo si trovi a dover soddisfare il proprio fabbisogno di tre vitamine - vitamina A, tiamina e riboflavina - alimentandosi esclusivamente di latte e pomodori. I dati rilevanti sono presentati nella tab. I, e i vincoli corrispondenti nella figura. Secondo tali dati, il fabbisogno di vitamina A può essere soddisfatto consumando una quantità di latte pari al valore di 17 lire, o una quantità di pomodori del valore di 2,3 lire, o una qualunque combinazione di latte e pomodori che giace sulla retta indicata con 'vitamina A' nella figura. Qualunque combinazione che si trova a nordest della retta soddisfa il fabbisogno con un qualche margine d'avanzo.
Le altre due diagonali rappresentano analogamente combinazioni di latte e pomodori che soddisfano i fabbisogni delle altre due vitamine. Di conseguenza, tutte le diete che soddisfano i requisiti alimentari richiesti corrispondono a punti che giacciono nella regione convessa il cui confine inferiore è rappresentato dalla retta spezzata ABCD. Il passo successivo consiste nell'individuare il punto della regione ammissibile corrispondente alla dieta più economica; come si evince chiaramente, tale punto sarà uno degli angoli A, B, C, D. In particolare, sarà l'angolo B, giacente sulla più bassa retta di isocosto che tocca la regione ammissibile. La linea tratteggiata nella figura rappresenta la retta di isocosto inferiore che soddisfa tutti i fabbisogni alimentari; tutte le altre rette di isocosto sono parallele a essa.Le proprietà essenziali delle soluzioni dei problemi di programmazione lineare verranno illustrate in dettaglio nei capitoli seguenti. Qui richiameremo l'attenzione su una particolarità: sebbene tutte le relazioni siano continue, ovvero lineari, un cambiamento lineare nei prezzi delle attività può determinare discontinuità nei livelli ottimali di queste ultime. Per risolvere il problema dietetico semplificato è stato sufficiente ispezionare un grafico bidimensionale. Tuttavia i grafici di questo tipo risultano inadeguati quando le attività considerate sono più di due, e i calcoli diventano sempre più gravosi via via che aumenta il numero di attività, sebbene i principî all'opera restino sempre gli stessi.
Per far fronte a questa difficoltà si rende necessaria una formulazione algebrica dei problemi di programmazione lineare. È quanto faremo nel prossimo capitolo in cui illustreremo altresì l'importante proprietà generale della dualità. Nel terzo capitolo descriveremo il 'metodo del simplesso', che fu il primo metodo messo a punto e che, con qualche perfezionamento, è tuttora il più usato per risolvere i problemi di programmazione lineare; nel capitolo successivo ne illustreremo il funzionamento applicandolo al problema dietetico semplificato. Nel quarto capitolo menzioneremo due metodi alternativi proposti di recente. Infine, parleremo di alcune applicazioni ed estensioni particolari della programmazione lineare.
Formulazione algebrica dei problemi di programmazione lineare; il fenomeno della dualità
Nel capitolo introduttivo abbiamo definito la ricerca operativa come uno strumento di gestione economica o aziendale. Più precisamente, si tratta di una branca della matematica applicata, ossia della programmazione matematica, che consiste a sua volta nella ricerca del massimo o del minimo di una funzione con più variabili (spesso, in pratica, centinaia o migliaia) soggette alla condizione di giacere in una data regione chiusa, convessa.Un esempio assai semplice di problema di programmazione è trovare il rettangolo che abbia l'area maggiore possibile entro un perimetro che non superi una lunghezza data. In questa formulazione del problema si celano tre disuguaglianze: né la lunghezza né la larghezza possono essere negative, e la loro somma non deve superare un dato massimo. Di solito, non si presta attenzione a tali disuguaglianze: in questo caso il senso comune ci dice che le dimensioni in questione non possono essere negative, e che un perimetro inferiore al massimo consentito non può racchiudere l'area maggiore possibile. Inconsciamente, quindi, si riduce il problema a un problema standard di massimizzazione, e lo si risolve immediatamente col calcolo. Tuttavia, se in casi banali come questo l'uso del calcolo per risolvere un problema di programmazione matematica può dare buoni risultati, in situazioni meno intuitive risulta inaccettabile. La programmazione matematica, al pari di altri modelli matematici, è notoriamente lontana dal senso comune.
Ciò che distingue i problemi di programmazione dai problemi standard di estremo vincolato è la presenza di disuguaglianze tra i vincoli. Per quanto strano possa sembrare, i vincoli costituiti da disuguaglianze non ebbero pressoché alcun ruolo nelle applicazioni al campo della fisica a partire dalle quali venne sviluppata nel XIX secolo la matematica applicata. Essi invece costituiscono la norma delle applicazioni in campo economico, aziendale e sociale, che vanno acquistando importanza crescente e sono fondamentali nella programmazione matematica.La programmazione lineare è un caso speciale di programmazione matematica in cui tutte le relazioni tra le variabili, tanto la funzione obiettivo da massimizzare (o minimizzare) quanto le relazioni che definiscono la regione ammissibile, sono lineari. Il problema dietetico illustrato in precedenza è un caso tipico. Dal punto di vista matematico, la programmazione lineare consiste nel massimizzare (o minimizzare) il valore di una funzione lineare con parecchie variabili soggette a vincoli lineari che includono alcune disuguaglianze.
I problemi di programmazione lineare possono essere formulati in vari modi o usando terminologie differenti. Un sistema è quello di scrivere tutte le relazioni per esteso: scegliere n variabili xj, j=1,..., n (ad esempio i livelli di j attività), per massimizzare la somma
essendo le variabili soggette alle m disuguaglianze
Le disuguaglianze possono includere o meno restrizioni di segno, come xj ≥ 0.
Lo stesso problema, espresso in una notazione più compatta, diventa:massimizzare ctx,dove ct è il vettore riga a n componenti dei coefficienti delle variabili xj nella funzione da massimizzare e x è il vettore colonna a n componenti delle variabili scelte, soggette ai vincoli
dove A indica la matrice m x n dei coefficienti (aij), e b è il vettore colonna di vincoli costanti a m componenti. D'ora in avanti useremo quasi sempre questa notazione più compatta e generale.
La più notevole proprietà della programmazione lineare è detta dualità. I problemi di programmazione lineare si presentano a coppie: al problema presentato sopra, detto primale, se ne può associare un altro, il suo duale, che risulta dalla seguente manipolazione formale dei dati del primale. L'obiettivo del duale è:minimizzare ptBdove pt è il vettore riga a m componenti di 'variabili duali'. I vincoli nel problema duale sono:
Si osservi che il problema duale è stato ottenuto dal primale applicando le seguenti quattro regole: 1) il duale di un problema di massimizzazione è un problema di minimizzazione, e viceversa; 2) il segno di ogni vincolo espresso da una disuguaglianza nel primale è invertito nel duale (ma né le variabili del primale né quelle del duale possono avere segno negativo); 3) i coefficienti delle variabili nella funzione da massimizzare (o da minimizzare) nel primale sono interscambiati con le costanti nei vincoli; 4) se nel primale la matrice dei vincoli è postmoltiplicata per un vettore di variabili primali, essa è premoltiplicata per il vettore di variabili duali nel duale, e viceversa.
A quanto risulta, il primo a rilevare l'esistenza e l'importanza del fenomeno della dualità fu John von Neumann, il quale lo segnalò a Dantzig allorché questi gli espose la sua recente scoperta della programmazione lineare, senza peraltro divulgare in una pubblicazione la sua intuizione. La teoria dei duali fu in seguito sviluppata più estesamente da Albert W. Tucker dell'Università di Princeton e dai suoi allievi, in particolare da David Gale e da H. W. Kuhn. In questa sede presteremo attenzione al significato intuitivo e concreto della dualità, senza addentrarci nei particolari tecnici della sua dimostrazione e delle sue proprietà formali.
Alcune conseguenze delle definizioni della dualità fornite in precedenza sono di evidenza talmente immediata che possono essere discusse ancor prima di analizzare i significati dei concetti. Consideriamo una situazione in cui un problema e il suo duale abbiano entrambi soluzioni ammissibili, ossia in cui esistano una x e una p tali da soddisfare rispettivamente tutti i vincoli del primale e tutti i vincoli del duale. Si premoltiplichino i vincoli del primale per pt al fine di ottenere ptAx≤ptb. Analogamente, si postmoltiplichino i vincoli del duale per ottenere ptAx≥ctx. Ponendo insieme le due disuguaglianze, si avrà ctx≤ptb.
Detto in forma discorsiva, l'ammontare dei profitti nel primale ottenuto, usando un determinato insieme di livelli di attività ammissibili, non può superare il valore della funzione obiettivo duale, ottenuto usando prezzi-ombra ammissibili. Inoltre, se x e p sono tali che ctx = ptb, allora il valore della funzione obiettivo primale ha raggiunto il suo limite massimo, la funzione obiettivo duale il suo limite minimo, e x e p sono le soluzioni ai rispettivi problemi. Vedremo in seguito ulteriori implicazioni.
Rivolgiamo ora l'attenzione a un'applicazione specifica e di grande importanza della programmazione lineare. Consideriamo un'impresa o un'altra organizzazione le cui operazioni siano limitate dalle quantità disponibili di m risorse fisse. In questo caso, b è il vettore delle quantità disponibili di una risorsa, cj specifica il contributo di una j-esima attività all'obiettivo dell'impresa (in questo caso il profitto), c è il vettore formato dalle componenti cj, e l'elemento tipico, ai j, della matrice dei vincoli A specifica l'ammontare della i-esima risorsa richiesta da un'unità della j-esima attività. Gli unici dati nuovi introdotti dal duale sono gli elementi pi di p. Tali elementi pi sono interpretati come prezzi, detti generalmente prezzi-ombra, che rappresentano i valori marginali delle risorse per l'azienda. Così pi è l'incremento del profitto annuale reso possibile da un'unità addizionale della risorsa i-esima, e ptb, la funzione obiettivo del duale, è il valore-ombra aggregato delle risorse utilizzate dall'impresa.
A prima vista potrebbe sembrare assurdo che l'obiettivo dell'impresa sia quello di minimizzare il valore imputato alle risorse che essa impiega. In realtà, il significato del problema duale, in questo contesto, è quello di misurare i prezzi delle risorse dell'impresa in modo tale che il contributo di ciascuna attività ai profitti sia imputato completamente alle risorse (i vincoli) senza sopravvalutare il potenziale di guadagno dell'insieme di risorse di cui l'impresa dispone.
I vincoli del duale hanno un'importante implicazione per il comportamento dell'impresa. Nelle soluzioni dei problemi primale e duale, il valore totale delle risorse utilizzate da un livello unitario di qualsivoglia attività (poniamo Σi aij pi per la j-esima attività) sarà esattamente eguale al contributo che essa apporta ai profitti dell'impresa (cj) se l'attività è esercitata a un livello positivo, mentre il valore-ombra delle risorse richieste da un'unità di un'attività unitaria esercitata a livello nullo, ossia non utilizzata affatto, può essere maggiore della redditività unitaria di tale attività. Se il costo delle risorse richieste da un livello unitario di attività è superiore al contributo di quest'ultimo ai profitti dell'impresa, quell'attività è improduttiva e non dovrebbe essere impiegata. Torneremo in seguito su questa implicazione.
L'interazione tra un problema e il suo duale può essere vista più chiaramente scrivendo i problemi nella notazione estesa. Sia l'i-esimo vincolo del primale:
Se la diseguaglianza stretta sussiste nella soluzione del primale, la quantità disponibile della risorsa iesima non è pienamente utilizzata nel programma di massimizzazione del profitto. Il potenziale di profitto dell'impresa non aumenterebbe se fosse disponibile un'unità addizionale di tale risorsa, né diminuirebbe se un'unità di detta risorsa venisse sottratta. In breve, il valore ombra di tale risorsa, pj, è zero.
Questa proprietà, assieme all'interpretazione suddetta dei vincoli del duale, dà luogo alle cosiddette 'condizioni di Kuhn-Tucker': se nella soluzione del problema primale un vincolo è soddisfatto come disuguaglianza, allora la variabile che nel duale corrisponde a tale vincolo è nulla, e viceversa. Questa proprietà ha un'importante implicazione.
Consideriamo in primo luogo il primale. Esso richiede che nella soluzione, per ogni vincolo, o:
Se si moltiplicano i due membri di questa equazione per pi, si avrà:
sia che il vincolo i-esimo sia stato soddisfatto come uguaglianza oppure no. Addizionando queste equazioni per tutti i valori di i, si ottiene:
Il problema duale si presta a un'analisi simile. Come abbiamo già osservato, nella soluzione del duale i valori delle risorsa pi soddisfano la condizione che, per ogni attività j, o
Moltiplicando entrambi i membri dell'equazione per xj si ottiene un'eguaglianza, sia che Σi aij pi=cj, oppure no. Allora, sommando per tutti i valori di j, si ha:
Di conseguenza, i valori dei livelli di attività che risolvono un problema primale e i prezzi ombra della risorsa che risolvono il suo duale producono valori eguali in entrambe le funzioni obiettivo. In sintesi, non è possibile risolvere un problema primale di programmazione lineare senza risolvere, almeno implicitamente, il suo duale, e viceversa (per una discussione più approfondita della dualità, v. Hadley, 1962; v. Dantzig, 1963).
Soluzione dei problemi di programmazione lineare; il metodo del simplesso
Una serie di modelli economici e di gestione aziendale furono formulati in termini di disuguaglianze lineari assai prima che Dantzig sviluppasse il metodo del simplesso. Tuttavia essi rimasero curiosità di scarso rilievo data la mancanza di un metodo pratico per risolverli o per dimostrarne le implicazioni. Verso la fine degli anni quaranta una svolta venne segnata da due intuizioni cui si arrivò in modo indipendente: Dantzig scoprì il metodo del simplesso per risolvere i problemi di programmazione lineare, e Maurice Wilkes dell'Università di Cambridge e J. Presper Eckert e John U. Mauchley dell'Università di Pennsylvania misero a punto quasi contemporaneamente i primi calcolatori elettronici a programma - scoperte basate entrambe su un'idea di John von Neumann. Il metodo del simplesso di Dantzig e le sue varianti restano tuttora i più usati per risolvere i problemi di programmazione lineare, ma senza i computer elettronici a programma i calcoli notevolmente ripetitivi che essi richiedono sarebbero scarsamente fattibili.
L'elemento chiave del metodo del simplesso è chiamato a volte 'teorema di base', sia per la centralità che esso ha per tale metodo e per le sue varianti, sia perché si fonda sul concetto matematico di base. Nell'algebra delle matrici e dei vettori si definisce base di uno spazio un insieme di vettori linearmente indipendenti, tale che tutti i vettori nello spazio possono essere espressi come somme di multipli dei vettori dell'insieme. 'Dimensione' di uno spazio vettoriale è il numero di vettori delle sue basi. Applicando questi concetti alla programmazione lineare, i vettori sono costituiti dalle attività, e la dimensione è data dal numero di vincoli linearmente indipendenti. Il teorema di base afferma che il numero di attività esercitate a livelli positivi nella soluzione di un problema di programmazione lineare non deve mai essere maggiore del numero dei vincoli. Il problema si riduce così al problema combinatorio di individuare le attività da esercitare. È questa la forma del problema che il metodo del simplesso risolve.Il metodo in questione si basa su un procedimento in due fasi. La prima fase consiste nell'individuare una base ammissibile, vale a dire una base, o un insieme di attività, in grado di soddisfare i vincoli senza che alcuna attività sia esercitata a livelli negativi, il che sarebbe assurdo. Vedremo tra breve che questa fase è relativamente banale.La seconda fase consiste in un processo iterativo che partendo da una base ammissibile la migliora progressivamente sostituendo un'attività presente nella base con una nuova, scelta in modo da aumentare il valore della funzione obiettivo (o da diminuirlo, in un problema di minimizzazione). Poiché l'insieme di attività contiene un numero finito (sebbene a volte estremamente elevato) di basi, le iterazioni devono infine raggiungere un punto in cui nessuna delle attività inutilizzate aumenterà il valore della funzione obiettivo. Quando ciò accade il problema è risolto, e con esso, come abbiamo visto, il suo duale. Esistono attualmente numerosi programmi per calcolatore che eseguono automaticamente questa operazione a una velocità soddisfacente.
Chiarite queste nozioni di base, possiamo illustrare la logica applicata dai computer per risolvere un problema standard di massimizzazione. Consideriamo nuovamente il problema di massimizzazione del profitto: oppure, nella notazione estesa: in cui le xj devono soddisfare: oppure, usando la notazione estesa: dove x ≥ 0, oppure xj ≥ 0.Per semplificare l'esposizione, assumeremo b>0, sebbene l'argomento di fatto non lo richieda. È utile trasformare il primo insieme di disuguaglianze in equazioni aggiungendo m variabili ausiliarie (slack), yi, yi≥0, che indicano inputs sottoutilizzati e per questo motivo vengono solitamente chiamate 'variabili slack'; si otterranno così le eguaglianze: Tali equazioni sono equivalenti alle disuguaglianze che sostituiscono in quanto le variabili ausiliarie non possono essere negative. Un'ovvia base ammissibile è yi=bi, con ogni xj=0; tuttavia essa ha lo svantaggio che il valore della funzione obiettivo risulta eguale a zero. La difficoltà viene superata procedendo alla fase successiva.
Ogni iterazione nella seconda fase comporta una quantità di notazioni e una serie di operazioni algebriche che i programmi dei computer sono in grado di eseguire automaticamente. L'iterazione inizia con una base accettabile, ossia con una scelta di m attività e di variabili ausiliarie, operanti tutte a livelli positivi. La base ottenuta nella prima fase soddisfa tali requisiti, poiché in essa solo le m variabili ausiliarie hanno valori positivi. Arriviamo ora al cuore della procedura. Sia AB la matrice m x m formata dagli m vettori delle attività esercitate a livelli positivi, ossia inclusi nella base, e xB il vettore dei livelli ai quali sono esercitate. Si avrà immediatamente xB>0 e AB xB=b. Consideriamo ora una attività che non si trovi nella base attuale, e definiamo A₀ il vettore dei suoi coefficienti nei vincoli; sia inoltre c₀ il profitto unitario di tale attività conformemente alla funzione obiettivo. Vogliamo ora confrontare tale profitto unitario con la redditività della combinazione di attività comprese nella base attuale che ha lo stesso effetto sui vincoli. Poniamo che tale combinazione sia Z₀, dove Z₀ è la soluzione di AB Z₀=A₀. Indicando con cB il vettore delle redditività unitarie delle attività nella base, la redditività totale della combinazione Z₀ è ctB Z₀, oppure, il che è lo stesso, Σj cj zj, in cui la somma è ricavata dalle attività nella base e zj è il livello di attività (o variabile ausiliaria, slack variable) j in Z₀. Se c₀, ossia la redditività unitaria dell'attività A₀, è maggiore di ctB Z₀, ossia la redditività di una combinazione equivalente di attività presenti nella base, allora la redditività dell'impresa aumenterà sostituendo almeno una piccola quantità di A₀ con una quantità della combinazione equivalente che impiega le stesse risorse.Se l'attività A₀ è aggiunta alla base a un livello basso, il profitto annuale sarà incrementato, ma il programma conterrà troppe attività per costituire una base. Al fine di trovare una base più adatta di quella iniziale, occorre aumentare le risorse in A₀ sottraendole ad AB nelle proporzioni date da Z₀, sino a ridurre a zero il livello di uno dei vettori della base a seguito della assegnazione delle risorse da esso impiegate ad A₀.
Quando e se ciò si verifica, si è trovata una base migliore, in cui A₀ sostituisce l'attività che è stata azzerata. La procedura iterativa può essere replicata, ma i segni degli elementi di Z₀ devono essere tali che i livelli delle attività nella vecchia base non diminuiscono all'aumentare del livello di A₀. In tal caso l'aritmetica dice, letteralmente, che non esiste un limite massimo al valore che la funzione obiettivo può assumere; ciò significa che è stato commesso un errore nella formulazione del problema. Infine, se ctB AB≥0 per tutte le attività A₀ che non si trovano nella base attuale, è stato trovato l'ottimo e il problema è risolto.
Applicazione del metodo del simplesso al problema dietetico semplificato
La formulazione algebrica piuttosto astratta del metodo del simplesso presentata nel capitolo precedente può essere esemplificata in concreto applicandola al problema dietetico nella versione ridotta. I dati della tab. I necessitano di una qualche preparazione prima di iniziare il calcolo. Il fabbisogno quotidiano, 100%, dovrebbe essere esplicitato. Cosa ancora più importante, devono essere aggiunte delle attività ausiliarie o slack (ossia corrispondenti a inputs sottoutilizzati) per sostituire con equazioni le disuguaglianze presenti nella soluzione grafica. La formulazione più completa dei dati è mostrata nella tab. II.Si noti che nella tab. II i coefficienti delle attività ausiliarie hanno segno negativo, e ciò perché nel nostro esempio i vincoli significano 'almeno' anziché, come di consueto, 'non più di'. I coefficienti negativi delle attività slack 1, slack 2, slack 3 consentono di soddisfare i requisiti alimentari richiesti.
Trovare una base iniziale accettabile è sempre facile, in questo caso addirittura banale. Si noti che tutti e tre i requisiti alimentari possono essere soddisfatti consumando una quantità adeguata dei due alimenti. Scegliamo arbitrariamente il latte. Un consumo quotidiano di 16,6667 lire di latte consente di soddisfare esattamente il fabbisogno di vitamina A, mentre i fabbisogni delle altre vitamine verranno soddisfatti con un margine di sottoutilizzo. Così le attività latte, slack 2 e slack 3 costituiscono una base ammissibile per questo problema. I livelli delle tre attività della base (xB nella notazione algebrica) che costituiscono la soluzione sono mostrati nella colonna indicata con vincoli. I livelli delle variabili della base che producono gli stessi risultati delle attività escluse (corrispondenti alla matrice Z₀) sono mostrati nelle colonne indicate con pomodori e slack 1 (tali valori sono stati trovati risolvendo le equazioni simultanee appropriate).Il costo che comporta soddisfare i requisiti alimentari usando le attività presenti nella base, e solo esse, è stato trovato moltiplicando i livelli di attività nella colonna vincoli della tab. II per i costi unitari delle attività - ossia una lira per una lira di pomodori e un costo assunto eguale a zero per le attività ausiliarie - e addizionando. I risultati sono riportati nella riga 'Costi indiretti' della tab. II. I costi diretti delle attività escluse sono i loro coefficienti nella funzione obiettivo, 1 per l'uno o l'altro alimento e 0 per ogni attività ausiliaria.In questo caso, il costo diretto comportato dal consumo di 1 lira di pomodori è minore del costo comportato dall'impiegare unicamente le attività della base per ottenere lo stesso risultato. Si ottiene un risparmio includendo nella base l'attività pomodori. Con lo stesso ragionamento, slack 1, il cui costo diretto è superiore a quello indiretto, si dovrebbe escludere. L'attività della base che dovrà essere sostituita con pomodori sarà quella il cui livello si azzera per primo quando il livello dell'attività pomodori cresce al disopra dello zero. Tale attività risulta essere slack 2.
La nuova base che ne risulta, latte, pomodori, slack 3, è mostrata nella tab. III, del tutto analoga alla II. I dati rilevanti per la nuova base sono riportati nelle prime tre righe, sotto vengono indicate le soluzioni delle equazioni ottenute usando la nuova base, e nelle ultime due righe i loro costi diretti e indiretti. Il costo del soddisfacimento dei requisiti alimentari è stato diminuito a circa 10,5 lire, e il costo diretto di slack 1 è minore del suo costo indiretto. Si procede così, come mostra la tab. IV, a introdurre slack 1 al posto di slack 3.
Con questa base, il costo comportato dal soddisfacimento dei requisiti alimentari è stato ridotto a 7,84 lire al giorno. I costi diretti di entrambe le attività escluse superano quelli indiretti. Di conseguenza, nessun'altra attività dovrebbe essere introdotta nella base, e si è così trovata la dieta, o il programma ottimale.
Metodi alternativi
Il metodo del simplesso per risolvere i problemi di programmazione lineare è rimasto sostanzialmente indiscusso per 38 anni, nonostante non siano cessate le speranze di trovarne uno più soddisfacente. Il metodo del simplesso infatti procede da un punto di partenza arbitrario per arrivare progressivamente alla soluzione ottimale, ossia spostandosi da una soluzione-base accettabile a una migliore a essa adiacente, che differisce solo per un'unica attività. Ne risulta un percorso che si muove lungo i confini della regione ammissibile, il che equivale ad andare da Genova a Venezia via mare, con un viaggio di circa 2.000 km, sebbene in linea d'aria le due città distino solo 325 km.
Questa constatazione suggerì l'idea di ridurre notevolmente i calcoli attraversando direttamente la regione ammissibile per arrivare alla soluzione ottimale, anziché muoversi lungo i suoi confini. Numerosi metodi 'dei punti interni' vennero proposti e sperimentati, ma nessuno altrettanto efficiente quanto il metodo del simplesso. Nel 1979, tuttavia, L. G. Khachiyan mise a punto un metodo che sul piano teoretico è superiore a quello del simplesso per problemi di grandi dimensioni (ossia problemi con un numero elevatissimo sia di vincoli che di variabili. Problemi del genere esistono e sono stati risolti). Tuttavia risultò che in pratica l'algoritmo del simplesso era notevolmente più efficiente di quello di Khachiyan anche per problemi di grandi dimensioni.La scoperta di Khachiyan tuttavia fu un segnale promettente, e la ricerca continuò. Cinque anni dopo, N. K. Karmarkar presentò un nuovo algoritmo completamente diverso, che oltre a essere teoricamente preferibile a quello del simplesso per problemi di grandi dimensioni, era anche efficiente in pratica. Tale metodo e alcune sue versioni perfezionate sono correntemente impiegati per vari problemi di grandi dimensioni, e tuttavia per quelli di dimensioni più modeste il metodo del simplesso continua a essere il più usato. Esistono attualmente parecchi programmi di computer assai efficienti (eseguibili anche con un personal computer), che usano l'algoritmo del simplesso o sue varianti per risolvere problemi di programmazione lineare, ma la ricerca di un sostituto continua, e alla fine, con tutta probabilità, sarà coronata dal successo (per una discussione dettagliata dei metodi di Khachiyan e di Karmarkar v. Winston, 1995²).
Applicazioni ed estensioni della programmazione lineare
La programmazione lineare si è diffusa con grande rapidità e ha avuto una varietà di applicazioni. Nei dieci anni intercorsi dalla ideazione dell'algoritmo del simplesso, il primo e tuttora il principale metodo di soluzione messo a punto, la programmazione lineare è stata applicata in tutto il mondo nei più diversi ambiti - da governi, aziende, organizzazioni militari, scienziati, ecc. - per risolvere una sorprendente varietà di problemi pratici. Non è difficile capire il perché. In primo luogo, il tipo di problemi che essa tratta - problemi di massimizzazione o di minimizzazione in cui le variabili sono soggette a vincoli costituiti da disuguaglianze - si ritrova in un'ampia gamma di contesti per i quali non sussiste un altro metodo di soluzione altrettanto semplice e flessibile. In secondo luogo, il concetto fondamentale, quello di attività, per quanto per certi versi nuovo, è piuttosto semplice, e non è che la formalizzazione di approcci preesistenti di tipo prevalentemente intuitivo, come quelli basati sul concetto di fattori di produzione. In terzo luogo, tale metodo è in sintonia con un clima intellettuale generale di quantificazione, formalizzazione e burocratizzazione ereditato dalla centralizzazione e dalla pervasiva pianificazione economica e militare della seconda guerra mondiale. Alcuni esempi illustreranno la varietà di applicazioni della programmazione lineare.
Problemi di miscela di componenti. - Un campo di applicazione è quello della dietetica (il problema illustrato in precedenza è un esempio storico ma irrilevante). Con la programmazione lineare si è dimostrato che per l'uomo la dieta bilanciata più economica è composta quasi esclusivamente di cereali e legumi, come scoprirono migliaia di anni fa le società contadine più povere. La programmazione lineare è utilizzata attualmente dalle industrie di mangimi animali per scoprire le formule accettabili più economiche. A essa fanno ricorso anche i proprietari di raffinerie di petrolio, sempre in cerca dei modi ottimali di allocare la loro capacità a fronte delle costanti oscillazioni dei prezzi dei vari tipi e qualità di petrolio grezzo e di prodotti raffinati.Problemi di trasporto. - T. C. Koopmans fu il primo a risolvere un problema di trasporto con una variante dell'algoritmo del simplesso circa tre anni prima che Dantzig scoprisse la soluzione generale ai problemi di programmazione lineare. Ciò dimostra tanto l'ingegnosità di Koopmans quanto la grande semplicità dei problemi di trasporto, che li rende uno dei più diffusi campi di applicazione della programmazione lineare.Il tipico problema di trasporto è quello che deve affrontare un'impresa, ad esempio una cartiera, che ha stabilimenti e clienti dislocati in vari punti. Essa vorrà assegnare le ordinazioni dei clienti ai diversi stabilimenti in modo da minimizzare i costi di nolo. In termini di programmazione lineare, il problema può essere formulato come segue: siano i, j le attività di spedizione marittima di una unità (poniamo una tonnellata) di prodotto dallo stabilimento i al cliente j, e sia xij il numero di unità spedite. Il problema è quello di trovare valori non negativi delle xij in modo da minimizzare Σij cij xij, posto che il costo di spedizione di una tonnellata di prodotto da i a j sia cij. Le xij sono soggette a due vincoli. Il primo è che le spedizioni totali dello stabilimento i non devono eccedere la sua capacità, ossia Σj xij ≤ ki. Il secondo è che il totale delle spedizioni al cliente j deve eguagliare l'ammontare delle sue ordinazioni, ossia Σi xij=oj, per ogni valore di j. Ora, ogni livello di attività, xij, compare precisamente sotto due vincoli, e in entrambi i casi è moltiplicato solo per unità. Dato questo tipo speciale della matrice dei vincoli, è possibile risolvere il problema duale, da cui si ricava facilmente il primale, senza inversioni di matrici e altre complesse operazioni matematiche che rappresentano l'aspetto più gravoso dei calcoli di programmazione lineare. Di fatto, problemi di piccole dimensioni possono essere risolti usando semplicemente carta e matita.
Problemi di tipo analogo si presentano nella progettazione di circuiti elettrici e in molti altri contesti.
Problemi di assegnazione. - Un problema di assegnazione sorge quando un'organizzazione di qualche tipo ha n unità di una data risorsa - insegnanti, macchine, edifici, ecc. - e n mansioni da far svolgere, e deve stabilire a quale unità assegnare le varie mansioni. Se le unità sono identiche, il problema non sussiste, ma diventa rilevante se le loro capacità di svolgere le diverse mansioni differiscono. Quando il contributo che ciascuna unità apporterebbe agli obiettivi dell'organizzazione se venisse assegnata a una determinata mansione è noto o stimato, le assegnazioni ottimali possono essere determinate considerando il problema come una variante del problema del trasporto.
Si osservi che questo risultato è sorprendente perché i problemi di assegnazione non sembrano essere affatto problemi di programmazione lineare. Sia infatti i, j l'attività di assegnare la i-esima unità della risorsa alla mansione j-esima. Allora xij, il livello di quella attività, può assumere valore 0 oppure valore 1. Ma ciò viola la definizione stessa della programmazione lineare, secondo cui essa si applica a variabili che possono assumere uno qualunque di un continuum di valori. La soluzione di questa apparente contraddizione è un teorema (che non ci soffermeremo a dimostrare) il quale asserisce che i livelli di tutte le variabili in una soluzione base ammissibile di un problema di programmazione lineare sono numeri interi se ogni riga e ogni colonna della matrice dei vincoli del problema è un numero intero. In un problema di assegnazione, poiché a ciascuna mansione deve essere assegnata una e una sola unità, i vincoli sono effettivamente Σi xij=1 per l'i-esima risorsa, e Σj xij=1 per la j-esima mansione, sicché l'ipotesi di tale teorema è soddisfatta. Un problema di assegnazione può essere risolto considerandolo come un problema di trasporto e ignorando la restrizione che la soluzione debba essere intera; la restrizione sarà soddisfatta automaticamente.
Problemi di rete. - Le correnti elettriche tendono a 'scegliere' determinati percorsi attraversando sistemi connessi di conduttori, resistenze, induttori, ecc., in modo da incontrare la minima resistenza. Poiché gli effetti di tutti questi impedimenti ai flussi di corrente sono semplicemente addizionali, la ripartizione di una data quantità di corrente tra percorsi alternativi può essere analizzata nei termini di un problema di minimizzazione. I flussi di corrente e di altri fluidi attraverso conduttori, canali di irrigazione e sistemi analoghi possono essere programmati e analizzati allo stesso modo, e ciò vale anche per lo smistamento del traffico di automobili e mezzi pesanti tra percorsi alternativi da un'origine a una destinazione date (su questo campo di applicazione v. in particolare Ford e Fulkerson, 1962).
Applicazioni in agricoltura. - Gli agricoltori desiderano allocare la terra a loro disposizione in modo da ottenere il massimo rendimento netto. Negli Stati Uniti e in molti altri paesi gli agricoltori e i responsabili della politica agraria ricorrono alla programmazione lineare per determinare l'allocazione ottimale dei campi tra le varie colture tenendo conto della dotazione complessiva di terra, delle caratteristiche dei campi, e della dotazione complessiva di manodopera, di macchinari, di credito e di altre risorse.
Problemi di programmazione dinamica. - Una delle più importanti applicazioni della programmazione è la pianificazione delle operazioni e degli investimenti di un'impresa o di altre organizzazioni su una sequenza di periodi, in genere anni. In questo caso ogni anno (o altro periodo) è considerato un problema di programmazione in cui le attività dell'organizzazione trasformano stocks iniziali di beni e obbligazioni in stocks terminali e, così facendo, generano il contributo dell'anno al valore netto attuale delle operazioni dell'impresa. Le relazioni tra gli stocks iniziali, i livelli di attività e gli stocks terminali di ciascun anno costituiscono la matrice dei vincoli per quell'anno. Le matrici dei vincoli per tutti gli anni del periodo di programmazione possono essere identiche, e in genere si assume che siano abbastanza simili. I vincoli di collegamento sono dati dalla condizione che gli stocks iniziali di ciascun anno non eccedano gli stocks terminali dell'anno precedente. Di conseguenza, il numero dei vincoli in un problema di programmazione dinamica cresce rapidamente al crescere del numero dei periodi. Espresso in forma numerica, date n risorse e una programmazione estesa a t periodi, il numero di vincoli che devono essere soddisfatti sarà n(2t-1). Poiché, come abbiamo osservato, la difficoltà e i costi della soluzione aumentano di un valore pari al cubo del numero dei vincoli, il problema assume rapidamente proporzioni incontrollabili quando si cerca di determinare una volta per tutte i livelli di attività ottimali. È più conveniente dunque dividere il problema in una serie di sottoproblemi: ossia risolvere t problemi con 2n vincoli ciascuno piuttosto che un solo problema con n(2t-1) vincoli.Tuttavia insorge una difficoltà. Se il problema totale è diviso in t subproblemi che sono risolti con una procedura iterativa, le iterazioni tendono a oscillare in modo instabile anziché convergere verso un'unica soluzione. Per rimediare a tale difficoltà, George Dantzig e Philip Wolfe idearono il metodo della decomposizione; si tratta di una procedura iterativa stabile, basata sul principio che ogni soluzione ammissibile di uno dei subproblemi può essere espressa come una somma ponderata di n soluzioni base ammissibili del medesimo subproblema. La soluzione del problema principale comporta allora due fasi, che in pratica coincidono. La prima consiste nell'identificare le soluzioni base ammissibili dei subproblemi senza preoccuparsi di combinarle in una soluzione ammissibile del problema principale. Nella seconda fase, le soluzioni base ammissibili dei subproblemi sono combinate in una soluzione del problema principale considerando tali soluzioni, anziché le singole attività, come gli elementi i cui livelli devono essere determinati per ottenere una soluzione ottimale ammissibile del problema principale (per un'illustrazione dettagliata della procedura v. Dantzig e Wolfe, 1960).
Naturalmente, le divisioni non si basano necessariamente su sequenze temporali, ma possono far riferimento a regioni geografiche, paesi (nel caso di multinazionali), o a qualche altro principio.I metodi basati sul principio della decomposizione non dovrebbero essere confusi con due altre procedure di ottimizzazione dinamica. Il primo è quello della cosiddetta programmazione dinamica, sviluppato da Richard Bellman nel 1957. Tale metodo si basa su una formula di ricorsività, a volte chiamata 'equazione di Bellman', in base alla quale i livelli di attività ottimali di ogni subperiodo devono massimizzare il valore attuale della somma di: a) il contributo del subperiodo alla funzione obiettivo principale; b) il massimo contributo a tale funzione obiettivo che può essere ottenuto usando gli stocks terminali che risultano dai livelli di attività di quel periodo. L'equazione di Bellman è assai affine all'intuizione che sta alla base del terzo approccio ai problemi dinamici, la cosiddetta teoria del controllo ottimale. Tale teoria, introdotta nel 1962 da un gruppo di matematici sovietici guidati da L. S. Pontryagin, è uno sviluppo della classica teoria di Eulero delle equazioni differenziali di ottimizzazione. Le equazioni differenziali di ottimizzazione cui essa arriva sono affini all'equazione di Bellman, ma non identiche. Entrambe queste teorie si fondano su concetti assai diversi da quelli usati dal metodo di decomposizione e sono applicate con grande efficacia a varie situazioni.
Teoria dei giochi. - I giochi tra due persone a somma costante hanno un'importanza di primo piano nella teoria dei giochi. In questo tipo di giochi, a volte chiamati 'giochi a forma matriciale', ogni attore ha a disposizione un numero finito di strategie e, per celare le proprie intenzioni, opera tra di esse una scelta casuale. Egli deve decidere poi la probabilità da assegnare all'uso di ciascuna strategia, e si assume che scelga tali probabilità in modo da massimizzare l'aspettativa matematica di guadagno, a prescindere da quello che farà l'avversario: opterà cioè per una 'strategia di maximin'. Poiché un'aspettativa matematica è una funzione lineare delle probabilità dei vari risultati, la scelta delle probabilità è un problema di programmazione lineare. Una conseguenza importante di questa formulazione è che il problema di scelta di ciascun giocatore è il duale di quello del suo avversario.
Programmazione a variabili intere. - Abbiamo illustrato all'inizio gli assunti che definiscono l'ambito della programmazione lineare. Uno di questi è che ogni attività possa essere esercitata a qualunque livello non negativo. Ciò può costituire una grave limitazione. Supponiamo ad esempio che un ente (un'agenzia governativa, una società, e via dicendo) abbia un budget di investimento fisso, diciamo un miliardo di lire, da dividere tra una serie di programmi fattibili, che costano dai 100 ai 600 milioni di lire l'uno e che promettono differenti tassi annuali di remunerazione. Per effettuare la scelta ottimale tra questi programmi il metodo della programmazione lineare appare inapplicabile, ma se ciascuna scelta è considerata un'attività che può essere esercitata a un livello 0 oppure a un livello 1, e se si può ignorare la condizione di un insieme di valori continuo per i livelli, identificare l'insieme più redditizio o in altro modo efficiente di progetti diventa un problema di programmazione lineare. La programmazione intera riporta questo tipo di problemi, e molti altri, nell'ambito della programmazione lineare.
L'idea di fondo, che si deve in larga misura a George Dantzig, è piuttosto semplice, ma la sua esecuzione è complicata e costosa. Consideriamo il seguente problema: per i=1, ..., n, scegliere le variabili xi=0 oppure=1 in modo da massimizzare Σi ri xi; tali variabili sono soggette al vincolo Σi ci xi≥B, dove ci, ri indicano rispettivamente il costo e il rendimento atteso del progetto i.In base all'idea di Dantzig tali problemi (che, a differenza dell'esempio sopra riportato, possono avere più di un vincolo) possono essere risolti risolvendo una sequenza di problemi di programmazione lineare normali. Il primo è il problema così come è stato formulato, trascurando la condizione per cui le xi debbano assumere valori interi, ossia imponendo solo 0≥xi≥1.
Se la soluzione richiede valori frazionali, allora viene formulato un nuovo problema con la stessa funzione obiettivo e gli stessi vincoli, cui viene aggiunto un nuovo vincolo lineare, detto 'taglio' (cutting plane), che la soluzione del vecchio problema violerebbe senza però escludere alcuna delle soluzioni ammissibili (intere) dal problema originario. La chiave del metodo sta dunque nella costruzione del 'taglio', che può essere effettuata in vari modi, troppo tecnici per essere illustrati in questa sede (per un'analisi dettagliata v. Dantzig, 1963, cap. 26).
Se la soluzione del problema espanso richiede valori frazionali per alcune delle xi, si può aggiungere un'altra variabile, operando un secondo 'taglio', e così via sino ad arrivare a una soluzione intera del problema. Ralph Gomory ha elaborato un algoritmo dei tagli che porterà sempre a una soluzione ammissibile con un numero finito, per quanto elevato, di iterazioni, se tale soluzione esiste. Tuttavia il metodo di Gomory è piuttosto lento. Alcuni metodi alternativi, per i quali non sono stati dimostrati teoremi altrettanto rassicuranti, si rivelano più efficaci nella pratica. Tutti i metodi conosciuti richiedono la soluzione di un numero spropositatamente elevato di problemi per risolvere un problema di programmazione lineare a variabili intere.
Conclusioni
La programmazione lineare è una famiglia di metodi di matematica applicata per risolvere alcuni problemi di ordine pratico trattandoli come problemi di massimizzazione o di minimizzazione di funzioni lineari di variabili soggette a vincoli lineari costituiti da disuguaglianze. Quest'ultima condizione distingue la programmazione lineare dai metodi classici di massimizzazione, che in genere sono applicazioni del calcolo, laddove la programmazione lineare si basa fondamentalmente sull'algebra e sulla geometria di spazi vettoriali di dimensione finita.La programmazione lineare si è rivelata utile in una straordinaria varietà di campi. Le sue principali applicazioni riguardano i progetti di valutazione e di investimento da parte di imprese, agenzie governative e organizzazioni di qualunque tipo. In tali contesti essa è usata per analizzare l'intera gamma di decisioni, dalle operazioni giorno per giorno agli investimenti a lungo termine. Ma la programmazione lineare ha numerose altre applicazioni che nel campo della scienza e dell'ingegneria, vanno dalla cristallografia all'analisi dei circuiti elettrici, alla progettazione di grandi strutture.I metodi matematici classici non sono adatti a trattare problemi in cui sono presenti disuguaglianze, in quanto questi comportano calcoli estremamente lunghi. Una svolta decisiva si ebbe con l'invenzione dei calcolatori elettronici e con l'ideazione del metodo del simplesso. A 45 anni di distanza dalla sua messa a punto, l'algoritmo del simplesso resta il più utilizzato per risolvere i problemi di programmazione lineare, eccettuati quelli di grandi dimensioni con migliaia di disuguaglianze.
Una delle caratteristiche più importanti e più affascinanti dei problemi di programmazione lineare è il fenomeno della dualità: a ogni problema di programmazione lineare se ne può associare un altro, il suo duale, che ha una interpretazione rilevante e di solito arricchisce il significato del problema cui è associato. Ad esempio, nella teoria dei giochi il duale del problema di determinare una strategia ottimale mista per un giocatore in un gioco tra due persone a somma costante, è il problema che si trova ad affrontare l'avversario. Forse ancora più importante, nelle applicazioni economiche e aziendali il duale del problema di allocare le risorse di un'impresa o di una nazione è il problema di determinare i valori relativi di quelle risorse per l'impresa o la nazione in questione. Si potrebbero citare innumerevoli altri esempi. Non sorprende, pertanto, che la programmazione lineare e i metodi di analisi affini si siano diffusi in tutto il mondo tra le imprese e le organizzazioni di ogni tipo. La ricerca sulla programmazione lineare, e in particolare lo studio di metodi più veloci e più economici per risolvere i problemi di programmazione lineare e problemi di programmazione affini, prosegue intensamente in molti paesi.
(V. anche Consumi; Produzione).
Bibliografia
Baumol, W.J., Economic theory and operations analysis, Englewood Cliffs, N.J., 1977⁴.
Bellman, R., Dynamic programming, Princeton, N.J., 1957.
Chvatal, V., Linear programming, New York 1983.
Dantzig, G., Linear programming & extensions, Princeton, N.J., 1963.
Dantzig, G., Wolfe, P., Decomposition principle for linear programs, in "Operations research", 1960, VIII, pp. 101-111.
Dorfman, R., Mathematical or 'linear' programming: a non-mathematical exposition, in "American economic review", 1953, XLIII, pp. 797-825.
Dorfman, R., An economic interpretation of optimal control theory, in "American economic review", 1969, LIX, pp. 817-831.
Dorfman, R., Samuelson, P.A., Solow, R., Linear programming and economic analysis, New York 1958.
Fang, Shu-Cherng, Puthenpura, S., Linear optimization and extensions: theory and algorithms, Englewood Cliffs, N.J., 1993.
Ford, L.R. jr., Fulkerson, D.R., Flows in network, Princeton, N.J., 1962.
Hadley, G., Linear programming, Reading, Mass., 1962.
Hadley, G., Nonlinear and dynamic programming, Reading, Mass., 1964.
Karmarkar, N.K., A new polynomial time algorithm for linear programming, in "Combinatorica", 1984, IV, pp. 373-395.
Luenberger, D.G., Introduction to linear and nonlinear programming, Reading, Mass., 1984².
Pontryagin, L.S. e altri, The mathematical theory of optimal processes, New York-London 1962.
Solow, D., Linear programming: an introduction to finite improvement algorithms, New York 1984.
Thompson, G.L., Thore, S., Computational economics, Danvers, Mass., 1992.
Winston, W.L., Introduction to mathematical programming: applications and algorithms, Belmont, Cal., 1995².