# Leonid Vital'evič Kantorovič

Leonid Vital'evič Kantorovič (IPA:) (in russo: Леони́д Вита́льевич Канторо́вич; San Pietroburgo, 19 gennaio 1912 – Mosca, 7 aprile 1986) è stato un matematico ed economista sovietico, vincitore del Premio Nobel per l'economia nel 1975, primo ed unico sovietico ad aver mai conseguito tale onorificenza.
Kantorovič è celebre per le sue teorie e per lo sviluppo di tecniche riguardanti l'allocazione ottimale delle risorse. Lavorò per il governo sovietico, col compito di ottimizzare la produzione di compensato in un'industria. Nel 1939 pose le basi per lo studio della programmazione lineare, che sarebbe stato, in seguito, approfondito e affinato da George Dantzig. Fu autore di molti libri, tra i quali Metodi matematici per organizzare e pianificare la produzione (1939), Calcolo economico e utilizzazione delle risorse (1959), Soluzioni ottimali in economia (1972).
Il premio Nobel del 1975, che divise con Tjalling Koopmans, gli fu conferito con la seguente motivazione: "per i contributi alla teoria dell'allocazione ottimale delle risorse".

## Biografia
### Origini e formazione

Leonid Vital'evič Kantorovič nacque a San Pietroburgo, al secolo capitale dell’Impero russo, il 19 gennaio del 1912 da una famiglia ebraica. Gli eventi della Rivoluzione russa di febbraio e ottobre del 1917, videro la famiglia Kantorovič trascorrere un anno in Bielorussia. Il padre di Leonid Vitalij (Haim), medico specialista in venereologia, morì nel 1922 lasciando Leonid alle cure della madre Paulina Zaks di professione dentista. All’epoca della morte del padre, Leonid aveva due fratelli, Nikolaj di undici anni più grande che era un rinomato psichiatra e Georgij, mentre Lidia all’epoca ingegnere edile e Nadežda erano le sue due sorelle maggiori. Nel 1926 Leonid all’età di quattordici anni si iscrisse alla facoltà di Matematica e Meccanica dell’Università di San Pietroburgo e nel 1930 all’età di diciotto anni conseguì la laurea in matematica. In università frequentò le lezioni e partecipò ai seminari di Vladimir I. Smirnov, Grigorii Fichtenholz, e Boris Delaunay. I suoi amici di università furono Isidor P. Natanson, Sergei L. Sobolev, Solomon Mikhlin, Dmitry e Vera Faddeev.

### Periodo a San Pietroburgo, 1912-1960

