Ricerca Operativa II
prova scritta del 5 febbraio 2001

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, CBA. 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 flusso a costo minimo 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 su reti opportunamente modificato.

Soluzione

Il problema può formularsi ricorrendo a un grafo i cui nodi rappresentino gli stati di lavorazione dei pezzi nei vari turni. 
Si può introdurre un nodo 0 a rappresentare l’inizio dei lavori. Alla fine del I turno su alcuni pezzi sarà stata completata la sola fase A, su altri la sola fase B, e su altri ancora la sola fase C. Ciò dà luogo a tre nodi. 
Alla fine del II turno, tenendo conto delle sequenze di montaggio ammissibili, vi saranno alcuni pezzi su cui saranno state completate le fasi A e B, altri le fasi A e C, altri ancora le fasi B e C: ciò dà luogo a tre nuovi nodi. 
Infine, al termine del III turno vi dovranno essere solo pezzi con tutte e tre le fasi completate. Ciò corrisponde a un unico nodo finale
Le transizioni tra un nodo e l’altro corrispondono agli archi illustrati in figura. Nel grafo risultante, ogni cammino dal nodo 0 al nodo terminale corrisponde a una sequenza ammissibile di fasi di montaggio. Come si vede, il grafo è stratificato, e l’insieme degli archi di ogni strato corrisponde all’insieme di fasi di montaggio che è possibile eseguire in ciascun turno.

0

A

B

C

AB

AC

BC

ABC

A

A

A

B

C

B

C

B

B

C

Ridenominiamo in nodi del grafo in modo da poter individuare ciascun arco per mezzo della coppia dei suoi estremi. Produrre 150 pezzi corrisponde a far transitare un flusso di 150 unità dal nodo 0 al nodo 7. In particolare, far transitare un certo flusso x in un certo arco corrisponde a eseguire su x pezzi la fase associata a quell’arco in quel turno. La distribuzione del flusso nella rete è così soggetta a vincoli di capacità corrispondenti alla disponibilità di manodopera nei diversi turni. Analogamente, il transito di un flusso in un arco comporta il costo dell’esecuzione della fase corrispondente in quel turno. Le capacità e i costi sono riportate nella figura che segue: osserviamo tuttavia che le capacità degli archi 14 e 36 non sono note: infatti questi archi corrispondono all’esecuzione della medesima fase di montaggio (B).

0

1

2

3

4

5

6

7

100, 3

70, 2

20, 1

b2 , 3

20, 2

60, 2

60, 2

b1 , 4

100, 1

100, 2

Il problema può ora formularsi come segue: 
min	3x01 + 2x02 + 2x03 + 4x14 + 2x15 + 2x24 + 3x36 + 2x47 + x57 + x67
	  x01  =  x14 + x15 	  x01  <  100		  x47  <  100
  x02  =  x24 		  x02  <   60		  x57  <  100
	  x03  =  x36 		  x03  <   20		  x67  <   20
	  x14 + x24  =  x47 	  x14 + x36  <   40
	  x15  =  x57 		  x15  <   60
	  x36  =  x67		  x24  <   70
	  x01 + x02 + x03 = 150
	  xij  >  0  per ogni arco ij.

(nel riquadro, i vincoli di capacità). Il problema può essere semplificato eliminando alcune variabili. Ad esempio, le variabili x02, x24 possono essere ridenominate entrambe x04; allo stesso modo, x15 e x57 possono essere ridenominate x17; infine, x03, x36 e x67 possono ridenominarsi x07. Si ottiene così il problema:

min	3x01 + 4x04 + 6x07 + 4x14 + 3x17 + 2x47 
	  x01 – x14 – x17  = 0
  x14 + x04 – x47  = 0	

0

1

4

7

3

4

6

4

3

2

	  x01 + x04 + x07 = 150
  x14 + x07  <   40  
  x04  <   60	
  x17  <  100  
  x01  <  100
  x47  <  100
  x07  <   20
	  x17  <   60
	  x04  <   70
	  xij  >  0  per ogni arco ij.

definito sul grafo di figura (i pesi sugli archi indicano i costi). Per la sua risoluzione si può procedere attribuendo inizialmente l’intera capacità di 40 all’arco 14. La soluzione ottima può quindi essere facilmente ricavata con il metodo del simplesso. Successivamente si può valutare se convenga o no deviare parte del flusso verso l’arco 07 aumentandone la capacità a discapito di 14.