Problemistrutturati 12

(1)

12

Problemi strutturati

12.1 INTRODUZIONE

Nei precedenti capitoli sono stati esaminati problemi di Programmazione Lin- eare e problemi di Programmazione Lineare Intera che abbiamo visto essere di fondamentale importanza all’interno della Ricerca Operativa in quanto un ele- vatissimo numero di problemi reali può essere formulato in termini di problemi di Programmazione Lineare o di Programmazione Lineare Intera. Nelle varie analisi effettuate non si è fino ad ora mai tenuto conto dell’eventualità che alcuni problemi applicativi presentino una loro struttura intrinseca, cioè delle caratteristiche particolari che possono consentire di formulare il problema in modi alternativi tali da evidenziare informazioni ulteriori sul problema derivanti da questa sua forma strutturata. Nel caso in cui un problema applicativo o, piú in generale, una classe di problemi presenti una struttura particolare, è naturale pensare che sia possibile sviluppare tecniche specifiche di soluzione che sfruttando la particolare struttura diano luogo ad algoritmi “ad hoc” che risultano molto efficienti.

Lo scopo di questo capitolo è quello di descrivere brevemente alcune classi modelli strutturati, facendo uso di uno strumento fondamentale rappresentato dai grafi. Riportiamo perciò di seguito alcune definizioni fondamentali della teoria dei grafi che permetteranno di formulare i cosiddetti problemi di ottimizzazione su grafi. Evidenzieremo come alcuni problemi già formulati in termini di problemi di Programmazione Lineare possono essere formulati in modo alternativo come problemi di ottimizzazione su grafi. Forniremo poi a titolo di esempio, la formulazione di una importante classe di problemi: il problema del cammino minimo.

Mostreremo, inoltre, come sia possibile definire un algoritmo specifico nel caso del problema del cammino minimo su grafi con particolari caratteristiche.

(2)

12.2 DUE ESEMPI “STORICI” DI MODELLI STRUTTURATI

In questo paragrafo verranno forniti due esempi che sono storicamente molto importanti e che dovrebbero fornire primi esempi di problemi strutturati che possono essere efficientemente modellati utilizzando una struttura particolare che, come vedremo, prender`a il nome di grafo.

Un primo esempio si riconduce alle origini storiche della teoria dei grafi. Infatti, esso è dovuto ad Eulero, grande matematico vissuto nel 1700, al quale viene attribuita l’introduzione del concetto di grafo. Egli viveva nella città tedesca di Könisberg la quale si trova alla confluenza di due fiumi e comprende un isolotto.

La citt`a risultava cos`ı divisa in quattro parti corrispondenti alle quattro regioni di terra che si venivano a formare (Figura 12.2.1): le due sponde (indicate con A e B), l’isolotto (indicato con C) e la parte di terra che si trova tra i due fiumi prima della confluenza (indicata con D). Queste varie parti della citt`a erano collegate da sette ponti come rappresentato nella Figura 12.2.1.

Fig. 12.2.1 I ponti della citt`a di K¨onisberg

Il problema che Eulero si poneva era quello di tracciare un percorso che, partendo da una qualsiasi delle quattro zone della citt`a, attraversi tutti i sette ponti una ed

(3)

una sola volta tutti i ponti ritornando alla fine al punto di partenza. Per risolvere questo problema, Eulero creò quello che oggi chiameremo un “modello matematico” del problema in esame facendo in modo che tutte le informazioni inerenti al problema fossero incluse nel modello stesso, e tralasciando al tempo stesso quelle informazioni che non avevano rilevanza ai fini della risoluzione del problema. A tale scopo, Eulero associò al problema una rappresentazione schematica come rappresentato nella Figura 12.2.2: ciascuna delle quattro zone della città

Fig. 12.2.2 Rappresentazione del problema ponti della citt`a di K¨onisberg

è rappresentata da un cerchio, e ciascun ponte da una linea. Questa rappresentazione è sufficiente a studiare il problema considerato; infatti essa contiene tutti gli elementi che caratterizzano il problema. È importante osservare che questa rappresentazione riflette perfettamente quanto osservato nel Capitolo 1 sulla costruzione di un modello matematico: infatti in questa rappresentazione sono incluse solo le informazioni inerenti al problema in esame mentre vengono volutamente trascurate informazioni, come la lunghezza dei ponti, la loro esatta posizione, la largezza dei fiumi, etc., che risulterebbero del tutto inessenziali ai fini della risoluzione del problema sopra enunciato. Come abbiamo avuto piú volte modo di osservare, un modello matematico che rappresenti in maniera ef- ficace una situazione reale deve avere questa capacità di estrarre dalla realtà le

(4)

caratteristiche essenziali di un problema evidenziando cos`ı solo quelle di interesse. Questa rappresentazione del problema riportata nella Figura 12.2.2 è una struttura matematica ben definita e, come vedremo nel prossimo paragrafo, pren- derà il nome di grafo. Senza entrare nei dettagli, ricordiamo che Eulero dimostrò che il problema dei ponti di Könisberg non ammette soluzione e quindi non era possibile effettuare una passeggiata che attraversando tutti i ponti una sola volta tornasse al punto di partenza. Eulero inoltre forn`ı una caratterizzazione dei grafi per i quali è possibile tracciare questo circuito (grafi euleriani).

Prima di introdurre formalmente i grafi, esaminiamo un altro esempio “storico”;

si tratta di un problema ben noto con il nome di problema dei quattro colori.

L’enunciato del problema `e molto semplice: si tratta di determinare il numero minimo di colori necessari per colorare le regioni di una qualsiasi carta geografica in modo tale che due ragioni adiacenti abbiano sempre colori diversi. Un esempio di colorazione di questo tipo fatta con quattro colori `e riportato nella Figura 12.2.3. Anche in questo caso, siamo interessati a costruire un modello

Fig. 12.2.3 Esempio di colorazione con quattro colori

matematico che permetta di studiare il problema considerato. E necessario,` cio`e rappresentare il problema con strumenti matematici adatti ad evidenziare le caratteristiche peculiari del problema stesso. Analogamente all’esempio precedente, una semplice rappresentazione pu`o essere fornita associando un cerchio ad ogni regione della mappa e collegando con una linea due cerchi corrispondenti

(5)

a due regioni adiacenti, come rappresentato nella Figura 12.2.4. Anche questa

Fig. 12.2.4 Rappresentazione del problema dei quattro colori

rappresentazione trascura elementi non essenziali a studiare il problema come, ad esempio, l’estensione delle regioni, la forma dei loro confini, etc., e mette in evidenza esclusivamente gli aspetti necessari ad analizzare il problema. La struttura utilizzata in questa rappresentazione `e la medesima dell’esempio precedente e, come vedremo del prossimo paragrafo, prende nome di grafo.

Per dare qualche informazione storica ricordiamo solo che una prima formulazione di questo problema risale alla metà del 1800 e per molti anni è stato ipotizzato che fosse possibile colorare una mappa in modo da non avere regioni adiacenti con lo stesso colore, utilizzando solamente quattro colori, ma non era stata data una dimostrazione matematica di ciò; questo è il motivo per cui, per molti decenni, questa possibilità era diffusa come la cosiddetta “congettura dei quattro colori”.

Senza entrare nei dettagli storici dei vari tentativi di dimostrazione, ricordiamo solamente che si `e dovuto aspettare il 1976 per avere una dimostrazione di quella che per decenni non poteva essere considerata niente di pi´u di una congettura.