Le attività scientifiche di Leonid incominciarono al secondo anno di università quando i contenuti delle materie di studio coprivano campi della matematica più astratti. Nel 1930 la capitale della repubblica socialista sovietica ucraina di allora, Charkiv, ospitò il Primo Congresso di Matematica dell’Unione ed in quell’occasione Leonid Kantorovič portò i suoi contributi alla teoria descrittiva degli insiemi ed in particolare presentò i suoi risultati alla risoluzione di alcuni problemi di Nikolai N. Luzin. Kantorovič si impegnò in attività sia di ricerca che didattiche presso l’Istituto di Matematica e Meccanica di San Pietroburgo. Nel 1932 venne nominato assistente alla cattedra, nel 1934 divenne Professore Ordinario e nel 1935 conseguì l’ambito dottorato in scienze (DSc). A quel periodo risalgono i contributi di Leonid Kantorovič all’analisi numerica, si veda la pubblicazione dei lavori A New Method of Approximate Conformal Mapping e The New Variational Method. Le ricerche vennero completate nel 1936 in occasione della stesura del libro Approximate Methods of Higher Analysis che scrisse assieme a V.I. Krylov. Gli anni trenta costituivano un periodo di intenso sviluppo per l’analisi funzionale; gli sforzi di Leonid si concentrarono lungo una nuova direttrice di ricerca costituita dallo studio sistematico di spazi funzionali dotati di ordinamento parziale. La teoria degli spazi parzialmente ordinati si rivelò essere particolarmente fruttuosa e quasi contemporaneamente veniva sviluppata negli U.S.A, in Giappone ed in Olanda. Sull’argomento Leonid Kantorovič entrò in contatto con J. von Neumann, G. Birkho, A.W. Tucker, M. Frechet in occasione della Prima Conferenza Internazionale di Topologia tenutasi a Mosca il 4 e 5 settembre 1935.
Nel 1938 Leonid si unì in matrimonio con Natalia di professione fisico; dalla loro unione nasceranno un figlio ed una figlia che diverranno in seguito economisti. Durante la guerra Kantorovič lavorò come Professore alla Scuola Militare di Ingegneria e Tecnica Navale della città ed al termine del periodo bellico guidò il Dipartimento di Metodi di Approssimazione della facoltà di matematica dell’Accademia delle Scienze sovietica dove si occupò di problemi computazionali, programmazione informatica e realizzazione di elaboratori di calcolo. Nel 1948 il Consiglio dei ministri dell'URSS emise la Direttiva No. 1990-774ss/op top secret che ordinava di organizzare in due settimane un gruppo di calcolo costituito sino a 15 impiegati della facoltà di matematica presso il distaccamento di San Pietroburgo dell’Accademia delle Scienze sovietica. Il gruppo avrebbe fatto capo al Professore Kantorovič ed avrebbe lavorato al programma atomico sovietico: il nome in codice del progetto era “Enorme” dal russo “огромный”.
Nel 1949 gli venne conferito il Premio di Stato dell’Unione Sovietica nel campo delle scienze e della tecnologia per il lavoro Functional Analysis and Applied Mathematics. Nel 1959 apparve, con sedici anni di ritardo, il testo The Best Use of Economic Resources contenente un’estesa trattazione del suo approccio ottimizzatorio a diversi problemi economici. La pubblicazione fu seguita dalla ristampa di Mathematical methods of Organizing and Planning Production del 1939. Sul finire degli anni 1950 fu permesso a Kantorovič di istituire il primo seminario sui metodi matematici in economia. Il seminario dal titolo Calcolo Economico aveva frequenza annuale.

### Periodo a Novosibirsk, 1960-1971

Nell’aprile del 1960 il seminario annuale si spostò in Siberia nella sede secondaria dell’Accademia delle Scienze sita in Novosibirsk. Kantorovič poiché non era membro del partito comunista non aveva diritto alla carica di direttore del Centro, assunse pertanto l’incarico di vice direttore. Kantorovič convinse i suoi studenti e colleghi di San Pietroburgo a seguirlo riuscendo a creare un gruppo attivo e ricco di talenti tra cui Abel Aganbegyan. Il seminario si sviluppò in un centro di ricerca più grande dedito allo studio dei problemi di pianificazione ottimale. Il Centro avviò anche la pubblicazione di un proprio periodico. In occasione dell’inaugurazione del Centro, Kantorovič presentò alcuni dei suoi libri di recente pubblicazione e criticò alquanto duramente l’avversione dei professionisti dell’economia sovietica all’ottimizzazione e alle tecniche matematiche. Dall’altro lato non mancò di contrastare i tentativi della critica e dei detrattori che fraintendevano il meccanismo di formazione dei prezzi nella pianificazione ottimale con una forma sottilmente mascherata di economia di mercato, i.e. capitalista. Kantorovič ribadì che questi metodi matematici rimanevano comunque pienamente conformi e coerenti con l’ortodossia marxista e la relativa teoria del lavoro. Si può ritenere che Kantorovič abbia in un certo senso dimostrato che i prezzi ombra corrispondono al valore-lavoro marxista. Kantorovič concluse dicendo che gli economisti ed i matematici sovietici ritenevano che l’applicazione dei metodi matematici fossero un concreto strumento per mettere in atto i principi economici del marxsismo-leninismo, principi considerati essenziali per l’ampia e complessa realizzazione del socialismo. Nel 1964 Kantorovič venne eletto Accademico delle Scienze dell’Unione Sovietica, l’anno seguente fu onorato con il Premio Lenin per aver ideato il metodo della programmazione lineare ed elaborato diversi modelli economici. Il premio venne condiviso con V.S. Nemčinov e V.V. Novožhilov. Nel 1967 il Governo dell’Unione Sovietica gli conferì l’Ordine di Lenin.

### Periodo a Mosca, 1971-1986

