Ricerca Operativa

L P P

( ) ( )

=L +l =¿

r r v v

−1 jr−1 jr

Trascritto in italiano: v

Il peso del cammino per arrivare a =

jr v

Al peso del cammino per arrivare al nodo precedente +

jr−1

v v

Il peso dell’arco diretto che collega a =

jr−1 jr

v

All’etichetta associata a +

jr−1 v v ≥

Il costo dell’arco diretto che collega a

jr−1 jr

v

Dell’etichetta associata al nodo che, per quanto detto prima è >

jr

P

Del peso del cammino quindi abbiamo una contraddizione.

r

2) condizione necessaria

v v

Ipotesi: tutte le etichette rappresentano il peso di un cammino da s a è

π jr)

(¿¿ jr

¿

j=1 … n

minimo .

∀ v v

Per assurdo esistono due nodi e con (p<q) per i quali la condizione

jp jq

v

v NON è verificata. Per le ipotesi deve esistere un cammino minimo da s

π p)+l

(¿¿ vq, vp

π q)≤

(¿¿ ¿

¿ v

v

fino a a cui è associata l’etichetta . Ma quindi deve esistere un cammino

π jp

(¿¿ )

jp ¿

v

v

v

orientato da s a di peso e questa è una contraddizione.

π q)

(¿ ¿

jq π p)+l

(¿¿ <¿

vq, vp

¿

Generali Algoritmo Dijkstra

Ipotesi: tutti i pesi degli archi devono essere positivi o nulli.

Calcola il peso del cammino da un nodo dato a tutti gli altri, aggiornando le etichette (

v v

v v

)ogni qual volta la condizione NON è verificata. Si possono

π i)+l π i)+l

(¿¿ (¿¿

vi ,vj vi ,vj

π j)=¿ π j)≤

(¿¿ (¿ ¿ ¿

¿ ¿

avere diversi cammini minimi dal nodo 1 al nodo i. Vi sono due insiemi di nodi:

1) S: contiene il nodo 1 è tutti gli altri nodi per cui abbiamo trovato un cammino minimo

2) T: tutti gli altri

Ad ogni iterazione (n-1 totali) l’algoritmo sposta un nodo da T->S

• Inizializzazione

Passo 0: Si pone S = {1}, T = {2,...,n}, π(1) = 0

1

( )

+¿

π(i) = ¿

{ l sei N ∞ altrimenti

∈ +

1i

precedente[i] = 1, i = 2,...,n.

• Iterazione generica

Assegnazione etichetta permanente 1

Passo1: si trova j T tale che π(j)=min[π(i)] , per i T

∈ ∈

Passo 2: si pone T = T \ {j}, S = S {j}

∪

Passo 3: se T = , STOP (terminazione dell’algoritmo)

∅

Assegnazione etichetta provvisoria

Passo4: per ogni i T ∩ N+(j) tale che π(i)>π(j)+lji si pone π(i) = π(j) + lji

∈

pred[i] = j e si va al Passo 1

Proposizione 12.5.2

1) L’etichetta provvisoria non è crescente all’aumentare delle iterazione

2) L’etichetta permanente è non decrescente all’aumentare delle iterazioni.

Teorema 12.5.3

Quando l’algoritmo termina le etichette rappresentano il peso del cammino minimo.

Perché?

1 il cammino per arrivare al j-esimo nodo (si ricorda che j viene dopo i) deve essere scelto

tra il più piccolo cammino

Dimostrazione per assurdo:

Deve essere rispettato il teo 12.5.2 (condizioni di ottimalità).

l l ≥ 0

Ci sono per assurdo due nodi p & q tc: π(q)>π(p)+ . Poiche per ipotesi,

pq pq

allora risulterà : π(q)>π(p). Poiche l’etichetta permanente non è decrescente, il nodo p

entra nell’insieme S prima di q, all’iterazione k. Alla fine di k abbiamo p S e q T ∩

∈ ∈

p)

+¿( e l’etichetta di p è diventata permanente. Dato che l’etichetta provvisoria del

¿

N l

nodo q non è crescente risulta che π(q) > π(p) + , ma, essendo stato selezionato p

pq l

all’iterazione k, l’etichetta di q viene aggiornata con π(q) = π(p) + -> quindi

pq

contraddizione. Simplesso

FASE 0)

Porre il modello in forma standard, ovvero deve essere composto solo da

equazioni : ≥

Per ogni inserisco una variabile di surplus negativa

