Appunti Ottimizzazione Combinatoria Gestionale, Sapienza

8- CAMMINO MINIMO E SCARTO COMPLEMENTARE.

1. Definire la condizione di scarto complementare.

2. Dare una definizione di “Grafo Ridotto”.

3. Dimostrare il teorema F4.

SVOLGIMENTO:

1. Dato il problema primale ed il rispettivo duale:

′ ′ ′ ′

Siano poi le rispettive soluzioni, vale che sono OTTIME per i rispettivi

problemi se e solo se: ′ ′ ′

( )

− + = 0 , ∈

∗ ∗

Ovvero vettore di incidenza di un cammino è ottimo se e solo se esiste una soluzione del

∗

duale tale per cui:

∗ ′ ∗ ∗

= + , ∈ = 1 ( ∈ )

′ ′ ′ ′

( )(, )

2. Data una soluzione duale , diremo Grafo Ridotto rispetto ad , il grafo con

′ ′ ′

= { ∈ : = − , ovvero è quel sotto grafo ricoprente di G(N,A), definito dagli

} ′

archi associati ai vincoli duali soddisfatti all’uguaglianza da .

3. (Vedi foglio dimostrazioni).

9- ALGORITMO DI BELLMAN – FORD.

1. Illustrare dettagliatamente l’algoritmo.

2. Analizzare la sua Complessità Computazionale.

3. Fornire un esempio numerico di applicazione dell’algoritmo.

SVOLGIMENTO:

1. Per illustrare l’algoritmo di Bellman-Ford, è necessario introdurre il concetto di

∀ ∈ ,

“arborescenza”. Si definisce arborescenza di radice i, quell’albero in cui, l’unico

cammino dal nodo i al nodo j è un cammino orientato. Un’ arborescenza può essere

.

descritta mediante il vettore dei predecessori

L’algoritmo di Bellman-Ford viene implementato per trovare l’arborescenza dei cammini

minimi e lo fa utilizzando le condizioni ottimalità necessarie e sufficienti per il cammino a

costo minimo, derivanti dalle condizioni di scarto complementare e quindi, dalla teoria

sulla Dualità. - Alla fine del processo sarà possibile ricondursi all’arborescenza

studiando il vettore dei predecessori.

- L’arborescenza dei cammini minimi sarà quella relativa al nodo la cui

variabile iniziale era stata inizializzata a zero.

In termini di dualità si procede come segue: 0



Vengono ordinati gli archi e definita una particolare soluzione duale che non è

ammissibile ma che è facile da scrivere.

 Ad ogni iterazione gli archi vengono visitati nell’ordine prefissato: se per un certo

(, ) > +

arco si ha che , violando quindi l’ammissibilità duale, si rende

ammissibile ponendo = +

 Dopo un certo numero di iterazioni tutte le condizioni di dualità vengono

soddisfatte.

In termini pratici:

 ∞.

Si inizializzano i costi di ogni arco ad

 Si scorrono i nodi partendo dalla radice (ordine prefissato) e si aggiorna man mano

il costo: se il costo del nodo successivo è maggiore rispetto a quello dato dalla

somma del costo del nodo di partenza più l’arco necessario a raggiungere il nodo

studiato, si aggiorna il costo del nuovo arco.

2. In termini di complessità computazionale si osserva come il blocco [Repeat – EndRepaeat]

venga eseguito non più di volte, ed ognuna di queste volte si avranno iterazioni del

= ||).

