Introduzione alla RO

Introduzione alla RO
Andrea Scozzari
a.a. 2013-2014
March 4, 2014
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
1 / 15
Cos’ `e la Ricerca Operativa
La Ricerca Operativa ha lo scopo di fornire le basi razionali al processo
decisionale cercando di comprendere e strutturare situazioni complesse al
fine di prevedere il comportamento dei sistemi e migliorarne le prestazioni
sulla base delle risorse e condizioni tecnologiche esistenti.
Institute For Operations Research and the Management Sciences
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
2 / 15
Il problema della dieta
Una dieta prescrive che giornalmente devono essere assimilate quantit`
a predeterminate
di calorie, proteine e calcio, intese come fabbisogni minimi giornalieri, disponendo di
cinque alimenti base (pane, latte, uova, carne, dolce). Tali fabbisogni minimi sono di
2000 calorie, 50 gr. di proteine, 700 mg. di calcio. Dalle tabelle dietetiche si ricavano i
seguenti contenuti di calorie (in cal.), proteine (in gr.), calcio (in mg.) per ogni singola
porzione di ciascun alimento, intendendo come porzione una quantit`
a espressa in
grammi e quindi razionabile.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
3 / 15
Il problema della dieta
I costi (in Euro) e il numero massimo di porzioni tollerate giornalmente
sono i seguenti
Determinare una dieta a costo minimo che soddisfi le prescrizioni richieste
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
4 / 15
Il problema della dieta
Il problema consiste nel determinare le quantit`a (o il numero di porzioni)
di ciascun alimento affinch`e siano soddisfatte le prescrizioni minimizzando
il costo complessivo della spesa. Sia
1. J l’insieme degli alimenti J ={pane, latte, uova, carne, dolce}, |J| = 5
2. I l’insieme dei nutrienti I ={calorie, proteine, calcio} |I | = 3
3. xj , j ∈ J la quantit`
a dell’alimento j da acquistare
4. aij , j ∈ J i ∈ I , la quantit`
a di nutriente i presente in una porzione dell’alimento j
5. bi , i ∈ I , i fabbisogni minimi giornalieri da soddisfare b ={2000 calorie, 50 gr. di
proteine, 700 mg. di calcio}
6. cj , j ∈ J, il costo relativo all’acquisto di una porzione di alimenti j (costo unitario
di acquisto)
7. uj , j ∈ J, il numero massimo di porzioni tollerate giornalmente.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
5 / 15
Il problema della dieta
Il costo complessivo:
2x1 + 3x2
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
6 / 15
Il problema della dieta
Il costo complessivo:
2x1 + 3x2 + 4x3 + 19x4 + 20x5
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
6 / 15
Il problema della dieta
Il costo complessivo:
2x1 + 3x2 + 4x3 + 19x4 + 20x5
Con riferimento al fabbisogno giornaliero di calorie:
110x1 + 160x2 + 180x3 + 260x4 + 420x5
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
6 / 15
Il problema della dieta
Il costo complessivo:
2x1 + 3x2 + 4x3 + 19x4 + 20x5
Con riferimento al fabbisogno giornaliero di calorie:
110x1 + 160x2 + 180x3 + 260x4 + 420x5 ≥ 2000
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
6 / 15
Il problema della dieta
Il costo complessivo:
2x1 + 3x2 + 4x3 + 19x4 + 20x5
Con riferimento al fabbisogno giornaliero di calorie:
110x1 + 160x2 + 180x3 + 260x4 + 420x5 ≥ 2000
4x1 + 8x2 + 13x3 + 14x4 + 4x5 ≥ 50
2x1 + 285x2 + 54x3 + 80x4 + 22x5 ≥ 700
(1)
Il numero di porzioni deve essere (ovviamente) non negativo ma non
superiore al massimo tollerato
0 ≤ x1 ≤ 4
0 ≤ x2 ≤ 8
Andrea Scozzari (a.a. 2013-2014)
0 ≤ x3 ≤ 3
Introduzione alla RO
0 ≤ x4 ≤ 2
0 ≤ x5 ≤ 2
March 4, 2014
6 / 15
Il problema della dieta
Il problema:
min
2x1 + 3x2 + 4x3 + 19x4 + 20x5
110x1 + 160x2 + 180x3 + 260x4 + 420x5 ≥ 2000
4x1 + 8x2 + 13x3 + 14x4 + 4x5 ≥ 50
(2)
2x1 + 285x2 + 54x3 + 80x4 + 22x5 ≥ 700
0 ≤ x1 ≤ 4
0 ≤ x2 ≤ 8
0 ≤ x3 ≤ 3
0 ≤ x4 ≤ 2
0 ≤ x5 ≤ 2
I problemi di questo tipo sono problemi di Programmazione Lineare
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
7 / 15
Il problema della dieta
Il problema nella sua forma pi`
u generale :
P
min
cj xj
j∈J
P
aij xj ≥ bi
i ∈I
(3)
j∈J
0 ≤ xj ≤ uj
Andrea Scozzari (a.a. 2013-2014)
j ∈J
Introduzione alla RO
March 4, 2014
8 / 15
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
9 / 15
Problema di Produzione
Una ditta di mobili produce librerie, tavoli e sedie. Per la produzione
utilizza pannelli di legno, operai assemblatori ed operai rifinitori secondo lo
schema seguente:
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
10 / 15
Problema di Produzione
In ogni giornata lavorativa sono disponibili:
1. 48 pannelli
2. 20 ore di operaio assemblatore
3. 8 ore di operaio rifinitore
Inoltre i prezzi di vendita dei mobili sono i seguenti:
4. Libreria 120 euro
5. Tavolo 60 euro
6. Sedia 40 euro
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
11 / 15
Problema di Produzione
Sapendo che la richiesta di sedie e librerie `e illimitata ma che non pi di 5 tavoli possono
essere venduti, determinare il numero di librerie, tavoli e sedie da produrre in modo da
rendere massimo l’incasso.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
12 / 15
Problema di Produzione
Sapendo che la richiesta di sedie e librerie `e illimitata ma che non pi di 5 tavoli possono
essere venduti, determinare il numero di librerie, tavoli e sedie da produrre in modo da
rendere massimo l’incasso.
incognite o variabili decisionali:
1. x1 numero di librerie prodotte
2. x2 numero di tavoli prodotti
3. x3 numero di sedie prodotte
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
12 / 15
Problema di Produzione
Il problema nella sua forma pi`
u generale :
P
max
pj xj
j∈J
P
aij xj ≤ bi
i ∈I
(4)
j∈J
xj ≥ 0
j ∈J
dove:
J l’insieme dei beni da produrre, J ={librerie, tavoli, sedie}
I l’insieme dei fattori produttivi, I ={pannelli, ore assemblaggio, ore rifinitura}
bi , i ∈ I , disponibilit`
a del fattore produttivo i
aij , i ∈ I j ∈ J, quantit`
a del fattore produttivo i impiegato nella produzione di una unit`
a
del bene j
pj , j ∈ J, profitto derivante dalla vendita di una unit`
a del bene j
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
13 / 15
Problema della pianificazione del personale
Un’azienda deve pianificare i turni lavorativi del proprio personale sulla base di un dato
fabbisogno giornaliero (vedi Tabella). Il contratto prevede che ogni persona deve
lavorare per 5 giorni consecutivi e deve avere 2 giorni di riposo. L’azienda vuole
programmare i turni in modo tale da occupare il numero minimo di lavoratori per
soddisfare il fabbisogno giornaliero.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
14 / 15
Problema della pianificazione del personale
Problema:
decidere il numero di persone da impiegare in modo tale da minimizzare il
numero (costo) totale di lavoratori e contemporaneamente soddisfacendo
le richieste giornaliere
Il costo totale (da minimizzare) associato al piano di assunzione scelto
rappresenta l’obiettivo che si vuole raggiungere.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla RO
March 4, 2014
15 / 15

Download Report