{

min[3x x x

+2 + ] x ≤

, invece per ogni inserisco una variabile di slack

1 2 3 5

x x

+ −x =2 x

positiva . Inoltre non è presente il vincolo di non

1 2 3 4

x x ≤ 5

+2 x

negatività per , quindi ho due scelte:

1 2 5

2 x ≥ 4 −¿

−x

1 3 ¿

+¿−x

Impongo e metto le ultime due maggiori di zero.

x e x ≥ 0 3

1 2 ¿

x =x

3 3 x x

=x + −2

Oppure uso l’equazione per dire che ,

3 1 2

{

min[4x x

+3 −2] x

eliminando la variabile

1 2 3

x x x

+2 + =5

1 2 4

x −x +2−x =4

1 2 5

Se per caso ho un problema di massimizzazione mi basta usare min ed

invertire il segno dei coefficienti della funzione obbiettivo.

FASE 1, i=0)

Mettere il modello in forma canonica e scegliere la base (di solito la matrice

identità).

Nella forma canonica passo al problema ausiliario, aggiungendo m (vincoli)

… .

variabili artificiali , che si sommano ad ogni vincolo, e la funzione

∝ ∝

1 m .+∝

obbiettivo risulta: min/max( ). Da ricordare che la FO deve dare

∝ +…

1 m

risultato pari a zero per verificare l’ammissibilità del problema originario.

Un po’ di nomenclatura:

X : è il vettore delle variabili di base, ovvero quelle n variabili che ho scelto

Bi

per formare la base.

B : è la matrice associata alle variabili di base, dove il pedice indica il passo

i

dell’algoritmo

c : vettore dei coefficienti delle variabili in base, nella funzione obbiettivo

Bi : vettore delle variabili non in base, le restanti variabili che non ho scelto

X ¿

N : la matrice delle variabili non in base, stessa cosa per il pedice

i

b : termini noti

i vettore dei coefficienti delle variabili non in base nella funzione

c :

¿

obbiettivo

Scriviamo la matrice a dei coefficienti del seguente modello:

min−2x 1+4x 2−2x 3+2 x 4

x 1+ 4x 2+2x 3+ x 4=6 → A=¿

2x 1+ x 2+2x 3+ x 5=3

x ≥0 ¿

¿

B

Iniziamo con e la poniamo uguale alla matrice identità:

i

( )

1 0 che si riferisce alle variabili e . Quindi il nostro

B x 4 x 5

=

i 0 1

x

( )

X = 4 e

Bi x

5

2

( )

c =

Bi 0 ( )

x ( )

−2

1

( )

1 4 2 e c

Allora otteniamo , = . E i termini noti sono

x 4

N X =

= ¿

2

i ¿

2 1 2 −2

x 3

63

( )

b = .

i

FASE 3) γ

Calcolo dei costi ridotti tramite formula.

i

B ( ) ( ) ( ) ( ) ( )

1 2 2

−2 −2 −4

( )

2

T

−1

γ i

= ->

(¿¿ ∗N ) ∗c − ∗ = − =

4 4 1 4 8 −4

i i Bi 0

2 2 4

−2 −2 −6

c −¿

¿

Criterio di ottimalità:

Dati tutti i valori dei costi ridotti il criterio è rispettato se questi sono tutti .

≥ 0

Da notare che se è strettamente positivo allora la soluzione ottima trovata è

anche l’unica, altrimenti ce ne potrebbero essere altre. Se viene rispettato hai

finito, senno trovi l’indice i del minore dei valori negativi (in questo caso -6-

>i=3) e si passa al:

Criterio di limitatezza:

Dati i valori che non hanno superato il criterio di ottimalità devo vedere se le

colonne associate ai suddetti valori sono tutte .

≤ 0

B

Quindi devo guardare la matrice e in questo caso tutte e tre le

−1

i

(¿¿ ∗N )

i

¿

colonne -> fallito anche qui il test quindi devo scegliere una nuova base

ammissibile. Se fosse stato verificato allora avrei finito.

FASE 4)

Determinazione di una nuova base ammissibile.

In pratica dobbiamo scegliere quale variabile entra e quale esce guardando le

B τ

colonne della matrice che chiameremo .

−1

i

(¿¿ ∗N ) i

i

¿

Scegliamo chi entra.

Devo trovare l’indice h della variabile minore presente nel vettore dei costi

ridotti. Una volta trovato h la variabile h-esima nel vettore sarà quella

X ¿

che entra. ( )

x

( )

−4 1

γ →h=3 → X → entrala variabile x

x

= =

−4 ¿

i 3

2

−6 x 3

Scegliamo chi esce con il criterio del rapporto minimo:

ho due vettori di numeri:

b: il vettore dei termini noti = 6 3

( )

1 4 2 2

τ N

: h-esima colonna di = →

h i 2 1 2 2

devo scegliere l’indice k del minore, secondo la formula sottostante. Se ho

che nella k-esima colonna di N ci sta un valore minore stretto di zero non

devo contare quell’elemento, ma il k resta comunque nel range di n, quindi ne

rimangono n-1.

{ }

−1 ∣

B b { }

∣ 3

{ }

6 3 = k=2, quindi l’uscente è il secondo elemento di

i 3 →

⁡

min = 2

τ 2 2

h x

( )

4

X x

= ->

B 0 5

x 5

Nuova base provvisoria, cambierà N, i=1:

x

( ) 2

( )

1 2 ( )

X = c

--- = ---

4 =

B

Bi Bi

i

x 0 2 −2

3

( )

x ( )

−2

1 ( )

1 4 0

--- = --- .

X x c

= N =¿ 4

¿ ¿

2 2 1 1 0

x

5

FASE 5)

Passaggio a forma canonica. ( )

Devi costruire la matrice di passaggio A composta da ,

−1 −1

τ B N B b

h di Bi i−1 i i−1

ovvero:

la colonna della matrice B che ho appena cambiato

• tutta la matrice dei coefficienti fuori base appena trovata

• il precedente valore dei termini noti

• ( )

2 1 4 0 6

→ 2 2 1 1 3

essendo un passaggio di base deve risultare questo anche nei calcoli, quindi

la logica che sta dietro il Pivot è la seguente:

La prima colonna della matrice A è il vecchio valore di B, quindi questo deve

( )

22

essere aggiornato al nuovo, ma questo vuol dire far coincidere con

( )

01 solo tramite sottrazioni/addizioni tra righe e tutto deve essere fatto in

DUE passaggi (impostare un valore a uno e l’altro a zero). Quindi risulta:

( )

0 3 3

−1 −1

1 1 1/2 1/2 3 /2

Questo aggiornamento modificherà anche la parte restante e

−1

B N

i−1 i