Teoria di Ricerca operativa

RICERCA OPERATIVA

Studio dei processi decisionali nei sistemi organizzati, nonché dei modelli e dei metodi per prevedere il comportamento di tali sistemi. In particolare quelli relativi alla crescita della loro complessività, per valutare le conseguenze di determinate decisioni e per individuare le decisioni che ottimizzano le loro prestazioni.

PROBLEMA DI OTTIMIZZAZIONE

Può essere definito intuitivamente come il problema di trovare la migliore soluzione possibile di un dato problema che può essere risolto in più modi:

• Il termine "possibile" richiede di poter distinguere una soluzione che possa essere utilizzata nella pratica, detta "soluzione ammissibile", da una che non può esserlo.
• Il termine "migliore" richiede di poter confrontare due soluzioni ammissibili, distinguendo la migliore dalla peggiore, o stabilendo che le due soluzioni sono equivalenti.

Una soluzione ammissibile è una delle possibili soluzioni del problema trovata la soluzione ammissibile, la vado ad inserire nella migliore delle soluzioni ammissibili, nella Z. La parte pix, è il migliore valore obiettivamente possibile dell'insieme delle soluzioni ammissibili.

Un problema di ottimizzazione lo descriviamo nei seguenti modi differenti uno dall'altro: linguaggio corrente, linguaggio matematico.

PB DI OTTIMIZZAZIONE

linguaggio corrente

PB DI OTTIMIZZAZIONE

linguaggio matematico

Non dice di costruire un modello astratto che descrive perfettamente il PB di ottimizzazione e che mi permette di usare specifici algoritmi per risolverlo.

METODO A 5 FASI

1. Raccolta dati
2. Identificazione del problema
3. Formalizzazione del problema
4. Soluzione del problema
5. Valutazione della soluzione

VARIABILE ALEATORIA

È un dato non noto con certezza, ma rappresentato da:

• La media
• La deviazione standard (che si misura con la stessa unità di misura della media, ovvero in un tempo).

VARIABILI

1. VARIABILE DECISIONALE: è un'incognita, e decidiamo per il valore che assume gli obiettivi del problema.
2. Le variabili decisionali si possono trovare in tutti i problemi di ottimizzazione.
3. Soluzioni ammissibili: sono le soluzioni del problema che rispettano tutti i vincoli di ammissibilità.
4. Una soluzione ammissibile: è l'insieme delle soluzioni ammissibili, definisce la Regione Ammissibile del modello.
5. Bisogna capire quali sono gli obiettivi, dipendono dalla funzione obiettivo. Le quali rispettano i criteri di valutazione di una soluzione economica del problema di massimo e, o minimo, vincolo di massimo e o minimo.

Nota: È essenziale capire che esogene sono quelli non controllabili e che sono dati e parametri del problema (insieme). Endogene sono le variabili di decisione.

MODELLI DI MISCELAZIONE

06/03/2014

Nei problemi di miscelazione si dispone di n risorse, contenente almeno uno dei riforni menti (assuniamo che il deposito di rif doma) nel presenti componenti j = 1, ....1 murb.

Qegni risorsa è disponibile il nº Gimmento ogni unità dell'ingrediente i nelle miscelazioni.

Di vincoli sui quesiti su questi portano a vincoli sto. stici, di quali due mixe,.

Gli obiettivi sono di minimizzare la quantità

di componenti nel produzione miscelata

3. obbi, atti 3 potenza del délegante

è il risorto, si il problema diventa

Min = Σc ² Bi

Σ a_ij x_j ≥ b_i, i = 1, ..., m

x_j ≥ 0, j = 1, ..., n

MODELLI DI FLUSSO SU RETE

1. Problema di flusso a costo minimo
2. Problema del cammino copialmente del costo minimo
3. Problema del massimo flusso
4. Problema di transportation
5. Problema della egemonanetto

PROBLEMA DI FLUSSO A COSTO MINIMO

Emodello più generale di problemi di

Flusso in rete Più importare modellizzata

con un GRAFO ORIENTATTO (digrafo)

avice una struttura relazione

formata da una coppia insiemi: N e A

dove N è l'insieme degli archi

D (N,A)

Esempio di un grafo orientata

(Esempi di un grafo orientata)

1. 2
2. 3
3. 4

2₂

1

