Il costo complessivo di espansione della produzione sia minimo (4)Pianificazione della produzione di energia Variabili decisionali

(1)

Esercizi di formulazione

• Pianificazione della produzione di energia

• Formazione delle classi nelle scuole

• Aste combinatorie

• Assegnamento di frequenze

• Problema di miscelazione

(2)

Pianificazione della produzione di energia

periodi di pianificazione

• fabbisogno stimato di energia nel periodo pari a

• produzione disponibile (che non può essere dismessa) dagli impianti a petrolio pari a

• esistono due opzioni per aumentare la produzione:

- impianti a carbone:

- costo per megawatt e - durata 20 anni

- impianti nucleari:

- costo per megawatt e - durata 15 anni

(3)

• per ragioni di sicurezza la capacità degli impianti nucleari non deve superare, in ogni periodo, il 20% della capacità totale.

Preparare un Piano di Produzione dell’energia equivale a decidere la capacità produttiva degli impianti a carbone e di quelli nucleari in ogni peridodo ∈ .

Problema:

Determinare un piano di produzione in modo che:

1. La domanda di energia sia soddisfatta in ogni periodo ∈

2. Siano rispettati I vincoli sulla durata degli impianti e di sicurezza

3. Il costo complessivo di espansione della produzione sia minimo

(4)

Variabili decisionali:

= quantità di capacità da carbone installata all’inizio del periodo

= quantità di capacità da nucleare installata all’inizio del periodo

= quantità di capacità da carbone disponibile nel periodo t

= quantità di capacità da nucleare disponibile nel periodo t

(5)

−

= =

= _max{₁_, ₁₉_} , 1,...,

t

s s

t x t T

w

−

= =

= _max{₁_, ₁₄_} , 1,...,

t

s s

t y t T

z

Capacità da carbone disponibile nel periodo

Capacità da nucleare disponibile nel periodo

Capacità nucleare non superiore al 20% della capacità totale T

e t z

w

z

t t

t

t ≤ 0.2, =1,..., +

+

(6)

Copertura della domanda nel periodo

T t

d e

z

w_t + _t + _t ≥ _t, = 1,...,

