1 Problema del taglio e ottimizzazione dei costi di una falegnameria Corso di Ricerca Operativa anno...

1

Problema del taglio e ottimizzazione dei costi di una falegnameria

Corso di Ricerca OperativaCorso di Ricerca Operativa

anno accademico 2001-2002anno accademico 2001-2002

2

Problema del taglio ottimaleProblema del taglio ottimale

La falegnameria La falegnameria LegnolandiaLegnolandia acquista tavole di legno acquista tavole di legno di lunghezza standard l . Vengono effettuati ordini per di lunghezza standard l . Vengono effettuati ordini per tavole di diversa lunghezza. La falegnameria deve tavole di diversa lunghezza. La falegnameria deve tagliare i semilavorati di partenza in modo da tagliare i semilavorati di partenza in modo da soddisfare gli ordini e minimizzare gli scarti. Ovvero, soddisfare gli ordini e minimizzare gli scarti. Ovvero, poiché gli sfridi sono inutilizzabili, l’obiettivo della poiché gli sfridi sono inutilizzabili, l’obiettivo della falegnameria e’ quello di minimizzare il numero di falegnameria e’ quello di minimizzare il numero di semilavorati di lunghezza standard l necessario per semilavorati di lunghezza standard l necessario per soddisfare l’ordine, cercando le modalità di taglio più soddisfare l’ordine, cercando le modalità di taglio più convenienti.convenienti.

3

Dati:Dati:ii a aijij l lii << l l

l l lunghezza del grezzo di partenza lunghezza del grezzo di partenzamm numero di tagli richiestinumero di tagli richiestin n numero di piani di taglio esaminatinumero di piani di taglio esaminatiaaijij numero di tagli di lunghezza numero di tagli di lunghezza lili che rientrano nel piano di taglio j che rientrano nel piano di taglio j

bbii numero di tagli di lunghezza li ordinatinumero di tagli di lunghezza li ordinati

xxjj numero di semilavorati di partenza tagliati secondo il piano jnumero di semilavorati di partenza tagliati secondo il piano j

Modello MatematicoModello Matematico

minmin z z == jj xxjj

jj a aij ij xxj j >> b bii i = 1,...,mi = 1,...,m

xxj j >> 0 0 j = 1,...,nj = 1,...,n

xxjj I I++ - - 0 0

minmin zz = = 1 x1 x

A x A x >>bb

4

Il titolare si aggiudica una commessa per la Il titolare si aggiudica una commessa per la realizzazione di tutti gli infissi (porte, finestre, realizzazione di tutti gli infissi (porte, finestre, porte-finestre, portoncini esterni) per trenta porte-finestre, portoncini esterni) per trenta villette,comprendenti dieci bivani,dieci trivani e villette,comprendenti dieci bivani,dieci trivani e dieci quadrivani con finiture di lusso.dieci quadrivani con finiture di lusso.

5

In totale, le quantità richieste per ciascuna misura di infisso e del corrispondente In totale, le quantità richieste per ciascuna misura di infisso e del corrispondente telaio, sono:telaio, sono:

Tipo Infisso (H X L) in metri

Telaio (H X L) in metri

Quantità

Finestra

1.40 x 1.20 1.54 x 1.34 40

1.40 x 0.80 1.54 x 0.94 40

1.60 x 1.30 1.74 x 1.44 20

Porta con vetro 2.10 x 0.90 2.17 x 1.04 80

Porta 2.10 x 0.90 2.17 x 1.04 80

2.10 x 0.80 2.17 x 0.94 20

2.10 x 1.30* 2.17 x 1.44 10

Porta finestra 2.35 x 1.00 2.42 x 1.14 40

2.35 x 1.30* 2.42 x 1.44 30

2.20 x 1.20* 2.27 x 1.34 30

Portoncino 2.30 x 1.20 2.44 x 1.34 20

2.35 x 1.40 2.49 x 1.54 10

**a due antea due ante

6

Dati gli spessori degli infissi da realizzare , si Dati gli spessori degli infissi da realizzare , si ritiene opportuno impiegare il semilavorato da ritiene opportuno impiegare il semilavorato da cm 5.2 x 15 x 490 , che verrà suddiviso nel cm 5.2 x 15 x 490 , che verrà suddiviso nel senso della larghezza, in modo da ottenere una senso della larghezza, in modo da ottenere una tavola che misura cm 5.2 x 7.5 x 980, per la tavola che misura cm 5.2 x 7.5 x 980, per la realizzazione dei telai, il semilavorato da cm 5.2 realizzazione dei telai, il semilavorato da cm 5.2 x 20.5 x 450 , dal quale si ottiene una tavola da x 20.5 x 450 , dal quale si ottiene una tavola da cm 5.2 x 10.25 x 900 , per gli infissi , e il cm 5.2 x 10.25 x 900 , per gli infissi , e il semilavorato da cm 6.5 x 20 x 490 , per i soli semilavorato da cm 6.5 x 20 x 490 , per i soli portonciniportoncini

7

-- 140 tagli da 2.42 m140 tagli da 2.42 m












Per la produzione dei telai,il falegname dovrà eseguire:Per la produzione dei telai,il falegname dovrà eseguire:

8

Ognuno di questi tagli ha una larghezza di 7 cm e Ognuno di questi tagli ha una larghezza di 7 cm e uno spessore di 5.2 cm.uno spessore di 5.2 cm.A questo punto si tratta di definire un certo A questo punto si tratta di definire un certo numero di piani di taglio, in modo tale che la numero di piani di taglio, in modo tale che la misura totale dei tagli contenuta in ciascun piano misura totale dei tagli contenuta in ciascun piano non superi la lunghezza del semi-lavorato , pari a non superi la lunghezza del semi-lavorato , pari a 9.80 m.9.80 m.Il piano di taglio sarà un vettore con un numero di Il piano di taglio sarà un vettore con un numero di righe pari al numero di tagli differenti che è righe pari al numero di tagli differenti che è necessario produrre, e dunque un vettore 1 x 12 necessario produrre, e dunque un vettore 1 x 12

