Università degli Studi di Cagliari FACOLTA’ DI INGEGNERIA Laboratorio di
Modelli Matematici per il Supporto alle Decisioni
- LAB_MMSD -Dott.ssa Michela Lai
mlai@unica.it
Dott.ing. Alberto Pillai
alberto.pillai@virgilio.it http://sorsa.unica.it/ Esercitazione 2
Università degli Studi di Cagliari FACOLTA’ DI INGEGNERIA Laboratorio di
Modelli Matematici per il Supporto alle Decisioni
- LAB_MMSD -
Dott.ssa Michela Lai
mlai@unica.it
Dott.ing. Alberto Pillai
alberto.pillai@virgilio.it http://sorsa.unica.it/ Esercitazione 2
Esercizi per casa 1
Scrivere il modello e risolverlo con dati a piacere
L’agenzia matrimoniale Cuori Solitari deve organizzare il gran ballo di fine
anno. L’agenzia ha n clienti maschi e n clienti femmine, ed ha prenotato
n tavoli da due posti al famoso ristorante Cupido. Dai profili psicologici
raccolti dai clienti, l’agenzia è in grado di calcolare, per ogni maschio
i, l’insieme F(i) delle femmine con le quali potrebbe essere interessato ad
intrecciare una relazione, e che potrebbero essere interessate ad intrecciare
una relazione con lui; un analogo insieme M(j) può essere ottenuto per ogni
femmina j. Dai profili dei clienti, l’agenzia è anche in grado di calcolare,
per ogni coppia (i; j) “compatibile”, il costo cij della cena da offrire, che
deve consistere di piatti graditi ad entrambi i commensali. L’agenzia vuole
quindi decidere come formare le coppie per il gran ballo in modo da evitare
coppie incompatibili e minimizzare il costo complessivo delle cene.
Esercizi per casa 1
Esercizi per casa 2 Individuazione del problema, analisi della realtà e raccolta dati
RISP % Mattina % Sera D.S. 30 30 D.N.S. 10 20 U.S. 10 15 U.N.S. 40 5 Per un’indagine conoscitiva si vogliono contattare rispettivamente almeno:
150 donne sposate
110 donne non sposate
120 uomini sposati
100 uomini non sposati
Dati:
Costo telefonate al mattino (prima delle 14:00) = 0.2€
Costo telefonate alla sera (dopo le 14:00) = 0.1€
Probabilità di risposta:
Quante telefonate effettuare nei due periodi?
Si richiede che almeno metà delle
telefonate sia effettuata al mattino
Problema del call center Individuazione del problema, analisi della realtà e raccolta dati
ESERCIZIO:
Scrivere il relativo modello di ottimizzazione
Problema del call center Costruzione del modello di ottimizzazione
Variabili
tm: numero di telefonate da compiere al mattino di costo unitario
tp: numero di telefonate da compiere al pomeriggio di costo unitario
Parametri
i: indice delle categorie di persone a cui telefonare
aim: probabilità di trovare una persona della categoria i al mattino
aip: probabilità di trovare una persona della categoria i al pomeriggio
bi: numero minimo di persone di categoria i a cui telefonare
Problema del call center Costruzione del modello di ottimizzazione
ESERCIZIO:
Scrivere l’istanza su lindo Funzione obiettivo:
min cm ∙ tm + cp ∙ tp
Soddisfacimento del numero minimo di chiamate per la categoria i:
aim ∙ tm + aip ∙ tp ≥ bi
Almeno la metà delle telefonate devono essere effettuate al mattino:
tm - tp ≥ 0
Vincoli di non-negatività:
tm ≥0 tp ≥0
Problema del call center Determinazione delle soluzioni
Modello di ottimizzazione:
min cm ∙ tm + cp ∙ tp
aim ∙ tm + aip ∙ tp ≥ bi
tm - tp ≥ 0
tm ≥0
tp ≥0
Problema del call center Determinazione delle soluzioni
ESERCIZIO:
Determinare la soluzione con Lindo
Problema del call center Analisi dei risultati
Soluzione con Lindo LP OPTIMUM FOUND AT STEP 5
OBJECTIVE FUNCTION VALUE
1) 1440.000
VARIABLE VALUE REDUCED COST
TM 480.000000 0.000000
TP 480.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 13800.000000 0.000000
3) 3400.000000 0.000000
4) 0.000000 -0.120000
5) 11600.000000 0.000000
6) 0.000000 -0.800000
NO. ITERATIONS= 5
Introduzione I problemi di flusso su rete presentano una speciale struttura che consente di adottare algoritmi particolarmente efficienti per la loro risoluzione
Tra i vari problemi di flusso, ci occuperemo del Problema del Flusso di Minimi Costo (MCF). In questa esercitazione:
faremo brevi richiami della teoria dei grafi e del MCF
vedremo due possibili applicazioni del MCF
utilizzeremo un solver specializzato per problemi di MCF
Richiami di teoria dei grafi Un grafo G(N, A) è definito da una coppia di insiemi N e A
N, detto insieme dei nodi, è l’insieme dei primi n numeri naturali
A, detto insieme degli archi, è un sottoinsieme del prodotto cartesiano N x N
Dato un nodo i Є N
P(i) = {j: (j, i) Є A}, è l’insieme dei predecessori di i
S(i) = {k: (i, k) Є A}, è l’insieme dei successori di i
Dato un arco (i, j) Є A
Il nodo i è la coda dell’arco
Il nodo j è la testa dell’arco
Si ha un grafo orientato quando (i, j)≠(j,i)
G(N, A) orientato
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 4), (2, 3), (2, 5), (3, 1), (3, 5), (4, 5), (5, 4)}
Si dice cammino un insieme di archi in cui ogni coppia contiene un nodo della coppia precedente.
Esempio: {(1, 2), (2, 5), (4, 5)}
Si dice cammino orientato un insieme di archi in cui la testa di ogni arco coincide con la coda dell’arco seguente.
Esempio: {(1, 2), (2, 5), (5, 4)} Richiami di teoria dei grafi
Grafo connesso esiste sempre un cammino tra qualsiasi coppia di nodi
Grafo fortemente connesso esiste un cammino orientato tra ogni coppia di nodi
Ciclo cammino chiuso, inizia e termina nello stesso nodo. Se il cammino è orientato, anche il ciclo è orientato.
Ciclo Hamiltoniano ciclo che passa per ogni nodo del grafo una sola volta
Richiami di teoria dei grafi
Foglia nodo testa/coda di un solo arco
Albero grafo connesso privo di cicli
ha almeno due foglie
Estraendo un qualsiasi arco l’albero viene suddiviso in due sottoalberi distinti
un albero con n nodi presenta n-1 archi
Dato un grafo G=(N, A)
Grafo parziale G‘=(N, A‘) grafo in cui
Albero ricoprente di un grafo albero che costituisce un grafo parziale che tocca tutti i nodi del grafo Richiami di teoria dei grafi
Matrice di incidenza nodi-archi uno dei possibili modi in cui rappresentare un grafo
Ha un numero di righe pari al numero dei nodi
Ha un numero di colonne pari al numero degli archi
In ogni colonna solo due elementi sono non-nulli:
1 in corrispondenza della coda di quell’arco
-1 in corrispondenza della testa di quell’arco
La matrice di incidenza è una struttura adatta a ricavare algoritmi, ma non consente una buona implementazione Richiami di teoria dei grafi
Esercizio
Ricavare la matrice di incidenza nodi-archi del grafo Richiami di teoria dei grafi Una matrice di incidenza con n nodi ha rango n-1
Dimostrazione
Il suo rango non è n, infatti, comunque si estragga un minore di ordine n la somma delle sue colonne risulta sempre nulla
Considerato un albero ricoprente del grafo, il minore ad esso corrispondente ha n righe e n-1 colonne.
Questo albero presenta almeno 2 foglie e la sua matrice di incidenza presenta almeno 2 righe con un coefficiente non nullo
Con delle permutazioni si porta il coefficiente non nullo di una foglia in prima riga sulla diagonale principale
Si cancella quella foglia e quel ramo, si ottiene un nuovo albero con almeno 2 foglie che possono essere portate in seconda riga sulla diagonale principale
Iterando questo procedimento, si portano n-1 coefficienti non nulli sulla diagonale principale Richiami di teoria dei grafi
Il problema del flusso di minimo costo Dato un grafo G(N,A), ad ogni nodo i viene associata una quantità di risorsa bi
Se bi > 0 il nodo i è un nodo offerta
Se bi < 0 il nodo i è un nodo domanda
Se bi = 0 il nodo i è un nodo di transito
Si assume che l’offerta totale di risorsa sia uguale alla domanda, in questo caso la rete si dice bilanciata
Notazione:
xij : flusso di risorsa che transita sull’arco (i,j)
cij : costo di transito sull’arco (i,j), il costo è unitario
Formalizzazione del MCF dove E è la matrice di incidenza nodi archi
Se una rete non è bilanciata, occorre bilanciarla con opportuni valori di domande/offerte in nodi artificiali connessi da archi di costo molto elevato Il problema del flusso di minimo costo
Comments