Funzione obiettivo

) (

1

t t n

j

t

t x n y c

=

+

min

(7)

) (

1

t t n

t

tx n y

c

=

+

min

−

= = =

− _s _max{₁_,_t ₁₉_} _s 0, 1,...,

t x t T

w

−

= = =

− _s _max{₁_,_t ₁₄_} _s 0, 1,...,

t y t T

z

T t

e w

z_t 0.2 _t 0.2 _t, 1,..., 8

.

0 − ≤ =

T t

z w x

y_t, _t , _t , _t ≥ 0, =1,...,

T t

d e

z

w_t + _t + _t ≥ _t, = 1,...,

s.t.

(8)

Formazione delle classi nelle scuole

quartieri, scuole, classi per ogni scuola

• la scuola ha capacità per la classe

• nel quartiere ci sono studenti della classe

• la distanza della scuola dal quartiere è

Problema: formare le classi in modo da minimizzare la distanza complessiva percorsa dagli studenti

Variabili decisionali:

= numero di studenti del distretto assegnati alla classe della scuola

(9)

Vincoli di capacità:

g j C

x

I

i

jg

ijg , ,

1

∀

≤

=

Ogni studente deve essere assegnato ad una classe:

g i S

x

J

j

ig

ijg , ,

1

∀

=

Distanza complessiva percorsa:

= = =

I

i

G

g

ijg J

j

ij x

d

1 1 1

(10)

g j C

x

I

i

jg

ijg , ,

1

∀

≤

=

g i S

x

J

j

ig

ijg , ,

1

∀

=

= = =

I

i

G

g

ijg J

j

ij x

d

1 1 1

min

g j i

x_ijg ≥ 0 ∀ , ,

(11)

Aste combinatorie

S₁

S₂ S₃

S₄ S₅

2 − S₄ −

3

− 2

− o₂

4 − S₅

− 4 S₃

1 − S₂

4 5

S₁

o₃ o₁

• Insieme di offerenti

• insieme di oggetti

• Ogni giocatore fa un’offerta per ciascun sottoinsieme di a cui è interessato.

(12)

Aste combinatorie

Vincoli:

• gli insiemi venduti devono essere disgiunti (oggetti in copia unica)

• ogni offerente ha diritto ad acquistare al più un insieme di oggetti

Obiettivo del venditore è massimizzare il guadagno

S₁

S₂ S₃

S₄ S₅

2 − S₄ −

3

− 2

− o₂

4 − S₅

− 4 S₃

1 − S₂

4 5

S₁

o₃ o₁

guadagno ottimo = 7

(13)

Aste combinatorie

Grafo:

• un nodo per ogni coppia offerente-offerta

• un arco fra una coppia di nodi se:

hanno in comune l’offerente

2 − S₄ −

3

− 2

− o₂

4 − S₅

− 4 S₃

1 − S₂

4 5

S₁

o₃

o₁ S₁, O₁

S₂, O₁

S₂, O₂

S₃, O₃ S₁, O₃

S₅, O₁ S₄, O₂

S₅, O₂

(14)

Aste combinatorie

Grafo = ( , ):

• un nodo per ogni coppia offerente-offerta

• un arco fra una coppia di nodi se:

le offerte non sono disgiunte

S₁, O₁

S₂, O₁

S₂, O₂

S₃, O₃ S₁, O₃

S₅, O₁ S₄, O₂

S₅, O₂ S₁

S₂ S₃

S₄ S₅

(15)

Aste combinatorie

S₁, O₁

S₂, O₁

S₂, O₂

S₃, O₃ S₁, O₃

S₅, O₁ S₄, O₂

S₅, O₂

massimizzare il guadagno equivale a calcolare l’insieme stabile (nodi a coppie non adiacenti) di peso massimo

1

4

2 5

4

4 3 2

peso su ciascun nodo pari al valore dell’offerta

(16)

Formulazione

Variabile binaria:

= 1 se è preso nell’insieme stabile;

= 0 altrimenti

= V

j

j jx w

|

1

max

≤ 1 + j

i x

x _∀ _∈

n j

x_j ∈{0,1}, = 1, ,

(17)

Assegnamento di frequenze

• Insieme di trasmettitori

• Spettro suddiviso in canali (frequenze)

• Due trasmettitori “vicini” a cui è assegnata la stessa frequenza possono generare interferenza

• Problema: determinare il minimo numero di frequenze tale che l’interferenza totale sia nulla

(18)

Grafo d’interferenza

• G = (V, E)

• un nodo per ciascun trasmettitore

• un arco fra trasmettitori potenzialmente interferenti

• Si definisce colorazione, l’assegnamento di un colore a ciascun nodo in modo che gli estremi di arco non ricevano mai lo stesso colore

• Determinare il minimo numero di frequenze tale che l’interferenza totale sia nulla equivale a calcolare una colorazione con il numero minimo di colori

a

e b

d c

a

e b

d c

(19)

Formulazione I

Variabili decisionali

= 1 se al vertice è assegnato il colore = 0 altrimenti

= 1, se il colore è attivato; = 0 altrimenti

k jk

ik x y

x + ≤ ∈

} 1 , 0

∈{ xik

=

|

1

min

V

k

yk

, 1

|

1

=

= V

k

xik _∈

∈

}, 1 , 0

∈{ yk

(20)

Formulazione II

Variabili decisionali

= 1 se l’insieme stabile s è “attivato”; = 0 altrimenti

, 1

: ∈

≥

S i s

xs _∈

} 1 , 0

∈{ xs

a

e b

d c

a

e b

d c

• Una colorazione equivale ad una partizione dei vertici in insiemi stabili

• sia S la collezione di tutti gli insiemi stabili

=

|

1

min

S

s

xs

∈

(21)

Problema di miscelazione

Un’azienda casearia desidera produrre un nuovo latte LAQ di alta qualità, espressa in termini di requisiti nutrizionali:

almeno 45 g/litro Calcio

almeno 45 g/litro Grassi

almeno 36 g/litro Carboidrati

almeno 32 g/litro Proteine

LAQ è prodotto miscelando tre diversi tipi di latte L1, L2, L3, con le seguenti caratteristiche nutrizionali (g/litro)

L3 L2

L1

1.5 38 40 35

1.2 35 48 31

1.4 Calcio

32 Grassi

50 Carboidrati

32 Proteine

(22)

Problema di miscelazione

Sapendo che i costi di produzione dei tre tipi di latte sono:

L3 L2

L1

0.6 €/litro

0.5 €/litro 0.4 €/litro

Formulare il problema di PL che minimizzi il costo di produzione di LAQ