9

min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15 min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15 +x16+ x17+x18+ x19+x20+x21+x22+x23+x24+x25+x26+x27 +x16+ x17+x18+ x19+x20+x21+x22+x23+x24+x25+x26+x27

+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39

Funzione obiettivo Funzione obiettivo

10

x1+2x2+x7+x9+x11+x14+4x15+3x18+x19+x24+x37+x39 >= 140x1+2x2+x7+x9+x11+x14+4x15+3x18+x19+x24+x37+x39 >= 140x1+5x3+x5+4x8+x17+x18+x20+x23+2x28+x29+x33+3x34+x36+x37 >= 170x1+5x3+x5+4x8+x17+x18+x20+x23+2x28+x29+x33+3x34+x36+x37 >= 170x1+x2+x3+2x8+x11+x14+x20+2x21+2x23+2x28+x30+x37+2x38 >= 130x1+x2+x3+2x8+x11+x14+x20+2x21+2x23+2x28+x30+x37+2x38 >= 130x2+x6+x8+x11+5x14+x18+x20+3x23+x26+2x28+x30+8x32+2x32+x33+4x34+xx2+x6+x8+x11+5x14+x18+x20+3x23+x26+2x28+x30+8x32+2x32+x33+4x34+x35+x36+x39 >= 10035+x36+x39 >= 100x1+x5+x6+x11+x13+3x16+3x20+2x27+x28+2x29+x31+x38+x39 >= 40x1+x5+x6+x11+x13+3x16+3x20+2x27+x28+2x29+x31+x38+x39 >= 40x5+x6+5x9+x13+2x16+x22+2x27+x32+2x33+x35+x36 >= 60x5+x6+5x9+x13+2x16+x22+2x27+x32+2x33+x35+x36 >= 60x1+x2+x4+x6+x11+x16+5x17+x22+x24+6x25+2x27+x33+x34+x39 >= 40x1+x2+x4+x6+x11+x16+5x17+x22+x24+6x25+2x27+x33+x34+x39 >= 40x5+x6+x7+x12+x17+x19+x22+x24+x29 >= 60x5+x6+x7+x12+x17+x19+x22+x24+x29 >= 60x5+x6+x7+x10+x11+x19+2x21+x24+x30+x33+x36+2x37+x38 >= 380x5+x6+x7+x10+x11+x19+2x21+x24+x30+x33+x36+2x37+x38 >= 380x1+x2+x4+x9+x13+x14+x24+x26+x27+7x30+x33+x36+x39 >= 160x1+x2+x4+x9+x13+x14+x24+x26+x27+7x30+x33+x36+x39 >= 1602x4+x7+x10+3x12+x21+x22+x25+x26+2x32+x35 >= 402x4+x7+x10+3x12+x21+x22+x25+x26+2x32+x35 >= 40x4+x10+2x13+x19+x22+x23+2x26+3x31+x32+2x35+x36+x38+x39 >= 20x4+x10+2x13+x19+x22+x23+2x26+3x31+x32+2x35+x36+x38+x39 >= 20

Avente i seguenti vincoliAvente i seguenti vincoli

11

Come possiamo notare esistono 39 variabili Come possiamo notare esistono 39 variabili corrispondenti ai piani di taglio impostati. corrispondenti ai piani di taglio impostati. Naturalmente ciascuno di essi è costituito da un Naturalmente ciascuno di essi è costituito da un numero di tagli tale per cui la somma delle loro numero di tagli tale per cui la somma delle loro misure non superi quella del semilavorato di misure non superi quella del semilavorato di partenza.partenza.I vincoli del problema sono in numero pari a quello I vincoli del problema sono in numero pari a quello dei tagli da produrre:12 e tengono conto del fatto dei tagli da produrre:12 e tengono conto del fatto che la produzione di ciascun taglio deve almeno che la produzione di ciascun taglio deve almeno soddisfare la domanda ad esso associata (i vincoli soddisfare la domanda ad esso associata (i vincoli infatti sono tutti di >=). infatti sono tutti di >=).

12

Implementando su Lindo otteniamo che Il Implementando su Lindo otteniamo che Il numero di grezzi da utilizzare è:numero di grezzi da utilizzare è:

245

13

Il falegname dovrà utilizzare 245 semilavorati di Il falegname dovrà utilizzare 245 semilavorati di partenza dei quali :partenza dei quali :

35 tagliati secondo il piano di taglio x535 tagliati secondo il piano di taglio x5 5 tagliati secondo il piano di taglio x65 tagliati secondo il piano di taglio x6 5 tagliati secondo il piano di taglio x75 tagliati secondo il piano di taglio x7

11 tagliati secondo il piano di taglio x1911 tagliati secondo il piano di taglio x19 23 tagliati secondo il piano di taglio x2123 tagliati secondo il piano di taglio x21 3 tagliati secondo il piano di taglio x223 tagliati secondo il piano di taglio x22 2 tagliati secondo il piano di taglio x242 tagliati secondo il piano di taglio x24 22 tagliati secondo il piano di taglio x3022 tagliati secondo il piano di taglio x30 7 tagliati secondo il piano di taglio x327 tagliati secondo il piano di taglio x32 5 tagliati secondo il piano di taglio x335 tagliati secondo il piano di taglio x33 127 tagliati secondo il piano di taglio x37127 tagliati secondo il piano di taglio x37

14

Il problema presenta 6 slacks fra le quali Il problema presenta 6 slacks fra le quali sicuramente la più interessante è quella in sicuramente la più interessante è quella in corrispondenza del taglio da 1.34 m dove corrispondenza del taglio da 1.34 m dove

assume il valore di 65 .assume il valore di 65 .La presenza della slack indica che c’è un La presenza della slack indica che c’è un esubero di tagli di questo tipo. Starà al esubero di tagli di questo tipo. Starà al

