Lezioni, Ricerca Operativa

UNA VOLTA FATTA L’ANALISI DI SENSIBILITA’

­ Se mi dice che “Dal momento che la società non ha molta esperienza con i metodi di riduzione dell'inquinamento, le stime dei co­

sti riportate nella tabella 3 sono grezze e potrebbero esserci errori del 10% in entrambe le direzioni” (Vedi esercizio

tasso di

AirPollutionAdvanced) o qualcosa di simile, devo verificare che aumentando e diminuendo (“entrambe le direzioni”) del

errore l’Oggettivo coefficiente, la soluzioni non varia. Per verificare ciò, devo verificare che la cella dell’Oggettivo Coefficiente

meno il decremento consentito sia maggiore dell’Oggettivo Coefficiente diminuito del tasso di errore. Stessa cosa per l’aumento

ma devo fare la somma tra l’OC e l’incremento consentito.

­ sensibile

Il parametro è se con l’incremento o la diminuzione del tasso di errore la mia soluzione cambia.

­ Inoltre se l’incremento o il decremento consentito di un coefficiente è molto basso rispetto agli altri bisognerà fare particolare

maggiore attenzione.

attenzione in quanto non tollera errori di valutazione. Sono proprio questi valori quelli da valutare con

PROBLEMA DUALE (22)

Per passare al problema duale devo moltiplicare tutti i valori della mia tabella, tranne quelli di output, e cambiare di

segno le eventuali disequazioni presenti nei vincoli. Per moltiplicare per -1 tutti i valori mi conviene scrivere -1 in

una cella e poi attraverso l’INCOLLA SPECIALE  Incolla Speciale…  Moltiplica selezioni i valori interessati.

2

pag.

TABELLE DI DATI (Z – Business Model)

Per tabella con variabili intendiamo un insieme di celle che vengono utilizzate per testare e analizzare dati al

variare di uno o due parametri. La tabella può contenere il risultato di diversi scenari in un’unica tabella, così da

poter analizzare e valutare la migliore opzione.

Prendendo l’immagine sopra come esempio procediamo come di seguito:

1 – Scrivo i “titoli” (E1:G1) delle cose che voglio vedere come cambiano al cambiare di quello che scriverò in verticale (in

questo caso il tasso).

2 – Scrivo in verticale (D3:D8) i vari tassi che voglio inserire nel mio scenario.

3 – Riporto sotto i titoli (E2:G2) i valori che avevo ricavato nel mio problema di partenza. NOTA BENE: Non bisogna

riportare il valore scrivendolo direttamente ma bisogna riportalo come riferimento alla cella!

4 – Lascio vuota la cella D2.

5 – Seleziono l’area D2:G8 e poi DATI - ANALISI DI SIMULAZIONE - TABELLA DATI

6 – In “Cella di input per colonna” inserisco il tasso (in questo esempio) che avevo considerato nel problema di partenza

Posso così visualizzare tutti i casi possibili in base al valore del tasso e decidere così quale sia l’opzione più

conveniente. In questa operazione mi aiuta la FORMATTAZIONE CONDIZIONALE che modificando i colori delle

celle mi aiuta a vedere quali siano i casi migliori e quelli peggiori.

3

pag.

Nel caso invece di una tabulazione a due dimensioni bisogna creare due assi, uno orizzontale ed uno verticale,

riportanti i valori della matrice che andremo a creare. Nell’angolo in alto a sinistra (quello dove si incontrano i due

assi) dobbiamo riportare, col solito metodo del riferimento, COSA VOGLIAMO VALUTARE SULLE DUE

DIMENSIONI. E’ anche possibile valutare più cose al variare di due parametri ma bisogna esprimerlo con una

giusta formula e sintassi.

SOLVER TABLE 2007

Il Solver Table 2007 funziona allo stesso modo della tabella.

NETWORK OPTIMIZATION PROBLEMS (41)

