•10/05/2004

•1

Programmazione Matematica:Modelli di Programmazione Intera

Daniele VigoD.E.I.S. − Università di Bologna

dvigo@deis.unibo.it

rev. 2.0 − Aprile 2004

Modelli.2D. Vigo

Indagine di Mercato• Mix di utenti da intervistare telefonicamente:

• Telefonate in 2 fasce orarie:• Mattina: 1 € per telefonata (almeno il 50%)• Sera: 1.5 € per telefonata

Donne Uomini

Sposate Non Sposate Sposati Non Sposati

150 110 120 100

15%

10%

sera

mattina

5%30%20%30%

40%10%10%30%

• minimizzare il costo complessivo delle telefonate

•10/05/2004

•2

Modelli.3D. Vigo

Modello matematico (PLI)• x1 : numero di telefonate alla mattina• x2 : numero di telefonate alla sera

min x1 + 1.5 x2

Donne sposate: 0.3 x1 + 0.3 x2 ≥ 150Donne non spos.: 0.1 x1 + 0.2 x2 ≥ 110Uomini sposati: 0.1 x1 + 0.3 x2 ≥ 120Uomini non spos.: 0.1 x1 + 0.15 x2 ≥ 100

x1 − x2 ≥ 0x1 , x2 ≥ 0 INTERE

Modelli.4D. Vigo

Noleggio di macchinari• Un ente pubblico deve noleggiare dei macchinari

• Noleggi possibili per 3 periodi diversi:• 1 mese: 400 € • 2 mesi: 700 € (= 350 €/mese)• 3 mesi: 900 € (= 300 €/mese)

• minimizzare il costo complessivo di noleggio

Mese Gennaio Febbraio Marzo Aprile Maggio

Fabbisogno 109

Giugno

5 7 9 5

•10/05/2004

•3

Modelli.5D. Vigo

Modello PLI• Non basta sapere quanti macchinari noleggiare

• quando (gennaio, febbraio, …)

• per quanto tempo (1,2 o 3 mesi)

GE1, GE2, GE3 = n. macch. affittati a Gennaio per 1, 2 e 3 mesi.

….

GI1, GI2, GI3 = n. macch. affittati a Giugno per 1, 2 e 3 mesi.

Modelli.6D. Vigo

Modello PLImin 400 GE1 + 400 FE1 + … + 400 GI1 +

700 GE2 + 700 FE2 + … + 700 GI2 + 900 GE3 + 900 FE3 + … + 900 GI3

GE1 + GE2 + GE3 ≥ 9FE1 + FE2 + FE3 + GE2 + GE3 ≥ 5MA1 + MA2 + MA3 + FE2 + FE3 + GE3 ≥ 7AP1 + AP2 + AP3 + MA2 + MA3 + FE3 ≥ 9MG1 + MG2 + MG3 + AP2 + AP3 + MA3 ≥ 10GI1 + GI2 + GI3 + MG2 + MG3 + AP3 ≥ 5GE1, GE2, …, GI2, GI3 ≥ 0 INTERE

•10/05/2004

•4

Modelli.7D. Vigo

Costo fisso di produzione• Problema di mix di produzione (tipo dieta)• Contributo prodotto j alla funzione obiettivo:

• 0, se non prodotto (xj = 0)

• Fj + pjxj se prodotto (xj > 0)

• Fj = costo fisso (macchinari)• pj = costo di produzione

• discontinuità nell’origine

Modelli.8D. Vigo

Costo fisso di produzione (2)

• vincoli di tipo logico (if …)

• occorre legare tra loro le x e le y con vincoli lineari

⎩⎨⎧

=>

=0 se00 se1

j

jj x

xy

∑=

+n

jjjjj xpyF

1

min

bAx ≥0≥x{ }1,0∈y

•10/05/2004

•5

Modelli.9D. Vigo

Costo fisso di produzione (3)

con M >> 1 (≅ +∞)⎩⎨⎧

=>

=0 se00 se1

j

jj x

xy jj Myx ≤

• validità del vincolo:• se xj > 0 yj deve essere =1 (xj ≤ +∞)• se xj = 0 yj può essere = 0 o 1 (0≤ 0 o +∞)

oppure• se yj = 0 xj deve essere = 0 (xj ≤ 0)• se yj = 1 xj può essere = 0 o >0 (xj ≤+∞)

• il vincolo impone solo parte della relazione logica