falegname decidere se conservare questi falegname decidere se conservare questi tagli in magazzino in attesa di una nuova tagli in magazzino in attesa di una nuova

commessa o se destinarli alla produzione di commessa o se destinarli alla produzione di un altro prodotto (come il pannello interno un altro prodotto (come il pannello interno

della porta) facente parte della stessa della porta) facente parte della stessa commessa in corso.commessa in corso.

15

FFacendo riferimento agli ordini, per quanto riguarda la acendo riferimento agli ordini, per quanto riguarda la produzione degli infissi, si avranno i seguenti tagli :produzione degli infissi, si avranno i seguenti tagli :
















16

Così come si è proceduto per i telai, occorre Così come si è proceduto per i telai, occorre ora definire dei piani di taglio, ricordando che ora definire dei piani di taglio, ricordando che stiamo considerando il grezzo che misura 9 stiamo considerando il grezzo che misura 9 metri ; dunque la somma delle misure dei tagli metri ; dunque la somma delle misure dei tagli contenuti in ciascun piano di taglio deve essere contenuti in ciascun piano di taglio deve essere minore, o al più uguale , a 9 metri.Il piano di minore, o al più uguale , a 9 metri.Il piano di taglio è ora un vettore 1 x 15 , perché 15 sono i taglio è ora un vettore 1 x 15 , perché 15 sono i tagli differenti da produrre. tagli differenti da produrre.

La funzione obiettivo ed i vincoli relativi al La funzione obiettivo ed i vincoli relativi al problema , sono riportati sotto:problema , sono riportati sotto:

17

min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21 min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21 +x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40 +x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40

Funzione obiettivo Funzione obiettivo

18

x1+x5+2x8+x9+2x12+x13+x17+x18+x19+x24+3x28+x31+x37+x39 >=200x1+x5+2x8+x9+2x12+x13+x17+x18+x19+x24+3x28+x31+x37+x39 >=200

2x2+x3+x9+x13+x14+x16+2x19+2x21+3x25+x27+2x30+2x34+x38+x39 >=1202x2+x3+x9+x13+x14+x16+2x19+2x21+3x25+x27+2x30+2x34+x38+x39 >=120

x2+2x6+x8+2x12+x13+x15+x17+2x22+x25+2x32+3x36+x39 >=400x2+2x6+x8+2x12+x13+x15+x17+2x22+x25+2x32+3x36+x39 >=400

2x4+2x7+x10+x15+x16+x22+3x23+2x27+x32+x33+x39 >=802x4+2x7+x10+x15+x16+x22+3x23+2x27+x32+x33+x39 >=80

4x4+2x7+x11+x13+x15+x17+3x21+x26+2x30+x33+3x35+x36+2x38 >=3204x4+2x7+x11+x13+x15+x17+3x21+x26+2x30+x33+3x35+x36+2x38 >=320

2x2+x6+2x9+2x14+x16+3x18+x23+4x29+x33+x37+3x40 >=802x2+x6+2x9+2x14+x16+3x18+x23+4x29+x33+x37+3x40 >=80

x3+x7+3x10+2x15+x17+x20+2x24+2x26+x30+2x33+2x40 >=4 x3+x7+3x10+2x15+x17+x20+2x24+2x26+x30+2x33+2x40 >=4

x3+2x5+x6+2x9+2x14+x16+4x20+x29+3x32+3x37 >=180x3+2x5+x6+2x9+2x14+x16+4x20+x29+3x32+3x37 >=180

3x1+x3+x5+x6+2x11+x16+x17+2x20+x24+2x27+4x31+x34 >=403x1+x3+x5+x6+2x11+x16+x17+2x20+x24+2x27+4x31+x34 >=40

x3+3x10+x16+2x18+2x20+x24+x26+x29+x31+4x34+x40 >=160x3+3x10+x16+2x18+2x20+x24+x26+x29+x31+4x34+x40 >=160

x1+x3+3x5+2x11+x18+3x22+5x26+x29+x31+2x35+x38 >=80x1+x3+3x5+2x11+x18+3x22+5x26+x29+x31+2x35+x38 >=80

x3+4x6+x7+x9+x13+x16+x18+x19+x22+3x29+x30+2x33+4x37+x38+3x40 >=180x3+4x6+x7+x9+x13+x16+x18+x19+x22+3x29+x30+2x33+4x37+x38+3x40 >=180

5x1+x3+2x7+x10+4x14+x15+x22+x27+x31+3x35+x36+2x37 >=1205x1+x3+2x7+x10+4x14+x15+x22+x27+x31+3x35+x36+2x37 >=120

x3+5x5+2x8+x13+x14+x16+x19+x21+7x23+2x26+3x28+x29+x31+2x33+x40 >=120x3+5x5+2x8+x13+x14+x16+x19+x21+7x23+2x26+3x28+x29+x31+2x33+x40 >=120

x1+x3+2x8+6x11+x15+x17+2x19+x20+3x24+x27+x28+x32+2x35+x36+4x38+x39 >=560x1+x3+2x8+6x11+x15+x17+2x19+x20+3x24+x27+x28+x32+2x35+x36+4x38+x39 >=560

19

Questa volta il numero dei grezzi è:Questa volta il numero dei grezzi è:

368368

20

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 0.000000

3) 0.000000 0.000000

4) 0.000000 0.000000

5) 0.000000 0.000000

6) 0.000000 0.000000

7) 2.000000 0.0000007) 2.000000 0.000000

8) 0.000000 0.000000

9) 0.000000 0.000000

10) 0.000000 0.000000

11) 0.000000 0.000000

12) 17.000000 0.00000012) 17.000000 0.000000

13) 0.000000 0.000000

14) 4.000000 0.00000014) 4.000000 0.000000

15) 5.000000 0.00000015) 5.000000 0.000000

16) 1.000000 0.00000016) 1.000000 0.000000

21