Questi due esempi “storici” ora brevemente riassunti, mettono in evidenza come due problemi anche molto diversi fra di loro possono essere “modellati” mediante una stessa struttura che come vedremo rappresenta uno strumento essenziale e molto flessibile per la rappresentazione e la soluzione di moltissimi problemi provenienti da applicazioni reali: si tratta dei grafi.

(6)

12.3 GRAFI: DEFINIZIONI FONDAMENTALI E ALCUNE PROPRIET`A ELEMENTARI

I grafi sono delle strutture matematiche che permettono di rappresentare una relazione binaria tra gli elementi di un insieme; se la relazione non prevede un ordine tra i due elementi dell’insieme si ha un grafo non orientato, se invece prevede un ordine si ha un grafo orientato. Riportiamo ora alcuni elementi di base della teoria dei grafi ed in particolare le definizioni fondamentali che verranno utilizzate nel seguito.

12.3.1 Grafi non orientati

Definizione 12.3.1 Grafo (non orientato)

Si definisce grafo non orientato G una coppia ordinata (V, E) dove V = {v1, . . . , vn} `e un insieme finito di elementi detti nodi o vertici ed E = {e1, . . . , e_m} un insieme di coppie non ordinate di nodi dette archi o spigoli.

In un grafo non orientato ogni arco e∈ E `e completamente definito da una coppia di nodi u, v e quindi si usa la notazione e = (u, v) per identificare tale arco.

Per rappresentare graficamente un grafo non orientato, di solito, si utilizzano dei punti o dei cerchi per i nodi mentre ogni arco viene rappresentato da una linea che congiunge i nodi estremi dell’arco (Figura 12.3.1).

Fig. 12.3.1 Rappresentazione dei nodi u e v e dell’arco e = (u, v) in un grafo non orientato

Si osservi che nel caso di grafo non orientato un arco `e definito da una coppia non ordinata di nodi e quindi risulta (u, v) = (v, u).

Un esempio di rappresentazione di grafo non orientato formato da 6 nodi e 8 archi (ovvero con |V | = 6, |E| = 8)¹ `e riportato nella Figura 12.3.2. In tale grafo l’insieme dei nodi `e costituito da

V ={v1, v₂, v₃, v₄, v₅, v₆}

1Dato un insieme I, si denota con |I| la sua cardinalit`a

(7)

Fig. 12.3.2 Esempio di grafo non orientato

l’insieme degli archi `e

E = {e1, e₂, e₃, e₄, e₅, e₆, e₇, e₈}

= {(v1, v₂), (v₂, v₃), (v₃, v₄), (v₄, v₅), (v₅, v₆), (v₆, v₁), (v₆, v₂), (v₆, v₃)}.

Definizione 12.3.2 Estremi di un arco. Arco incidente. Nodi adiacenti. Archi adiacenti.

Dato un grafo non orientato G = (V, E), se e = (u, v)∈ E `e un arco, allora i nodi u e v sono detti estremi dell’arco e, inoltre si dice che l’arco e incide in u e v e i due nodi u, v ∈ G si dicono adiacenti. Due archi si dicono adiacenti se hanno un estremo in comune.

Definizione 12.3.3 Intorno e stella di un nodo. Nodo isolato.

Grado di un nodo.

Sia dato un grafo non orientato G = (V, E) e un nodo v ∈ V . Si definisce

(8)

intorno del nodo v l’insieme N (v) dei nodi adiacenti a v. Si definisce stella del nodo v l’insieme δ(v) degli archi incidenti in v. Un nodo v si dice isolato se N (v) =∅. Si definisce grado del nodo v la cardinalit`a dell’insieme δ(v).

Nella Figura 12.3.2 sono adiacenti, ad esempio, i nodi v₄ e v₅, i nodi v₆ e v₂, i nodi v4 e v3. Come esempio di archi adiacenti si hanno gli archi e1 ed e2, gli archi e₁ ed e₆, gli archi e₈ ed e₃. L’intorno del nodo v₆ `e N (v₆) = {v1, v₂, v₃, v₅} e la stella del nodo v₂, δ(v₂) ={e1, e₇, e₂}.

Definizione 12.3.4 Sottografo. Sottografo indotto.

Dato un grafo non orientato G = (V, E), si definisce sottografo di G un grafo H = (W, F ) tale che W ⊆ V e F ⊆ E. Un sottografo H = (W, F ) di G si dice sottografo indotto da W se `e tale che l’arco (u, v) appartiene a F se e solo se u, v ∈ W e (u, v) ∈ E.

Si pu`o dire che il sottografo H di G indotto da W eredita tutti gli archi di G i cui estremi sono entrambi contenuti nel sottoinsieme W .

Fig. 12.3.3 Esempio di sottografo

Nella Figura 12.3.3 è rappresentato un sottografo del grafo di Figura 12.3.2 con W = {v1, v₂, v₆}; non è un sottografo indotto in quanto non comprende l’arco e₇. Un sottografo del grafo di Figura 12.3.2 indotto da W è riportato nella Figura 12.3.4.

(9)

Fig. 12.3.4 Esempio di sottografo indotto

Definizione 12.3.5 Grafo bipartito.

Un grafo non orientato G = (V, E) si dice bipartito se `e possibile partizionare l’insieme V dei suoi nodi in due sottoinsiemi X, Y in modo tale che ogni arco di G abbia un estremo appartenente a X e l’altro a Y ².

Un esempio di grafo bipartito `e riportato in Figura 12.3.5 dove l’insieme dei nodi V ={v1, v₂, v₃, v₄, v₅, v₆, v₇} `e stato partizionato negli insiemi X = {v1, v₂, v₃, v₄} e Y ={v5, v₆, v₇} e ogni arco del grafo congiunge esattamente un nodo appartenente ad X con un nodo appartenente ad Y .

12.3.2 Grafi orientati

Definizione 12.3.6 Grafo orientato

Si definisce grafo orientato o diretto G una coppia ordinata (V, E) dove V = {v1, . . . , vn} `e un insieme finito di elementi detti nodi o vertici e da un insieme E ={e1, . . . , em} ⊆ V × V di coppie ordinate di nodi dette archi o spigoli.

Quindi in un grafo orientato, a differenza del caso di un grafo non orientato, le coppie di nodi che definiscono gli archi sono coppie ordinate; la notazione utilizzata per indicare un arco in un grafo orientato continuer`a ad essere la stessa, ma in questo caso l’arco (u, v) indica che c’`e un collegamento dal nodo u al nodo

(10)

Fig. 12.3.5 Esempio di grafo bipartito

v, ma non il viceversa. Quindi l’arco (u, v) è diverso dall’arco (v, u). Ogni arco risulta “orientato” e per rappresentare graficamente un arco orientato e = (u, v) in un grafo orientato risulta pertanto necessario inserire una freccia ad identificare l’orientamento dell’arco, ovvero qual è il primo nodo e qual è il secondo dell’arco stesso. Una rappresentazione grafica di un arco e = (u, v) in un grafo orientato è fornita nella Figura 12.3.6.

Fig. 12.3.6 Rappresentazione dei nodi u e v e dell’arco orientato e = (u, v) in un grafo orientato

Dato l’arco e = (u, v), il primo nodo u viene detto coda, il secondo nodo v viene detto testa. Il nodo u si dice anche predecessore del nodo v e il nodo v successore del nodo u. L’arco e = (u, v)∈ E si dice uscente da u ed entrante in v.

Anche nel caso di grafi orientati, dato un arco e = (u, v)∈ E, i nodi u e v sono detti estremi dell’arco e, e si dice che l’arco e incide in u e v e i nodi u e v si dicono adiacenti.

(11)

Un esempio di rappresentazione di un grafo orientato `e riportato nella Figura 12.3.7.