Un esercizio di trasporti è riconoscibile dalla presenza di NODI e da FRECCE che collegano i vari nodi tra di

loro indicanti le direzioni percorribili.

Per risolvere questi esercizi solitamente si utilizza una struttura FROM, TO, Varie caratteristiche, Taken

(contenente 0 o 1 ad indicare se quella tratta viene percorsa o no, ossia l’output). Successivamente si crea

un’ulteriore tabella con:

- NODI = incolonna tutti i nodi facenti parte dell’esercizio ed è seguito dalle colonne OUT e IN che

indicano la merce o qualsiasi altra cosa che sta uscendo e che sta entrando dal/nel nodo;

- OUT = indica ciò che sta uscendo dal nodo presente nella stessa riga. Si ricava attraverso la

formula: = SOMMA.SE (From ; Nodo ; intervallo con valori da sommare)

- IN = indica ciò che sta entrando nel nodo presente nella stessa riga. Si ricava attraverso la formula:

= SOMMA.SE (To ; Nodo ; intervallo con valori da sommare)

- = OUT – IN

NET = è la differenza tra OUT e IN ossia

In questa tabella vengono messi vincoli ai NET che devono essere positivi per indicare dove

partono, 0 dove entrano ed escono, -1 dove arrivano e si fermano.

TRASPORTO (30 / 31 / 32)

Generalmente un problema di trasporti presenta una situazione in cui si deve trasportare qualcosa da delle

sources alle destinations in modo tale da minimizzare i costi. Presenta tabelle come laterali con vari casi e

sono utili formule come il cerca.vert o il cerca.oriz.

ASSEGNAMENTO (30)

4

pag.

Generalmente un problema di assegnamento si presenta quando ho qualcosa da assegnare a,

generalmente, un impianto.

Un esempio fatto in classe è quello di assegnamento di 3 macchinari nel migliore dei 4 stabilimenti

in modo che i costi siano minimizzati. Faccio quindi una tabella 3X4 dove ho i 3 macchinari e i 4

stabilimenti con output a piacimento. I vincoli sono che questi devono essere o 0 o 1 perché mi

devono indicare se il macchinario si trova o meno in quell’impianto. I costi totali sono dati come:

=MATR.SOMMA.PRODOTTO(matrice di output; matrice dei costi)

SHORTEST PATH PROBLEM

Il problema mi fornisce i Nodi e le distanze e solitamente un ingresso con un’uscita (o ultimo nodo da

raggiungere). Per svolgere l’esercizio devo aggiungere una colonna di Taken in cui mi verrà scritto se il

percorso tra quei nodi viene percorso oppure no ed è l’output del mio esercizio.

Creo poi la solita tabella laterale con NODI, IN, OUT e NET imposto nella colonna VINCOLI l’ingresso ( +1 ),

l’uscita ( -1 ) e tutti gli altri nodi di passaggio ( 0 ). La cella da controllare, ossia quella da essere minimizzata,

è la cella in cui si ha la matrice somma prodotto tra TAKEN e DISTANCE.

MINIMUM SPANNING TREE PROBLEM

Problema in cui devo unire tra loro tutti i nodi, andando a creare una rete, in modo da minimizzare la

distanza totale che tuttavia non può essere risolto con il SOLVER TABLE.

Esistono 2 tipologie di problema: quello con il DISEGNO e quello in TABELLA.

DISEGNO

Se mi viene dato il disegno, ossia diversi nodi uniti tra loro con l’ammontare della distanza devo procedere

così:

- Scelgo il percorso unente due nodi più corto in assoluto;

- Scelgo il percorso più corto unente due nodi, ammesso che non colleghi tra loro due nodi che già

sono stati compresi nella rete;

TABELLA

Può essere svolto sia con Excel sia direttamente su tabella. Il modo più corretto è quello attraverso Excel in

quanto da la possibilità di verificare se il percorso trovato è il migliore. Si procede così:

Vedi Esercizio 4 della Simulazione, Cartella “Giusti”.