Per quanto riguarda la produzione dei Per quanto riguarda la produzione dei portoncini viene utilizzato il semilavorato da portoncini viene utilizzato il semilavorato da

cm 6.5x20x490.cm 6.5x20x490.Occorrono allora:Occorrono allora:40 tagli da m 2.3040 tagli da m 2.3040 tagli da m 1.2040 tagli da m 1.2020 tagli da m 2.3520 tagli da m 2.3520 tagli da m 1.4020 tagli da m 1.40

22

Il problema associato sarà:Il problema associato sarà:

min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10

x1+x3+2x5+x8 >=40x1+x3+2x5+x8 >=402x2+x3+4x4+2x8+x9+2x10 >=402x2+x3+4x4+2x8+x9+2x10 >=40

x1+x2+2x6 >=20x1+x2+2x6 >=20x3+x4+3x7+2x9+x10 >=20x3+x4+3x7+2x9+x10 >=20

23

Il valore della funzione Il valore della funzione obiettivo è pari a:obiettivo è pari a:

4444

24

Facendo riferimento alla soluzione degli ultimi due Facendo riferimento alla soluzione degli ultimi due problemi affrontati si nota come variando i piani di problemi affrontati si nota come variando i piani di taglio siamo riusciti ad ottenere una soluzione taglio siamo riusciti ad ottenere una soluzione soddisfacente, data la presenza di un numero soddisfacente, data la presenza di un numero limitato di slacks di piccola entità.limitato di slacks di piccola entità.Un altro dato che si rileva è la possibilità di Un altro dato che si rileva è la possibilità di incrementare i termini noti dei vincoli mantenendo incrementare i termini noti dei vincoli mantenendo inalterato il valore della funzione obiettivo. Questo inalterato il valore della funzione obiettivo. Questo fatto ci porterebbe a pensare che sia possibile fatto ci porterebbe a pensare che sia possibile soddisfare una commessa maggiore con lo stesso soddisfare una commessa maggiore con lo stesso numero di grezzi. In realtà il problema è molto più numero di grezzi. In realtà il problema è molto più complesso in quanto ogni singolo infisso è costituito complesso in quanto ogni singolo infisso è costituito da più tagli diversi.da più tagli diversi.

Analisi dei risultatiAnalisi dei risultati

25

Massimizzazione del profitto di una Massimizzazione del profitto di una falegnameriafalegnameria

La falegnameria La falegnameria Legnolandia Legnolandia vuole vuole massimizzare i profitti annuali valutando massimizzare i profitti annuali valutando quale tipologia di infissi produrre e in quale quale tipologia di infissi produrre e in quale quantità,rispettando contemporaneamente la quantità,rispettando contemporaneamente la commessa acquisita nel problema commessa acquisita nel problema precedente.precedente.

26

Il personale della falegnameria è composto da 5 Il personale della falegnameria è composto da 5 operatori di cui 3 addetti alle seguenti macchine:operatori di cui 3 addetti alle seguenti macchine:

• 1 sega radiale O1 sega radiale O11

• 1 troncatrice O1 troncatrice O22

• 1 tecnosquadratrice O1 tecnosquadratrice O33

• 1 levigatrice a nastro O1 levigatrice a nastro O44

• un operatore lavora alla fase di assemblaggio(Oun operatore lavora alla fase di assemblaggio(O55) e ) e uno a quella di verniciatura (Ouno a quella di verniciatura (O66).).

27

La tabella seguente indica : La tabella seguente indica : - i tempi di lavorazione, in ore, di ogni - i tempi di lavorazione, in ore, di ogni macchina su ciascun prodotto macchina su ciascun prodotto - D è la disponibilità della macchina in - D è la disponibilità della macchina in h/anno facendo riferimento a 300 giornate h/anno facendo riferimento a 300 giornate lavorative di 8 h lavorative di 8 h

28

24001.3331.3331.5001.0001.2501.2501.0001.0001.0001.0001.0001.000O6

24002.0002.0003.5000.5832.0002.0000.5830.5830.5830.5000.5000.500O5

18001.0831.0831.6670.8331.0001.0000.8330.8330.8330.6670.6670.667O4

18000.1170.1170.2000.1170.1170.1170.1170.1170.1170.0830.0830.083O3

18000.1170.1170.1500.0830.1170.1170.0670.0670.0670.0330.0330.033O2

18000.1670.1670.3330.1330.1670.1670.0830.0830.0830.0500.0500.050O1

DX12X11X10X9X8X7X6X5X4X3X2X1

29

LeLe varie Xvarie Xii rappresentano il numero di:rappresentano il numero di: XX11 finestra cm 140x120 finestra cm 140x120 XX22 finestra cm 140x180 finestra cm 140x180 XX33 finestra cm 160x130 finestra cm 160x130 XX44 porta-finestra cm 220x120 porta-finestra cm 220x120 XX55 porta-finestra cm 235x130 porta-finestra cm 235x130 XX66 porta-finestra cm 235x100 porta-finestra cm 235x100 XX77 porta interna cm 210x90 porta interna cm 210x90 XX8 8 porta interna cm 210x80porta interna cm 210x80 XX99 porta interna a vetri cm 210x90 porta interna a vetri cm 210x90 XX1010 porta interna a 2 ante cm 210x130 porta interna a 2 ante cm 210x130 XX1111 portoncino cm 230x120 portoncino cm 230x120 XX12 12 portoncino cm 235x140portoncino cm 235x140

30

Qui di seguito vengono Qui di seguito vengono riportati i ricavi, i costi e gli utili riportati i ricavi, i costi e gli utili in € relativi a ciascun prodotto:in € relativi a ciascun prodotto:

31

Ricavi (€) Costi(€) Utili(€)

X1370 111 259

X2 390 117 273

X3430 129 301

X4450 143 307

X5465 148 317

X6410 140 270

X7650 205 445

X8635 200 435

X9500 176 324

X101015 504 511

X111300 500 800

X121800 513 1236

