• disequazioni variazionali
• flusso
• funzioni
• gap
• reti

Nella tesi considereremo una formulazione di tipo variazionale del problema
di flusso di costo minimo originariamente definito, in letteratura, come
problema di programmazione lineare su grafi. Il problema di flusso di costo
minimo consente di formulare una grande varietà di problemi lineari di flusso
su reti come il problema della ricerca dell'albero dei cammini minimi di radice
data o il problema del massimo flusso da un nodo sorgente ad un nodo
pozzo.
Le disequazioni variazionali sono state introdotte da Hartman - Stampacchia
nell'ambito del calcolo delle variazioni; la loro formulazione in dimensione
finita ha acquisito importanza quando é stato dimostrato che esse
consentono di formalizzare la condizione di equilibrio di Wardrop per un
problema di flusso su reti stradali.
La tesi é suddivisa in quattro capitoli più tre appendici.
Nel primo capitolo riprenderemo i concetti fondamentali della teoria dei
grafi, introducendo notazioni e definizioni utili nei capitoli successivi ed, in
particolare, analizzeremo le condizioni di ottimalità di Lagrange per problemi
di programmazione non lineare.
Nel secondo capitolo, dopo aver descritto le principali proprietà delle disequazioni
variazionali, introdurremo esplicitamente il problema del flusso di
costo minimo formulato mediante una disequazione variazionale in dimensione
finita, dove l'operatore rappresenta la funzione costo sugli archi del grafo
considerato. In particolare, mediante le condizioni di Lagrange descritte nel
primo capitolo, determineremo una generalizzazione al caso variazionale delle classiche condizioni di Bellman associate ai problemi di programmazione
lineare su grafi.
Nel terzo capitolo analizzeremo gli algoritmi risolutivi basati sulle funzioni
gap (o divergenza), mediante le quali é possibile riformulare una disequazione
variazionale tramite un opportuno problema di estremo vincolato avente la
funzione gap come funzione obbiettivo e la regione ammissibile coincidente
con quella della disequazione stessa.
Nel quarto capitolo considereremo modelli di reti di traffico, ispirati ai
principi di Wardrop, finalizzati alla previsione di flussi di equilibrio per problemi
di trasporto. Mostreremo che, sotto opportune ipotesi, calcolare un
punto di equilibrio equivale a risolvere una disequazione variazionale la cui
soluzione, a sua volta, può essere ottenuta risolvendo un problema di minimizzazione
di una funzione gap con vincoli lineari. Infine analizzeremo, su un
grafo orientato, una generalizzazione al caso variazionale del problema della
ricerca dell'albero dei cammini minimi di radice data.