una formulazione variazionale del problema di flusso di costo minimo

Università degli Studi di Pisa

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Matematica

Tesi di Laurea

Una formulazione variazionale del

Problema di usso di costo

minimo

Candidata

Francesca Monti

RELATORE

Prof. Giandomenico

Mastroeni

CONTRORELATORE

Prof. Paolo

Acquistapace

Anno Accademico 2016/2017

Ai miei genitori e a Nicola

Indice

Introduzione 1

1 Preliminari di Programmazione Lineare e non Lineare 5

1.1 Introduzione alla Programmazione Matematica . . . 5

1.2 Programmazione Lineare su gra . . . 7

1.2.1 Il problema del Flusso di Costo Minimo . . . 12

1.2.2 Flussi e potenziali di base . . . 19

1.3 Programmazione non lineare . . . 24

1.3.1 Condizioni generali di ottimalità . . . 27

2 Problema di usso di costo minimo nel caso variazionale 32 2.1 Disequazioni variazionali . . . 33

2.1.1 Teoremi di esistenza . . . 35

2.1.2 Teoremi di unicità . . . 39

2.2 Formulazione variazionale del Problema di usso di costo minimo 42 2.2.1 Esempio . . . 47

3 Funzioni Gap e algoritmi risolutivi 53 3.1 Funzioni gap . . . 54

3.2 Algoritmi risolutivi . . . 61

3.2.1 Metodi di ricerca esatta . . . 64

3.2.2 Metodi di ricerca inesatta . . . 65

4 Applicazioni 69 4.1 Il principio di Wardrop . . . 69 4.1.1 Modello variazionale di usso sugli archi e sui cammini 70 4.2 Applicazione a problemi di usso legati al traco . . . 75 4.3 Formulazione variazionale del problema dei cammini minimi . 79 4.3.1 Esempio . . . 81 A Denizioni e teoremi utilizzati 84 B Richiami sulla teoria della dualità lineare 90 C Esempio delle condizioni di Bellman nel caso classico 95

Bibliograa 102

Introduzione

Il problema di usso di costo minimo, originariamente denito, in letteratura, come problema di programmazione lineare su gra, è un problema fondamen-tale della Ricerca Operativa. In molti casi, la struttura di grafo che descrive questi problemi è dettata dal modo in cui essi vengono modellati; se pensia-mo, ad esempio, ad una rete stradale, essa può essere rappresentata come un grafo in cui i nodi sono gli incroci e gli archi le strade.

Il problema di usso di costo minimo consente di formulare una grande varietà di problemi lineari di usso su reti, come il problema della ricerca dell'albero dei cammini minimi di radice data o il problema del massimo usso da un nodo sorgente ad un nodo pozzo. Obiettivo è quello di minimizzare una funzione costo, ovvero determinare la via più economica per la spedizione di un certo prodotto attraverso una rete, con lo scopo di soddisfare le richieste di alcuni nodi tramite la disponibilità di altri nodi.

Nella tesi considereremo una formulazione di tipo variazionale del proble-ma di usso di costo minimo come estensione del probleproble-ma classico, ove il costo per unità di usso non è necessariamente costante. Cominceremo richia-mando il problema nel caso lineare, dove mostreremo la formulazione classica del problema per poi passare a quello non lineare, dove analizzeremo le con-dizioni di ottimalità di Lagrange ed inne dedicheremo particolare attenzione al modello variazionale descritto mediante disequazioni variazionali.

Se consideriamo il problema sotto l'aspetto decisionale possiamo conside-rare l'utente che deve fare delle scelte come un utente esterno al problema, quando le decisoni vengono eettuate a priori come nel caso classico di usso

Introduzione 2 di costo minimo, mentre come un utente interno al problema nel momento in cui le decisioni vengono prese durante il cammino come nel caso variazio-nale. Il modello variazionale si applica in molti ambiti, come, per esempio, in campo economico, in ingegneria strutturale o in problemi legati al traco [11, 4, 5, 3].

Per arontare il problema di usso di costo minimo da un punto di vista variazionale, studieremo le disequazioni variazionali introdotte da Hartman e Stampacchia nel 1966 nell'ambito del calcolo delle variazioni; la loro formula-zione in dimensione nita ha acquisito importanza quando è stato dimostrato che esse consentono di formalizzare la condizione di equilibrio di Wardrop per un problema di usso su reti stradali. I due principi di equilibrio di Wardrop sono noti uno come system optimum, corrispondente al modello di usso di costo minimo nel caso classico, l'altro come user equilibrium corrispondente al problema nel caso variazionale.

Risolvere una disequazione variazionale V I(K, F ), o semplicemente V I, consiste nel trovare x∗ _{∈ K tale che}

hF (x∗), x − x∗i ≥ 0, ∀ x ∈ K dove F : K → Rn.

Nel caso in cui F sia il gradiente di una funzione dierenziabile f e K sia chiuso e convesso, la V I corrisponde alla condizione necessaria di ottimalità del problema

(

min f (x) x ∈ K.

Se f è convessa allora la condizione diventa anche suciente. Le disequa-zioni variazionali possono essere espresse come problema di ottimizzazione tramite la minimizzazione di una funzione gap, cioè una funzione che risulta

Introduzione 3 essere maggiore o uguale a zero sull'insieme K ed è nulla solo in corrispon-denza di una soluzione della V I. La funzione gap si è mostrata utile nella denizione degli algoritmi perché permette di identicare le soluzioni della di-sequazione variazionale con l'insieme dei suoi minimi globali. Come algoritmi analizzeremo quelli dei metodi di discesa, nei quali utilizzeremo l'opposto del gradiente della funzione gap per ottenere una direzione di discesa ammissibile e assicurare la convergenza globale della successione generata dall'algoritmo. La tesi è suddivisa in quattro capitoli più tre appendici nella prima del-le quali richiameremo alcuni teoremi e denizioni di concetti base che non sono stati deniti nel corso dei capitoli, nella seconda faremo dei richiami sulla teoria della dualità, inne nella terza un esempio di applicazioni sulle condizioni di Bellman del caso classico.

Nel primo capitolo riprenderemo i concetti fondamentali della teoria dei gra, introducendo notazioni e denizioni utili nei capitoli successivi. Punto di partenza della tesi è il problema classico di usso di costo minimo con riferimento alle varianti: il problema di usso massimo e il problema dei cammini minimi. Nella seconda parte l'attenzione sarà rivolta all'analisi di problemi in cui non tutte le funzioni sono lineari: 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 dise-quazioni variazionali con relativi teoremi di esistenza e unicità, introdurremo esplicitamente il problema di usso di costo minimo formulato mediante una disequazione variazionale in dimensione nita, 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 gra.

Nel terzo capitolo analizzeremo gli algoritmi risolutivi basati sulle funzioni gap (o divergenza), mediante le quali è possibile riformulare una disequazione

Introduzione 4 variazionale tramite un opportuno problema di estremo vincolato avente la funzione gap come funzione obiettivo e la regione ammissibile coincidente con quella della disequazione stessa. Gli algoritmi risolutivi che descriveremo sono quelli basati su metodi di ricerca esatta o inesatta lungo una direzione di discesa.

Nel quarto capitolo considereremo modelli di reti di traco, ispirati ai principi di Wardrop, nalizzati alla previsione di ussi di equilibrio per pro-blemi di trasporto e derivanti dalle scelte che ogni singolo utente eettua per determinare il cammino dalla propria origine alla propria destinazione. Il riferimento è principalmente il modello basato sul concetto di equilibrio di Wardrop. 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 minimizzazio-ne di una funziominimizzazio-ne gap con vincoli liminimizzazio-neari. Inminimizzazio-ne analizzeremo, su un grafo orientato, una generalizzazione al caso variazionale del problema della ricerca dell'albero dei cammini minimi di radice data.

Capitolo 1

Preliminari di Programmazione

Lineare e non Lineare

1.1 Introduzione alla Programmazione

Mate-matica

La ricerca operativa, nota anche come Scienza della Gestione, fornisce stru-menti matematici di supporto alle attività decisionali in cui occorre gestire e coordinare attività e risorse limitate al ne di massimizzare o minimizzare una funzione obiettivo. In particolare si occupa di formalizzare un proble-ma in un modello proble-mateproble-matico e calcolarne, quando possibile, una soluzione ottima o approssimata.

Essa riveste un ruolo importante perché permette di operare le scelte migliori per raggiungere un determinato obiettivo rispettando vincoli che sono imposti dall'esterno e non sono sotto il controllo di chi deve compiere le decisioni.

Nell'ambito della ricerca operativa un ruolo di fondamentale importanza è svolto dalla programmazione matematica, disciplina che studia problemi in cui si vuole minimizzare o massimizzare una funzione ristretta ad una regione dello spazio e denita da vincoli esplicitati mediante intersezioni di curve di livello di funzioni a valori reali.

1.1 Introduzione alla Programmazione Matematica 6 Questi problemi consistono nel cercare, se esiste, un punto di minimo o di massimo di una funzione f : Rn_{→ R nella regione dove è denita e possono}

essere formulati nel seguente modo:

(

min f (x) x ∈ Ω

L'insieme Ω = {x ∈ Rn_{: g(x) ≤ 0, h(x) = 0}, con g : R}n

→ Rm _e

h : Rn_{→ R}p, è detto regione ammissibile, la funzione f è detta funzione

obiettivo e ciascuna equazione-disequazione che descrive Ω è detta vincolo. Questi problemi sono noti come problemi di programmazione mate-matica o problemi di ottimizzazione e in base alla struttura delle funzioni che li deniscono si possono classicare nel seguente modo:

ˆ Problemi di Programmazione Lineare (PL), in cui la funzione obiettivo f(x) e tutte le funzioni che deniscono i vincoli sono lineari o lineari ani, ovvero del tipo c1x1+ c2x2+ ... + cnxn+ cn+1;

ˆ Problemi di Programmazione Non Lineare (PNL), in cui almeno una delle funzioni che li deniscono non è lineare o lineare ane.

La seguente tabella mostra un esempio per ognuna delle due tipologie di problemi: Problema PL Problema PNL        min x1+ x2 x1 ≥ 0 x2 ≥ 0            min x2 1+ (x2+ 3)2 x1+ x2 ≥ 0 x1 ≥ 0 x2 ≥ 0

1.2 Programmazione Lineare su gra 7 Una classe particolare di problemi di PL si può modellizzare tramite il concetto di grafo e per questo prendono il nome di problemi di program-mazione lineare su gra.

1.2 Programmazione Lineare su gra

Spesso la matematica, per descrivere situazioni reali, ricorre alla teoria dei gra. I gra, infatti, sono degli oggetti matematici che possono essere utiliz-zati come strumento per modellare in maniera schematica un ampio nume-ro di pnume-roblemi decisionali ed hanno un'importanza fondamentale in svariati campi, anche diversi tra loro. Essi sono un mezzo per rappresentare, in modo astratto, l'esistenza o meno di una relazione binaria tra elementi di un insieme, come, ad esempio, due città, due calcolatori o due componenti elettronici.

Il primo ad utilizzare i gra come entità matematiche fu Eulero nel 1736 con il problema dei sette ponti di K¨onigsberg (gura 1.1), un problema legato alla città e quindi frutto di una situazione reale. La questione era capire se ci fosse o meno la possibilità di fare una passeggiata in città, partendo e arrivando nello stesso punto e attraversando tutti i sette ponti una e una sola volta.

1.2 Programmazione Lineare su gra 8 Tale problema venne risolto proprio da Eulero in uno dei suoi trattati, che venne per questo motivo considerato il primo trattato scientico sulla teoria dei gra.

In seguito, nei primi anni dell'ottocento, anche altri scienziati utiliz-zarono la teoria dei gra in vari campi scientici, sviluppando importanti applicazioni, come Kirchho nello studio delle reti elettriche.

Introduciamo tale teoria esponendo alcune denizioni e notazioni che verranno utilizzate nel corso dei capitoli della tesi.

Denizione 1.2.1. Un grafo è una coppia di insiemi di cardinalità nita G = (N , A), dove N si dice insieme dei nodi ed A, un sottoinsieme del prodotto cartesiano N × N con | A |= m, si dice insieme degli archi. Se ai nodi e agli archi vengono associati dei valori numerici, allora il grafo si dice pesato e tali valori vengono detti pesi; un grafo pesato si dice rete.

In una rete gli archi possono essere pensati come dei canali attraverso i quali uiscono dei beni, e possono essere rappresentati con grandezze discrete, come ad esempio il numero di auto su una strada, oppure continue, come ad esempio la quantità di acqua che scorre in una condotta. I pesi assumono dierenti rappresentazioni a seconda che siano associati ad un nodo o ad un arco.

Dati due nodi i, j l'arco che va da i a j si indica con a = (i, j), con i 6= j, oppure con ar in corrispondenza di un'opportuna scelta di numerazione

del-l'insieme degli archi. I gra si possono distinguere in due tipologie: gra non orientati per i quali gli archi non hanno un verso di percorrenza, uti-lizzati per rappresentare reti di calcolatori e gra orientati dove invece le coppie (i, j) sono ordinate. Questi ultimi possono rappresentare ad esempio reti stradali, utilizzati per la rappresentazione di sensi unici e di strade a doppio senso.

1.2 Programmazione Lineare su gra 9 Un esempio di grafo orientato è rappresentato dalla gura (1.2) con N = {1, 2, 3, 4} insieme dei nodi e con A = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)} insieme degli archi.

