Università degli studi di Ancona

Facolta di Ingegneria

Corso di Ricerca Operativa

Prof. F. Pezzella

PROBLEMA DI PLANT LOCATION PER UN’AZIENDA DI SERVIZI ALLE INDUSTRIE
















Ciampichetti Daniele ( Matr 220783 )

software utilizzato: LINDO, Excel di Office

(e algoritmo dei trasporti)




INDICE

  1. Descrizione del problema

  2. Calcolo costi unitari di trasporto

  3. Definizione del problema di localizzazione semplice

  4. Modello di plant location per il problema in esame

  5. Calcolo della soluzione ottima

  6. Analisi dei risultati

  7. Limiti della soluzione ottima in condizioni di orari rigidi

  8. Redistribuzione dell’offerta

  9. Definizione del problema dei trasporti

  10. Modello dei trasporti per il problema in esame

  11. Calcolo della nuova soluzione ottima

  12. Analisi dei nuovi risultati e conclusioni



1. DESCRIZIONE DEL PROBLEMA


I clienti di un’azienda di servizi alle industrie (impianti elettrici, servizi informatici, sistemi per l’automazione, ecc ) con 15 dipendenti e sede ad Ancona sono dislocati in modo piuttosto disomogeneo nelle seguenti province: Fo, Rn, Pu, An, Mc, Ap, Te.


La distribuzione della domanda nelle diverse province è espressa in termini di ore lavorative nella seguente tabella ( i valori sono stati calcolati facendo una media degli ultimi 5 anni) per un totale di 600 ore lavorative settimanali, corrispondenti a 40 ore lavorative per ciascun dipendente (8ore x 5 giorni alla settimana):


Fo

Rn

Pu

An

Mc

Ap

Te

60

70

85

135

100

90

60



Il costo di ciascuna ora cresce ovviamente con la distanza che deve percorrere ciascun dipendente per raggiungere il cliente da servire; fermo restando, infatti, che la domanda di 600 ore settimanali deve essere evasa, si tratta di pagare ai dipendenti il tempo del viaggio nonché di provvedere alle spese del trasferimento coi mezzi aziendali.





2. CALCOLO DEI COSTI UNITARI DI TRASPORTO


Come già detto, i vari clienti non sono localizzati nelle vicinanze di ciascun capoluogo, ma distribuiti in modo non uniforme sul territorio di ogni provincia, motivo per cui il calcolo dell’aumento retributivo di ogni singola ora non può essere fatto a partire dalle distanze esatte in km fra i capoluoghi o dai tempi di percorrenza da un capoluogo all’altro, bensì su valori medi; in particolare i costi per clienti di Mc e Pu risultano pressoché uguali, così come per quelli di Rn e Ap e quelli di Te e Fo, perciò è conveniente dividere le province come segue:


  1. province adiacenti ( Mc e Pu )

  2. province per raggiungere le quali è necessario attraversare un’altra provincia ( Rn e Ap )

  3. province per raggiungere le quali è necessario attraversare due province ( Te e Fo )


In altre parole potremmo definire una distanza “fittizia” in modo che, ad esempio d( An, Mc)=1, d(An, Ap)=2 , ecc.


Ai 5 € di salario base vanno quindi sommati i costi aggiuntivi che, riferendoci a valori medi sulla singola ora, sono calcolati come segue :


a) ore straordinarie di trasferimento che, come detto, non vanno computate ai fini del soddisfacimento della domanda di 600 ore settimanali; calcolando che in media un cliente della provincia di Pu o Mc viene raggiunto in mezz’ora, ad ogni 8 ore lavorative se ne deve aggiungere una; due sono invece le ore che ogni 8 vanno aggiunte se il dipendente serve un cliente di Ap o Rn e 3 se il cliente è di Te o Fo. L’espressione del costo aggiuntivo è pertanto


5 € * d / 8 ore


dove d è la distanzia fittizia sopra definita.


b) spese di trasferimento coi mezzi aziendali che, limitandosi al solo carburante, sono in media di 3 € per raggiungere una provincia adiacente, 6 € se d=2 e 9 € se d=3.


calcolando ancora un trasferimento ogni 8 ore il costo aggiuntivo per ogni ora è di 3 € *d / 8 ore

( si potrebbe obiettare che tale ipotesi sottostima il costo: se ad esempio il dipendente impiega 3 ore per raggiungere Te non potranno pretendersi 11 ore di lavoro effettivo e magari le ore utili saranno 6 o 5; tale meccanismo è però compensato ad esempio dal fatto che con lo stesso mezzo aziendale potrebbero viaggiare 2 o 3 dipendenti)


Il costo di ciascuna ora lavorativa in funzione della distanza è riassunto nella seguente tabella:


d=0

d=1

d=2

d=3

5 €

6 €

7 €

8 €


Ovvero in termini di province:


Fo

Rn

Pu

An

Mc

Ap

Te

8 €

7 €

6 €

5 €

6 €

7 €

8 €


Pertanto attualmente l’azienda spende ogni settimana per i salari e per le spese di trasporto:


8*60+7*70+6*85+5*135+6*100+7*90+8*60 = 3865 €


Essendosi la domanda stabilizzata negli ultimi 5 anni e dovendo predisporre un piano aziendale per i prossimi 5, si decide di cercare un aumento degli utili attraverso un servizio più efficiente piuttosto che ampliando ulteriormente la cerchia dei clienti (dato che ciò comporterebbe un ulteriore estensione sul territorio nonché il superamento della soglia dei 15 dipendenti).


L’ipotesi che la domanda nei prossimi 5 anni non si discosti eccessivamente da quella degli ultimi 5 risulta quindi plausibile; le strade attraverso cui si intende ridurre le inefficienze attuali sono la delocalizzazione ,ovvero l’apertura di nuove sedi in province opportune, e , se necessario, il ricorso a orari di lavoro più flessibili (non più necessariamente 40 ore settimanali per ogni dipendente, ma dalle 35 alle 45 a seconda delle esigenze).















3. DEFINIZIONE DEL PROBLEMA DI LOCALIZZAZIONE


Si ha un problema di localizzazione industriale quando assegnati n centri di domanda si vogliono individuare ,fra m possibili impianti di offerta, quelli da attivare in modo da minimizzare il costo totale dovuto al trasporto e alla attivazione stessa degli impianti.


Parliamo di localizzazione semplice quando il modello di programmazione lineare è nella forma:


min z= ΣiΣjcijxij + Σifixi


Σixij =1 j (1)


yi-xij >=0 i,j (2)


xij, yi= 0,1 i,j (3)


dove il significato di parametri e vincoli è il seguente:









Il nome di “localizzazione semplice” è dovuto al fatto che non sono presenti vincoli sulle sorgenti, ovvero si ipotizza che ciascun impianto possa erogare quantità arbitrarie di offerta.

4. MODELLO DI PLANT LOCATION PER IL PROBLEMA IN ESAME


Una preventiva ricerca di locali ritenuti adatti all’attivazione delle nuove sedi ha prodotto prezzi diversi nelle varie province, come riportato nella seguente tabella :


Fo

Rn

Pu

Mc

Ap

Te

40000 €

35000 €

50000 €

40000 €

50000 €

35000 €


Avendo scelto di riferire i costi del lavoro e le spese di trasporto alle ore settimanali ( per una lettura più immediata dei risultati essendo abituale , per le dimensioni dell’azienda e per il tipo di servizio richiesto, organizzare il lavoro settimanalmente ) anche tali valori, che rappresenteranno i costi fissi di attivazione del nostro modello, vanno espressi in termini di “rata settimanale” dovuta all’acquisto dei locali e alle spese annesse (basta dividere tutto per 52*5= 260 ):


Fo

Rn

Pu

Mc

Ap

Te

153 €

134 €

192 €

153 €

192 €

134 €


Gli altri parametri fondamentali del modello sono i costi unitari di trasporto cij, che vanno calcolati come indicato nel paragrafo 2 e che vanno a costituire la matrice seguente:



Fo

Rn

Pu

An

Mc

Ap

Te

Fo

5 €

6 €

7 €

8 €

9 €

10 €

11 €

Rn

6 €

5 €

6 €

7 €

8 €

9 €

10 €

Pu

7 €

6 €

5 €