Nel 1971 Kantorovič accettò l’incarico di guidare il dipartimento di ricerca all’Istituto Nazionale del Controllo Economico, un’istituzione elitaria per la formazione della futura classe dirigente. Nel 1975 gli fu conferito, in condivisione con Tjalling Koopmans, il premio per l'economia in memoria di Alfred Nobel. Kantorovič fu l’unico economista a ricevere due premi diametralmente ed ideologicamente opposti: il premio Stalin ed il premio Nobel.
Kantorovič morì di cancro il 7 aprile 1986 e fu sepolto al cimitero di Novodevič'e di Mosca.

## Matematica
### Le origini della Programmazione Lineare: il problema della cooperativa di compensati

Gli anni 30 furono importanti per Leonid anche grazie ad un evento fortuito che lo fece entrare in contatto con l’Economia. Nel 1938 in qualità di professore universitario svolse attività di consulenza presso il laboratorio della cooperativa di compensati Plywood Trust. Il problema che gli fu sottoposto e che passerà alla storia dell’economia matematica con il nome di the Plywood Trust Problem, costituiva un caso davvero speciale di ricerca dei punti di estremo di una funzione lineare definita su un politopo convesso. Economicamente Leonid si trovò davanti al problema di distribuire cinque tipi di legno grezzo ad otto macchine sfogliatrici in modo da massimizzare la produzione complessiva di compensati. Ogni tornio, per ciascuno dei cinque tipi di legno, era caratterizzato da una nota capacità esfoliatrice. Il vincolo cui era soggetta la cooperativa era costituito dal fatto che le quantità da produrre di ciascuno tipo di legno doveva essere in una proporzione fissata; nello specifico veniva richiesto di produrre tanti compensati del tipo 1 quanti quelli del tipo 2, del tipo 3, del tipo 4 e del tipo 5. Un tale vincolo esprimeva la tipica filosofia alla base della pianificazione economica sovietica. Leonid Kantorovič fu riconosciuto essere il primo a fornire una formulazione matematica precisa ad un problema di schedulazione della produzione. Tuttavia la ricerca della soluzione non poteva ricorrere al ben noto metodo di confrontare i valori che la funzione assumeva in corrispondenza dei vertici del poliedro poiché ciò avrebbe richiesto di risolvere milioni di equazioni. Kantorovič ideò un metodo innovativo che battezzò con il termine “dei moltiplicatori risolventi” e che traeva spunto dal teorema dei moltiplicatori di Lagrange.
Il metodo da lui escogitato era così articolato: per prima cosa esprimeva la funzione obiettivo come combinazione lineare dei gradienti delle equazioni che definivano i vincoli (ossia la varietà per dirla nei termini della geometria differenziale), assegnato poi arbitrariamente un valore iniziale ai moltiplicatori di Lagrange (alias moltiplicatori risolventi), questo veniva raffinato via via attraverso approssimazioni numeriche successive considerando la massima pendenza nella variazione dei moltiplicatori che generava un incremento nel quantitativo di compensati prodotti. La sua mente creativa non si fermò qui, si spinse oltre e fu capace di immaginare piani di produzione ottimali non solo applicabili ad uno stabilimento, ma validi anche per un’industria come per una nazione intera. Leonid Kantorovič fu capace di riconoscere la struttura matematica che si celava dietro ad un’ampia classe di problemi di ottimizzazione economica. La ricerca degli estremi vincolati veniva a costituire l’essenza dell’economica pianificata e l’elaborazione di un piano economico a livello nazionale era riconducibile ad un grandioso problema di programmazione lineare. Kantorovič riferendosi al terzo Piano quinquennale dell’Unione Sovietica (1938-1942) affermò: “Esistono due modi per incrementare l’efficienza produttiva di un reparto, di un’impresa o di un intero settore industriale. Un modo si basa sugli miglioramenti apportati nella tecnologia… l’altro si basa sul perfezionamento dell’organizzazione della pianificazione e della produzione”. La presentazione dei suoi risultati avvenuta il 13 maggio del 1939 all’Università di San Pietroburgo venne accolta con entusiasmo, la pubblicazione del libro, sebbene in numero limitato, avvenne a tempo di record (27 luglio 1939).
La diffusione delle sue idee tuttavia si fermò per almeno vent’anni. Le sue teorie vennero additate come non conformi alla teoria del valore-lavoro marxista ed i moltiplicatori risolventi venivano visti come lo spettro dei prezzi di un’economia di mercato piuttosto che una misura della scarsità delle risorse. Kantorovič fu accusato di eresia introducendo idee borghesi e concetti tipici della teoria della produttività marginale. Il marginalismo di Kantorovič, sebbene non esplicito nei suoi lavori, risiedeva nel ricorrere ai moltiplicatori di Lagrange per determinare il tasso di sostituzione di una risorsa scarsa. Il tasso di sostituzione della risorsa scarsa corrisponde al moltiplicatore e coincide con il suo costo opportunità (il cosiddetto "prezzo ombra"). Il suo metodo matematico in mano ai pianificatori infastidiva la burocrazia che gestiva gli affari economici dell’U.R.S.S. Le alte gerarchie, solite stabilire per così dire a comando l’allocazione delle risorse, avrebbero assistito ad una decentralizzazione della loro autorità dovuto al diretto coinvolgimento dei pianificatori in sede di redazione del piano. Lo scontro tra il matematico e la burocrazia sovietica fu inevitabile quando nel 1940 Kantorovič scrisse una lettera al Gosplan contenente le sue raccomandazioni su come poteva applicarsi la programmazione lineare alla pianificazione dell’economia sovietica. Per molti anni Kantorovič rimase completamente isolato nelle sue ricerche sulla pianificazione ottimale, mentre i suoi lavori confinati in U.R.S.S. da barriere ideologiche e linguistiche, dalla II Guerra Mondiale prima e dalla Guerra Fredda poi, vennero resi noti al “blocco occidentale” solo a metà degli anni 1950 a seguito del disgelo di Khruščëv.
Il lavoro Mathematical methods of Organizing and Planning Production del 1939 fu pubblicato in inglese solo nel 1960. La prima formulazione del metodo di risoluzione dei problemi di programmazione lineare era incompleta dal momento che mancava una definizione esplicita della natura dello spazio duale. Un algoritmo rigoroso e completo venne fornito da Kantorovič in un lavoro ultimato ai primi del 1940 con M.K. Gavurin, ma che fu pubblicato nel 1949 Primenenie matematicheskikh metodov v voprosakh analiza gruzopotokov che in italiano suonerebbe come Applicazione dei metodi matematici in materia di analisi del traffico merci.