ciclo for per m volte (dove ().

Si avrà quindi una complessità di tipo polinomiale essendo il problema un

3.  INIZIALIZZAZIONE y(1)= 0 ∞

y(2)= y(3)= y(4)=

 ORDINO GLI ARCHI

1,2

1 1,3

2 3,2

3

3,4

4

2,4

5

 REPEAT 1 (2) = 1

(2) = ∞ + 1 Prec(2)=1

K=1 >(1) (3) = 6 Prec(3)=1

(3) = ∞ > (1) + 6

K=2 - -

(2) = 1 < (3) − 2 = 4

K=3 (4) = 9 Prec(4)=3

(4) = ∞ > (3) + 3 = 9

K=4 (4) = 5 Prec(4)=2

(4) = 9 > (2) + 4 = 5

K=5

 REPEAT 2

Al passo successivo si vede come non cambi più il vettore prec.

 RICAVO VETTORE OTTIMO:

prec(4) 2

prec(2) 1

prec(3) 1

10- ALGORITMO DI FLOYD - WARSHALL.

1. Scrivere l’algoritmo completa e spiegare cosa risolve.

2. Spiegare le varie operazioni, in particolare come si inizializzano le strutture dati e la formula

di aggiornamento della matrice D.

3. Fornire un esempio numerico dell’algoritmo.

SVOLGIMENTO:

1. Dato un grafo G(N,A), l’algoritmo di Floyd Warshall trova il cammino orientato di costo

minimo tra OGNI coppia di nodi. A differenza dell’algoritmo di Bellman Ford, che trova

l’arborescenza migliore data una radice i, il seguente algoritmo indica una soluzione più

complessa per il grafo G.

Affinché sia applicabile è necessario che esista un cammino orientato tra ogni coppia di

nodi, in modo tale che il problema del cammino minimo ammetta sempre una soluzione.

Pertanto è necessario applicare l’algoritmo su un grafo completo: se così non fosse lo si

può rendere tale inserendo gli archi mancanti ed imputando loro un costo infinito.

2. L’algoritmo ha come finalità la scrittura di una “Matrice dei Costi Minimi”, che avvenga

attraverso un processo iterativo.

MATRICE DEI COSTI MINIMI:

Dato un insieme di nodi N, si definisce il cammino minimo tra i e j con nodi interni solo

all’insieme .

Detto quindi il costo del cammino minimo sopra definito, si definisce la matrice dei

costi relativi. 0

Inizializzando una matrice , si vuole allora ricavare la matrice , dove nella matrice

iniziale i valori sono tutti pari ad infinito (si scorrono solo i nodi a distanza 0), nell’ultima

matrice l’insieme dei nodi comprende tutti i nodi del grafo.

 PASSO 0

Per ogni nodo si calcola la distanza dai propri adiacenti.

 PASSO K

Si aggiunge alla lista dei nodi un nuovo nodo e ricalcolo le distanze ottime.

 +1

Come passare da ?

Al passo k-1 non considero il nodo k-esimo. Per ogni cammino mi chiedo, nel caso k,

se abbia senso passare per quel nodo, cioè impongo

−1 −1 −1

= min { ; + }

3. 0 1 2

0

( )

∞ 0 −1

2 ∞ 0

0 1 2

1

( )

∞ 0 −1

2 0

0 1

2

( )

∞ 0 −1

2 3 0

0 1 0

3

( )

0 −1

2 3 0

1 1 1 1 1 1 1 1 1 1 2

0 1 2 3

( ) ( ) ( ) ( )

2 2 2 2 2 2 2 2 2 2 2

3 3 3 3 3 3 1 3 3 1 3

11- PROBLEMI DI FLUSSO MASSIMO.

1. Introdurre il problema del massimo flusso e dire perché si tratta di un problema di flusso

minimo.

2. Dimostrare che il flusso uscente da “s” è uguale al flusso entrante in “t”, e quindi ad f(x).

3. Determinare il duale del problema, DMF.

4. Dimostrare il teorema F5.

SVOLGIMENTO:

1. Anche i problemi di flusso massimo, così come quelli del cammino minimo, devono spesso

essere risolti. Questo tipo di problema, data una rete, cerca quel percorso migliore che

,

permetta di trasferire, partendo da una certo sorgente la massima quantità di flusso su

.

un nodo, la massima quantità di flusso su un nodo

 Problema di Massimo Flusso

- Si ha un nodo sorgente con soli archi uscenti ed un nodo pozzo con soli archi

entranti.

- Ho delle capacità per ogni arco, aventi però tutti costi uguali.

- Voglio trovare un flusso ammissibile tale da massimizzare il flusso entrante in

detto flusso s-t ed indicato con f(x).

- Se ho più sorgenti ne creo una a monte, se ho più valli ne creo una a valle.

Si tratta di un problema a costo minimo in cui ho un arco da t ad s di capacità

infinita e di costo pari a -1 mentre tutti gli altri archi hanno costo pari a 0.

In termini matematici, il flusso deve rispettare le seguenti caratteristiche:

o VINCOLO DI CAPACITA’ 0 ≤ ≤

o CONSERVAZIONE DEL FLUSSO

∑ − ∑ = 0 ∈ {, }

− + ()

∈ () ∈

o NULLA ESCE DA t E NULLA ENTRA IN s

∑ = ∑ = 0

− +

() ()

∈ ∈

In forma compatta si può scrivere che:

− +

()) ())

( − ( = 0, ∀ ∈ {, }

− + −

()) ()) ()) ()

{ ( − ( = ( =

− + +

()) ()) ()) ()

( − ( = −( = −

Sommando verticalmente il sistema scritto sopra si ottiene quindi che:

Ma l’insieme formato dall’unione delle stelle entranti (che deve essere uguale a quello

formato dalle stelle uscenti) è proprio l’insieme degli archi A: () ()

= =

Da cui si ricava che:

(). E quindi che il flusso uscente da “s” è uguale al flusso entrante in “t” che è uguale al flusso

x complessivo.

Il problema primale si può dunque scrivere come segue:

2. Figura 1- Riscrivendo il primale

3. (Vedi foglio dimostrazioni).

12- LOCALIZZAZIONE IMPIANTI.

1. Definire il problema di localizzazione impianti.

2. Descrivere Formulazione Forte e Debole.

3. Spiegare come si possono risolvere e che caratteristiche hanno.

4. Spiegare un possibile meccanismo di generazione vincoli.

SVOLGIMENTO:

1. I problemi di Localizzazione di Impianti derivano dai Problemi di Distribuzione dove si cerca

di ottimizzare il trasporto di beni da una o più origini in una o più destinazioni: per

ottimizzazione si intende la minimizzazione dei costi di trasporto, rispettando una serie di

vincoli (capacità dei veicoli, raggiungibilità delle destinazioni…).

E’ un problema di grande