Teoria ed esercizi esame di Ottimizzazione combinatoria

La sommatoria degli archi in uscita è = alla sommatoria degli archi in ingresso v è il flusso

massimo, quello che risulta dall’operazione di aggiunta dei nodi d’ingresso e di uscita.

PROBLEMA DEL FLUSSO MASSIMO: ALGORITMI

A+ è il SOTTINSIEME in cui ho il PERCORSO I-J che va verso t (j, la parte di arrivo, è nel sottinsieme Nt)

A- è il “”” “”” in cui ho il PERCORSO J I che va verso s, (il contrario).

Per ogni taglio, IL FLUSSO CHE HO IN A+ - FLUSSO CHE VA IN A-, mi dà il FLUSSO TOTALE DEL

→

PERCORSO (il delta) v è sempre minore o uguale del flusso in avanti verso la fine del grafo.

La prima quantità è detta FLUSSO DEL TAGLIO (NS,NT) (quella con la differenza di sommatorie per

intenderci) e viene indicata come

;

La seconda quantità è detta CAPACITA’ DEL TAGLIO (NS,NT) e si indica con:

Il grafi residuo è quel grafo che si trova dalla differenza tra il grafo e le sue capacità e il flusso (con le

sue xij, ovvero la “potenza” del flusso).

ALGORITMO DI FORD FULKERSON:

Problema di flusso massimo - Algoritmo di Ford Fulkerson - YouTube

https://www.youtube.com/watch?v=VbeTl1gG4l4

ALGORITMO DI EDMOND KARPS:

ALGORITMO DI GOLDBERG-TARJAN

PROBLEMA DEL FLUSSO DI COSTO MINIMO

GEOMETRIA DELLA PROGRAMMAZIONE LINEARE

ESERCIZI di PROGRAMMAZIONE LINEARE

MINIMIZZAZIONE DEI COSTI

COSTRUIAMO LA TABELLA DEI VINCOLI

Dovendo trasportare 800 persone, si può dire che:

FUNZIONE OBIETTIVO PUO’ ESSERE DEFINITA COME:

dobbiamo minimizzare questo costo

TRASFORMIAMO IL PROBLEMA IN UN INSIEME DI EQUAZIONI E DISEQUAZIONI

*si deve minimizzare la funzione z

*si possono semplificare le prime due disequazioni dei vincoli.

→

Si costruiscono le rette di ogni vincolo per le disequazioni, basta trasformarle in equazioni e

vedere, ponendo x = 0 e y = 0, dove intersecano gli assi.

Dato che abbiamo maggiore uguale dobbiamo CONSIDERARE LA PARTE DI PIANO CHE STA SOPRA LA

RETTA. In caso contrario, TUTTO CIO’ CHE STA SOTTO.

TROVO LA REGIONE AMMISSIBILE

Zona in cui tutti i valori rispettano i vincoli.

Quindi, sappiamo che il max o il min si trovano sul bordo della regione ammissibile.

D è il punto che prevede il massimo numero di aerei a disposizione

TROVIAMO LE COORDINATE DEI VERTICI

In questo caso, la x esprime il n di aerei di tipo A, mentre y quelli di b. →

Trovo A mettendo A SISTEMA LE DUE RETTE DI CUI E’ IL PUNTO DI INTERSEZIONE trovo le sue

→

coordinate A prevede l’utilizzo di 1 aereo di tipo A e 8 di tipo B

Continuando si trova:

ORA SI USA LA FUNZIONE OBIETTIVO:

MASSIMIZZAZIONE DI PROFITTO

→

Quelli a destra sono i vincoli devo massimizzare la funzione obiettivo, ovvero i guadagni

Per costruire la regione ammissibile RAPPRESENTO I VINCOLI SUL PIANO CARTESIANO:

COORDINATE DEI VERTICI:

Si mettono a sistema le diverse equazioni che generano questi punti

SI PUO’TROVARE LA SOLUZIONE USANDO LA RETTA PARALLELA ALLA FUNZIONE OBIETTIVO:

per trovare la parallela basta isolare la y senza tener conto della z.

mi trovo la RETTA PARALLELA CHE TOCCA IL PUNTO MASSIMO

soluzione ottima

UN ALTRO MODO E’ CERCARLA NEI VERTICI: →

sostituisco le coordinate dei vertici alla funzione obiettivo anche qui mi trovo il pto 20 60 che mi

fornisce il valore massimo.

METODO DEL SIMPLESSO

