Un enigma in fabbrica

Nella fabbricazione di alcuni prodotti, certe fasi di montaggio possono essere liberamente eseguite in diverse sequenze.

Esaminiamo il caso di un prodotto che richiede 3 fasi di montaggio A, B, C, supponendo che le sequenze di montaggio possibili siano ABC, ACB, BAC. Supponiamo di dover produrre 150 pezzi di questo prodotto in una giornata di lavoro, corrispondente a 3 turni di 8 ore.

Per motivi organizzativi, il trasporto dei semilavorati da un reparto di montaggio a un altro avviene solo a fine turno: ne segue che su ogni pezzo viene eseguita esattamente una fase di montaggio in ogni turno.

Inoltre, in dipendenza dalle necessità di reparti estranei a questa produzione, la disponibilità di operai specializzati nelle varie fasi di montaggio varia turno per turno, e con essa varia in conseguenza il numero di pezzi che è possibile lavorare. La dipendenza tra fasi di montaggio e turni è riportata nella tabella seguente:

Fase	I turno	II turno	III turno
A	100	70	20
B	60	40	100
C	20	60	100

Numero di pezzi eseguibili nei vari turni per ogni fase.

Il costo di una fase di montaggio dipende dalla fase e dal turno secondo la tabella seguente:

Fase	I turno	II turno	III turno
A	3	2	1
B	2	4	1
C	1	2	2

Costo dell’esecuzione su un pezzo di una fase di montaggio nei vari turni.

Formulare in termini di programmazione lineare il problema di produrre tutti i 150 pezzi richiesti

1. assegnando il carico di lavoro delle varie fasi nei vari turni nel rispetto delle disponibilità di manodopera;

2. minimizzando il costo sostenuto per la produzione.

Risolvere il problema impiegando il metodo del simplesso.

Soluzione

Sia x_ij una variabile reale non negativa indicante il numero di pezzi su cui è stata effettuata la fase di montaggio i nel turno j. Il numero di pezzi lavorati nel turno j + 1 dipende

· dalla manodopera disponibile

· dal numero di pezzi lavorati nel turno j

· dalle sequenze di montaggio ammissibili.

Poiché queste ultime sono solo ABC, ACB, BAC, dovrà aversi

x_C2 + x_B2 = x_A1 x_B3 = x_C2

x_A2 = x_B1 x_C3 = x_B2 + x_A2

La scarsità di manodopera comporta i vincoli

x_A1 < 100 x_B1 < 60 x_A2 < 70 x_B2 < 40 x_C2 < 60 x_B3 < 100 x_C3 < 100

D’altra parte, dovendo produrre 150 pezzi, si dovrà imporre

x_B3 + x_C3 = 150.

La funzione costo da minimizzare si scrive

c(x) = 3x_A1 + 2x_B1 + 2x_A2 + 4x_B2 + 2x_C2 + x_B3 + 2x_C3

Eliminate le variabili x_A2 e x_B3, il problema diventa

min 3x_A1 + 4x_B1 + 4x_B2 + 3x_C2 + 2x_C3

x_ij > 0 x_A1 < 100 x_B1 < 60

x_B2 < 40 x_C2 < 60 x_C3 < 100

x_C2 + x_B2 – x_A1 = 0

x_C3 – x_B1 – x_B2 = 0

x_C2 + x_C3 = 150.

Questo problema può essere ulteriormente ridotto osservando che

x_A1 = x_B2 + x_C2 (1)

x_C3 = x_B1 + x_B2 (2)

e che

§ siccome x_B2 < 40, x_C2 < 60 Þ x_B2 + x_C2 < 100, il vincolo x_A1 < 100 può essere rimosso,

§ siccome x_B1 < 60, x_B2 < 40 Þ x_B1 + x_B2 < 100 anche il vincolo x_C3 < 100 può essere rimosso,

Si ricava dunque

min 6x_B1 + 9x_B2 + 6x_C2

x_ij > 0 x_B1 < 60

