Indice esempi reali
Un problema di trasporto e smaltimento rifiuti
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Smaltimento {
public static void main(String arg[]) throws Exception {
String lp_string =
" 3250 3680 3340 3700 3905 3190 1180 1340 1225 1360 1430 1165 100000 100000 min . \n"
+ " 60 80 100 0 0 0 0 0 0 0 0 0 0 0 le 500 \n"
+ " 0 0 0 0 0 0 60 80 100 0 0 0 0 0 le 900 \n"
+ " 0 0 0 120 110 80 0 0 0 0 0 0 0 0 le 1000 \n"
+ " 0 0 0 0 0 0 0 0 0 120 110 80 0 0 le 450 \n"
+ " 14 0 0 14 0 0 5 0 0 5 0 0 0 0 le 147 \n"
+ " 0 14 0 0 14 0 0 5 0 0 5 0 0 0 le 115 \n"
+ " 0 0 14 0 0 14 0 0 5 0 0 5 0 0 le 95 \n"
+ " 14 14 14 0 0 0 5 5 5 0 0 0 1 0 eq 185 \n"
+ " 0 0 0 14 14 14 0 0 0 5 5 5 0 1 eq 210 \n"
+ " 1 1 1 1 1 1 1 1 1 1 1 1 0 0 integer . ";
InputString lp_input = new InputString(lp_string);
lp_input.setInputFormat("X111-X113:double,X121-X123:double, X211-X213:double,"
+ "X221-X223:double,Y1-Y2:double, TYPE:varstring(9), RHS:double");
MILP lp = new MILP(lp_input);
SolutionType solution_type = lp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
double scorporo = 0;
Solution solution = lp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
if (var.getName().equals("Y1") || var.getName().equals("Y2")) scorporo += var.getValue() * 100000;
}
double valore_ottimo = solution.getOptimumValue();
SscLogger.log("Valore ottimo:" + (valore_ottimo - scorporo));
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Un problema di produzione in uno stabilimento farmaceutico
Uno stabilimento farmaceutico produce un importante farmaco \( F\) la cui composizione è data da due componenti (\(C_1,C_2\)), che costituiscono
i principi attivi fondamentali, e da un componente (\(C_3\)) nel quale sono presenti gli eccipienti.
Questo stabilimento dispone di quattro linee di produzione (\(L_1,L_2,L_3,L_4 => L_i\)), implementate nel corso degli anni e
caratterizzate da livelli differenziati di produttività. Inoltre alcune delle linee sono adibite anche alla produzione di altri farmaci;
di conseguenza su ciascuna linea vi è una disponibilità differenziata di ore. La tabella che segue mostra
quanti decilitri \(d_{ij}\) di ciascun componente j-esimo (\(C_1,C_2,C_3 => C_j\)) vengono prodotti sulla linea di produzione i-esima in un ora. Nella tabella
viene riportato anche il numero di ore di produzione disponibili su ciascuna linea in un mese:
Chiamiamo \(q_1,q_2,q_3\) le quantità da determinare dei componenti \(C_1,C_2,C_3\) da produrre. In via preliminare possiamo dire che il nostro obiettivo è massimizzare la quantià \( Q\) del farmaco \( F\) prodotto dalla miscelazione dei componenti. Supponiamo ad esempio che il farmaco \( F\) sia prodotto combinando con le stesse percentuali i tre componenti, ne consegue che \( Q\) dipende dalla quantità \(q_j\) del componente \(C_j\) che viene prodotto in quantità minore o di cui vi è una disponibilità minore, in quanto i rimanenti componenti sono determinati per proporzione. Un problema di questo tipo è un problema di max{min{\(q_1\),\(q_2\),\(q_3\)}}. Questi tipi di problemi, se la quantità \(Q\) è funzione del minimo dei valori {\(q_1\),\(q_2\),\(q_3\)} e il fine è quello di massimizzare \(Q\), vengono linearizzati formulando il problema nel seguente modo, ovvero ponendo \(Q\) minore o uguale a ciascuno dei valori \(q_1\),\(q_2\),\(q_3\) :
\[ max: Q \] \[ Q \leq q_1 \] \[ Q \leq q_2 \] \[ Q \leq q_3 \]
La casa farmaceutica produce in verità due versioni \(F_a\) e \(F_b\) (le cui quantità indichiamo con \(Q_a , Q_b => Q_{k} \)) di questo farmaco: la prima versione è destinata al Sistema Sanitario Nazionale in cui i principi attivi \(C_1\),\(C_2\) sono in quantità considerata sufficiente; la seconda versione, destinata al mercato, contiene una quantià di principi attivi maggiore rispetto agli eccipienti \(C_3\). Nella tabella che segue riportiamo le proporzioni dei componenti \(C_1,C_2,C_3\) nelle due varianti di farmaco ed il ricavo (\(r_a , r_b => r_k\)) che l'azienda ottiene dalla sua vendita, nonché i costi (\(c_1,c_2,c_3 => c_j\)) di produzione dei componenti \(C_1,C_2,C_3\). Contrattualmente l'azienda deve fornire ogni mese un minimo di 6000 decilitri di farmaco del tipo \(F_a\) al Sistema Sanitario Nazionale.
Nella definizione del modello suddividiamo le quantità \(q_j\) in due parti : (\(q_{ja} , q_{jb} => q_{jk}\)), distinte a seconda che vengano utilizzate per il farmaco \(F_a\) o \(F_b\). Indichiamo con \( X_{ij}\) il numero di ore lavorate sulla linea di produzione i-esima per produrre il componente j-esimo e imponiamo a tale variabile \( X_{ij}\) di essere intera, in quanto le turnazioni degli operai e le turnazioni delle produzioni impongono una gestione del tempo in ore intere. Fatte queste premesse abbiamo nel modello i seguenti vincoli :
Vincoli dovuti alla disponibilità di ore su ogni linea : \[ \sum_{j=1}^{3} X_{1j} \leq 800\] \[ \sum_{j=1}^{3} X_{2j} \leq 800\] \[ \sum_{j=1}^{3} X_{3j} \leq 500\] \[ \sum_{j=1}^{3} X_{4j} \leq 350\]
Vincoli legati alla quantià prodotte (\(q_{ja} , q_{jb}\)) di \(C_1\),\(C_2\),\(C_3\) : \[ (quantità \,di\, C_1\, da\, produrre)\quad q_{1a} + q_{1b} = \sum_{i=1}^{4} X_{i1}*d_{i1} \] \[ (quantità \,di\, C_2\, da\, produrre)\quad q_{2a} + q_{2b} = \sum_{i=1}^{4} X_{i2}*d_{i2} \] \[ (quantità \,di\, C_3\, da\, produrre)\quad q_{3a} + q_{3b} = \sum_{i=1}^{4} X_{i3}*d_{i3} \]
Vincoli per impostare il max { min {... } }, suddivisi per tipologia di farmaco : \[ p_{jk}*Q_k \leq q_{jk} \quad \forall j,k \]
Vincoli di produzione minima del farmaco \(F_a\) : \[ Q_a \geq 6000 \]
Scopo del problema è massimizzare le quantita prodotte dei due farmaci, ma potendo disporre del ricavo per farmaco ed i relativi costi per produrre le diverse componenti, la funzione obiettivo massimizzera l'utile (ricavi - costi) : \[ max : \sum_{k=a}^{b}Q_k*r_k - \sum_{j=1}^{3}\sum_{k=a}^{b}q_{jk}*c_j \]
Sostituendo nei vincoli e nella funzione obiettivo i valori reali otteniamo:
\[ max: 20*Q_a + 32*Q_b -15*q_{1a} -15*q_{1b} -9*q_{2a} -9*q_{2b} -2*q_{3a} -2*q_{3b}\]
\[ Q_a \geq 6000 \] \[ 0.18*Q_a \leq q_{1a} \] \[ 0.20*Q_a \leq q_{2a} \] \[ 0.62*Q_a \leq q_{3a} \] \[ 0.25*Q_b \leq q_{1b}\] \[ 0.26*Q_b \leq q_{2b} \] \[ 0.49*Q_b \leq q_{3b}\] \[ X_{11}+ X_{12}+ X_{13} \leq 800 \] \[ X_{21}+ X_{22}+X_{23} \leq 800 \] \[ X_{31}+ X_{32}+X_{33} \leq 500 \] \[ X_{41}+X_{42}+X_{43} \leq 350 \] \[ q_{1a} + q_{1b} = 9.0* X_{11} +13* X_{21}+18*X_{31} +10*X_{41} \] \[ q_{2a} + q_{2b} = 14* X_{12} +10* X_{22}+4.0*X_{32} +16*X_{42} \] \[ q_{3a} + q_{3b} = 5.0* X_{13} +6* X_{23}+9.0*X_{33} +18*X_{43} \]
\[ X_{ij} \in \mathbb{Z} \,\,e\,\, X_{ij} \ge 0 ,\forall i,\forall j \] \[ Q_k \ge 0 , q_{jk} \ge 0 , \, \forall j, \forall k \]
Risolvendo il problema SSC sotto riportato otteniamo la seguente soluzione ottima : \[ Q_{a}=6000 , Q_{b}=21408 , q_{1a} = 1080 ,q_{2a} = 1200 , q_{3a} = 3720 , q_{1b} = 5352 , q_{2b} = 5576 , q_{3b} = 10490 \]
con un utile complessivo mensile di : 619172 Euro.
| Linea di produzione | Disponibilità di ore sulla linea in un mese | Quantià \(d_{ij}\) in decilitri prodotto in un ora sulla relativa linea di produzione | |||
|---|---|---|---|---|---|
| Componente \( C_1\) | Componente \( C_2\) | Componente \( C_3\) | |||
| Linea \(L_1\) | 800 | 9 | 14 | 5 | |
| Linea \(L_2\) | 800 | 13 | 10 | 6 | |
| Linea \(L_3\) | 500 | 18 | 4 | 9 | |
| Linea \(L_4\) | 350 | 10 | 16 | 18 | |
Chiamiamo \(q_1,q_2,q_3\) le quantità da determinare dei componenti \(C_1,C_2,C_3\) da produrre. In via preliminare possiamo dire che il nostro obiettivo è massimizzare la quantià \( Q\) del farmaco \( F\) prodotto dalla miscelazione dei componenti. Supponiamo ad esempio che il farmaco \( F\) sia prodotto combinando con le stesse percentuali i tre componenti, ne consegue che \( Q\) dipende dalla quantità \(q_j\) del componente \(C_j\) che viene prodotto in quantità minore o di cui vi è una disponibilità minore, in quanto i rimanenti componenti sono determinati per proporzione. Un problema di questo tipo è un problema di max{min{\(q_1\),\(q_2\),\(q_3\)}}. Questi tipi di problemi, se la quantità \(Q\) è funzione del minimo dei valori {\(q_1\),\(q_2\),\(q_3\)} e il fine è quello di massimizzare \(Q\), vengono linearizzati formulando il problema nel seguente modo, ovvero ponendo \(Q\) minore o uguale a ciascuno dei valori \(q_1\),\(q_2\),\(q_3\) :
\[ max: Q \] \[ Q \leq q_1 \] \[ Q \leq q_2 \] \[ Q \leq q_3 \]
La casa farmaceutica produce in verità due versioni \(F_a\) e \(F_b\) (le cui quantità indichiamo con \(Q_a , Q_b => Q_{k} \)) di questo farmaco: la prima versione è destinata al Sistema Sanitario Nazionale in cui i principi attivi \(C_1\),\(C_2\) sono in quantità considerata sufficiente; la seconda versione, destinata al mercato, contiene una quantià di principi attivi maggiore rispetto agli eccipienti \(C_3\). Nella tabella che segue riportiamo le proporzioni dei componenti \(C_1,C_2,C_3\) nelle due varianti di farmaco ed il ricavo (\(r_a , r_b => r_k\)) che l'azienda ottiene dalla sua vendita, nonché i costi (\(c_1,c_2,c_3 => c_j\)) di produzione dei componenti \(C_1,C_2,C_3\). Contrattualmente l'azienda deve fornire ogni mese un minimo di 6000 decilitri di farmaco del tipo \(F_a\) al Sistema Sanitario Nazionale.
| Tipo di farmaco \( F_k\) | Ricavo \( r_k\) in Euro al decilitro | Quantità minima da produrre in decilitri in un mese | Quantità \(p_{jk}\) in decilitri necessaria per ogni decilitro di farmaco prodotto | |||
|---|---|---|---|---|---|---|
| Componente \( C_1\) | Componente \( C_2\) | Componente \( C_3\) | ||||
| Farmaco \(F_a\) | 20 | 6000 | 0.18 | 0.20 | 0.62 | |
| Farmaco \(F_b\) | 32 | - | 0.25 | 0.26 | 0.49 | |
| Costi di produzione \( c_j\) in Euro dei componenti al decilitro | 15 | 9 | 2 | |||
Nella definizione del modello suddividiamo le quantità \(q_j\) in due parti : (\(q_{ja} , q_{jb} => q_{jk}\)), distinte a seconda che vengano utilizzate per il farmaco \(F_a\) o \(F_b\). Indichiamo con \( X_{ij}\) il numero di ore lavorate sulla linea di produzione i-esima per produrre il componente j-esimo e imponiamo a tale variabile \( X_{ij}\) di essere intera, in quanto le turnazioni degli operai e le turnazioni delle produzioni impongono una gestione del tempo in ore intere. Fatte queste premesse abbiamo nel modello i seguenti vincoli :
Vincoli dovuti alla disponibilità di ore su ogni linea : \[ \sum_{j=1}^{3} X_{1j} \leq 800\] \[ \sum_{j=1}^{3} X_{2j} \leq 800\] \[ \sum_{j=1}^{3} X_{3j} \leq 500\] \[ \sum_{j=1}^{3} X_{4j} \leq 350\]
Vincoli legati alla quantià prodotte (\(q_{ja} , q_{jb}\)) di \(C_1\),\(C_2\),\(C_3\) : \[ (quantità \,di\, C_1\, da\, produrre)\quad q_{1a} + q_{1b} = \sum_{i=1}^{4} X_{i1}*d_{i1} \] \[ (quantità \,di\, C_2\, da\, produrre)\quad q_{2a} + q_{2b} = \sum_{i=1}^{4} X_{i2}*d_{i2} \] \[ (quantità \,di\, C_3\, da\, produrre)\quad q_{3a} + q_{3b} = \sum_{i=1}^{4} X_{i3}*d_{i3} \]
Vincoli per impostare il max { min {... } }, suddivisi per tipologia di farmaco : \[ p_{jk}*Q_k \leq q_{jk} \quad \forall j,k \]
Vincoli di produzione minima del farmaco \(F_a\) : \[ Q_a \geq 6000 \]
Scopo del problema è massimizzare le quantita prodotte dei due farmaci, ma potendo disporre del ricavo per farmaco ed i relativi costi per produrre le diverse componenti, la funzione obiettivo massimizzera l'utile (ricavi - costi) : \[ max : \sum_{k=a}^{b}Q_k*r_k - \sum_{j=1}^{3}\sum_{k=a}^{b}q_{jk}*c_j \]
Sostituendo nei vincoli e nella funzione obiettivo i valori reali otteniamo:
\[ max: 20*Q_a + 32*Q_b -15*q_{1a} -15*q_{1b} -9*q_{2a} -9*q_{2b} -2*q_{3a} -2*q_{3b}\]
\[ Q_a \geq 6000 \] \[ 0.18*Q_a \leq q_{1a} \] \[ 0.20*Q_a \leq q_{2a} \] \[ 0.62*Q_a \leq q_{3a} \] \[ 0.25*Q_b \leq q_{1b}\] \[ 0.26*Q_b \leq q_{2b} \] \[ 0.49*Q_b \leq q_{3b}\] \[ X_{11}+ X_{12}+ X_{13} \leq 800 \] \[ X_{21}+ X_{22}+X_{23} \leq 800 \] \[ X_{31}+ X_{32}+X_{33} \leq 500 \] \[ X_{41}+X_{42}+X_{43} \leq 350 \] \[ q_{1a} + q_{1b} = 9.0* X_{11} +13* X_{21}+18*X_{31} +10*X_{41} \] \[ q_{2a} + q_{2b} = 14* X_{12} +10* X_{22}+4.0*X_{32} +16*X_{42} \] \[ q_{3a} + q_{3b} = 5.0* X_{13} +6* X_{23}+9.0*X_{33} +18*X_{43} \]
\[ X_{ij} \in \mathbb{Z} \,\,e\,\, X_{ij} \ge 0 ,\forall i,\forall j \] \[ Q_k \ge 0 , q_{jk} \ge 0 , \, \forall j, \forall k \]
Risolvendo il problema SSC sotto riportato otteniamo la seguente soluzione ottima : \[ Q_{a}=6000 , Q_{b}=21408 , q_{1a} = 1080 ,q_{2a} = 1200 , q_{3a} = 3720 , q_{1b} = 5352 , q_{2b} = 5576 , q_{3b} = 10490 \]
con un utile complessivo mensile di : 619172 Euro.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Farmaceutico {
public static void main(String[] args) throws Exception {
String pl_problem=
"max: 20Qa +32Qb -15q1a -15q1b -9q2a -9q2b -2q3a -2q3b \n"
+"0.18Qa <= q1a\n"
+"0.20Qa <= q2a\n"
+"0.62Qa <= q3a\n"
+"0.25Qb <= q1b\n"
+"0.26Qb <= q2b\n"
+"0.49Qb <= q3b\n"
+"9x11 + 13x21 + 18x31 + 10x41 = q1a + q1b \n"
+"14x12 + 10x22 + 4x32 + 16x42 = q2a +q2b \n"
+"5x13 + 6x23 + 9x33 + 18x43 = q3a + q3b\n"
+"x11 + x12 + x13 <= 800\n"
+"x21 + x22 + x23 <= 800\n"
+"x31 + x32 + x33 <= 500\n"
+"x41 + x42 + x43 <= 350\n"
+"Qa>=6000\n"
+"int x* ";
MILP milp = new MILP(pl_problem);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=milp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
}
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Un problema di assegnazione ispettori-ispezioni
Una multinazionale aerospaziale è dotata di otto siti produttivi che richiedono ispezioni regolari da parte di
ispettori specializzati. Le sedi degli ispettori risiedono in città diverse rispetto a quelle in cui sono ubicati i siti produttivi e
necessitano di viaggi aerei organizzati ad hoc per raggiungere tali sedi, data la presenza di apparecchiature delicate e costose da trasportare.
L'azienda deve pertanto pianificare dei voli per gli ispettori in modo che ciascun gruppo possa
ispezionare quattro degli otto siti produttivi con l'obiettivo di minimizzare i costi complessivi di trasporto aereo.
Poiché gli ispettori (ispettori \(A\) e ispettori \(B\)) partono da due città diverse rispetto ai siti da ispezionare, nel modello si aggiungono queste due località, portando il totale delle località sulla rete di trasporto a dieci. Ipotizzando che la città \(1\) sia la città di partenza per il gruppo ispettivo \(A\) e la città \(5\) per il gruppo ispettivo \(B\), è possibile iniziare a definire i vincoli del modello. In primo luogo, è necessario imporre che le città \(1\) e \(5\) siano le città di partenza degli ispettori; inoltre, ogni sito produttivo deve essere ispezionato una sola volta; si impone inoltre che ciascun gruppo visiti esattamente quattro siti; infine le città \(1\) e \(5\) devono essere anche le città di ritorno degli ispettori dopo le visite ai diversi siti.
Il problema può essere formulato come un "Problema del commesso viaggiatore", in cui ogni località deve essere visitata esattamente una volta e la città di partenza deve coincidere con la città di arrivo al termine del ciclo di visite ispettive. Riportiamo i costi aerei \( c_{ij}\) per recarsi, da parte di un gruppo completo, dalla citta \(i\) alla città \(j\) espressi in migliaia di Euro:
Nella tabella dei costi precedentemente descritta, nel caso in cui non vi sia un collegamento diretto tra una città di origine e una di destinazione, è stato inserito lo zero: in questo modo rappresentiamo la mancanza di collegamento tra due città. Introduciamo inoltre il concetto di "tratta", come il passaggio intermedio da una città di origine ad una di destinazione all'interno dell'itinerario. Essendo quattro le città da visitare per ciascun gruppo e dovendo tornare alle proprie città di partenza, ogni gruppo deve effettuare un itenerario di cinque tratte. Inoltre il gruppo ispettivo \( A\) deve partire dal nodo \( 1\) (la città dove risiede) e il gruppo ispettivo \( B\) dal nodo \( 5 \text{.} \) Infine, abbiamo che per ciascun gruppo la città di arrivo nella tratta \( t\) deve conincidere con la città di partenza nel tratto \( t+1\). Fatte queste premesse i vincoli del problema risultano, se indichiamo con \( X_{kijt}\) una variabile binaria che risulta pari ad uno se il gruppo ispettivo \( k\)-esimo, nel suo itinerario, va dalla città \( i\)-esima alla città \( j\)-esima durante il tratto \( t\)-esimo ( \(\forall (i,j)\) : \(i \neq j\) e \( c_{ij} \gt 0\) ):
Vincoli dovuti al fatto che il gruppo di ispettori \( A\) parte dalla città \( 1\) nel primo tratto \( t=1\) e dovrà tornare nella città \( 1\) nel tratto finale \( t=5\): \[ \sum_{j=1}^{10} X_{A1j1} = 1 \,,\, \sum_{i=1}^{10} X_{Ai15} = 1 \]
Vincoli dovuti al fatto che il gruppo di ispettori \( B\) parte dalla città \( 5\) nel primo tratto \( t=1\) e dovrà tornare nella città \( 5\) nel tratto finale \( t=5\): \[ \sum_{j=1}^{10} X_{B5j1} = 1 \,,\, \sum_{i=1}^{10} X_{Bi55} = 1 \]
Vincoli dovuti al fatto che solo uno dei due gruppi deve arrivare nella città \( j\), rispettivamente una sola volta. \[ \sum_{k=A}^{B}\sum_{i=1}^{10} \sum_{t=1}^{5} X_{kijt} = 1 \,,\, \forall j\]
Vincoli dovuti al fatto che ciascun gruppo ispettivo deve effettuare ciascun tratto \( t\) solo una volta : \[\sum_{i=1}^{10} \sum_{j=1}^{10} X_{kijt} = 1 \,,\, \forall k , \forall t\]
Vincoli dovuti al fatto che per ciascun gruppo ispettivo la località di arrivo nel tratto \( t\) deve conincidere con quella di partenza nel tratto \( t+1\) \[\sum_{i=1}^{10} X_{kizt} = \sum_{j=1}^{10} X_{kzj(t+1)} \,,\, \forall k , \forall t , \forall z \]
Infine la funzione obiettivo da minimizzare risulta: \[ min : \sum_{k=A}^{B} \sum_{i=1}^{10}\sum_{j=1}^{10}\sum_{t=1}^{5} X_{kijt}*c_{ij} \]
\[ X_{kijt} \in \{0,1\} ,\forall k, \forall t, \forall (i, j) : i \neq j \, \text{ e } \, c_{ij} \gt 0 \]
Considerando tali restrizioni, si configura un sistema caratterizzato da 480 variabili e 104 equazioni lineari, tutte relative a variabili binarie. Scrivendo il problema in SSC (sotto riportato), dato l'ingente numero di variabili e restrizioni coinvolte, anziché inserirli manualmente come testo, si è adottato un approccio di generazione dinamica delle variabili e dei vincoli. Il problema SSC ammette soluzione ottima data da :
\[ Ispettori \,\,A : X_{A191}=1 , X_{A922}=1, X_{A233}=1, X_{A344}=1, X_{A415}=1 \] \[ Ispettori \,\,B : X_{B561}=1 , X_{B672}=1, X_{B7103}=1, X_{B1084}=1, X_{B855}=1 \]
Ovvero al gruppo ispettivo \( A\) risulta assegnato il seguente itinerario :(1,9) => (9,2) => (2,3) => (3,4) => (4,1); mentre al gruppo ispettivo \( B\) il seguente : (5,6) => (6,7) => (7,10) => (10,8) => (8,5).
Per un costo complessivo totale di 80000 Euro.
Poiché gli ispettori (ispettori \(A\) e ispettori \(B\)) partono da due città diverse rispetto ai siti da ispezionare, nel modello si aggiungono queste due località, portando il totale delle località sulla rete di trasporto a dieci. Ipotizzando che la città \(1\) sia la città di partenza per il gruppo ispettivo \(A\) e la città \(5\) per il gruppo ispettivo \(B\), è possibile iniziare a definire i vincoli del modello. In primo luogo, è necessario imporre che le città \(1\) e \(5\) siano le città di partenza degli ispettori; inoltre, ogni sito produttivo deve essere ispezionato una sola volta; si impone inoltre che ciascun gruppo visiti esattamente quattro siti; infine le città \(1\) e \(5\) devono essere anche le città di ritorno degli ispettori dopo le visite ai diversi siti.
Il problema può essere formulato come un "Problema del commesso viaggiatore", in cui ogni località deve essere visitata esattamente una volta e la città di partenza deve coincidere con la città di arrivo al termine del ciclo di visite ispettive. Riportiamo i costi aerei \( c_{ij}\) per recarsi, da parte di un gruppo completo, dalla citta \(i\) alla città \(j\) espressi in migliaia di Euro:
| Costi \( c_{ij}\) in migliaia di Euro |
città 1 | città 2 | città 3 | città 4 | città 5 | città 6 | città 7 | città 8 | città 9 | città 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| città 1 | 0 | 10 | 11 | 15 | 23 | 0 | 0 | 33 | 5 | 0 |
| città 2 | 11 | 0 | 10 | 0 | 17 | 18 | 0 | 29 | 3 | 0 |
| città 3 | 13 | 10 | 0 | 8 | 12 | 0 | 0 | 18 | 0 | 0 |
| città 4 | 15 | 0 | 12 | 0 | 0 | 0 | 0 | 15 | 0 | 0 |
| città 5 | 25 | 17 | 12 | 0 | 0 | 5 | 5 | 15 | 0 | 5 |
| città 6 | 0 | 18 | 0 | 0 | 5 | 0 | 6 | 0 | 20 | 0 |
| città 7 | 0 | 0 | 0 | 0 | 5 | 6 | 0 | 20 | 0 | 6 |
| città 8 | 33 | 29 | 18 | 15 | 15 | 0 | 20 | 0 | 0 | 9 |
| città 9 | 8 | 3 | 0 | 0 | 0 | 20 | 0 | 0 | 0 | 0 |
| città 10 | 0 | 0 | 0 | 0 | 5 | 0 | 6 | 7 | 0 | 0 |
Nella tabella dei costi precedentemente descritta, nel caso in cui non vi sia un collegamento diretto tra una città di origine e una di destinazione, è stato inserito lo zero: in questo modo rappresentiamo la mancanza di collegamento tra due città. Introduciamo inoltre il concetto di "tratta", come il passaggio intermedio da una città di origine ad una di destinazione all'interno dell'itinerario. Essendo quattro le città da visitare per ciascun gruppo e dovendo tornare alle proprie città di partenza, ogni gruppo deve effettuare un itenerario di cinque tratte. Inoltre il gruppo ispettivo \( A\) deve partire dal nodo \( 1\) (la città dove risiede) e il gruppo ispettivo \( B\) dal nodo \( 5 \text{.} \) Infine, abbiamo che per ciascun gruppo la città di arrivo nella tratta \( t\) deve conincidere con la città di partenza nel tratto \( t+1\). Fatte queste premesse i vincoli del problema risultano, se indichiamo con \( X_{kijt}\) una variabile binaria che risulta pari ad uno se il gruppo ispettivo \( k\)-esimo, nel suo itinerario, va dalla città \( i\)-esima alla città \( j\)-esima durante il tratto \( t\)-esimo ( \(\forall (i,j)\) : \(i \neq j\) e \( c_{ij} \gt 0\) ):
Vincoli dovuti al fatto che il gruppo di ispettori \( A\) parte dalla città \( 1\) nel primo tratto \( t=1\) e dovrà tornare nella città \( 1\) nel tratto finale \( t=5\): \[ \sum_{j=1}^{10} X_{A1j1} = 1 \,,\, \sum_{i=1}^{10} X_{Ai15} = 1 \]
Vincoli dovuti al fatto che il gruppo di ispettori \( B\) parte dalla città \( 5\) nel primo tratto \( t=1\) e dovrà tornare nella città \( 5\) nel tratto finale \( t=5\): \[ \sum_{j=1}^{10} X_{B5j1} = 1 \,,\, \sum_{i=1}^{10} X_{Bi55} = 1 \]
Vincoli dovuti al fatto che solo uno dei due gruppi deve arrivare nella città \( j\), rispettivamente una sola volta. \[ \sum_{k=A}^{B}\sum_{i=1}^{10} \sum_{t=1}^{5} X_{kijt} = 1 \,,\, \forall j\]
Vincoli dovuti al fatto che ciascun gruppo ispettivo deve effettuare ciascun tratto \( t\) solo una volta : \[\sum_{i=1}^{10} \sum_{j=1}^{10} X_{kijt} = 1 \,,\, \forall k , \forall t\]
Vincoli dovuti al fatto che per ciascun gruppo ispettivo la località di arrivo nel tratto \( t\) deve conincidere con quella di partenza nel tratto \( t+1\) \[\sum_{i=1}^{10} X_{kizt} = \sum_{j=1}^{10} X_{kzj(t+1)} \,,\, \forall k , \forall t , \forall z \]
Infine la funzione obiettivo da minimizzare risulta: \[ min : \sum_{k=A}^{B} \sum_{i=1}^{10}\sum_{j=1}^{10}\sum_{t=1}^{5} X_{kijt}*c_{ij} \]
\[ X_{kijt} \in \{0,1\} ,\forall k, \forall t, \forall (i, j) : i \neq j \, \text{ e } \, c_{ij} \gt 0 \]
Considerando tali restrizioni, si configura un sistema caratterizzato da 480 variabili e 104 equazioni lineari, tutte relative a variabili binarie. Scrivendo il problema in SSC (sotto riportato), dato l'ingente numero di variabili e restrizioni coinvolte, anziché inserirli manualmente come testo, si è adottato un approccio di generazione dinamica delle variabili e dei vincoli. Il problema SSC ammette soluzione ottima data da :
\[ Ispettori \,\,A : X_{A191}=1 , X_{A922}=1, X_{A233}=1, X_{A344}=1, X_{A415}=1 \] \[ Ispettori \,\,B : X_{B561}=1 , X_{B672}=1, X_{B7103}=1, X_{B1084}=1, X_{B855}=1 \]
Ovvero al gruppo ispettivo \( A\) risulta assegnato il seguente itinerario :(1,9) => (9,2) => (2,3) => (3,4) => (4,1); mentre al gruppo ispettivo \( B\) il seguente : (5,6) => (6,7) => (7,10) => (10,8) => (8,5).
Per un costo complessivo totale di 80000 Euro.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
public class CommessoViaggiatore {
public static void main(String[] args) throws Exception {
//matrice dei costi
double cij[][] =
{ { 0, 10, 11, 15, 23, 0, 0, 33, 5, 0 },
{ 11, 0, 10, 0, 17, 18, 0, 29, 3, 0 },
{ 13, 10, 0, 8, 12, 0, 0, 18, 0, 0 },
{ 15, 0, 12, 0, 0, 0, 0, 15, 0, 0 },
{ 25, 17, 12, 0, 0, 5, 5, 15, 0, 5 },
{ 0, 18, 0, 0, 5, 0, 6, 0,20, 0 },
{ 0, 0, 0, 0, 5, 6, 0, 20, 0, 6 },
{ 33, 29, 18, 15, 15, 0, 20, 0, 0, 9 },
{ 8, 3, 0, 0, 0, 20, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 5, 0, 6, 7, 0, 0 }};
char ispettori[] = { 'A', 'B' };
int numero_tratte=5;
// definizione funzione obiettivo.
String fo = "min:";
for (int d = 0; d < ispettori.length; d++) {
for (int t = 0; t < numero_tratte; t++) {
for (int i = 0; i < cij.length; i++) {
for (int j = 0; j < cij[0].length; j++) {
if (cij[i][j] != 0) {
fo += "+" + cij[i][j] + "X" + ispettori[d] + (i + 1) + "" + (j + 1) + "" + (t + 1);
}
}
}
}
}
SscLogger.log(fo);
// Vincoli1: gli ispettori A partono dalla citta 1 durante il tratto 1
String vincoli1 = "\n";
for (int j = 0; j < cij[0].length; j++) {
if (cij[0][j] != 0) {
vincoli1 += " +XA1" + (j + 1) + "1";
}
}
vincoli1 += " =1\n";
SscLogger.log(vincoli1);
// Vincoli2: gli ispettori A ritornano alla citta 1 durante il tratto 5
String vincoli2 = "";
for (int i = 0; i < cij.length; i++) {
if (cij[i][0] != 0) {
vincoli2 += " +XA" + (i + 1) + "15";
}
}
vincoli2 += " =1\n";
SscLogger.log(vincoli2);
// Vincoli3: gli ispettori B partono dalla citta 5 durante il tratto 1
String vincoli3 = "";
for (int j = 0; j < cij[4].length; j++) {
if (cij[4][j] != 0) {
vincoli3 += " +XB5" + (j + 1) + "1";
}
}
vincoli3 += " =1\n";
SscLogger.log(vincoli3);
// Vincoli4: gli ispettore B ritornano alla citta 5 durante il tratto 5
String vincoli4 = "";
for (int i = 0; i < cij.length; i++) {
if (cij[i][4] != 0) {
vincoli4 += " +XB" + (i + 1) + "55";
}
}
vincoli4 += " =1\n";
SscLogger.log(vincoli4);
// Vincoli5: ogni gruppo deve visitare una citta una sola volta.
String vincoli5 = "";
for (int j = 0; j < cij[0].length; j++) {
for (int d = 0; d < ispettori.length; d++) {
for (int t = 0; t < numero_tratte; t++) {
for (int i = 0; i < cij.length; i++) {
if (cij[i][j] != 0) {
vincoli5 += " +X" + ispettori[d] + (i + 1) + "" + (j + 1) + "" + (t + 1);
}
}
}
}
vincoli5 += " =1\n";
}
SscLogger.log(vincoli5);
// Vincoli6: ciascun gruppo deve effettuare ciascun tratto solo una volta
String vincoli6 = "";
for (int d = 0; d < ispettori.length; d++) {
for (int t = 0; t < numero_tratte; t++) {
for (int i = 0; i < cij.length; i++) {
for (int j = 0; j < cij[0].length; j++) {
if (cij[i][j] != 0) {
vincoli6 += " +X" + ispettori[d] + (i + 1) + "" + (j + 1) + "" + (t + 1);
}
}
}
vincoli6 += " =1\n";
}
}
SscLogger.log(vincoli6);
// Vincoli7: per ciascun gruppo la localita di arrivo nel tratto t
// deve conincidere con quella di partenza nel tratto t+1
String vincoli7 = "";
for (int d = 0; d < ispettori.length; d++) {
for (int t = 0; t < numero_tratte-1; t++) {
for (int k = 0; k < cij.length; k++) {
for (int i = 0; i < cij.length; i++) {
if (cij[i][k] != 0) {
vincoli7 += " +X" + ispettori[d] + (i + 1) + "" + (k + 1) + "" + (t + 1);
}
}
vincoli7+= " =";
for (int j = 0; j < cij[0].length; j++) {
if (cij[k][j] != 0) {
vincoli7 += " +X" + ispettori[d] + (k + 1) + "" + (j + 1) + "" + (t + 2);
}
}
vincoli7 += "\n";
}
vincoli7 += "\n";
}
}
SscLogger.log(vincoli7);
String pl_problem = fo + vincoli1 + vincoli2 + vincoli3 + vincoli4 + vincoli5 +
vincoli6 + vincoli7 + "\n bin ALL";
MILP milp = new MILP(pl_problem);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution soluzione = milp.getSolution();
for (Variable var : soluzione.getVariables()) {
if(var.getValue()!=0) SscLogger.log("Variable name :" + var.getName() + " value :" + var.getValue());
}
SscLogger.log("valore f.o. :" + soluzione.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Per il trasporto dei rifiuti l'azienda chimica dispone esclusivamente di due tipologie di automezzi (\(A_1,A_2 => A_k\)); queste due tipologie di automezzi presentano una portata massima di trasporto per singolo viaggio (\(q_1,q_2 => q_k \)), un limite massimo di km giornalmente percorribili per singolo automezzo (\(km_1,km_2 => km_k\)) ed un costo complessivo di trasporto al km (\(ct_1,ct_2 => ct_k \)), riassumendo :
Le distanze (\(d_{ij}\)) in km tra i siti produttivi e quelli di smaltimento sono le seguenti :
Nella data presa in esame, le tre discariche forniscono all'azienda chimica le seguenti quantità di rifiuti da trattare, accompagnate dai relativi costi di smaltimento (\(cs_1,cs_2,cs_3 => cs_j\)) per tonnellata:
Nella data presa in esame i due siti produttivi presentano le seguenti quantita di rifiuti da smaltire :
L'azienda chimica dispone di due tipologie di automezzi per il trasporto (\( A_1,A_2 => A_k \) ); più precisamente il sito produttivo \( P_1 \) dispone di un mezzo di tipo \( A_1\) e due mezzi di tipo \( A_2 \) , mentre il sito produttivo \( P_2 \) dispone di due mezzi di tipo \( A_1\) ed un mezzo di tipo \( A_2 \). Per cui considerando il limite di km giornalieri abbiamo complesivamente le seguenti quantità di km effettuabili dai due siti in base al numero di automezzi disponibili:
Indichiamo con \( X_{kij}\) il numero di viaggi che un automezzo di tipo \( A_k\) compie dal sito di produzione \( P_i\) alla discarica \( D_j\). Precisiamo che dal punto di vista del modello ogni viaggio comprende anche il ritorno alla sede di partenza. Le variabili \( X_{kij}\) sono variabili intere non negative. Effettuate queste premesse abbiamo in base alle limitazioni introdotte i seguenti vincoli.
Vincoli di percorrenza per gli automezzi di tipo \( A_1\) e \( A_2\) che partono da \( P_1\) (si moltiplica per due per il viaggio di ritorno):
\[ 2*\sum_{j=1}^{3} X_{11j}*d_{1j} \leq 500\] \[ 2*\sum_{j=1}^{3} X_{21j}*d_{1j} \leq 450*2\]
Vincoli di percorrenza per gli automezzi di tipo \( A_1\) e \( A_2\) che partono da \( P_2\) (si moltiplica per due per il viaggio di ritorno):
\[ 2*\sum_{j=1}^{3} X_{12j}*d_{2j} \leq 500*2\] \[ 2*\sum_{j=1}^{3} X_{22j}*d_{2j} \leq 450\]
Vincoli capacità di smaltimento in tonnellate delle tre discariche \( D_1,D_2,D_3\) :
\[ \sum_{k=1}^{2}\sum_{i=1}^{2} X_{ki1}*q_k \leq 147\] \[ \sum_{k=1}^{2}\sum_{i=1}^{2} X_{ki2}*q_k \leq 115\] \[ \sum_{k=1}^{2}\sum_{i=1}^{2} X_{ki3}*q_k \leq 95\]
Vincoli legati alla produzione di rifiuti; le quantità trasportate e smaltite non possono essere maggiori delle quantita da smaltire presenti nei due siti produttivi :
\[ \sum_{k=1}^{2}\sum_{j=1}^{3} X_{k1j}*q_k \leq 185\] \[ \sum_{k=1}^{2}\sum_{j=1}^{3} X_{k2j}*q_k \leq 210\]
Ricordiamo che uno degli obiettivi e anche quello di minimizzare la quantita di rifiuti non smaltita. Chiamiamo con \( Y_i\) la quantita residua non smaltita dal sito \( P_i\), allora i precedenti vincoli diventano :
\[ \sum_{k=1}^{2}\sum_{j=1}^{3} X_{k1j}*q_k + Y_1 = 185\] \[ \sum_{k=1}^{2}\sum_{j=1}^{3} X_{k2j}*q_k + Y_2 = 210\]
I costi di trasporto risultano essere (si moltiplica per due in quanto i tragitti \( X_{kij}\) comprendono anche il ritorno alla sede di partenza): \[ 2*\sum_{k=1}^{2}\sum_{i=1}^{2}\sum_{j=1}^{3} X_{kij}*d_{ij} *ct_k \]
I costi di smaltimento risultano essere : \[ \sum_{k=1}^{2}\sum_{i=1}^{2}\sum_{j=1}^{3} X_{kij}*q_k*cs_j \]
Un altro costo risulta essere quello di tenere in giacenza rifiuti non smaltiti, per cui la funzione obiettivo deve anche cercare di minimizzare il quantitativo di rifiuti non smaltiti \( Y_i\). Per fare ciò assegnamo nella funzione obiettivo alle variabili \( Y_i\) un coefficente (penalità) \( M\) molto elevato; in definitiva la funzione obiettivo finale da minimizzare risulta: \[ min : 2*\sum_{k=1}^{2}\sum_{i=1}^{2}\sum_{j=1}^{3} X_{kij}*d_{ij} *ct_k + \sum_{k=1}^{2}\sum_{i=1}^{2}\sum_{j=1}^{3} X_{kij}*q_k*cs_j + \sum_{i=1}^{2}Y_i*M \]
Sostituendo nei vincoli e nella funzione obiettivo i valori reali otteniamo:
\[ min: 3250*X_{111} + 3680*X_{112}+ 3340*X_{113} + 3700*X_{121} + 3905*X_{122}+ 3190*X_{123} +\] \[ 1180*X_{211} + 1340*X_{212}+ 1225*X_{213} + 1360*X_{221} + 1430*X_{222}+ 1165*X_{223} +100000*Y_1 + 100000*Y_2 \]
\[ 60* X_{111} +80* X_{112}+ 100*X_{113} \leq 500 \] \[ 60* X_{211} +80* X_{212}+ 100*X_{213} \leq 900 \] \[ 120* X_{121} +110* X_{122}+ 80*X_{123} \leq 1000 \] \[ 120* X_{221} +110* X_{222}+ 80*X_{223} \leq 450 \] \[ 14*X_{111} + 14*X_{121} + 5*X_{211} + 5*X_{221} \leq 147 \] \[ 14*X_{112} + 14*X_{122} + 5*X_{212} + 5*X_{222} \leq 115 \] \[ 14*X_{113} + 14*X_{123} + 5*X_{213} + 5*X_{223} \leq 95 \] \[ 14*X_{111} + 14*X_{112}+ 14*X_{113} + 5*X_{211} + 5*X_{212}+ 5*X_{213} +Y_1 = 185 \] \[ 14*X_{121} + 14*X_{122}+ 14*X_{123} + 5*X_{221} + 5*X_{222}+ 5*X_{223} +Y_2 = 210 \]
\[ X_{kij} \in \mathbb{Z} \,\,e\,\, X_{kij} \ge 0 , \forall k ,\forall i,\forall j \]
Risolvendo il problema SSC sotto riportato otteniamo la seguente soluzione ottima : \[ X_{111}=8 , X_{122}=5 , X_{123} = 5 ,X_{211} = 7 , X_{212} = 6 , X_{223} = 5 , Y_1 = 8.0 , Y_2 = 45 \]
con un costo complessivo di : 83600 Euro.