1

2

3

4

Figura 1.2: Esempio di grafo Introduciamo alcune notazioni che useremo in seguito:

ˆ Ad ogni nodo i ∈ N è possibile associare un valore reale qi detto

bilancio; in base al valore che esso assume si dice:

a) domanda del nodo se qi > 0. Esso rappresenta la quantità di

usso che esce dalla rete al nodo i, che in questo caso è detto destinazione o pozzo;

b) oerta del nodo se qi < 0. Esso rappresenta la quantità di usso

che entra nella rete al nodo i, che in questo caso è detto origine o sorgente;

c) nodo di trasferimento se qi = 0.

Se indichiamo con q := (q1, ..., qn)T il vettore dei bilanci associato, esso

deve soddisfare la relazione Pi∈N qi = 0, quindi la somma di tutte le

domande deve essere uguale alla somma delle oerte cambiata di segno; se indichiamo con

1.2 Programmazione Lineare su gra 10 D = {i ∈ N : qi > 0} O = {i ∈ N : qi < 0} si ha che: X i∈D qi = − X i∈O qi.

ˆ Per ogni arco ar = (i, j) indichiamo con:

a) fr il usso che attraversa l'arco e con f := (f1, ..., fm)T il vettore

dei ussi sugli archi;

b) cr il costo per unità di usso dell'arco e con c(f) := (c1(f ), ..., cm(f ))T

il vettore costo associato a tutti gli archi;

c) dr una capacità superiore che indica il massimo numero di

unità di usso che possono attraversare l'arco, e d := (d1, ..., dm)

il vettore associato;

d) lr una capacità inferiore che rappresenta il minimo numero di

unità di usso che possono attraversare l'arco, che generalmente nelle applicazioni viene assunta uguale a 0.

ˆ La matrice Γ = (γij) ∈ Rn× Rm detta matrice di incidenza i cui

elementi sono : γir =       

−1 se i è il nodo iniziale dell'arco ar

+1 se i è il nodo nale dell'arco ar

1.2 Programmazione Lineare su gra 11 Adesso possiamo dare le seguenti denizioni:

Denizione 1.2.2. Si denisce usso ammissibile su una rete G = (N , A), un vettore f ∈ Rm _{che verica i seguenti vincoli di conservazione del usso}

e di capacità sugli archi: X (j,i)∈A fji− X (i,j)∈A fij = qi ∀ i ∈ N e lij ≤ fij ≤ dij ∀ (i, j) ∈ A.

Denizione 1.2.3. L'insieme dei ussi ammissibili sulla rete è denito da:

Kf := {f ∈ Rm: Γf = q, 0 ≤ f ≤ d}

Deniamo inoltre costo complessivo del usso f la seguente somma: X

(i,j)∈A

cijfij

dove cij è il costo per unità di usso.

La gura (1.3) mostra un esempio di grafo a costo costante con domande, oerte e capacità: 1 2 3 4 5 -3 -5 0 0 8 3,4 1,3 1,1 1 , 4 4,7 5,1 6,8 1,1 1,3 fij dij qi

1.2 Programmazione Lineare su gra 12

1.2.1 Il problema del Flusso di Costo Minimo

Da qualsiasi parte guardiamo intorno a noi sono presenti delle reti sotto molteplici forme come ad esempio reti elettriche, di produzione o di distribu-zione, reti di monitoraggio o di trasporto. In molti ambiti, esiste la necessità di far passare una determinata quantità di un bene, sia essa energia elettrica, prodotto di consumo o messaggio, da un punto ad un altro della rete.

Il problema di usso è il modello matematico che meglio si presta a rappre-sentare questi problemi di rete; esso ha un notevole numero di applicazioni, come la distribuzione di un prodotto dalla fabbrica ai magazzini oppure dai magazzini stessi ai rivenditori. Grazie alla sua grande essibilità, è utilizzato anche per modellizzare problemi reali che non riguardano concretamente la spedizione di merci, come ad esempio il percorso di un'auto attraverso una rete autostradale. Nella sua formulazione si preferisce quindi utilizzare il termine più astratto usso piuttosto che trasporto.

L'interesse è rivolto a far avvenire il passaggio della quantità di un bene nel modo più eciente possibile quindi, tra tutti i problemi di usso su una rete, quello di maggiore importanza è il Problema di Flusso di Costo Minimo. Attraverso di esso è possibile determinare la via più economica per la spedizione di un certo prodotto attraverso una rete, con lo scopo di soddisfare le richieste di alcuni nodi tramite la disponibilità di altri nodi.

Il modello matematico può essere espresso sinteticamente con la seguente funzione obiettivo: min P (i,j)∈Acijfij Γf = q 0 ≤ f ≤ d (1.1)

Con particolari ed opportune ipotesi, che semplicano la descrizione dei problemi reali, è possibile formulare problemi equivalenti, la cui analisi risulta meno complessa.

1.2 Programmazione Lineare su gra 13 Le principali sono:

i) Singola sorgente - singolo pozzo

Se si hanno più sorgenti o più pozzi, è possibile introdurre una rete ampliata G0 _{= (N}0_{, A}0_{) dove N}0 _{= N ∪ {s, t} , e A}0 _{= A ∪ {(s, j) :}

j ∈ O} ∪ {(i, t) : i ∈ D}, s e t sono detti nodi ttizi e rappresentano rispettivamente la nuova sorgente e il nuovo pozzo. Tutti gli archi ttizi hanno costo 0 e ad ogni arco (s, j) viene associata una capacità dsj =