x_B2 < 40 x_C2 < 60

x_C2 + x_B1 + x_B2 = 150

e la tabella del simplesso si può scrivere

B1	B2	C2
6	9	6	0	0	0	0
1	0	0	1	0	0	60
0	1	0	0	1	0	40
0	0	1	0	0	1	60
1	1	1	0	0	0	150

La tabella non è in forma canonica. Per portarla in forma canonica si può applicare il metodo delle variabili artificiali. E' evidentemente sufficiente introdurre una sola variabile artificiale, e modificare di conseguenza la funzione obiettivo

B1	B2	C2
0	0	0	0	0	0	1	0
1	0	0	1	0	0	0	60
0	1	0	0	1	0	0	40
0	0	1	0	0	1	0	60
1	1	1	0	0	0	1	150

La tabella può essere facilmente portata in forma canonica sottraendo l'ultima riga alla riga 0:

B1	B2	C2
–1	–1	–1	0	0	0	0	–150
1	0	0	1	0	0	0	60
0	1	0	0	1	0	0	40
0	0	1	0	0	1	0	60
1	1	1	0	0	0	1	150

La soluzione può essere migliorata eseguendo successive operazioni di pivot sugli elementi evidenziati in rosso:

B1	B2	C2
0	–1	–1	1	0	0	0	–90
1	0	0	1	0	0	0	60
0	1	0	0	1	0	0	40
0	0	1	0	0	1	0	60
0	1	1	–1	0	0	1	90

B1	B2	C2
0	–1	0	1	0	1	0	–30
1	0	0	1	0	0	0	60
0	1	0	0	1	0	0	40
0	0	1	0	0	1	0	60
0	1	0	–1	0	–1	1	30

B1	B2	C2
0	0	0	0	0	0	1	0
1	0	0	1	0	0	0	60
0	0	0	1	1	1	0	10
0	0	1	0	0	1	0	60
0	1	0	–1	0	–1	1	30

Disponiamo quindi di una soluzione ammissibile di base. Reintegrando la funzione obiettivo originale si ottiene la tabella

B1	B2	C2
6	9	6	0	0	0	0
1	0	0	1	0	0	60
0	0	0	1	1	1	10
0	0	1	0	0	1	60
0	1	0	–1	0	–1	30

che può essere posta in forma canonica sottraendo alla riga 0 la prima riga moltiplicata per 6, la quarta moltiplicata per 9 e la terza moltiplicata per 6.

B1	B2	C2
0	0	0	3	0	3	–990
1	0	0	1	0	0	60
0	0	0	1	1	1	10
0	0	1	0	0	1	60
0	1	0	–1	0	–1	30

Questa soluzione è ottima in quanto i costi ridotti sono tutti > 0 e il problema è di minimizzazione. In conclusione, le lavorazioni di montaggio dovranno essere eseguite come riportato nella seguente tabella

	I turno	II turno	III turno	Totale lavorazioni
A	90	60	0	150
B	60	30	60	150
C	0	60	90	150
Totale nei turni	150	150	150

Ora, tanto per perdere altro tempo, risolviamo anche il problema di trovare una soluzione pessima. In questo caso i costi ridotti indicano che si può tentare di aumentare il valore della funzione obiettivo eseguendo un’operazione di pivot sull’elemento evidenziato. Si ottiene

B1	B2	C2
0	0	0	0	–3	0	–1020
1	0	0	0	–1	–1	50
0	0	0	1	1	1	10
0	0	1	0	0	1	60
0	1	0	0	1	0	40

La soluzione di base ottenuta è x_B1 = 50, x_B2 = 40, x_C2 = 60. Ricordando che x_B3 = x_C2, x_A2 = x_B1, si ricava x_B3 = 60, x_A2 = 50. Le trasformazioni (1)-(2) forniscono inoltre x_A1 = 100, x_C3 = 90. Poiché i coefficienti di costo ridotto risultano non positivi, la soluzione individuata è pessima.