ETD system

Electronic theses and dissertations repository

 

Tesi etd-09062017-111823


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