Modello del percorso ottimo - Ricerca operativa

OSSERVAZIONE SUL PERCORSO OTTIMO

Il Percorso O mo è composto necessariamente da So opercorsi O mi.

∗

DIMOSTRAZIONE ∗ ∗

∗ ) ) )

( = ( + (

∗ ∗

)

( ( )

Se esistesse un altro percorso , siccome si è assunto che è o mo, il costo del nuovo

∗

cammino deve essere necessariamente maggiore o uguale a ∗

) )

( (

∗

) ) )

( = ( + (

∗ ∗

)

( ( )

)

(

Quindi: ∗ ∗ ∗

∗

) ) ) ) ) )

( = ( + ( ≥ ( = ( + (

E cioè: ∗

) )

( ≥ (

METODO RISOLUTIVO PRIMALE

Il Metodo Risolu vo si basa sulle condizioni di o malità di Belmann.

Si schema zza il metodo risolu vo: ∀ (, ) ∈

> + = + ℎè ≤ + ∀(, ) ∈

L’algoritmo scorre gli archi per un numero finito di volte e si verifica se i vincoli del duale

sono non soddisfa .

Se non sono soddisfa si impone la loro soddisfazione per uguaglianza.

Ciò si deve verificare fino a quando non si trova nessun arco per cui la condizione di

o malità non è verificata (cioè scorrendo tu gli archi , quando si ha che i vincoli del duale

sono soddisfa ci si ferma).

Seguono i passi de aglia del metodo:

ELEMENTI ≔

≔

≔ ℎ

= min {(, )}

( , )∈

PASSO 0: INIZIALIZZAZIONE = {}

=0

Dato che al momento non si ha nessun percorso che arriva al nodo :

= +∞ ∀ ∈ \{}

[] = ∀ ∈

PASSO 1: ESPANSIONE → = \{}

PASSO 2 (, ()

∀ ) ∈ ≠ → > +

Allora vuol dire che esiste un altro cammino che arriva al nodo poi faccio un altro

:

passe no e percorro l’arco per arrivare al nodo generando un nuovo cammino

(, )

formato dal so ocammino che va da ad più l’arco se questo nuovo cammino ha

(,

);

un costo minore rispe o al cammino determinato nelle altre iterazioni, allora questo

nuovo cammino è migliora vo e quindi si ha il nuovo costo per arrivare a

.

Quindi si impone: = + [] = = ∪ {}

Se e se (

< 0 < ∙ − 1)

In tal caso si è individuato un ciclo nega vo e quindi il problema sarà inferiormente

illimitato.

Nota che rappresenta il costo più basso che si può o enere per un

(

∙ − 1)

cammino senza cicli.

PASSO 3 Se = ∅

Altrimen 1

NB: () {(,

= ) ∈ } → ℎ

Il numero di iterazioni dell’algoritmo corrisponde al numero di volte che si compie il Passo 1

Per come è stato presentato l’algoritmo, al Passo 1 si ha una certa libertà, in quanto viene

solamente precisato di estrarre un nodo da .

In base alla strategia di estrazione del nodo si possono avere diverse versioni dell’algoritmo.

Possiamo dis nguere tra due versioni:

1. A Correzione di E che a

Tra i metodi a correzione di e che a è possibile annoverare la strategia che fa

un’esplorazione in ampiezza del grafo (si estrae il nodo in tesa ad supposto che

quando inseriamo in in coda ad come una pila).

,

L’altra strategia di estrazione è la strategia che fa un’esplorazione del grafo in

profondità, cioè si inseriscono i nodi nella pila dal basso verso l’alto ma si estrae in

testa alla lista.

2. A Valutazione di E che a (Algoritmo di Dijkstra)

Al passo 1 si estrae il nodo a cui è associata l’e che a minima.

Questo metodo ha una proprietà fondamentale:

≥ 0 ∀(, ) ∈ ℎ ℎ

Questo vuol dire che non sarà più aggiornata, non esiste un percorso migliora vo

al nodo quando rappresenterà quindi il valore di e che a o mo. Si avrà

≥ 0:

determinato il percorso o mo dal nodo al nodo

.

DIMOSTRAZIONE

Sia l’insieme dei nodi che sono sta estra da e cioè:

= {: ≠ +∞, ∉ }

Allora tu i nodi hanno e che a permanente.

∈

Estraiamo tale che:

= min

{ }

∈

Quindi si estrae da e lo si inserisce in

= ∪ {}

Ora, supponendo che per non viene verificata la condizione di o malità:

()

∀(, ) ∈ → = +

Imponiamo: = ∪ {}

Siccome è stato supposto che i cos nella rete sono tu non nega vi:

≥

Alla fine di questa iterazione: ≥ ∀ ∈

Alla successiva iterazione si estrae il nodo ℎ:

ℎ = min

{ }

∈

Quindi: ≥

Se esiste l’arco allora:

(ℎ, ) > + ò

Non può succedere perché e assun i cos non nega vi, la relazione sopra

≤

citata non sarà mai verificata.

In defini va: + ≥ ∀ ∈ |(ℎ, ) ∈

E cioè i vincoli del problema duale sono sempre verifica per ogni nodo

appartenente ad qualsiasi sia

ℎ.

ESERCIZIO 1

=1

1

2

1 3

7

1

4 1

1

Viene riportata una rete e si vuole trovare il percorso o mo da a tu gli altri nodi.

= 1

Procediamo con l’algoritmo.

PASSO 0 = {1}

1 2 3 4 5 6

= 0 +∞ +∞ +∞ +∞ +∞

= [1,2,3,4,5,6]

PASSO 1 (Iterazione 1)

Estrai da

1 = {∅}

PASSO 2 = {(1,2)}

Verifichiamo: > + → +∞ > 0 + 1?

Aggiorniamo: 1 2 3 4 5 6

= 0 1 +∞ +∞ +∞ +∞

= [1,1,3,4,5,6]

= {2}

PASSO 3 ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 2)

Estrai da

2 = {∅}

PASSO 2 = {(2,3), (2,4)}

Analizziamo (2,3) > + → +∞ > 1 + 7?

Analizziamo (2,4): > + → +∞ > 1 + 1?

Aggiorniamo: 1 2 3 4 5 6

= 0 1 8 2+∞+∞

= [1,1,2,2,5,6]

= {3,4}

PASSO 3 ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 3)

Tu i cos associa agli archi sono cos posi vi.

Dobbiamo scegliere che strategia di estrazione portare avan : usiamo strategia

Estrai da

3 : = {4}

PASSO 2 (3) {(3,1)}

=

In questo caso e quindi mi posso fermare e non valutare l’arco. Si può proseguire

= 1 =

al passo 3

PASSO 3

Si ricorda che non è necessario fare il passo sui cicli di costo nega vo perché i cos sono tu

posi vi. ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 4)

Estrai da

4 = {∅}

PASSO 2 (4) {(4,6)}

=

Analizziamo (4,6) > + → +∞ > 2 + 2?

Aggiorniamo: 1 2 3 4 5 6

= 0 1 8 2 +∞ 4

= [1,1,2,2,5,4]

= {6}

PASSO 3 ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 5)

Estrai da

6 = {∅}

PASSO 2 (6) {(6,5)}

=

Valu amo (6,5): > + → +∞ > 4 + 1?

Aggiorniamo: 1 2 3 4 5 6

= 0 1 8 2 5 4

= [1,1,2,2,6,4]

{5}

=

PASSO 3 ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 6)

Estrai da

5 = {∅}

PASSO 2 (5) {(5,2), (5,3),

= (5,4)}

Andremo a valutare dei nodi che hanno già delle e che e e verifichiamo se si possono

aggiornare (se esistono cammini con un costo minore)

Valu amo (5,2): > + → 1 > 5 + 3?

Non andiamo ad aggiornare.

Valu amo (5,3): > + → 8 > 5 + 1?

Si ha un path che mi perme e di arrivare al nodo 3, che vado a ricostruire tramite lista dei

predecessori che ci indica come in questa a uale configurazione si ha un cammino dic osto

8 che finisce a 3 e ha come predecessori 2 e 1.

Uso il ve ore dei predecessori per ricostruire il path a ritroso.

E’ o mo questo path? No, si ha trovato un altro path che ha un costo pari a 5+1=6 e ha

quindi un costo associato migliore.

Aggiorniamo: 1 2 3 4 5 6

= 0 1 6 2 5 4

= [1,1,5,2,6,4]

{3}

=

Valu amo (5,4): > + → 2 > 5 + 1?

Non si aggiorna nulla.

PASSO 3 ≠ {∅}

Quindi si torna al Passo 1 e inizia una nuova iterazione

PASSO 1 (Iterazione 7)

Estrai da

3 = {∅}

PASSO 2 (3) {(3,1)}

=

Poiché non bisogna fare nulla

= 1 =

PASSO 3 = {∅}

Allora STOP, si è o enuta la soluzione o ma.

Se viene chiesto di costruire il path per il nodo 4:

1 1

PASSO 1 (Iterazione 3)

Tu i cos associa agli archi sono cos posi vi.

Dobbiamo scegliere che strategia di estrazione portare avan : usiamo strategia

Bisogna estrarre il nodo con e che a minore:

= min

{ }

∈

= min

{8,2} = 4