Ricerca operativa

La ricerca operativa (nota anche come teoria delle decisioni, scienza della gestione o, in inglese, operations research ("Operational Research" in Europa) e indicata con le sigle RO o OR) è la branca della matematica applicata in cui problemi decisionali complessi vengono analizzati e risolti mediante modelli matematici e metodi quantitativi avanzati (ottimizzazione, simulazione, ecc.) come supporto alle decisioni stesse. 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.

L'obiettivo è dunque quello di fornire un supporto alla presa di decisioni. Per giungere a questo scopo, la ricerca operativa 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 dunque 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.

Storia

La nascita della ricerca operativa è dovuta ad esigenze di tipo militare, durante la seconda guerra mondiale^[1].

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; tuttavia era 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 mandata via radio la segnalazione ad opportune località, nacque così il "Biggin Hill Experiment". Rowe, soprintendente della "Bawdsey Research Station", utilizzò l'espressione "operational research" nel 1938 in una relazione tecnica conclusiva del progetto per descrivere il tipo di attività sviluppata.

Nel 1939, Blackett 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.

La diffusione della ricerca operativa in Italia fu merito soprattutto di Giuseppe Pompilj che nella seconda metà degli anni '50 collaborò con la Marina Militare, in collegamento con le Forze Armate statunitensi. Pompilj, nel 1961, fu inoltre tra i fondatori dell'AIRO (Associazione italiana di ricerca operativa), tra i quali vanno ricordati anche Benedetto Barberi, allora direttore dell'Istituto nazionale di statistica e Bruno de Finetti e nel 1962 istituì la Scuola di perfezionamento in Ricerca Operativa presso l'Università di Roma.

Il primo problema di ottimizzazione è contenuto nella leggenda della fondazione dell'antica Cartagine da parte di Didone, raccontata nel I libro dell'Eneide. Nell'880 a.C. la regina fenicia Didone, fuggita da Tiro insieme a pochi fedeli, approdò sulle coste settentrionali dell'Africa. Qui chiese a Iarba, re dei Getuli, un appezzamento di terreno su cui costruire una nuova città. Il re, per tutta risposta, le offrì una pelle di toro, dicendole che poteva appropriarsi di tanto terreno quanto poteva comprenderne con quella pelle (“quanto cerchiar di bue potesse un tergo”). L'astuta Didone accettò la sfida. Fece tagliare la pelle in tante strisce sottili ed ottenne una corda con la quale riuscì a delimitare una vasta zona, a forma di semicerchio, affacciata sul mare. È stato calcolato che in questo modo si potrebbe verosimilmente comprendere un semicerchio equivalente per estensione a 15 campi di calcio.

Descrizione

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 programmazione reticolare (gestione progetti); nella teoria delle code (per gestire i problemi di traffico); nella teoria delle scorte (stoccaggio di magazzino); nella teoria dei grafi (utilizzata ad esempio per le reti di telecomunicazione); nella teoria dei giochi (problemi di decisione in condizioni competitive).

Fasi

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