C lo ricaviamo dalla funzione obiettivo (dai coefficienti); A dai vincoli; b dai vincoli; x dal numero di

variabili.

INVERSA DELLA MATRICE A prendendo solo le righe {1,2}, date come basi dalla traccia dell’esercizio

→ →

presi b delle righe {1,2} moltiplicare INVERSA DI A(B1) * b(B1).

ESERCIZIO 2

B1 è formato dalle righe della prima riga dei vincoli (x>= 0, y>= 0, z>=0), che in forma normale vanno

trasformate in <=.

Prendo la matrice risultante da B, e faccio l’INVERSO * b (l’insieme delle b riferite ai vincoli presi da b

→ 0,0,0).

Trovo h

il primo valore = alla COLONNA HESIMA DELL’INVERSA DI A cambiata di segno;

An1 è la matrice formata dai valori che non ho preso come base all’inizio (Ni)

IN caso di più valori →

prendo i POSITIVI e faccio valore b – matrice dei 2 valori in Ani * bi scelgo il minimo.

ESERCIZIO 3

EXCURSUS SULLA MATRICE INVERSA

INVERSA 2X2 →

1) TROVO DETERMINANTE facendo prodotto elementi in diagonale – l’altro prodotto il det !=0,

quindi matrice invertibile; →

2) trovo matrice dei COFATTORI cofattore di un valore è il numero che resta se levo TUTTA LA RIGA

→

E TUTTA LA COLONNA DEL VALORE INIZIALE se il valore iniziale è in pos dispari, devo cambiarlo di

segno (tipo a11 è pari; a21 a12 a32 a41 sono tutte posizioni dispari, in quanto la somma tra la

posizione verticale e orizzontal è un n dispari).

→

3) CALCOLO TRASPOSTA DELLA MATRICE COF le righe diventano colonne, e viceversa;

4) MOLTIPLICO LA TRASPOSTA DI COF * 1/DETERMINANTE.

MATRICE 3X3

DETERMINANTE PER LE 3X3

1) AGGIUNGI COLONNE = ALLE PRIME DUE;

2) TRACCIAMO LE DIAGONALI DA SX A DX E DA DX A SX

3)SOMMIAMO I PRODOTTI DEI VALORI DELLE TRE DIAGONALI SD e DS

ESERCIZI MODELLIZZAZIONE 1)

ESERCIZIO 2

ESERCIZIO 3

ESERCIZIO 4

6x + 3y >= 30

2x + 8y >=24

min 100y + 50x

METTIAMO IL PROBLEMA IN FORMA STANDARD

1) devo TRASFORMARE LA FUNZIONE OBIETTIVO IN UNA DI MINIMO, moltiplicando *-1;

→

2) devo trasformare in = le disequazioni se ho <= AGGIUNGO UNA VARIABILE S per far arrivare

al valore; se >= sottraggo.

ESERCIZI DI RETI

breve recap: →

avendo 4+2+1 in ingresso (source) dovrò averlo anche in uscita (sink) 7 è il MAX FLOW.

L’”Augmenting path” è qualsiasi path che va da s a t e che ha tutti gli edge (i collegamenti) non

→

pieni se io posso “aumentare il flusso” (esempio 3 collegamenti fatti così: 1/13 – 4/14 – 7/8).

Qui posso aumentare (Augmenting = aumentante) il flusso di 1 per toccare il massimo (dopo avrei

8/8).

Per bottleneck, si intende quella situazione per cui un edge LIMITA IL FLUSSO, in quanto la sua

capacità è minore di quelle degli edge dell’AP →sappiamo

Usando il bottleneck abbiamo aumentato il flow che, sicuramente, da 0 a 6 non

abbiamo intasi, in quanto il minimo “tubo” può prendere al massimo 6.

→

l’aumento fatto così non massimizza il flusso per farlo usiamo anche i RESIDUAL EDGES, con cui

→

diminuiamo il flow questo serve per RIASSESTARE IL TIRO, per fare l’“UNDO” delle nostre scelte.

Il RESIDUAL GRAPH è il grafo contenente anche i residual edges:

D’ora in poi, ci si riferirà a questo grafo quando si parlerà di “grafo” generico.

FORD FULKERSON, in breve, CERCA TUTTI I BOTTLENECK POSSIBILI, iterando ogni volta diversi

→

Augmenting paths, e LI SOMMA la SOMMA BOTTLENECK = MAX FLOW

Mantenendo la condizione di prima (bottleneck 6), abbiamo un secondo possibile augmenting