### Marxismo, plusvalore e prezzi ombra

Secondo la teoria del valore-lavoro di Marx, il valore di una merce è dato dalla quantità di lavoro in esso incorporato, misurabile con la durata del tempo richiesto per realizzarlo. Un bene presenta pertanto tanto più valore quanto più è grande la quantità di lavoro umano in esso incorporato. Secondo Marx alla classe lavoratrice è impedito l’accesso ai mezzi di produzione e per non morire di fame, il proletariato diviene costretto a vendere il suo lavoro alle condizioni stabilite dalla controparte. La controparte capitalista si troverebbe nella condizione storica di poter sfruttare la classe subordinata producendo e vendendo prodotti ad un prezzo in cui è incorporato del lavoro che i capitalisti non avrebbero remunerato (il plusvalore). L’economia comunista si caratterizza per il divieto della proprietà privata dei mezzi di produzione, mezzi che sono invece di proprietà collettiva, statale o cooperativa. Inoltre l'allocazione delle risorse non è lasciata al mercato in cui la competizione tra le imprese individuali stabilirebbe i prezzi delle risorse, bensì si basa sulla pianificazione delle quantità da produrre. Il prezzo dei beni e/o servizi realizzati viene fissato dall’autorità statale centrale. L’autorità centrale agendo in regime di monopolio fa sì che i prezzi non siano più parametri liberi del sistema economico. Il problema di massimizzare i quantitativi prodotti o minimizzare l’utilizzo delle risorse fu affrontato da Kantorovič assegnando valori numerici a questi fattori siano essi rappresentati da capitale, da impianti che da ore uomo. Il valore numerico assegnato alle risorse scarse sono i moltiplicatori di Lagrange che rappresentano il rapporto tra la variazione della funzione obiettivo nel punto di ottimo e la variazione della risorsa scarsa espressa tramite un’equazione vincolare. Espandere il vincolo di un’unità risulterebbe economicamente percorribile se la funzione obiettivo aumenta più del costo aggiuntivo da sostenere. Lo sfruttamento economico della risorsa richiede dunque un prezzo unitario della risorsa minore del moltiplicatore di Lagrange. Il motivo per cui il moltiplicatore di Lagrange viene anche appellato come "prezzo ombra" della risorsa risiede proprio nel fatto che tale grandezza rappresenta il prezzo massimo che si è disposti a pagare per accaparrarsi un’unità aggiuntiva della risorsa. Il plusvalore concettualizzato da Marx si celerebbe nella differenza tra il costo unitario della risorsa tempo-uomo ed il suo prezzo ombra. Considerando il lavoro come un qualsiasi altro bene destinatario di un prezzo, un’autorità centrale che fissasse i prezzi sulla base del loro costo marginale, ossia che eguagliasse il prezzo di vendita al suo costo marginale fornirebbe una soluzione al problema della trasformazione dei valori nei prezzi di produzione, problema tutt’oggi controverso e noto come "dibattito sul calcolo socialista".

