Indice esempi reali

Un problema di ottimizzazione di un Portafoglio titoli


Il dipartimento commerciale e gestione patrimoniale di una società di servizi finanziari incarica uno dei suoi consulenti finanziari di seguire un nuovo cliente. Il consulente finanziario contatta il nuovo cliente e fissa un incontro per comprenderne le esigenze finanziarie ed il profilo. Durante questo colloquio il consulente finanziario apprende che il cliente desidera investire 100.000 Euro per un periodo di 7 anni e rileva che la sua propensione al rischio risulta essere nella media. Basandosi su queste informazioni, il consulente seleziona un insieme di obbligazioni, titoli di stato, azioni ed ETF che dovrebbero permettere la costruzione di un portafoglio personalizzato e di raggiungere gli obiettivi di investimento desiderati. La tabella che segue elenca i titoli selezionati dal consulente:


Nome
investimento
Cedola o dividendo del
tilolo \( k\) nell'anno \( t\) come
frazione di un Euro investito
(\( c_{kt}\))
Totale
cedole
(\( c_{k}\))
Tipologia Durata
in anni
(\( d_{k}\))
Livello
rischio
(\( r_{k}\))
Valuta Costi
fissi
in Euro
(\(f_k\))
Taglio
in
Euro
(\(I_k\))
Codice
titolo
(\( k\))
1° anno 2° anno 3° anno 4° anno 5° anno 6° anno 7° anno
RBS tasso fisso step up 6Y 0,031 0,036 0,041 0,046 0,051 0,056 - 0,261 Obbligaz.
Distribuzione
6 1 Sterlina 0 1 A
Treasury USA 7Y 0,044 0,044 0,044 0,044 0,044 0,044 0,044 0,308 Obbligaz.
Distribuzione
7 1 Dollaro 0 1 B
BTP Italia 3Y 0,035 0,035 0,035 - - - - 0,105 Obbligaz.
Distribuzione
3 1,5 Euro 0 1 C
BUND Germania 7Y 0,027 0,027 0,027 0,027 0,027 0,027 0,027 0,189 Obbligaz.
Distribuzione
7 1 Euro 0 1 D
BTP Italia 3Y - - - - 0,033 0,033 0,033 0,099 Obbligaz.
Distribuzione
3 1,5 Euro 0 1000 E
BTP Italia 7Y 0,040 0,040 0,040 0,040 0,040 0,040 0,040 0,280 Obbligaz.
Distribuzione
7 2 Euro 0 1 F
BOT Italia 1Y 0,030 - - - - - - 0,030 Obbligaz.
Distribuzione
1 1 Euro 0 1 G1
BOT Italia 1Y - 0,030 - - - - - 0,030 Obbligaz.
Distribuzione
1 1 Euro 0 1 G2
BOT Italia 1Y - - - 0,030 - - - 0,030 Obbligaz.
Distribuzione
1 1 Euro 0 1 G4
BOT Italia 1Y - - - - - - 0,028 0,028 Obbligaz.
Distribuzione
1 1 Euro 0 1 G7
Obblig. TeleKom 7Y 0,070 0,070 0,070 0,070 0,070 0,070 0,070 0,490 Obbligaz.
Distribuzione
7 3 Euro 0 1 H
Azioni EMNEL 0,070 0,070 0,080 0,080 0,080 0,090 0,090 0,560 Azionario 7 4 Euro 0 1 I
Obblig. EMNEL 4Y - 0,0625 0,0625 0,0625 0,0625 - - 0,250 Obbligaz.
Distribuzione
4 1,5 Euro 0 1 L
ETF Core S&P 500 UCITS USD 0 0 0 0 0 0 0,900 0,900 ETF Azion.
Accumulazione
7 4 Dollaro 50 1 M
ETF Core MSCI Europe UCITS ETF 0 0 0 0 0 0 0,600 0,600 ETF Azion.
Accumulazione
7 4 Euro 50 1 N
ETF Core Govt Bond UCITS 0 0 0 0 0 0 0,310 0,310 ETF Obbligaz.
Accumulazione
7 1 Euro 50 1 O