−qj che è uguale al usso in ingresso a j ∈ O nel problema originario,

mentre ad ogni arco (i, t) viene associata una capacità dit = qi, uguale

al usso in uscita da i ∈ D. L'oerta di s sarà data da q0

s = P j∈Oqj e la domanda di t da q0 t = P

i∈Dqi, mentre tutti i restanti nodi sono di

trasferimento.

s G(N,A) t

O D

Figura 1.4: Esempio di rete ampliata G0

ii) Capacità inferiori nulle

Se un arco (i, j) ha capacità inferiore lij 6= 0, questo implica che il

usso fij dovrà essere almeno pari a lij e quindi possiamo costruire un

1.2 Programmazione Lineare su gra 14 1. q0 j = qj − lij 2. d0 ij = dij − lij 3. q0 i = qi+ lij 4. f0 ij = fij − lij

5. Alla funzione obiettivo si aggiunge un termine costante cijlij

iii) Nessuna capacità associata ai nodi

In alcuni casi la massima quantità di usso che può attraversare un nodo ha una limitazione superiore. Questo problema può essere risolto costruendo un nuovo grafo, equivalente a quello dato, ma tale da avere capacità assegnate a tutti i nodi.

Sia i ∈ N il nodo in questione privo di capacità, allora lo sostituiamo con due nodi i0 _{ed i}00_{, mentre gli archi (j, i) li sostituiamo con archi}

(j, i0) e gli archi (i, j) con gli archi (i00, j) , con costi e capacità uguali agli archi originali. Inoltre aggiungiamo un arco (i0_{, i}00_{), con costo nullo}

e capacità superiore ed inferiore equivalenti alla massima quantità di usso che può attraversare il nodo i; inne la domanda del nodo i viene attribuita ad i0 _{se è positiva, ad i}00 _{se è negativa.}

iv) Eccesso di domanda o di oerta

In alcuni problemi può succedere che l'oerta qi con i ∈ O non

rappre-senti l'oerta al nodo i, ma la massima oerta che il nodo i può fornire alla rete. In questo caso la (1.1) non è vericata per i nodi i ∈ O, e per trasformare questo problema in un problema di usso di costo minimo ci riconduciamo a costruire una rete ampliata G0 _{avente un nuovo nodo}

sorgente s, da cui

N0 = N ∪ {s}, A0 = A ∪ {(s, i) : i ∈ O}.

1.2 Programmazione Lineare su gra 15 della nuova sorgente s coincide con la domanda globale dei nodi pozzo:

qs = −

X

j∈D

qj.

Inne poniamo qi = 0 per ogni i ∈ O in modo che risulti P_i∈N0qi = 0.

A questo punto, calcolati i ussi sulla nuova rete ampliata G0_{, questo}

tipo di trasformazione ci permette di conoscere per ciascuna sorgente la capacità produttiva eettivamente utilizzata, ovvero fsi, e quella non

utilizzata dsi− fsi.

Allo stesso modo si procede se abbiamo un eccesso di domanda, caso in cui per ciascun nodo pozzo è data una limitazione superiore qj del

valore che la domanda può assumere e ad ogni nodo sorgente è data l'oerta −qi.

Osserviamo che il problema del usso di costo minimo è una generalizzazione di due importanti problemi : il problema dei cammini minimi e il pro-blema di usso massimo. Entrambi i problemi possono essere formulati come casi particolari di quello di usso di costo minimo, in quanto presentano tra loro caratteristiche distinte, ma che ritroviamo nel problema di usso di costo minimo. Un'altra cosa da mettere in evidenza è il fatto che gli algoritmi per il problema di usso di costo minimo spesso fanno ricorso ad algoritmi utilizzati per i cammini minimi o per il usso massimo; facciamo un cenno a questi due problemi.

1.2 Programmazione Lineare su gra 16 - Problema dei cammini minimi

Il problema della determinazione dei cammini minimi, detti anche di costo minimo, è uno tra i più importanti problemi di ottimizzazione su reti. Consideriamo un grafo G = (N, A), un cammino orientato dal nodo n1 al

nodo nk, con k ≥ 2, è un sottografo di G denito da una coppia di successioni

di nodi n1, ..., nk e di archi a1, ..., ak−1 tali che ni ∈ N con i = 1, ..., k e

ai = (ni, ni+1) ∈ A per i = 1, ..., k − 1. Se ad ogni arco (i, j) è associato un

costo cij, allora il costo di un cammino P orientato è denito come la somma

dei costi degli archi da cui esso è formato. C(P ) = X

(i,j)∈P

cij

Se deniamo con Prt l'insieme dei cammini (orientati) che connettono r a

t, il problema dei cammini minimi consiste nel determinare, se esiste, un cammino orientato di costo minimo dal nodo radice r al nodo t con t 6= r, cioé min{C(P ) : P ∈ Prt} (1.2) o più in generale min P (i,j)∈P cijfij Γf = q f ≥ 0 (1.3) con qi = ( −(n − 1) se i = r 1 se i 6= r

1.2 Programmazione Lineare su gra 17 Quindi il problema (1.2) può essere formulato come un problema di us-so di costo minimo, ponendo le capacità superiori di ogni arco illimitate, il bilancio del nodo radice qr = −(n − 1) con n numero dei nodi e il bilancio

degli altri nodi uguali a 1. Questo equivale a supporre che dal nodo radice r debbano partire n − 1 unità di usso dirette ognuna verso un nodo pozzo i, il quale richiede al costo minimo un'unità di usso.

Se il grafo contiene un ciclo orientato di costo negativo non possiamo trovare cammini minimi; è possibile però vericare in tempo polinomiale se un grafo contiene un ciclo negativo e quindi lavorare sempre con gra privi di cicli di costo negativo in modo da ottenere una soluzione ottima.

- Problema di usso massimo

Il problema di usso massimo è in realtà, come detto in precedenza, un altro caso particolare del problema di usso di costo minimo.

In questo tipo di problema vogliamo determinare la quantità massima di usso v che partendo dal nodo sorgente s si può far giungere no al nodo destinazione t, tenendo conto dei vincoli di capacità sugli archi, cioé la quan-tità massima di usso che li può attraversare, e di quelli di equilibrio nei nodi intermedi, per i quali la quantità di usso entrante deve essere sempre pari a quella uscente.

Ad esempio, se la rete è una rete di comunicazione, il problema consiste nel far giungere attraverso di essa la massima quantità di dati possibile dal computer sorgente a quello destinazione, tenendo conto della quantità di informazione trasportabile nell'unità di tempo (vincoli di capacità) e dei cavi di collegamento (archi della rete).

1.2 Programmazione Lineare su gra 18 Sia:

ˆ F S(i) := (i, j) ∈ A, j ∈ N l'insieme degli archi uscenti dal nodo i, detta stella uscente di i;

ˆ BS(i) := (j, i) ∈ A, j ∈ N l'insieme degli archi entranti in i, detta stella entrante di i.

I vincoli di conservazione del usso si possono esprimere con:

X (j,i)∈BS(i) fji− X (i,j)∈F S(i) fij = qi dove qi =        −c se i = s 0 altrimenti c se i = t (1.4)

Osservando che max(c) = − min(−c), la (1.4) corrisponde al vincolo Γf = q allora una formulazione analitica del problema è data da:

       max c Γf = q 0 ≤ f ≤ d (1.5)

Come si può notare nel problema dei cammini minimi gli archi hanno associati costi ma non capacità, mentre nel problema di usso massimo gli archi hanno associate capacità ma non costi.

1.2 Programmazione Lineare su gra 19

1.2.2 Flussi e potenziali di base

Legati al problema di usso di costo minimo sono i concetti di grafo connesso, di base e di potenziali di base; essi saranno oggetto di questo paragrafo. Proposizione 1.2.1. Un grafo è connesso (cfr.Denizione A.0.1) se e solo se contiene almeno un albero di copertura (cfr.Denizione A.0.2) ; inoltre se ha n nodi ogni albero di copertura contiene n − 1 archi ed almeno due foglie.

Una delle proprietà della matrice di incidenza Γ è quella di avere

rk(Γ) ≤ n − 1, per cui il sistema Γf = q è sovradeterminato. Ogni colonna della matrice, infatti, contiene un 1 , un −1 e tutti zeri, per cui la somma delle righe della matrice Γ è il vettore nullo e le righe di Γ non sono tutte linearmente indipendenti.

Consideriamo il seguente problema:        min cT_f Γf = q 0 ≤ f ≤ d (1.6)

Osserviamo che la regione ammissibile, a causa dei vincoli di capacità, è un insieme chiuso e limitato, per cui se non è vuota il problema (1.6) ammette sempre ottimo nito.

1.2 Programmazione Lineare su gra 20 Se scriviamo il vincolo f ≤ d come f + w = d con w ≥ 0 si ottiene la formulazione seguente:            min cTf Γf = q f + w = d f ≥ 0, w ≥ 0 (1.7) Sia M = Γ 0 Im Im !

∈ R(n+m)×2m _{allora la seconda e terza equazione}

in forma matriciale si possono esprimere come:

M f w ! = q d !

Volendo determinare una base associata a (1.7) ed una sottomatrice MB

di ordine (n + m) × (n + m − 1) tale che rk(MB) = n + m − 1, consideriamo

una tripartizione (T, L, U) dell'insieme degli archi, in modo che T rappresenti un albero di copertura di G. Pertanto fT _{= (f}T

T, fLT, fUT) e sia (T

0_{, L}0_{, U}0₎

l'analoga partizione della variabile w, ossia wT _{= (w}T

T0, wT_L0, wT_U0).