Ribadiamo che l’unica differenza con il caso dei grafi non orientati `e nella presenza sull’arco di una freccia che indica l’orientamento dell’arco stesso. In tale

Fig. 12.3.7 Esempio di grafo orientato

grafo l’insieme dei nodi `e costituito da

V ={v1, v₂, v₃, v₄, v₅, v₆} l’insieme degli archi `e

E = {e1, e2, e3, e4, e5, e6, e7, e8, e9}

= {(v1, v2), (v2, v3), (v3, v2), (v3, v4), (v4, v5), (v6, v5), (v6, v1), (v2, v6), (v3, v6)}.

Si osservi che risulta

e₂ = (v₂, v₃)6= (v3, v₂) = e₃ cio`e l’arco e₂ = (v₂, v₃) `e diverso dall’arco (v₃, v₂) = e₃.

Anche nel caso dei grafi orientati si possono dare le definizioni di intorno di un nodo e di stella di un nodo analogamente al caso di grafi non orientati. Inoltre

(12)

un intorno di un nodo è partizionato in intorno positivo e intorno negativo e analogamente la stella di un nodo (che nel caso orientato è indicata con ω) è partizionata in stella entrante e stella uscente. Formalmente si hanno le seguenti definizioni.

Definizione 12.3.7 Intorno positivo, intorno negativo. Stella entrante, stella uscente.

Sia dato un grafo orientato G = (V, E) e un nodo v ∈ V . Si definisce intorno positivo del nodo v l’insieme N⁺(v) dei nodi successori del nodo v e intorno negativo del nodo v l’insieme N⁻(v) dei nodi predecessori del nodo v.

Si definisce stella entrante del nodo v l’insieme ω⁻(v) degli archi incidenti in v e stella uscente ω⁺(v), l’insieme degli archi uscenti da v

Quindi N⁺(v) `e l’insieme dei nodi estremi della stella uscente di v, escluso v stesso, mentre N⁻(v) `e l’insieme dei nodi estremi della stella entrante di v, escluso v stesso. Nell’esempio di grafo orientato rappresentato nella Figura 12.3.7 si ha, ad esempio, N⁺(v3) ={v2, v6, v4} e N⁻(v3) ={v2} mentre ω⁺(v2) ={e2, e8} e ω⁻(v₂) ={e1, e₃}.

Definizione 12.3.8 Nodo sorgente. Nodo pozzo.

In un grafo orientato, un nodo con soli archi uscenti `e detto sorgente; un nodo con soli archi entranti `e detto pozzo.

Per quanto riguarda la definizione di sottografo e sottografo indotto nel caso di grafi orientati, essa è la medesima già data nel caso di grafi non orientati (Definizione 12.3.4). Anche la definizione di grafo orientato bipartito essa è la medesima già data nel caso di grafi non orientati (Definizione 12.3.5).

12.3.3 Cammini, cicli, alberi

Definizione 12.3.9 Cammino.

Sia dato un grafo G = (V, E) (orientato o non orientato), dove V = {v1, . . . , vn} e E = {e1, . . . , em}. Si definisce cammino in G, un insieme ordi-

(13)

nato e finito di nodi e archi di G,

P ={v^j0, eh₁, vj₁, eh₂, . . . , vj_p−1, ehp, vjp} tale che ogni arco e_h_i `e incidente nei nodi v_j_i−1 e v_j_i.

Si osservi che nel caso in cui G `e un grafo orientato, il cammino come definito nella definzione precedente non tiene conto dell’orientamento degli archi in quanto `e richiesto che l’arco ehi incida sui nodi vj_i−1 e vji, senza specificare quale dei due nodi sia la testa e quale la coda di e_h_i.

I nodi vj0 e vjp sono detti estremi del cammino P . Il nodo vj0 `e anche detto origine del cammino.

Definizione 12.3.10 Cammino orientato.

Sia dato un grafo orientato G = (V, E) dove V = {v1, . . . , vn} e E = {e1, . . . , em}. Si definisce cammino orientato in G, un insieme ordinato e finito di nodi e archi di G,

P ={vj0, eh₁, vj1, eh₂, . . . , vj_p−1, ehp, vjp}

tale che risulti e_h_i = (vj_i−1, vji), ovvero vj_i−1 e vji sono rispettivamente la coda e la testa dell’arco ehi.

Naturalmente l’esistenza di un cammino orientato da un nodo u ad un nodo v non implica esistenza di un cammino orientato dal nodo v al nodo u.

Definizione 12.3.11 Cammino semplice.

Un cammino [orientato] `e detto cammino [orientato] semplice se gli archi e i nodi che lo costituiscono sono tutti distinti.

Nel grafo riportato nella Figura 12.3.7 i cammini

P₁ ={v3, e₄, v₄, e₅, v₅, e₆, v₆, e₇, v₁}, P₂ ={v1, e₁, v₂, e₂, v₃, e₄, v₄}.

sono cammini semplici; un esempio di cammino non semplice `e il cammino {v2, e₈, v₆, e₇, v₁, e₁, v₂, e₂, v₃}.

(14)

Definizione 12.3.12 Cammino chiuso. Ciclo. Ciclo orientato

Dato un grafo (orientato o non orientato) G = (V, E), un cammino in G `e detto cammino chiuso se i suoi estremi coincidono. Inoltre, si definisce ciclo o circuito un cammino chiuso

C ={vj0, eh₁, vj1, . . . , vh_p−1, ehp, vj0} tale che {vj0, e_h₁, v_j₁, . . . , e_h_p−1, v_h_p−1} `e un cammino semplice.

Dato un grafo orientato, si definisce ciclo orientato un cammino orientato chiuso

C ={v^j0, eh₁, vj₁, . . . , vh_p−1, ehp, vj₀}

tale che {vj0, e_h₁, v_j₁, . . . , e_h_p−1, v_h_p−1} `e un cammino orientato semplice.

Quindi un ciclo è un cammino chiuso in cui gli archi e i nodi sono distinti ad eccezione del primo nodo che coincide con l’ultimo. Nel grafo riportato nella Figura 12.3.7 il cammino{v1, e₁, v₂, e₈, v₆, e₇, v₁} è un cammino chiuso ed è anche un ciclo orientato, mentre il cammino {v3, e₃, v₂, e₈, v₆, e₇, v₁, e₁, v₂, e₂, v₃} è un cammino chiuso ma non un ciclo perché il cammino{v3, e₃, v₂, e₈, v₆, e₇, v₁, e₁, v₂} non è semplice.

Definizione 12.3.13 Grafo connesso.

Un grafo (orientato o non orientato) si dice connesso se per ogni coppia di nodi del grafo u, v, esiste un cammino (non necessariamente orientato) che congiunge u e v.

Definizione 12.3.14 Grafo aciclico non orientato. Albero non orientato.