• esame della situazione reale e raccolta delle informazioni (nelle imprese la fonte d'informazione è la contabilità industriale);
• formulazione del problema: individuazione delle variabili controllabili e non controllabili; scelta della funzione economica da ottimizzare (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;
• applicazione della soluzione.

Modelli teorici e Sistemi reali

Lo scopo di un modello è sempre quello di rappresentare un sistema reale, quindi i modelli sono semplici rappresentazioni della realtà e spesso sono semplicemente descrittivi della stessa; questi tipi di modelli vengono detti iconici o, come nella cosiddetta topologia, "analogici". Quando invece il modello è a carattere "risolutivo", come accade nei cosiddetti "problemi di decisione", che sono tipicamente alla base dei problemi di Ricerca Operativa, si ricorre ai cosiddetti "modelli simbolici", che sono più astratti e si esprimono con relazioni matematiche tra le variabili e le grandezze da ottimizzare, per questo vengono definiti normalmente "modelli matematici". In questo caso la maggiore difficoltà, che poi è anche il pregio del modello, consiste nel selezionare le variabili rilevanti escludendo quelle ritenute secondarie. Infatti in ultima analisi il modello è sempre una semplificazione della realtà, che è influenzata da un numero di variabili così elevato da rendere impossibile giungere all'individuazione di una soluzione ottimale. Va però sempre ricordato che l'ultima fase della Ricerca Operativa, vale a dire l'attuazione della soluzione, è di norma al di fuori della portata dell'esperto di Ricerca operativa, che si limita a comunicare il risultato della sua Ricerca al committente (imprenditore o responsabile istituzionale). Ciò nulla toglie alla validità di questo metodo per affrontare e risolvere anche problemi cosiddetti "triviali", cioè di scelta individuale di tutti i tipi: fare la spesa, organizzare il proprio tempo libero o di lavoro, finanza personale.

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 Grafico 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.
• processi stocastici che si occupa di realizzare modelli probabilistici al fine di determinare i comportamenti dei sistemi. Questa branca risulta essere alla base dell'ingegneria finanziaria e dell'ottimizzazione stocastica.

Ottimizzazione

Lo stesso argomento in dettaglio: Ottimizzazione (matematica).

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 è:

${\displaystyle \max C(x_{1},\dots ,x_{n})}$	(funzione obiettivo)
${\displaystyle \varphi _{1}(x_{1},\dots ,x_{n})\leq b_{1}}$
${\displaystyle \dots }$	(vincoli)
${\displaystyle \varphi _{m}(x_{1},\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 integralità). I vincoli e l'obiettivo possono essere lineari, nel qual caso si parla di programmazione lineare o PL e il modello generico diventa:

${\displaystyle \max \sum _{i=1}^{n}c_{i}x_{i}}$	(funzione obiettivo)
${\displaystyle \sum _{i=1}^{n}a_{1,i}x_{i}\leq b_{1}}$
${\displaystyle \dots }$	(vincoli)
${\displaystyle \sum _{i=1}^{n}a_{m,i}x_{i}\leq b_{m}}$

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).

Dualità

Lo stesso argomento in dettaglio: Problema primale standard § Algebra della PL.

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 lineare intera si parla di dualità lagrangiana.

Una tipica coppia di problemi duali lineari è la seguente:

Problema primale standard	Problema duale standard
${\displaystyle \max \sum _{i=1}^{n}c_{i}x_{i}}$	${\displaystyle \min \sum _{j=1}^{m}y_{j}b_{j}}$	(funzione obiettivo)
${\displaystyle \sum _{i=1}^{n}a_{1,i}x_{i}\leq b_{1}}$	${\displaystyle \sum _{j=1}^{m}y_{j}a_{j,1}=c_{1}}$
${\displaystyle \dots }$	${\displaystyle \dots }$	(vincoli)
${\displaystyle \sum _{i=1}^{n}a_{m,i}x_{i}\leq b_{m}}$	${\displaystyle \sum _{j=1}^{m}y_{j}a_{j,n}=c_{n}}$
	${\displaystyle y_{j}\geq 0\qquad j=1,\dots ,m}$

In realtà un problema primale può avere differenti formulazioni e per ognuna di esse 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.

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:

${\displaystyle {\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:

${\displaystyle {\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\geq 0\end{cases}}\end{array}}}$

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 ${\displaystyle A_{i}}$. Diciamo ${\displaystyle I(x)}$ l'insieme dei vincoli attivi di una soluzione, cioè:

${\displaystyle 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è:

${\displaystyle 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.

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 è:

${\displaystyle {\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}}$

Proprietà di integralità

Quando in un problema di PLI si eliminano i vincoli ${\displaystyle x\in \mathbb {Z} ^{n}}$ si ottiene un problema di programmazione lineare detto rilassamento continuo. Se, inoltre, accade che le soluzioni ottime del problema originario 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 sé. 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:

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

e il suo inviluppo convesso come:

${\displaystyle 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:

${\displaystyle \{x\in \mathbb {R} ^{n}:Ax\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:

${\displaystyle \left\{{\begin{array}{l}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} \end{array}}\right.}$

L'insieme ammissibile originario è 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 il problema del 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.

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.

${\displaystyle {\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}}$

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 originario; 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 ridondante ottenuto dalla moltiplicazione di alcuni vincoli (chiamati surrogati) per dei coefficienti ${\displaystyle \pi _{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

${\displaystyle {\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\Ex\leq d\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}}$

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):

${\displaystyle {\begin{array}{l}\max(\langle c,x\rangle +\langle y,b-Ax\rangle )=\langle y,b\rangle +\max \langle c-yA,x\rangle \\Ex\leq d\\x\in \mathbb {Z} ^{n}\end{array}}}$

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.

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:

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

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

${\displaystyle ({\tilde {P}})\max\{\langle c,x\rangle :Ax\leq b,x\in Conv(X)\}}$,

dove ${\displaystyle X=\{x\in \mathbb {N} ^{n}:Ex\leq d\}}$.

Questo risultato è di fondamentale importanza perché la risoluzione del problema ${\displaystyle ({\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 ${\displaystyle ({\tilde {P}})}$ ed è possibile generare una soluzione ottima x^* di ${\displaystyle ({\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.

Esempi di problemi

Ottimizzazione

Una fabbrica produce n_i prodotti di tipo 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.

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.

Schedulazione

Si vogliono ordinare gli ordini di lavorazione su una medesima macchina in base alle date di consegna richieste dal cliente tenendo conto dell'eventuale tempo di set-up per incominciare la lavorazione del lotto. Il problema di schedulazione, inquadrato nella teoria della schedulazione, viene risolto ricorrendo alla programmazione lineare: si tratta di trovare la permutazione ottimale delle righe d'ordine in modo da rispettare il più possibile le date di consegna richieste dal cliente e in caso di ritardo, in modo da minimizzare i giorni di ritardo. La sequenza trovata tiene conto anche dei tempi di set-up facendo in modo di lavorare in successione lotti che richiedono lo stesso attrezzaggio.

Algoritmi

Alcuni 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 grafi sono:

• Algoritmo di Prim o algoritmo di Kruskal per individuare il minimum spanning tree di un grafo.
• Algoritmo di Dijkstra per individuare il cammino più breve tra due nodi di un grafo pesato con pesi non negativi.
• Algoritmo di Bellman-Ford per individuare il cammino più breve tra due nodi di un grafo pesato; meno efficiente del precedente, ma funzionante anche con pesi negativi.
• Algoritmo di Ford-Fulkerson per individuare il flusso massimo passante tra due punti di una rete.
• Problema di assegnazione.

Note

1. Australian War Memorial, WWII, CHAPTER 8 - BOMBER COMMAND: JUNE 1941 TO FEBRUARY 1942 (PDF), su awm.gov.au. URL consultato il 27 giugno 2013. pag. 177

Bibliografia

• (EN) Aleksei D. Korshunov ed. (1996): Discrete Analysis and Operation Research, Kluwer, ISBN 0-7923-3866-9
• (EN) William Greenberg, Jacek Polewczak (1991): Modern Mathematical Methods in Transport Theory, Birkhäuser, ISBN 3-7643-2571-2
• (EN) Frederick S. Hillier, Gerald J. Lieberman: Introduction to Operations Research, McGraw-Hill Professional, ISBN 0-07-301779-5
• Mario Volpato, Studi e modelli di ricerca operativa, Torino, UTET, 1971.
• David Carfì, Fondamenti di teoria delle decisioni. Teoria dei preordini e applicazioni, Antipodes, 2012. ISBN 978-88-96926-10-9

Voci correlate

• Problema di localizzazione
• Associazione italiana di ricerca operativa
• Elenco di voci sulla ottimizzazione
• Progetto:Matematica/Elenco di algoritmi di ottimizzazione
• Teoria dei Giochi

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «ricerca operativa»
• Wikimedia Commons contiene immagini o altri file sulla ricerca operativa

Collegamenti esterni

• Operativa, ricerca, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Aldo Ruscitti, OPERATIVA, RICERCA, in Enciclopedia Italiana, IV Appendice, Istituto dell'Enciclopedia Italiana, 1979.
• Francesco BRAMBILLA e Giuseppe POMPILJ, OPERATIVA, RICERCA, in Enciclopedia Italiana, III Appendice, Istituto dell'Enciclopedia Italiana, 1961.
• Lucio Bianco e Mario Lucertini, OPERATIVA, RICERCA, in Enciclopedia Italiana, V Appendice, Istituto dell'Enciclopedia Italiana, 1993.
• Ricerca operativa, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• Ricerca operativa, in Dizionario di Economia e Finanza, Istituto dell'Enciclopedia Italiana, 2012.
• (EN) Samuel Eilon, Morris Tanenbaum, Russell L. Ackoff e William K. Holstein, operations research, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Operations Research, su MathWorld, Wolfram Research.
• Associazione italiana di ricerca operativa, su airo.org.
• Associazione europea delle società di ricerca operativa, su euro-online.org.
• (EN) Associazione internazionale delle società di ricerca operativa, su ifors.org.
• (EN) Associazione americana di Ricerca Operativa e Management Science, su informs.org.
• Appunti di ricerca operativa a cura dell'Università di Trieste, su univ.trieste.it. URL consultato il 29 giugno 2006 (archiviato dall'url originale il 20 marzo 2007).
• Appunti di ricerca operativa a cura dell'Università di Pisa, facoltà d'informatica, su di.unipi.it. URL consultato il 5 luglio 2007 (archiviato dall'url originale il 17 maggio 2008).

Controllo di autorità	Thesaurus BNCF 7400 · LCCN (EN) sh85095020 · GND (DE) 4043586-6 · BNF (FR) cb11941329g (data) · J9U (EN, HE) 987007548425405171

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica