Ricerca operativa - problema del trasporto

POSSIBILE RISOLUZIONE DEL PROBLEMA IN ESAME:

Iniziamo con l’individuazione delle variabili decisionali, partiamo dalla funzione obiettivo richiesta dal

problema.

Tenendo conto della funzione obiettivo (minimizzazione dei costi complessivi di trasporto e dei costi

complessivi di produzione), per la definizione delle variabili decisionali facciamo le seguenti considerazioni.

I costi di trasporto unitari (cioè quanto costa trasportare una merce da una fabbrica ad una città)

costituiscono una quantità che lega singolarmente ogni fabbrica con ciascuna città.

Quindi un certo numero di variabili decisionali coinvolge due indici (l’indice che indica la fabbrica e l’indice

che indica la città). Di conseguenza indichiamo con x la quantità di merce che viene trasportata dalla

ij

fabbrica F alla città C (con i = 1, 2, 3, 4, 5 e j = 1, 2, 3, 4, 5). Tale quantità dovrà essere ovviamente non

i j 2

negativa.

A questo punto, poiché si è deciso di risolvere il problema con il foglio elettronico Excel, si è pensato di

creare un’altra tabella, in cui vengono messi i costi unitari di ogni fabbrica con le varie città (si sa dal testo

del problema che : per trasportare 1Kg di merce per 1 Km, il costo è di 10 dollari):

Le distanze tra fabbriche e città, sono state calcolate con il Teorema di Pitagora (trovando la diagonale del

triangolo). Per esempio, la distanza tra la Citta3 e la Fabbrica1 è data da : =RADQ((2)^2+(1)^2)).

VINCOLI IMPOSTATI NEL RISOLUTORE DEL PROGRAMMA EXCEL :

Per ogni Fabbrica i la quantità totale di prodotto inviata da esso deve essere pari alla quantità di prodotto a

i

in esso immagazzinata. La quantità totale di prodotto inviata dalla Fabbrica i è data dalla formula :

n

 

x a i = 1, … , m . Esempio (Fabbrica1) : x + x + x + x + x = 1000

11 12 13 14 15

ij i

1

j

Per ogni Citta j la quantità totale di prodotto ricevuta da esso deve essere pari alla quantità di prodotto b j

da esso richiesta. La quantità totale di prodotto ricevuta dalla Citta j è data dalla formula :

m

  j = 1, . . . , n . Esempio (Citta1) : x + x + x + x + x = 500

x b 11 21 31 41 51

ij i

1

i

I vincoli impostati nel risolutore del programma Excel sono, quindi, due :

- Uguagliare la produzione delle fabbriche hai valori presenti nel problema;

- Uguagliare la richiesta dei beni da parte delle città hai valori che compaiono nella tabella del testo.

Le celle evidenziate in giallo, nella prima tabella, sono variabili. Sarà il risolutore ad attribuire loro i relativi

valori, una volta soddisfatta la funzione obiettivo.

Fig 1.0 celle variabili funzione obiettivo

FUNZIONE OBIETTIVO :

Se inviare un’unità di prodotto dalla Fabbrica i alla Città j ha costo pari a c , inviarne una quantità x ha

ij ij

costo pari a c x . Sommando su tutte le possibili coppie Fabbrica-Città, abbiamo la seguente formula per

ij ij

l’obiettivo: 3

m n

 .

c x

ij ij

 

i 1 j 1

Per il calcolo della funzione obiettivo (impostando l’opzione di minimizzazione nel risolutore) si è fatto uso

della funzione “=MATR.SOMMA.PRODOTTO(B3:F7;K3:O7)”.

In conclusione, il valore della funzione obiettivo è di 78284,27125 e, la distribuzione della merce tra le varie

città (ottenendo il minimo costo di trasporto) è rappresentata nella Fig 1.0.

RISOLUZIONE SECONDA PARTE DEL PROBLEMA :

Il secondo quesito del problema chiede di trovare la posizione ottimale della nuova fabbrica in modo da

ridurre i costi totali di trasporto alle varie città.

La prima parte del procedimento è, pressoché, identica. Alle due tabelle sopra evidenziate, ne va aggiunta

una terza in cui vengono trascritti i costi che la Fabbrica5 ha verso le città (variando di volta in volta la

posizione, senza andare ad occupare i punti nei quali sono già presenti fabbriche o città).

È stata poi aggiunta una nuova colonna in cui compaiono delle variabili binarie (che possono, quindi,

assumere i soli valori di “1” e “0”). Esse servono al risolutore per soddisfare la funzione obiettivo.

Il risolutore, infatti, una volta impostati i vincoli troverà, automaticamente (facendo tutte le possibili

prove), il punto in cui posizionare la nuova città massimizzando il profitto e minimizzando i trasporti.

funzione obiettivo 4

Nella tabella dei costi, nelle celle che intersecano la Fabbrica5 con le città è stata immessa la formula per

calcolare la matrice somma-prodotto delle colonne delle città presenti nella tabella “costi decisionali” per

le variabili decisionali (presenti nella stessa tabella). In questo modo, la funzione obiettivo verrà calcolata in

base alla posizione della nuova fabbrica nella posizione migliore e con costo minore .

Per esempio, nella cella K7 è stata inserita la seguente formula :

.

VINCOLI IMPOSTATI NEL RISOLUTORE DEL PROGRAMMA EXCEL :

I vincoli impostati sono gli stessi del punto precedente con l’aggiunta di altri. Si deve quindi :

- Uguagliare la produzione delle fabbriche hai valori presenti nel problema;

- Uguagliare la richiesta dei beni da parte delle città hai valori che compaiono nella tabella del testo.

Inoltre :

- Si vincolano le variabili decisionali a valori binari (questa colonna, nella seconda parte dell’esercizio

assumerà valori variabili, assieme alle celle evidenziate in giallo a cui il risolutore assegnerà le

quantità di cibo da trasportare alle città);

- Si vincola la somma delle variabili decisionali ad “1” (per permettere al programma di trovare

l’unica soluzione ottimale al problema). 5