La tabella sopra riportata elenca per ogni titolo \( k\) le quantità \( c_{kt}\), ovvero o le cedole annuali attese nell'anno \( t\) (nel caso di titolo a distribuzione) o il rendimento a scadenza atteso nell'anno \( t=7\) (nel caso di titolo ad accumulazione), il loro totale \( c_{k}\), il tipo di titolo (azioni/obbligazioni), la durata \( d_{k}\), il livello di rischio \( r_{k}\), la presenza di costi fissi in entrata \( f_{k}\), la valuta ed infine il taglio minimo di acquisto (Increment) \( I_{k}\).

In base alla caratteristiche del cliente, il consulente ritiene che la propensione media al rischio debba essere, su una scala che va da 1 a 5, al livello di 2 (rischio medio). Inoltre, sempre nella ricerca della riduzione del rischio, introduce ulteriori limitazioni legate in particolar modo alla diversificazione degli investimenti.

In definitiva per impostare un livello di rischio adeguato, impone che:
1) Il rischio medio totale non superi il livello di 2.
2) L'investimento in dollari non superi il 30% (30.000 Euro), questo per ridurre il rischio di fluttuazione della valuta (rischio cambio).
3) L'investimento in sterline non superi il 15% (15.000 Euro).
4) Nel caso di più tipologie di investimento, tutte relative ad una stessa società emittente, occorre investire solamente in uno tra gli strumenti finanziari ad essa riconducibili (ad esempio, obbligazioni ed azioni di una stessa società).

Tra i titoli selezionati occorre distinguere tra quelli che distribuiscono cedole annuali (distribuzione), dagli altri che reinvestono automaticamente i proventi ed i dividendi nello stesso titolo (accumulazione). Nel caso di questi ultimi, al momento della scadenza o della liquidazione dell'investimento, si riceve la remunerazione sia del capitale investito che dei dividendi/interessi accumulati, mentre nel caso dei primi i dividenti/interessi acquistiti al termine di ciascun anno possono essere reinvestiti in altri strumenti nell'anno successivo.

Le durate in anni dei titoli riportate nella tabella sopra descritta o sono relative alla naturale scadenza di obbligazioni o alla durata che si ritiene più opportuna per investire in un titolo; ad esempio per i titoli azionari il consulente si propone di investire per l'intero arco temporale di 7 anni. La presenza nella tabella, nella sezione cedole, del simbolo '-' , sta ad indicare che quel titolo non è valido in quello specifico anno e che quindi non può restituire cedole.

Una volta definite tutte queste limitazioni il consulente finanziario cerca di determinare con quali proporzioni (ottime) suddividere i 100.000 euro tra i titoli selezionati al fine di massimizzare il rendimento totale. Per determinare tali quote basta risolvere un problema di programmazione lineare.

Con \( X_{k}\) indichiamo una variabile che rappresenta (in euro) l'ammontare investito nel titolo k-esimo (con \( k \in \{A,B,C,...,O \} \)), mentre con \( LQ_{t}\) una variabile (liquidità) che rapprenta l'ammontare temporaneamente non investito nell'anno t-esimo (con \( t \in \{1,2,3,...,7\} \)). Inoltre indichiamo con \( \mathbb{I}_t\) l'insieme dei titoli la cui validità inizia nell'anno t-esimo; con \( \mathbb{F}_t\) l'insieme dei titoli la cui scadenza cade alla fine dell'anno t-esimo ed infine con \( \mathbb{A}_t\) l'insieme dei titoli "attivi" nell'anno t-esimo, ovvero quei titoli che distribuiscono utili nell'anno t-esimo in quanto tale anno è compreso tra l'anno di inizio e fine validità.

Su un titolo, quello con codice \( E\), è presente la condizione dell'acquisto con taglio minimo, ovvero il titolo può essere acquistato con taglio minimo di 1000 Euro o un suo multiplo. Questo vincolo può essere implementato sui titoli che presentano tale limitazione imponendo semplicemente che le variabili \( X_{k}\) siano intere rappresentando quindi il numero di tagli su cui investire, queste vanno poi inserite nei vincoli e nella f.o. moltiplicate per l'ammontare del taglio \( I_{k}\). Nel nostro caso quindi imporremo che la variabile \( X_{E}\) assuma valori interi positivi. Fatte queste premesse abbiamo i seguenti vincoli:

Vincolo relativo al primo anno di investimento. L'ammontare dei titoli su cui si investe nell'anno \( t = 1\), sommato alla parte di ammontare non investito (liquidità) sarà uguale alla somma messa a disposizione dal cliente (100.000 Euro):

\[ LQ_{1} + \sum_{k \in \mathbb{I}_1 } I_{k} * X_{k} = 100000 \] \[ X_{E} \in \mathbb{N} \] \[ X_{k} \ge 0 , \forall k \in \{A,B,C,...,O\}\] \[ LQ_t \ge 0 , \forall t \in \{1,2,3,...,7\}\]
Vincoli relativi agli anni successivi al primo. Al termine dell'anno \( t\) l'ammontare dei titoli che giungono a scadenza e che vengono disinvestiti, insieme alla liquidità e agli utili ricavati nel medesimo anno, possono nell'anno successivo \( t+1\) o essere reinvestiti negli strumenti finanziari che iniziano a rendersi disponibili o essere temporaneamente mantenuti come liquidità:

\[ LQ_{t+1} + \sum_{k \in \mathbb{I}_{t+1} } I_{k} * X_{k} = LQ_{t} + \sum_{k \in \mathbb{F}_t } I_{k} * X_{k} +\sum_{k \in \mathbb{A}_t } I_{k} * X_{k}*c_{kt} \,\,\,\,\,\, \forall t \in \{1,2,3,4,5,6\} \]
Vincolo relativo al livello di rischio. Il rischio deve essere in media minore di 2, per fare ciò ponderiamo gli ammontari dei titoli col relativo rischio e si impone che in media il valore sia minore rispetto al rischio desiderato (\( \le 2\)); occore però osservare che i titoli hanno spesso durate diversificate, per cui ponderiamo gli ammontari anche con la loro durata \( d_k\) per dare l'appropriato peso ai titoli che presentano durate maggiori:
\[ \sum_{k=A}^{O} I_{k}*X_{k}*d_k*r_k \le 2 * \sum_{k=A}^{O} I_{k}*X_{k}*d_k \]
Il portafoglio titoli presenta sia obbligazioni che azioni della società EMNEL. Per soddisfare il vincolo relativo alla condizione che occorre al massimo investire solo su uno dei due strumenti, introduciano le variabili binarie \( EM_1 , EM_2 \). Impostando opportunamente tali variabili è possibile costruire dei vincoli che permettono che solo su uno dei due titoli sia possibile investire:

\[ EM_1 + EM_2 \le 1 \] \[ X_I \le 100000*EM_1 \] \[ X_L \le 100000*EM_2 \] \[ EM_1,EM_2 \in \{0,1\} \]
Inoltre, occorre inserire i vincoli relativi ai punti 2) e 3), ovvero quelli che limitano l'investimento in dollari e sterline rispettivamente del 30% ed 15%:

\[ X_B + X_M \le 30000 \] \[ X_A \le 15000 \]
Per poter rappresentare dei costi fissi (nell'esempio sono stati inseriti sugli ETF) occorre introdurre una ulteriore variabile binaria per ogni titolo che presenta tali costi. Questa variabile binaria, che chiamiamo \( J_k\), rappresenta la decisione di investire o meno nel titolo k-esimo e, se si decide di investire in tale titolo, può assumere solo il valore 1; questo permette di costruire dei vincoli \( (a)\) che associano la decisione di investire nel titolo k-esimo solo se la corrispettiva variabile binaria \( J_k\) assume valore pari ad 1, in questo modo il costo fisso \( f_k\) relativo a ciascun titolo viene incorporato nella funzione obiettivo tramite la stessa variabile binaria introdotta \( (b)\):

\[ X_k \le 100000*J_k \,\,\,\,\forall k \in \{M,N,O\} \,\,\,\,\,(a)\] \[ \sum_{k=M}^{O} J_{k}*f_k \,\,\,\,\,(b)\] \[ J_{k} \in \{0,1\} \,\,\,\,\forall k \in \{M,N,O\} \]
Infine possiamo esplicitare la funzione obiettivo, che ha come finalità quella di massimizzare il rendimento totale meno i costi fissi:
\[ max : \sum_{k=A}^{O} I_{k}*X_{k}*c_k - \sum_{k=M}^{O} J_{k}*f_k \]


Sostituendo nella funzione obiettivo e nei vincoli i valori reali otteniamo il seguente problema di programmazione lineare:

\[ max : 0.261X_A+0.308X_B+0.105X_C+0.189X_D+99X_E+0.28X_F+0.03X_{G1}+0.03X_{G2}+0.03X_{G4}+ \] \[ 0.028X_{G7}+0.49X_H+0.56X_I+0.25X_L+0.90X_M+0.60X_N+0.31X_O -50J_M -50J_N -50J_O \]
vincolato a: \[ (vincoli\,\, relativi\,\, alle\,\, somme\,\, investite) \] \[ LQ_1+X_A+X_B+X_C+X_D+X_F+X_{G1}+X_H+X_I+X_M+X_N+X_O = 100000 \,\,\,(1^{\circ}\,anno)\] \[ LQ_2+X_{G2}+X_L = X_{G1}+LQ_1+0.031X_A+0.044X_B+0.035X_C+0.027X_D+0.04X_F+0.03X_{G1}+0.07X_H+0.07X_I \,\,\,(2^{\circ}\,anno)\] \[ LQ_3 = X_{G2}+LQ_2+0.036X_A+0.044X_B+0.035X_C+0.027X_D+0.04X_F+0.03X_{G2}+0.07XH+0.07X_I+0.0625X_L \,\,\,(3^{\circ}\,anno)\] \[ LQ_4+X_{G4} = LQ_3+X_C+0.041X_A+0.044X_B+0.035X_C+0.027X_D+0.04X_F+0.07X_H+0.08X_I+0.0625X_L \,\,\,(4^{\circ}\,anno)\] \[ LQ_5+1000X_E = X_{G4}+LQ_4+0.046X_A+0.044X_B+0.027X_D+0.04X_F+0.03X_{G4}+0.07X_H+0.08X_I+0.0625X_L \,\,\,(5^{\circ}\,anno)\] \[ LQ_6 = LQ_5 +X_L+0.051X_A+0.044X_B+33X_E+0.027X_D+0.04X_F+0.07X_H+0.08X_I+0.0625X_L \,\,\,(6^{\circ}\,anno)\] \[ LQ_7+X_{G7} = LQ_6+X_A+0.056X_A+0.044X_B+33X_E+0.027X_D+0.04X_F+0.07X_H+0.09X_I \,\,\,(7^{\circ}\,anno)\]
\[ X_{E} \in \mathbb{Z} \] \[ X_{k} \ge 0 , \forall k \in \{A,B,C,...,O\}\] \[ LQ_t \ge 0 , \forall t \in \{1,2,3,...,7\}\]
\[ (vincolo\,\, relativo\,\, al\,\, rischio\,\, \le 2) \] \[ 6X_A+7X_B+4.5X_C+7X_D+4500X_E+14X_F+X_{G1}+X_{G2}+X_{G4}+X_{G7}+21X_H+28X_I+6X_L+28X_M+28X_N+7X_O <= \] \[ 12X_A+14X_B+6X_C+14X_D+6000X_E+14X_F+2X_{G1}+2X_{G2}+2X_{G4}+2X_{G7}+14X_H+14X_I+8X_L+14X_M+14X_N+14X_O \]
\[ (ulteriori\,\, vincoli) \] \[ X_A \le 15000 \] \[ X_B + X_M \le 30000 \]
\[ EM_1 + EM_2 \le 1 \] \[ X_I \le 100000EM_1 \] \[ X_L \le 100000EM_2 \] \[ EM_1,EM_2 \in \{0,1\} \]
\[ X_M \le 100000J_M \] \[ X_N \le 100000J_N \] \[ X_O \le 100000J_O \] \[ J_M,J_N,J_O \in \{0,1\} \]

Risolvendo il problema SSC sotto riportato otteniamo la seguente soluzione ottima :

\[ X_A=15000, X_B=0, X_C=0, X_D=0, X_E=3, X_F=0, X_{G1}=0, X_{G2}=0, X_{G4}=2086,\] \[ X_{G7}=18861, X_H=5871, X_I=0, X_L=876, X_M=30000, X_N=0, X_O=49129 \]
Per un rendimento complessivo di 50028 Euro.


import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Portafoglio {
     
    public static void main(String[] args) throws Exception {
         
        String pl_problem=
         
        "max : 0.261XA +0.308XB +0.105XC +0.189XD +99XE+0.28XF +0.49XH +0.56XI +0.25XL +0.90XM +0.50XN +0.31XO +"+
              "0.03XG1 +0.03XG2  +0.03XG4 + 0.028XG7 -50JM -50JN -50JO  \n"+
 
        "LQ1+ XA + XB + XC +XD + XF  +XG1 + XH + XI + XM +XN +XO = 100000 \n"+
 
        "XG2 + XL +LQ2 = XG1+LQ1     +0.031XA +0.044XB +0.035XC +0.027XD +0.04XF +0.03XG1 +0.07XH +0.07XI           \n"+
        "         +LQ3 = XG2+LQ2     +0.036XA +0.044XB +0.035XC +0.027XD +0.04XF +0.03XG2 +0.07XH +0.07XI +0.0625XL \n"+
        "XG4      +LQ4 =     LQ3+XC  +0.041XA +0.044XB +0.035XC +0.027XD +0.04XF          +0.07XH +0.08XI +0.0625XL \n"+
        "1000XE   +LQ5 = XG4+LQ4     +0.046XA +0.044XB          +0.027XD +0.04XF +0.03XG4 +0.07XH +0.08XI +0.0625XL \n"+
        "         +LQ6 =     LQ5+XL  +0.051XA +0.044XB +33XE    +0.027XD +0.04XF          +0.07XH +0.08XI +0.0625XL \n"+
        "XG7      +LQ7 =     LQ6+XA  +0.056XA +0.044XB +33XE    +0.027XD +0.04XF          +0.07XH +0.09XI           \n"+
 
        " 6XA + 7XB + 4.5XC + 7XD + 4500XE +14XF  +XG1  +XG2  +XG4 +XG7 + 21XH+ 28XI +6XL +28XM +28XN  +7XO <=        "+
        "12XA +14XB +   6XC +14XD + 6000XE +14XF +2XG1 +2XG2 +2XG4+2XG7 + 14XH+ 14XI +8XL +14XM +14XN +14XO         \n"+
 
        "XB + XM  <= 30000  \n"+
        "XA <=15000         \n"+
 
        "EM1 + EM2 <=1      \n"+
        "XI <= 100000EM1    \n"+
        "XL <= 100000EM2    \n"+
             
        "XO <=100000JO      \n"+
        "XM <=100000JM      \n"+
        "XN <=100000JN      \n"+
			
        "int XE             \n"+
        "bin EM1, EM2, JM, JN, JO";
        
        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);
    }
}


				

