Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Problema del cammino di costo minimo

Algoritmo di Dijkstra

Esempio. Calcoliamo tutti i cammini minimi dal nodo 1 agli altri nodi

()*+

/.-, ()*+

/.-, /.-,

()*+

/ /

@ A ;

] 6

2 4

9 1 O

;;

;;

;;

()*+

/.-,

2

;;

;;

=

1 3

3 3

4 4

= ;;

=

= ;

;;

=

()*+

/.-, /

()*+

.-, /.-,

()*+

=

6 ;;

=

=

/ /

5 7

3 1 2

{1}, {2,

Inizialmente U P 3, 4, 5, 6, 7} colle seguenti etichette

= =

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) ∅) ∅) ∅) ∅) ∅) ∅)

(0, (∞, (∞, (∞, (∞, (∞, (∞, dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 39 / 72

Problema del cammino di costo minimo

Algoritmo di Dijkstra

I nodi 2 e 3 sono adiacenti ad 1 ed otteniamo la seguente tabella

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) ∅) ∅) ∅) ∅)

1) 1)

(0, (2, (6, (∞, (∞, (∞, (∞,

{2}.

Il potenziale minimo è d 2 e U

= =

2

I nodi 3 e 4 sono adiacenti a 2; i costi parziali sono

d min{6, 2 3} 5 e d min{∞, 2 9} 11.

= + = = + =

3 4

Otteniamo la seguente tabella di etichette aggiornate

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) ∅) ∅) ∅)

1) 2) 2)

(0, (2, (5, (11, (∞, (∞, (∞,

{3}.

Il potenziale minimo è d 5 e U

= = dsm

3

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 40 / 72

Problema del cammino di costo minimo

Algoritmo di Dijkstra

I nodi 4 e 5 sono adiacenti a 3; i costi parziali sono

d min{11, 5 4} 9 e d min{∞, 5 1} 6

= + = = + =

5

4

Otteniamo la seguente tabella di etichette aggiornate

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) ∅) ∅)

1) 2) 3) 3)

(0, (2, (5, (9, (6, (∞, (∞,

{5}.

Il potenziale minimo è d e U =

5

Il nodo 7 è adiacente a 5; il costo parziale è

d min{∞, 6 2} 8.

= + =

7

Otteniamo la seguente tabella di etichette aggiornate

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) ∅)

1) 2) 3) 3) 5)

(0, (2, (5, (9, (6, (∞, (8, dsm

{7}.

Il potenziale minimo è d e U =

7

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 41 / 72

Problema del cammino di costo minimo

Algoritmo di Dijkstra

I nodi 4 e 6 sono adiacenti a 7; i costi parziali sono

d min{9, 8 3} 9 e d min{∞, 8 3} 11

= + = = + =

4 6

Otteniamo la seguente tabella di etichette aggiornate

nodo 4 nodo 5 nodo 6 nodo 7

nodo 1 nodo 2 nodo 3

∅) 1) 2) 3) 3) 7) 5)

(0, (2, (5, (9, (6, (11, (8,

{4}.

Il potenziale minimo è d e U =

4

Il nodo 6 è adiacente a 4 (il nodo 5 ha etichetta permanente); il

costo parziale è d min{11, 9 1} 10.

= + =

6

Otteniamo la seguente tabella di etichette aggiornate

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) 1) 2) 3) 3) 4) 5)

(0, (2, (5, (9, (6, (10, (8, dsm

{6}.

Il potenziale minimo è d e U =

6

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 42 / 72

Problema del cammino di costo minimo

Algoritmo di Dijkstra

Essendo P abbiamo etichettato in maniera permanente tutti i nodi:

=

nodo 1 nodo 2 nodo 3 nodo 4 nodo 5 nodo 6 nodo 7

∅) 1) 2) 3) 3) 4) 5)