Un grafo non orientato `e detto aciclico se non contiene cicli come sottografi.

Inoltre si definisce albero non orientato o semplicemente albero un grafo aciclico e connesso.

(15)

Definizione 12.3.15 Albero ricoprente.

Dato un grafo connesso G = (V, E) si dice albero ricoprente di G un albero T = (W, F ) con W = V e F ⊆ E.

Un albero ricoprente è quindi un sottografo di G che contiene tutti i nodi di G e soltanto un sottoinsieme di archi ed inoltre è un albero. Il sottoinsieme degli archi F contiene tutti gli archi necessari per connettere tra loro tutti i nodi con uno e un solo cammino. Naturalmente un grafo ammette un albero ricoprente se e solo se è connesso.

Definizione 12.3.16 Grafo aciclico orientato. Alberi orientati.

Un grafo orientato `e detto aciclico se non contiene cicli orientati come sottografi. Inoltre si definisce albero orientato un grafo orientato connesso G = (V, E) aciclico in cui si distingue un nodo particolare r detto radice (albero radicato) che verifica una delle seguenti condizioni:

i) per ogni nodo v∈ G diverso da r esiste un cammino orientato da r a v;

ii) per ogni nodo v∈ G diverso da r esiste un cammino orientato da v a r;

Nel caso i) si parla di albero sorgente, nel caso ii) si parla di albero pozzo.