32

Modello matematicoModello matematicofunzione obiettivo:funzione obiettivo:

max max SSjj uujjxxjj j=1….nj=1….n Vincoli:Vincoli:• Di produzione e magazzinoDi produzione e magazzino

Sj aijxj bi i=1….n , j=1….ni=1….n , j=1….n• Di mercatoDi mercato xxj j ddj j j=1….nj=1….n

33

Funzione obiettivoFunzione obiettivo

max 259x1+273x2+301x3+307x4+317x5+270x6+445x7max 259x1+273x2+301x3+307x4+317x5+270x6+445x7

+435x8+324x9+511x10+800x11+1236x12+435x8+324x9+511x10+800x11+1236x12

34

Avente i seguenti vincoli di produzione:Avente i seguenti vincoli di produzione:

0.05x1+0.05x2+0.05x3+0.083x4+0.083x5+0.083x6+0.167x7+0.167x8+0.133x9+0.333x10+0.167x11+0.167x12<=1800

0.033x1+0.033x2+0.033x3+0.067x4+0.067x5+0.067x6+0.117x7+0.117x8+0.083x9+0.150x10+0.117x11+0.117x12<=1800

0.083x1+0.083x2+0.083x3+0.117x4+0.117x5+0.117x6+0.117x7+0.117x8+0.117x9+0.2x10+0.117x11+0.117x12<=1800

0.667x1+0.667x2+0.667x3+0.833x4+0.833x5+0.833x6+1.00x7+1.00x8+0.833x9+1.667x10+1.083x11+1.083x12<=1800

0.5x1+0.5x2+0.5x3+0.583x4+0.583x5+0.583x6+2.00x7+2.00x8+0.583x9+3.50x10+2.00x11+2.00x12<=2400

1.00x1+1.00x2+1.00x3+1.00x4+1.00x5+1.00x6+1.25x7+1.25x8+1.00x9+1.50x10+1.333x11+1.333x12<=2400

35

e di mercato:e di mercato:

x1>=40

x2>=40

x3>=20

x4>=30

x5>=30

x6>=40

x7>=80

x8>=20

x9>=80

x10>=10

x11>=20

x12>=10

36

Implementando la nostra funzione sul software LINDO si Implementando la nostra funzione sul software LINDO si vede come il massimo profitto si ottiene producendo il vede come il massimo profitto si ottiene producendo il bene che assicura il maggior utile possibile (il bene che assicura il maggior utile possibile (il portoncino). Pertanto considerando che le porte a due portoncino). Pertanto considerando che le porte a due ante e i portoncini costituiscono una porzione marginale ante e i portoncini costituiscono una porzione marginale della richiesta di mercato assegnamo un peso in modo della richiesta di mercato assegnamo un peso in modo da penalizzare le variabili corrispondenti nella funzione da penalizzare le variabili corrispondenti nella funzione obiettivo.obiettivo. Dall’ analisi di mercato abbiamo stimato un valore dei Dall’ analisi di mercato abbiamo stimato un valore dei coefficienti correttivi pari a: 0.1 per le porte a due ante, coefficienti correttivi pari a: 0.1 per le porte a due ante, di 0.5 per i portoncini da cm 230x120 e di 0.2 per quelli di 0.5 per i portoncini da cm 230x120 e di 0.2 per quelli da cm 235x140. da cm 235x140.

Analisi dei Analisi dei risultatirisultati

37

Senza inserire i Senza inserire i coefficienti correttivi coefficienti correttivi

abbiamo un profitto di:abbiamo un profitto di:

38

€ € 1.365.6101.365.610

39

Che risulta un po’ ma solo un Che risulta un po’ ma solo un po’ per così dire: po’ per così dire:

“ECCESSIVO”“ECCESSIVO”

40

Con l’introduzione dei coefficienti correttivi il Con l’introduzione dei coefficienti correttivi il nostro problema assume la forma:nostro problema assume la forma:

maxmax 259x1+273x2+301x3+307x4+317x5+270x6+445x7 259x1+273x2+301x3+307x4+317x5+270x6+445x7

+435x8+324x9+511*0.1x10+800*0.5x11+1236*0.2x12+435x8+324x9+511*0.1x10+800*0.5x11+1236*0.2x12

Mentre i vincoli rimangono gli stessi.Mentre i vincoli rimangono gli stessi.

Il profitto ora è diventato di:Il profitto ora è diventato di:

41

€ € 773.560,0773.560,0

42

€ € 773560773560

VARIABLE VALUE REDUCED COSTVARIABLE VALUE REDUCED COST

X1 40.000000 -259.000000X1 40.000000 -259.000000

X2 40.000000 -273.000000X2 40.000000 -273.000000

X3 941.000000 -301.000000X3 941.000000 -301.000000

X4 30.000000 -307.000000X4 30.000000 -307.000000

X5 30.000000 -317.000000X5 30.000000 -317.000000

X6 40.000000 -270.000000X6 40.000000 -270.000000

X7 784.000000 -445.000000X7 784.000000 -445.000000

X8 20.000000 -435.000000X8 20.000000 -435.000000

X9 219.000000 -324.000000X9 219.000000 -324.000000

X10 10.000000 -51.099998X10 10.000000 -51.099998

X11 20.000000 -400.00000X11 20.000000 -400.00000

X12 10.000000 -247.19999X12 10.000000 -247.19999

43