(0, (2, (5, (9, (6, (10, (8,

Passiano a determinare i cammini.

Prima di 2 c’è 1: il cammino è 1–2.

Prima di 3 c’è 2 e prima c’è 1: il cammino è 1–2–3.

Prima di 4 c’è 3, prima c’è 2 e prima c’è 1: il cammino è 1–2–3–4.

Prima di 5 c’è 3, prima c’è 2 e prima c’è 1: il cammino è 1–2–3–5.

Prima di 6 c’è 4, prima c’è 3, prima c’è 2 e prima c’è 1: il cammino

è 1–2–3–4–6.

Prima di 7 c’è 5, prima c’è 3, prima c’è 2 e prima c’è 1: il cammino

è 1–2–3–5–7. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 43 / 72

Problema del cammino di costo minimo

Algoritmo di Dijkstra

L’albero dei cammini minimi è il seguente /.-,

()*+

()*+

/.-,

()*+

/.-, /

/

@ ]

A 6

4

2 9 1 O

()*+

/.-,

2

1 3

3

3 4 4

()*+

/.-, /.-,

()*+ /.-,

()*+

6

/ /

5 7

3 1 2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 44 / 72

Problema del trasporto

Introduzione

Il problema del trasporto prende il nome dal contesto nel quale è stato

sviluppato: la determinazione di modelli per la destinazione ottimale di

merce. Anche questo problema è un particolare problema di flusso di

G

costo minimo ma in un grafo bipartito cioè in un grafo A) dove

= (N,

è possibile partizionare N in due insiemi N e N tali che

o d

∪ ∩ ∅

N N N e N N

= =

o o

d d

∈ ∈ ∈

per ogni j) A si ha i N e j N .

(i, o d

Il problema consiste nello stabilire il flusso di costo minimo di una

merce richiesta da n punti vendita e disponibile in quantità

= #N

d

limitata negli m centri di produzione. Saranno note

= #N

o −a ∈

le offerte a dei centri di produzione (bilancio 0 su i N ),

< o

i i ∈

le domande b dei punti vendita (bilancio b 0 su j N ),

>

j j d

i costi c di spedizione per unità di merce da i al j.

ij dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 45 / 72

Problema del trasporto

Introduzione

Si possono verificare tre casi:

n

m X

X a b

=

1 i j

j=1

i=1

cioè la domanda totale uguaglia l’offerta ed il problema si dirà

bilanciato,

m n

X X

a b

<

2 i j

i=1 j=1

in tal caso le richieste non possono essere soddisfatte,

m n

X X

a b

>

3 i j

i=1 j=1

in tal caso resteranno giacenze nei centri di produzione. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 46 / 72

Problema del trasporto

Introduzione

Supporremo di trovarci sempre in presenza di un problema bilanciato.

Nel caso 2 si aggiunge un centro di produzione fittizio m 1 con

+

disponibilità pari all’eccesso di domanda

n m

X X

a b a

=

m+1 j i

j=1 i=1

Nel caso 3 si aggiunge un punto vendita fittizio n 1 con

+

domanda pari all’eccesso di offerta

m n

X X

b a b

= .

n+1 i j

i=1 j=1

In entrambi i casi i costi unitari di trasporto tra una delle due entità

aggiunte e le rimanenti risulteranno nulli. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 47 / 72

Problema del trasporto

Introduzione

Nuovamente x rappresenta la quantità di merce trasportata dal centro

ij

di produzione i al punto di vendita j ed il problema risulta:

 n

m X

X

 c x

min

 ij ij

 j=1

i=1

 n

 X

 x a i 1, m

= , = . . . ,

 ij i

j=1

 m

 X

 x b j 1, n

= , = . . . ,

 ij j

 i=1

 ≥

x 0, i 1, m, j 1, n

= . . . , = . . . ,

 ij dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 48 / 72

Problema del trasporto

Introduzione

Scritto sottoforma di tabella simpliciale diventa

c c c c c c c c c

. . . . . . . . . . . . mn

11 12 1n 21 22 2n m1 m2

1 1 1 0 0 0 0 0 0 a

... ... ... ... 1

0 0 0 1 1 1 0 0 0 a

... ... ... ... 2

..

··· ··· ··· ··· ··· ··· .

0 0 0 0 0 0 1 1 1 a

... ... ... ... m

1 0 0 1 0 0 1 0 0 b

... ... ... ... 1

0 1 0 0 1 0 0 1 0 b

... ... ... ... 2

.. .. .. .. .. .. .. .. .. ..

.. .. ..

. . .

. . . . . . . . . .

0 0 1 0 0 1 0 0 1 b

... ... ... ... n

dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 49 / 72

Problema del trasporto

Introduzione

Un problema del trasporto può essere visualizzato nella seguente

maniera / D

O 3

W h

W

12 (10)

(15) h 8

N W h 1

1 W h p

N W h

W h p

N W h

8 W p

h

W h

N p

W h

W h

N p

W

h

W

h

N p

W

7 h W

h

N p

W

h W

N

h p

W

h N W

h p W

h N p W

h W

N p

h W

h +

N

h p

N p

9 /

N

p N

p

V N D

O 3

V p h

V

5 (10)

(4) N h

p

V h 2

2 N

V h

p

V h

N

V p h

V h

N

8 p V h

V N

h

p V h N

V h

p V

h N

V

h

p V

h N

V

h V

h N

V

h V N

h V

p h V N

h

p 10 V

h

p V &

V

h V

h

h +

5 / D

O 7 (6)

(7) 3

3 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 50 / 72

Problema del trasporto

Introduzione

La descrizione come problema di PL è la seguente

 min 12x 8x 7x 9x 5x 8x

+ + + + +

11 12 13 21 22 23

 5x 7x

 +10x + +

 31 32 33

 x x x 15

+ + =

 11 12 13

 x x x 4

+ + =

 21 22 23

 x x x 7

+ + =

 31 32 33

 x x x 10

+ + =

 11 21 31

 x x x 10

+ + =

 12 22 32

 x x x 6

+ + =

 13 23 33

 ≥

x x x x x x x x x 0

, , , , , , , ,

 11 12 13 21 22 23 31 32 33 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 51 / 72

Problema del trasporto

Introduzione

Alcune osservazioni.

Indicato con Q la somma delle quantità offerte (o domandate)

m n

X X

Q a b

= =

i j

i=1 j=1

a b

i j

x per ogni i, j, si ha

si osserva che, ponendo =

ij Q

n n m n

b

a j

i

X X X X

x b a e x a b

= = = = ;

ij j i ij i j

Q Q

j=1 j=1 i=1 i=1

S 6 ∅.

quindi = S

Inoltre la regione ammissibile oltre ad essere chiusa è anche

≤ ≤ };

limitata poiché 0 x min{a b quindi, per il Teorema di

,

ij i j dsm

Weierstrass, esiste soluzione ottima.

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 52 / 72

Problema del trasporto

Introduzione

L’osservazione più utile riguarda il problema duale che assume la

seguente forma (verificatela dalla tabella simpliciale):

m n

 X X

 max a u b v

+

 i i j j

i=1 j=1

 ≤

u v c i 1, 2, m, j 1, 2, n

 + , = . . . , = . . . ,

i j ij

Osservazione

Ogni variabile duale è associata ad un nodo: le variabili u sono

i

associate ai nodi di N mentre le variabili v sono associate ai nodi N .

o j d

Il problema duale è detto problema dei potenziali e la formula degli

scarti complementari diventa

− −

x u v 0, i 1, 2, m, j 1, 2, n

(c ) = = . . . , = . . . ,

ij ij i j dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 53 / 72

Problema del trasporto

La tabella dei trasporti

L’applicazione diretta del metodo del simplesso, causa l’ampiezza dei

dati, sarebbe complessa: si userà una variante che, mantenendone la

struttura, risulta più rapida. Lavoreremo con la seguente tabella:

c c c

α α α

11 11 12 12 1n 1n

···

x x x a u

11 12 1n 1 1

c c c

α α α

21 21 22 22 2n 2n

···

x x x a u

21 22 2n 2 2

.. .. .. .. ..

. . . . .

c c c

α α α

mn mn

m1 m1 m2 m2 ···

x x x a u

mn m m

m1 m2

b b b n

1 2

v v v

n

1 2

Riassume i costi unitari, le disponibilità, le richieste, i costi ridotti, la dsm

soluzione di base ammissibile sia primale sia duale.

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 54 / 72

Problema del trasporto

La tabella dei trasporti

Nel nostro caso la tabella diventa

12 8 7

α α α

11 12 13

x x x 15 u

11 12 13 1

9 5 8

α α α

21 22 23

x x x 4 u

21 22 23 2

10 5 7

α α α

31 32 33

x x x 7 u

31 32 33 3

10 10 6

v v v

1 2 3 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 55 / 72

Problema del trasporto

Soluzione di base

Il primo punto riguarda l’individuazione di una soluzione di base

ammissibile. −

Avendo m n vincoli, la matrice di incidenza ha carB m n 1

+ = +

mentre le variabili sono mn: quindi ogni soluzione di base

ammissibile deve avere almeno

− − − −

mn n 1) 1)(n 1)

(m + = (m

assegnazioni nulle. Per la precisione − −

se le assegnazioni nulle sono esattamente 1)(n 1) il vertice

(m

I è non degenere, − −

se le assegnazioni nulle sono maggiori di 1)(n 1) il vertice è

(m

I degenere.

Inoltre non ci devono essere cicli chiusi (perché?) dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 56 / 72

Problema del trasporto

Soluzione di base

Per generare una prima soluzione di base si può utilizzare il metodo di

che consiste nella seguente procedura:

Nord–Ovest

partiamo dalla casella x in alto a sinistra (Nord–Ovest);

1 11

assegniamo il massimo valore compatibile con i vincoli;

2 ci spostiamo nella casella adiacente a destra se ci sono ancora

3 disponibilità, diversamente scendiamo di una casella e ripetiamo il

punto 2 fino al completamento della tabella.

La soluzione così trovata è una soluzione di base con base formata

dalle caselle visitate. Questa procedura non tiene di conto dei costi

unitari e potrebbe generare una soluzione distante da quella ottima.

Un secondo metodo, noto come metodo di costo minimo, prevede il

riempimento delle caselle a partire da quella di minor costo (in caso di

parità la scelta segue l’ordine lessicografico). dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 57 / 72

Problema del trasporto

La tabella dei trasporti

Generiamo una soluzione di base con il metodo dei costi minimi

12 B 8 7 B

α

12

9 0 6 15 u 1

9 5 B 8

α α

21 23

0 4 0 4 u 2

10 B 5 B 7 α

33

1 6 0 7 u 3

10 10 6

v v v

1 2 3

{x }.

Le variabili in base sono x x x x

, , , ,

11 13 22 31 32 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 58 / 72

Problema del trasporto

La tabella dei trasporti

Se vogliamo visualizzare la soluzione di base attraverso il grafo

abbiamo la seguente rappresentazione / D

O 3

9 (10)

(15) 8

N 1

1 p

N p

N p

p

N p

N p

N

6 p

N p

N p

N p

N p

N +

p

N p

N

p /

N

p N

p N D

O 3

h

4 (10)

p

(4) N h

h 2

2 p N h

h

p N h

h

p N

h

p N

h

h

p N

h

h

p N

h

h

p N

h

h N

h N

p h

h N

p h

1

h

p &

h

h

h +

6 / D

O (6)

(7) 3

3

dove, questa volta, i valori sugli archi rappresentano le variabili x .

ij

Come si vede abbiamo ottenuto un albero ricoprente. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 59 / 72

Problema del trasporto

La tabella dei trasporti

Determinata una soluzione di base ammissibile, si ricerca la soluzione

ottima procedendo come per il metodo del simplesso, facendo entrare

ed uscire di base le variabili opportune.

Il primo passo consiste nel calcolare le variabili duali attraverso gli

scarti complementari. Quindi, per ogni x in base si deve avere

ij

u v c

+ = .

i j ij

Essendo le variabili duali in numero superiore a 1 rispetto alla

caratteristica, il sistema di equazioni è sovradeterminato e dipende da

un parametro: poniamo quindi u 0.

=

1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 60 / 72

Problema del trasporto

La tabella dei trasporti

Otteniamo la seguente tabella aggiornata

12 B 8 7 B

α

12

9 0 6 15 0

9 5 B 8

α α

21 23

0 4 0 4 -2

10 B 5 B 7 α

33

1 6 0 7 -2

10 10 6

12 7 7

−2, −2,

La soluzione di base duale associata è 12, 7, 7). A questo

(0,

punto si controlla se è ammissibile determinando il gradiente ridotto;

cioè calcolando − −

c u v

α =

ij ij i j dsm

per ogni j) non in base.

(i,

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 61 / 72

Problema del trasporto

La tabella dei trasporti

Otteniamo la seguente tabella aggiornata

12 B 8 1 7 B

9 0 6 15 0

9 -1 5 B 8 3

0 4 0 4 -2

10 B 5 B 7 2

1 6 0 7 -2

10 10 6

12 7 7

Poiché 0 la soluzione di base duale non è ammissibile e quindi

α <

21

la soluzione di base ammissibile primale non è ottima. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 62 / 72

Problema del trasporto

La tabella dei trasporti

Entra in base x ma chi esce? Mettendo in base x cioè

21 21

aggiungendo l’arco 1) all’albero si viene a creare un ciclo: tra gli

(2,

archi di quel ciclo cerchiamo quello da eliminare:

/ D

O 3

3s

9 (10)

(15) 8

3s

N 1

1 3s p

N s 3

N s 3 p

3s

N 3s

3s

N p

3s

N

6 3s

N p

3s

N

3s N

s 3 p

3s N

3s N p

3s +

N

N p

_ _ _ _ _ _ _ _ _ _ _ _ _ /

N

N

p N D

O 3

h

4 (10)

(4) N

p h 2

2 N h

N

p h

N

N

h

p N

h N

h

p N

h N

h N

p h N

1

h

p &

h

h +

6 / D

O (6)

(7) 3

3

Il ciclo è formato dagli archi

{(2, 1), 1), 2), 2)}

(3, (3, (2, dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 63 / 72

Problema del trasporto

La tabella dei trasporti

Aumenteremo il più possibile il flusso in x e x e lo diminuiremo in

21 32

x e x : ovviamente quanto aumenteremo x e x coincide a

31 22 21 32

quanto diminuiremo x e x che devono rimanere non negative. Il

31 22

massimo che possiamo aggiungere è

}

min{x x min{1, 4} 1

, = =

31 22

In tal caso esce x . Come si riesce a vedere il tutto dalla tabella del

31

trasporto? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 64 / 72

Problema del trasporto

La tabella dei trasporti 8 1 7 B

12 B

9 0 6 15 0

9 -1 5 B 8 3

0 4 0 4 -2

10 B 5 B 7 2

1 6 0 7 -2

10 10 6

12 7 7

Il minimo tra le caselle indicate da è 1. Quindi aumentiamo di 1 le

variabili nelle caselle indicate da e diminuiamo di 1 quelle nelle

caselle indicate da . dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 65 / 72

Problema del trasporto

La tabella dei trasporti

La nuova tabella risulta

12 B 8 7 B

9 0 6 15

9 B 5 B 8

1 3 0 4

10 5 B 7

0 7 0 7

10 10 6

{x }.

con variabili in base x x x x Nuovamente ci calcoliamo

, , , ,

11 13 21 22 32

le variabili duali ponendo u 0 e risolvendo il sistema di equazioni

=

1 u v c

+ =

i j ij dsm

per ogni j) in base.

(i,

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 66 / 72

Problema del trasporto

La tabella dei trasporti B 8 7 B

12 9 0 6 15 0

9 B 5 B 8

1 3 0 4 -3

10 5 B 7

0 7 0 7 -3

10 10 6

12 8 7

Ed ora passiamo al gradiente ridotto calcolando

− −

c u v

α =

ij ij i j

per ogni j) non in base.

(i, dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 67 / 72

Problema del trasporto

La tabella dei trasporti

12 B 8 0 7 B

9 0 6 15 0

9 B 5 B 8 4

1 3 0 4 -3

10 1 5 B 7 3

0 7 0 7 -3

10 10 6

12 8 7

Essendo tutte le componenti del gradiente ridotto non negative

abbiamo ottenuto la soluzione ottima. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 68 / 72

Problema del trasporto

La tabella dei trasporti

Il grafo che rappresenta la soluzione ottima è la seguente

/ D

O 3

h

9 (10)

(15) h 8

N h 1

1 h

N h

h

N h

h

h

N h

h

N h

h

N h

6 h

N h

N

h

h N

h

h N

h N

h

h +

N

h N

1 /

N

N

N D

O 3

h

3 (10)

(4) N h

h 2

2 N h

h

N h

h

N

h N

h

h N

h

h N

h

h N

h

h N

h N

h

h N

h

h &

h

h

h +

7 / D

O (6)

(7) 3

3

Il costo del trasporto è 209. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 69 / 72

Problema del trasporto

La tabella dei trasporti

Ripetiamo l’algoritmo partendo da una soluzione costruita col metodo

di Nord–Ovest (in rosso), determinando le variabili duali in scarti

blu), calcolando i coefficienti del gradiente ridotto (in

complementari (in

viola) ed individuando, eventualmente, il ciclo minimizzante (in verde).

12 B 8 B 7 -3

10 5 0 15 0

9 0 5 B 8 1

0 4 0 4 -3

10 1 5 B 7 B

0 1 6 7 -3

10 6

10

12 8 10

{x } {x }

Passiamo da B x x x x a B x x x x

= , , , , = , , , ,

1 11 12 22 32 32 2 11 13 22 32 32

aumentando x e x di 5 unità. dsm

13 32

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (prima parte) 70 / 72


PAGINE

72

PESO

632.05 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Teoria dei grafi: i grafi e definizioni principali; Matrice di incidenza, esempi. Albero ricoprente di costo minimo: Algoritmo di Kruskal; Algoritmo di Prim; applicazioni ed esempi. Problema del flusso di costo minimo: Algoritmo di Dijkstra; applicazioni ed esempi. Problema del trasporto: tabella dei trasporti; soluzione di base; applicazioni ed esempi.


DETTAGLI
Corso di laurea: Corso di laurea in economia e amministrazione delle imprese
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Castellani Marco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ricerca operativa

Programmazione Lineare Intera
Dispensa
Programmazione lineare
Dispensa
Modelli
Dispensa
Analisi numerica - Metodo delle secanti
Dispensa