Proposizione 1.2.2. Sia B = (T, U, T0_{, L}0_{) ove G(N, T ) è un albero di}

co-pertura di G, allora la matrice MB fornisce una soluzione associata a (1.7)

che viene determinata risolvendo il sistema

MB f w ! B = q d ! fL wU0 ! = 0 0 !

La soluzione così ottenuta è detta soluzione di base e la matrice associata MB matrice di base.

1.2 Programmazione Lineare su gra 21 Infatti, essendo M =       ΓT ΓL ΓU 0 0 0 IT 0 0 IT0 0 0 0 IL 0 0 IL0 0 0 0 IU 0 0 IU0      

si avrà che la sottomatrice

MB =       ΓT ΓU 0 0 IT 0 IT0 0 0 0 0 IL0 0 IU 0 0       ha rango rk(MB) = n + m − 1 da cui MB f w ! B =       ΓT ΓU 0 0 IT 0 IT0 0 0 0 0 IL0 0 IU 0 0             fT fU wT0 wL0       =       q dT dL dU      

che corrisponde al sistema:

           ΓTfT + ΓUfU = q fT + wT 0 = dT wL0 = dL fU = dU

1.2 Programmazione Lineare su gra 22 In particolare il seguente sistema fornisce la soluzione f:

       ΓTfT = q − ΓUdU fL= 0 fU = dU (1.8)

Teorema 1.2.1. Se i vettori d e q sono a componenti intere, allora le soluzioni di base di (1.7) sono a componenti intere.

Il teorema 1.2.1 è una proprietà fondamentale del usso di costo minimo e segue dal fatto che le matrici di base associate hanno determinante uguale a ±1.

Nel problema di usso di costo minimo una soluzione è ammissibile se 0 ≤ f ≤ d; questo è vero per f ∈ L e f ∈ U per cui solo la disequazione

0 ≤ fij ≤ dij ∀ (i, j) ∈ T

costituisce la condizione di ammissibilità per il usso di base associato a una tripartizione (T, L, U).

La soluzione di base si dice degenere se e solo se almeno una componente di base è zero. Una componente fij con (i, j) ∈ U o una componente wij con

(i, j) ∈ L0 non può essere nulla perché le capacità superiori non sono nulle, allora il usso è degenere quando esiste un arco (i, j) ∈ T tale che fij = 0, che

corrisponde ad un arco vuoto, oppure fij = dij che corrisponde ad un arco

saturo; infatti in caso wij = 0 con (i, j) ∈ T0 allora fij = dij con (i, j) ∈ T .

Il problema duale (cfr. Appendice B) associato al problema di usso di costo minimo è detto problema dei potenziali ai nodi, dove con potenziale si

1.2 Programmazione Lineare su gra 23 denisce un qualsiasi vettore λ∗

∈ Rn_{. Il problema duale associato a (1.7) è}

dato dal seguente:        max (λT_{q + µ}T_d) λT_{Γ + µ}T _{≤ c}T µT _{≤ 0} (1.9)

Le soluzioni duali complementari a f soddisfano il sistema (λT_{, µ}T_)M

B =

(cT_{, 0)}

B e tramite opportuni calcoli si arriva al seguente:

           λT_Γ T = cTT µT U = cTU − λTΓU µT T = 0 µT_L = 0

Da questo segue che (λT_{, µ}T_{) è ammissibile se vale}

