Ricerca operativa

Da Wikipedia, l'enciclopedia libera.

La pagina di discussione contiene dei suggerimenti per migliorare la voce: Ricerca operativa

La ricerca operativa (nota anche come teoria delle decisioni, scienza della gestione o, in inglese, Operational Research e indicata con le sigle RO o OR) fornisce strumenti matematici di supporto alle attività decisionali in cui occorre gestire e coordinare attività e risorse limitate al fine di massimizzare o minimizzare una funzione obiettivo.

La ricerca operativa si occupa di formalizzare un problema in un modello matematico e calcolare una soluzione ottima, quando possibile, o approssimata (detta anche subottima) per esso.

Essa costituisce un approccio scientifico alla risoluzione di problemi complessi, si può ricondurre all'ambito della Matematica Applicata ma presenta forti caratteristiche interdisciplinari relative in prevalenza a Matematica, Informatica, Economia e finanza, Ingegneria ed altre. Inoltre la ricerca operativa ha molte applicazioni commerciali soprattutto negli ambiti economico, infrastrutturale, logistico, militare, della progettazione di servizi e di sistemi di trasporto e nelle tecnologie. Nel caso particolare di problemi di carattere economico, la funzione da massimizzare può coincidere con il massimo profitto ottenibile o con il minor costo da sostenere.

La ricerca operativa riveste un ruolo importante nelle attività decisionali perché permette di operare le scelte migliori per raggiungere un determinato obiettivo rispettando vincoli che sono imposti dall'esterno e non sono sotto il controllo di chi deve compiere le decisioni.

Indice

1 Storia
2 Classificazione
- 2.1 Ottimizzazione
  - 2.1.1 Dualità
  - 2.1.2 Aspetti geometrici della Programmazione Matematica
3 Programmazione Lineare Intera
4 Esempi di problemi
- 4.1 Ottimizzazione
- 4.2 Pianificazione
5 Scopi e metodi
6 Fasi
7 Modelli matematici (problemi di decisione)
8 Algoritmi
9 Voci correlate
10 Collegamenti esterni

[modifica] Storia

La nascita della Ricerca Operativa è dovuta ad esigenze di tipo militare, durante la seconda guerra mondiale.

Immediatamente prima e durante la guerra erano sorti in alcuni Paesi alleati gruppi di ricerca orientati alla soluzione di importanti problemi di ordine strategico e tattico collegati alla difesa nazionale.

Tra il 1935 e il 1937 il Regno Unito lavorò sul progetto del radar come difesa antiaerea, ma era tuttavia importante che fosse efficiente la localizzazione e la successiva intercettazione e rientro a terra dei velivoli inglesi. Apparve quindi indispensabile anzitutto l'ottimizzazione della distribuzione delle apparecchiature radar sul territorio ed, inoltre, che fosse mandato via radio la segnalazione ad opportune località, nacque così il "Boggin Hill Experiment".

A.P. Rowe, soprintendente della "Bawdsey Research Station", nel 1938, nel descrivere in una relazione tecnica conclusiva del progetto, il tipo di attività sviluppata, utilizzò l'espressione "Operational Research".

Nel 1939, Patrick Maynard Stuart Blackett, fisico e professore presso l'Università di Manchester, fu chiamato a costituire un gruppo di ricerca, composto da scienziati e militari, impegnato nella lotta contro i sommergibili tedeschi.

Il successo ottenuto da questo gruppo, passato alla storia, produsse il risultato di moltiplicare, nel Regno Unito e negli altri Paesi alleati, gruppi di ricerca aventi caratteristiche simili.

Si stima che nel corso della seconda guerra mondiale furono complessivamente impegnati, nel Regno Unito, in Canada e negli USA, oltre 700 scienziati; il termine del conflitto dunque determinò una "riconversione" dell'approccio, fino ad allora usato per soli fini bellici, orientandolo verso problematiche di tipo civile (come la localizzazione dei depositi industriali, il mixing di carico di un servizio di autotrasporto).