ROW SLACK OR SURPLUS DUAL PRICESROW SLACK OR SURPLUS DUAL PRICES 2) 1568.915039 0.000000 2) 1568.915039 0.000000 3) 1642.352051 0.000000 3) 1642.352051 0.000000 4) 1578.355957 0.000000 4) 1578.355957 0.000000 5) 0.106004 0.000000 5) 0.106004 0.000000 6) 0.522999 0.000000 6) 0.522999 0.000000 7) 0.010002 0.000000 7) 0.010002 0.000000 8) 0.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 9) 0.000000 0.000000 10) 921.000000 0.00000010) 921.000000 0.000000 11) 0.000000 0.000000 11) 0.000000 0.000000 12) 0.000000 0.000000 12) 0.000000 0.000000 13) 0.000000 0.000000 13) 0.000000 0.000000 14) 704.000000 0.00000014) 704.000000 0.000000 15) 0.000000 0.000000 15) 0.000000 0.000000 16) 139.000000 0.00000016) 139.000000 0.000000 17) 0.000000 0.000000 17) 0.000000 0.000000 18) 0.000000 0.000000 18) 0.000000 0.000000 19) 0.000000 19) 0.000000 0.0000000.000000

X3

X7

X9

44

Col nuovo problema abbiamo quindi Col nuovo problema abbiamo quindi una riduzione del profitto.una riduzione del profitto.Da LINDO si nota che, per raggiungere Da LINDO si nota che, per raggiungere il massimo obiettivo bisogna produrre il massimo obiettivo bisogna produrre in più rispetto alla commessa i in più rispetto alla commessa i seguenti infissi:seguenti infissi:

• 921 finestre cm 160x130921 finestre cm 160x130• 139 porte interne a vetri cm 210x90139 porte interne a vetri cm 210x90• 704 porte interne cm 210x90704 porte interne cm 210x90

Ovviamente questi valori corrispondono Ovviamente questi valori corrispondono alle slacks.alle slacks.


45

Vediamo ora la variazione del profitto se si tiene Vediamo ora la variazione del profitto se si tiene conto del fatto che l’azienda possiede un conto del fatto che l’azienda possiede un

magazzino con una disponibilità di 200 mmagazzino con una disponibilità di 200 m33 per per l’accatastamento del prodotto finito. Sotto è l’accatastamento del prodotto finito. Sotto è

riportata la tabella con il volume occupato dai riportata la tabella con il volume occupato dai singoli infissi: singoli infissi:

46

0.2140.214Portoncino cm 235x140Portoncino cm 235x140

0.1800.180Portoncino cm 230x120Portoncino cm 230x120

0.1370.137Porta interna a 2 ante cm 210x130Porta interna a 2 ante cm 210x130

0.0950.095Porta interna a vetri cm 210x90Porta interna a vetri cm 210x90

0.0840.084Porta interna cm 210x80Porta interna cm 210x80

0.0950.095Porta interna cm 210x90Porta interna cm 210x90

0.1170.117Porta finestra cm 235x100Porta finestra cm 235x100

0.1530.153Porta finestra cm 235x130Porta finestra cm 235x130

0.1370.137Porta finestra cm220x120Porta finestra cm220x120

0.1080.108Finestra cm 160x130Finestra cm 160x130



Volume occupato [mVolume occupato [m33]]Tipo di infissoTipo di infisso

47

Il problema avrà la stessa forma con in più il Il problema avrà la stessa forma con in più il vincolo di magazzino che riportiamo sotto:vincolo di magazzino che riportiamo sotto:

0.087x1+0.058x2+0.108x3+0.137x4+0.153x5+0.117x6+0.095x7+0.084x8+0.095x9+0.137x10+0.180x11+0.214x12<=200

i vincoli di produzione e di mercato restano invariati.i vincoli di produzione e di mercato restano invariati.

48

€ € 759616759616

VARIABLE VALUE REDUCED COSTVARIABLE VALUE REDUCED COST X1 40.000000 0.000000 X1 40.000000 0.000000 X2 537.330383 0.000000 X2 537.330383 0.000000 X3 442.991150 0.000000 X3 442.991150 0.000000 X4 30.000000 0.000000 X4 30.000000 0.000000 X5 30.000000 0.000000 X5 30.000000 0.000000 X6 40.000000 0.000000 X6 40.000000 0.000000 X7 784.362549 0.000000 X7 784.362549 0.000000 X8 20.000000 0.000000 X8 20.000000 0.000000 X9 219.235321 0.000000 X9 219.235321 0.000000 X10 10.000000 0.000000 X10 10.000000 0.000000 X11 20.000000 0.000000 X11 20.000000 0.000000 X12 10.000000 0.000000 X12 10.000000 0.000000

49

ROW SLACK OR SURPLUS DUAL PRICESROW SLACK OR SURPLUS DUAL PRICES 2) 1568.857056 0.000000 2) 1568.857056 0.000000 3) 1642.312500 0.000000 3) 1642.312500 0.000000 4) 1578.342407 0.000000 4) 1578.342407 0.000000 5) 0.000000 158.868515 5) 0.000000 158.868515 6) 0.000000 47.082264 6) 0.000000 47.082264 7) 0.000000 111.013580 7) 0.000000 111.013580 8) 0.000000 559.999939 8) 0.000000 559.999939 9) 0.000000 -30.239998 9) 0.000000 -30.239998 10) 497.330383 0.000000 10) 497.330383 0.000000 11) 422.991150 0.000000 11) 422.991150 0.000000 12) 0.000000 -40.519997 12) 0.000000 -40.519997 13) 0.000000 -39.479996 13) 0.000000 -39.479996 14) 0.000000 -66.320000 14) 0.000000 -66.320000 15) 704.362549 0.000000 15) 704.362549 0.000000 16) 0.000000 -3.840001 16) 0.000000 -3.840001 17) 139.235321 0.000000 17) 139.235321 0.000000 18) 0.000000 -621.7622085 18) 0.000000 -621.7622085 19) 0.000000 -115.000198 19) 0.000000 -115.000198 20) 0.000000 -286.840179 20) 0.000000 -286.840179

Vinc. magazzinoVinc. magazzino

50

