Università degli Studi di FirenzeUniversità degli Studi di Firenze

CdLS Ingegneria per la Tutela dell’Ambiente e del CdLS Ingegneria per la Tutela dell’Ambiente e del TerritorioTerritorio

Corso di Ricerca OperativaCorso di Ricerca Operativa

Introduzione Introduzione all’Ottimizzazione con il all’Ottimizzazione con il

Risolutore di ExcelRisolutore di ExcelDocenteDocente

Prof.ssa M.G. TecchiProf.ssa M.G. Tecchi

StudentiStudenti

Bellacci Bellacci LorenzoLorenzo

Carubini Carubini GianoGiano

MODELLI d’OTTIMIZZAZIONEMODELLI d’OTTIMIZZAZIONE

variabili di decisione variabili di decisione ++parametri parametri + +vincoli vincoli

complessità complessità situazioni situazioni realireali

necessità di necessità di automatizzareautomatizzare

ProblemProblema PLa PL

soluzione soluzione

ottimaottima

RISOLUTORE di EXCELRISOLUTORE di EXCEL

• ottimizzazione modelli ottimizzazione modelli vincolativincolati

• utilizzo Metodo del utilizzo Metodo del SimplessoSimplesso• risoluzione di problemi risoluzione di problemi lineari e non linearilineari e non lineari

Modelli Lineari VincolatiModelli Lineari Vincolati

RISOLUTORE di EXCELRISOLUTORE di EXCEL

Il modello è composto da:Il modello è composto da:

• VincoliVincoli

• Funzione Funzione obiettivoobiettivo

Corretta compilazione Corretta compilazione foglio di lavoro Excelfoglio di lavoro Excel

Vincoli di segnoVincoli di segno

Vincoli tecniciVincoli tecnici

CREAZIONE FOGLIO EXCELCREAZIONE FOGLIO EXCEL ((Esempio modello OAK Esempio modello OAK

Products)Products)Obiettivo: Obiettivo: MassimizzazioneMassimizzazione

Variabili di Variabili di decisionedecisione Disequazioni di Disequazioni di

vincolovincolo

Coefficienti di Coefficienti di costocosto

B3*B4+C3*C4

B6*B4+C6*C4

B7*B4+C7*C4

B8*B4+C8*C4

B9*B4+C9*C4

B10*B4+C10*C4

B11*B4+C11*C4

COMPILAZIONE FINESTRA COMPILAZIONE FINESTRA RISOLUTORERISOLUTORE

Utilizzo Utilizzo complessivocomplessivo

Disponibilità di Disponibilità di magazzinomagazzino

COMPUTAZIONE SOLUZIONE OTTIMACOMPUTAZIONE SOLUZIONE OTTIMA

MODIFICA del MODELLO

RAPPORTIRAPPORTI

SENSIBILITA’SENSIBILITA’informazioni sul informazioni sul

grado di sensibilità grado di sensibilità della soluzione a della soluzione a

piccolepiccolevariazioni dei variazioni dei

coefficienti della coefficienti della F.O.F.O. o dei o dei vincolivincoli..

LIMITILIMITIelenca la cella elenca la cella

obiettivo e le celle obiettivo e le celle variabili con i variabili con i

rispettivi valori, i rispettivi valori, i limitilimiti

inferiore e inferiore e superiore e i valori superiore e i valori

obiettivo.obiettivo.

VALORIVALORIelenca la cella elenca la cella obiettivo e le obiettivo e le celle variabili celle variabili con i relativi con i relativi

valorivalorioriginali e finali, i originali e finali, i

vincoli e le vincoli e le informazioni sui informazioni sui

vincoli.vincoli.

RAPPORTO SENSIBILITA’RAPPORTO SENSIBILITA’

Adeguamento del modello a Adeguamento del modello a situazioni situazioni realireali

• imprecisione datiimprecisione dati

• variazione stime dativariazione stime dati

effetti sulla effetti sulla soluzione soluzione

ottimale e sul ottimale e sul valore della F.O.valore della F.O.

Quanto possono essere aumentati o diminuiti i coefficienti della F.O. e/o dei “vincoli a destra” (termini

noti) senzacambiare la soluzione ottimale

(assumendo fissati gli altri dati). Variazione del valore ottimo della F.O. in

relazione della variazione unitaria del termine noto associato al prezzo ombra. Sono

sempre associati alle variabili di legame

VARIAZIONE COEFFICIENTI F.O.VARIAZIONE COEFFICIENTI F.O. (interpretazione grafica)(interpretazione grafica)

variazione pendenza variazione pendenza linea linea isoprofittoisoprofitto

0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150

Captain

Ma

te

8C+4M=1280

4C+12M=1600

4C+14M=760 C=140

M=120

C+M100

56C+48M=10160

56C+40M=9680

56C+80M=13160

variazione<variazione consentita soluzione ottimale invariata

variazione>variazione consentita cambia soluzione ottimale

variazione=variazione consentita infinite soluzioni ottimali

situazione iniziale

VARIAZIONE TERMINI NOTIVARIAZIONE TERMINI NOTI

Incremento (/decremento) Incremento (/decremento) termine noto con vincolo termine noto con vincolo ≥ ≥ (/≤)(/≤)Decremento (/incremento) Decremento (/incremento) termine noto con vincolo termine noto con vincolo ≥ ≥ (/≤)(/≤)

RESTRIZIONE RESTRIZIONE di vincolodi vincolo

ATTENUAZIONE ATTENUAZIONE di vincolodi vincolo

VARIAZIONE F.O. = f (prezzi ombra)VARIAZIONE F.O. = f (prezzi ombra)

VARIAZIONE TERMINI NOTIVARIAZIONE TERMINI NOTI

1. variazione termini noti<variazione 1. variazione termini noti<variazione consentitaconsentita• peso invariato del vincolopeso invariato del vincolo• variazione soluzione ottimalevariazione soluzione ottimale• variazione valore F.O.variazione valore F.O.

2. variazione termini noti=variazione 2. variazione termini noti=variazione consentitaconsentita• il vincolo diventa il vincolo diventa di di legamelegame• se n° vincoli di legame>n° variabili di se n° vincoli di legame>n° variabili di decisione decisione soluzione soluzione degeneredegenere

3. variazione termini noti>variazione 3. variazione termini noti>variazione consentitaconsentita• peso del vincolo=0 peso del vincolo=0 ridondanzaridondanza

ridondanza

CONCLUSIONICONCLUSIONI

1. Semplificazione problemi PL 1. Semplificazione problemi PL complessicomplessi (analisi problemi reali)(analisi problemi reali)

L’uso del L’uso del RisolutoreRisolutore comporta:comporta:

3. Valutazione effetti 3. Valutazione effetti incertezzaincertezza dei dati sui dei dati sui risultati (range possibili soluzioni ottimali)risultati (range possibili soluzioni ottimali)

2. La computazione viene 2. La computazione viene sempresempre terminata (necessità di valutare terminata (necessità di valutare attendibilità soluzione)attendibilità soluzione)

FUNZIONE OBIETTIVO (F.O.)FUNZIONE OBIETTIVO (F.O.)

Variabili di Variabili di decisione decisione (incognite)(incognite)

Coefficienti di Coefficienti di costo costo (dati)(dati)

××

VINCOLIVINCOLI

Restrizione allo spazio delle possibili Restrizione allo spazio delle possibili decisionidecisioni

Vincoli tecniciVincoli tecnici Vincoli di non negativitàVincoli di non negatività