Si osservi che nel caso di un albero sorgente il nodo r non ha archi entranti (`e un nodo sorgente) e ogni nodo v6= r ha esattamente un arco entrante; quindi un albero sorgente `e completamente determinato specificando per ogni nodo il suo predecessore.

Analogamente nel caso di un albero pozzo il nodo r non ha archi uscenti (`e un nodo pozzo) e ogni nodo v6= r ha esattamente un arco uscente; quindi un albero pozzo `e completamente determinato specificando per ogni nodo il suo successore.

Un esempio di albero sorgente `e rappresentato nella Figura 12.3.8 e un esempio di albero pozzo `e rappresentato nella Figura 12.3.9.

(16)

Fig. 12.3.8 Esempio di albero sorgente

Fig. 12.3.9 Esempio di albero pozzo

(17)

12.3.4 Grafi pesati

Un ulteriore ampliamento del concetto di grafo consiste nell’associare ad ogni arco un numero reale che chiameremo peso. Questo d`a luogo ai cosiddetti grafi pesati che possono essere cos`ı formalmente definiti.

Definizione 12.3.17 Grafo pesato.

Un grafo pesato è una tripla ordinata G = (V, E, L) tale che ¯G = (V, E) è un grafo ed L è una funzione L : E → IR ∪ {−∞, +∞} che associa ad ogni arco (u, v) un peso ℓ_uv.

Per rappresentare un grafo pesato `e sufficiente inserire accanto a ciascun arco (u, v) il peso corrispondente ℓ_uv. Un esempio di rappresentazione di grafo pesato

`e riportato nella Figura 12.3.10.

Fig. 12.3.10 Esempio di grafo pesato

In questo esempio `e stato assegnato il peso 3 all’arco (v₁, v₂) (ovvero ℓv1,v2 = 3);

il peso 2 all’arco (v₂, v₃) (ovvero ℓv₂,v₃ = 2), etc.

(18)

Dato un grafo orientato pesato G = (V, E, L) `e possibile assegnare ad ogni cammino orientato in G un peso che verr`a chiamato peso del cammino; formalmente si ha la seguente definizione.

Definizione 12.3.18 Peso di un cammino.

Dato un grafo orientato pesato G = (V, E, L) e dato un cammino orientato P in G, si definisce ℓ(P ) peso del cammmino P la somma dei pesi degli archi che costituiscono il cammino.

Ad esempio, il cammino orientato

P ={v1, e1, v2, e2, v3, e9, v6}

nel grafo di Figura 12.3.10 ha un peso pari a ℓv₁,v₂+ ℓv₂,v₃+ ℓv₃,v₆ = 3 + 2 + 2 = 7, ovvero ℓ(P ) = 7.

12.3.5 Matrici di incidenza e loro propriet`a

Per rappresentare formalmente un grafo si pu`o fare uso di opportune matrici chiamate matrici di indicenza del grafo. Dato un grafo G = (V, E) con V = {v1, . . . vn} e E = {e1, . . . , em}, formalmente si ha la seguente definizione.

Definizione 12.3.19 Sia G = (V, E) un grafo non orientato. Si definisce matrice di incidenza di G una matrice AG tale che abbia

i) n =|V | righe (ovvero una riga per ogni nodo) ii) m =|E| colonne (ovvero una colonna per ogni arco) iii) [AG]_ij =

1 se l’arco e_j `e incidente nell’i-esimo nodo v_i 0 altrimenti.

Come esempio, si consideri il grafo non orientato di Figura 12.3.11.

La matrice di incidenza che lo rappresenta `e la seguente (dove, per chiarezza, sono indicati anche i nodi e gli archi):

e1 e2 e3 e4 e5

v₁ 1 0 0 0 1

v₂ 1 1 0 0 0

v₃ 0 0 1 0 0

v₄ 0 1 1 1 0

v₅ 0 0 0 1 1

(19)

Fig. 12.3.11 Grafo non orientato

Proposizione 12.3.20 La matrice di incidenza di un grafo (non orientato) bipartito `e totalmente unimodulare.

Dimostrazione: La dimostrazione discende immediatamente da un’applicazione del Teorema 10.5.3. Infatti gli elementi di una matrice di incidenza di un grafo non orientato sono nell’insieme {0, 1}. Inoltre ogni colonna ha esattamente due elementi non nulli. Inoltre, poiché il grafo è bipartito esiste una partizione dell’insieme dei nodi V in due insiemi che chiamiamo U e W . Ma allora la partizione degli indici di riga negli insiemi Q1 e Q2 richiesta dal Teorema 10.5.3 si può facilmente ottenere inserendo in uno (Q₁) tutti quelli corrispondenti ai nodi che stanno in U e nell’altro (Q2) quelli che stanno in W .

Per quanto riguarda i grafi orientati, la definizione di matrice di incidenza `e la seguente.

(20)

Definizione 12.3.21 Sia G = (V, E) un grafo orientato. Si definisce matrice di incidenza di G una matrice A_G tale che abbia

i) n =|V | righe (ovvero una riga per ogni nodo) ii) m =|E| colonne (ovvero una colonna per ogni arco)

iii) [AG]_ij =





−1 se l’arco ej `e uscente dall’i-esimo nodo vi

1 se l’arco ej `e entrante nell’i-esimo nodo vi

0 altrimenti.

Come esempio, si consideri il grafo orientato di Figura 12.3.12.

Fig. 12.3.12 Grafo orientato

(21)

La matrice di incidenza che lo rappresenta `e la seguente (dove, per chiarezza, sono indicati anche i nodi e gli archi):

e1 e2 e3 e4 e5

v₁ -1 0 0 0 -1

v₂ 1 -1 0 0 0

v₃ 0 0 1 0 0

v₄ 0 1 -1 1 0

v₅ 0 0 0 -1 1

Proposizione 12.3.22 La matrice di incidenza di un grafo orientato `e totalmente unimodulare.

Dimostrazione: La dimostrazione discende immediatamente da un’applicazione del Teorema 10.5.3. Infatti gli elementi di una matrice di incidenza di un grafo orientato sono nell’insieme {−1, 0, 1}. Inoltre ogni colonna ha esattamente due elementi non nulli. Per ottenere la partizione degli indici di riga negli insiemi Q₁ e Q₂ richiesta dal Teorema 10.5.3 `e sufficiente inserire in uno (Q₁) quelli di tutte le righe e porre l’altro (Q₂) coincidente con l’insieme vuoto.

(22)

12.4 CENNI SUI MODELLI DI OTTIMIZZAZIONE SU RETI

Nel paragrafo 12.2 sono stati esaminati due esempi significativi anche dal punto di vista delle origini storiche della teoria dei grafi. Alla luce dei concetti formali introdotti nel paragrafo precedente possiamo esaminare di nuovo quei due esempi costatando come, sia il problema dei ponti di K¨onisberg, sia il problema dei quattro colori possano essere formulati attraverso l’uso di grafi non orientati.

In particolare, il problema dei ponti di Könisberg è rappresentato dal grafo riportato nella Figura 12.2.2 che è un grafo non orientato G = (V, E) con quattro nodi e cinque archi in cui l’insieme dei nodi è costituito dalle quattro zone della città, ovvero V ={A, B, C, D} e l’insieme degli archi è costituito dai sette ponti.

Utilizzando il linguaggio formale della teoria dei grafi risolvere questo problema vuol dire determinare, se esiste, un cammino chiuso che passa una sola volta per ciacuno degli archi del grafo (tale cammino prende nome di ciclo euleriano). Si pu`o dimostrare che un grafo ammette un ciclo euleriano se e solo se il grafo `e connesso e ciascun nodo ha grado pari.

Anche il problema dei quattro colori `e rappresentato da un grafo non orientato (Figura 12.2.4) in cui i nodi sono associati alle regioni e gli archi collegano due nodi corrispondenti a due regioni adiacenti.

Al di l`a questi due esempi “storici”, i concetti della teoria dei grafi e gli algoritmi che si basano su di essi sono oggi molto utilizzati nell’affrontare problemi provenienti da applicazioni reali. Infatti il linguaggio della teoria dei grafi consente di rappresentare in modo semplice molti problemi reali e conseguentemente di definire metodi molto efficienti per la soluzione dei problemi stessi.

E impossibile definire una lista esaustiva di problemi che possono essere formu-` lati utilizzando il formalismo dei grafi. Una classe molto generale è costituita dai cosiddetti modelli di distribuzione di flusso a costo minimo ai quali si possono ricondurre molti problemi di interesse. Esula dallo scopo di queste note la trattazione di modelli di questo tipo. Riportiamo solamente nel paragrafo che segue una formulazione come modelli su grafo del problema dell’assegnamento e del problema dei trasporti che hanno la stessa struttura e che abbiamo già formulato in precedenza come modello di Programmazione Lineare Intera-0–1 (paragrafo 9.2.1) il primo e come modello di Programmazione Lineare (paragrafo 3.4.3) il secondo. Questo permetterà di giustificare la proprietà di interezza della soluzione già riportata nell’Osservazione 9.2.2 in riferimento al problema dell’assegnamento e nel Teorema 3.4.2 per quanto riguarda il problema dei trasporti.

12.4.1 Il problema dell’assegnamento come problema di ottimizzazione su grafi Come gi`a visto nel paragrafo 9.2.1, date n persone P1,. . . ,Pn, n lavori L1,. . . , L_n da svolgere e c_ij il costo dell’assegnamento della persona i al lavoro j, si parla di problema di assegnamento se si vuole assegnare assegnare i lavori alle persone

(23)

minimizzando il costo totale di realizzazione di tutti i lavori, tenendo conto che ciascun lavoro deve essere svolto esattamente da una persona e che ciascuna persona deve svolgere esattamente un lavoro. Tale problema si pu`o facilamente rappresentare attraverso un grafo bipartito G = (V, E) dove l’insieme dei nodi V

`e partizionato negli insiemi U e W e dove in U si collocano i nodi rappresentanti le persone e in W i nodi rappresentanti i lavori. Un arco tra un nodo i∈ U e un nodo j ∈ W rappresenta l’assegnamento della persona i-esima al j-esimo lavoro.

A questo punto introducendo le variabili binarie xij ∈ {0, 1} con il medesimo significato del paragrafo 9.2.1, ovvero

xij =

1 se la persona i `e assegnata al lavoro j 0 altrimenti,

si avr`a una variabile per ogni arco del grafo bipartito. All’ottimo, le variabili pari ad 1 indicheranno quali archi fanno parte dell’assegnamento ottimo.

Ora, se indichiamo con A_G la matrice di incidenza di questo grafo bipartito, i vincoli del problema dell’assegnamento possono essere riscritti nella forma

A_Gx = 1.

Poich`e per la Proposizione 12.3.20 tale matrice AG `e totalmente unimodulare, per il Teorema 12.4 il poliedro

P ={x ∈ IRⁿ: AGx = 1, x≥ 0}

ha tutti i vertici interi. Questo giustifica la propriet`a di interezza enunciata nell’Osservazione 9.2.2.

In maniera del tutto analoga, si pu`o riformulare il problema dei trasporti e anche in questo caso, attraverso la totale unimodularit`a della matrice di incidenza, si giustifica il teorema sull’interezza della soluzione (Teorema 3.4.2).

Queste brevi ma importatissime considerazioni, in realt`a si applicano ad un’ampia classe di problemi. Per ogni approfondimento si rimanda alla letteratura specifica.

(24)

12.5 IL PROBLEMA DEL CAMMINO MINIMO

In questo paragrafo studiamo il problema del cammino minimo, come esempio di una classe di problemi che si possono formulare anche attraverso un modello di Programmazione Lineare Intera, ma che, sfruttando la struttura che essi presen- tano, possono essere alternativamente formulati come problemi di ottimizzazione su grafi. Come vedremo, questo permette di definire algoritmi di soluzione “ad hoc” basati sulla struttura del grafo.

Le applicazioni reali nelle quali `e richiesto di risolvere problemi di cammini minimi sono molto numerose. Ne citiamo di seguito alcune come esempio:

• instradamento di veicoli

• ottimizzazione del traffico su reti di trasporto

• ottimizzazione del traffico su reti di telecomunicazione

• problemi di elaborazione dei segnali

• problemi di allocazione temporale di attivit`a

• problemi di gestione dei progetti.

Formalmente il problema del cammino minimo pu`o essere enunciato nel modo seguente.

Problema del cammino minimo

Dato un grafo orientato pesato G = (V, E, L) e dati due nodi s∈ V e t ∈ V , determinare un cammino orientato P^∗ in G da s a t di peso minimo.

Si osservi che (i) se non esiste un cammino orientato da s a t in G, il problema non ha soluzioni ammissibili; (ii) se esiste un ciclo orientato in G di peso negativo la soluzione del problema è illimitata (poiché conterrà tale ciclo ripetuto un numero illimitato di volte).

Per questo, nella trattazione del problema supporremo che siano soddisfatte le seguenti due assunzioni:

A1: il grafo G contiene un cammino orientato da s a tutti gli altri nodi del grafo;

A2: il grafo G non contiene cicli orientati di peso negativo.

L’assunzione A1 non è restrittiva poiché se esistessero in G nodi i che non fossero raggiungibili da s, è sufficiente aggiungere al grafo un arco fittizio (s, i) di peso molto alto. L’assunzione A2 in realtà è limitativa, ma si rende necessaria per garantire che il problema non sia illimitato inferiormente. Si tenga presente che

(25)

esistono algoritmi che posso individuare efficientemente la presenza in un grafo di cicli orientati di peso negativo.

Ora vediamo preliminarmente come sia possibile formulare il problema del cammino minimo come problema di Programmazione Lineare Intera associando una variabile booleana xij ad ogni arco (i, j)∈ E. In particolare un modello lineare pu`o essere cos`ı costruito:

– Variabili. Si definiscono le variabili booleane xij =

1 se (i, j)∈ P 0 altrimenti

Il vettore x∈ R^m si chiama vettore di incidenza del cammino P . – Funzione obiettivo. La funzione obiettivo `e il peso del cammino:

X

(i,j)∈E

c_ijx_ij.

– Vincoli. I vincoli devono imporre che la soluzione corrisponda al vettore di incidenza di un cammino semplice da s a t, cio`e:

• in ciascun nodo k che non sia s o t deve essere X

(i,k)∈ω⁻(k)

x_ik− X

(k,j)∈ω⁺(k)

x_kj = 0 per ogni k∈ V − {s, t}

• per il nodo s si abbia un solo arco uscente e per il nodo t si abbia un solo arco entrante:

X

(i,k)∈ω⁻(k)

xik− X

(k,j)∈ω⁺(k)

xkj =

+1 se k = t

−1 se k = s

Questa formulazione permette quindi di determinare la soluzione ottima del problema risolvendo un problema di Programmazione Lineare Intera. Vedremo nel seguito come invece sia possibile sfruttare la struttura del problema per definire un algoritmo specifico.

In termini pi`u generali, la formulazione appena riportata si inquadra nel contesto dei cosidetti problemi di flusso a costo minimo la cui trattazione esula dallo scopo di queste note.

12.5.1 Alcune propriet`a dei cammini minimi

Riportiamo di seguito alcuni risultati teorici importanti relativi ai cammini minimi. Nel seguito, per brevit`a di notazione, indicheremo un cammino elencando solamente i nodi del cammino, omettendo l’indicazione degli archi.

(26)

Il primo risultato riporta una semplice propriet`a riguardante i sottocammini di un cammino minimo.

Proposizione 12.5.1 Se Pr ={s, v^j1, vj₂, . . . , vjr} `e un cammino minimo dal nodo s al nodo vjr, allora il cammino Pq={s, vj1, vj2, . . . , vjq} con q ≤ r `e un cammino minimo da s a v_j_q.

Dimostrazione: La dimostrazione procede per assurdo. Infatti, se per assurdo esistesse un nodo v_j_p con p < r tale che P_p = {s, vj1, v_j₂, . . . , v_j_p} non `e un cammino minimo da s a vjp, allora si potrebbe trovare un cammino P_p^′ da s a v_j_p tale che ℓ(P_p^′) < ℓ(P_p), ovvero di peso inferiore. Ma allora il cammino ottenuto come concatenazione dei cammini P_p^′ e {v^jp+1, . . . vjr} darebbe luogo ad un cammino P_r^′ = P_p^′ ∪ {vjp+1, . . . v_j_r} tale che ℓ(Pr^′) < ℓ(P_r) e questa `e una contraddizione.

Teorema 12.5.1 Sia G un grafo orientato pesato privo di cicli orientati di peso negativo. Allora esiste un albero T = (V, E_T) con le seguenti propriet`a:

i) T `e un albero ricoprente di G.

ii) T `e un albero sorgente radicato in s.

iii) Ogni cammino orientato in T dal nodo s ad un nodo vi corrisponde ad un cammino minimo da s a v_i in G.

