Appunti Teoria ed esercizi - Laboratorio di Ricerca operativa

OPL

Formulazione Problema in FS:

Modello della dieta a costo minimo: 89

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

90

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

91

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esercitazione 1

//variabili decisionali

int numVariabili =...;

int numVincoli =...;

range Variabili = 1..numVariabili;

range Vincoli = 1..numVincoli;

int C[Variabili] =...;

int B[Vincoli] = ...;

int A[Vincoli][Variabili] = ...;

dvar float+ X[Variabili];

minimize sum(i in Variabili)C[i]*X[i]; //f obiettivo

subject to{

forall(i in Vincoli)

sum(j in Variabili) A[i][j]*X[j] == B[i];

};

File .dat

numVariabili= 6;

numVincoli= 3;

C=[1, 2, 1, 1, 1, 1];

B=[3, 2, 2];

A=[[1 , 2, 3, 1, 0, 0],

[2, -1, -1, 0, 1, 0],

[1,2, -1, 0, 0, 1]]; 92

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esercitazione 2

int Nmesi=...;

int QN=...;

int QE=...;

int QC=...;

int CN=...;

int CE=...;

float CS=...;

range mesi=1..Nmesi;

float D[mesi]=...;

float S0=...;

dvar float+ X[mesi];

dvar float+ Y[mesi];

dvar float+ Z[mesi];

minimize sum(i in mesi)(CN*X[i] +CE*Y[i]+CS*Z[i]);

subject to{

forall(i in mesi)

produzioneN: X[i]<=QN;

forall(i in mesi)

produzioneE: Y[i]<=QE;

forall(i in mesi)

statoC: Z[i]<=QC;

Z[5]==0;

mese1: X[1]+Y[1]+S0==D[1]+Z[1];

forall(i in mesi: i>=2)

mese_i: X[i]+Y[i]+Z[i-1]==D[i]+Z[i];

}

File .dat

Nmesi= 5;

QN=100;

QE=25;

QC=20;

CN=18;

CE=22;

CS=0.3;

D=[120,110,90,40,130];

S0=10; 93

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esercitazione 4

int nOggetti=...;

int nScatole=...;

range oggetti = 1..nOggetti;

range scatole = 1..nScatole;

int w[oggetti] = ...;

int B =...;

dvar int x[oggetti][scatole] in 0..1;

dvar int y[scatole] in 0..1;

//minimize sum (i in scatole) y[i];

//subject to{

//forall(i in scatole)

//oggetto_j: sum(j in oggetti)x[i][j];

//}

File .dat

Nmesi= 5;

QN=100;

QE=25;

QC=20;

CN= 18;

CE= 22;

CS= 0.3;

D= [120,110,90,40,130];

S0= 10; 94

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esercitazione 5

int numN=...;

int numM = ...;

range rangeN = 1..numN;

range rangeM = 1..numM;

int costi[rangeM]=...;

int A[rangeN][rangeM] =...;

dvar int x[rangeM] in 0..1;

minimize sum(j in rangeM)costi[j]*x[j];

subject to{

forall(i in rangeN)

somma_i:sum(j in rangeM)A[i][j]*x[j]>=1;

}

File .dat

numN=8;

numM=9;

costi =

[47,27,45,20,40,45,60,60,22];

A =[[1,0,0,0,1,1,0,1,0],

[1,0,0,1,0,1,1,1,0],

[0,1,1,1,1,0,1,0,0],

[0,0,0,0,0,0,0,0,1],

[0,0,0,0,1,1,0,1,0],

[1,1,0,0,0,0,0,1,0],

[0,1,0,0,1,0,1,0,1],

[1,0,1,0,1,1,0,0,0]]; 95

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Modello dieta

int nAlimenti =...;

int nNutrienti = ...;

range Alimenti = 1..nAlimenti;

range Nutrienti = 1..nNutrienti;

float C[Alimenti] = ...;

int U[Nutrienti] = ...;

int L[Nutrienti] = ...;

float A[Nutrienti][Alimenti] = ...;

dvar float+ X[Alimenti];

minimize sum(i in Alimenti)C[i]*X[i];

subject to{

forall(i in Nutrienti)

sum(j in Alimenti)A[i][j] *X[i]<= U[i];

forall(i in Nutrienti)

sum(j in Alimenti)A[i][j] * X[i]>= L[i];

};

File .dat

nAlimenti = 7;

