Esercitazione n
o7 per il corso di Ricerca Operativa
Modello di miscelazione Il problema `e stato tratto dal libro
W. L. Winston. ”Operations Research, Application and Algorithms”, 4th Edition, Thomson Learning, 2004, ISBN: 0-534-38058-1, page 86.
Un problema di miscelazione Una azienza produce tre tipi di gasolio (gas 1, gas 2, gas 3). Ciascuno dei tre tipi di gasolio `e ottenuto per miscelazione di tre tipi di oli grezzi (crude 1, crude 2, crude 3). I prezzi di vendita/acquisto al barile di ciascun gasolio/olio grezzo sono i seguenti:
prezzi di vendita al barile prezzi di acquisto al barile
Gas 1 $70 Crude 1 $45
Gas 2 $60 Crude 2 $35
Gas 3 $50 Crude 3 $25
L’azienda pu`o acquistare fino a 5000 barili di ogni tipi di olio grezzo.
I tre tipi di gasolio differiscono nel numero di ottani e nel contenuto di zolfo.
Gli olii grezzi miscelati per realizzare il gas 1 devono avere un numero di ottani medio di almeno 10 e contenere al pi`u l’1% di zolfo. Gli olii grezzi miscelati per realizzare il gas 2 devono avere un numero di ottani medio di almeno 8 e contenere al pi`u il 2% di zolfo. Gli olii grezzi miscelati per realizzare il gas 3 devono avere un numero di ottani medio di almeno 6 e contenere al pi`u il 1% di zolfo. Il numero di ottani e il contenuto di zolfo dei tre tipi di olii grezzi sono:
numero di ottano contenuto zolfo
Crude 1 12 0.5%
Crude 2 6 2.0%
Crude 3 8 3.0%
La produzione di un barile di gasolio costa $4 e l’azienda `e in grado di produrre fino a 14,000 barili di gasolio giornalieri. I clienti richiedono le seguenti quantit`a di ogni tipo di gasolio: gas 1- 3000 barili/giorno, gas 2- 2000 barili/giorno, and gas 3- 1000 barili/giorno. L’azienda considera un obbligo il soddisfacimento della domanda.
Inoltre l’azienda ha la possibilit`a di fare pubblict`a per stimolare l’acquisto di suoi prodotti. Per ogni dollaro speso giornalmente per la pubblicit`a di un certo tipo di gasolio, la domanda giornaliera di quel tipo di gasolio aumenta di 10 barili. Ade sempio, se l’azienda decide di spendere $20 gionealieri per la pubblicit`a di gas 2, la domanda giornaliera di gas 2 aumenta di 20(10) = 200 barili. Formulare un modello di PL che consenta di massimizzare il profitto (=ricavo-costi).
Analisi sintetica del problema.
prezzo prezzo domanda al pi`u almeno vendita produzione barile
zolfo Ottani $/barile $/barile giorno GAS variabili di decisione
1% 10 70 4 3000 1 X11 X12 X13 A1
2% 8 60 4 2000 2 X21 X22 X23 A2
1% 6 50 4 1000 3 X31 X32 X33 A3
OLIO GREZZO 1 2 3
prezzo acquisto $/barile 45 35 25 olio disponibile, max barile/giorno 5000 5000 5000
numero di ottani 12 6 8 contenuto di zolfo 0.5% 2.0% 3.0%
* per ogni tipo di gasolio: 1 $ al giorno aumenta la domanda di 10 barili/giorno
* Max quantit`a di gasolio da produrre 14000 barili/giorno.
Formulazione.
Consideriamo inizialmente il caso in cui non si prevede di poter investire in pubblicit´a.
– Variabili di decisione. Associamo le variabili di decisione Xij alle quantit`a barili di olio grezzo di tipo j utilizzati per la produzione del gasolio di tipo i (i = 1, 2, 3; j = 1, 2, 3).
Sulla base di tale definzione `e possibile ricavare l’espressione analitica delle quantit`a di diversi gasolii realizzati e di olii utilizzati.
• Olioj per j = 1, 2, 3 utilizzato = X3
i=1
Xij
• Gasi per i = 1, 2, 3 prodotto = X3 j=1
Xij
– Funzione obiettivo. Si vuole max il profitto Z = ricavo -costiP
#gas (ricavo)gasi * (quantit`a di gas)gasi -P
#gas costi di produzione)gasi
* (quantit`a di gas)gasi -P
#olii( costi di acquisto)olioj * (quantit`a di olio usato )olioj.
Dunque si ottiene:
X3 i=1
(ricavo - costi di produzione)i∗gasi= (70−4) X3 j=1
X1j+(60−4) X3 j=1
X2j+(50−4) X3 j=1
X3j
X3
(costi di acquisto) ∗ olioj = 45 X3
Xi1+ 35 X3
Xi2+ 25 X3
Xi3
Da cui si ottiene l’espressione della funzione obiettivo:
max Z = 21X11+11X12+1X13+31X21+21X22+11X23+41X31+31X32+21X33
– Vincoli.
Vincoli di domanda sui Gas 1, 2, 3
C1 : 1X11+ 1X12+ 1X13= 3000 C2 : 1X21+ 1X22+ 1X23= 2000 C3 : 1X31+ 1X32+ 1X33= 1000 Vincoli di disponibilit`a di Olio 1, 2, 3:
C4 : 1X11+ 1X21+ 1X31≤ 5000 C5 : 1X12+ 1X22+ 1X32≤ 5000 C6 : 1X13+ 1X23+ 1X33≤ 5000 Vincoli di produzione della raffineria:
C7 : 1X11+ 1X12+ 1X13+ 1X21+ 1X22+ 1X23+ 1X31+ 1X32+ 1X33≤ 14000 Vincoli di qualit`a sul numero medio minimo di ottani nei Gas 1, 2, 3:
(12X11+ 6X12+ 8X13) (X11+ X12+ X13) >= 10 che da luogo al vincolo C8
C8 : 2X11− 4X12− 2X13≥ 0 C9 : 4X21− 2X22≥ 0 C10 : 6X31+ 2X33≥ 0
Vincoli sul massimo contenuto % di zolfo nei Gas 1, 2, 3:
(0.005X11+ 0.02X12+ 0.03X13)/(X11+ X12+ X13) =< 0.01 che d´a luogo al vincolo C11
C11 : −0.005X11+ 0.01X12+ 0.02X13≤ 0 C12 : −0.015X21+ 0.01X23≤ 0
C13 : −0.005X31+ 0.01X32+ 0.02X33≤ 0
Infine si devono considerare i vincoli di non negativit`a Xij ≥ 0, i = 1, 2, 3 j = 1, 2, 3.
La formulazione completa del modello base `e quindi
max 21X11+ 11X12+ 1X13+ 31X21+ 21X22+ 11X23+ 41X31+ 31X32+ 21X33
X11+ X12+ X131= 3000 X21+ X22+ X23= 2000 X31+ X32+ X33= 1000 X11+ X21+ X31≤ 5000 X12+ X22+ X32≤ 5000 X13+ X23+ X33≤ 5000
X11+ X12+ X13+ X21+ X22+ X23+ X31+ X32+ X33≤ 14000 2X11− 4X12− 2X13≥ 0
4X21− 2X22≥ 0 6X31+ 2X33≥ 0
−0.005X11+ 0.01X12+ 0.02X13≤ 0
−0.015X21+ 0.01X23≤ 0
−0.005X31+ 0.01X32+ 0.02X33≤ 0 Xij ≥ 0, i = 1, 2, 3 j = 1, 2, 3
Supponiamo ora di inserire la possibilit´a di investire in pubblicit´a. Si tratta di individuare le nuove variabili di decisione e verificare come cambia la formu- lazione.
– Variabili di decisione. Si agiungono le variabili Ai = euro spesi giornalmente per la pubblicit`a per il gasolio di tipo i (i = 1, 2, 3);
– Funzione obiettivo. nella funzione obiettivo si deve considerare anche un costo di pubblicit`a (da sottrarre al profitto)
costi pubblicit`a = A1+ A2+ A3
– Vincoli.
I vincoli che sono modificati sono quelli relativi alla domanda. L’investimento in pubblicit`a consente di aumenatare la richiesta effettiva
X11+ X12+ X13= 3000 + 10A1
X21+ X22+ X23= 2000 + 10A2
X31+ X32+ X33= 1000 + 10A3
Il resto dei vincoli generali ´e invariato.
Infine si devono considerare i vincoli di non negativit`a: Aj≥ 0, j = 1, 2, 3.
La formulazione completa `e quindi
max 21X11+ 11X12+ 1X13+ 31X21+ 21X22+ 11X23+ 41X31+ 31X32+ 21X33− A1− A2− A3
X11+ X12+ X131− 10A1= 3000 X21+ X22+ X23− 10A2= 2000 X31+ X32+ X33− 10A3= 1000 X11+ X21+ X31≤ 5000
X12+ X22+ X32≤ 5000 X13+ X23+ X33≤ 5000
X11+ X12+ X13+ X21+ X22+ X23+ X31+ X32+ X33≤ 14000 2X11− 4X12− 2X13≥ 0
4X21− 2X22≥ 0 6X31+ 2X33≥ 0
−0.005X11+ 0.01X12+ 0.02X13≤ 0
−0.015X21+ 0.01X23≤ 0
−0.005X31+ 0.01X32+ 0.02X33≤ 0 Xij ≥ 0, i = 1, 2, 3 j = 1, 2, 3 Aj ≥ 0, j = 1, 2, 3