Omettiamo per brevità la dimostrazione di quetso teorema. L’albero la cui esistenza è garantita dal precedente teorema prende nome di albero dei cammini minimi. Mostrare l’albero dei cammini minimi costituisce il modo più sintetico e immediato di esibire una soluzione del problema dei cammini minimi da s ad ogni altro nodo del grafo. Ovviamente, fissati s in G possono esistere alberi dei cammini minimi distinti.

(27)

Nello studio del problema dei cammini minimi e nella definizione degli algoritmi risolutivi si introduce un’etichetta π(vi) per ogni nodo vi del grafo per indicare il peso di un cammino dal nodo s al nodo vi (non necessariamente quello minimo).

Tale etichetta prende nome di etichetta distanza. Ovviamente, per definizione si pone π(s) = 0.

Il teorema che segue esprime una condizione necessaria e sufficiente di ottimalit`a per le etichette distanza di un cammino minimo. Per ogni arco (vi, vj) ∈ E, continuiamo a denotare con lv_iv_j il peso dell’arco.

Teorema 12.5.2 Condizione di ottimalit`a.

Sia G un grafo orientato pesato privo di cicli orientati di peso negativo. Per ogni nodo vj ∈ V sia π(vj) un’etichetta distanza associata. Allora le π(vj), j = 1, . . . ,|V | rappresentano il peso del cammino minimo da s a vj se e solo se

π(v_j)≤ π(vi) + l_v_i_v_j (12.5.1) per ogni arco (vi, vj)∈ E.

Dimostrazione: Iniziamo con la condizione sufficiente. Per assurdo sia vjp un nodo per il quale risulti π(vjp) strettamente maggiore del peso del cammino minimo Pp = {s, vj1, vj2, . . . , vjp}. Per la Proposizione 12.5.1, il sottocammino Pq ={s, v^j1, vj₂, . . . , vjq} con q ≤ p `e un cammino minimo da s a v^jq. Sia ora vjr

il primo nodo del cammino Pp per il quale si abbia π(vjr) > ℓ(Pr). Quindi deve risultare π(vj_r−1) = ℓ(P_r−1). Ma allora si avrebbe

ℓ(Pr) = ℓ(Pr−1) + lv_jr−1vjr = π(vj_r−1) + lv_jr−1v_jr ≥ π(vjr) > ℓ(Pr) e questa `e una contraddizione.

Per dimostrare la condizione necessaria, supponiamo che per ogni vj ∈ V le etichette π(vj) rappresentino il peso di un cammino minimo da s a vj, e che per assurdo esistano due nodi vjpe vjqper i quali si ha π(vjq) > π(vjp)+lv_jpv_jq. Poiché si è supposto che tutte le etichette rappresentano il peso di un cammino minimo da s, allora deve esistere un cammino orientato da s a vjp di peso π(vjp). Ma allora esisterà un cammino orientato da s a vjqdi peso π(vjp)+lv_jpv_jq strettamente minore di π(vjq) e questo è una contraddizione.

(28)

La maggior parte degli algoritmi per la determinazione dei cammini minimi fa uso della condizione (12.5.1) si basa un schema di questo tipo:

• Inizializzazione

Si inizializzano le etichette distanza π(vi) per ogni vi∈ V

• Iterazione generica

Finch´e esiste una coppia di nodi v_i, v_j per i quali π(v_j) > π(v_i) + l_v_i_v_j si pone

π(v_j) = π(v_i) + l_v_i_v_j,

ovvero si aggiornano iterativamente le etichette fino al soddisfacimento della condizione (12.5.1).

Ad ogni iterazione dell’algoritmo, ad ogni insieme di etichette distanza pu`o essere associato un albero ricoprente di cammini che viene rappresentato specificando per ogni nodo vi il suo predecessore che viene indicato con pred[vi]. Come gi`a visto, specificando il predecessore di ogni nodo si ha la completa determinazione di un albero sorgente.