Nei settori più propriamente civili, la Ricerca Operativa riprese tecniche note nel settore industriale, migliorandole ed arricchendole con l'uso di strumenti matematici e di conoscenze organizzative: si occupò della standardizzazione della produzione, di problemi connessi alla pianificazione e programmazione industriale. Nel Regno Unito la riconversione avvenne prevalentemente nel settore pubblico, con studi relativi ai trasporti ferroviari, stradali ed urbani.

In Italia tali tecniche giunsero, per motivi facilmente intuibili, con una decina di anni di ritardo. Nel 1961, un gruppo di ricercatori, tecnici e dirigenti d'azienda fondò l'AIRO (Associazione Italiana di Ricerca Operativa) avente lo scopo di promuovere studi teorici ed applicazioni pratiche della disciplina.

[modifica] Classificazione

La Ricerca Operativa si divide in numerose sotto-branche. La prima e più importante classificazione distingue tra:

Ottimizzazione (detta anche approccio what-is-best); che si occupa di formalizzare il problema in un modello matematico (tipicamente un modello di Programmazione matematica o un Grafo di flusso) ed individuare per esso una soluzione ottima o subottima.
Simulazione (detta anche approccio what-if); che si occupa di problemi "difficili" da risolvere per ottimalità, spesso NP Ardui. Queste tecniche prevedono la formalizzazione del problema in un modello matematico e la determinazione di "buoni" parametri mediante metodi statistici o di teoria dei giochi.

[modifica] Ottimizzazione

L'ottimizzazione si occupa di problemi formalizzabili come minimizzazione o massimizzazione di una funzione (detta funzione obiettivo) sottoposta a dei vincoli. Un problema di minimizzazione è sempre riconducibile ad un problema di massimizzazione, e viceversa.

Il caso più semplice consiste nel minimizzare una funzione differenziabile senza alcun vincolo; per la risoluzione di questi problemi si utilizzano le tecniche dell'Analisi differenziale. Tipicamente, invece, gli altri casi sono riconducibili ad un modello di Programmazione Matematica, la cui forma generica è:

$\max C(x_1, \dots, x_n)$	(funzione obiettivo)
$\varphi_1 (x_1,\dots,x_n) \leq b_1$
$\dots$	(vincoli)
$\varphi_m(x1, \dots, x_n) \leq b_m$

che rappresenta un problema con n variabili ed m vincoli. I vincoli e l'obiettivo sono funzioni reali a variabili vettoriali e possono anche rappresentare dei vincoli sul valore delle variabili (ad esempio di non negatività o di intergralità). I vincoli e l'obiettivo possono essere lineari, nel qual caso si parla di Programmazione Lineare o PL e il modello generico diventa:

$\max \sum_{i=1}^n c_i x_i$	(funzione obiettivo)
$\sum_{i = 1}^n a_{1,i} x_i \leq b_1$
$\dots$	(vincoli)
$\sum_{i = 1}^n a_{m,i} x_i \leq b_m$

Questo tipo di problemi è di facile soluzione e si utilizzano algoritmi generici (o general-purpose) come quello del simplesso. Tuttavia spesso nelle applicazioni le variabili sono vincolate ad assumere valori binari (nel qual caso si parla di Programmazione-0,1) o interi (Programmazione Lineare Intera o PLI). In questi casi il problema può complicarsi e la soluzione non può essere generica ma si rende necessario lo studio del problema specifico e l'utilizzo di particolari tecniche risolutive come gli algoritmi Branch and Bound o quelli Branch and Cut. In altre applicazioni possono capitare funzioni obiettivo o vincoli non lineari; se questi sono quadratici si parla di Programmazione Quadratica o Ottimizzazione Quadratica, diversamente si parla genericamente di Ottimizzazione non lineare; entrambi questi casi presentano problemi di "difficile soluzione" ed esistono delle tecniche specifiche (come ad esempio il metodo del gradiente).

[modifica] Dualità