nNutrienti = 3;

C=[4,4,15,22.5,3,1,15];

U=[35,25,20];

L=[25,15,10];

A=[[11.5, 3.15, 8, 18.5, 2.1, 12, 74],

[72.7, 4.85, 3.8, 0.5, 0, 68, 1],

[1.5, 1.55, 11, 19, 0.1, 6, 9]];

96

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Modello PCentro

int m = ...;

int n = ...;

range clienti = 1..m;

range impianti = 1..n;

int c[clienti][impianti] = ...;

int p = ...;

dvar int x [clienti][impianti] in 0..1;

dvar int y[impianti] in 0..1;

dvar float+ cmax;

minimize cmax;

subject to {

forall(i in clienti)

sum(j in impianti )x[i][j]==1;

forall(i in clienti,j in impianti){

x[i][j]<= y[i];

cmax >= x[i][j] * c[i][j];

}

sum(j in impianti)

y[j] == p;

}

File .dat

m = 5;

n = 6;

c= [[12,8,2,3,8],

[8,4,6,5,7],

[2,6,5,6,5],

[3,5,6,9,10],

[8,4,5,10,8],

[7,3,3,4,4]];

p = 2; 97

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Assegnamento

//task sono origini e cpu sono destinazioni

int origini = ...;

range nOrigine = 1..origini;

int destinazioni = ...;

range nDestinazione = 1..destinazioni;

int costiAss[nOrigine][nDestinazione] = ...; //tempi di calcolo

dvar int+ F[nOrigine][nDestinazione] in 0..1;

minimize sum(i in nOrigine, j in nDestinazione)

costiAss[i][j] * F[i][j];

subject to{

forall(i in nOrigine)

sum(j in nDestinazione) F[i][j] == 1;

forall(j in nDestinazione)

sum(i in nOrigine) F[i][j] == 1;

};

File .dat

origini = 5;

destinazioni = 5;

costiAss=[[7,2,1,9,4],

[9,6,9,5,5],

[3,8,3,1,8],

[7,9,4,2,2],

[8,4,7,4,8]]; 98

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Flusso di Costo Minimo

int nNodi = ...;

range nodi = 1..nNodi;

tuple archi{

int nodoP;

int nodoA;

}

{archi} Archi =...;

int C[Archi] =...;

int D[nodi]= ...;

dvar int+ X[Archi];

minimize sum (<i,j> in Archi) C[<i,j>]*X[<i,j>];

subject to{

forall(i in nodi)

sum(<i,j> in Archi) X[<i,j>] -

sum (<j,i> in Archi) X[<j,i>] == D[i];

}

// Rispettare equazioni di continuità su tutti i nodi =>

divergenza sul nodo i = somma archi entranti su i - somma archi uscenti su i

File .dat

nNodi = 7;

Archi = {<1,3>,<1,6>,<2,1>,<3,5>,<3,6>,<4,1>,

<4,5>,<5,7>,<6,2>,<6,7>,<7,2>};

C = [2,9,4,2,3,1,1,4,4,7,2];

D = [10,-8,0,6,0,0,-8]; 99

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Flusso di Costo Minimo - Versione 2

tuple arco{

int NodoOut;

int NodoIn;

int costo;

}

{arco} Archi= ...;

tuple nodo{

int IndiceNodo;

int divergenza;

}

{nodo} Nodi= ...;

dvar float+ F[Archi];

minimize sum(<i,j,k> in Archi)F[<i,j,k>]*k;

subject to{

forall(<i,d>in Nodi)

sum(<i,j,k> in Archi)F[<i,j,k>] -

sum(<j,i,k> in Archi) F[<j,i,k>] == d;

};

// Rispettare equazioni di continuità su tutti i nodi =>

divergenza sul nodo i = somma archi entranti su i - somma archi uscenti su i

File .dat

Archi = {<1,3,2>,<1,6,9>,<2,1,4>,<3,5,2>,<3,6,3>,

<4,1,1>,<4,5,1>,<5,7,4>,<6,2,4>,<6,7,7>,<7,2,2>};

Nodi = {<1,10>,<2,-8>,<3,0>,<4,6>,<5,0>,<6,0>,<7,-8>};

100

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Trasporto

int pVendita =...;

range nPVendita = 1..pVendita;

int impianti = ...;

range nImpianti = 1..impianti;

int cImpianti[nImpianti] = ...;

int rPVendita[nPVendita] = ...;

