Teoria ed esercizi esame di Ottimizzazione combinatoria

Revisionato il 19/07/2026

di Bellet_1202

Publisher

Vota

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Contiene teoria ed esercizi spiegati in parole semplici per l'esame di Ottimizzazione combinatoria. Problemi di modelli, diagramma ad albero, metodi di gestione del flusso tramite algoritmi di …

Esame Ottimizzazione combinatoria

Facoltà Ingegneria

Dal corso del Prof. Dal Lago Ugo

Università Università degli Studi di Bologna

A.A. 2024-2025

110 pagine

Appunti esame

Scarica

Estratto del documento

Ottimizzazione combinatoria

La ricerca operativa e l'ottimizzazione combinatoria si occupano di studiare le metodologie a supporto delle decisioni, minimizzando i costi e le perdite e massimizzando i ricavi. È una disciplina a forte contenuto economico.

Definizioni e concetti fondamentali

Il problema è la classe "problema da risolvere", l'istanza del problema è un possibile setup di valori per il suddetto. G = soluzioni ammissibili e non. Non basta, G è tutto l'insieme a cui appartengono le soluzioni dell'equazione, mentre Fp sono le soluzioni dell'equazione. Tradotto: trovare rispettivamente il minimo e il massimo dell'insieme delle soluzioni Fp, ricavate con la funzione di costo cp(g), dove g è la soluzione ipotetica.

Soluzioni e funzione di costo

In un insieme, esistono per forza un massimo e un minimo. Cp è un modo per indicare a livello convenzionale (non c'entra con il segno di un valore). Dato un problema e una g qualsiasi, tale che g sia la funzione di costo che genera un valore ottimo (Zp, che può essere ad esempio un minimo o un massimo, dipende da cosa vuole il problema).

1 è il massimo, in quanto 1² = 1. Il valore ottimo è il prodotto di funzione cp ZP. La soluzione ottima g è ciò che produce, tramite cp, ZP. Dato che sono soggetti a errore, gli algoritmi euristici potrebbero concludere che non esiste soluzione pur esistendo (approssimano male).

Algoritmi esatti ed euristici

Un algoritmo esatto è un algoritmo che risolve il problema nel modo più efficiente (se con efficienza intendiamo la nostra esigenza, se il mio problema è trovare l'algoritmo più inefficiente dal punto di vista temporale, la soluzione più efficiente sarà, paradossalmente, l'algoritmo più lento ed inefficiente). Un algoritmo euristico trova una qualsiasi soluzione per forza, più bassa o più alta di quella ottima (quindi più approssimativa).

L'errore assoluto è uguale al costo soluzione non ottimizzato meno il costo soluzione ottima (in valore assoluto), il delta tra la soluzione "euristica" e quella "esatta". Quindi: ZP è il valore ottimo dato dalla funzione di costo applicata alla soluzione ottima. Un algoritmo esatto mi trova g tale che cp(g)=ZP; un algoritmo euristico mi trova g*.

Sezione 2: I modelli

Un modello è un insieme di problemi relativi alla stessa categoria. Come risolvo una matrice? Modello di risoluzione di una matrice. Come sorto questo array? Modello di sorting di un array (comprende quicksort, bubblesort, collections sort come possibili soluzioni). Come risolvo questa equazione di secondo grado? Ecc.

In PL, posso avere variabili appartenenti a R (quindi anche frazionari); in PLI, ho solo interi. Questo si traduce in una possibilità di usare le variabili PLI come flag logici.

Esempio di problema di PL

Considerare il max al negativo per trovare il min.
Come massimizzare il profitto e minimizzare i costi, con determinati vincoli.
Quanto metallo fondere tenendo conto dei vincoli economici (quanto costa) e di reperibilità (quanto ne è disponibile).

Posso avere n valori quantitativi (200 scatole) oppure 2 valori booleani (1 = scatola presente; 0 = scatola non presente).

Quando x è 0, y è 1 e viceversa.
X -> y = 0, solo se abbiamo x=0 e y = 1.

Il resto si capisce, considerando la tabella di verità. Ragionare sulle tabelle di verità fa capire i vincoli. Assegnare la variabile xij tale per cui l’iesimo oggetto sia assegnato al jesimo luogo (di una matrice ad esempio).

Avendo un insieme F, sottinsieme di un numero di elementi N dobbiamo determinare il costo di ogni F e trovare il minimo D. La situazione è rappresentabile con una matrice MxN dove M è il numero delle FJ, quindi tutte le facenti parte di F (f va da f1 a fM).

La prima sommatoria è il risultato di dobbiamo prendere il costo delle variabili moltiplicate per le variabili che fanno parte del sottoinsieme di costo totale minimo (come se avessi una stringa di n elementi, ognuno dei quali si sviluppa in basso m volte. Ogni n ha una stringa di F, quindi ho una matrice nxm, dove solo una delle stringhe verticali avrà 1, ovvero quella dei minimi costi, contenuta in D).

x-a1 o a2 indica quanto è grande x. Z1 può essere uguale a tutto l’intervallo (a2-a1) se x = 0 e se y non annulla (quindi y != 0).

Rete di flusso

N e A sono rispettivamente l’insieme dei nodi e l’insieme degli archi.

Anteprima

Vedrai una selezione di 20 pagine su 110