ROW SLACK OR SURPLUS DUAL PRICESROW SLACK OR SURPLUS DUAL PRICES 2) 1568.915039 0.0000002) 1568.915039 0.000000 3) 1642.352051 0.0000003) 1642.352051 0.000000 4) 1578.355957 0.0000004) 1578.355957 0.000000 5) 0.106004 0.0000005) 0.106004 0.000000 6) 0.522999 0.0000006) 0.522999 0.000000 7) 0.010002 0.0000007) 0.010002 0.000000 8) 0.017001 8) 0.017001 0.0000000.000000 9) 0.000000 0.0000009) 0.000000 0.000000 10) 498.000000 0.00000010) 498.000000 0.000000 11) 423.000000 0.00000011) 423.000000 0.000000 12) 0.000000 0.00000012) 0.000000 0.000000 13) 0.000000 0.00000013) 0.000000 0.000000 14) 0.000000 0.00000014) 0.000000 0.000000 15) 704.000000 0.00000015) 704.000000 0.000000 16) 0.000000 0.00000016) 0.000000 0.000000 17) 139.000000 0.00000017) 139.000000 0.000000 18) 0.000000 0.00000018) 0.000000 0.000000 19) 0.000000 0.00000019) 0.000000 0.000000 20) 0.000000 0.00000020) 0.000000 0.000000

Con la programmazione intera: profitto Con la programmazione intera: profitto € € 759616759616

XX22

XX7 7

XX33

XX99

X2 finestra 140x180 X3 finestra 160x130 X7 porta 210x90 X9 porta interna a vetri 210x90

51

Le macchine OLe macchine O11,O,O22,O,O3 3 non vengono utilizzate non vengono utilizzate per tutto il tempo in cui sono disponibili;mentre per tutto il tempo in cui sono disponibili;mentre si saturano i vincoli relativi alla levigatrice a si saturano i vincoli relativi alla levigatrice a nastro,alle operazioni di assemblaggio e nastro,alle operazioni di assemblaggio e verniciatura e il vincolo di magazzino; tuttavia verniciatura e il vincolo di magazzino; tuttavia quest’ultimo assume il valore più alto tra le quest’ultimo assume il valore più alto tra le variabili duali. Potenziando il magazzino senza variabili duali. Potenziando il magazzino senza alterare gli altri parametri, il profitto dovrebbe alterare gli altri parametri, il profitto dovrebbe aumentare in misura maggiore di quanto aumentare in misura maggiore di quanto accadrebbe lasciandolo invariato e modificando accadrebbe lasciandolo invariato e modificando le disponibilità. le disponibilità.

Analisi dei Analisi dei risultatirisultati

52

Osservazione sulla formulazione adottata per il Osservazione sulla formulazione adottata per il vincolo di magazzinovincolo di magazzino

La disposizione dei pezzi è tale da minimizzare il La disposizione dei pezzi è tale da minimizzare il volume occupato,ma non abbiamo idea di quale sia volume occupato,ma non abbiamo idea di quale sia tale distribuzione ottima,perché ovviamente tale distribuzione ottima,perché ovviamente l’algoritmo non dà risposte in questo senso.Potremmo l’algoritmo non dà risposte in questo senso.Potremmo non riuscire a collocare gli infissi in modo da non riuscire a collocare gli infissi in modo da compattare i volumi e in questo caso il magazzino compattare i volumi e in questo caso il magazzino verrebbe saturato precocemente. verrebbe saturato precocemente.

53

SoluzioneSoluzione

Riformuliamo il vincolo in modo più aderente Riformuliamo il vincolo in modo più aderente ragionando in termini di pezzi e non di ragionando in termini di pezzi e non di volumi,supponendo che il magazzino possa volumi,supponendo che il magazzino possa contenere al massimo 800 pezzi disposti su contenere al massimo 800 pezzi disposti su rastrelliere.rastrelliere.

54

Considerando i pezziConsiderando i pezzi

800800

disposti verticalmentedisposti verticalmente

55

X1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12<=800X1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12<=800

Il vincolo di magazzino diventeràIl vincolo di magazzino diventerà

56


Funzione obiettivoFunzione obiettivo€ € 307.123,0307.123,0

57

€ € 307.123,0307.123,0 VARIABLE VALUE REDUCED COST VARIABLE VALUE REDUCED COST

X1 40.000000 0.000000 X1 40.000000 0.000000 X2 40.000000 0.000000 X2 40.000000 0.000000 X3 20.000000 0.000000 X3 20.000000 0.000000 X4 30.000000 0.000000 X4 30.000000 0.000000 X5 30.000000 0.000000 X5 30.000000 0.000000 X6 40.000000 0.000000 X6 40.000000 0.000000 X7 460.000000 0.000000 X7 460.000000 0.000000 X8 20.000000 0.000000 X8 20.000000 0.000000 X9 80.000000 0.000000 X9 80.000000 0.000000 X10 10.000000 0.000000 X10 10.000000 0.000000 X11 20.000000 0.000000 X11 20.000000 0.000000 X12 1 0.000000 0.000000 X12 1 0.000000 0.000000

58

ROW SLACK OR SURPLUS DUAL PRICESROW SLACK OR SURPLUS DUAL PRICES 2) 1687.560059 0.000000 2) 1687.560059 0.000000 3) 1722.189941 0.000000 3) 1722.189941 0.000000 4) 1708.969971 0.000000 4) 1708.969971 0.000000 5) 1054.199951 0.000000 5) 1054.199951 0.000000 6) 1190.060059 0.000000 6) 1190.060059 0.000000 7) 1465.010010 0.000000 7) 1465.010010 0.000000 8) 0.000000 445.000000 8) 0.000000 445.000000 9) 0.000000 -186.000000 9) 0.000000 -186.000000 10) 0.000000 -172.000000 10) 0.000000 -172.000000 11) 0.000000 -144.000000 11) 0.000000 -144.000000 12) 0.000000 -138.000000 12) 0.000000 -138.000000 13) 0.000000 -128.000000 13) 0.000000 -128.000000 14) 0.000000 -175.000000 14) 0.000000 -175.000000 15) 380.000000 0.00000015) 380.000000 0.000000 16) 0.000000 -10.000000 16) 0.000000 -10.000000 17) 0.000000 -121.000000 17) 0.000000 -121.000000