6 €

7 €

8 €

9 €

An

8 €

7 €

6 €

5 €

6 €

7 €

8 €

Mc

9 €

8 €

7 €

6 €

5 €

6 €

7 €

Ap

10 €

9 €

8 €

7 €

6 €

5 €

6 €

Te

11 €

10 €

9 €

8 €

7 €

6 €

5 €


A rigore , i veri costi “unitari” di trasporto si ottengono in verità dalla matrice precedente moltiplicando ogni colonna per la domanda della destinazione corrispondente; il vincolo xij=0,1 implica infatti che come unità minima di “prodotto” trasportata dalla sede i alla destinazione j si consideri l’intera domanda della sede j-esima (se così non fosse nessuna sede verrebbe attivata; sarebbe come valutare se vale la pena spendere 153€ per attivare una sede a Fo che elargirà una sola ora a 5€ , piuttosto che far arrivare un dipendente dalla sede di An al costo di 8€ ).


E’ proprio tale prodotto che ci restituisce la funzione obiettivo:


min 300x11+420x12+595x13+1080x14+900x15+900x16+660x17+360x21+ 350x22+510x23+945x24+800x25+810x26+600x27+420x31+420x32+425x33+810x34+700x35+720x36+540x37+480x41+490x42+510x43+675x44+600x45+630x46+480x47+540x51+560x52+595x53+810x54+500x55+540x56+420x57+600x61+630x62+680x63+945x64+600x65+450x66+360x67+660x71+700x72+765x73+1080x74+700x75+540x76+300x77+153y1+134y2+192y3+0y4+153y5+192y6+134y7


mentre i vincoli sono quelli di un problema di localizzazione semplice:

x11+x21+x31+x41+x51+x61+x71=1

x12+x22+x32+x42+x52+x62+x72=1

x13+x23+x33+x43+x53+x63+x73=1

x14+x24+x34+x44+x54+x64+x74=1

x15+x25+x35+x45+x55+x65+x75=1

x16+x26+x36+x46+x56+x66+x76=1

x17+x27+x37+x47+x57+x67+x77=1

y1-x11>=0

y1-x12>=0

y1-x13>=0

y1-x14>=0

y1-x15>=0

y1-x16>=0

y1-x17>=0

y2-x21>=0

y2-x22>=0

y2-x23>=0

y2-x24>=0

y2-x25>=0

y2-x26>=0

y2-x27>=0

y3-x31>=0

y3-x32>=0

y3-x33>=0

y3-x34>=0

y3-x35>=0

y3-x36>=0

y3-x37>=0

y4-x41>=0

y4-x42>=0

y4-x43>=0

y4-x44>=0

y4-x45>=0

y4-x46>=0

y4-x47>=0

y5-x51>=0

y5-x52>=0

y5-x53>=0

y5-x54>=0

y5-x55>=0

y5-x56>=0

y5-x57>=0

y6-x61>=0

y6-x62>=0

y6-x63>=0

y6-x64>=0

y6-x65>=0

y6-x66>=0

y6-x67>=0

y7-x71>=0

y7-x72>=0

y7-x73>=0

y7-x74>=0

y7-x75>=0

y7-x76>=0

y7-x77>=0

end




















5. CALCOLO DELLA SOLUZIONE OTTIMA


I software a disposizione per calcolare la soluzione ottima sono il LINDO ed il foglio elettronico EXCEL di OFFICE attraverso la funzione risolutore.


Il LINDO è un programma di ottimizzazione lineare nel quale il modello va scritto con la sintassi appena descritta : st sta per “subject to” ed indica l’inizio dei vincoli cui deve sottostare la funzione obiettivo, mentre “end” indica che i vincoli sono terminati (e con essi il modello).

I vincoli di “binarietà” possono essere indicati variabile per variabile, oppure con il comando “int n” dopo end, che indica al software di riconoscere come binarie le prime n variabili; nel caso in esame è stato omesso il comando in “int 56” per due motivi:




Con il comando “pivot” del menu “solve” si può osservare l’evolversi del valore di z ad ogni passo dell’algoritmo del simplesso, mentre il comando “tableau” consente di visualizzare anche l’evoluzione della matrice M, che tuttavia nel nostro caso non è pensabile per via delle dimensioni del tableau stesso:




X11 ENTERS AT VALUE 0.00000E+00 IN ROW 9 OBJ. VALUE= 0.00000E+00


X77 ENTERS AT VALUE 0.00000E+00 IN ROW 57 OBJ. VALUE= 0.00000E+00


X22 ENTERS AT VALUE 0.00000E+00 IN ROW 17 OBJ. VALUE= 0.00000E+00


X21 ENTERS AT VALUE 0.00000E+00 IN ROW 16 OBJ. VALUE= 0.00000E+00


X67 ENTERS AT VALUE 0.00000E+00 IN ROW 50 OBJ. VALUE= 0.00000E+00


X31 ENTERS AT VALUE 0.00000E+00 IN ROW 23 OBJ. VALUE= 0.00000E+00


X57 ENTERS AT VALUE 0.00000E+00 IN ROW 43 OBJ. VALUE= 0.00000E+00


X12 ENTERS AT VALUE 0.00000E+00 IN ROW 10 OBJ. VALUE= 0.00000E+00


X32 ENTERS AT VALUE 0.00000E+00 IN ROW 24 OBJ. VALUE= 0.00000E+00


Y2 ENTERS AT VALUE 1.0000 IN ROW 3 OBJ. VALUE= -844.00


X33 ENTERS AT VALUE 0.00000E+00 IN ROW 25 OBJ. VALUE= -844.00


Y7 ENTERS AT VALUE 1.0000 IN ROW 8 OBJ. VALUE= -1278.0


X66 ENTERS AT VALUE 0.00000E+00 IN ROW 49 OBJ. VALUE= -1278.0


X55 ENTERS AT VALUE 0.00000E+00 IN ROW 41 OBJ. VALUE= -1278.0


X23 ENTERS AT VALUE 1.0000 IN ROW 18 OBJ. VALUE= -1788.0


X56 ENTERS AT VALUE 0.00000E+00 IN ROW 42 OBJ. VALUE= -1788.0


X76 ENTERS AT VALUE 1.0000 IN ROW 56 OBJ. VALUE= -2328.0


X45 ENTERS AT VALUE 0.00000E+00 IN ROW 34 OBJ. VALUE= -2328.0


Y4 ENTERS AT VALUE 1.0000 IN ROW 6 OBJ. VALUE= -2928.0


X44 ENTERS AT VALUE 1.0000 IN ROW 33 OBJ. VALUE= -3603.0


X42 ENTERS AT VALUE 0.00000E+00 IN ROW 4 OBJ. VALUE= -3603.0


Y5 ENTERS AT VALUE 0.00000E+00 IN ROW 5 OBJ. VALUE= -3603.0


SLK 42 ENTERS AT VALUE 0.00000E+00 IN ROW 42 OBJ. VALUE= -3603.0


SLK 56 ENTERS AT VALUE 0.00000E+00 IN ROW 7 OBJ. VALUE= -3603.0


SLK 23 ENTERS AT VALUE 0.00000E+00 IN ROW 23 OBJ. VALUE= -3603.0


SLK 16 ENTERS AT VALUE 0.00000E+00 IN ROW 2 OBJ. VALUE= -3603.0


SLK 18 ENTERS AT VALUE 0.00000E+00 IN ROW 4 OBJ. VALUE= -3603.0


SLK 33 ENTERS AT VALUE 0.00000E+00 IN ROW 41 OBJ. VALUE= -3603.0



LP OPTIMUM FOUND AT STEP 28


OBJECTIVE FUNCTION VALUE


1) 3603.000


VARIABLE VALUE REDUCED COST

X11 0.000000 0.000000

X12 0.000000 0.000000

X13 0.000000 85.000000

X14 0.000000 405.000000

X15 0.000000 300.000000

X16 0.000000 360.000000

X17 0.000000 226.000000

X21 1.000000 0.000000

X22 1.000000 0.000000

X23 1.000000 0.000000

X24 0.000000 270.000000

X25 0.000000 200.000000

X26 0.000000 270.000000

X27 0.000000 166.000000

X31 0.000000 60.000000

X32 0.000000 0.000000