Nella teoria dell'ottimizzazione è di fondamentale importanza il concetto di dualità. In questo modo è, inoltre, possibile definire condizioni di ottimalità.

La dualità in Ricerca Operativa può essere interpretata come una corrispondenza tra due problemi formalizzati in un modello di Programmazione lineare. Tipicamente una coppia di problemi duali ha lo stesso valore ottimo di funzione obiettivo (dualità forte) oppure il valore ottimo di un problema rappresenta una limitazione dell'altro. La forma di dualità più importante e più conosciuta è quella che associa due problemi di Programmazione Lineare (dualità lineare); tuttavia esistono anche altri tipi di dualità, ad esempio in presenza di problemi di Programmazione Quadratica si parla di dualità quadratica ed in presenza di problemi di Programmazione Linerare Intera si parla di dualità lagrangiana.

Una tipica coppia di problemi duali lineari è la seguente:

Problema primale	Problema duale
$\max \sum_{i=1}^n c_i x_i$	$\min \sum_{j=1}^m y_j b_j$	(funzione obiettivo)
$\sum_{i = 1}^n a_{1,i} x_i \leq b_1$	$\sum_{j = 1}^m y_j a_{j,1} = c_1$
$\dots$	$\dots$	(vincoli)
$\sum_{i = 1}^n a_{m,i} x_i \leq b_m$	$\sum_{j = 1}^m y_j a_{j,n} = c_n$
	$y_j \geq 0 \qquad j = 1, \dots, m$

In realtà un problema primale può avere differenti formulazioni e per ognuna di essere esiste una diversa formulazione duale, anch'essa equivalente alle altre formulazioni duali. Comunque qualsiasi problema di programmazione lineare può essere ricondotto a questa coppia.

I problemi duali lineari hanno importanti proprietà:

il duale del duale è il primale, cioè riconducendo il problema duale alla forma primale e applicando la corrispondenza di cui sopra si riotterrà una formulazione equivalente del problema primale.
valori obiettivo, i valori ottimi delle funzioni obiettivo dei due problemi sopra coincidono
ottimalità, in Programmazione Lineare esiste un modo per calcolare, data una soluzione (anche non ottima) del problema primale, la corrispondente soluzione duale. Questa proprietà viene utilizzata come procedura di decisione per l'ottimalità delle due soluzioni: se i corrispondenti valori della funzione obiettivo coincidono, la soluzione è ottima.

L'algoritmo del simplesso sfrutta a pieno queste proprietà e lo stesso algoritmo, applicato implicitamente al problema duale, prende il nome di algoritmo del simplesso duale.

[modifica] Aspetti geometrici della Programmazione Matematica

Sebbene le formulazioni introdotte in precedenza siano intuitive e "vicine" agli elementi del dominio del problema da modellare spesso si preferisce dare una formulazione e un'interpretazione geometrica dei problemi e della teoria della Programmazione Matematica.

In questo caso si formula il problema come la minimizzazione, o la massimizzazione, di una funzione (cioè la funzione obiettivo) all'interno di un insieme detto regione ammissibile. Pertanto il caso della Programmazione Lineare diventa la minimizzazione di una funzione lineare all'interno di una regione poliedrale, ovvero definita da una matrice di vincoli lineari:

$\mathcal{P} = \{x \in \mathbb{R}^n: Ax \leq b\}$ .

In questo caso il sistema matriciale che definisce il poliedro è costituito esattamente dai vincoli del problema di programmazione lineare. Pertanto un problema di programmazione lineare è esprimibile come:

max c x

$A x \leq b$

$x \geq 0$

Questo tipo di formulazione è importante sia nell'ambito della programmazione lineare intera e di tutta la programmazione matematica, in quanto permette di studiare bene le proprietà di un problema, sia per definire in maniera semplice ed elegante alcuni aspetti della programmazione lineare. Ad esempio è possibile definire in termini geometrici la condizione di ottimalità di una soluzione. Ogni riga di una matrice individua un vincolo, precisamente un iperpiano che definisce un semispazio che indichiamo con $A i$ . Diciamo $I (x)$ l'insieme dei vincoli attivi di una soluzione, cioè:

$I (x) = {i : A i x = b i}.$

Una soluzione, quindi, può dirsi ottima se e solo se il vettore dei costi appartiene al cono convesso generato dai vincoli attivi, cioè:

$x^* \leq x\quad\forall x \in S \Leftrightarrow c \in \mbox{Cono}(A_{I(x^*)}) \Leftrightarrow c = \sum_{i \in I(x^*)} \lambda_i A_i, \quad\lambda_i \geq 0 \,\forall i \in I(x^*)$ .

Inoltre questa condizione può essere generalizzata per comprendere il caso non lineare. Infatti il vettore dei costi non è altro che il gradiente della funzione obiettivo (costante perché la funzione è lineare) e il cono dei vincoli attivi è il cosiddetto normal cone definito su qualunque insieme.

[modifica] Programmazione Lineare Intera

Un problema di Programmazione Lineare Intera (indicata con la sigla PLI) è un problema di programmazione lineare nel quale le variabili sono vincolate ad assumere valori interi. Un caso particolare, molto frequente, è la cosiddetta programmazione-0,1 o programmazione binaria, nella quale le variabili sono vincolate ad assumere valori binari. Generalmente i problemi di Programmazione Lineare Intera sono NP-Ardui, a meno che non godano della proprietà di integralità (vedi sotto). Questo significa che (a meno che non valga P = NP) molti problemi di PLI richiedono, al caso pessimo, un tempo di computazione della soluzione esponenziale rispetto alla dimensione dei dati in ingresso. In pratica si tratta di problemi "difficili" da risolvere. Tuttavia alcuni di questi problemi, di uso comune nelle applicazioni, sono stati studiati a fondo e oggi esistono delle tecniche che permettono di risolverli in tempo ragionevole nelle applicazioni più comuni. Tipicamente, poi, si cerca di ricondurre la soluzione di un problema di PLI "difficile" a quella di uno facile o già studiato (vedi Rilassamenti ed Euristiche); in questo modo è possibile affrontare una grande varietà di problemi.

La forma generica di un problema di Programmazione Lineare Intera è:

max c x

$A x \leq b$

$x \in \mathbb{Z}^n$

[modifica] Proprietà di integralità

Quando in un problema di PLI si eliminano i vincoli $x \in \mathbb{Z}^n$ si ottiene un problema di Programmazione Lineare detto rilassamento continuo. Se, inoltre, accade che le soluzioni ottime del problema originiario sono anche soluzioni ottime del suo rilassamento continuo si dice che il problema gode della proprietà di integralità.

In effetti la proprietà di integralità riguarda l'insieme ammissibile del problema più che il problema in se. Infatti la funzione obiettivo del rilassamento continuo ha lo stesso valore di quella del problema originario sul suo insieme ammissibile e, inoltre, poiché è un problema di Programmazione Lineare ha sempre una soluzione ottima di vertice. Segue, quindi, che un problema ha la proprietà di integralità se la regione ammissibile del suo rilassamento continuo è "stretta" sull'insieme ammissibile originario; cioè, in termini geometrici, se coincide con il suo inviluppo convesso.

Formalmente, quindi, definiamo l'insieme ammissibile del problema originario come:

$X = \{x \in \mathbb{Z}^n: A x \leq b\}$ ;

e il suo inviluppo convesso come:

$Conv(X) = \{y \in \mathbb{R}^n: y = \sum_{i = 1}^n \lambda_i x_i, x_i \in X, \sum_{i = 1}^n \lambda_i = 1\}$ .

Il problema, quindi, ha la proprietà di integralità se vale:

$\{x \in \mathbb{R}^n: A x \leq b\} = Conv(X)$ .

Regione ammissibile con proprietà di integralità

Nell'immagine accanto è riportata a titolo esemplificativo la rappresentazione grafica della regione ammissibile di un problema a due variabili caratterizzato dai vincoli:

$x_1 + x_2 \leq 3$

$x_1 \leq 2$

$x_2 \leq 2$

$- x_1 \leq 0$

$- x_2 \leq 0$

$x_1, x_2 \in \mathbb{N}$

L'insieme ammissibile orginario è indicato con dei puntini neri e, in grigio, è rappresentato il suo inviluppo convesso. Come si evince la regione definita dai vincoli sopra coincide esattamente con l'inviluppo convesso del problema originale.

La proprietà di integralità è estremamente importante perché ci permette di applicare i metodi semplici e relativamente veloci per la risoluzione di un problema di Programmazione Lineare ad un problema di Programmazione Lineare Intera. In altre parole di fronte ad un problema di PLI che gode della proprietà di integralità è possibile risolvere il suo rilassamento continuo ed ottenere una soluzione ottima per esso. Molti problemi di PLI che godono della proprietà di integralità sono ben conosciuti e molto utilizzati. Come esempio possiamo citare i problemi di flusso di costo minimo (o Min Cost Flow, MCF) e di flusso massimo su di un grafo di flusso e il problema di accoppiamento di costo minimo.

[modifica] Rilassamenti ed Euristiche

Come già ribadito spesso risolvere un problema di Programmazione Lineare intera può essere "difficile"; in questi casi si possono ottenere delle limitazioni superiori ed inferiori del valore ottimo della funzione obiettivo. Questo è molto importante sia perché a volte nelle applicazioni interessa il valore ottimo della funzione obiettivo piuttosto che la soluzione ottima del problema, sia perché conoscere tale valore è fondamentale per utilizzare algoritmi di enumerazione implicita come gli algoritmi Branch and Bound.

Prendiamo, quindi, in considerazione un problema di massimizzazione in Programmazione Lineare Intera, facendo notare che il caso di minimizzazione è assolutamente equivalente.

max c x

$A x \leq b$

$x \in \mathbb{Z}^n$

A partire da questo problema generico è possibile costruire uno o più problemi detti rilassamenti che forniscono una limitazione superiore del valore ottimo della funzione obiettivo. In altre parole il valore ottimo di un rilassamento è maggiore o uguale al valore ottimo del problema originiario; ovviamente questo è di una qualche utilità se il rilassamento è più facile da risolvere del problema originario. Si noti che se avessimo un problema di minimizzazione i rilassamenti fornirebbero una limitazione inferiore del valore ottimo del problema originario, in quanto i rilassamenti calcolano quasi sempre una soluzione non ammissibile per il problema originario e laddove la soluzione ottima di un rilassamento fosse ammissibile anche per il problema originario sarebbe altresì ottima.