int costiTrasp[nImpianti][nPVendita] = ...;

dvar float+ F[nImpianti][nPVendita];

// siccome ciò che distribuisco > di ciò che richiedo,

// avrò bisogno di un impianto fittizio, con costo di trasporto = 0

// 30-27 = 3 = rImpianto fittizio

minimize sum(i in nImpianti, j in nPVendita)

costiTrasp[i][j] * F[i][j];

subject to{

forall(i in nImpianti)

sum(j in nPVendita)F[i][j] == cImpianti[i];

forall(j in nPVendita)

sum(i in nImpianti) F[i][j] == rPVendita[j];

};

File .dat

pVendita = 4;

impianti = 3;

cImpianti = [12,8,10];

rPVendita = [8,10,9,3];

costiTrasp =[[2,5,2,0],[3,4,6,0],[1,5,3,0]];

101

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Bin Packing

int m = ...;

int n = ...;

range M = 1..m;

range N = 1..n;

int B = ...;

int w[N] = ...;

dvar int X[M][N] in 0..1;

dvar int Y[M] in 0..1;

minimize sum (i in M) Y[i];

subject to{

forall(j in N)

sum(i in M) X[i][j] == 1;

forall(i in M)

sum(j in N) w[j] * X[i][j] <= B*Y[i];

};

File .dat

m=10;

n=50;

B=650;

w=[92,91,90,89,85,84,81,80,80,78,78,77,77,76,75,74,73,69,69,68,68,

67,67,65,64,63,63,61,60,56,54,54,51,49,45,43,42,39,39,39,38,36,35,

34,34,33,32,31,30,50]; 102

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Bin Packing Generalizzato

int m = ...;

int n = ...;

range M = 1..m;

range N = 1..n;

int b[M] = ...;

int v[M][N] = ...;

int w[M][N] = ...;

dvar int X[M][N] in 0..1;

maximize sum( i in M , j in N) v[i][j] * X[i][j];

subject to {

forall(j in N)

sum(i in M)X[i][j] == 1;

forall(i in M)

sum(j in N) w[i][j] * X[i][j] <= b[i];

};

File .dat

m = 5;

n = 10;

v = [[110,65,19,89,62,37,89,78,74,88],

[16,69,93,31,17,115,102,96,27,97],

[25,54,45,72,77,87,98,87,99,99],

[78,28,45,83,18,59,74,55,91,99],

[59,71,9,20,39,97,61,77,5,51]];

w =[[95,54,3,72,44,20,72,75,68,69],

[1,53,91,30,1,99,96,82,8,83],

[21,44,43,56,71,87,97,83,87,98],

[66,26,42,72,13,52,73,44,74,88],

[59,60,5,9,27,85,49,59,4,45]];

b =[91,87,109,88,64]; 103

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Surgelati

int trimestre=...; //un numero intero multiplo di 4 = 1 anno

range Trimestri = 1..trimestre;

int PrezzoAcquisto[Trimestri]=...;

int Domanda[Trimestri]=...;

int PrezzoVendita=...; // €/Quintale

int PrezzoTrasfSurg=...; // €/Quintale

int CostoMag=...; // €/(Quintale*Mese)

int CapProd=...;// Quintali/Mese

int CapMag=...; //Quintali

dvar float+ X[Trimestri];//quantità di bastoncini prodotti al trimestre

dvar float+ Z[Trimestri];//quantità di bastoncini immagazzinati al trimestre

minimize PrezzoVendita*sum(i in Trimestri)X[i]- //Ricavi

PrezzoTrasfSurg*sum(i in Trimestri)X[i]- //Costi di produzione

3*CostoMag*sum(i in Trimestri)Z[i] - //Costi di magazzino

sum(i in Trimestri)PrezzoAcquisto[i]*X[i];

//Costi di acquisto del pesce

subject to{

forall(i in Trimestri){

X[i]<=3*CapProd; //vincoli sulla capacità produttiva

Z[i]<=CapMag; //vincoli sulla capacità del magazzino;

}

X[1] == Domanda[1] + Z[1]; //equazione di bilancio al primo trimestre

forall(i in Trimestri : i>=2){ //equazioni di bilancio ai trimestri successivi

X[i]+Z[i-1] == Domanda[i]+Z[i];}

/************************************************

*Aggiungere questi vincoli per considerare *

*la deperibilità della merce ogni tre trimestri