X33 0.000000 0.000000

X34 0.000000 135.000000

X35 0.000000 100.000000

X36 0.000000 180.000000

X37 0.000000 106.000000

X41 0.000000 120.000000

X42 0.000000 6.000000

X43 0.000000 0.000000

X44 1.000000 0.000000

X45 1.000000 0.000000

X46 0.000000 90.000000

X47 0.000000 46.000000

X51 0.000000 180.000000

X52 0.000000 76.000000

X53 0.000000 85.000000

X54 0.000000 135.000000

X55 0.000000 39.000000

X56 0.000000 0.000000

X57 0.000000 0.000000

X61 0.000000 240.000000

X62 0.000000 146.000000

X63 0.000000 170.000000

X64 0.000000 270.000000

X65 0.000000 0.000000

X66 0.000000 0.000000

X67 0.000000 0.000000

X71 0.000000 300.000000

X72 0.000000 216.000000

X73 0.000000 255.000000

X74 0.000000 405.000000

X75 0.000000 100.000000

X76 1.000000 0.000000

X77 1.000000 0.000000

Y1 0.000000 29.000000

Y2 1.000000 0.000000

Y3 0.000000 43.000000

Y4 1.000000 0.000000

Y5 0.000000 0.000000

Y6 0.000000 28.000000

Y7 1.000000 0.000000



ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 -360.000000

3) 0.000000 -484.000000

4) 0.000000 -510.000000

5) 0.000000 -675.000000

6) 0.000000 -600.000000

7) 0.000000 -540.000000

8) 0.000000 -434.000000

9) 0.000000 -60.000000

10) 0.000000 -64.000000

11) 0.000000 0.000000

12) 0.000000 0.000000

13) 0.000000 0.000000

14) 0.000000 0.000000

15) 0.000000 0.000000

16) 0.000000 0.000000

17) 0.000000 -134.000000

18) 0.000000 0.000000

19) 1.000000 0.000000

20) 1.000000 0.000000

21) 1.000000 0.000000

22) 1.000000 0.000000

23) 0.000000 0.000000

24) 0.000000 -64.000000

25) 0.000000 -85.000000

26) 0.000000 0.000000

27) 0.000000 0.000000

28) 0.000000 0.000000

29) 0.000000 0.000000

30) 1.000000 0.000000

31) 1.000000 0.000000

32) 1.000000 0.000000

33) 0.000000 0.000000

34) 0.000000 0.000000

35) 1.000000 0.000000

36) 1.000000 0.000000

37) 0.000000 0.000000

38) 0.000000 0.000000

39) 0.000000 0.000000

40) 0.000000 0.000000

41) 0.000000 -139.000000

42) 0.000000 0.000000

43) 0.000000 -14.000000

44) 0.000000 0.000000

45) 0.000000 0.000000

46) 0.000000 0.000000

47) 0.000000 0.000000

48) 0.000000 0.000000

49) 0.000000 -90.000000

50) 0.000000 -74.000000

51) 1.000000 0.000000

52) 1.000000 0.000000

53) 1.000000 0.000000

54) 1.000000 0.000000

55) 1.000000 0.000000

56) 0.000000 0.000000

57) 0.000000 -134.000000


NO. ITERATIONS= 28


























La costruzione del modello con il foglio elettronico è leggermente più complicata e può essere riassunta nei seguenti passi:


  1. si assegnano le variabili decisionali ad un intervallo di celle (in verde nella figura ) e si immettono dei valori per inizializzarle


  1. si sceglie una cella in cui visualizzare la funzione obiettivo (in azzurro nella figura) e si immette la funzione matematica che la caratterizza: al posto dei nomi delle variabili si scrivono le celle del foglio di lavoro che le contraddistinguono (è possibile cliccare di volta in volta su ciascuna locazione, anziché digitarne per esteso l’indirizzo)



  1. poiché quando la funzione risolutore chiede i vincoli del modello intende delle locazioni di memoria e non singoli valori, anche i parametri del modello come i costi fissi di attivazione e i costi unitari di trasporto vanno allocati in opportune locazioni.(in arancione)




  1. si seleziona la cella obiettivo e si lancia risolutore dal menu strumenti; nella finestra che si apre vanno indicate le celle che devono essere variate ed i vincoli cui deve sottostare la funzione obiettivo:



  1. si apre la finestra opzioni e si seleziona “presupponi modello lineare” e “presupponi non negativo”:



6) lanciando a questo punto il comando “risolvi” si può scegliere se visualizzare nelle celle variabili i valori calcolati dal risolutore oppure lasciare i valori che si erano scelti per inizializzare le celle stesse:

A prescindere da tale scelta, se si selezionano “valori” e “sensibilità” dal menù rapporti i valori della soluzione ottima e dell’analisi di sensitività vengono caricati in un foglio di lavoro supplementare:


Microsoft Excel 9.0 Rapporto valori





Foglio di lavoro: [ipotesi2.xls]Foglio1





Data di creazione: 16/07/02 18.19.59



















Cella obiettivo (Min)






Cella

Nome

Valori originali

Valore finale




$C$27

costo attivaz

3.603 €

3.603 €

















Celle variabili






Cella

Nome

Valori originali

Valore finale




$C$3

Fo stato sede

0

0




$D$3

Fo Fo

0

0




$E$3

Fo Rn

0

0




$F$3

Fo Pu

0

0




$G$3

Fo An

0

0




$H$3

Fo Mc

0

0




$I$3

Fo Ap

0

0




$J$3

Fo Te

0

0




$C$4

Rn stato sede

1

1




$D$4

Rn Fo

1

1




$E$4

Rn Rn

1

1




$F$4

Rn Pu

1

1




$G$4

Rn An

0

0




$H$4

Rn Mc

0

0




$I$4

Rn Ap

0

0




$J$4

Rn Te

0

0




$C$5

Pu stato sede

0

0




$D$5

Pu Fo

0

0




$E$5

Pu Rn

0

0




$F$5

Pu Pu

0

0




$G$5

Pu An

0

0




$H$5

Pu Mc

0

0




$I$5

Pu Ap

0

0




$J$5

Pu Te

0

0




$C$6

An stato sede

1

1




$D$6

An Fo

0

0




$E$6

An Rn

0

0




$F$6

An Pu

0

0




$G$6

An An

1

1




$H$6

An Mc

1

1




$I$6

An Ap

0

0




$J$6

An Te

0

0




$C$7

Mc stato sede

0

0




$D$7

Mc Fo

0

0




$E$7

Mc Rn

0

0




$F$7

Mc Pu

0

0




$G$7

Mc An

0

0




$H$7

Mc Mc

0

0




$I$7

Mc Ap

0

0




$J$7

Mc Te

0

0




$C$8

Ap stato sede

0

0




$D$8

Ap Fo

0

0




$E$8

Ap Rn

0

0




$F$8

Ap Pu

0

0




$G$8

Ap An

0

0




$H$8

Ap Mc

0

0




$I$8

Ap Ap

0

0




$J$8

Ap Te

0

0




$C$9

Te stato sede

1

1




$D$9

Te Fo

0

0




$E$9

Te Rn

0

0




$F$9

Te Pu

0

0




$G$9

Te An

0

0




$H$9

Te Mc

0

0




$I$9

Te Ap

1

1




$J$9

Te Te

1

1

















Vincoli







Cella

Nome

Valore della cella

Formula

Stato

Tolleranza


$D$11

frazione domanda evasa per provincia Fo

1

$D$11=1

Non vincolante

0


$E$11

frazione domanda evasa per provincia Rn

1

$E$11=1

Non vincolante

0


$J$11

frazione domanda evasa per provincia Te

1

$J$11=1

Non vincolante

0


$G$11

frazione domanda evasa per provincia An

1

$G$11=1

Non vincolante

0


$H$11

frazione domanda evasa per provincia Mc

1

$H$11=1

Non vincolante

0


$I$11

frazione domanda evasa per provincia Ap

1

$I$11=1

Non vincolante

0


$F$11

frazione domanda evasa per provincia Pu

1

$F$11=1

Non vincolante

0


$M$3

Fo

0

$M$3>=0

Vincolante

0


$M$4

Rn

0

$M$4>=0

Vincolante

0


$M$5

Pu

0

$M$5>=0

Vincolante

0


$M$6

An

1

$M$6>=0

Non vincolante

1


$M$7

Mc

0

$M$7>=0

Vincolante

0


$M$8

Ap

0

$M$8>=0

Vincolante

0


$M$9

Te

1

$M$9>=0

Non vincolante

1


$N$3

Fo

0

$N$3>=0

Vincolante

0


$N$4

Rn

0

$N$4>=0

Vincolante

0


$N$5

Pu

0

$N$5>=0

Vincolante

0


$N$6

An

1

$N$6>=0

Non vincolante

1


$N$7

Mc

0

$N$7>=0

Vincolante

0


$N$8

Ap

0

$N$8>=0

Vincolante

0


$N$9

Te

1

$N$9>=0

Non vincolante

1


$O$3

Fo

0

$O$3>=0

Vincolante

0


$O$4

Rn

0

$O$4>=0

Vincolante

0


$O$5

Pu

0

$O$5>=0

Vincolante

0


$O$6

An

1

$O$6>=0

Non vincolante

1


$O$7

Mc

0

$O$7>=0

Vincolante

0


$O$8

Ap

0

$O$8>=0

Vincolante

0


$O$9

Te

1

$O$9>=0

Non vincolante

1


$S$9

Te

0

$S$9>=0

Vincolante

0


$P$4

Rn

1

$P$4>=0

Non vincolante

1


$P$5

Pu

0

$P$5>=0

Vincolante

0


$P$6

An

0

$P$6>=0

Vincolante

0


$P$7

Mc

0

$P$7>=0

Vincolante

0


$P$8

Ap

0

$P$8>=0

Vincolante

0


$P$9

Te

1

$P$9>=0

Non vincolante

1


$Q$3

Fo

0

$Q$3>=0

Vincolante

0


$Q$4

Rn

1

$Q$4>=0

Non vincolante

1


$Q$5

Pu

0

$Q$5>=0

Vincolante

0


$Q$6

An

0

$Q$6>=0

Vincolante

0


$Q$7

Mc

0

$Q$7>=0

Vincolante

0


$Q$8

Ap

0

$Q$8>=0

Vincolante

0


$Q$9

Te

1

$Q$9>=0

Non vincolante

1


$R$3

Fo

0

$R$3>=0

Vincolante

0


$R$4

Rn

1

$R$4>=0

Non vincolante

1


$R$5

Pu

0

$R$5>=0

Vincolante

0


$R$6

An

1

$R$6>=0

Non vincolante

1


$P$3

Fo

0

$P$3>=0

Vincolante

0


$R$8

Ap

0

$R$8>=0

Vincolante

0


$R$9

Te

0

$R$9>=0

Vincolante

0


$S$3

Fo

0

$S$3>=0

Vincolante

0


$S$4

Rn

1

$S$4>=0

Non vincolante

1


$S$5

Pu

0

$S$5>=0

Vincolante

0


$S$6

An

1

$S$6>=0

Non vincolante

1


$S$7

Mc

0

$S$7>=0

Vincolante

0


$S$8

Ap

0

$S$8>=0

Vincolante

0


$R$7

Mc

0

$R$7>=0

Vincolante

0
























6. ANALISI DEI RISULTATI


Da entrambe le soluzioni si deduce che:






La soluzione ottima ottenuta può essere anche espressa in termini di ore lavorative:


  1. la sede di Rn dovrà soddisfare una domanda di 215 ore settimanali


  1. la sede di Te deve soddisfare la domanda delle province di Ap e Te, corrispondente a 150 ore


  1. la sede di An dovrà soddisfare una domanda di 235 ore settimanali


Ne segue che Il guadagno di 262 € si concretizza solo se , ad esempio:


1)nella sede di Rn i 5 dipendenti necessari a soddisfare la domanda accettino di lavorare 43 ore settimanali ciascuno


2)nella sede di Ap i 4 dipendenti necessari siano disposti a lavorare solo 37 ore ciascuno


3)nella sede di An 6 dipendenti lavorino 39 ore a settimana


Pertanto il problema della localizzazione può considerarsi risolto se l’azienda riesce ad operare in condizioni di orari flessibilI: i costi di attivazione vengono completamente ammortizzati in circa 2 anni e mezzo (sui salari si risparmiano 530€ a settimana e il costo complessivo dei locali è di 70000€ ), mentre sui 5 anni si avrebbe un guadagno di 262*52*5=68120 €.



























7. LIMITI DELLA SOLUZIONE OTTIMA IN CONDIZIONI DI ORARI RIGIDI


Diversa è la situazione se l’azienda opera in condizioni di orari rigidi: anche introducendo vincoli sulle sorgenti che permettono di passare dal modello di localizzazione semplice a modelli più raffinati, la questione non può avere soluzione fintanto che si rimane nella programmazione lineare binaria.


L’incompatibilità fra i dati del problema e le variabili decisionali xij binarie, sta infatti nelle domande delle varie province che non sono esprimibili come multipli di 40: l’unico modo per avere un numero di ore multiple di 40 in ciascuna sede è ricorrere a xij frazionarie, mentre noi conosciamo il problema della localizzazione come un problema a numeri interi.


Vi sono però altri modelli di programmazione lineare che si adattano perfettamente alla situazione in cui ci si trova una volta attivate le sedi: si ha un difetto dell’offerta a Rn, un’eccedenza ad An e Te e ci si chiede come sia possibile ridistribuire le ore in eccedenza verso le sedi in cui si è in difetto minimizzando ancora una volta il costo dell’ operazione.


difetto di 15 ore







Eccedenza di 5ore ore






Eccedenza di 10ore




E’ chiaro che una soluzione immediata consiste nel compensare la carenza di Rn facendo arrivare 5 ore da An e 10 da Te, ma è altrettanto chiaro che non si tratta della scelta migliore, perché:



8. REDISTRIBUZIONE DELL’ OFFERTA


E’ chiaro dalla conclusione del paragrafo precedente che la soluzione consiste nel costruire un problema dei trasporti a partire dalla soluzione ottima del problema di localizzazione : si tratta di distribuire le ore lavorative dalle 3 nuove origini (Rn, An,Te) nelle solite 7 destinazioni (Fo, Rn, Pu, An, Mc, Ap, Te).


Ovviamente si tratta di un approccio tutt’altro che rigoroso, dettato dalla mancata conoscenza di modelli di localizzazione più raffinati a variabili non intere (si è sottolineato come non sia sufficiente affiancare vincoli di origine al modello di localizzazione semplice per superare la questione), che tuttavia potrebbe risultare efficace.


L’efficacia di questo tipo di approccio va comunque verificata caso per caso : in fondo ciò che si va a redistribuire non sono esattamente le ore ottenute nella soluzione ottima precedente ( 215 nella sede di Rn, 235 nella sede di An e 150 nella sede di Te), ma una sorta di approssimazione della soluzione stessa (espressa in termini di ore e non di assegnamenti sede-clienti ) al multiplo di 40 più vicino: 200 ore a Fo, 240 ore ad An e 160 ore a Te.


Potrebbe cioè aver luogo un meccanismo simile a quello che si ha approssimando all’intero più vicino la soluzione del P.L.A. ad un problema di programmazione intera, per cui non solo la soluzione approssimata non è ottima per il P.L.I. ma non è nemmeno buona.


Nel caso in esame si vedrà come questo meccanismo non abbia luogo: non si può escludere che vi sia una soluzione migliore di quella trovata risolvendo “in cascata” il problema di localizzazione e quello di trasporto, ma il peggioramento della soluzione ottima introdotto dal vincolo di rigidità degli orari è tutto sommato accettabile.




9. DEFINIZIONE DEL PROBLEMA DEI TRASPORTI


Il problema dei trasporti è un caso particolare di programmazione lineare in cui la funzione obiettivo da minimizzare assume la forma:


ΣiΣjcijxij (1)


mentre i vincoli sono nella forma:


Σjxij=ai i=1,2,…,n (2)

Σixij=bj j=1,2,…,m (3)

xij>=0


Risulta inoltre implicito che se, ottenuta una soluzione, si sommano le xij prima rispetto alle i e poi rispetto alle j e viceversa, in entrambi i casi si deve ottenere la stessa somma, ovvero:


Σiai jbj (4)


Il nome del modello deriva dalla sua applicazione classica: minimizzazione del costo totale di trasporto di un certo prodotto da m origini, in grado di produrre le quantità a1,a2, …. , am, ad n destinazioni che ne richiedono le quantità b1,b2, … , bn.


In questo caso restano determinate anche le seguenti interpretazioni di parametri e vincoli:







Riconducendo il modello appena presentato alla forma standard di un problema di programmazione lineare, si ottiene un vettore b che ha per componenti tutti e soli gli ai ed i bj, mentre la matrice A gode di due importanti proprietà:




questi due risultati sono in realtà dei lemmi per il seguente teorema:


se gli ai ed i bj (ovvero le componenti del vettore b) sono interi, allora ogni soluzione di base del problema dei trasporti (e quindi anche la soluzione ottima) ha componenti intere.


Tutti i dati di un modello dei trasporti possono sempre essere rappresentati in modo compatto e intuitivo con un grafo, i cui nodi siano le origini e le destinazioni ed i cui archi (sempre orientati dalle origini alle destinazioni) vengono etichettati con i costi unitari di trasporto. Come esempio si possono prendere proprio i valori del problema in esame:



10. MODELLO DEI TRASPORTI PER IL PROBLEMA IN ESAME


La formalizzazione del modello dal grafo del paragrafo precedente è immediato (si è ricorre alla sintassi del LINDO) :


min 6x11+5x12+6x13+7x14+8x15+9x16+10x17+8x21+7x22+6x23+5x24+6x25+7x26+8x27+11x31+10x32+9x33+8x34+7x35+6x36+5x37

st

x11+x12+x13+x14+x15+x16+x17=200

x21+x22+x23+x24+x25+x26+x27=240

x31+x32+x33+x34+x35+x36+x37=160

x11+x21+x31=60

x12+x22+x32=70

x13+x23+x33=85

x14+x24+x34=135

x15+x25+x35=100

x16+x26+x36=90

x17+x27+x37=60

end


Stavolta i costi unitari sono proprio quelli della matrice 7x7 introdotta nel paragrafo 4, in quanto x11=1 significa effettivamente che un dipendente della sede di Fo lavorerà un’ora presso un cliente della provincia stessa e non che dovrà lavorarvi per il 100% delle ore chieste dai clienti di Fo, ovvero 50 ore.


Le equazioni con 3 variabili sono i vincoli di destinazione, mentre le equazioni con 5 variabili sono i vincoli di origine con le bi ottenute dall’approssimazione al multiplo di 40 più vicino come già ampiamente evidenziato.


Anche in questo caso sono stati omessi i vincoli di interezza sulle variabili decisionali perché il problema dei trasporti ha soluzioni intrinsecamente intere, ovvero senza che l’interezza sia indotta da vincoli “esterni”.










11. CALCOLO DELLA NUOVA SOLUZIONE OTTIMA


Il LINDO opera 9 operazioni di pivot, ognuna per far entrare in base una delle variabili non nulle nella soluzione finale:



0) THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 6.000 5.000 6.000 7.000 8.000 9.000

2 ART 1.000 1.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 0.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 ART 1.000 0.000 0.000 0.000 0.000 0.000

6 ART 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 1.000 0.000 0.000 0.000

8 ART 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 ART 0.000 0.000 0.000 0.000 0.000 0.000

ART ART -2.000 -2.000 -2.000 -2.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 10.000 8.000 7.000 6.000 5.000 6.000 7.000

2 1.000 0.000 0.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 1.000 1.000 1.000

4 0.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 -2.000 -2.000 -2.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 8.000 11.000 10.000 9.000 8.000 7.000 6.000

2 0.000 0.000 0.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 0.000 0.000

4 0.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 -2.000 -2.000 -2.000 -2.000 -2.000



ROW X37

1 5.000 0.000

2 0.000 200.000

3 0.000 240.000

4 1.000 160.000

5 0.000 60.000

6 0.000 70.000

7 0.000 85.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART -2.000 -1200.000





1) X12 ENTERS AT VALUE 70.000 IN ROW 6 OBJ. VALUE= -350.00



THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 6.000 0.000 6.000 7.000 8.000 9.000

2 ART 1.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 0.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 ART 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 1.000 0.000 0.000 0.000

8 ART 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 ART 0.000 0.000 0.000 0.000 0.000 0.000

ART ART -2.000 0.000 -2.000 -2.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 10.000 8.000 2.000 6.000 5.000 6.000 7.000

2 1.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 1.000 1.000 1.000

4 0.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 0.000 -2.000 -2.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 8.000 11.000 5.000 9.000 8.000 7.000 6.000

2 0.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 0.000 0.000

4 0.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 0.000 -2.000 -2.000 -2.000 -2.000



ROW X37

1 5.000 -350.000

2 0.000 130.000

3 0.000 240.000

4 1.000 160.000

5 0.000 60.000

6 0.000 70.000

7 0.000 85.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART -2.000 -1060.000

















































2) X24 ENTERS AT VALUE 135.00 IN ROW 8 OBJ. VALUE= -1025.0



THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 6.000 0.000 6.000 2.000 8.000 9.000

2 ART 1.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 -1.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 ART 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 1.000 0.000 0.000 0.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 ART 0.000 0.000 0.000 0.000 0.000 0.000

ART ART -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 10.000 8.000 2.000 6.000 0.000 6.000 7.000

2 1.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 0.000 1.000 1.000

4 0.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 8.000 11.000 5.000 9.000 3.000 7.000 6.000

2 0.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 -1.000 0.000 0.000

4 0.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART -2.000 -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X37

1 5.000 -1025.000

2 0.000 130.000

3 0.000 105.000

4 1.000 160.000

5 0.000 60.000

6 0.000 70.000

7 0.000 85.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART -2.000 -790.000


3) X37 ENTERS AT VALUE 60.000 IN ROW 11 OBJ. VALUE= -1325.0



THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 6.000 0.000 6.000 2.000 8.000 9.000

2 ART 1.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 -1.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 ART 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 1.000 0.000 0.000 0.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 5.000 8.000 2.000 6.000 0.000 6.000 7.000

2 1.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 3.000 11.000 5.000 9.000 3.000 7.000 6.000

2 0.000 0.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 -2.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X37

1 0.000 -1325.000

2 0.000 130.000

3 0.000 105.000

4 0.000 100.000

5 0.000 60.000

6 0.000 70.000

7 0.000 85.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -670.00



4) X11 ENTERS AT VALUE 60.000 IN ROW 5 OBJ. VALUE= -1685.0


THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 6.000 2.000 8.000 9.000

2 ART 0.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 -1.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 1.000 0.000 0.000 0.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 5.000 2.000 2.000 6.000 0.000 6.000 7.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 0.000 0.000 -2.000 0.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 3.000 5.000 5.000 9.000 3.000 7.000 6.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 0.000 0.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 0.000 0.000 -2.000 0.000 -2.000 -2.000


ROW X37

1 0.000 -1685.000

2 0.000 70.000

3 0.000 105.000

4 0.000 100.000

5 0.000 60.000

6 0.000 70.000

7 0.000 85.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -550.000



5) X13 ENTERS AT VALUE 70.000 IN ROW 2 OBJ. VALUE= -2105.0



THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 0.000 -4.000 2.000 3.000

2 X13 0.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 -1.000 0.000 0.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 ART 0.000 0.000 0.000 -1.000 -1.000 -1.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 0.000 2.000 0.000 0.000



ROW X17 X21 X22 X23 X24 X25 X26

1 -1.000 8.000 8.000 6.000 0.000 6.000 7.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 0.000 1.000 1.000 1.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 -1.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 2.000 -2.000 -2.000 -2.000 0.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 3.000 11.000 11.000 9.000 3.000 7.000 6.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 -2.000 -2.000 -2.000 0.000 -2.000 -2.000



ROW X37

1 0.000 -2105.000

2 0.000 70.000

3 0.000 105.000

4 0.000 100.000

5 0.000 60.000

6 0.000 70.000

7 0.000 15.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -410.000




6) X23 ENTERS AT VALUE 15.000 IN ROW 7 OBJ. VALUE= -2195.0


THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 0.000 2.000 8.000 9.000

2 X13 0.000 0.000 1.000 1.000 1.000 1.000

3 ART 0.000 0.000 0.000 0.000 1.000 1.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 X23 0.000 0.000 0.000 -1.000 -1.000 -1.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 1.000 0.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 0.000 0.000 -2.000 -2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 5.000 2.000 2.000 0.000 0.000 6.000 7.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 -1.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 0.000 0.000 0.000 0.000 -2.000 -2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 3.000 5.000 5.000 3.000 3.000 7.000 6.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 -1.000 -1.000 -1.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 0.000 0.000 0.000 0.000 0.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 0.000 0.000 0.000 0.000 0.000 -2.000 -2.000



ROW X37

1 0.000 -2195.000

2 0.000 70.000

3 0.000 90.000

4 0.000 100.000

5 0.000 60.000

6 0.000 70.000

7 0.000 15.000

8 0.000 135.000

9 0.000 100.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -380.000




7) X25 ENTERS AT VALUE 90.000 IN ROW 3 OBJ. VALUE= -2735.0


THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 0.000 2.000 2.000 3.000

2 X13 0.000 0.000 1.000 1.000 1.000 1.000

3 X25 0.000 0.000 0.000 0.000 1.000 1.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 X23 0.000 0.000 0.000 -1.000 -1.000 -1.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 0.000 -1.000

10 ART 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 0.000 0.000 0.000 0.000



ROW X17 X21 X22 X23 X24 X25 X26

1 -1.000 2.000 2.000 0.000 0.000 0.000 1.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 -1.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 0.000 0.000 0.000 0.000 0.000 -1.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 2.000 0.000 0.000 0.000 0.000 0.000 0.000



ROW X27 X31 X32 X33 X34 X35 X36

1 -3.000 11.000 11.000 9.000 9.000 7.000 6.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 -1.000 -1.000 -1.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 1.000 1.000 1.000 1.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 2.000 -2.000 -2.000 -2.000 -2.000 -2.000 -2.000



ROW X37

1 0.000 -2735.000

2 0.000 70.000

3 0.000 90.000

4 0.000 100.000

5 0.000 60.000

6 0.000 70.000

7 0.000 15.000

8 0.000 135.000

9 0.000 10.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -200.000


8) X36 ENTERS AT VALUE 90.000 IN ROW 10 OBJ. VALUE= -3275.0


THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 0.000 2.000 2.000 -3.000

2 X13 0.000 0.000 1.000 1.000 1.000 1.000

3 X25 0.000 0.000 0.000 0.000 1.000 1.000

4 ART 0.000 0.000 0.000 0.000 0.000 -1.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 X23 0.000 0.000 0.000 -1.000 -1.000 -1.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 ART 0.000 0.000 0.000 0.000 0.000 -1.000

10 X36 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 0.000 0.000 0.000 2.000



ROW X17 X21 X22 X23 X24 X25 X26

1 -1.000 2.000 2.000 0.000 0.000 0.000 -5.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 1.000 1.000

4 -1.000 0.000 0.000 0.000 0.000 0.000 -1.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 -1.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 0.000 0.000 0.000 0.000 0.000 -1.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 2.000 0.000 0.000 0.000 0.000 0.000 2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 -3.000 11.000 11.000 9.000 9.000 7.000 0.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 -1.000 -1.000 -1.000 -1.000 0.000 0.000

4 -1.000 1.000 1.000 1.000 1.000 1.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 1.000 1.000 1.000 1.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 2.000 -2.000 -2.000 -2.000 -2.000 -2.000 0.000



ROW X37

1 0.000 -3275.000

2 0.000 70.000

3 0.000 90.000

4 0.000 10.000

5 0.000 60.000

6 0.000 70.000

7 0.000 15.000

8 0.000 135.000

9 0.000 10.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 -20.000


9) X35 ENTERS AT VALUE 10.000 IN ROW 9 OBJ. VALUE= -3345.0



THE TABLEAU


ROW (BASIS) X11 X12 X13 X14 X15 X16

1 ART 0.000 0.000 0.000 2.000 2.000 4.000

2 X13 0.000 0.000 1.000 1.000 1.000 1.000

3 X25 0.000 0.000 0.000 0.000 1.000 1.000

4 ART 0.000 0.000 0.000 0.000 0.000 0.000

5 X11 1.000 0.000 0.000 0.000 0.000 0.000

6 X12 0.000 1.000 0.000 0.000 0.000 0.000

7 X23 0.000 0.000 0.000 -1.000 -1.000 -1.000

8 X24 0.000 0.000 0.000 1.000 0.000 0.000

9 X35 0.000 0.000 0.000 0.000 0.000 -1.000

10 X36 0.000 0.000 0.000 0.000 0.000 1.000

11 X37 0.000 0.000 0.000 0.000 0.000 0.000

ART ART 0.000 0.000 0.000 2.000 2.000 4.000



ROW X17 X21 X22 X23 X24 X25 X26

1 6.000 2.000 2.000 0.000 0.000 0.000 2.000

2 1.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 0.000 0.000 0.000 0.000 1.000 1.000

4 0.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 -1.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 0.000 0.000 0.000 0.000 0.000 -1.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 6.000 2.000 2.000 0.000 0.000 0.000 2.000



ROW X27 X31 X32 X33 X34 X35 X36

1 4.000 4.000 4.000 2.000 2.000 0.000 0.000

2 0.000 -1.000 -1.000 0.000 0.000 0.000 0.000

3 1.000 -1.000 -1.000 -1.000 -1.000 0.000 0.000

4 0.000 0.000 0.000 0.000 0.000 0.000 0.000

5 0.000 1.000 0.000 0.000 0.000 0.000 0.000

6 0.000 0.000 1.000 0.000 0.000 0.000 0.000

7 0.000 1.000 1.000 1.000 0.000 0.000 0.000

8 0.000 0.000 0.000 0.000 1.000 0.000 0.000

9 -1.000 1.000 1.000 1.000 1.000 1.000 0.000

10 0.000 0.000 0.000 0.000 0.000 0.000 1.000

11 1.000 0.000 0.000 0.000 0.000 0.000 0.000

ART 4.000 4.000 4.000 2.000 2.000 0.000 0.000



ROW X37

1 0.000 -3345.000

2 0.000 70.000

3 0.000 90.000

4 0.000 0.000

5 0.000 60.000

6 0.000 70.000

7 0.000 15.000

8 0.000 135.000

9 0.000 10.000

10 0.000 90.000

11 1.000 60.000

ART 0.000 0.000



LP OPTIMUM FOUND AT STEP 9


OBJECTIVE FUNCTION VALUE


1) 3345.000


VARIABLE VALUE REDUCED COST

X11 60.000000 0.000000

X12 70.000000 0.000000

X13 70.000000 0.000000

X14 0.000000 2.000000

X15 0.000000 2.000000

X16 0.000000 4.000000

X17 0.000000 6.000000

X21 0.000000 2.000000

X22 0.000000 2.000000

X23 15.000000 0.000000

X24 135.000000 0.000000

X25 90.000000 0.000000

X26 0.000000 2.000000

X27 0.000000 4.000000

X31 0.000000 4.000000

X32 0.000000 4.000000

X33 0.000000 2.000000

X34 0.000000 2.000000

X35 10.000000 0.000000

X36 90.000000 0.000000

X37 60.000000 0.000000



ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 1.000000

3) 0.000000 1.000000

4) 0.000000 0.000000

5) 0.000000 -7.000000

6) 0.000000 -6.000000

7) 0.000000 -7.000000

8) 0.000000 -6.000000

9) 0.000000 -7.000000

10) 0.000000 -6.000000

11) 0.000000 -5.000000


NO. ITERATIONS= 9


Il foglio elettronico offre inoltre la possibilità di “interfacciare” il problema di localizzazione con quello dei trasporti; costruendo infatti i due modelli nello stesso foglio di lavoro si può operare nei seguenti passi:


  1. risolvere il problema di plant location come indicato nel paragrafo 5

  2. esprimere la soluzione ottenuta in termini di ore lavorative ed approssimarla al multiplo di 40 più vicino

  3. introdurre automaticamente l’approssimazione nei vincoli di origine del problema dei trasporti


