Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Pasticceria - 3.11.04 ::
Testo del problema
Una pasticceria rifornisce un centro commerciale di due tipi di lavorati. Gli operai dell’azienda lavorano in tre turni orari (dalle 6 alle 14, dalle 14 alle 22 e dalle 22 alle 6). Il costo della produzione di ogni tipo di lavorato varia da turno a turno, a causa della diversa paga oraria degli operai. Alla fine di ciascun turno, parte dei lavorati prodotti viene trasportata al centro commerciale, parte può essere immagazzinata e trasportata al centro commerciale al termine dei turni successivi. Anche la conservazione dei lavorati nel magazzino, tuttavia, ha un costo.
La produzione di ciascun lavorato richiede l’utilizzo di alcune materie prime, conservate in un magazzino esterno, diverso da quello utilizzato per i lavorati, avente capacità limitata. Il rifornimento di materie prime deve essere effettuato una volta al giorno, all’inizio del primo turno.
La pasticceria deve assicurare una fornitura minima giornaliera complessiva. Inoltre, a causa di convenzioni con i trasportatori, sono fissati dei limiti minimi e massimi alla quantità totale di lavorati trasportabili dalla pasticceria al centro commerciale alla fine di ogni turno.
Pianificare la produzione giornaliera, minimizzando i costi.
Formulare il problema, classificarlo e risolverlo con i dati del file PASTICC.TXT.
Dati
1) Costi di produzione (Euro / Kg)
Turno Lavorato A Lavorato B
1 12 15
2 8 11.5
3 10 12
2) Costi di magazzino (Euro / Kg)
Lavorato A 1.8
Lavorato B 0.4
3) Composizione dei lavorati (percentuale)
Ingrediente Lavorato A Lavorato B
X 20 50
Y 60 10
Z 20 40
4) Volume degli ingredienti (decimetri cubi / Kg)
Ingrediente Volume
X 20
Y 35
Z 15
5) Capacita' del magazzino:
7100 decimetri cubi
6) Fornitura minima per il centro commerciale:
300 Kg
7) Contratto con i trasportatori: limiti di quantita' trasportabili
dopo ogni turno (Kg)
Turno Minimo Massimo
1 65 135
2 70 135
3 50 135
8) Affitto del magazzino:
0.20 Euro / decimetro cubo
9) Aumento della produzione minima:
5 Kg
Formulazione del problema
Dati
- turni = 3 (numero di turni)
- lavorati = 2 (numero di lavorati prodotti)
- mp = 3 (numero di materie prime)
- cProdij (costo di produzione del lavorato i=1..2 nel turno j=1..3) [€]
- cMagi (costo di immagazzinamento del lavorato i=1..2) [€]
- compik (percentuale di materia prima k=1..3 nel lavorato i=1..2) [%]
- volMPk (volume occupato dalla materia prima k=1..3) [dm3/Kg]
- cap = 7100 (capacità del magazzino) [dm3]
- fornMin = 300 (fornitura minima da garantire al centro commerciale) [Kg]
- trMinj (quantità minima di lavorato trasportabile dopo il turno j=1..3) [Kg]
- trMaxj (quantità massima di lavorato trasportabile dopo il turno j=1..3) [Kg]
Variabili
- xij (quantità di lavorato i=1..2 da produrre nel turno j=1..3) [Kg]
- yij (quantità di lavorato i=1..2 da spedire al centro commerciale dopo il turno j=1..3) [Kg]
- zij (quantità di lavorato i=1..2 da mandare in magazzino dopo il turno j=1..3) [Kg]
- wk (quantità di materia prima k=1..3 da comprare) [Kg]
Le variabili sono continue e non negative.
Funzione obiettivo
Dobbiamo minimizzare i costi:
min [(somma)i (somma)j xij * cProdij] + [(somma)i (somma)j zij * cMagi]
Importante: nel contributo della produzione si contano tutti e tre i turni, mentre nel contributo del magazzino solo i primi due turni (perché alla fine del terzo turno il magazzino va svuotato).
Vincoli
- vincolo che impone di spedire una quantità minima di lavorato dopo ogni turno:
(somma)i yij >= trMinj (per ogni j)
- vincolo che impone di spedire una quantità massima di lavorato dopo ogni turno:
(somma)i yij <= trMaxj (per ogni j)
- vincolo sulla produzione minima da garantire al centro commerciale:
(somma)i (somma)j xij >= fornMin
- vincolo di capacità del magazzino:
(somma)i (somma)j zij <= cap
- vincolo che impone che le materie prime utilizzate non superino quelle disponibili:
(somma)i (somma)j compik * xij <= wk (per ogni k)
che va Lindizzato spostando tutti i termini non noti a sinistra, e quindi:
(somma)i (somma)j compik * xij – wk <= 0 (per ogni k)
- vincoli che impongono la conservazione dei lavorati nei vari turni. Nota bene: l'intero contenuto del magazzino deve essere spedito in giornata, quindi entro e non oltre il terzo turno (nulla rimane del giorno prima)
- xi1 – yi1 – zi1 = 0 (per ogni i)
- zi1 + xi2 – yi2 – zi2 = 0 (per ogni i)
- zi2 + xi3 – yi3 = 0 (per ogni i)
Lindizzazione del problema
! esercizio - Pasticceria
! variabili: x(i,j) = quantità di lavorato prodotto al turno j [Kg]
! y(i,j) = quantità di lavorato spedito dopo il turno j [Kg]
! z(i,j) = quantità di lavorato immagazzinato dopo il turno j [Kg]
! w(k) = quantità di materie prime acquistate [Kg]
! le variabili sono continue e non negative
! funzione obiettivo;
min 12 x11 + 15 x12 + 8 x21 + 11.5 x22 + 10 x31 + 12 x32 + 1.8 z11
+ 0.4 z12 + 1.8 z21 + 0.4 z22
st
! vincolo di spedizione minima di lavorato
trMin1) y11 + y12 >= 65
trMin2) y21 + y22 >= 70
trMin3) y31 + y32 >= 50
! vincolo di spedizione massima di lavorato
trMax1) y11 + y12 <= 135
trMax2) y21 + y22 <= 135
trMax3) y31 + y32 <= 135
! vincolo di produzione minima
produz) y11 + y12 + y21 + y22 + y31 + y32 >= 300
! vincolo di capacità del magazzino
capacit) 20 q1 + 35 q2 + 15 q3 <= 7100
! vincolo disponibilità materie prime
dispMP1) 0.2 x11 + 0.2 x21 + 0.2 x31 + 0.5 x12 + 0.5 x22 + 0.5 x32 - q1 <= 0
dispMP2) 0.6 x11 + 0.6 x21 + 0.6 x31 + 0.1 x12 + 0.1 x22 + 0.1 x32 - q2 <= 0
dispMP3) 0.2 x11 + 0.2 x21 + 0.2 x31 + 0.4 x12 + 0.4 x22 + 0.4 x32 - q3 <= 0
! vincolo di conservazione dei lavorati nei vari turni
cons11) x11 - y11 - z11 = 0
cons12) x12 - y12 - z12 = 0
cons21) z11 + x21 - y21 - z21 = 0
cons22) z12 + x22 - y22 - z22 = 0
cons31) z21 + x31 - y31 = 0
cons32) z22 + x32 - y32 = 0
end
Altre domande
Al direttore della pasticceria viene offerto dello spazio per conservare le materie prime in un magazzino adiacente. L’affitto sarebbe di 0.20 euro per ogni decimetro cubo occupato. La proposta è vantaggiosa? Qual’è il massimo volume di magazzino che è utile affittare?
Osservando il report della soluzione, vediamo che il prezzo-ombra del vincolo relativo alla capacità del magazzino è 0.352931:
ROW SLACK OR SURPLUS DUAL PRICES
TRMIN1) 0.000000 -3.100000
TRMIN2) 65.000000 0.000000
TRMIN3) 50.000000 0.000000
TRMAX1) 70.000000 0.000000
TRMAX2) 0.000000 0.900000
TRMAX3) 35.000000 0.000000
PRODUZ) 0.000000 -18.782352
CAPACIT) 0.000000 0.352941
...
Questo vuol dire che la proposta di 0.20 euro per decimetro cubo è quasi la metà di quello che saremmo disposti a pagare, quindi la proposta è assolutamente vantaggiosa. Per poter dire qual è il massimo volume di magazzino che è utile affittare dovremmo invece fare un'analisi parametrica, fissando ad esempio arbitrariamente il valore della capacità a 100000 e vedere cosa succede:
RIGHTHANDSIDE PARAMETRICS REPORT FOR ROW: CAPACIT
VAR VAR PIVOT RHS DUAL PRICE OBJ
OUT IN ROW VAL BEFORE PIVOT VAL
7100.00 0.352941 3208.82
X12 Z21 14 7550.00 0.352941 3050.00
X22 SLK 9 7 8400.00 0.247059 2840.00
100000. 0.000000E+00 2840.00
A quanto pare conviene arrivare a 8400 decimetri cubi totali, quindi affittare 8400 – 7100 = 1300 decimetri cubi.
Il direttore del centro commerciale richiede un aumento della produzione minima garantita di 5 Kg. Che aumento comporterebbe nei costi di produzione? La produzione ottima cambierebbe?
Come si può vedere dall'analisi di sensitività:
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
TRMIN1 65.000000 50.000000 35.000000
TRMIN2 70.000000 65.000000 INFINITY
TRMIN3 50.000000 50.000000 INFINITY
TRMAX1 135.000000 INFINITY 70.000000
TRMAX2 135.000000 12.058824 35.000000
TRMAX3 135.000000 INFINITY 35.000000
PRODUZ 300.000000 5.256410 23.076923
...
La produzione può aumentare di 5.256410 (colonna “allowable increase”) senza che usciamo dalla soluzione ottima. Ovviamente cambierà il valore ottimo, e per scoprire di quanto abbiamo due modi equivalenti: il primo è quello sbrigativo e prevede l'aggiornamento dei dati nel listato in Lindo e la riesecuzione dell'algoritmo risolutivo; il secondo è quello più furbo in generale (non sempre gli algoritmi trovano la soluzione in pochi secondi), e consiste nel controllare il prezzo-ombra relativo al vincolo di produzione e moltiplicarlo per le unità di cui vogliamo incrementarlo. Nel nostro caso il prezzo-ombra vale 18.782352, che moltiplicato per 5 (i 5 kg di cui vogliamo aumentare la produzione) fa 93,91176.
Il responsabile della qualità, inoltre, riferisce che l’aumento della fornitura minima richiesta richiede una modifica al contratto con i trasportatori, che comprenda un incremento della quantità minima trasportata dopo ciascun turno. Il responsabile propone di aumentare la quantità minima trasportabile durante il primo turno, dato che la richiesta dei trasportatori è la meno stringente, portandola da 65 a 70 Kg. Valutare la sua proposta. Come possono essere modificate le quantità minime trasportate in modo che la produzione ottima non cambi?
Aumentare la quantità minima trasportabile dopo il primo turno è l'idea peggiore, perché si tratta dell'unico vincolo attivo:
ROW SLACK OR SURPLUS DUAL PRICES
TRMIN1) 0.000000 -3.100000
TRMIN2) 65.000000 0.000000
TRMIN3) 55.000000 0.000000
La conseguenza di questo aumento è tuttavia solo un aumento del valore ottimo (3318.235), ma non della soluzione ottima. Per sapere fino a quanto possiamo aumentare le quantità minime trasportabili senza che quest'ultima cambi, basta guardare la colonna “allowable increase” dell'analisi di sensitività:
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
MIN1 65.000000 50.000000 35.000000
MIN2 70.000000 65.000000 INFINITY
MIN3 50.000000 50.000000 INFINITY
Torna alla pagina di Ricerca Operativa