Esaminiamo di seguito uno degli algoritmi basati su uno schema di questo tipo che pu`o essere applicato ad una particolare classe di grafi orientati pesati, ovvero ai grafi con tutti i pesi positivi o nulli. Si tratta dell’algoritmo di Dijkstra.

12.5.2 L’algoritmo di Dijkstra

L’algoritmo di Dijkstra permette di risolvere il problema del cammino minimo fra due nodi qualora tutti i pesi degli archi siano positivi o nulli. Più precisamente, l’algoritmo calcola il peso del cammino minimo da un nodo dato a tutti gli altri nodi del grafo. Per semplicità i nodi saranno etichettati con un numero intero progressivo, e cioè V = {1, . . . , n}, e i pesi dei cammini verranno calcolati dal nodo 1 a tutti gli altri nodi. Il peso di un cammino minimo dal nodo 1 al nodo i verrà indicato con π^∗(i) (notare che potrebbero esistere diversi cammini minimi da 1 a i, tutti di uguale peso). L’algoritmo termina in n− 1 iterazioni. A ogni iterazione, l’insieme dei nodi è partizionato in due sottoinsiemi, S e T . L’insieme S contiene il nodo 1 e tutti i nodi per cui è già stato trovato il peso del cammino minimo; in T ci sono i restanti nodi. A ogni iterazione l’algoritmo sposta un nodo da T a S. L’esecuzione termina quando T è vuoto.

(29)

ALGORITMO DI DIJKSTRA

• Inizializzazione

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

π(i) =

l_1i se i∈ N⁺(1) +∞ altrimenti pred[i] = 1, i = 2, . . . , n.

• Iterazione generica

Assegnazione etichetta permanente

Passo 1: 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

Passo 4: 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

Quando il nodo i riceve l’etichetta permanente passando dall’insieme T all’insieme S, il valore dell’etichetta π(i) corrisponde al peso del cammino minimo dal nodo 1 a i, ovvero si ha π(i)^∗.

Si osservi che il Passo 4 `e equivalente alla seguente istruzione:

si pone π(i) = min(π(i), π(j) + lji), per ogni i∈ T ∩ N⁺(j).

Riportiamo di seguito alcune propriet`a delle etichette distanza calcolate dall’algoritmo di Dijkstra. Per far questo abbiamo bisogno di aggiungere alle etichette l’indice delle iterazioni dell’algoritmo che denoteremo con k, ovvero π^k(j) de- noter`a il valore dell’etichetta distanza associata al nodo j all’iterazione k−esima dell’algoritmo.

(30)

Proposizione 12.5.2

1) L’etichetta provvisoria assegnata ad un ciascun nodo `e non crescente all’aumentare delle iterazioni dell’algoritmo.

2) L’etichetta permanente assegnata ad ogni iterazione `e non decrescente all’aumentare delle iterazioni dell’algoritmo.

Dimostrazione: La propriet`a 1) discende immediatamente dal fatto che ogni volta che l’etichetta provvisoria di un nodo viene aggiornata, essa decresce.

La proprietà 2) si può dimostrare per assurdo. Infatti, supponiamo per assurdo che esista almeno una iterazione dell’algoritmo in cui l’etichetta permanente assegnata sia strettamente minore di quella assegnata all’iterazione precedente, e sia k la prima iterazione in cui questo accade. Se supponiamo che i e j siano i nodi selezionati rispettivamente all’iterazione k− 1 e all’iterazione k dell’algoritmo, risulterà quindi π^k(i) > π^k(j). Poichè π^k−1(i) = π^k(i), si avrà

π^k−1(i) > π^k(j). (12.5.2) Ora, poiché all’iterazione k− 1 è stato selezionato il nodo i, allora deve essere π^k−1(i) ≤ π^k−1(j) e utilizzando la (12.5.2) si ha π^k−1(j) > π^k(j). Ma questo vorrebbe dire che l’etichetta j è stata aggiornata all’iterazione k − 1, ovvero π^k(j) = π^k−1(i) + lij < π^k−1(i) e questa è una contraddizione essendo lij ≥ 0 per ogni (i, j)∈ E per ipotesi.

Riportiamo infine il teorema che garantisce che l’algoritmo di Djikstra determina i cammini minimi.

Teorema 12.5.3 Quando l’algoritmo di Dijkstra termina, il valore di ciascuna etichetta distanza π(i), per i = 1, . . . , n rappresenta il peso di un cammino minimo dal nodo sorgente s = 1 al nodo i.

Dimostrazione: E sufficiente dimostrare che alla fine dell’algoritmo le etichette` distanza soddisfano la condizione di ottimalità del Teorema 12.5.2, ovvero la (12.5.1). Supponiamo per assurdo che esistano due nodi p e q per i quali si ha π(q) > π(p)+l_pq. Poiché, per ipotesi, l_pq≥ 0, allora risulterà π(q) > π(p). Quindi per il punto 2) della Proposizione 12.5.2, il nodo p deve essere entrato nell’insieme S in un’iterazione k precedente all’iterazione in cui il nodo q è entrato in S. Ma allora, alla fine dell’iterazione k si ha la seguente situazione

p∈ S e q ∈ T ∩ N⁺(p),

(31)

ed inoltre l’etichetta π(p) è diventata permanente e quindi non sarà più modifi- cata. Per il punto 1) della Proposizione 12.5.2, l’etichetta provvisoria del nodo q non può crescere all’aumentare delle iterazioni e quindi risultando π(q) >

π(p) + lpq all’ultima iterazione, quest’ultima disuguaglianza deve valere anche all’iterazione k. Quindi, all’iterazione k, essendo stato selezionato il nodo p, l’etichetta del nodo q viene aggiornata ponendo π(q) = π(p) + lpq e questa `e una contraddizione.

Esaminiamo ora un esempio di applicazione dell’Algoritmo di Djikstra.

Esempio 12.5.3 Dato il grafo di Figura 12.5.1, trovare il peso dei cammini minimi dal nodo s a tutti gli altri nodi del grafo (il peso associato a ciascun arco

`e mostrato in figura in prossimit`a dell’arco stesso).

Fig. 12.5.1 Grafo dell’Esempio 12.5.3

Soluzione.

• Iterazione 0

S ={s}, T ={1, 2, 3, 4, 5}

(32)

π(s) = 0 π(1) = 2 π(2) = 7 π(3) = 1 π(4) = +∞ π(5) = +∞

pred[1] = s pred[2] = s pred[3] = s pred[4] = s pred[5] = s

• Iterazione 1

mini∈T π(i) = π(3) = 1, j = 3 (etichetta permanente) S ={s, 3}, T ={1, 2, 4, 5}

T∩N⁺(3) ={2}, π(2) = π(3)+l₂₃= 5, pred[2] = 3 (etichetta provvisoria)

• Iterazione 2

mini∈T π(i) = π(1) = 2, j = 1 (etichetta permanente) S ={s, 3, 1}, T ={2, 4, 5}

T∩N⁺(1) ={4}, π(4) = π(1)+l₁₄= 5, pred[4] = 1 (etichetta provvisoria)

• Iterazione 3

mini∈T π(i) = π(2) = π(4) = 5, j = 2 o j = 4 Scegliamo j = 2 (etichetta permanente)

S ={s, 3, 1, 2}, T ={4, 5}

T∩N⁺(2) ={4, 5}, π(5) = π(2)+l₂₅ = 11, pred[5] = 2 (etichetta provvisoria)

• Iterazione 4

mini∈T π(i) = π(4) = 5, j = 4 (etichetta permanente) S ={s, 3, 1, 2, 4}, T ={5}

T∩ N⁺(4) =∅.

• Iterazione 5

mini∈T π(i) = π(5) = 11, j = 5 (etichetta permanente) S ={s, 3, 1, 2, 4, 5}, T =∅

STOP

Una comoda rappresentazione delle iterazioni dell’algoritmo `e data dalla seguente tabella:

(33)

1 2 3 4 5

Iterazione 0 π(i) 2 7 1 +∞ +∞

pred[i] s s s s s

Iterazione 1 π(i) 2 5 +∞ +∞

pred[i] s 3 s s

Iterazione 2 π(i) 5 5 +∞

pred[i] 3 1 s

Iterazione 3 π(i) 5 11

pred[i] 1 2

Iterazione 4 π(i) 11

pred[i] 2

Possiamo ora facilmente fornire la soluzione dell’esercizio costruendo l’albero dei cammini minimi calcolato dall’algoritmo di Djikstra (Figura 12.5.1).

Fig. 12.5.2 Albero dei cammini minimi dell’Esempio 12.5.3

(34)

(35)

Sommario

Prefazione iii

1 Introduzione 1

1.1 Che cosa `e la Ricerca Operativa 1

1.2 Breve storia della Ricerca Operativa 2

1.3 La Ricerca Operativa oggi 3

1.4 L’approccio modellistico 7

1.5 Modelli della Ricerca Operativa 8

1.5.1 Costruzione di un modello matematico 10 1.5.2 Vantaggi dell’approccio modellistico 11 1.5.3 Critiche all’approccio modellistico 11

2 La Programmazione Matematica 13

2.1 Problemi di Ottimizzazione 13

2.1.1 Definizioni fondamentali 14

2.1.2 Classificazione dei problemi di Ottimizzazione 14 2.2 Problemi di Programmazione Matematica 15

2.3 Modelli di Programmazione Matematica 17

2.3.1 Esempi di modelli di Programmazione Matematica 18

3 Modelli di Programmazione Lineare 25

(36)

3.1 Generalit`a 25 3.2 Struttura di un modello di Programmazione Lineare 26 3.3 Generalit`a sui modelli di Programmazione Lineare 28 3.4 Classi di modelli di Programmazione Lineare 29 3.4.1 Modelli di allocazione ottima di risorse 30

3.4.2 Modelli di miscelazione 46

3.4.3 Modelli di trasporto 55

4 Il linguaggio di modellizzazione algebrica AMPL 61

4.1 Installazione e avvio di AMPL 62

4.2 Un primo esempio 63

4.3 I solutori 66

4.4 Alcuni esempi di modelli di Programmazione Lineare 67

4.5 Gli insiemi e i parametri in AMPL 71

4.5.1 Gli insiemi 75

4.5.2 I parametri 78

4.5.3 Le variabili 80

4.5.4 La funzione obiettivo e i vincoli 81

4.5.5 Le espressioni 83

4.5.6 Due esempi di modelli di Programmazione Lineare 85

4.6 I principali comandi AMPL 101

4.6.1 Il comando option 101

4.6.2 Il comando display 103

4.6.3 Reindirizzamento dell’output dei comandi 104 4.6.4 Il comando displayper visualizzare altre grandezze

relative alle variabili all’ottimo 104 4.6.5 Comandi per aggiornare il modello: reset, drop e

restore 105

4.6.6 Altri utili comandi: show, xref, expand 106 4.6.7 Nomi generici per variabili, vincoli, e funzioni

obiettivo 106

5 La Programmazione Lineare 109

5.1 Introduzione 109

5.2 Struttura di un problema di Programmazione Lineare 110 5.3 Interpretazione geometrica di un Problema di Programmazione

Lineare 111

(37)

5.3.1 Rappresentazione di vincoli lineari 111 5.3.2 Rappresentazione di funzioni obiettivo lineari 114

5.3.3 Esempi di risoluzione grafica 115

6 Teoria della Programmazione Lineare 127

6.1 Elementi di geometria in IRⁿ 127

6.1.1 Rette, semirette, segmenti 127

6.1.2 Insiemi Convessi 129

6.1.3 Vertici 133

6.1.4 Caratterizzazione dei vertici dell’insieme ammissibile

di un problema di PL 133

6.2 Il Teorema fondamentale della Programmazione Lineare 143

7 Il metodo del simplesso 149

7.1 La forma standard 151

7.2 Vertici e soluzioni di base 154

7.3 Introduzione al metodo del simplesso 167

7.4 La Fase II del metodo del simplesso 169

7.4.1 Criterio di ottimalit`a 170

7.4.2 Criterio di illimitatezza 173

7.4.3 Determinazione di una nuova base ammissibile 174 7.4.4 Calcolo della nuova matrice^]B⁻¹]N e del nuovo

vettore^]B⁻¹b: operazione di pivot 179 7.4.5 Struttura dell’algoritmo ed esempi 184 7.4.6 Convergenza del metodo del simplesso 193

7.5 La Fase I del metodo del simplesso 197

7.5.1 Ammissibilit`a del problema originario 198 7.5.2 Individuazione di una matrice di base ammissibile

B del problema originario e determinazione della

matrice B⁻¹N ed del vettore B⁻¹b 200

7.5.3 Esempi 206

8 La dualit`a nella Programmazione Lineare 221

8.1 Teoria della dualit`a 221

8.1.1 Risultati fondamentali della teoria della dualit`a 226 8.1.2 Condizioni di complementarit`a 231

8.2 Interpretazione della Dualit`a 238

(38)

8.2.1 Interpretazione economica della dualit`a e prezzi

ombra 238

9 Modelli di Programmazione Lineare Intera 251 9.1 Variabili intere per rappresentare quantit`a indivisibili 251 9.2 Variabili binarie per rappresentare scelte alternative 252

9.2.1 Problemi di assegnamento 252

9.2.2 Problemi di Knapsack binario 260

9.2.3 Problemi di “Capital Budgeting” (pianificazione

degli investimenti) 261

9.3 Variabili binarie come variabili indicatrici 264

9.3.1 Problema del costo fisso 268

9.3.2 Problemi di “lot sizing” (gestione della scorte) 273 9.3.3 Problemi di localizzazione di impianti 275 9.4 Variabili binarie per indicare il soddisfacimento di vincoli

disgiuntivi 280

9.4.1 Problemi di “scheduling” (sequenziamento) 280

10 Teoria della Programmazione Lineare Intera 285

10.2 Preliminari 288

10.3 Relazioni tra Programmazione Lineare Intera e

Programmazione Lineare 289

10.4 Formulazioni lineari di problemi di Programmazione

Lineare Intera 290

10.5 Propriet`a di interezza e totale unimodularit`a 296

11 Metodi generali per la soluzione di problemi di PLI 301

11.1 Enumerazione totale 302

11.2 Soluzione approssimata per arrotondamento 302

11.3 La tecnica del “Branch and Bound” 303

11.3.1 Il problema del knapsack binario. 314

12 Problemi strutturati 323

12.2 Due esempi “storici” di modelli strutturati 324 12.3 Grafi: definizioni fondamentali e alcune propriet`a

elementari 328

(39)

12.3.1 Grafi non orientati 328

12.3.2 Grafi orientati 331

12.3.3 Cammini, cicli, alberi 334

12.3.4 Grafi pesati 339

12.3.5 Matrici di incidenza e loro propriet`a 340 12.4 Cenni sui modelli di Ottimizzazione su reti 344

12.4.1 Il problema dell’assegnamento come problema di

ottimizzazione su grafi 344

12.5 Il problema del cammino minimo 346

12.5.1 Alcune propriet`a dei cammini minimi 347

12.5.2 L’algoritmo di Dijkstra 350