(9) Esercizi di Programmazione Lineare Intera

Esercizi di Programmazione Lineare Intera
a cura di A. Agnetis
1
Risolvere il seguente problema di PLI con l’algoritmo dei piani di Gomory:
max z = 40x1 + 24x2 + 15x3 + 8x4
8x1 + 6x2 + 5x3 + 4x4
≤
22
xi
≥
0
xi intero
Soluzione.
Si tratta di un problema di knapsack intero, che potrebbe dunque anche risolversi ad
esempio con la programmazione dinamica, o con un branch and bound specializzato.
Tuttavia utilizziamo i piani di Gomory.
Portando il problema in forma canonica:
0 -40 -24 -15 -8 0
22 8
6
5
4 1
l’elemento di pivot è chiaramente 8, da cui il tableau ottimo
110 0
22
1
8
6
3
4
10 12
5
8
1
2
5
1
8
La soluzione ottima è frazionaria. Dunque, aggiungendo il taglio si ha:
110 0
22
1
8
3
-4 0
6
10 12
5
3
4
- 34
5
8
- 58
1
8
- 18
1
2
- 12
0
0
1
applicando una iterazione del metodo duale del simplesso, si ha che l’elemento pivot è
-3/4, si ottiene il nuovo tableau ottimo:
1
104 0
2 1
1 0
0
0
1
5
0
8
0
4
0
8
1
5
6
2
3
1
6
4
3
e quindi la soluzione ottima (2, 1, 0, 0).
2
Risolvere il seguente problema di PLI con l’algoritmo dei piani di Gomory, indicando le
equazioni del taglio in funzione delle variabili originarie:
max z = x1 + 2x2
x1 − 2x2
≥
−2
x1 + x2
≤
3
x1 , x2
≥
0
x1 , x2 interi
Soluzione.
Portando il problema in forma canonica si ha
0 -1
2 -1
3 1
-2 0 0
2 1 0
1 0 1
ove
x3 = 2 + x1 − 2x2
x4 = 3 − x1 − x2
Dopo due iterazioni del metodo del simplesso si arriva al tableau ottimo:
14
3
5
3
4
3
0
0
1
0
1
0
1
3
1
3
- 13
4
3
1
3
2
3
La soluzione è frazionaria, occorre quindi generare un taglio. Scegliendo la prima riga, si
ha:
1
2
1
− x3 − x4 ≤ −
3
3
3
2
e dunque il nuovo tableau:
14
3
5
3
4
3
- 23
0
0
1
0
0
1
0
0
1
3
1
3
- 13
- 13
4
3
1
3
2
3
- 13
0
0
0
1
effettuando l’operazione di pivot attorno all’elemento sulla riga 3 e in colonna 3, si ottiene
il nuovo tableau ottimo
4
1
2
2
0
0
1
0
0
1
0
0
0
0
0
1
1 1
0 1
1 -1
1 -3
e dunque la soluzione ottima del problema originario è (2, 1). Per ottenere l’espressione
del taglio, osserviamo che questo può scriversi
x3 + x4 ≥ 2
da cui, sfruttando le espressioni di x3 e x4 sopra riportate, si ha in definitiva che il taglio
è
x2 ≤ 1
3
Un insieme di 7 lavorazioni deve essere eseguito da una macchina a controllo numerico.
Ciascuna lavorazione richiede alcuni utensili, e, una volta effettuata, porta un certo profitto. La seguente tabella mostra, per ogni lavorazione, l’insieme di utensili richiesto e il
corrispondente profitto:
lavorazione
Utensili
profitto
1
A, C, D, E
2000
2
A, B, F, G
1500
3
A, B, C, E
1800
4
B, D, E, G
1700
5
E, F, G
800
6
A, D, G
900
7
A, E, F
750
Il magazzino utensili della macchina può ospitare solo al più 5 utensili. Formulare come
PLI il problema di determinare la configurazione del magazzino utensili con l’obiettivo di
massimizzare il profitto.
3
Soluzione.
Si tratta di decidere quali utensili dovranno essere montati sulla macchina, e di conseguenza quali lavorazioni potranno essere effettuate. Risulta allora conveniente introdurre le seguenti variabili di decisione:
{
xi =
{
yj =
1 se la lavorazione i è effettuata
0 altrimenti
1 se l’utensile j è montato
0 altrimenti
La funzione obiettivo risulta dunque essere
min 2000x1 + 1500x2 + 1800x3 + 1700x4 + 800x5 + 900x6 + 750x7
Vediamo ora i vincoli. Un primo tipo di vincoli consiste nell’esprimere il fatto che una
lavorazione può essere eseguita solo se tutti i corrispondenti utensili sono montati sulla
macchina. Questo può essere espresso dicendo che una lavorazione i non può effettuarsi
se l’utensile j richiesto non è montato. Nel nostro esempio, otteniamo 25 vincoli:
x 1 ≤ yA
x 1 ≤ yC
x 1 ≤ yD
x 1 ≤ yE
x 2 ≤ yA
x 2 ≤ yB
x 2 ≤ yF
x 2 ≤ yG
...
...
In alternativa, si poteva più compattamente scrivere
x1 + x2 + x3 + x6 + x7 ≤ 5yA
x2 + x3 + x4 ≤ 3yB
x1 + x3 ≤ 2yC
...
...
4
dove, si noti, se yj = 0 tutte le variabili corrispondenti a lvaorazioni che richiedono
l’utensile j sono contemporaneamente poste a 0. (Questa seconda formulazione è però
molto più debole, dal punto di vista risolutivo, della prima).
Un secondo tipo di vincoli è relativo alla capacità limitata di immagazzinamento della
macchina, che può esprimersi semplicemente come
yA + yB + yC + yD + yE + yF + yG ≤ 5
4
In una rete di calcolatori, vi sono n terminali ciascuno dei quali deve essere collegato ad un
concentratore. Ci sono m concentratori, a ognuno dei quali possono essere collegati al più
k terminali. Perché un terminale possa essere collegato a un concentratore, quest’ultimo
deve essere ”attivo”. Il costo di attivazione di un concentratore j è fj , mentre il costo di
collegamento del terminale i con il concentratore j è cij . Formulare come PLI il problema
di minimizzare i costi complessivi, nel rispetto dei vincoli.
Soluzione.
Si tratta di un problema di plant location. Le variabili di decisione saranno
{
1 se il terminale i è collegato al concentratore j
0 altrimenti
xij =
{
yj =
1 se il concentratore j è attivato
0 altrimenti
La funzione obiettivo risulta dunque dalla somma dei due tipi di costi:
min
n
∑
cij xij +
i=1
m
∑
fj y j
j=1
Per quanto riguarda i vincoli, oltre ai consueti vincoli di assegnamento (ciascun terminale
deve essere connesso a uno e un solo concentratore)
m
∑
xij = 1 i = 1, . . . , n
j=1
avremo i vincoli per cui un terminale i non può essere collegato al concentratore j se
quest’ultimo non è attivato, ossia
xij ≤ yj
i = 1, . . . , n,
j = 1, . . . , m
Infine, i vincoli sulla capacità di ciascun concentratore:
n
∑
xij ≤ k j = 1, . . . , m
i=1
5
5
Ci sono n lavori indivisibili da effettuare, ognuno caratterizzato da una sua durata pi ,
i = 1, . . . , n. Avendo due persone a disposizione, volete ripartire i lavori tra queste due
persone facendo in modo che i loro carichi di lavoro siano il più possibile bilanciati.
Formulare il problema in termini di problema di knapsack, e risolverlo con un opportuno algoritmo nel caso n = 4, p1 = 2, p2 = 3, p3 = 6, p4 = 7.
Soluzione.
Poiché la somma dei pi è pari a 18, si tratta di risolvere il problema
max z = 2x1 + 3x2 + 6x3 + 7x4
2x1 + 3x2 + 6x3 + 7x4 ≤ 9
xi ∈ {0, 1}
dove le variabili pari a 1 e a 0 indicheranno la partizione dei lavori tra le due persone.
Applicando l’algoritmo di programmazione dinamica si ottiene
↓k→y
0
1
2
3
4
0
0
0
0
0
0
1
0
0
0
0
0
2
0
2
2
2
2
3
0
2
3
3
3
4
0
2
3
3
3
5
0
2
5
5
5
6
0
2
5
6
6
7
0
2
5
6
7
8
0
2
5
8
8
9
0
2
5
9
9
Dalla tabella si ricostruisce una soluzione ottima, x1 = 1, x2 = 0, x3 = 0, x4 = 1.
6
In figura è rappresentata una rete stradale che unisce varie località. A ogni tratto di
strada sono associati due numeri. Il primo rappresenta il tempo necessario a percorrerlo,
il secondo il pedaggio che è necessario pagare. Si vuole andare da A a B nel minor tempo
possibile, ma si hanno in tasca solo 44 euro per pagare i pedaggi. Formulare in termini di
programmazione lineare a numeri interi il problema di trovare il percorso più conveniente.
Soluzione.
La formulazione si ottiene aggiungendo alla classica formulazione di cammino minimo
un vincolo di knapsack. Chiaramente, l’aggiunta di questo vincolo distrugge la totale
unimodularità della matrice dei coefficienti, per cui il problema non è più risolvibile in
termini di programmazione lineare.
6
1
2.5, 13
2
4, 14
3, 16
2, 11
2, 30
A
B
2, 8
1, 6
6, 23
4, 20
3
1.5, 25
4
Figura 1: Rete stradale.
min z = 3xA1 + 4xA3 + 2x13 + 2.5x12 +
x23 + 1.5x34 + 2x41 + 2x42 + 4x2B + 6x4B
xA1 + xA2 = 1
xA1 + x41 = x13 + x12
x12 + x42 = x23 + x2B
xA3 + x13 + x23 = x34
x34 = x41 + x42 + x4B
16xA1 + 20xA3 + 30x13 + 13x12 + 6x23 + 25x34 + 11x41 + 8x42 + 14x2B + 23x4B ≤ 44
xij
intero
7
Dato un grafo G = (N, A), non orientato, si consideri il seguente problema. I nodi del
grafo rappresentano città che devono essere difese da pattuglie. Le pattuglie possono
essere dislocate in corrispondenza dei nodi del grafo, e possono essere di due tipi, fisse e
mobili. Una pattuglia fissa dislocata nella città i difende solo la città i. Una pattuglia
mobile dislocata nella città i difende, oltre a i, anche tutte le città adiacenti, ossia difende
{i} ∪ δ(i). Dislocare una pattuglia fissa ha un costo pari a 2, una mobile ha costo 3.
Il problema è quello di difendere tutti i nodi del grafo al costo minimo. Formulare il
problema come programmazione lineare a numeri interi.
Soluzione.
7
Consideriamo due insiemi di variabili, ossia:
{
1 se è installata una pattuglia fissa in i
0 altrimenti
xi =
{
1 se è installata una pattuglia mobile in i
0 altrimenti
yi =
La funzione obiettivo può essere immediatamente espressa come
min
∑
(2xi + 3yi )
i∈N
Si tratta ora di esprimere il vincolo sulla difesa di ciascuna città. Questo può essere
scritto tenendo conto che una città i è difesa se in i è dislocata una pattuglia, oppure se
in i ∪ δ(i) ve ne è almeno una mobile:
∑
xi + yi +
yj ≥ 1
j∈δ(i)
8
Siete i curatori dell’opera omnia del celebre gruppo Hashirim, i quali hanno pubblicato,
durante la loro carriera, complessivamente n brani, di varie durate (sia pi la durata del
brano i). Vi è stato chiesto di far uscire una collana di m compact disc, comprendente
tutti i brani, con l’unico requisito che la differenza tra la durata complessiva del cd più
lungo e di quello più corto sia minima.
Dovete decidere di quali brani deve essere composto ogni cd. Formulare il problema
come programmazione lineare a numeri interi.
Soluzione.
Utilizziamo delle variabili di assegnamento, del tipo
{
xij =
1 se il brano i è assegnato al cd j
0 altrimenti
E dunque si hanno i vincoli in base ai quali ciascun brano deve essere assegnato a un
cd:
m
∑
xij = 1
i = 1, . . . , n
j=1
Per scrivere la funzione obiettivo, dobbiamo introdurre le variabili scalari y e z che
staranno a indicare la lunghezza del più corto e più lungo cd rispettivamente. Per fare
questo basta imporre
y≤
n
∑
pi xij
j = 1, . . . , m
i=1
8
z≥
n
∑
pi xij
j = 1, . . . , m
i=1
dopo di che, la funzione obiettivo è semplicemente
min z − y
9
Un’azienda produce scarpe. Nella tabella sono indicate le risorse richieste dalla produzione
di ciascun paio di scarpe, e il prezzo di vendita. Il problema consiste nel determinare
la produzione di ciascun tipo di scarpa, considerando le risorse disponibili, e tenendo
presente che per ciascun tipo di scarpa è stabilita una soglia minima, sotto la quale non
vi è convenienza a produrre (ad esempio, la produzione di scarponi sarà pari a 0 oppure
dev’essere almeno pari a 100 paia, e cosi’ per gli altri tipi). Formulare il problema di
massimizzare il profitto in termini di programmazione lineare intera.
tipo
cuoio (g) ore-macchina chiodi
scarponi da montagna
850
3
20
mocassini
600
2
15
scarpe da passeggio
700
2.5
20
disponibilità
120000
7000
40000
soglia
100
200
150
prezzo (euro/paio)
150
120
130
Soluzione.
Come in tutti i problemi di allocazione di risorse, avremo alcune variabili continue (x1 ,
x2 , x3 ) corrispondenti al numero di unità di ciascun prodotto da produrre. La funzione
obiettivo e i vincoli sulla disponibilità di risorse sono dunque:
max z = 150x1 + 120x2 + 130x3
850x1 + 600x2 + 700x3 ≤ 120000
3x1 + 2x2 + 2.5x3 ≤ 7000
20x1 + 15x2 + 20x3 ≤ 40000
oltre a questi vincoli, vanno però aggiunti quelli relativi alla soglia di produzione.
In particolare, dobbiamo esprimere il fatto che se un tipo di articolo viene prodotto, la
corrispondente variabile deve assumere almeno un certo valore. Questo richiede allora
l’introduzione di variabili binarie:
{
yi =
1 se l’articolo i è prodotto
0 altrimenti
9
vanno quindi aggiunti altri due tipi di vincoli. Il primo tipo impone che una variabile
xi non può essere maggiore di zero se quell’articolo non viene prodotto. Tale vincolo deve
scomparire nel caso in cui invece l’articolo venga prodotto, per cui dobbiamo usare un
numero M sufficientemente grande a secondo membro (ad es. M > 100000):
x 1 ≤ M y1
x 2 ≤ M y2
x 3 ≤ M y3
Un secondo tipo di vincoli deve invece imporre che, se un articolo viene prodotto, ciò deve
avvenire in una certa quantità minima:
x1 ≥ 100y1
x2 ≥ 200y2
x3 ≥ 150y3
10
Una macchina deve effettuare n lavorazioni non interrompibili {1, 2, . . . , n}. La lavorazione i richiede un tempo di processamento pi . Per ogni lavorazione è specificata una
due date di . Formulare in termini di programmazione lineare a numeri interi il problema
di determinare l’ordine in cui eseguire le lavorazioni in modo tale da minimizzare la somma
delle tardiness (ricordiamo che la tardiness Ti è definita come max{0, Ci − di }, ove Ci è il
tempo di completamento del job i).
Soluzione.
Si tratta di un problema di scheduling (NP completo in senso ordinario). Possiamo
utilizzare le variabili continue Si a indicare l’istante di inizio del job i, e dunque:
Ci = Si + pi
i = 1, . . . , n
Ti ≥ Ci − di
i = 1, . . . , n
Ti ≥ 0
i = 1, . . . , n
dove la variabile Ti , dal momento che stiamo minimizzando, sarà pari, in una soluzione
ottima, esattamente alla tardiness del job i. La funzione obiettivo sarà dunque
min
n
∑
Ti
i=1
10
Rimane da esprimere il vincolo che la macchina non può eseguire più di una lavorazione
alla volta. A questo scopo possiamo introdurre le variabili
{
sij =
1 se il job i è effettuato prima di j
0 se il job j è effettuato prima di i
Vogliamo dunque imporre che se sij = 1, allora deve essere
Si + p i ≤ Sj
mentre ciò non è vero se sij = 0. Introducendo una costante M sufficientemente grande
∑
(ad esempio M > pi ), per ogni coppia di job i, j avremo i due vincoli:
Si + pi ≤ Sj + M (1 − sij )
e
Sj + pj ≤ Si + M (1 − sji )
oltre a, ovviamente:
sij + sji = 1
11
Esercizi proposti
11
Risolvere il seguente problema di knapsack con il metodo del branch and bound o con la
programmazione dinamica:
max z = 2x1 + 3x2 + 4x3 + 6x4
x1 + 4x2 + 5x3 + 6x4 ≤ 9
xj ∈ {0, 1}
Risposta. La soluzione ottima è (1, 0, 0, 1), di valore 8.
12
Risolvere il seguente problema con il metodo del branch and bound:
max z = 3x1 + x2
x1 + 4x2
≤
12
2x1 + x2
≤
5
xj intero
Risposta. La soluzione ottima è (2, 1), di valore 7.
13
Risolvere il seguente problema di knapsack:
max z = 2x1 + 3x2 + 4x3 + 6x4
x1 + 4x2 + 5x3 + 6x4 ≤ 9
xj ∈ {0, 1}
Risposta. La soluzione ottima è (1, 0, 0, 1), di valore 8.
12
14
Risolvere il seguente problema di PLI con l’algoritmo dei piani di Gomory:
max z = 40x1 + 24x2 + 15x3 + 8x4
8x1 + 6x2 + 5x3 + 4x4
≤
22
xj
≥
0
xj intero
Risposta. La soluzione ottima è (2, 1, 0, 0), di valore 104.
15
Risolvere il seguente problema di PLI con l’algoritmo dei piani di Gomory:
max z = 2x1 + x2
3x1 − 2x2 ≤ 0
x1 + 2x2 ≥ 0
xj ≥ 0
xj ∈ {0, 1}
Risposta. La soluzione ottima è (0, 1), di valore 1.
16
Risolvere il seguente problema di knapsack
max z = 52x1 + 40x2 + 38x3 + 19x4 + x5
17x1 + 5x2 + 13x3 + 4x4 + 5x5 ≤ 20
xi ∈ {0, 1}
Risposta. La soluzione ottima è (0, 1, 1, 0, 0), di valore 78.
17
Risolvere il seguente problema di knapsack
max z = 52x1 + 10x2 + 38x3 + 9x4 + x5
17x1 + 5x2 + 13x3 + 3x4 + x5
xi
13
≤
intero
29
Risposta. La soluzione ottima è (1, 0, 0, 4, 0), di valore 88.
18
Risolvere il seguente problema di knapsack
max z = 12x1 + 9x2 + 10x3 + 7x4
8x1 + 6x2 + 7x3 + 5x4 ≤ 20
xi ∈ {0, 1}
Risposta. La soluzione ottima è (1, 0, 1, 1), di valore 29.
19
Si risolva il seguente problema di knapsack
max z = 3x1 + 7x2 + 9x3 + 11x4
6x1 + 8x2 + 9x3 + 10x4 ≤ 23
xi ∈ {0, 1}
Risposta. La soluzione ottima è (0, 0, 1, 1), di valore 20.
20
Risolvere il seguente problema di PLI con l’algoritmo dei piani di Gomory:
max z = x1 + 2x2
x1 − 2x2 ≥
−2
x1 + x2
≤
3
x1 , x2
≥
0
x1 , x2 interi
Risposta. La soluzione ottima è (2, 1), di valore 4.
14
21
Grazie a una vincita al superenalotto, avete ora il problema di investire 100 milioni di
lire. Un vostro amico vi consiglia di comprare quote di fondi di investimento, della società
Kezef. In particolare vi sono due tipi di fondi: Kezef Italia e Kezef Europa. Le quote
possono essere acquistate solo in lotti indivisibili, da 12 milioni ciscuno per Kezef Italia, da
20 milioni ciascuno per Kezef Europa. Il vostro amico ritiene che il rendimento annuo di
Kezef Italia dovrebbe essere pari a un sesto del capitale investito; quello di Kezef Europa
pari al 15%. Il numero di lotti di Kezef Europa non può superare il 50% del numero
complessivo di lotti acquistati. Formulare il problema come programmazione lineare a
numeri interi e risolverlo con il metodo dei piani di taglio, indicando le disequazioni
(tagli) generate nel corso del procedimento.
22
Ci sono n lavori indivisibili da effettuare, ognuno caratterizzato da una sua durata pi ,
i = 1, . . . , n. Avendo due persone a disposizione, volete ripartire i lavori tra queste
due persone facendo in modo che i loro carichi di lavoro siano il più possibile bilanciati.
Formulare il problema in termini di problema di knapsack.
23
Un operatore turistico noleggia il proprio furgoncino a 8 posti per far fare ai turisti
escursioni guidate di Radiator Springs. Si presentano all’operatore quattro gruppi di
turisti, costituiti da 2, 3, 4 e 5 persone. Siccome non c’è posto per tutti, l’operatore chiede
a ogni gruppo (i cui componenti non vogliono separarsi) di offrire una cifra per il trasporto.
I componenti dei quattro gruppi si consultano, e alla fine offrono, rispettivamente, 30, 50,
80 e 70 euro. Quali gruppi accetterà l’operatore turistico per massimizzare i guadagni?
Rispondere formulando il problema e applicando un opportuno algoritmo.
24
Una macchina deve eseguire 6 lavori, ciascuno dei quali è caratterizzato da una durata pi ,
una data di consegna di e un peso wi , che può pensarsi come una misura dell’importanza
di ciascun lavoro. Tra i lavori esistono relazioni di precedenza. Formulare come PLI
il problema di determinare la sequenza di lavorazione sulla macchina in modo tale da
15
minimizzare il massimo valore che assume la quantità wi Ti , ove Ti indica la tardiness del
lavoro i-esimo.
i di
1 8
2 12
3 8
4 8
5 12
6 13
wi
2
1
2
1
4
3
pi
4
3
2
4
1
1
precede...
5
5
6
6
–
–
25
Un grafo non orientato G(N, A) rappresenta un’area geografica, in cui N è l’insieme dei
nodi (numerati da 1 a n) e A è quello degli archi. I nodi rappresentano potenziali città
in cui una linea aerea può aprire sedi. Aprire una sede nella città i ha un costo pari a fi .
Per ogni arco (i, j) sono dati due valori: cij e dij . Può essere attivata una tratta aerea tra
le città i e j, solo se vi è una sede in i oppure in j. Se vi è una sede soltanto in una delle
due città, allora la compagnia prevede di guadagnare cij . Se vi è una sede in ambedue
le città, allora la compagnia prevede di guadagnare dij > cij . Il problema consiste nel
determinare in quali città aprire una sede, in modo da massimizzare i profitti. Scrivere la
formulazione del problema come PLI.
26
E’ dato un grafo non orientato G(N, A), in cui N è l’insieme dei nodi (numerati da 1 a n)
e A è quello degli archi. Per ogni arco (i, j) è associato un peso cij . Il problema consiste
nel colorare ciascun nodo con uno tra quattro colori (Rosso, Blu, Nero, Verde), in modo
da minimizzare il peso complessivo degli archi aventi ambedue gli estremi con lo stesso
colore. Formulare tale problema come PLI.
27
In un pronto soccorso, per ciascun giorno della settimana è dato un certo fabbisogno in
termini di persone che devono essere presenti in servizio a tempo pieno. Il fabbisogno di
una persona a tempo pieno può essere soddisfatto da due persone a tempo parziale.
persone
lunedi martedi mercoledi giovedi venerdi sabato
10
8
12
9
9
7
16
domenica
8
La struttura dei turni è la seguente: quattro giorni consecutivi di lavoro a tempo pieno,
seguiti da un giorno di lavoro a tempo parziale, seguiti da due di riposo.
Il costo settimanale di un lavoratore si ottiene considerando 100 euro per ogni giorno
feriale (dal lunedi al venerdi), 110 per ogni sabato lavorato e 130 per ogni domenica
lavorata. Questi costi si dimezzano per le giornate lavorate a tempo parziale.
Formulare come PLI il problema di come coprire il fabbisogno di personale al costo
minimo.
28
Un circuito elettronico è rappresentato da un grafo non orientato G(N, A), in cui N è
l’insieme dei nodi (componenti) e A quello degli archi (collegamenti). Per ogni nodo i è
dato un peso wi che rappresenta l’area del componente e per ogni arco (i, j) un valore cij
che rappresenta il numero di collegamenti elettrici tra i due componenti i e j. Si vuole
partizionare l’insieme dei nodi in 3 insiemi, in modo tale che il peso dei nodi di ciascun
sottoinsieme sia compreso tra due valori L e U , e che la somma dei valori degli archi aventi
estremi in insiemi diversi sia minimizzata. Formulare tale problema come PLI.
29
In una scuola di musica, bisogna definire l’orario settimanale. Ci sono da riempire complessivamente quattro pomeriggi (L, Ma, Me, G) di tre ore ciascuno (indicate come ore 1,
2 e 3). Le specifiche sono le seguenti:
• Ci sono da allocare 6 ore di chitarra, 3 di violino, 2 di pianoforte e 1 di arpa.
• Ogni giorno vi deve essere lezione di almeno due strumenti diversi.
• Siccome l’arpista e il pianista hanno litigato, non vogliono incontrarsi e quindi le
due lezioni corrispondenti non devono mai essere consecutive.
• Ogni insegnante può esprimere delle preferenze, in termini di ore in cui non vuole
fare lezione:
– l’insegnante di chitarra non vuole fare lezione nelle ore 1 del lunedi o del
martedi;
– l’insegnante di violino non vuole fare lezione nelle ore 2 del mercoledi o del
giovedi;
17
– l’insegnante di pianoforte non vuole mai fare lezione nell’ora 3 di qualsiasi
giorno;
– l’insegnante di arpa non vuole fare lezione il martedi.
Formulare come PLI il problema di determinare un orario che rispetti tutti i vincoli
indicati, minimizzando il numero di ore che non rispettano le preferenze degli insegnanti.
30
Il centro prove di una casa automobilistica deve eseguire una serie di test su motori. I
motori disponibili sono raggruppati in classi, numerate da 1 a 5 (1 è la classe più alta).
Ciascun test j è caratterizzato da due informazioni: il chilometraggio kj e la classe minima
cj . Ad esempio, se cj = 3, vuol dire che il test j può essere svolto da motori di classe 1,
2 o 3, ma non 4 o 5.
A ogni classe i, sono associate due quantità: il prezzo pi di acquisto di un motore di
quella classe, e un costo chilometrico hi . Ad esempio, se tutto il test j venisse svolto da un
motore di classe i, il costo chilometrico sarebbe kj hi . Si consideri che uno stesso motore
può essere utilizzato per più test, dunque pi viene pagato una volta sola.
Formulare PER ESTESO come PLI il problema di determinare quali motori acquistare
e come assegnare i test al fine di minimizzare la spesa complessiva.
test j
A
B
C
D
E
motore (classe) i
1
2
3
4
5
kj (km) cj
20000
4
40000
2
30000
5
50000
4
20000
3
pi (euro) hj (euro/km)
10500
0.3
8500
0.4
8000
0.5
7500
0.6
6000
0.7
31
Nel territorio di una ASL, vi sono n centri abitati, in ognuno dei quali può essere dislocata
una unità di pronto soccorso. Per ogni coppia di centri i e j è nota la distanza dij .
18
Considerando che, data una dislocazione delle unità, ciascun centro abitato si servirà del
pronto soccorso più vicino, il problema consiste nel decidere dove localizzare m < n unità
di pronto soccorso, facendo in modo che sia minima la massima distanza di un centro
abitato dal pronto soccorso a esso più vicino. (Non si può aprire più di una unità in un
centro abitato.) Formulare il problema come PLI.
32
Un sistema per la gestione dei carichi elettrici domestici controlla, tra le altre cose, uno
scaldabagno. Lo scaldabagno può essere tenuto acceso o spento durante ciascuna delle 24
ore. Siccome si vuole però che la temperatura dell’acqua non scenda mai troppo rispetto
a un valore di riferimento, devono valere le seguenti condizioni:
• Nell’arco delle 24 ore, lo scaldabagno non può rimanere spento per più di 12 ore.
• Lo scaldabagno non può restare mai spento per più di 4 ore consecutive.
• Ogni intervallo di tempo in cui lo scaldabagno è acceso deve durare almeno 3 ore.
Il costo dell’energia elettrica varia di ora in ora: sia pt il consumo (in KWh) se lo
scaldabagno è acceso durante l’ora t, t = 1, . . . , 24 (chiaramente il consumo è nullo se
lo scaldabagno è spento). Formulare come programmazione lineare intera il problema
di decidere, per ciascuna ora nell’arco di una giornata, se lo scaldabagno deve rimanere
acceso o spento, nel rispetto delle condizioni indicate, e in modo da minimizzare i costi
complessivi.
33
Un’officina di gommista consiste di un reparto cambio gomme (1), seguito da un reparto
dove viene effettuata la convergenza (2). Ogni vettura i deve essere processata prima
dal reparto (1), per un tempo pi1 , e poi dal (2), per un tempo pi2 , fermo restando che
ciascun reparto può operare su una vettura sola alla volta. L’istante al quale una vettura
termina la lavorazione nel reparto (2) prende il nome di tempo di completamento. La
sequenza con cui le vetture sono processate dai due reparti è la stessa. Considerando che
per ciascuna vettura saranno necessari i tempi (in minuti) indicati in tabella, formulare
come programmazione lineare intera il problema di determinare la sequenza delle vetture
che minimizza la somma dei tempi di completamento delle lavorazioni.
19
vettura pi1
A
12
B
7
C
9
D
8
pi2
8
15
11
4
34
Un grafo G = (N, A) rappresenta una rete stradale. Una pattuglia di polizia può essere
localizzata in qualsiasi nodo. Vi sono due tipi di pattuglie. Una normale, che ha un costo
cn , che consente di controllare il nodo stesso. Una speciale, che ha un costo superiore
cs > cn , che consente di controllare, oltre al nodo stesso, anche tutti i suoi adiacenti.
Per il grafo in figura, formulare come programmazione a numeri interi il problema di
determinare in quali nodi dislocare pattuglie normali e speciali in modo da controllare
tutti i nodi del grafo al costo minimo.
35
Uno stabilimento per la produzione di ceramiche deve organizzare la produzione per il
prossimo periodo. La fornace deve produrre i lotti indicati in tabella, per ognuno dei quali
è dato l’istante di rilascio (ri , release date, in giorni a partire da oggi) prima del quale il
lotto non può iniziare, il tempo necessario al suo processamento (pi , giorni), una data di
consegna prevista (di , due date, in giorni a partire da oggi) e la penale (wi , in euro) che
si paga se un lotto non viene terminato entro la propria due date. Una volta iniziato, il
lotto non può essere interrotto.
Formulare come programmazione lineare intera il problema di determinare l’istante di
inizio di ciascun lotto in modo tale da minimizzare i costi legati alle penali.
lotto ri
A
0
B
1
C
7
D
2
pi
4
5
3
6
di
8
8
12
15
wi
3000
2500
1000
4000
36
Dalle 12 alle 18 di un certo giorno, il prezzo dell’energia elettrica al consumatore è
il seguente (centesimi di euro/kWh, supposto costante all’interno dello slot temporale
orario):
20
12–13 13–14 14–15 15–16 16–17 17–18
3
1
2
2
3
1
Un consumatore deve usare, nell’arco orario compreso tra le 12 e le 18, tre elettrodomestici: lavatrice, lavastoviglie e forno. Per i programmi scelti, tali elettrodomestici
hanno i profili di carico (kW) indicati nella seguente tabella (si noti che i programmi di
lavatrice e forno durano tre ore, la lavastoviglie due):
lavatrice
2 1 1,5
lavastoviglie
forno
2,5
1
2,5 2 1,5
Una volta fatto partire, un elettrodomestico non può essere interrotto. In nessuna
ora si possono superare i 3.5 kW complessivi. Il problema è decidere quando far partire
ciascun elettrodomestico per minimizzare i costi complessivi, nel rispetto del vincolo sul
consumo complessivo. Formulare il problema come programmazione lineare a numeri
interi.
37
È dato un insieme di 10 elettrodomestici, che devono essere caricati su 4 furgoni. Ciascun
elettrodomestico è caratterizzato da un peso wi , e dal suo tipo (congelatore, lavatrice,
lavastoviglie). Il massimo peso che un furgone può portare è 230 kg. Ciascun elettrodomestico, per il trasporto, deve essere montato su un apposito supporto di legno.
Uno stesso supporto può essere usato, su un furgone, per più elettrodomestici dello stesso
tipo. I furgoni hanno varie restrizioni per quanto riguarda i tipi di elettrodomestico che
possono ospitare, come indicato nella tabella, che riporta anche il costo dei vari tipi di
supporto.
i
wi
1 80
2 90
3 105
4 80
5 75
6 85
7 90
8 55
9 65
10 75
tipo
congelatore
congelatore
congelatore
frigorifero
frigorifero
frigorifero
frigorifero
lavastoviglie
lavastoviglie
lavastoviglie
21
tipo
furgoni compatibili
congelatore
1,2,4
frigorifero
1,3,4,5
lavastoviglie
2,3,4,5
costo supporto
500 euro
600 euro
700 euro
Formulare come PLI il problema di come caricare i furgoni minimizzando la spesa per
i supporti.
38
Un insieme di n lavorazioni deve essere effettuato da una macchina utensile. Ogni lavorazione è caratterizzata da un numero di giorni-macchina necessari per effettuarla pi , una
due date di (espressa in giorni a partire da oggi), e un guadagno ri . Il guadagno però è conseguito se e solo se la lavorazione termina entro la propria due date. La macchina utensile
può eseguire una sola lavorazione per volta. Le lavorazioni non sono interrompibili.
Formulare come PLI il problema di determinare in che ordine sequenziare le lavorazioni
sulla macchina al fine di massimizzare il guadagno.
22