### Il Problema del Trasporto ottimale

Nel 1939 Kantorovič tra i vari problemi di programmazione lineare scorse ed isolò il problema del trasporto ottimale. Insieme al suo discepolo M.K. Gavurin intraprese la descrizione di uno speciale metodo matematico per risolvere il "Problema del Trasporto di Monge": il metodo del potenziale. La pubblicazione del loro lavoro, sebbene indirizzato al pubblico specialistico costituito da ingegneri dei trasporti e da pianificatori, venne rigettata da diverse riviste del settore, sicché si dovette attendere il 1942 per vederne la divulgazione. Il brevissimo articolo di appena quattro pagine On the Translocation of Masses era edito da Doklady, ma non passò inosservato. Il lavoro attirò l’attenzione di diversi economisti e matematici statunitensi che incominciarono a ricercare le pubblicazioni di L.V. Kantorovič: tra questi c’era Tjalling C. Koopmans il quale aveva lavorato in segreto al problema del trasporto durante il periodo bellico. Sul finire degli anni 1950 i principali lavori di Kantorovič divennero noti al blocco occidentale, in particolare fu proprio per iniziativa di T.C. Koopmans che Mathematical methods of Organizing and Planning Production venne pubblicato nel 1960 sulla rivista Management Science preceduto nel 1958 da On the Translocation of Masses.
Kantorovič in chiusura del breve articolo indica un paio di problemi pratici alla cui soluzione può applicarsi il teorema ivi dedotto. Il primo problema di tipo discreto riguarda la localizzazione di un certo numero finito di stazioni. Dati m stabilimenti di produzione $A_{1}$,…,$A_{m}$ collegati tramite una rete di trasporto ferroviaria ad n mercati $B_{1}$,…,$B_{n}$ destinati a consumare i beni prodotti dagli m stabilimenti; indicato con $a_{1}$,…,$a_{m}$ la quantità di beni disponibile presso ogni stabilimento e con $b_{1}$,…,$b_{n}$ la quantità di beni richiesta da ogni mercato; espresso le rispettive unità di misura in termini di vagoni al giorno prodotti e consumati; introdotto il costo $r(i,k):=r_{i,k}$ sostenuto per muovere una vagone dallo stabilimento i-esimo al mercato k-esimo; si vogliono servire i mercati in modo che vengano approvvigionati con i quantitativi richiesti al minor costo totale di trasporto ed in modo che la quantità complessiva di beni prodotti giornalmente eguagli il consumo giornaliero totale
vincolo di bilancio tra domanda ed offerta: $\sum _{k=1}^{n}b_{k}=\sum _{i=1}^{m}a_{i}$.
La formulazione di Kantorovič data al problema in “On the translocation of masses” non era limitata ai problemi discreti, bensì abbracciava sia i problemi continui che quelli caratterizzati dalla dimensione infinita dello spazio funzionale ove cercare la soluzione. Il secondo problema, livellamento di una data area di terra, rappresenta infatti un problema di tipo continuo in cui si vogliono spostare le masse di terra al minor costo possibile in modo che dal rilievo della superficie di terra di partenza, descritta da una funzione $h=f(x,y)$ , si giunga al profilo della superficie, descritto da una seconda funzione $h=g(x,y)$.
Kantorovič introduce uno spazio metrico compatto $(X,r)$ metrizzato con una metrica generica $r(x,y)$ adatta a rappresentare il costo per trasferire una massa di peso unitario dalla posizione di coordinate $x$ alla posizione di coordinate $y$. Indicato con $B(X)$ la σ-algebra di Borel di $X$, una funzione di insieme definita sugli insiemi di Borel, ossia sugli elementi di $B(X)$,
$f\colon B(X)\to [0,+\infty )$
secondo Kantorovič si presta a caratterizzare la distribuzione iniziale delle masse da muovere. Kantorovič richiede inoltre che $f$ sia additiva ossia che sia possibile suddividere le masse in gergo splitting: infatti se un boreliano $A$ di $X$ è dato da $A=A_{1}+A_{2}+...$ con $A_{i}\cap A_{k}=\varnothing$ per $i\neq k$ allora è possibile “distribuire” le masse nel modo seguente $f(A)=f(A_{1})+f(A_{2})+...$. Una seconda funzione di insieme
$g\colon B(X)\to [0,+\infty )$
con le medesime proprietà di $f$ si presta a caratterizzare la distribuzione finale delle masse.
Kantorovič esprime l'equazione di bilancio delle masse prima e dopo lo spostamento come $f(X)=g(X)$, fatto che equivale alla richiesta che $\int _{X}\ \mathrm {d} f(x)=\int _{X}\ \mathrm {d} g(x)$.
Kantorovič introduce come incognita del problema una famiglia di funzioni additive ${F}$ tali che $F\colon B(X)\times B(X)\to [0,+\infty )$ e per le quali valga $F(A_{1},X)=f(A_{1})$ e $F(X,A_{2})=g(A_{2})$. Il ruolo della mappa $F$ è quello di rappresentare il trasferimento delle masse, la famiglia di funzioni ${F}$ costituisce invece la totalità dei trasferimenti. Poiché si è interessati a minimizzare il costo di trasporto, Kantorovič definisce il lavoro speso associato ad un generico piano di trasporto $F$ come il funzionale seguente
    $W(F)=\int _{X}\int _{X}\ r(x,y)F(\mathrm {d} f,\mathrm {d} g)$
