Ricerca Operativa

La Ricerca Operativa è la disciplina che studia come formalizzare in modo scientifico problemi complessi, che riguardano varie discipline, spesso relativi ad una presenza di risorse matematiche

Essa utilizza diversi strumenti in prevalenza matematici.

Si può affermare in ogni caso che la programmazione matematica pur non essendo tutta la Ricerca Operativa è uno degli elementi fondamentali.

Programmazione Matematica

Per problema di ottimizzazione matematica si intende un qualsiasi problema di ottimizzazione riconducibile alla seguente espressione generale:

Ricercare i valori delle variabili che consentono di massimizzare o minimizzare una funzione  nel rispetto delle condizioni

In cui le bi sono costanti scalari e le funzioni f e gi assumono valori scalari reali

Riunendo le variabili in un vettore x ad n componenti , i coefficienti delle relazioni  in una matrice G, di dimensioni mxn, indicando con {::} le possibili relazioni  e con Max! o Min! l’operazione di minimizzazione o massimizzazione, un problema di p.m. puo’ essere sinteticamente espresso come:

SOLUZIONE: Un insieme di n valori assegnati alle componenti del vettore costituisce una soluzione del problema

Classificazione dei problemi di Programmazione Matematica

I problemi di programmazione matematica possono essere, in dipendenza di certe loro caratteristiche variamente classificati.

In prima istanza si fa riferimento a tre chiavi di aggregazione:

->le caratteristiche della funzione obiettivo e dei vincoli

->le dimensioni del sistema vincolare (numero di variabili e o vincoli)

->le caratteristiche delle variabili

 

Dualità in Programmazione Lineare

La teoria della dualità consente di associare ad un problema di programmazione lineare un altro problema di programmazione lineare che utilizza lo stesso insieme di dati che viene detto duale.

Convenzioni

Introduciamo le seguenti forme standard:

Forma standard del diretto
Forma standard del duale

Teorema: Il duale del duale è il diretto

Teorema sulle tre possibilità di un problema di programmazione lineare

Data una coppia di problemi tra loro duali si può verificare una delle seguenti tre possibilità:

1. Ne il problema diretto ne il problema duale ammettono soluzioni ammissibili
2. uno ammette soluzione ammissibile illimitata, l'altro non ammette soluzioni
3. sia il problema diretto che il problema duale ammettono soluzioni ammissibili: in questo caso si verifica sempre che v>=z (teorema della dualità in forma debole)

Teorema della dualità in forma forte

Assegnato un problema di programmazione lineare, se il problema diretto e quello duale ammettono soluzioni ammissibili, allora per entrambi esiste una soluzione ottima. Ed in particolare si verifica che Zmax=Vmin

Esercizi Scarto Complementare

1. Esercizi scarto complementare 1 (PDF)

1. Esercizi scarto complementare 2 (PDF)

Problemi di flusso su rete

Come abbiamo già indicato i problemi di programmazione lineare possono essere suddivisi in problemi di mixing e problemi di flusso su rete Per i problemi di mixing la risoluzione può essere fatta in modo efficiente con gli algoritmi del simplesso, mentre per i problemi di flusso su rete esistono algoritmi ancora più efficienti.

Problemi di flusso su rete a costo minimo

E’ il principale problema di flusso su rete e da esso derivano:

• il problema dell’assegnamento
• il problema del trasporto
• il problema del massimo flusso
• il problema del percorso minimo

Tale problema consiste nel determinare lo spostamento di una risorsa su una rete, allo scopo di soddisfare le domande di tale risorsa che si suppongono concentrate in alcuni nodi della rete, in presenza di determinate offerte che si suppongono concetrate in altri nodi della rete stessa: tale spostamento deve essere effettuato al minimo costo.

Problema del trasporto

Esso è un particolare problema di flusso su rete che può essere così descritto:

Esistono m origini ed n destinazioni, ogni origine ha una disponibilità di risorsa ai, ogni destinazione richiede una quantità di risorsa pari a bj.

Detto Cij il costo per spostare una unità di risorsa dall'origine i alla destinazione j un problema del trasporto può essere scritto come problema di programmazione lineare nel seguente modo:

_____________IMMAGINE DA INSERIRE___________________

Il problema del trasporto gode delle seguenti proprietà:

• La quantità totale offerta è uguale alla quantità totale richiesta. Problemi con quantita offerta diversa dalla quantità richiesta possono essere risolti con l'introduzioni di origini o destinazioni fittizie
• Il sistema dei vincoli non è a rango massimo, ma è pari al più ad n+m-1
• E' sempre consistente. Vi è infatti una soluzione che soddisfa sempre tutti i vincoli

Risoluzione del problema del trasporto

Per risolvere il problema del trasporto la prima cosa da fare è trovare una prima SDBA

Algoritmi risolutivi per il problema del percorso minimo

Gli algoritmi utilizzati per risolvere il problema del percorso minimo si suddividono in:

• Algoritmi arborescenti: forniscono il percorso minimo tra un nodo fissato come origine e tutti gli altri
• Algoritmi matriciali: determinano i cammini minimi tra tutti i nodi del grafo
• Algoritmi euristici

Gli algoritmi arborescenti a loro volta si suddividono in

• Algoritmi label setting: fissata un origine, a ogni iterazione viene individuato il percorso minimo tra essa e uno o più nodi del grafo
• Algoritmi label correcting: fissata un origine, solo all'ultima iterazione arrivano a determinare simultaneamente i percorsi minimi tra un nodo origine e tutti gli altri

Tra gli algoritimi arborescenti label setting ricordiamo l'algoritmo di Dantzing e l'algoritmo di Dijkstra mentre tra gli algoritmi label correcting ricordiamo l'algoritmo di Foord Moore Bellman

Tra gli algoritmi matriciali ricordiamo il principio di decomposizione di Hu

Problema del cammino massimo e tecnica PERT

Strutturalmente il problema del cammino massimo è identico a quello del cammino minimo con la differenza che la funzione obiettivo è a massimizzare piuttosto che a minimizzare: per la sua risoluzione si fa ricorso alla cosiddetta tecnica PERT

La tecnica PERT si fonda sulla scomposizione di un progetto in attività, intese come insieme di operazioni necessarie a realizzare un progetto, delimitate da due eventi di "inizio attività" e "fine attività"

Grazie a tale tecnica è possibile rapprentare un progetto tramite un grafo in cui gli archi rappresentano le attività ed i rispettivi nodi rappresentano gli eventi di inizio e fine dell'attività stessa.

Scopo dell'analisi PERT è di determinare il tempo necessario per il completamento del progetto, ossia determinare la durata del progetto minima

Dal momento che ogni arco è caratterizzato da un costo che rappresenta il tempo necessario per completare un attività, la ricerca della durata minima si riconduce alla ricerca del percorso massimo del grafo equivalente.

Le ipotesi/regole principali du un grafo che rappresenta un progetto sono le seguenti:

• non possono esistere attività in parallelo, ossia archi diversi con la stessa origine e la stessa destinazione
• non possono esistere attività del tipo j->i con j>i
• le attività possono apparire al più una sola volta
• non vi possono essere loop

L'analisi PERT si suddivide in due step differenti:

1. Calcolo dei parametri relativi agli eventi
2. Calcolo dei parametri relativi alle attività

Calcolo dei parametri relativi agli eventi

Cominciamo subito con il dire che il grafo grazie al quale riesco a rappresentare un progetto prende il nome di reticolo PERT. Ogni evento può essere rappresentato come un nodo formato da 4 campi:

• Codice dell'evento: indice dell'evento all'interno del reticolo PERT
• Tempo al più presto dell'evento: minimo tempo necessario al verificarsi dell'evento con l'ipotesi che tutte le attività che confluiscono in esso siano terminate
• Tempo al più tardi dell'evento: massimo tempo necessario al verificarsi dell'evento con l'ipotesi che la durata totale del progetto non cambi
• Scorrimento dell'evento: intervallo di tempo che intercorre tra il tempo al più presto e il tempo al più tardi dell'evento; slittamenti del verificarsi dell'evento contenuti all'interno del suo scorrimento non producono incrementi della durata del progetto

Il Tempo al più presto dell'evento inizio progetto si pone generalmente a 0, il tempo al più presto dell'evento fine progetto corrisponde alla durata minima del progetto

Il Tempo al più tardi dell'evento fine progetto _______________________

Definiamo Evento Critico un evento a scorrimento nullo. Gli eventi critici devono necessariamente verificarsi entro una durata fissata in quanto un loro slittamento nel tempo, si ripercuote sulla durata del progetto