⇒

Modelli.10D. Vigo

Costo fisso di produzione (4)

• non è necessario imporre anche l’altra metà della relazione logica

• una soluzione con xj = 0 ed yj = 1 non può essere ottima (ne esiste una equivalente che costa meno)

∑=

+n

jjjjj xpyF

1

min

bAx ≥

0≥x { }1,0∈yjj Myx ≤

•10/05/2004

•6

Modelli.11D. Vigo

Mix di pubblicità• Budget di 150 K € per pubblicizzare una nuova

iniziativa.• Due possibili canali pubblicitari:

• Giornali: 1 K€ per annuncio• TV: 10 K€ per annuncio

• Al massimo 30 annunci su giornali e 15 annunci su TV

• Il numero di utenti raggiunti dipende in modo non lineare dal numero di annunci inviati.

• massimizzare il numero totale di utenti raggiunti

Modelli.12D. Vigo

Mix di pubblicità (2)Giornali

n. annunci Nuovi utenti per annuncio

1−10 90011−20 60021−30 300

10 20 30

200011−1550006−10100001−5

Nuovi utenti per annuncio

n. annunciTV

9000

1500018000

•10/05/2004

•7

Modelli.13D. Vigo

Modello PLI• si possono usare variabili binarie per indicare se le

variabili decisionali sono nella 1ª, 2ª o 3ª fascia• Vincoli di tipo logico come per il costo fisso

Modelli.14D. Vigo

Modello PLIG1, G2, G3 = n. annunci su giornali nelle 3 fasceT1, T2, T3 = n. annunci su TV nelle 3 fasce

max 900 G1 + 600 G2 + 300 G3 +10000 T1 +5000 T2 +2000 T3

G1 + G2 + G3 + 10 T1 +10 T2 + 10 T3 ≤ 150G1, G2, G3 ≤ 10T1, T2, T3 ≤ 5G1, G2, G3, T1, T2, T3 ≥ 0, INTERE

•10/05/2004

•8

Modelli.15D. Vigo

Turnazione del personale• personale richiesto per giorno della settimana:

Lu Ma Me Gi Ve Sa Do

22 18 13 14 15 18 25

• ogni persona • lavora 5 giorni consecutivi• i 2 giorni successivi sono di riposo

• minimizzare il numero di persone necessarie• altri vincoli possibili in problemi reali:

• turni diversi• preferenze

Modelli.16D. Vigo

Modello matematico (PLI)x1 : numero di persone che iniziano il turno Lunx2 : numero di persone che iniziano il turno Mar …

min x1 + x2 + x3 + x4 + x5 + x6 + x7Lu: x1 + x4 + x5 + x6 + x7 ≥ 22Ma: x1 + x2 + x5 + x6 + x7 ≥ 18Me: x1 + x2 + x3 + x6 + x7 ≥ 13Gi: x1 + x2 + x3 + x4 + x7 ≥ 14Ve: x1 + x2 + x3 + x4 + x5 ≥ 15Sa: + x2 + x3 + x4 + x5 + x6 ≥ 18Do: + x3 + x4 + x5 + x6 + x7 ≥ 25

x1 … x7 ≥ 0 INTERE

•10/05/2004

•9

Modelli.17D. Vigo

Turnazione personale: varianti• Una volta stabiliti il numero di persone necessarie

per turno, i turni vanno attribuiti alle persone• Ogni persona esprime una preferenza per il turno

(7=prima, 1=ultima scelta)• Assegnare le persone ai turni massimizzando la

preferenza espressa• Idem tenendo conto dell’anzianità di servizio:

punteggio di assegnazione=preferenza*anzianità

Modelli.18D. Vigo

Assegnazione di incarichin persone ed n incarichicij tempo/costo ass. incarico j alla pers. i

• determinare l’assegnamento delle persone agli incarichi di costo complessivo minimo

• Es. n= 2lavoro

pers. 1 21 20 402 30 20

Costo = 40

•10/05/2004

•10

Modelli.19D. Vigo

Assegnazione di incarichi (2)• n = 3 lavoro

pers. 1 2 31 20 60 302 80 40 903 50 70 80

6 soluzioni

Costo = 120

N. soluzioni = n (n−1) (n−2) … = n!se n = 20 ⇒ n! ≈ 2.4 * 1018

enumerazione su PC 486/33 (≈1 Mflop/sec.): 4.6M anni !