( λT_Γ L+ µTL ≤ cTL µT U ≤ 0 ⇒        λT_Γ T = cTT λT_Γ L≤ cTL λT_Γ U ≥ cTU (1.10)

La (1.10) è condizione suciente di ottimalità del usso di base associa-to alla tripartizione (T, L, U). Inoltre, le soluzioni di tale problema possono essere pensate come potenziali associati ai nodi, caratterizzate dal fatto che nella funzione obiettivo si presentano sempre sotto forma di dierenza, per cui abbiamo il vantaggio di poterle variare tutte della stessa quantità con-servando l'ammissibilità e l'ottimalità. Per questo motivo si parla spesso di dierenze di potenziale, ne è un esempio il caso delle reti elettriche, dove la tensione è chiamata anche dierenza di potenziale.

1.3 Programmazione non lineare 24

1.3 Programmazione non lineare

I problemi di ottimizzazione sono detti di programmazione non lineare (PNL) quando la funzione obiettivo o almeno un vincolo non sono funzioni lineari o lineari ani. In questa sezione ci occuperemo di problemi di (PNL) della forma:        min f (x) g(x) ≤ 0 h(x) = 0 (1.11) dove le funzioni f : Rn → R, g : Rn → Rm_, h : Rn → Rp _{sono di}

classe C2 su una regione dello spazio Ω = {x ∈ Rn _{: g(x) ≤ 0, h(x) = 0}.}

Inoltre richiameremo i principali elementi teorici che ci serviranno per analizzare tali problemi, in particolare considereremo le condizioni necessarie e sucienti di ottimalità anché un punto sia di minimo per un problema del tipo (1.11).

Denizione 1.3.1. Una funzione f si dice coerciva su K se lim

kxk→+∞ x∈K

f (x) = +∞ (1.12)

Sia K un chiuso, x0 _{∈ K e f una funzione semicontinua inferiormente}

(cfr.Denizione A.0.7); allora l'insieme

L = {x ∈ Rn : f (x) ≤ f (x0)} è chiuso.

1.3 Programmazione non lineare 25 Consideriamo adesso il seguente insieme M = {x ∈ K : f(x) ≤ f(x0_)},

per la (1.12) L è limitato e quindi compatto. Ma allora anche M è compatto essendo K chiuso, infatti M = K ∩ L e i sottoinsiemi chiusi di insiemi compatti sono compatti. Da questo segue la seguente proposizione:

Proposizione 1.3.1. Sia f semicontinua inferiormente su K 6= ∅ chiuso e valga la (1.12); allora f ammette minimo globale (cfr.Denizione A.0.3) su K.

Le seguenti denizioni ci saranno utili per denire le condizioni di rego-larità dei vincoli.

Denizione 1.3.2. [8] Dato un insieme convesso X ⊆ Rn_{, una funzione}

f : X → R si dice convessa se per ogni x, y ∈ X e per ogni t ∈ [0, 1] si ha

f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (y).

Geometricamente, la Denizione (1.3.2) equivale a dire che, per ogni cop-pia di punti (x, f(x)), (y, f(y)) del suo graco il segmento che li unisce sta tutto sopra la parte di graco compresa tra i due punti stessi.

Denizione 1.3.3. [8] Dato un punto x ∈ Ω, un vettore d è detto tangente a Ω in x se esiste una successione di punti {zk} ⊂ Ω con zk → x ed una

successione di scalari positivi {tk} con tk → 0 tali che

lim

k→∞

zk− x

tk

= d.

L'insieme di tali vettori è chiamato cono tangente a Ω in x e viene indicato con TΩ(x).

1.3 Programmazione non lineare 26 Denizione 1.3.4. [8] Dato un punto x ∈ Ω, indichiamo con A(x) l'insieme dei vincoli di disuguaglianza che sono attivi in x, cioé A(x) = {i : gi(x) = 0}.

L'insieme D(x) = ( d ∈ Rn: d T_∇g i(x) ≤ 0 ∀ i ∈ A(x) dT_∇h j(x) = 0 ∀ j = 1, ..., p )

viene chiamato cono delle direzioni ammissibili del primo ordine nel punto x.

Denizione 1.3.5. [8] Dato il problema (1.11), i vincoli di tale problema si dicono regolari in un punto x ∈ Ω se TΩ(x) = D(x).

Ci sono delle condizioni sucienti che ci garantiscono la regolarità dei vincoli [8], alcune di esse sono rappresentate da:

(a) Se gi e hj sono funzioni lineari per ogni i = 1, ..., m e per ogni j = 1, ...p,

allora i vincoli sono regolari in ogni punto x ∈ Ω;

(b) Se le funzioni gi sono convesse per ogni i = 1, ..., m, le hj sono lineari

per ogni j = 1, ...p ed esiste x tale che g(x) < 0 e h(x) = 0, allora i vincoli sono regolari in ogni punto x ∈ Ω;

(c) Se x ∈ Ω ed i vettori (

∇gi(x) ∀ i ∈ A(x)

∇hj(x) ∀ j = 1, ..., p

sono linearmente indipendenti, allora i vincoli sono regolari nel punto x.

1.3 Programmazione non lineare 27

1.3.1 Condizioni generali di ottimalità

Nel caso non vincolato, nell'ipotesi che f sia dierenziabile due volte, le condizioni necessarie sono l'annullamento del gradiente di f e la matrice hessiana di f semidenita positiva; vediamo cosa cambia nel caso in cui sono presenti dei vincoli, ponendo in particolare l'attenzione sulle condizioni del primo ordine. Le condizioni di ottimalità si servono delle condizioni di regolarità sui vincoli descritte nel paragrafo precedente.

Il gradiente di una funzione f(x) in un punto è sempre ortogonale alla curva di livello passante per quel punto; per cui, se calcoliamo il gradiente di un vincolo hi(x) = 0 in un punto di minimo vincolato x, la direzione di ∇hi(x)

è ortogonale al vincolo e nel caso di una disequazione punta verso l'interno della regione ammissibile.

Quindi una condizione per il punto di minimo x di una funzione f può essere espressa dicendo che esistono costanti scalari, µj e λi , tale che ∇f(x) =

µ_j∇hi(x) e ∇f(x) = λi∇gi(x). In generale questa condizione può essere

espressa anche in altri termini introducendo la funzione Lagrangiana:

L(x, λ, µ) = f (x) + Σm

i=1λigi(x) + Σpj=1µjhj(x) (1.13)

∇xL(x, λ, µ) = 0 (1.14)

Con quest'ultima equazione troviamo i punti di minimo del problema vincolato tra i punti stazionari della funzione lagrangiana. I parametri λ, µ presenti nella funzione prendono il nome di moltiplicatori di Lagrange.

1.3 Programmazione non lineare 28 Si può dimostrare che, in ipotesi di regolarità dei vincoli, la (1.14) è una condizione necessaria, ma in generale non è suciente anché x sia un punto di minimo per la f nel problema vincolato.

Con queste premesse possiamo enunciare il seguente teorema:

Teorema 1.3.1. [8] Se x è un minimo locale (cfr.Denizione A.0.4) di f su Ωed i vincoli sono regolari in x, allora esistono due vettori λ ∈ Rm e µ ∈ Rp

tali che (x, λ, µ) soddisfa il sistema di Lagrange-Kuhn-Tucker (LKT):

                 ∇xL(x, λ, µ) = ∇f (x) + Σmi=1λi∇gi(x) + Σpj=1µj∇hj(x) = 0 λigi(x) = 0 ∀ i = 1, ..., m λ ≥ 0 g(x) ≤ 0 h(x) = 0 (1.15)

Denizione 1.3.6. x è chiamato punto stazionario se (x, λ, µ) è una soluzione del sistema LKT (1.15).

In generale il teorema 1.3.1 senza l'ipotesi di regolarità dei vincoli non è più valido.

1.3 Programmazione non lineare 29 Esempio

Sia dato il seguente problema: (

min x + 2y x2+ y2 ≤ 0

L'insieme Ω = {(x, y) ∈ R2 _{: x}2_{+ y}2 _{≤ 0} = {(0, 0)} e quindi la}

lagran-giana è data da L(x, y, λ) = x + 2y + λ(x2_{+ y}2_{). A questo punto applicando}

il teorema 1.3.1 otteniamo che :

                 ∇xL(x, y, λ) = 1 + 2λx = 0 ∇yL(x, y, λ) = 2 + 2λy = 0 λ(x2+ y2) = 0 λ ≥ 0 x2 _{+ y}2 _{≤ 0}

Tale sistema per il punto (x, y) = (0, 0) è impossibile in quanto i vincoli in tale punto non sono regolari.

Infatti il cono delle direzioni ammissibili nel nostro problema è dato dall'insieme D(x, y) = {d ∈ R2 _{: d}T_{∇g(x, y) ≤ 0}; quindi, poiché vale che:}

∇g(x, y) = 2x 2y ! ⇒ ∇g(x, y) = 0 0 ! Di conseguenza  d1 d2  0 0 ! ≤ 0 ⇒ 0 ≤ 0

1.3 Programmazione non lineare 30 per cui essendo vero per ogni d = (d1, d2) si ha che D(x, y) = R2 mentre

TΩ(x, y) = TΩ(0, 0) = {(0, 0)}. Questo signica che D(x, y) 6= TΩ(x, y) e per

la Denizione (1.3.5) di vincoli regolari in un punto, quelli del nostro proble-ma non sono regolari.

Le funzioni convesse dierenziabili si possono caratterizzare anche tramite le proprietà delle loro derivate e a tal proposito enunciamo i seguenti teoremi: Teorema 1.3.2. [8] Se X ⊆ Rn _{è un insieme convesso aperto e f : X → R}

una funzione di classe C1_{; allora f è convessa su X se e solo se}

f (y) ≥ f (x) + (y − x)T∇f (x) ∀x, y ∈ X.

Osserviamo che f(y) − f(x) ≥ h∇f(x), y − xi per ogni x, y ∈ X e se vale f (y) − f (x) ≥ h∇f (x), y − xi ≥ 0 per ogni y ∈ X allora x è minimo su X.

Infatti per il teorema 1.3.2 una funzione è convessa se e solo se il graco della funzione sta sopra al piano tangente ad esso in ogni suo punto.

Inoltre in relazione al secondo ordine enunciamo il seguente teorema: Teorema 1.3.3. Se X ⊆ Rn è un insieme convesso aperto e f : X → R una

funzione di classe C2_{; allora f è convessa ⇔ la matrice ∇}2_{f (x)è semidenita}

positiva per ogni x ∈ X.

Teorema 1.3.4. Supponiamo che f sia convessa, i vincoli gi siano convessi

per ogni i = 1, ..., m ed i vincoli hj siano lineari per ogni j = 1, ..., p. Se

(x, λ, µ)è una soluzione del sistema LKT (1.15), allora x è un minimo globale di f su Ω.

1.3 Programmazione non lineare 31 Dim:

Siano λ e µ due vettori ssati, la Lagrangiana L(x, λ, µ) è una funzione convessa rispetto ad x in quanto somma di funzioni convesse. Poiché (x, λ, µ) è una soluzione del sistema LKT (1.15), ovvero ∇xL(x, λ, µ) = 0, si ha che:

L(x, λ, µ) ≥ L(x, λ, µ) ∀ _{x ∈ R}n_.

Osserviamo che L(x, λ, µ) = f(x) e di conseguenza per ogni x ∈ Ω si avrà che:

f (x) ≤ L(x, λ, µ) = f (x) + Σm_i=1λigi(x) + Σ p

j=1µjhj(x) ≤ f (x).

A questo punto abbiamo concluso che f(x) ≥ f(x) ∀ x ∈ Rn quindi x è

un minimo globale di f su Ω.

Capitolo 2

Problema di usso di costo

minimo nel caso variazionale

Molti problemi di Economia, Ingegneria, Fisica, Biologia e Ricerca Operativa vengono studiati attraverso le Disequazioni Variazionali, introdotte da Hart-man e Stampacchia nel 1966 nell'ambito del calcolo delle variazioni. La loro formulazione in dimensione nita ha acquisito importanza quando è stato dimostrato che esse consentono di formalizzare la condizione di equilibrio di Wardrop per un problema di usso su reti stradali (Principi di equilibrio di Wardrop 4.1).

Dopo aver descritto le principali proprietà delle disequazioni variazionali, indicate con il termine V I (Variational Inequality), ed i relativi teoremi di esistenza e unicità delle soluzioni, introdurremo esplicitamente il problema del usso di costo minimo formulato mediante una disequazione variaziona-le in dimensione nita, dove l'operatore rappresenta la funzione costo sugli archi del grafo considerato. In particolare, mediante le condizioni di Lagran-ge descritte nel primo capitolo, determineremo una Lagran-generalizzazione al caso variazionale delle classiche condizioni di Bellman associate ai problemi di programmazione lineare su gra.

2.1 Disequazioni variazionali 33

2.1 Disequazioni variazionali

Denizione 2.1.1. Sia K ⊆ Rn _{un insieme non vuoto e sia F : K → R}n_una

funzione continua su K. Si denisce disequazione variazionale V I(K, F ) il problema di trovare un vettore x∗ _{∈ K tale che}

hF (x∗), x − x∗i ≥ 0, ∀ x ∈ K (VI) dove con h·, ·i indichiamo il prodotto scalare usuale in Rn.

Dal punto di vista geometrico, risolvere la disequazione variazionale (VI) consiste nel trovare un punto x∗ _{tale che F (x}∗_{) forma un angolo non ottuso}

con ogni vettore y − x∗ _{al variare di y in K.}

La connessione tra le disequazioni variazionali e la teoria dell'ottimiz-zazione può essere osservata considerando un problema di ottimizdell'ottimiz-zazione dierenziabile, con f e K opportuni, del tipo:

(

min f (x)

x ∈ K. (2.1)

Se K è convesso allora la (VI) corrisponde alla condizione necessaria di ottimalità del problema (2.1). Se f è convessa allora la condizione diventa anche suciente cioé

x∗ è soluzione di V I(K, ∇f) ⇔ x∗ risolve (2.1)

Nella denizione K è un sottoinsieme generico, ma nella maggior parte delle applicazioni K è chiuso e convesso quindi di solito si assume con queste proprietà. In particolare, nel caso in cui K sia convesso, risolvere la disequa-zione V I(K, F ) signica trovare x∗ _{tale che il piano hF (x}∗_{), x − x}∗_{i = 0 sia}

2.1 Disequazioni variazionali 34 di supporto per K.

I risultati relativi all'esistenza delle soluzioni di una disequazione varia-zionale sono soprattutto i corollari del teorema di Hartman - Stampacchia, il quale ci garantisce l'esistenza nel caso in cui l'operatore F sia continuo e K sia compatto. L'unicità della soluzione è legata alla stretta monotonia di F . Per arontare i teoremi di esistenza e unicità, abbiamo bisogno di intro-durre alcune condizioni e denizioni che ci garantiscono tali proprietà.

Denizione 2.1.2. Sia K ⊆ Rn un insieme non vuoto, chiuso e

conves-so, e sia G una matrice n × n simmetrica e denita positiva. Si denisce proiezione di un punto y ∈ Rn _{su un insieme K, rispetto alla norma G,}

indicata con PG,K(y), la soluzione del seguente problema:

(

min ky − xkG

x ∈ K

dove la norma di G di un vettore x ∈ Rn _{è data da kxk}

G= (xTGx) 1 2.

Dalla denizione di proiezione possiamo dedurre direttamente che Osservazione 2.1.1. [1] Per ogni x ∈ Rn _{e per ogni y ∈ K si ha che}

hx − PG,K(x), G(y − PG,K(x))i ≤ 0. (2.2)

Denizione 2.1.3. Sia K ⊆ Rn _{un chiuso e convesso e sia F : K −→ K}

una funzione. Un punto x ∈ K è detto punto sso per F se:

2.1 Disequazioni variazionali 35 Teorema 2.1.1 (Brower). [10] Sia K ⊆ Rn _{compatto e convesso e sia}

F : K −→ K continua. Allora F ammette un punto sso.

Teorema 2.1.2. [10] Sia K ⊆ Rn _{chiuso, convesso e non vuoto.}

Allora y = PG,K(x) se e solo se :

y ∈ K : hy, w − yi ≥ hx, w − yi oppure

hx − y, w − yi ≤ 0 per ogni x ∈ K.

2.1.1 Teoremi di esistenza

Il risultato di base per l'esistenza di una soluzione della disequazione varia-zionale V I(K, F ) si basa sull'ipotesi di compattezza di K e sulla continuità di F . Grazie a questo fondamentale risultato sono stati formulati alcuni co-rollari nei quali l'ipotesi di compattezza di K è stata sostituita con qualche condizione aggiuntiva sulla funzione F .

Iniziamo con enunciare e dimostrare il teorema fondamentale dell'esisten-za della soluzione per un problema del tipo V I(K, F ).

Teorema 2.1.3 (Hartman-Stampacchia). [2] Sia K ⊆ Rn _compatto,

conves-so e non vuoto e sia F : K −→ Rn _{una funzione continua. Allora esiste una}

2.1 Disequazioni variazionali 36 Dim:

Sia I(x) = x la funzione identità, l'applicazione PG,K(I − F ) : K → K è

continua e quindi per il teorema di Brower 2.1.1 ammette almeno un punto sso x∗ _{∈ K tale che x}∗ _{= P}

G,K(I − F )(x∗).Applicando a x∗ il teorema 2.1.2

si ha che:

x∗ = PG,K(x∗− F (x∗)) ⇔ hx − x∗, x∗− F (x∗) − x∗i ≤ 0

⇔ hx − x∗, −F (x∗)i ≤ 0 ⇔ hF (x∗), x − x∗i ≥ 0 ∀x ∈ K ovvero x∗ _{è soluzione di V I(K, F ).}

2 Senza l'ipotesi di compattezza di K il problema dell'esistenza della solu-zione si può dimostrare introducendo, con il seguente corollario, una restri-zione sull'insieme K.

Corollario 2.1.1. [6] Sia K ⊆ Rn _{chiuso, convesso e non vuoto e sia}

F : Rn _{−→ R}n _{una funzione continua. Se esiste un sottoinsieme limitato}

L ⊆ K tale che ∀x ∈ K\L ∃ y ∈ L tale che hF (x), y − xi ≥ 0 allora il problema V I(K, F ) ha una soluzione.

Anche nel caso in cui K non sia compatto si possono stabilire condizioni necessarie e sucienti per l'esistenza della soluzione della disequazione (VI). Sia K un chiuso e convesso, consideriamo l'insieme KR = K ∩ BR dove

indichiamo con

BR= {x ∈ Rn: kxk ≤ R}.

Allora per il teorema 2.1.3 esiste almeno una soluzione xRper la disequazione

variazionale V I(KR, F )

2.1 Disequazioni variazionali 37 Teorema 2.1.4. Sia K ⊂ Rn _{chiuso e convesso e sia F : K −→ R}n _una

funzione continua. Condizione necessaria e suciente anché V I(K, F ) abbia soluzione è che esista un R > 0 tale che esista una soluzione xR di

V I(KR, F ) che soddis

kxRk < R. (2.5)

Dim:

(⇒) Poiché KR ⊂ K, se esiste una soluzione x∗ per la V I(K, F ) allora,

scegliendo un R tale che kx∗_{k < R, avremo che essa è soluzione anche}

per la V I(KR, F ).

(⇐) Sia xRuna soluzione di V I(KR, F ). Poiché kxRk < R, per ogni y ∈ K il

punto w = xR+(y−xR)appartiene a KRper un  > 0 sucientemente

piccolo. Da questo segue che xR∈ KR ⊂ K e si ha che

0 ≤ hF (xR), w − xRi = hF (xR), y − xRi ∀y ∈ K

e questo vuol dire che xR è soluzione del problema V I(K, F ).

2

Dal teorema 2.1.4 possiamo dedurre condizioni sucienti per l'esistenza di una soluzione della disequazione variazionale. Come esempio mostriamo il seguente corollario

Corollario 2.1.2. Sia y ∈ K ed R > 0 tale che kyk < R e supponiamo che per ogni x ∈ K con kxk = R si abbia che

hF (x), y − xi < 0

2.1 Disequazioni variazionali 38 Dim:

Sia xR una soluzione di V I(KR, F ). Se kxRk = R allora si ha che

hF (xR), y − xRi < 0 e questo è un assurdo perché y ∈ KR e xR è soluzione

della disequazione (2.4).

2

Un altra condizione suciente che discende sempre dal teorema 2.1.4 è data dal seguente corollario

Corollario 2.1.3. Se F è una funzione continua e coerciva allora esiste una soluzione per la V I(K, F ).

Dim:

Poiché F è una funzione coerciva allora per la Denizione (1.3.1) esiste un y ∈ K tale che

lim

kxk→+∞x∈K

hF (x) − F (y), x − yi

kx − yk = +∞.

Allora scegliamo T > kF (y)k e R > kyk tale che, per kxk ≥ R con x ∈ K si abbia

hF (x) − F (y), x − yi ≥ T kx − yk. Da questo otteniamo che

hF (x), x − yi ≥ T kx − yk + hF (y), x − yi ≥ T kx − yk − kF (y)kkx − yk quindi per kxk ≥ R avremo che

2.1 Disequazioni variazionali 39 A questo punto se xR ∈ KR è una soluzione di V I(KR, F ) allora per ogni

x ∈ KR vale che

hF (xR), xR− xi = −hF (xR), x − xRi ≤ 0

di conseguenza vale anche per y ∈ KR, quindi per la (2.6) si ha che kxRk < R;

applicando il teorema 2.1.4 si ha la tesi.

2

2.1.2 Teoremi di unicità

In questa sezione studieremo l'insieme delle soluzioni di una disequazione variazionale e mostreremo quando esso è vuoto, compatto, convesso o formato da un unico elemento. Vedremo che la condizione di continuità della funzione F non è più suciente per l'esistenza di una soluzione, per cui dovremo sfruttare altre proprietà come la pseudo-monotonia (cfr.Denizione A.0.11) o la stretta monotonia (cfr.Denizione A.0.12).

In un problema di estremo convesso, l'insieme delle soluzioni è anch'esso convesso, e questo risultato può essere generalizzato, con l'ipotesi di pseudo-monotonia della funzione, alle disequazioni variazionali.

Proposizione 2.1.1. Sia K ⊂ Rn _{non vuoto, chiuso e convesso e sia}

F : K −→ Rn una funzione continua e pseudo-monotona. Allora x∗ _{∈ K è}

soluzione di V I(K, F ) se e solo se per ogni y ∈ K si ha che hF (y), y−x∗_{i ≥ 0.}

2.1 Disequazioni variazionali 40 Dim:

x∗ ∈ K è una soluzione di V I(K, F ) ⇔ per ogni y ∈ K si ha che

hF (x∗_{), y − x}∗_{i ≥ 0 ⇔ per ogni y ∈ K si ha hF (y), y − x}∗_{i ≥ 0 per la}

pseudo-monotonia di F .

2

Proposizione 2.1.2. Se F è strettamente monotona su K allora la disequa-zione V I(K, F ) ha un'unica soludisequa-zione.

Dim:

Supponiamo che y, w siano soluzioni distinte di V I(K, F ). Allora vale che per ogni x ∈ K

hF (y), x − yi ≥ 0 e hF (w), x − wi ≥ 0

Se sostituiamo, al posto della x, w nella prima, y nella seconda e ne facciamo la dierenza otteniamo che

hF (y) − F (w), w − yi ≥ 0 ⇒ hF (y) − F (w), y − wi ≤ 0

che contraddice l'ipotesi di stretta monotonia di F per cui necessariamen-te deve essere che y = w.

2

Teorema 2.1.5. Sia K ⊂ Rn _{non vuoto, chiuso e convesso e sia}

F : K −→ Rn una funzione continua. Se F è coerciva rispetto a K, allora V I(K, F ) ha un insieme non vuoto e compatto di soluzioni.

2.1 Disequazioni variazionali 41 L'ipotesi di coercività della funzione F può essere indebolita, come ve-dremo nei seguenti teoremi, in quanto è una condizione piuttosto forte e limitante.

Teorema 2.1.6. Sia K ⊂ Rn _{non vuoto, chiuso e convesso e sia}

F : K −→ Rn una funzione continua. Se esiste un vettore y ∈ K tale che l'insieme

S = {y ∈ K : hF (x), x − yi ≤ 0}

sia vuoto o limitato, allora V I(K, F ) ha soluzione. Inoltre se l'insieme è chiuso e limitato allora l'insieme delle soluzioni è compatto.

Teorema 2.1.7 (unicità). Sia K ⊂ Rn _{non vuoto, chiuso e convesso e sia}

F : K −→ Rn _{una funzione continua. Se F è fortemente monotona su K,}

allora esiste un'unica soluzione per V I(K, F ).

Dim:

Poiché la forte monotonia implica la coercività della funzione, per il teorema 2.1.5 la soluzione esiste. L'unicità segue dalla proposizione 2.1.2, in quanto la forte monotonia implica la stretta monotonia.

2

Osservazione 2.1.2. Il problema V I(K, F ) può non avere soluzioni quando la funzione F è monotona oppure pseudo-monotona, ma se esiste almeno un punto della regione ammissibile che verichi le ipotesi di regolarità dei vincoli, viste nella sezione (1.3) , allora la pseudo-monotonia è suciente per stabilire l'esistenza di una soluzione. Inoltre osserviamo che nel caso in cui K non sia limitato la forte monotonia ci garantisce sia l'esistenza che l'unicità della soluzione.

2.2 Formulazione variazionale del Problema di usso di costo minimo 42

2.2 Formulazione variazionale del Problema di

usso di costo minimo

In molte circostanze reali possono vericarsi delle situazioni, non prevedibili a priori, in cui siamo costretti a modicare del tutto o in parte i programmi stabiliti e le scelte eettuate in un primo momento.

Ad esempio, se dobbiamo fare un viaggio, prima della partenza scegliamo la strada da percorrere, ma durante il tragitto può capitare di dover cambiare percorso causa traco, lavori in corso etc...

Se si considera il sistema viario come una rete, il viaggiatore si trova ad essere un utente esterno alla rete nel momento in cui programma il percorso e quindi ad avere costi ssi, un utente interno alla rete durante il viaggio e a dover prendere nuove decisioni in relazione alla variazione delle condizioni del momento. Il problema arontato dall'utente interno può essere schematizzato in forma variazionale.

In questa sezione mostreremo la relazione tra le disequazioni variazionali (VI) e i problemi di usso di costo minimo, presentando il modello varia-zionale come estensione del problema classico, ove il costo c(f) per unità di usso non è necessariamente costante.

In particolare, vedremo come il problema (1.1) si generalizza nel caso variazionale con la ricerca di un vettore di ussi f∗ _{∈ K}

f tali che f∗ sia

soluzione della seguente disequazione variazionale:

hc(f∗), f − f∗i ≥ 0, ∀ f ∈ Kf (2.7)

2.2 Formulazione variazionale del Problema di usso di costo minimo 43 Equivalentemente, un punto di equilibrio f∗ _{è caratterizzato dal fatto di}

essere soluzione del problema di estremo:

min P

(i,j)∈Acij(f∗)fij

Γf = q 0 ≤ f ≤ d

(2.8)

Possiamo notare che se la nostra funzione obiettivo dei costi non dipende da f il problema si riconduce al caso standard visto nel capitolo precedente. Infatti se c(f∗_{) = c con c costante per ogni f}∗ _{allora si ha che :}

hc(f∗), f − f∗i = hc, f − f∗i ≥ 0 ⇔ hc, f i ≥ hc, f∗i ∀ f ∈ Kf

⇔ hc, f∗i = min

f ∈Kf

hc, f i ⇔ f∗ è un punto di minimo per il problema (1.1) .

Procediamo con il problema di usso di costo minimo nel caso variazio-nale, tenendo conto delle denizioni e dei teoremi introdotti nel precedente capitolo, utili per la risoluzione del nostro problema di estremo. Andiamo a determinare, quindi, il sistema (LKT) (1.3.1) per il problema (2.8), partendo dalla lagrangiana ad esso associata:

2.2 Formulazione variazionale del Problema di usso di costo minimo 44 Applicando le condizioni (LKT) (1.15) otteniamo:

       ∇fL(f∗; f, λ, µ, s) = 0 hµ, f − di = 0, hs, f i = 0 Γf = q, 0 ≤ f ≤ d, µ ≥ 0, s ≥ 0 (2.9) da cui:        c(f∗) + λΓ + µ − s = 0 hµ, f∗_{− di = 0, hs, f}∗_{i = 0} Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0, s ≥ 0 (2.10)

Eliminando i moltiplicatori s da (2.10) otteniamo il seguente sistema:        c(f∗) + λΓ + µ = s ≥ 0 hµ, f∗_{− di = 0, hc(f}∗_{) + λΓ + µ, f}∗_{i = 0} Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0, (2.11)

I vincoli sono lineari quindi le condizioni oltre ad essere necessarie sono anche sucienti; a tal proposito si ha la seguente proposizione:

Proposizione 2.2.1. f∗ _{è una soluzione della (2.7) se e solo se esiste}

2.2 Formulazione variazionale del Problema di usso di costo minimo 45 Dalla proposizione (2.2.1) segue direttamente il seguente principio di equilibrio:

Teorema 2.2.1. f∗ _{è una soluzione della (2.7) se e solo se esiste}

λ∗ _{∈ R}p e µ∗ _{∈ R}n₊ tali che per ogni (i, j) ∈ A :

0 < f_ij∗ < dij ⇒ cij(f∗) = λ∗i − λ ∗ j, µ ∗ ij = 0, (2.12) f_ij∗ = 0 ⇒ cij(f∗) ≥ λ∗i − λ ∗ j, µ ∗ ij = 0, (2.13) f_ij∗ = dij ⇒ cij(f∗) = λ∗i − λ ∗ j − µ ∗ ij. (2.14)

Dato cij(f∗)possiamo osservare che per le condizioni (2.12), (2.13), (2.14),

trovata una soluzione λ∗_{, ne esistono innite che dieriscono tra loro per una}

costante. Infatti, nel caso in cui f∗ _{sia unica, anche la soluzione c}

ij(f∗)è unica

perché, perturbando un moltiplicatore di Lagrange di un fattore k, la funzione obiettivo non cambia; esplicitamente abbiamo cij(f∗) = λ∗i + k − λ

∗

j − k =

λ∗_i−λ∗

j. Mentre, se è la funzione obiettivo ad essere moltiplicata per un fattore

k, tutti i moltiplicatori di Lagrange verranno moltiplicati per lo stesso fattore k e questo ci dice che il moltiplicatore di Lagrange dà informazioni sul modo in cui il vincolo inuenza la funzione obiettivo.

2.2 Formulazione variazionale del Problema di usso di costo minimo 46 Poniamo cλ∗ ij (f ∗_{) := c} ij(f∗) − λ∗i + λ ∗

j e deniamo queste quantità costi

ridotti; allora le condizioni del teorema 2.2.1 possono essere riscritte nel seguente modo: cλ_ij∗(f∗) := cij(f∗) − λ∗i + λ ∗ j = λ ∗ i − λ ∗ j − λ ∗ i + λ ∗ j = 0 per la (2.12) cλ_ij∗(f∗) := cij(f∗) − λ∗i + λ ∗ j ≥ λ ∗ i − λ ∗ j − λ ∗ i + λ ∗ j = 0 per la (2.13) cλ_ij∗(f∗) := cij(f∗)−λ∗i+λ ∗ j = λ ∗ i−λ ∗ j−µ ∗ ij−λ ∗ i+λ ∗ j = −µ ∗ ij ≤ 0 per la (2.14)

Le condizioni (2.12), (2.13) e (2.14) sono una generalizzazione delle condi-zioni di Bellman per il classico problema di usso di costo minimo e possono essere sintetizzate nel seguente sistema:

       cλ∗ ij(f ∗_{) = 0 se 0 < f}∗ ij < dij cλ∗ ij(f ∗_{) ≥ 0 se f}∗ ij = 0 cλ_ij∗(f∗) ≤ 0 se f_ij∗ = dij (2.15)

2.2 Formulazione variazionale del Problema di usso di costo minimo 47

2.2.1 Esempio

Consideriamo il grafo della gura (2.1):

-1 -5 2 4 0 Figura 2.1: Esempio

Consideriamo la funzione costo denita nel seguente modo :

c(f ) = 5 − f12 3 , 4 − f13, 4f23+ 2, 20 − 2f24 7 , 2f34+ 3, 5 − f35, 3f45+ 1 2 

Il nostro scopo è quello di trovare una f∗ _{tale che sia soluzione della (2.7)}

che, per quanto visto sopra, è soluzione anche del sistema (2.11) per cui risolvendo :        c(f∗) + λΓ + µ = s ≥ 0 hµ, f∗_{− di = 0, hc(f}∗_{) + λΓ + µ, f}∗_{i = 0} Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0,

2.2 Formulazione variazionale del Problema di usso di costo minimo 48 dove c(f) è la funzione costo associata al grafo e q il vettore dei bilanci, si ottiene come soluzione f∗ _{= (2, 3, 0, 3, 0, 3, 1). La funzione costo calcolata}

in f∗ _{vale :} c(f∗) = 5 − 2 3 , 4 − 3, 4 ∗ 0 + 2, 20 − 2 ∗ 3 7 , 2 ∗ 0 + 3, 5 − 3, 3 ∗ 1 + 1 2  = = (1, 1, 2, 2, 3, 2, 2) .

Nel caso in cui cij(f∗) = cij, ovvero sia costante, le equazioni del teorema

(2.2.1) si trasformano nel seguente sistema:

( cij − λ∗i + λ ∗ j ≥ 0 ∀ (i, j) ∈ L cij − λ∗i + λ∗j ≤ 0 ∀ (i, j) ∈ U (2.16)

Infatti se consideriamo la prima disequazione sopra scritta, essa si ottiene dalla condizione (2.13) : cij ≥ λ∗i − λ ∗ j ⇒ cij − λ∗i + λ ∗ j ≥ 0

2.2 Formulazione variazionale del Problema di usso di costo minimo 49 La seconda disequazione della (2.16) si ottiene facendo lo stesso calcolo nella (2.14): cij = λ∗i − λ ∗ j − µ ∗ ij ⇒ cij − λ∗i + λ ∗ j = −µ ∗ ij ≤ 0

Anche in questo caso possiamo denire i costi ridotti ponendo cλ∗

ij := cij − λ∗i + λ ∗

j, allora le condizioni (2.16) possono essere riscritte nel

seguente modo:        cλ_ij∗ ≥ 0 ∀ (i, j) ∈ L cλ_ij∗ = 0 ∀ (i, j) ∈ T cλ_ij∗ ≤ 0 ∀ (i, j) ∈ U (2.17)

Osserviamo che il usso di base f∗

ij è ammissibile se e solo se il usso sugli

archi appartenenti all'albero di copertura T rispetta i vincoli di capacitá, mentre il potenziale di base λ∗ _{è ammissibile se e solo se i costi ridotti degli}

2.2 Formulazione variazionale del Problema di usso di costo minimo 50 Nella seguente tabella sono riassunti tutti i casi possibili per i ussi e i potenziali di base nel caso lineare.

usso di base potenziale di base 0 ≤ f_ij∗ ≤ dij cλ ∗ ij ≥ 0 ∀ (i, j) ∈ L ammissibile ∀ (i, j) ∈ T cλ∗ ij ≤ 0 ∀ (i, j) ∈ U

∃ (i, j) ∈ T tale che f_ij∗ < 0 ∃ (i, j) ∈ L tale che cλ∗ ij < 0

non ammissibile oppure oppure

∃ (i, j) ∈ T tale che f_ij∗ > dij ∃ (i, j) ∈ U tale che cλ ∗ ij > 0

∃ (i, j) ∈ T tale che f_ij∗ = 0 ∃ (i, j) ∈ L tale che cλ∗ ij = 0

degenere oppure oppure

∃ (i, j) ∈ T tale che f_ij∗ = dij ∃ (i, j) ∈ U tale che cλ ∗ ij = 0 f_ij∗ 6= 0 e f∗ ij 6= dij cλ ∗ ij 6= 0 ∀ (i, j) ∈ L non degenere ∀ (i, j) ∈ T cλ∗ ij 6= 0 ∀ (i, j) ∈ U

Applicando il teorema sulle condizioni sucienti di ottimalità per soluzio-ni di base ai problemi usso - potenziali si ottengono le condiziosoluzio-ni di Bellman nel caso capacitato.

2.2 Formulazione variazionale del Problema di usso di costo minimo 51 Le condizioni per il potenziale di base λ∗ _{sono denite dalla soluzione del}

sistema λT_Γ

T = cTT ed i seguenti teoremi mostrano le relazioni tra usso e

potenziale.

Teorema 2.2.2. Data una tripartizione (T, L, U) degli archi che genera un usso di base f∗ _{ammissibile, se il potenziale di base λ}∗ _{soddisfa le condizioni}

di Bellman (2.17) allora il usso f∗ _{è ottimo.}

Il teorema 2.2.2 è una condizione suciente di ottimalità per il problema Primale, mentre il seguente corollario esprime la corrispondente condizione per il problema Duale.

Corollario 2.2.1. Data una tripartizione (T, L, U) che genera un potenziale di base ammissibile, se il usso di base è ammissibile, allora il potenziale è ottimo.

Se il usso di base f∗ _{è non degenere allora le condizioni di Bellman sono}

anche necessarie per l'ottimalità, infatti abbiamo che:

Teorema 2.2.3. Sia (T, L, U) una tripartizione degli archi che genera un usso di base f∗ _{ammissibile e non degenere, sia λ}∗ _{il potenziale di base}

allora si ha che: f∗ é ottimo ⇔ ( cλ∗ ij ≥ 0 ∀ (i, j) ∈ L cλ∗ ij ≤ 0 ∀ (i, j) ∈ U

2.2 Formulazione variazionale del Problema di usso di costo minimo 52 Dim:

(⇒) Per ipotesi il usso f∗ è ammissibile e non degenere per cui vale che 0 < f_ij∗ < dij per ogni arco in T , quindi la tripartizione è unica e di

conseguenza gli archi in L e in U devono necessariamente rispettare le condizioni del sistema.

(⇐) Segue dal teorema 2.2.2.

2

Riprendendo il sistema (2.11) possiamo vedere che, anche nel caso va-riazionale, vale la stessa cosa del caso lineare. Infatti se cλ∗

ij (f∗) = 0 con

0 < f_ij∗ < dij per ogni arco (i, j) ∈ T allora le condizioni

ˆ cλ∗ ij (f

∗_{) ≥ 0 con f}∗

ij = 0 per ogni arco (i, j) ∈ L

ˆ cλ∗

ij (f∗) ≤ 0 con fij∗ = dij per ogni arco (i, j) ∈ U

sono univocamente determinate, per cui esse diventano anche necessarie come dimostrato nel teorema precedente.

Capitolo 3

Funzioni Gap e algoritmi

risolutivi

In questo capitolo introdurremo le funzioni gap ( o di divergenza), le quali furono inizialmente introdotte per le disequazioni variazionali e successiva-mente utilizzate anche per problemi di programmazione convessa [15]. Una funzione gap è una funzione che risulta essere maggiore o uguale a zero sull'in-sieme su cui è denita ed è nulla solo in corrispondenza di una soluzione della (VI); per cui è possibile esprimere la (VI) come problema di ottimizzazione tramite la minimizzazione di una funzione gap.

Inoltre essa si è mostrata utile nella denizione degli algoritmi perché permette di identicare le soluzioni della disequazione variazionale con l'in-sieme dei suoi minimi globali. Come algoritmi analizzeremo quelli dei metodi di discesa, nei quali utilizzeremo l'opposto del gradiente della funzione gap per ottenere una direzione di discesa ammissibile e assicurare la convergenza globale della successione generata dall'algoritmo.

3.1 Funzioni gap 54

3.1 Funzioni gap

Denizione 3.1.1. Sia K ⊆ Rn chiuso, una funzione g : Rn _{→ R si dice}

funzione gap per la (VI) se valgono le seguenti condizioni :

ˆ g(x) ≥ 0 per ogni x ∈ K,

ˆ g(x) = 0 se e solo se x è una soluzione di (VI).

Osserviamo che la seguente funzione, introdotta da Auslender [13], è una funzione gap per la disequazione variazionale V I(K, F ):

g(y) = sup

x∈K

hF (y), y − xi (3.1)

Inoltre osserviamo che la (VI) è equivalente al seguente problema di ottimizzazione:

min

y∈Ksup_x∈KhF (y), y − xi (3.2)

In generale la funzione (3.1) non è dierenziabile, ma con un'oppotuna regolazizzazione possiamo ottenere una funzione gap dierenziabile e

3.1 Funzioni gap 55 Sia G una matrice n × n simmetrica e denita positiva e x ∈ Rn_{, in [7]}

Fukushima considera la seguente funzione regolarizzata:

gF = minhF (x), y − xi + 1

2hy − x, G(y − x)i con y ∈ K (3.3) dove minimizza una funzione convessa su un insieme chiuso e convesso per cui il minimo esiste sempre in quanto la funzione è a valori niti su tutto K.

Lemma 3.1.1. Il problema (3.3) è equivalente per ogni x ∈ Rn al problema:

min ky − (x − G−1F (x))k2_G con y ∈ K (3.4)

Dim:

La condizione necessaria e suciente di ottimalità per il problema min

y∈Kf (y)

è h∇f(y0_{), z−y}0_{i ≥ 0}per ogni z ∈ K. Applicando tale condizione ai problemi

(3.3) e (3.4) otteniamo: ˆ per (3.3)

3.1 Funzioni gap 56 ˆ per (3.4)

h2G(y0_{− x + G}−1

F (x)), z − y0i = 2hG(y0_{− x) + F (x), z − y}0_{i ≥ 0}

e dividendo per 2 si ha:

hG(y0 − x) + F (x), z − y0i ≥ 0 z ∈ K (3.6) da cui (3.5) è equivalente alla (3.6).

2

Osservazione 3.1.1. Data fx(y) = hy − x, G(x − y)i = ky − xk2G allora

∇fx(y) = G(y − x) + G(y − x) = 2G(y − x).

Per il lemma 3.1.1, per ogni x la soluzione ottima di (3.3) è la proiezione del punto (x − G−1_{F (x)) rispetto alla norma su G, sull'insieme K.}

Proposizione 3.1.1. [7] Per ogni x ∈ Rn_{, sia H : R}n _{→ R}n _{la funzione il}

cui valore H(x) sia l'unica soluzione ottima del problema (3.3). Allora x è soluzione della disequazione variazionale V I(K, F ) se e solo se H(x) = x, ovvero x è un punto sso di H.

Dim:

Applicando il lemma 3.1.1 con y = H(x) si ottiene la tesi.