path, il cui bottleneck è S1. In questo caso, IL BOTTLENECK E’ 4 (NON 10), IN QUANTO SI DEVONO

USARE LE CAPACITA’ RESIDUE.

POSSIAMO SFRUTTARE I FLUSSI AL CONTRARIO.

Avendo usato path già usati, LI AGGIORNIAMO.

NON POSSIAMO PIU’ TROVARE AUGMENTING PATH (partendo da s, entrambe le vie percorribili

sono piene).

20 è il max flow.

Il FORD FULKERSON è molto inefficiente, in quanto si tratta di “andare a tentoni”. Per ottimizzare si

usa l’EDMONDS KARP.

Time complexity di FF è O(Ef), dove E è il n di edges e f è il max flow.

Time complexity di EK NON DIPENDE DALLE CAPACITY.

EK trova il PIU’ PICCOLO PATH.

Usiamo EK per torvare il MAX FLOW:

Abbiamo raggiunto il SINK. Ora troviamo il PATH PIU’ CORTO. In questo caso, sono tutti linghi

→

uguali, per cui facciamo finta che quello sotto arrivi prima degli altri abbiamo trovato lo

SHORTEST AUGMENTING PATH.

Ora troviamo il BOTTLENECK DEL AP:

RIFACCIAMO LA STESSA ROBA DELL’INIZIO:

Non posso andare nell’edge in basso.

Esiste ancora un augmenting path (quello sopra), per cui rifacciamo:

→

Qui non possiamo andare giù, in quanto il flusso contrario è a 0 ricordiamoci che il flusso

→

contrario si valorizza nello stesso modo del flusso normale, solo con il – davanti (Tipo qui) in

pratica, dove c’è flusso in una direzione, c’è anche nella sua direzione opposta con la stessa

intensità

CI FERMIAMO perché abbiamo RAGGIUNTO IL SINK

NON CI SONO PIU’ AP

MAXFLOW = VALORI SOMMATI DEGLI EDGES TERMINANO NEL SINK

= 20

ESERCIZIO MCF

*appunti a caso

max -3x1 + x2

x2 <= 2x1 + 2 = -2x1 + x2 <= 2

-x2 – 2 <= -x1 = -x2 <= x1+2

-x2 <= 0

-2x2 – 2 <= -x1 = x1+2 >= -2x2

C/2 >= 1/3x + y

y <= 2x

1/6 C <= x

x+y = C

Max 0,15x + 0,25 y.

I OLI e j Benzine

A = x11 + x12 + x13

B = x21 + x22 + x23

X11 <= 30%A

x12 >= 40%A

x21…

x22…

Max A5,5 + B4,5 – A( 3*0,3 + 6*0,4) – B(3*0,5 + 6*0,1)

ESERCIZIO MCF CON CANCELLAZIONE CICLI

Fai edmond karp…

Poi cancellazione cicli → →

evidenzio gli edge coi costi negativi si vede quale ciclo da un costo negativo in caso di più cicli

→

si trova il minore si fa il MIN TRA I FLUSSI DEGLI EDGE DEL CICLO CON COSTO NEGATIVO

→

MINORE si SOSTITUISCE QUEL FLUSSO CON TUTTI GLI ALTRI DEL CICLO.

Max – y

y <= 3

-x <= 2

-x + y <= 3

-2x + y <= 3

MASSIMA CARDINALITA’ FRA ALBERI “BIPARTITE”

Ci sono diversi tizi che vanno in biblioteca e hanno determinate preferenze riguardo ai libri da

→

prendere trovare la MASSIMA CARDINALITA’ significa matchare più persone possibili con più

libri possibili.

1 vuole libro 2

il primo libro (il 2) è già preso per il giallo, per cui si passa al secondo

Viola vuole come primo il libro 1, quindi lo prende diretto.

rosso ha SOLO IL LIBRO 3, ma questo è già preso

Stessa cosa il marrone.

il marrone ha però un secondo, per cui si può accontentare.

L’APPROCCIO GREEDY PERMETTE DI MATCHARE SOLO 4 PERSONE SU 5.

POSSIAMO FARE MEGLIO:

Prima di tutto creiamo un albero orientato con edges aventi CAPACITY = 1

→

Introduciamo source e sink sempre con capacity di 1 mettere la capacity di 1 ci assicura che

OGNI TIZIO ABBIA UN LIBRO SOLO. Rischieremmo questa situazione:

Oppure potremmo avere diverse copie degli stessi libri, modificando la capacity sul sink:

Modificando quelli centrali posso permettere