Back to index

Un problema di trasporto e smaltimento rifiuti


Una multinazionale chimica è dotata in una specifica regione di due siti produttivi (\( P_1,P_2 => P_i\)) da cui deve regolarmente conferire una variegata quantità di rifiuti industriali speciali. Nella regione sono presenti tre discariche (\(D_1,D_2,D_3 => D_j\)) capaci di accogliere tali rifiuti. L'obiettivo primario consiste nell'ottimizzare, sulla base delle quantità giornaliere da smaltire e della capacità giornaliera di conferimento delle discariche, i costi di trasporto e di smaltimento. E' altresì essenziale ridurre al minimo la quantità di rifiuti non conferiti, poichè il mancato smaltimento comporta ulteriori oneri gestionali.


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 :

Automezzi tipo \( A_1\) Automezzi tipo \( A_2\)
Km percorribili al giorno (\(km_k\)) 500 450
Portata in Tonnellate (\(q_k\)) 14 5
Costo trasporto al km in Euro (\(ct_k\)) 7,5 3



Le distanze (\(d_{ij}\)) in km tra i siti produttivi e quelli di smaltimento sono le seguenti :

Discarica \( D_1\) Discarica \( D_2\) Discarica \( D_3\)
Sito produttivo \( P_1\) 30 40 50
Sito produttivo \( P_2\) 60 55 40