In generale un problema di Programmazione Matematica (P^') è un rilassamento di (P) se e solo se la sua regione ammissibile contiene quella di (P) e sulla loro intersezione i valori delle funzioni obiettivo coincidono. In Programmazione Lineare Intera esistono diversi tipi di rilassamenti.

Rilassamento continuo: si ottiene sostituendo ai vincoli di integralità delle variabili dei semplici vincoli di non negatività, oppure eliminandoli del tutto a seconda della struttura del problema; un rilassamento continuo può essere facilmente risolto con le tecniche di soluzione della Programmazione Lineare, inoltre se il problema originario gode della proprietà di integralità è sufficiente a risolvere il problema.
Rilassamento per eliminazione di vincoli: Si studia la struttura del problema e si individuano i vincoli complicanti, vale a dire i vincoli senza i quali il problema è facilmente risolvibile, e si eliminano. Si noti che il problema così ottenuto non è necessariamente polinomiale ma può essere un problema NP-Arduo di cui si conosce bene la struttura e che si sa affrontare, ad esempio un problema dello zaino.
Rilassamento Surrogato: Si studia la struttura del problema e si aggiunge un vincolo rindondante ottenuto dalla moltiplicazione di alcuni vincoli (chiamati surrogati) per dei coefficienti $π i$ chiamati moltiplicatori surrogati. Successivamente si eliminano i vincoli surrogati, ottenendo così il rilassamento del problema.
Rilassamento Lagrangiano: Si studia la struttura del problema e si individuano i vincoli complicanti, scrivendo quindi il problema come

max c x

$A x \leq b$

$E x \leq d$

$x \in \mathbb{Z}^n$

dove i primi sono i vincoli complicanti, a questo punto si eliminano i vincoli complicanti ma si aggiunge un termine di penalizzazione alla funzione obiettivo pesato secondo un vettore di parametri del rilassamento detto vettore dei moltiplicatori Lagrangiani. Si ottiene quindi il problema seguente indicato con (P_y):

max(c x + y (b - A x)) = y b + max(c - y A) x

$E x \leq d$

$x \in \mathbb{Z}^n$ .

Per ottenere, invece, una limitazione inferiore del valore ottimo della funzione obiettivo si utilizzano delle euristiche; vale a dire algoritmi che calcolano una buona soluzione ma non necessariamente ottima. Tipicamente una buona euristica dovrebbe fornire anche una limitazione teorica dell'errore commesso (lo scarto rispetto alla soluzione ottima), tuttavia non sempre è possibile costruire euristiche supportate da questa proprietà. In qualunque caso le euristiche dipendono strettamente dal problema in esame, pertanto non esiste una tecnica euristica applicabile al problema generico di Programmazione Lineare Intera. Prendono il nome di Euristiche Lagrangiane quelle tecniche ottenute generando una soluzione ammissibile a partire dalla soluzione ottima di un rilassamento Lagrangiano o di un Duale Lagragiano.

[modifica] Dualità Lagrangiana

In presenza di un problema di PLI "difficile" da risolvere spesso si considera un suo rilassamento Lagrangiano (vedi Rilassamenti ed euristiche) tuttavia di solito interessa calcolare il valore del parametro y che permetta di ottenere il miglior valore obiettivo (ovvero, nel caso in cui il problema originale sia un problema di massimizzazione, il valore di y che minimizza z(P_y), valore ottimo del problema (P_y)). Formalizzando questo approccio si ottiene il seguente problema:

$(LD) \min \{y b + \max (c - yA) x: y \geq 0\}$ .

Il problema (LD) prende il nome di Duale Lagrangiano. Se consideriamo il duale lineare del problema (LD) otteniamo il seguente:

$(\tilde{P}) \max \{cx: Ax \leq b, x \in Conv(X)\}$ , dove $X = \{x \in \mathbb{N}^n: Ex \leq d\}$ .

Questo risultato è di fondamentale importanza perché la risoluzione del problema $(\tilde{P})$ può essere molto difficile, soprattutto a causa della difficoltà nel reperire una descrizione poliedrale di Conv(X). Risolvendo (LD), invece, si ottiene il valore ottimo di $(\tilde{P})$ ed è possibile generare una soluzione ottima x^* di $(\tilde{P})$ a partire da una soluzione ottima y^* di (LD).

Sebbene più semplice da risolvere anche il problema (LD) presenta delle difficoltà; infatti non solo la funzione obiettivo non è lineare ma, generalmente, non è nemmeno differenziabile. Tuttavia esistono degli algoritmi studiati a fondo applicabili, tra le altre cose, alla risoluzione di Duali Lagrangiani quali, ad esempio, l'algoritmo dei piani di taglio, gli algoritmi del subgradiente e gli algoritmi Bundle.

[modifica] Esempi di problemi

[modifica] Ottimizzazione

Una fabbrica produce n prodotti i, ognuno dei quali genera un profitto p_i e richiede un certo quantitativo di risorse r_i,j. La fabbrica dispone di una quantità limitata per alcune risorse r_j. Alcuni prodotti non possono essere realizzati in una quantità minore di m_i e non superiore a M_i. Si chiede quali prodotti produrre e in che quantità per ottenere il massimo profitto, rispettando tutti i vincoli.

[modifica] Pianificazione

Immaginando di dover consegnare della merce a n destinatari diversi usando m corrieri, sapendo che ognuno dei destinatari è reperibile soltanto in una determinata fascia oraria e che un corriere non può caricare più di l lotti, individuare i percorsi che devono eseguire i corrieri al fine di minimizzare i chilometri percorsi e consegnare tutti i pacchi.

[modifica] Scopi e metodi

La ricerca operativa consiste nell'applicazione di un metodo scientifico, da parte di gruppi interdisciplinari, a problemi che indicano il controllo dei sistemi organizzati al fine di fornire soluzioni che meglio servano gli scopi dell'organizzazione nel suo insieme. Essa non si sostituisce ai responsabili della decisione ma, fornendo soluzioni dei problemi ottenute con metodi scientifici, permette di effettuare scelte razionali. Può essere utilizzata nella programmazione lineare (pianificazione del problema); nella programmazione dinamica (pianificazione delle vendite); nella teoria delle code (per gestire i problemi di traffico); nella teoria delle scorte (stoccaggio di magazzino); nella teoria dei grafi (utilizzata per le reti di comunicazione); teoria dei giochi (problemi di decisione in condizioni competitive).

[modifica] Fasi

L'elaborazione del problema è suddivisa in passaggi obbligatori ossia:

esame della situazione reale e raccolta delle informazioni;
formulazione del problema: individuazione delle variabili controllabili e non e la scelta della funzione economica da massimizzare o minimizzare;
costruzione del modello matematico, che ha lo scopo di dare una buona rappresentazione del problema; deve essere semplice da utilizzare; rappresentare il problema, fornendo tutte le informazioni per poter assumere una decisione il più idonea possibile;
soluzione del modello (mediante modalità differenti);
analisi e verifica delle soluzioni ottenute: si controlla se la funzione teorica offre vantaggi attesi e si verifichi la rappresentatività del modello;
attuazione della soluzione.

[modifica] Modelli matematici (problemi di decisione)

I modelli matematici sono semplici rappresentazioni della realtà e sono semplicemente descrittivi della stessa; questi tipi di modelli vengono detti iconici. Questi modelli sono più astratti e si esprimono con relazioni matematiche tra le varibili e le grandezze da ottimizzare.

[modifica] Algoritmi

Acuni degli algoritmi utilizzati in ricerca operativa per la programmazione lineare sono:

Algoritmo del simplesso per risolvere problemi di ottimizzazione lineare.
Algoritmo della barriera logaritmica per risolvere i problemi di ottimizzazione convessa.

Alcuni degli algoritmi utilizzati in ricerca operativa per la teoria dei grafo sono:

Algoritmo di Prim o Algoritmo di Kruskal per individuare lo Shortest spanning tree di un grafo.
Algoritmo di Dijkstra per individuare il cammino più breve tra due nodi di un grafo.
Algoritmo di Ford-Fulkerson per individuare il flusso massimo passante tra due punti di una rete
Problema di assegnazione

[modifica] Voci correlate

[modifica] Collegamenti esterni

(IT) Appunti di ricerca operativa a cura dell'Università di Trieste

Estratto da "http://it.wikipedia.org../../../r/i/c/Ricerca_operativa.html"

Categoria: Ricerca operativa

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Ricerca operativa

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Storia

[modifica] Classificazione

[modifica] Ottimizzazione

[modifica] Dualità

[modifica] Aspetti geometrici della Programmazione Matematica

[modifica] Programmazione Lineare Intera

[modifica] Proprietà di integralità

[modifica] Rilassamenti ed Euristiche

[modifica] Dualità Lagrangiana

[modifica] Esempi di problemi

[modifica] Ottimizzazione

[modifica] Pianificazione

[modifica] Scopi e metodi

[modifica] Fasi

[modifica] Modelli matematici (problemi di decisione)

[modifica] Algoritmi

[modifica] Voci correlate

[modifica] Collegamenti esterni

Views

Navigazione

comunità

Ricerca

Altre lingue