In figura sono state isolate le celle che operano i 3 passi indicati in altrettante cornici (di colore blu):





L’unico svantaggio di questo modo di procedere è che nella finestra del risolutore viene memorizzato un solo gruppo di vincoli alla volta: al momento di risolvere il problema dei trasporti viene quindi eliminato il modello di localizzazione ( e inserire la cella obiettivo, le celle variabili e 56 vincoli ha lo svantaggio di essere piuttosto laborioso).


I risultati cui si perviene sono ancora una volta salvati sia nelle celle variabili del modello, sia in un foglio di lavoro supplementare:


Microsoft Excel 10.0 Rapporto valori





Foglio di lavoro: [ipotesi2_totale.xls]Foglio1





Data di creazione: 16/07/13 22.55.24



















Cella obiettivo (Min)






Cella

Nome

Valori originali

Valore finale




$B$27

 

4.745 €

3.345 €

















Celle variabili






Cella

Nome

Valori originali

Valore finale




$D$3

Fo Fo

0

0




$E$3

Fo Rn

0

0




$F$3

Fo Pu

0

0




$G$3

Fo An

0

0




$H$3

Fo Mc

0

0




$I$3

Fo Ap

0

0




$J$3

Fo Te

0

0




$D$4

Rn Fo

0

60




$E$4

Rn Rn

0

70




$F$4

Rn Pu

0

70




$G$4

Rn An

100

0




$H$4

Rn Mc

100

0




$I$4

Rn Ap

0

0




$J$4

Rn Te

0

0




$D$5

Pu Fo

0

0




$E$5

Pu Rn

0

0




$F$5

Pu Pu

0

0




$G$5

Pu An

0

0




$H$5

Pu Mc

0

0




$I$5

Pu Ap

0

0




$J$5

Pu Te

0

0




$D$6

An Fo

60

0




$E$6

An Rn

30

0




$F$6

An Pu

0

15




$G$6

An An

0

135




$H$6

An Mc

0

90




$I$6

An Ap

90

0




$J$6

An Te

60

0




$D$7

Mc Fo

0

0




$E$7

Mc Rn

0

0




$F$7

Mc Pu

0

0




$G$7

Mc An

0

0




$H$7

Mc Mc

0

0




$I$7

Mc Ap

0

0




$J$7

Mc Te

0

0




$D$8

Ap Fo

0

0




$E$8

Ap Rn

0

0




$F$8

Ap Pu

0

0




$G$8

Ap An

0

0




$H$8

Ap Mc

0

0




$I$8

Ap Ap

0

0




$J$8

Ap Te

0

0




$D$9

Te Fo

0

0




$E$9

Te Rn

40

0




$F$9

Te Pu

85

0




$G$9

Te An

35

0




$H$9

Te Mc

0

10




$I$9

Te Ap

0

90




$J$9

Te Te

0

60

















Vincoli







Cella

Nome

Valore della cella

Formula

Stato

Tolleranza


$L$3

Fo

0

$L$3=$B$3

Non vincolante

0


$B$4

Rn

200

$B$4=$L$4

Non vincolante

0


$B$5

Pu

0

$B$5=$L$5

Non vincolante

0


$B$6

An

240

$B$6=$L$6

Non vincolante

0


$B$7

Mc

0

$B$7=$L$7

Non vincolante

0


$B$8

Ap

0

$B$8=$L$8

Non vincolante

0


$B$9

Te

160

$B$9=$L$9

Non vincolante

0


$D$11

frazione domanda evasa per provincia Fo

60

$D$11=$D$13

Non vincolante

0


$E$11

frazione domanda evasa per provincia Rn

70

$E$11=$E$13

Non vincolante

0


$F$11

frazione domanda evasa per provincia Pu

85

$F$11=$F$13

Non vincolante

0


$G$11

frazione domanda evasa per provincia An

135

$G$11=$G$13

Non vincolante

0


$H$11

frazione domanda evasa per provincia Mc

100

$H$11=$H$13

Non vincolante

0


$I$11

frazione domanda evasa per provincia Ap

90

$I$11=$I$13

Non vincolante

0


$J$11

frazione domanda evasa per provincia Te

60

$J$11=$J$13

Non vincolante

0














12. ANALISI DEI NUOVI RISULTATI E CONCLUSIONI


La soluzione del problema dei trasporti è piuttosto semplice (soprattutto perché nella soluzione del problema di localizzazione si erano già rese piccole le spese del trasporto, compatibilmente con i costi di attivazione) :

15 ore svolte dai dipendenti di An nella provincia di Pu sopperiscono alle ore non elargibili dalla sede di Rn; vengono quindi a mancare 10 ore a Mc che vengono compensate dai dipendenti della sede di Te.


A conferma della semplicità della soluzione si può provare a risolvere il problema con l’algoritmo dei trasporti di dantzig: se si cerca la soluzione iniziale col metodo dell’angolo di Nord-Ovest è sufficiente il primo passo.


Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5]

[6]

[7]

[8]

[9]

[10]

200

[8]

[7]

[6]

[5]

[6]

[7]

[8]

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

60

70

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5]

[6]

[7]

[8]

[9]

[10]

140

[8]

[7]

[6]

[5]

[6]

[7]

[8]

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

70

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6]

[7]

[8]

[9]

[10]

70

[8]

[7]

[6]

[5]

[6]

[7]

[8]

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

0

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6]

[5]

[6]

[7]

[8]

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

0

15

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5]

[6]

[7]

[8]

225

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

0

0

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5] 135

[6]

[7]

[8]

90

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

0

0

0

100

90

60



Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5] 135

[6] 90

[7]

[8]

0

[11]

[10]

[9]

[8]

[7]

[6]

[5]

160

0

0

0

0

10

90

60





Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5] 135

[6] 90

[7]

[8]

0

[11]

[10]

[9]

[8]

[7] 10

[6]

[5]

150

0

0

0

0

0

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5] 135

[6] 90

[7]

[8]

0

[11]

[10]

[9]

[8]

[7] 10

[6] 90

[5]

60

0

0

0

0

0

0

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 15

[5] 135

[6] 90

[7]

[8]

0

[11]

[10]

[9]

[8]

[7] 10

[6] 90

[5] 60

0

0

0

0

0

0

0

0



Ovvero proprio la redistribuzione ottima ottenuta nel paragrafo precedente: 15 ore a Pu vengono svolte dai dipendenti di An e il “buco” di 15 ore che viene così a crearsi a Mc viene coperto dai dipendenti di Te.


Volendo convincersi ulteriormente che tale tabella è quella ottima, si può effettuare la prima iterazione dell’algoritmo dei trasporti:

6-u1-v1=0 u1=0 → v1=6

5-u1-v2=0 u1=0 → v2=5


6-u1-v3=0 u1=0 → v3=6

6-u2-v3=0 v3=6 → u2=0

5-u2-v4=0 u2=0 → v4=5

6-u2-v5=0 u2=0 → v5=6

7-u3-v5=0 v5=6 → u3=1

6-u3-v6=0 u3=1 → v6=5

5-u3-v7=0 u3=1 → v7=4


A questo punto tutti i coefficienti cij’ relativi a variabili non in base sono non negativi, per cui siamo effettivamente all’ottimo:


7-u1-v4=2

8-u1-v5=2

9-u1-v6=4

10-u1-v7=6

8-u2-v1=2

7-u2-v2=2

7-u2-v6=1

8-u2-v7=4

11-u3-v1=4

10-u3-v2=4

9-u3-v3=2

8-u3-v4=2


Fra l’altro la presenza di molti coefficienti di costo uguali su archi diversi fa si che nel metodo dei minimi costi e in quello di Vogel si abbiano molte scelte equivalenti sulla xij da saturare: mentre col metodo dell’angolo di Nord-Ovest la soluzione iniziale ottenuta è univoca e coincidente proprio con la soluzione ottima, ricorrendo agli altri due metodi in alcuni casi si perviene a una soluzione iniziale diversa: sarà quindi necessario applicare l’algoritmo dei trasporti.


In altre parole, nel caso in esame il metodo dell’angolo di Nord-Ovest è quello che restituisce la soluzione iniziale più vicina all’ottimo, mentre sappiamo che in generale avviene il contrario.