Il problema del trasporto secondo Kantorovič consiste nel ricercare $F^{*}$ tale che $W(F^{*})=min_{F}W(F)$. Dal punto di vista matematico il problema consiste nel cercare se l’insieme delle funzioni di trasporto sia vuoto o meno e nel caso ammetta soluzione ci si domanda se la soluzione sia unica o meno. Le funzioni $F^{*}$ che realizzano il minimo sono dette trasporti minimali; Kantorovič poi caratterizza un trasporto $F$ come potenziale se esiste una funzione $U(x)$ tale che:
    i) $|U(x)-U(y)|\leq r(x,y)$
    ii) $U(y)-U(x)=r(x,y)$ per $x\to y$
In ultimo dimostra il teorema secondo cui il trasporto F è minimale se e soltanto se è potenziale.
Riguardo all’esistenza o meno di soluzioni Kantorovič nell’articolo si esprime affermando che per decidere se un trasporto è minimale non si deve far altro che “costruire” un trasporto potenziale e se questo esercizio dovesse risultare impossibile allora si sarebbe certi che il trasporto in oggetto non può essere minimale. Il teorema fornisce inoltre un metodo “pratico” su come ridurre il costo del trasporto ed eventualmente consente al risolutore di dirigersi verso il trasporto minimale. Ancora oggi nel campo della programmazione matematica è prassi risolvere il problema duale soprattutto quando la sua risoluzione è più facile e rapida del problema primale. All’ottimo vale l’uguaglianza dei valori delle funzioni obiettivo nei due problemi primale e duale, sicché risulta possibile valutare la qualità di un punto ammissibile nel problema primale senza dover risolvere esattamente quest’ultimo. Per esaminare infatti la bontà di un punto ammissibile in esame $F'$ è sufficiente confrontare il valore $W(F')$ con $W(F^{*})$ quest'ultimo ricordiamo essere pari al valore all'ottimo della funzione obiettivo del duale. In un problema di costo minimo se dovesse risultare che $0<W(F')-W(F^{*})\leq \varepsilon$ allora ci si potrebbe accontentare di approssimare $F^{*}$ con $F'$ confidenti del fatto che il costo aggiuntivo da sostenere per aver scelto il trasporto sub-ottimale $F'$ è certamente non superiore ad $\varepsilon$.

#### Problema Primale del Trasporto: caso discreto

Funzione obiettivo in $m\cdot \ n$ incognite
    $min\sum _{i=1}^{m}\sum _{j=1}^{n}r_{i,j}\cdot \ F_{i,j}$
soggetta ai seguenti vincoli:
    $\left\{{\begin{array}{l}\sum _{j=1}^{n}F_{i,j}\leq a_{i}\forall \ i=1,...,m\\\sum _{i=1}^{m}F_{i,j}\geq b_{j}\forall \ j=1,...,n\\F_{i,j}\geq 0\forall \ i,j\\\end{array}}\right.$
Le variabili del problema sono indicate con $F_{i,j}$ ed ognuna rappresenta la quantità di beni da trasportare dal generico nodo di origine i al generico nodo di destinazione j. Il numero delle incognite sono pari a $m\cdot \ n$ osservato che $m\cdot \ n$ sono a priori tutti i possibili archi per congiungere i nodi di origine con i nodi di destinazione in esame.
Premesso che la quantità di beni da muovere da un nodo ad un altro non può che essere positiva $F_{i,j}>0$ e che risulta $F_{i,j}=0$ quando l'arco $i-j$ non viene attivato ossia non viene trasportata alcuna massa tra il nodo di origine $i$ ed il nodo di destinazione $j$, la sommatoria estesa a tutti gli $n$ nodi di destinazione $\sum _{j=1}^{n}F_{i,j}$ rappresenta la somma di tutti gli archi uscenti dal nodo origine $i$ e che, trasportando una massa $F_{i,j}$, hanno come destinazione gli $n$ nodi. Ognuna delle $i=1,...,m$ disequazioni $\sum _{j=1}^{n}F_{i,j}\leq a_{i}$ impone che la quantità di massa (beni) inviata dallo stabilimento i-esimo non ecceda la quantità ivi disponibile $a_{i}$.
La sommatoria $\sum _{i=1}^{m}F_{i,j}$ rappresenta la somma di tutti gli archi che hanno origine negli $m$ nodi, che movimentano massa $F_{i,j}$ e che sono entranti nel nodo $j$.
Ognuna delle $j=1,...,n$ disequazioni $\sum _{i=1}^{m}F_{i,j}\geq b_{j}$ impone che la quantità di beni entranti nel mercato j-esimo sia non inferiore alla domanda di beni dello specifico mercato $j$. Il coefficiente $r_{i,j}$ rappresenta il costo di trasporto per muovere un’unità di bene o un'unità di massa dal nodo origine $i$ al nodo destinazione $j$. In merito al bilancio delle masse, si osservi che la regione ammissibile per come è stata definita ammette implicitamente che si possa avere un eccesso di offerta rispetto alla domanda, per rendersene conto è sufficiente sommare tutti gli $m$ vincoli lato offerta per ottenere la diseguaglianza seguente
    $\sum _{i=1}^{m}a_{i,j}\geq \sum _{i=1}^{m}\sum _{j=1}^{n}F_{i,j}$
il cui confronto con la somma di tutti gli $n$ vincoli lato domanda
    $\sum _{j=1}^{n}b_{i,j}\leq \sum _{j=1}^{n}\sum _{i=1}^{m}F_{i,j}$
porta a concludere che
    $\sum _{j=1}^{n}b_{i,j}\leq \sum _{i=1}^{m}a_{i,j}$

#### Problema Duale del Trasporto: caso discreto

Nel seguito si introduce la formulazione duale del problema del trasporto ottimale facendo ricorso all’approccio lagrangiano che consiste nello scrivere la funzione lagrangiana ${\mathcal {L}}$ del problema primario di ottimizzazione e nel connetterla al teorema minimax di John von Neumann (1928). Tale teorema evidenzia che il valore all’ottimo della funzione lagrangiana del problema primario ($minmax{\mathcal {L}}$) coincide con il valore all’ottimo della funzione lagrangiana del problema duale ($maxmin{\mathcal {L}}$), ossia vale
    $minmax{\mathcal {L}}$ ≡ $maxmin{\mathcal {L}}$
Introdotti i moltiplicatori di Lagrange rappresentati da due vettori
    ${\mathbf {U} }=(U_{1},\ldots ,U_{m})$
    ${\mathbf {V} }=(V_{1},\ldots ,V_{n})$
la funzione Lagrangiana del problema del trasporto ottimale è la seguente
    ${\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })=\sum _{i=1}^{m}\sum _{j=1}^{n}r_{i,j}\cdot \ F_{i,j}+\sum _{i=1}^{m}U_{i}\cdot (\sum _{j=1}^{n}F_{i,j}-a_{i})-\sum _{j=1}^{n}V_{j}\cdot (\sum _{i=1}^{m}F_{i,j}-b_{j})$
dopo semplici passaggi algebrici si ottiene
    ${\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })=[\sum _{i=1}^{m}\sum _{j=1}^{n}F_{i,j}\cdot \ (r_{i,j}+U_{i}-V_{j})]-\sum _{i=1}^{m}U_{i}\cdot a_{i}+\sum _{j=1}^{n}V_{j}\cdot b_{j}$