1. 4
2. 3

N = {1, 2, 3, 4}

A = {(1,2), (1,3),(2,3),(2,2), (3,4)}

A &substartEquals; N × N

N × N è un probab contexto perche

N è in insulin 2 o, amnesi inaultto

insione. è un insieme delle coppia organi

X = N N⁴, (4,2), (4,3),(2,4), N ×(4,2)

A ⊂&=N deve la stessa proprietà di N.

Un altro metodo per rappresentare un

grato orientato e attraverso una

MATRICE DI INCIDENGA NODO ARCO,

se è nodi N * M, allora

la martri di ihmulator, notnico sopra gildro tutti rights

quadra. Sono i nodi su gré e letare colonne

Problema del Massimo Flusso

Sia data una rete R = (N, A, b_e, c_e), per la quale si assume che b_e ≥ 0, per ogni e ∈ A. Sia S e T due particolari nodi, S e T detti "sorgente" nel punto di flusso, e T "Pozzo". Sia poi S = N \ {S, t}.

Si obiettivo è quello di trovare la massima quantità di flusso possibile sui nodi sorgente e pozzo. Introducendo delle nuove variabili costruisce un grafo di flusso, cercando in sostanza di massimizzare il flusso.

Per trovare il componente del vettore flusso dovremo fare la somma, cioè.

• ∑ x_ij = ∑ x_ij, ∀ i ∈ S, T ∈ A
• Flusso uscente: ∑ x_ij + ∑ x_ij ∈ A
• Flusso entrante: x_ij i ∈ N, j ≠ S, T
• Flusso uscente = flusso entrante, per i accumulato
• ∑ x_ij, ∀ (i, j) ∈ A

Il flusso uscende s è può venire assorbito dai nodi pozzo T.

Problema di Trasporto

Siano date n_i origini presso le quali è disponibile un certo prodotto in quantità pari a a_i, e m destinatari ciascuno dei quali può ricevere fino a un valore disponibile b_j. Sia i = 1, ..., n e j = 1, ..., m. Si intende disporre il trasporto di queste rimanenze in modo da assegnarle ai destinatari nel rispetto dei costi

Immaginiamo che ci sia un collegamento che da ogni origine vado a tutte le destinazioni.

Il problema consiste nel determinare il trasferito più adeguato di merce da ciascuna origine verso ciascuna destinazione, in modo tale da minimizzare il costo complessivo di trasporto x_ij ≥ 0 variabili le pensano associate all’arco che connetta l’origine i con la destinazione j

• x_ij

min (∑c_ij = 1

xi = aj

Devo costruire un vincolo che leghi il valore che assume x_j al valore di y_j.

Se x_j = 0 y_j = 0

Questo vincolo lo scrivo come

x_j ≤ M y_j

dove M è un numero arbitrariamente grande. Per soddisfare il vincolo l'unico modo è che 4y_j sia uguale a 4x_j.

Il vincolo x_j ≤ M y_j è un vincolo di LEGAME

Σ 2y_j ≥ b_k x_j + z_i = m

14/03/2014

MODELLI DI LOCALIZZAZIONE

• Il obiettivo che si vede perseguire è quello di stabilire, date localizzazioni di centri di servizio, in modo da soddisfare la domanda rispettando un certo grado di sicurezza.
• Le domande, oltre a essere geografiche, sono numericamente le variabili con le quali si possono presentare modelli di localizzazione sono:
• CONTINUI: con centri di servizio senza posizione fissa.
• TIPO DISCRETO: le insieme sia presenti.
• Singolo proposto: in plus, si può ottimizzare
• A UN LIVELLO: le decisioni prese non si modificano in un altro livello.
• A DUE LIVELLI: una suddivisione tra aree di copertura “a monte” e quelli da localizzare.
• Problema di localizzazione sui nodi e il CPL, che può essere schematizzato utilizzando un GRAFO ORIENTATO (digrati) coperto BIPARTITO, i collegamenti relazioni. Non si crea un collegamento con il primo nodo di N₃, e uno collegato in grado orientato di N₃ a N₄ con un albero,
• GRAFO COMPLETO N₃ nodi di N₄ collegato a tutti i nodi che ha e gli altri BIPARTITO per che sinistra ha tutti i nodi di N₃ e a sesta ha tutti i nodi di N₄.