18) 0.000000 -393.899994 18) 0.000000 -393.899994 19) 0.000000 -45.0000000 19) 0.000000 -45.0000000 20) 0.000000 -197.800003 20) 0.000000 -197.800003

X7

59

380 porte piene 380 porte piene

cm 210x90cm 210x90

Per raggiungere l’ottimo Per raggiungere l’ottimo devo produrre in più devo produrre in più

60

Se teniamo conto Se teniamo conto del flusso in uscitadel flusso in uscita

E del fatto che possiamo simularlo E del fatto che possiamo simularlo con una capacita addizionale pari a:con una capacita addizionale pari a:

60 pezzi 60 pezzi al meseal mese

6060**1212 pezzipezzi

61

Avremo il nuovo vincoloAvremo il nuovo vincolo di magazzinodi magazzino

X1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12<=800+60*12X1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12<=800+60*12

62


Funzione obiettivoFunzione obiettivo€ € 606.106,0606.106,0

Come era in previsione il profitto è aumentato.Come era in previsione il profitto è aumentato.

63

VARIABLE VALUE REDUCED COSTVARIABLE VALUE REDUCED COST

X1 40.000000 -259.000000X1 40.000000 -259.000000

X2 40.000000 -273.000000X2 40.000000 -273.000000

X3 20.000000 -301.000000X3 20.000000 -301.000000

X4 30.000000 -307.000000X4 30.000000 -307.000000

X5 30.000000 -317.000000X5 30.000000 -317.000000

X6 40.000000 -270.000000X6 40.000000 -270.000000

X7 1003.000000 -445.000000X7 1003.000000 -445.000000

X8 20.000000 -435.000000X8 20.000000 -435.000000

X9 257.000000 -324.000000X9 257.000000 -324.000000

X10 10.000000 -51.100000X10 10.000000 -51.100000

X11 20.000000 -400.00000X11 20.000000 -400.00000

X12 10.000000 -247.19999X12 10.000000 -247.19999

64

ROW SLACK OR SURPLUS DUAL ROW SLACK OR SURPLUS DUAL PRICESPRICES

2) 1573.338013 0.0000002) 1573.338013 0.000000 3) 1643.968018 0.0000003) 1643.968018 0.000000 4) 1624.729980 0.0000004) 1624.729980 0.000000 5) 363.759003 0.0000005) 363.759003 0.000000 6) 0.868998 0.0000006) 0.868998 0.000000 7) 609.260010 0.0000007) 609.260010 0.000000 8) 0.000000 0.0000008) 0.000000 0.000000 9) 0.000000 0.0000009) 0.000000 0.000000 10) 0.000000 0.000000 10) 0.000000 0.000000 11) 0.000000 0.00000011) 0.000000 0.000000 12) 0.000000 0.00000012) 0.000000 0.000000 13) 0.000000 0.00000013) 0.000000 0.000000 14) 0.000000 0.00000014) 0.000000 0.000000 15) 923.000000 0.00000015) 923.000000 0.000000 16) 0.000000 0.00000016) 0.000000 0.000000 17) 177.000000 0.00000017) 177.000000 0.000000 18) 0.000000 0.00000018) 0.000000 0.000000 19) 0.000000 0.00000019) 0.000000 0.000000 20) 0.000000 0.00000020) 0.000000 0.000000

X7

X9

XX77 porte piene 210x90 X porte piene 210x90 X9 9 porte vetri 210x90porte vetri 210x90

65

923 porte piene923 porte piene177 porte a vetri177 porte a vetri

Rispetto alla commessa si producono in più:Rispetto alla commessa si producono in più:

66

ROW SLACK OR SURPLUS DUAL PRICESROW SLACK OR SURPLUS DUAL PRICES

2) 1573.317139 0.0000002) 1573.317139 0.000000

3) 1643.947144 0.0000003) 1643.947144 0.000000

4) 1624.729980 0.0000004) 1624.729980 0.000000

5) 363.656586 0.0000005) 363.656586 0.000000

6) 0.0000000 85.3916706) 0.0000000 85.391670

7) 609.106689 0.0000007) 609.106689 0.000000

8) 0.0000000 274.2166448) 0.0000000 274.216644

9) 0.0000000 -57.9124919) 0.0000000 -57.912491

10) 0.0000000 -43.91249110) 0.0000000 -43.912491

11) 0.0000000 -15.91249111) 0.0000000 -15.912491

12) 0.000000 -17.00000012) 0.000000 -17.000000

13) 0.000000 -7.00000013) 0.000000 -7.000000

14) 0.000000 -54.00000014) 0.000000 -54.000000

15) 923.613281 0.00000015) 923.613281 0.000000

16) 0.000000 -10.00000016) 0.000000 -10.000000

17) 176.386734 0.00000017) 176.386734 0.000000

18) 0.000000 -521.98748818) 0.000000 -521.987488

19) 0.000000 -45.00000019) 0.000000 -45.000000

20) 0.000000 -197.80000320) 0.000000 -197.800003

Vincolo di magazzinoVincolo di magazzino

Op. assemblaggioOp. assemblaggio

67

Conclusioni Conclusioni

Analizzando le variabili duali emerge cheAnalizzando le variabili duali emerge cheil beneficio maggiore ai fini dell’ottimizzazioneil beneficio maggiore ai fini dell’ottimizzazione

si ottiene ampliando ulteriormente il magazzinosi ottiene ampliando ulteriormente il magazzinoe assegnando un maggior numero di operatorie assegnando un maggior numero di operatori

alla fase di assemblaggio. alla fase di assemblaggio.

Capitooo ????Capitooo ????

1 Problema del taglio e ottimizzazione dei costi di una falegnameria Corso di Ricerca Operativa anno...

Documents

Transcript of 1 Problema del taglio e ottimizzazione dei costi di una falegnameria Corso di Ricerca Operativa anno...