Il problema duale associato alla Lagrangiana è per definizione
    $\max _{U,V}\min _{F\geq 0}{\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })$
Al fine di ottenere una descrizione esplicita del problema duale si minimizza $\min _{F\geq 0}{\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })$ rispetto ad $F$ tenendo fissi ${\mathbf {U} }$ e ${\mathbf {V} }$ e si ottiene così
    $\min _{F\geq 0}{\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })=-\sum _{i=1}^{m}U_{i}\cdot a_{i}+\sum _{j=1}^{n}V_{j}\cdot b_{j}+\min _{F\geq 0}[\sum _{i=1}^{m}\sum _{j=1}^{n}F_{i,j}\cdot \ (r_{i,j}+U_{i}-V_{j})]$
pertanto risulta
    $\min _{F\geq 0}{\mathcal {L}}({\mathbf {F} },{\mathbf {U} },{\mathbf {V} })=\left\{{\begin{matrix}-\sum _{i=1}^{m}U_{i}\cdot a_{i}+\sum _{j=1}^{n}V_{j}\cdot b_{j}&{\mbox{ se }}r_{i,j}+U_{i}-V_{j}\geq 0{\mbox{ per ogni }}\ i,j\\-\infty &{\mbox{ se }}r_{i,j}+U_{i}-V_{j}<0{\mbox{ per ogni}}\ i,j\\\end{matrix}}\right.$
in conclusione si ottiene il seguente problema di massimizzazione vincolato
    $\max _{U,V}\{\sum _{i=1}^{m}-U_{i}\cdot a_{i}+\sum _{j=1}^{n}V_{j}\cdot b_{j}{\mbox{ tale che }}r_{i,j}+U_{i}-V_{j}\geq 0{\mbox{ per ogni }}\ i,j\}$
Il problema duale del trasporto ottimale è il seguente problema di programmazione lineare avente funzione obiettivo in $n+m$ incognite
    $max\{\sum _{j=1}^{n}V_{j}\cdot b_{j}-\sum _{i=1}^{m}U_{i}\cdot a_{i}\}$
soggetta ai seguenti vincoli:
    $\left\{{\begin{array}{l}V_{j}-U_{i}\leq r_{i,j}{\mbox{ per ogni }}i,j\\\end{array}}\right.$
Le variabili $V_{j}$ e $U_{i}$ sono chiamate da Kantorovič potenziali dei vari punti. La differenza dei potenziali esprime quanto “valga” in più il posizionamento di un punto rispetto agli altri: il termine potenziale caratterizza i punti proprio in riferimento alla loro reciproca posizione. Osservando la funzione lagrangiana ${\mathcal {L}}$ si può intuire che ogniqualvolta si verifica uno spostamento ottimale da $i$ a $j$, ossia la tratta $i-j$ nel primale è minimale, $F_{i,j}\neq 0$, nel duale risulta necessariamente $V_{j}-U_{i}=r_{i,j}$.

## Aree tematiche

Kantorovič scrisse più di 300 lavori che come da lui stesso suggerito possono essere ricondotti a nove aree tematiche:
* teoria descrittiva delle funzioni e teoria degli insiemi
* teoria dell’approssimazione delle funzioni
* metodi di approssimazione
* analisi funzionale
* analisi funzionale e matematica applicata
* programmazione lineare
* hardware e software
* pianificazione ottimale e prezzi ottimali
* problemi economici di un’economia pianificata