Modelli.20D. Vigo

Variabili decisionali

lavoropers. 1 2 3

1 20 60 302 80 40 903 50 70 80

variabili1 2 3

1 0 0 12 0 1 03 1 0 0

Matrice di permutazione: un solo 1 ∀ riga e colonna

1 se la persona i esegue l’incarico j0 altrimenti

xij =

•10/05/2004

•11

Modelli.21D. Vigo

Modello matematico (PLI)• Funzione obiettivo (min. costo)

min Σi=1,nΣj=1,n cij xij

• Un solo lavoro per persona:

Σj=1,n xij = 1 (i = 1, …, n)• Una sola persona per lavoro:

Σi=1,n xij = 1 (j = 1, …, n)xij ∈{0, 1} (i,j = 1, …, n)

variabili1 2 3

1 0 0 12 0 1 03 1 0 0

Modelli.22D. Vigo

Assegnazione di incarichi (bis)• Una compagnia desidera assegnare n =14 impiegati

ai suoi m=10 uffici, che hanno una richiesta rj

Ufficio 1 2 3 4 5 6 7 8 9 10Richiesta 1 1 1 1 2 1 2 2 2 1

• Ogni impiegato ha espresso la propria preferenza pijper uno specifico ufficio (1=prima …10=ultima)

• Assegnare gli impiegati agli uffici massimizzando la soddisfazione per l’ufficio ottenuto (= minimizzazione preferenze assegnate)

•10/05/2004

•12

Modelli.23D. Vigo

Modello matematico• Funzione obiettivo (min. preferenze assegnate)

min Σi=1,nΣj=1,m pij xij

• Un solo ufficio per impiegato:

Σj=1,m xij = 1 (i = 1, …, n)• Il numero richiesto di impiegati per ufficio :

Σi=1,n xij = rj (j = 1, …, m)xij ∈{0, 1} (i,=1, …,n;

j = 1, …, m)

Modelli.24D. Vigo

Riorganizzazione del personale• Un’azienda prevede la necessità di migliorare nel

breve periodo la preparazione del suo personale• Tre categorie: inesperto, addestrato ed esperto

Costo licenziamento

Costo assunzione

Assumibili per anno

Esperti 700 € 250 € 500

Addestrati 500 € 150 € 800

Inesperti 350 € 100 € 1200

•10/05/2004

•13

Modelli.25D. Vigo

Riorganizzazione del personale (2)• Costo di riaddestramento:

• inesperti ⇒ addestrati : 400 €• addestrati ⇒ esperti : 500 €

• Stima impiegati necessari

Attuale Anno 1 Anno 2 Anno 3

Esperti 800 1200 1500 2000

Addestrati 1500 1500 2000 2500

Inesperti 2000 1600 1000 0

Modelli.26D. Vigo

Riorganizzazione del personale (3)• Determinare il piano di assunzioni, licenziamenti

ed addestramenti per i prossimi tre anni.• Obiettivi:

• minimizzazione dei costi• minimizzazione dei licenziamenti

•10/05/2004

•14

Modelli.27D. Vigo

Localizzazione infrastrutture• apertura centri CUP in una città divisa in 6 zone • 1 sito per quartiere• tempi di trasferimento tra i quartieri (in minuti):

1 2 3 4 5 61 0 10 20 30 30 202 10 0 25 35 20 103 20 25 0 15 30 204 30 35 15 0 15 255 30 20 30 15 0 156 20 10 20 25 15 0

Modelli.28D. Vigo

Localizzazione infrastrutture (2)• massimo tempo di trasferimento 15 minuti

1 2 3 4 5 61 0 10 – – – –2 10 0 – – – 103 – – 0 15 – –4 – – 15 0 15 –5 – – – 15 0 156 – 10 – – 15 0

• minimizzare il numero di centri aperti

•10/05/2004

•15

Modelli.29D. Vigo

Modello matematico (PLI)xi : 1 se si attiva il sito nel quartiere i, 0 altrimenti

min x1 + x2 + x3 + x4 + x5 + x6

1: x1 + x2 ≥ 12: x1 + x2 + x6 ≥ 13: + x3 + x4 ≥ 14: + x3 + x4 + x5 ≥ 15: + x4 + x5 + x6 ≥ 16: + x2 + x5 + x6 ≥ 1

x1 … x6 ≥ 0 INTERE

Modelli.30D. Vigo

Problema del set covering (SCP)• Matrice binaria A con m righe e n colonne:

se Aij =1 si dice che la colonna j “copre” la riga i• Cj “costo” della colonna j (j=1,…,n)

• determinare un sottoinsieme di colonne avente costo minimo e tale che ogni riga sia coperta da almeno una colonna selezionata

•10/05/2004

•16

Modelli.31D. Vigo

Modello PLI

min Σj=1,n Cj xj

Σj=1,n Aij xj ≥ 1 (i = 1, …, m)

xj ∈{0, 1} (j = 1, …, n)

1 se la colonna j viene selezionata0 altrimenti

xj =

Modelli.32D. Vigo

Variante: set partitioning (SPP)• determinare un sottoinsieme di colonne avente

costo minimo e tale che ogni riga sia coperta da esattamente una colonna selezionata.

Σj=1,n Aij xj = 1 (i = 1, …, m)

•10/05/2004

•17

Modelli.33D. Vigo

Problema dello zaino (KP01)• Problema di selezione:• n oggetti• Pj profitto dell’oggetto j (j=1,…,n)• Wj peso dell’oggetto j (j=1,…,n)• 1 contenitore (zaino) di capacità K

• determinare un sottoinsieme di oggetti avente massimo profitto e peso complessivo non superiore alla capacità K dello zaino

Modelli.34D. Vigo

Modello PLI

max Σj=1,n Pj xj

Σj=1,n Wj xj ≤ K

xj ∈{0, 1} (j = 1, …, n)

oppure 0 ≤ xj ≤ 1 INTERA ( j = 1, …, n)

1 se l’oggetto j viene inserito nel contenitore0 altrimenti

xj =

•10/05/2004

•18

Modelli.35D. Vigo

Variante: KP−bounded• Il generico oggetto j è disponibile in cj esemplari• può essere scelto cj volte

max Σj=1,n Pj xj

Σj=1,n Wj xj ≤ K

xj ∈{0, 1} (j = 1, …, n)

oppure 0 ≤ xj ≤ cj INTERA ( j = 1, …, n)

Modelli.36D. Vigo

Variante: subset sum problem• Il generico oggetto j ha profitto Pj e peso Wj = Pj.

dato un insieme di n numeri, selezionarne un sottoinsieme di somma massima e non eccedente una data soglia K

• Taglio di barre e minimizzazione scarto

max Σj=1,n Pj xj

Σj=1,n Pj xj ≤ K

xj ∈{0, 1} (j = 1, …, n)

•10/05/2004

•19

Modelli.37D. Vigo

Problema KP multiplo (MKP01)• n oggetti• Pj profitto dell’oggetto j (j=1,…,n)• Wj peso dell’oggetto j (j=1,…,n)• m contenitori, ciascuno di capacità Ki (i=1,…,m)• un oggetto può al più andare in un solo contenitore

• impaccare nei contenitori un sottoinsieme di oggetti avente massimo profitto in modo che la somma dei pesi degli oggetti inseriti in ogni contenitore non superi la corrispondente capacità Ki

Modelli.38D. Vigo

Modello PLI

max Σj=1,n Pj (Σi=1,m xij)

Σj=1,n Wj xij ≤ Ki (i = 1, …, m)

Σi=1,m xij ≤ 1 (j = 1, …, n)

xij ∈{0,1} (i = 1, …, m; j = 1, …, n)

1 se l’oggetto j viene inserito nel contenitore i0 altrimenti

xij =

•10/05/2004

•20

Modelli.39D. Vigo

Bin Packing (1BP)• n oggetti• Wj peso dell’oggetto j (j=1,…,n)• n contenitori (bin), ciascuno di capacità K

• impaccare tutti gli oggetti nel minor numero possibile di contenitori in modo che la somma dei pesi degli oggetti inseriti in ogni contenitore non superi la capacità K

Modelli.40D. Vigo

Modello PLI

1 se l’oggetto j viene inserito nel contenitore i0 altrimenti

xij =

1 se il contenitore i viene utilizzato0 altrimenti

yi =

•10/05/2004

•21

Modelli.41D. Vigo

Modello PLI

min Σi=1,n yi

Σj=1,n Wj xij ≤ K yi (i = 1, …, n)

Σi=1,n xij = 1 (j = 1, …, n)

yi ∈{0, 1} (i = 1, …, n)