Nella data presa in esame, le tre discariche forniscono all'azienda chimica le seguenti disponibilità di rifiuti da trattare, accompagnate dai relativi costi di smaltimento (\(cs_1,cs_2,cs_3 => cs_j\)) per tonnellata:

Discarica \(D_1\) Discarica \(D_2\) Discarica \(D_3\)
Quantità smaltibile in tonnellate 147 115 95
Costo di smaltimento in Euro per tonnellata (\(cs_j\)) 200 220 185



Nella data presa in esame i due siti produttivi presentano le seguenti quantita di rifiuti da smaltire :

Sito produttivo\( P_1\) Sito produttivo\( P_2\)
Quantita in tonnellate da smaltire 185 210


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:

Caratteristica Km automezzi tipo \( A_1\) Km automezzi tipo \( A_2\)
Sito produttivo\( P_1\) 500 \( 450 * 2\)
Sito produttivo\( P_2\) \( 500 * 2\) 450


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: 3250X_{111} + 3680X_{112}+ 3340X_{113} + 3700X_{121} + 3905X_{122}+ 3190X_{123} +\] \[ 1180X_{211} + 1340X_{212}+ 1225X_{213} + 1360X_{221} + 1430X_{222}+ 1165X_{223} +100000Y_1 + 100000Y_2 \]
\[ 60X_{111} +80X_{112}+ 100X_{113} \leq 500 \] \[ 60X_{211} +80X_{212}+ 100X_{213} \leq 900 \] \[ 120X_{121} +110X_{122}+ 80X_{123} \leq 1000 \] \[ 120X_{221} +110X_{222}+ 80X_{223} \leq 450 \] \[ 14X_{111} + 14X_{121} + 5X_{211} + 5X_{221} \leq 147 \] \[ 14X_{112} + 14X_{122} + 5X_{212} + 5X_{222} \leq 115 \] \[ 14X_{113} + 14X_{123} + 5X_{213} + 5X_{223} \leq 95 \] \[ 14X_{111} + 14X_{112}+ 14X_{113} + 5X_{211} + 5X_{212}+ 5X_{213} +Y_1 = 185 \] \[ 14X_{121} + 14X_{122}+ 14X_{123} + 5X_{221} + 5X_{222}+ 5X_{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.



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);
	}
}

				

Back to index

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:

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: 20Q_a + 32Q_b -15q_{1a} -15q_{1b} -9q_{2a} -9q_{2b} -2q_{3a} -2q_{3b}\]
\[ Q_a \geq 6000 \] \[ 0.18Q_a \leq q_{1a} \] \[ 0.20Q_a \leq q_{2a} \] \[ 0.62Q_a \leq q_{3a} \] \[ 0.25Q_b \leq q_{1b}\] \[ 0.26Q_b \leq q_{2b} \] \[ 0.49Q_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.0X_{11} +13X_{21}+18X_{31} +10X_{41} \] \[ q_{2a} + q_{2b} = 14X_{12} +10X_{22}+4.0X_{32} +16X_{42} \] \[ q_{3a} + q_{3b} = 5.0X_{13} +6X_{23}+9.0X_{33} +18X_{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);
    }
}
				

Back to index

Un problema di assegnazione ispettori-ispezioni


Una multinazionale aerospaziale è dotata di otto siti produttivi che richiedono ispezioni regolari da parte di due gruppi di ispettori. Gli ispettori risiedono in città diverse rispetto a quelle in cui sono ubicati i siti produttivi e pertanto 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 i due gruppi di 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 ulteriori due località portando, sulla rete di trasporto, il totale delle località 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 una variante del "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:


Vincoli dovuti al fatto che il gruppo di ispettori \( A\) deve partire dalla città \( 1\) nel primo tratto \( t=1\) e deve 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\) deve partire dalla città \( 5\) nel primo tratto \( t=1\) e deve 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{ , } \, 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);
	}
}

				

Back to index