Nel metodo dei minimi costi ci si trova a dover scegliere arbitrariamente una elemento della tabella fra tanti con lo stesso cij ed è proprio questo fatto che può condurre ad una soluzione iniziale non ottima:


Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5]

[6]

[7]

[8]

[9]

[10]

200

[8]

[7]

[6]

[5]

[6]

[7]

[8]

240

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

100

60

70

85

135

100

90

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5]

[6]

[7]

[8]

[9]

[10]

200

[8]

[7]

[6]

[5] 135

[6]

[7]

[8]

105

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

100

60

70

85

0

100

90

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5] 70

[6]

[7]

[8]

[9]

[10]

130

[8]

[7]

[6]

[5] 135

[6]

[7]

[8]

105

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

100

60

0

85

0

100

90

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5]

[6]

[7]

[8]

[9]

[10]

130

[8]

[7]

[6]

[5] 135

[6]

[7]

[8]

105

[11]

[10]

[9]

[8]

[7]

[6] 90

[5] 60

10

60

0

85

0

100

0

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5] 70

[6]

[7]

[8]

[9]

[10]

130

[8]

[7]

[6]

[5] 135

[6] 100

[7]

[8]

5

[11]

[10]

[9]

[8]

[7]

[6] 90

[5] 60

10

60

0

85

0

0

0

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5] 70

[6]

[7]

[8]

[9]

[10]

130

[8]

[7]

[6] 5

[5] 135

[6] 100

[7]

[8]

0

[11]

[10]

[9]

[8]

[7]

[6] 90

[5] 60

10

60

0

80

0

0

0

0



Fo

Rn

Pu

An

Mc

Ap

Te


[6] 50

[5] 70

[6] 80

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 5

[5] 135

[6] 100

[7]

[8]

0

[11]

[10]

[9]

[8]

[7]

[6] 90

[5] 60

10

10

0

0

0

0

0

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 50

[5] 70

[6] 80

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 5

[5] 135

[6] 100

[7]

[8]

0

[11] 10

[10]

[9]

[8]

[7]

[6] 90

[5] 60

0

0

0

0

0

0

0

0



Si tratta quindi di calcolare quale variabile deve entrare in base e al posto di quale (anche se è già intuibile che saranno le 10 ore che da Te “vanno” a Fo a dover essere cambiate per prime):


6-u1-v1=0 u1=0 → v1=6

5-u1-v2=0 u1=0 → v2=5

6-u1-v3=0 u1=0 → v3=6

6-u2-v3=0 v3=6 → u2=0

5-u2-v4=0 u2=0 → v4=5

6-u2-v5=0 u2=0 → v5=6

11-u3-v1=0 v1=6 → u3=5

6-u3-v6=0 u3=5 → v6=1

5-u3-v7=0 u3=5 → v7=0


7-u1-v4=2 7-u2-v6= 6

8-u1-v5=2 8-u2-v7=8

9-u1-v6=8 10-u3-v2=0

10-u1-v7=10 9-u3-v3= -2

8-u2-v1=2 8-u3-v4= -2

7-u2-v2=2 7-u3-v5= -4


Come preventivato, è la cella corrispondente a u3,v1 a doversi annullare: è infatti quella a valore minimo in posizione pari nel ciclo individuato nella figura;


Fo

Rn

Pu

An

Mc

Ap

Te


[6] 50

[5] 70

[6] 80

[7]

[8]

[9]

[10]

0

[8]

[7]

[6] 5

[5] 135

[6] 100

[7]

[8]

0

[11] 10

[10]

[9]

[8]

[7]

[6] 90

[5] 60

0

0

0

0

0

0

0

0



Una volta sostituito il valore 10 nella casella indicata, non è difficile assegnare alle variabili del ciclo l’unico set di valori in grado di soddisfare i vincoli;


Fo

Rn

Pu

An

Mc

Ap

Te


[6] ?

[5] 70

[6] ??

[7]

[8]

[9]

[10]

200

[8]

[7]

[6] ???

[5] 135

[6] ?

[7]

[8]

240

[11]

[10]

[9]

[8]

[7] 10

[6] 90

[5] 60

160

60

70

85

135

100

90

60



Si ha infatti che:






Avendo trovato la solita soluzione per l’ennesima volta, si omette di verificarne di nuovo l’ottimalità.


Col metodo di Vogel si pone invece la questione della scelta arbitraria fra più righe o colonne con lo stesso valore di Δ, anziché fra celle con lo stesso cij; nel caso in esame si perviene direttamente alla soluzione ottima se, a parità di Δ, si considera il minimo cij su una riga piuttosto che su una colonna:


Fo

Rn

Pu

An

Mc

Ap

Te


[6]

[5]

[6]

[7]

[8]

[9]

[10]

Δ=1

200

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

Δ=1

160

Δ=2

Δ=2

Δ=0

Δ=1

Δ=1

Δ=1

Δ=2



60

70

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5]

[6]

[7]

[8]

[9]

[10]

Δ=1

140

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

Δ=1

160


Δ=2

Δ=0

Δ=1

Δ=1

Δ=1

Δ=2



0

70

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6]

[7]

[8]

[9]

[10]

Δ=1

70

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5]

Δ=1

160



Δ=0

Δ=1

Δ=1

Δ=1

Δ=2



0

0

85

135

100

90

60




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6]

[7]

[8]

[9]

[10]

Δ=1

70

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100



Δ=0

Δ=1

Δ=1

Δ=1




0

0

85

135

100

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6]

[7]

[8]

[9]

[10]

Δ=1

70

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100



Δ=0

Δ=1

Δ=1

Δ=1




0

0

85

135

100

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]

[5]

[6]

[7]

[8]

Δ=1

240

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100



Δ=3

Δ=1

Δ=1

Δ=1




0

0

15

135

100

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]15

[5]

[6]

[7]

[8]

Δ=1

225

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100




Δ=1

Δ=1

Δ=1




0

0

0

135

100

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]15

[5] 135

[6]

[7]

[8]

Δ=1

90

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100





Δ=1

Δ=1




0

0

0

0

100

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]15

[5] 135

[6] 90

[7]

[8]


0

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100





Δ=1

Δ=1




0

0

0

0

10

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]15

[5] 135

[6] 90

[7]

[8]


0

[11]

[10]

[9]

[8]

[7] 10

[6]

[5] 60

Δ=2

90






Δ=1




0

0

0

0

0

90

0




Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6] 70

[7]

[8]

[9]

[10]


0

[8]

[7]

[6]15

[5] 135

[6] 90

[7]

[8]


0

[11]

[10]

[9]

[8]

[7] 10

[6] 90

[5] 60


0










0

0

0

0

0

0

0




Se infatti al passo 5) si fosse scelta la colonna 4 con Δ=1 anziché la riga 1, anch’essa con Δ=1, si sarebbe pervenuti alla seguente tabella:


Fo

Rn

Pu

An

Mc

Ap

Te


[6] 60

[5] 70

[6]

[7]

[8]

[9]

[10]

Δ=1

70

[8]

[7]

[6]

[5] 135

[6]

[7]

[8]

Δ=1

105

[11]

[10]

[9]

[8]

[7]

[6]

[5] 60

Δ=1

100



Δ=0


Δ=1

Δ=1




0

0

85

0

100

90

0




Non si sarebbe quindi potuto ottenere Δ=3 sulla colonna 3 e quindi le 15 ore dalla sede di An ai clienti di Pu non si sarebbero potute assegnare senza almeno un passo dell’algoritmo di Dantzig.


Tutto questo per sottolineare come il problema di localizzazione restituisca una soluzione in termini di ore lavorative la cui redistribuzione ,per soddisfare i vincoli sugli orari, è decisamente semplice : un passo dell’algoritmo di Dantzig o addirittura nessuno e si poteva quindi anche evitare di ricorrere al LINDO o al foglio di lavoro, risolvendo il problema “carta e penna”.


Pertanto risolvere “in cascata” il problema dei trasporti e quello di localizzazione si è rilevato, nel caso in esame, un metodo soddisfacente: rispetto ai 3335 € della soluzione ottima nel problema di localizzazione semplice ,si ha un’assegnazione fra clienti e dipendenti più pratica a fronte di una spesa aggiuntiva ragionevole di 10 €.




13



Torna alla home page di Ingegneria-elettronica.com