xij ∈{0, 1} (i, j = 1, …, n)

Modelli.42D. Vigo

Variante: Vector Packing (VPP)• Il generico oggetto j ha un volume Vj ed ogni

contenitore ha anche una capacità in volume Timpaccare tutti gli oggetti nel minor numero possibile di contenitori in modo da rispettare, in ogni contenitore, sia il vincolo di peso che quello di volume

Σj=1,n Wj xij ≤ K yi (i = 1, …, n)

Σj=1,n Vj xij ≤ T yi (i = 1, …, n)

In generale: ogni oggetto j ha m dimensioni…

•10/05/2004

•22

Modelli.43D. Vigo

Variante: Bin con capacità variabile• Il generico contenitore i ha capacità Ki (e costo Ci)

impaccare tutti gli oggetti in un insieme di contenitori di costo minimo in modo che la somma dei pesi degli oggetti inseriti in ogni contenitore i non superi la capacità Ki

min Σi=1,n Ci yi

Σj=1,n Wj xij ≤ Ki yi (i = 1, …, n)

Modelli.44D. Vigo

Sequenziamento di lavorazioni• n lavorazioni• pj tempo di processamento lavorazione j• no preemption = una volta iniziata la lavorazione

non può essere interrotta • m macchine identiche• una sola lavorazione alla volta per ogni macchina

• assegnare le lavorazioni alle macchine in modo tale che il tempo totale di processamento sia minimo

•10/05/2004

•23

Modelli.45D. Vigo

Sequenziamento di lavorazioni (2)• n = 5, m = 2, pj = {90, 50, 30, 40, 20}

m1

m2

t

J1

90

J5

110

J2

50

J4 J3

120

Modelli.46D. Vigo

Variabili decisionali

lavorazionimacch. 1 2 3 4 5

1 1 0 0 0 12 0 1 1 1 0

z = massimo tempo di lavorazione (makespan)

1 se la macchina i esegue lavorazione j0 altrimenti

xij =

•10/05/2004

•24

Modelli.47D. Vigo

Modello matematico (PL mista)• Funzione obiettivo (min. makespan)

min z• definizione makespan:

Σj=1,n pj xij ≤ z (i = 1, …, m)• Ogni lavorazione su una sola macchina:

Σi=1,m xij = 1 (j = 1, …, n)

xij ∈{0, 1} (i, j = 1, …, n)z ≥ 0

Modelli.48D. Vigo

Level Strip Packing (LSP)• n oggetti rettangolari• hj altezza dell’oggetto j (j=1,…,n)• wj larghezza dell’oggetto j (j=1,…,n)• 1 contenitore (strip) di altezza infinita e larghezza

finita K

• impaccare tutti gli oggetti nella strip, minimizzando l’altezza complessiva dell’impaccamento.

•10/05/2004

•25

Modelli.49D. Vigo

Level Strip Packing• Gli oggetti vengono piazzati a livelli (scaffali, shelves)

• Gli oggetti sono affiancati sulla base del livello

• L’altezza di un livello è quella dell’oggetto più alto

Modelli.50D. Vigo

LSP: considerazioni• Esiste sempre una soluzione ottima nella quale

l’oggetto più a sinistra di ogni livello è quello che determina l’altezza della shelf (“inizializza” illivello).

• E’ necessario considerare al più n livelli che possono essere inizializzati dall’oggetto corrispondente.

• Non occorre specificare dove sono impaccati i vari oggetti: basta specificare quali sono gli oggetti che inizializzano i livelli e gli oggetti contenuti in ogni livello.

•10/05/2004

•26

Modelli.51D. Vigo

Modello PLI• Se supponiamo che sia h1 ≥ h2 ≥ … ≥ hn

allora gli oggetti successivi al primo inseriti in un livello sono più bassi del primo

1 se l’oggetto i inizializza il livello i0 altrimenti(i = 1, …, n)

yi =

1 se l’oggetto j è allocato nel livello i0 altrimenti(i = 1, …, n−1; j = i + 1, …, n)

xij =

Modelli.52D. Vigo

Modello PLI

min Σi=1,n hi yi

Σi=1,j−1 xij + yj = 1 (j = 1, …, n)

Σj=i+1,n wj xij ≤ (K − wi) yi (i = 1, …, n)

yi ∈{0, 1} (i = 1, …, n)

xij ∈{0, 1} (i =1, …, n−1; j=i+1,…, n)