MAXIMUM FLOW PROBLEM

5

pag.

Il problema mi fornisce i Nodi e le Capacità e solitamente uno o più ingressi con una o più uscite (o

ultimo/i nodo/i da raggiungere). Per svolgere l’esercizio devo aggiungere una colonna di Taken in cui mi

verrà scritto quanto flusso passerà nel percorso unente quei due nodi.

Creo poi la solita tabella laterale con NODI, IN, OUT e NET imposto nella colonna VINCOLI dove dovrò

solamente specificare che le quantità, o flows, nei nodi di passaggio deve essere zero. La cella da

controllare, ossia quella da essere massimizzata, è la cella in cui ho la somma di tutti i NET degli “ingressi”

(Il net nella prima linea).

MINIMUM COST FLOW PROBLEM

Il problema mi fornisce i Nodi, le Capacità e i Costi e solitamente un’ ingresso con un’uscite (o ultimo

nodo da raggiungere). Per svolgere l’esercizio devo aggiungere una colonna di Taken in cui mi verrà scritto

quanto flusso passerà nel percorso unente quei due nodi.

Creo poi la solita tabella laterale con NODI, IN, OUT e NET imposto nella colonna VINCOLI la quantità

attesa in ingresso ( +X ), e la stessa quantità in uscita ( -X ) e tutti gli altri nodi di passaggio ( 0 ). La cella da

controllare, ossia quella da essere minimizzata, è la cella in cui si ha la matrice somma prodotto tra TAKEN

e COST.

INTEGER PROBLEM (IP)

Problemi di Programmazione Lineare con la restrizione che tutte le variabili siano dei numeri interi.

MIP

Se questa condizione è rispettata solo in parte allora si ha un problema di Mixed Integer Problem ( ). Se

BIP

invece il problema di IP ha variabili che possono assumere solo valori 0 e 1 si ha un problema (Binary

Integer Problem).

NON LINEAR PROGRAMMING (NLP)

ELASTICITA’ DEL PREZZO

6

pag. P(x) = x *

Il profitto dato dalla produzione e vendita di prodotti di una funzione NON LINEARE è dato da

p(x) – c*x ossia il PROFITTO è dato dalla differenza tra il prodotto della quantità e il prezzo in base alla

quantità e il prodotto tra la quantità e il costo. Devo anche tener conto del costo marginale e di fatti come la

curva di esperienza.

VOLUME DISCOUNTS

Il prezzo di un prodotto dipende dal volume ordinato quindi non avrò una funzione lineare ma una

SPACCATA.

PORTFOLIO SELECTION WITH RISKY SECURITIES

Gli investitori sono preoccupati sia del loro “ritorno” o guadagno e del rischio associato ai loro investimenti.

Per tutte le formule guardo le slide 5 e 6 del file RO60.

UNCONSTRAINED OPTIMIZATION

Caso in cui non c’è alcun vincolo e l’obiettivo è quello di massimizzare f(X) in base appunto alla X scelta.

Questo problema, come quello fatto in classe, può essere risolto attraverso un procedimento di risoluzione

iterativa (ossia con una tabella o con un SOLVER TABLE 2007)

LINEARLY CONSTRAINED OPTIMIZATION

QUADRATIC PROGRAMMING

CONVEX PROGRAMMING

È un modo di raggruppare tutti quei problemi, quindi anche i precedenti, che presentano una funzione f(x)

concava.

La funzione obiettivo è quindi una funzione concava mentre tutti i vincoli devono essere convessi. Ciò

permette di sapere che il massimo locale è anche il massimo globale.

SEPARABLE PROGRAMMING

E’ un caso speciale dei CONVEX PROGRAMMING pertanto oltre al fatto di avere la funzione obiettivo e le

funzioni vincolari come funzioni separabili, devono essere rispettate anche le condizioni delm Convex

Programming. La funzione è quindi separabile in una somma di fu