Formulazioni PLI di problemi di decisione

Dispensa per il modulo di“Analisi e Ottimizzazione dei Processi di Produzione”

Universita di Roma “Tor Vergata”

a cura di Andrea Pacifici∗, Claudio Cavalletti, Daniela Guerrucci

A.A. 2003-04

1 Introduzione: La formulazione dei problemi di

ottimizzazione combinatoria

Scopo di questa sezione1 e quello di introdurre il concetto di formulazione di un pro-blema di Ottimizzazione Combinatoria. Formalmente, un problema di OttimizzazioneCombinatoria (OC) e caratterizzato da un insieme di vettori S ⊆ 0, 1n (regione am-missibile) e da un vettore di costo c ∈ Rn. Ciascun vettore x ∈ S e detto soluzioneammissibile.

Il problema di (OC) consiste nell’individuare una soluzione ammissibile x∗ ∈ S incorrispondenza della quale la funzione lineare cT x assume un valore minimo, ovvero:

min cT x (1)

x ∈ S

Il vettore x∗ ∈ S e detto soluzione ottima. Osserviamo che, avendo l’insieme 0, 1n

cardinalita finita, anche l’insieme S e composto da un insieme finito di elementi. Ilformato dei problemi di Ottimizzazione Combinatoria rende agevole associare un modellomatematico a molti problemi reali in cui si voglia risolvere un problema di decisione, e inparticolare a problema nei quali si voglia scegliere in un insieme finito di alternative quellache consenta di massimizzare (minimizzare) una funzione obiettivo lineare di guadagno(costo).

∗Il testo di queste dispense e tratto —eccezion fatta per la Sezione 1 —dagli appunti di ClaudioCavalletti e Daniela Guerrucci per il corso di AOPP da me tenuto nell’A.A. 2003-04. Ringrazio, per ilprezioso aiuto, Daniela e Claudio e tutti coloro vorranno segnalarmi omissioni o errori: resta inteso chequesti ultimi sono da imputare soltanto al sottoscritto. A.P.

1Questo paragrafo e tratto integralmente dalla “Dispensa Integrativa del corso di Ricerca OperativaA.A. 1997-98 a cura di Gianpaolo Oriolo.

1

Variabili 0-1 consentono, infatti, di rappresentare l’appartenenza o meno di un ele-mento a un insieme finito, vincoli di tipo logico, strutture combinatorie quali i grafi e, piuin generale, l’espressione di alternative (e/o scelte) tra due o piu decisioni.

Il primo passo della associazione di un modello di (OC) a un problema di decisioneconsiste nel definire le variabili di decisione del problema in esame. Questo consente diassociare, in modo biunivoco, alle soluzioni di un problema di decisione i vettori di uninsieme S ⊆ 0, 1n. Alcuni esempi saranno utili a chiarire questo processo.

• Nel caso del problema del knapsack (zaino), se n e il numero di oggetti disponibili,e possibile associare ad ogni possibile scelta di oggetti un vettore x a valori 0-1 didimensione n: il valore 1 (0) della componente xi rappresenta il fatto che l’elementoi-esimo e presente (assente) nello zaino.

• Nel caso del problema del TSP, se n e il numero delle citta - e assunto senza perdi-ta di generalita che esista un collegamento tra ogni coppia di citta (l’assenza diun collegamento puo essere rappresentata con un collegamento di lunghezza moltogrande) - e possibile associare ad ogni tour un vettore x a valori 0-1 di dimensionen(n−1)

2(pari cioe al numero totale di collegamenti): il valore 1(0) della componente

xi rappresenta il fatto che un tour utilizza (non utilizza) il collegamento i.

• Nel caso del problema dell’assegnamento, se n e il numero di origini (destinazioni),e possibile associare ad ogni assegnamento un vettore x a valori 0-1 di dimensionen2: il valore 1 (0) della componente xi, associata alla coppia origine-destinazione(k, h), rappresenta il fatto che l’origine k e (non e) assegnata alla destinazione h.

• Nel caso del problema del massimo matching, se E e l’insieme degli archi, e possibileassociare ad ogni matching un vettore x a valori 0-1 di dimensione | E |: il valore 1(0) della componente xe rappresenta il fatto che l’arco e appartiene (non appartiene)al matching.

In generale, una volta definito il vettore x delle variabili di decisione, e immediatoscrivere la funzione obiettivo del problema in esame come prodotto scalare di x per ilvettore dei costi elementari c (normalmente un dato del problema). Nei casi esaminati,rispettivamente, gli elementi di c sono le utilita dei singoli elementi, le lunghezze dei col-legamenti, i costi delle coppie e infine, nel caso del massimo matching, tutti 1.

Una volta associato un problema di (OC), ovvero una coppia (S, c), con S ⊂ 0, 1n

e c ∈ Rn, a un problema di decisione, il successivo passo e quello di definire una formu-lazione lineare del problema (S, c).

Definizione Diciamo che un poliedro P ⊆ Rn e una formulazione lineare del problema(S, c) se e solo se:

S = P ∩ 0, 1n.

¤

2

L’insieme Qn = x ∈ Rn : 0 ≤ x ≤ 1 e detto n-Cubo Unitario. Allora, un poliedroe una formulazione lineare del problema (S, c) se e solo se la sua intersezione con Qn

coincide con S.Una formulazione lineare ci consente quindi di separare i vettori a componenti 0,1

che corrispondono alle soluzioni del nostro problema (i vettori che appartengono a S),dai vettori a componenti 0,1 che non corrispondono a soluzioni del nostro problema(i vettori che non appartengono a S). Naturalmente, la definizione di una formulazionelineare per un problema di (OC) conduce direttamente alla formulazione di un programmadi Programmazione Lineare Intera per il medesimo problema: e sufficiente aggiungere ivincoli di interezza sulle variabili. Viceversa, e facile verificare che tutti i programmi diProgrammazione Lineare Intera (PLI) descritti sono delle formulazioni per i corrispondentiproblemi di (OC) una volta eliminati (o, come si suol dire, “rilassati”) i vincoli di interezzasulle variabili.

In modo formale, se P e una formulazione lineare di un problema di (OC) (S, c),possiamo riscrivere il problema (S, c) nel modo seguente:

min cT x (2)

x ∈ P

x ∈ 0, 1n

Definizione Il problema di programmazione lineare:

min cT x (3)

x ∈ P

ottenuto eliminando i vincoli di interezza sulle componenti del vettore x viene dettorilassamento lineare del problema (2). ¤

Poiche la regione ammissibile del problema (1) contiene S, abbiamo che la soluzioneottima del problema x del rilassamento soddisfa la seguente relazione:

cT x ≤ min cT x : x ∈ S

ovvero, cT x fornisce una limitazione inferiore per il valore della soluzione ottima di OC.In particolare, se x appartiene all’insieme S (cioe se le componenti di x sono intere), allorae anche una soluzione ottima di (2); mentre, se x non appartiene a S ma esiste x′ ∈ Stale che cT x = cT x′, possiamo concludere che la soluzione x′ e ottima per (2).

Vogliamo qui sottolineare che per risolvere problemi di Programmazione Lineare (deltipo (1), cioe) esistono algoritmi efficienti sia dal punto di vista teorico (l’algoritmo del-l’ellissoide, per esempio) che dal punto di vista pratico (l’algoritmo del simplesso, peresempio). Quindi, la formulazione lineare di un problema di Ottimizzazione Combinato-ria consente di disporre rapidamente sia di condizioni (sufficienti) di ottimalita che di unbound per il valore della soluzione ottima (e quindi, nei casi fortunati in cui la soluzioneottima del rilassamento della formulazione sia intera, addirittura della soluzione ottima

3

del problema di partenza). Questo e particolarmente utile dal momento che l’Ottimiz-zazione Combinatoria rientra nella classe dei problemi NP-hard.

Evidentemente, ad un certo problema di OC possono essere associate diverse formu-lazioni lineari. Di conseguenza, ad ogni problema di tipo (1) possono essere associatidiversi problemi equivalenti di tipo (2) e quindi diversi rilassamenti lineari. La sceltadella formulazione di un problema (S, c) appare quindi di importanza decisiva nel deter-minare la qualita del “lower bound” e delle conseguenti condizioni di ottimalita appenadescritte. In particolare, date due diverse formulazioni P1 e P2 di un medesimo problema(S, c), diciamo che P1 e migliore di P2 se P1 ⊂ P2: cio garantisce che, qualunque sia ilvettore dei costi c, valga mincT x : x ∈ P2 ≤ mincT x : x ∈ P12.

E possibile affermare che esiste una formulazione ottima di un generico problema diOttimizzazione Combinatoria (S, c), ovvero una formulazione migliore, nel senso primaspecificato, di tutte le possibili formulazioni lineari di (S, c). Tale formulazione e costitui-ta, per definizione, dal poliedro contenuto in tutti i poliedri contenenti S, ovvero dall’in-volucro convesso dell’insieme S. E utile richiamare la definizione di insieme convesso eun importante teorema che caratterizza l’involucro convesso di un insieme finito di vettori.

Definizione Dato un insieme Y = y1, . . . , ym di m vettori di Rn, l’insieme involucroconvesso dell’insieme Y e definito nel seguente modo:

conv(Y ) = x ∈ Rn : x =∑

i=1...m

λiyi,

∑i=1...m

λi = 1,

0 ≤ λi ≤ 1, i = 1 . . .m¤

In altre parole, l’involucro convesso di Y , e l’insieme i cui elementi sono tutti e solii punti che possono essere espressi come combinazione convessa dei punti di Y . Se Y efinito, vale il seguente teorema.

Teorema (Weyl). Sia Y = y1, . . . , ym un insieme finito di m vettori di Rn. Alloraconv(Y ) e un poliedro, ovvero esiste un insieme finito di disequazioni Ax ≤ b tale checonv(Y ) = x ∈ Rn : Ax ≤ b con (A, b) a componenti razionali. ¤

Il teorema precedente consente di enunciare il prossimo teorema, di cui si omette la(semplice) dimostrazione.

Teorema Un problema di Ottimizzazione combinatoria (S, c) ammette sempre la for-mulazione lineare conv(S). Tale formulazione ha la proprieta che x ∈ S se e solo se x eun vertice di conv(S). ¤

2Date due diverse formulazioni P1 e P2 puo capitare che P1 6⊆ P2 e P2 6⊆ P1; in tal caso pero e possibileconsiderare P3 = P1 ∩ P2. Per definizione, P3 e una formulazione di (S, c), P3 ⊂ P1 e P3 ⊂ P2.

4

In altre parole, per ogni problema di (OC) esiste una formulazione (poliedro) che ha laproprieta che tutti i vertici sono interi. Questo risultato, tuttavia, e un risultato puramente“esistenziale”, non da cioe alcuna informazione su come individuare questo poliedro la cuiconoscenza sarebbe, viceversa, fondamentale. Esso infatti consentirebbe di risolvere unproblema di (OC), per sua natura discreto, per mezzo della Programmazione Lineare. Perfare cio, sarebbe sufficiente considerare il rilassamento lineare della formulazione ottima erisolvere il problema di tipo (1) utilizzando un algoritmo per la (PL) che, come l’algoritmodel simplesso, restituisca come soluzione ottima un vertice.

Purtroppo, in generale, il problema di determinare la formulazione ottima di un pro-blema di (OC) non e un problema di facile risoluzione. Esistono tuttavia problemi per iquali questa formulazione e nota; uno di questi e il problema dell’assegnamento. Infatti,per tale problema e disponibile una formulazione con la proprieta che tutti i suoi verti-ci sono interi (per la totale unimodularita della matrice) essa e quindi la formulazioneottima.

2 Formulazione di funzioni booleane

Presentiamo ora una interessante applicazione del concetto di formulazione lineare diun problema di Ottimizzazione Combinatoria: la formulazione di funzioni booleane. Unafunzione booleana f(x), con x ∈ 0, 1p, xT = (x1 . . . xp), e una qualunque applicazionef : 0, 1n −→ 0, 1. Essa puo essere espressa attraverso la sua tabella di verita, la qualeindica il valore assunto da f in corrispondenza ad ogni possibile valore delle variabilix1, . . . , xp. Una tabella di verita e costruita come segue.

Ciascun x ∈ 0, 1p puo essere fatto corrispondere ad un numero binario compreso tra0 e 2p − 1: denotiamo con x(i) il vettore di 0, 1p corrispondente al numero binario i,i = 1, . . . , 2p − 1. Una funzione booleana f(x) puo essere specificata fornendo il valorebinario che essa assume in corrispondenza a ciascuno degli x(i). Per esempio nella tabellaseguente e rappresentata una funzione di tre variabili (OR esclusivo):

x(i) x1 x2 x3 f(x(i))

0 0 0 0 01 0 0 1 12 0 1 0 13 0 1 1 04 1 0 0 15 1 0 1 06 1 1 0 07 1 1 1 0

Definizione Si definisce mintermine delle p variabili x1, . . . , xp una funzione che vale 1in corrispondenza di un solo valore dell’argomento x o, per dirla diversamente, di un solox(i). In particolare, il mintermine che assume valore 1 in corrispondenza di x(i) e chiamatomi. ¤

5

E facile vedere che un mintermine mi e dato dalla congiunzione (AND) di variabilidirette xj (o negate xj) a seconda che la variabile xj compaia con il valore 1 (oppure 0)nel vettore corrispondente x(i). Per esempio, il mintermine m4 (x(4) = (1 0 0)T )) e datoda:

m4 = x1 ∧ x2 ∧ x3

dove xj = 1− xj e il negato di una variabile booleana xj ∈ 0, 1.Una generica funzione puo essere scritta in forma analitica come OR dei mintermini

corrispondenti a quei valori di x(i) per cui essa vale 1. Pertanto la funzione booleanarappresentata nella precedente tabella puo scriversi come:

y = m1 ∨m2 ∨m4 = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3).

Questo significa che, data una qualunque funzione booleana, siamo in grado di darneuna descrizione utilizzando le sole funzioni AND e OR: questa osservazione ci torneraparticolarmente utile per “formulare” una qualunque funzione booleana.

2.1 Formulazione di funzioni AND e OR

Tutto cio premesso, vediamo come associare ad una funzione booleana f(x) ∈ 0, 1,x ∈ 0, 1p un opportuno sottoinsieme Sf dell’insieme 0, 1p+1: un vettore (x1, . . . , xn, xp+1)

(a valori 0-1) appartiene a Sf se e solo se xp+1 = f(x1, . . . , xp). E immediato verificare che| Sf |= 2p. D’altro canto, abbiamo visto che ogni formulazione lineare di un problema diOC consente di separare i punti a componenti 0-1 che rappresentano soluzioni ammissibilidel problema da quelli che non lo sono; in modo analogo e possibile definire una formu-lazione di una funzione booleana per separare i punti di Sf dai punti di 0, 1p+1 \ Sf .Naturalmente, in questo caso non ha senso definire una funzione obiettivo, cosı come,evidentemente, il concetto stesso di formulazione lineare e indipendente dalla definizionedi una funzione obiettivo.

Nel seguito illustriamo delle formulazioni lineari per le funzioni booleane AND e ORdi p variabili.

Attenzione: nelle formulazioni PLI, illustrate di seguito, sono sottintesi i box con-straints del tipo

0 ≤ x ≤ 1

per tutte le variabili x ∈ 0, 1 considerate nella formulazione. Questi vincoli fannonecessariamente parte delle formulazioni proposte.

2.1.1 AND

Si consideri la funzione booleana (AND di p variabili) del tipo:

y = x1 ∧ x2 ∧ . . . ∧ xp .

E necessario modellare le seguenti implicazioni:

6

(i) se esiste una variabile nulla tra le xi, i = 1, . . . , p, allora y = 0 (nella soluzioneintera);

(ii) se tutte le variabili xi sono pari a 1, i = 1, . . . , p, allora y = 1 (nella soluzione intera).

Per quanto riguarda l’implicazione (i) e sufficiente scrivere:

y ≤ 1

p

p∑i=1

xi (4)

Evidentemente, non appena una delle p variabili e pari a 0, allora∑p

i=1 xi ≤ p equindi y < 1 cioe y = 0 nella soluzione intera. Viceversa, se per tutti gli i = 1, . . . , p,xi = 1, si ha che y ≤ 1, vale a dire y e libera di assumere i valori 0 e 1 nella soluzioneintera.

L’implicazione (ii) si puo scrivere come segue:

y ≥p∑

i=1

xi − (p− 1) (5)

In questo caso, se tutte le variabili xi, i = 1, . . . , p, sono pari a 1, allora il membrodestro della diseguaglianza e pari a 1 e si ha y ≤ 1 e quindi (nella soluzione intera) y = 1.Viceversa, se esiste una xi = 0, si ha immediatamente y ≥ ε con ε ≤ 0, quindi y di fattoe libera.

La formulazione completa e costituita dalle diseguaglianze (4) e (5), oltre che dai boxconstraints.

Questo non e l’unico approccio possibile. A titolo di esempio si da una formulazionealternativa per la implicazione (i), per un AND di 4 variabili, che prevede tuttavia diutilizzare 4 diseguaglianze in luogo di 1.

y ≤ x1

y ≤ x2

y ≤ x3

y ≤ x4 (6)

La formulazione completa e in questo caso data dalle diseguaglianze (6) e (5), oltreche dai box constraints.

2.1.2 OR

Analogamente si puo dare una formulazione della funzione booleana (OR di p variabili)del tipo:

y = x1 ∨ x2 ∨ . . . ∨ xp .

E necessario modellare le seguenti implicazioni:

(i) se esiste una variabile pari a 1 tra le xi, i = 1, . . . , 3, allora (nella soluzione intera)y = 1;

7

(ii) se tutte le variabili xi sono pari a 0, i = 1, . . . , p, allora (nella soluzione intera)y = 0.

Per quanto riguarda l’implicazione (i) e sufficiente scrivere:

y ≥ 1

p

p∑i=1

xi (7)

Evidentemente, non appena una delle p variabili e pari a 1, allora∑p

i=1 xi > 0 e quindiy > 0 cioe y = 1. Viceversa, se per tutti gli i = 1, . . . , p, xi = 0, si ha che y ≤ 1, vale adire y e libera (nella soluzione intera) di assumere i valori 0 e 1.

L’implicazione (ii) si puo scrivere come segue:

y ≤p∑

i=1

xi (8)

In questo caso, se tutte le variabili xi, i = 1, . . . , p, sono pari a 0, allora il membrodestro della diseguaglianza e pari a 0 e si ha y ≤ 0 e quindi (nella soluzione intera) y = 0.Viceversa, se esiste una xi = 1, si ha immediatamente y ≤ ε con ε ≥ 1, quindi y di fattoe libera.

La formulazione completa e costituita dalle diseguaglianze (7) e (8), oltre che dai boxconstraints.

Anche per l’OR, quello presentato non e l’unico approccio possibile. A titolo di esempiosi da una formulazione alternativa per l’implicazione (i), per un OR di 4 variabili, cheprevede tuttavia di utilizzare 4 diseguaglianze in luogo di 1.

y ≥ x1

y ≥ x2

y ≥ x3

y ≥ x4 (9)

La formulazione completa e in questo caso data dalle diseguaglianze 9 e 5 (oltre chedai box constraints.)

2.1.3 Formulazione di funzioni booleane generiche

Vediamo ora come formulare una generica funzione booleana espressa in forma ana-litica come OR di mintermini. Faremo riferimento alla funzione che abbiamo utilizzatocome esempio per illustrare il procedimento.

y = m1 ∨m2 ∨m4 = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) .

Innanzitutto vediamo come formulare la negazione di una variabile booleana x ∈0, 1. Sia dunque 0, 1 3 y = x. E sufficiente scrivere banalmente

y = (1− x) (10)

8

per esprimere la relazione logica.

L’idea consiste nell’utilizzare una variabile booleana di appoggio αi ∈ 0, 1 per ognimintermine che compare nell’espressione della funzione. Nel caso in esame, si introduconotre variabili binarie α1, α2 e α4 relative ai tre mintermini m1, m2 e m4. Si vuole checiascuna variabile αi sia pari a 0 [1] quando il corrispondente mintermine mi assumevalore 0 [1]. Pertanto porremo:

α1 = x1 ∧ x2 ∧ x3

α2 = x1 ∧ x2 ∧ x3

α4 = x1 ∧ x2 ∧ x3 (11)

Le tre relazioni logiche 11 possono essere facilmente formulate utilizzando la formu-lazione (si vedano le diseguaglianze (4) e (5)) per l’AND delle variabili x3 e per i negati (siveda la relazione (10)) delle variabili x1 e x2. Si ottengono in tal modo 6 diseguaglianzeche legano le variabili αi, i = 1, 2, 4 e xj (eventualmente negate (1− xj), j = 1, 2, 3.)

A questo punto non si deve fare altro che esprimere la variabile y come OR dellevariabili αi per ottenere la formulazione desiderata:

y = α1 ∨ α2 ∨ α4 .

Utilizzando le 2 diseguaglianze (7) e (8) siamo in grado facilmente di formulare talerelazione e, in conclusione, di dare una formulazione lineare per la funzione booleanay = f(x1, x2, x3).

E ovvio estendere la procedura appena illustrata ad una qualunque funzione booleana.Si noti tuttavia che il numero di variabili ausiliarie e il numero di diseguaglianze chedobbiamo utilizzare e direttamente proporzionale al numero di mintermini che compaiononell’espressione analitica e quindi, nel caso peggiore, dell’ordine di O(2p).

3 Formulazione PLI di relazioni diverse

In questa sezione affrontiamo il problema di formulare come PLI diversi problemi didecisione che, per le loro caratteristiche, costituiscono degli esempi notevoli per classi piugenerali di problemi. Essere in grado di formulare come PLI tali problemi di decisionecostituisce uno strumento di notevole utilita per affrontare problemi di decisione piugenerali.

Osserviamo, innanzitutto, che, per un generico problema di programmazione matema-tica, si ha che:

minf(x) t.c. x ∈ Ω = −max−f(x) t.c. x ∈ Ω,

con Ω ⊆ Rn.Senza perdita di generalita ci riferiremo dunque ai problemi di minimo:

minf(x) t.c. x ∈ Ω. (12)

9

In particolare siamo interessati a problemi in cui le variabili decisionali possono assumeresolo valori interi:

minf(x) t.c. x ∈ P, x ∈ Zn, (13)

e P e un poliedro di Rn.

3.1 Funzioni obiettivo di tipo min max, (max min)

In molti casi, ci puo porre il problema di dover linearizzare una funzione obiettivodella forma:

f(x) = maxg1(x), g2(x), . . . , gq(x) (14)

con gi : Rn −→ R, per 1 ≤ i ≤ q, funzioni lineari di n variabili. Questo, per esempio,consentirebbe di formulare il Problema (13) come problema di PLI.

Un modo di procedere e il seguente: si consideri il problema

minz t.c. z ≥ gi(x), i = 1, . . . , q, x ∈ Ω. (15)

Il Problema (15) e evidentemente equivalente al Problema (12), con f(x) del tipo (14), equindi, se valgono in particolare le restrizioni su Ω = P ∩ Zn, allora puo essere formulatocome problema di PL o PLI.

E immediato osservare che, se il problema e quello di massimizzare una funzionef ′(x) = ming1(x), g2(x), . . . , gq(x), possiamo procedere esattamente in modo analogoponendo pero , questa volta, z ≤ gi(x), i = 1, . . . , q.

Una applicazione di questa procedura e data dalla seguente:

3.1.1 Formulazione PLI di funzioni obiettivo modulo

Si consideri dunque il Problema (13), in cui la funzione da minimizzare e f(x) = | g(x)|,dove g : Rn −→ R. Tale funzione e , evidentemente, non lineare. Osservando che:

| g(x)| = maxg(x),−g(x)

e applicando la procedura descritta sopra, otteniamo la formulazione equivalente:

minz t.c. z ≥ g(x), z ≥ −g(x), x ∈ P, x ∈ Zn

(eventualmente, se g(x) e lineare, tale problema e un PLI.)

Si badi al fatto che non e affatto ovvio formulare il problema di massimizzare una fun-zione modulo: in tal caso, non si puo utilizzare l’equivalenza max|f(x)| = −min−|f(x)|,che e vera ma che non consente di sfruttare le considerazioni fatte sopra. Infatti, minimiz-zare−maxf(x),−f(x) non e lo stesso problema della minimizzazione di maxf(x),−f(x).Tuttavia e possibile formulare max|f(x)| utilizzando opportunamente una variabile bi-naria, come vedremo nel seguito.

10

3.2 Costi fissi

Caso 1 Si consideri il Problema (13), con una funzione obiettivo (di costo) del tipo:

f(x) =n∑

j=1

gj(xj) , gj(x) =

0 se xj = 0,bj + ajxj se xj > 0

(16)

con aj, bj ≥ 0 dati.Utilizzando delle variabili intere αj ∈ 0, 1, j ∈ 1, . . . , n, siamo in grado di for-

mulare tale problema, altrimenti non lineare, come PLI. Dobbiamo esprimere la seguentedoppia implicazione:

- se xj = 0, desideriamo che αj = 0,

- se xj > 0, si vuole che αj = 1.

In questo modo, ponendo f(x) =∑n

j=1 ajxj+bjαj siamo in grado di esprimere la funzioneobiettivo come funzione lineare delle xj e αj .

A tale scopo e sufficiente scrivere le seguenti diseguaglianze:

Mαj ≥ xj j ∈ 1, . . . , n

dove M e un numero “sufficientemente grande”3. Come si vede, αj e forzato ad assumerevalori positivi (α = 1) non appena xj > 0. Viceversa, se xj = 0 si ha che α e libera(in altre parole abbiamo formulato solo la seconda delle due implicazioni su indicate):tuttavia, poiche la funzione obiettivo deve essere minimizzata e bj > 0, in assenza di altrivincoli, αj assumera valore pari a 0.

Caso 2 Una situazione piu complessa si ha quando si debba minimizzare una funzioneobiettivo dove, in luogo delle relazioni (16), si ha:

f(x) =n∑

j=1

gj(xj) , gj(xj) =

0 se xj = 0dj + ajxj se 0 < xj ≤ xj

fj + ajxj se xj > xj

(17)

con fj > dj .Una funzione obiettivo di questo tipo puo descrivere, ad esempio, la struttura dei

costi di un sistema produttivo a capacita limitata. Il valore x potrebbe corrispondere allacapacita massima dell’impianto: per produrre una quantita x > x e necessario ampliarel’impianto (o costruirne un altro), con conseguente aumento dei costi fissi.

Per formulare il problema (17) si puo procedere nel modo seguente. La nostra funzioneobiettivo sara:

f(x) =n∑

j=1

ajxj + dj αj + (fj − dj)βj , αj, βj ∈ 0, 1

3vale a dire, per cui ogni valore ammissibile di xj e non superiore ad M . In generale, tale valore nonesiste. Viceversa, esiste sempre se il Problema (13) e limitato.

11

dove per αj e βj devono valere le seguenti implicazioni:

(i) xj > 0 ⇒ αj = 1(ii) xj > xj ⇒ βj = 1

In questo modo, il termine di costo dj sara considerato solo per 0 < xj, e il termine(fj − dj) solo per xj > xj. Si noti che, per xj > xj, si avra αj = βj = 1, cioe entrambei termini vengono sommati nella funzione obiettivo, e i costi fissi risultano pari a: dj +(fj − dj) = fj .

Caso 3 Un terzo caso di struttura dei costi puo essere il seguente:

f(x) =n∑

j=1

gj(xj) , gj(xj) =

0 se xj = 0dj + ajxj se 0 < x ≤ xfj + cjxj se x > x

(18)

Supponiamo inoltre che valgano le seguenti relazioni:

0 < aj < cj , ajxj + dj = cjxj + fj j ∈ 1, .., n

Si vede facilmente che le funzioni gj(x) sono continue e che vale anche: fj < dj .

Se consideriamo per semplicita il caso dj = 04, possiamo riscrivere le funzioni di costogj(x) nel seguente modo:

gj(xj) = max (ajxj + dj), (cjxj + fj). (19)

Il problema e dunque riconducibile alla minimizzazione di una funzione di massimo.La formulazione sara quindi analoga alla (15):

min f(x) =∑n

j=1 gj(xj) : gj(xj) ≥ ajxj + dj ,

gj(xj) ≥ cjxj + fj ,j ∈ 1, .., n ,x ∈ Ω .

(20)

Si consideri adesso il caso dj > 0. La formulazione precedente non e corretta poiche nelpunto xj = 0 si ottiene un valore di costo non nullo. Per ovviare a cio occorre modificareleggermente la formulazione (20), rendendola generale:

min f(x) =∑n

j=1 gj(xj) : gj(xj) ≥ ajxj + dj − dj αj ,

gj(xj) ≥ cjxj + fj − fj αj ,M(1− αj) ≥ xj ,M(xj) ≥ (1− αj) ,j ∈ 1, .., n ,x ∈ Ω ,

(21)

4Nel caso dj > 0, l’espressione riportata non e valida nel punto xj = 0, in cui si dovrebbe avere costonullo.

12

dove M e una costante definita come in precedenza (Big M ). Rispetto al caso precedente,sono stati aggiunti il terzo e il quarto vincolo, in modo che, quando xj = 0, risulti:

x = 0 ⇒ α = 1 ,

dal quarto vincolo. In questo modo, quando xj = 0, i primi due vincoli diventano:

gj(0) ≥ dj − dj = 0 ,gj(0) ≥ fj − fj = 0 ,

e, minimizzando, si avra proprio gj = 0, come si voleva. Inoltre, dal terzo vincolo segueche, quando x > 0 :

x > 0 ⇒ α = 0 ,

e i primi due vincoli assumeranno la forma (20) vista nel caso precedente.

3.3 Implicazioni

Nella formulazione PLI di molti problemi decisionali puo rendersi necessario l’utilizzodi una doppia implicazione del tipo seguente:

α = 1 ⇔ aT x ≤ b, α ∈ 0, 1, x ∈ Rn . (22)

Utilizzando le tecniche viste fin qui per implicazioni piu semplici, siamo in grado diformulare la relazione (22). Si consideri innanzitutto la prima implicazione:

α = 1 ⇒ aT x ≤ b, (23)

che puo essere definita per mezzo di una costante M sufficientemente grande5 (Big M),in modo analogo a quanto si e visto nel paragrafo 3.2:

aT x ≤ b + M(1− α). (24)

In questo modo, quando α = 1, deve valere aT x ≤ b, mentre se α = 0, il vincolo ebanalmente soddisfatto.

Passiamo quindi alla seconda implicazione:

α = 1 ⇐ aT x ≤ b. (25)

Ricordando che la relazione (A ⇒ B) e equivalente alla relazione (B ⇒ A), possiamoriscrivere nel modo seguente la (25):

α = 0 ⇒ aT x > b . (26)

5cioe deve esistere M tale che, per ogni x ammissibile, valga: aT x ≤ M

13

La forma ottenuta e piu “familiare”, in quanto utilizza una variabile binaria perforzare una disuguaglianza, tuttavia e non lineare a causa del vincolo che deve valere“strettamente”. La relazione che si vuole utilizzare e analoga alle precedenti:

Mα + aT x > b , (27)

in modo che, quando α = 0, deve valere la disuguaglianza aT x > b, mentre se α = 1 ilvincolo e soddisfatto banalmente. Rimane pero da aggirare l’ostacolo della non linearitadel vincolo.

Supponiamo che (b + ε) sia il piu piccolo valore che l’espressione (M + aT x) puoassumere quando (M + aT x > b). Possiamo quindi riscrivere la disuguaglianza stretta inquesto modo:

Mα + aT x ≥ b + ε , (28)

e, di conseguenza, sara rispettato anche il vincolo non lineare:

M + aT x ≥ b + ε > b .

In definitiva, la doppia implicazione iniziale:

α = 1 ⇔ aT x ≤ b ,

con α ∈ 0, 1, puo essere formulata utilizzando due disuguaglianze lineari del tipo:

aT x ≤ b + M(1− α),

Mα + aT x ≥ b + ε ,(29)

Un secondo tipo di implicazione, piu complesso da formulare, e il seguente:

α = 1 ⇔ aT x = b . (30)

Utilizzando due variabili binarie di appoggio, il problema puo essere scomposto in dueimplicazioni piu semplici, la cui formulazione e gia nota:

β = 1 ⇔ aT x ≤ b,

γ = 1 ⇔ aT x ≥ b ,(31)

con α = β ∧ γ .

14

Le due implicazioni sono del tipo (22) e ciascuna puo essere formulata con due dis-equazioni lineari, come visto in precedenza. La variabile α e ottenuta come funzionebooleana AND delle variabili β e γ, e puo essere formulata nel modo seguente6:

α ≤ 1

2(β + γ),

α ≥ (β + γ)− 1 .

(32)

In questo modo si avra:

(i) Se α = 1, per la relazione di AND anche β e γ saranno pari a 1, e, di conseguenza,valgono entrambe le implicazioni (31):

β = 1 ⇒ aT x ≤ b

γ = 1 ⇒ aT x ≥ b⇒ aT x = b .

Quindi: (α = 1) ⇒ (aT x = b) .

(ii) Se (aT x = b), le implicazioni (31) danno:

aT x ≤ b ⇒ β = 1

aT x ≥ b ⇒ γ = 1⇒ α = β ∧ γ = 1 .

E quindi vale anche l’implicazione inversa: (aT x = b) ⇒ (α = 1) .

3.3.1 Massimizzazione di funzioni obiettivo modulo

Nel paragrafo 3.1.1 si e ottenuta la formulazione per il problema di minimizzazione difunzioni obiettivo modulo:

f(x) = | g(x)| , con g : Rn −→ R

Il problema che adesso ci proponiamo di formulare e la massimizzazione di funzioniobiettivo dello stesso tipo:

max |f(x)| con x = (x1, ..., xn) . (33)

Per semplicita utilizzeremo in seguito la notazione f in luogo di f(x). Poiche perdefinizione di funzione modulo si ha:

6si veda il paragrafo 2.1.1.

15

z = |f(x)| =

f se f > 0 ,−f se f < 0 ,

possiamo riscrivere il problema (33) nel modo seguente:

max zt.c.

z ≤ f se f > 0 ,z ≤ −f se f < 0 ,

(34)

Dalla massimizzazione della funzione obiettivo z segue che, se f > 0, si massimizzeraproprio f , mentre se f < 0 , si massimizzera −f .

Un modo per formulare il problema (34) e il seguente:

max zt.c.

(i) z ≤ f + Mα,(ii) z ≤ −f + M(1− α),(iii) M(1− α) ≥ f,(iv) Mα ≥ −f,

α ∈ 0, 1,

nel quale α e una variabile booleana di appoggio tale che (terzo e quarto vincolo):

(iii) f > 0 ⇒ α = 0 ,(iv) f < 0 ⇒ α = 1 .

Di conseguenza, per i primi due vincoli avremo:

(i) f > 0 ⇒ α = 0 ⇒ z ≤ f ,(ii) f < 0 ⇒ α = 1 ⇒ z ≤ −f ,

cioe si e ottenuta una formulazione per il problema (34). Si noti che, nel caso particolaref = 0, α puo assumere entrambe i valori 0, 1. In entrambe i casi tuttavia, il risultato ecorretto. Infatti, se α = 0:

(i) α = 0 ⇒ z ≤ f = 0 ,

e il secondo vincolo e banale; se α = 1:

(ii) α = 1 ⇒ z ≤ −f = 0 .

e il primo vincolo e banalmente soddisfatto.

16

3.4 Vincoli disgiuntivi

Si consideri il seguente problema di scheduling (sequenziamento di operazioni):

- n lavorazioni (job) da effettuare, con tempo di processamento: pj , j ∈ 1, . . . , n- 1 macchina per effettuare le lavorazioni (problema single-machine)

- lavorazioni non interrompibili (non-preemptive).

Se definiamo tempo di completamento Cj l’istante in cui termina la lavorazione del jobj, l’obiettivo del problema sara la minimizzazione di una certa funzione lineare dei tempidi completamento:

min f(C1, C2, . . . , Cn) .

Per il tempo di completamento del job j, essendo il problema non-preemptivo, vale larelazione:

Cj = Sj + Pj ,

dove Sj e l’istante di inizio (starting-time) della lavorazione e Pj il tempo di processamentodel job. Naturalmente deve valere anche: Sj , Pj , Cj ≥ 0 .

Il problema considera una sola macchina per le n lavorazioni, di conseguenza dovremoincludere nella formulazione un vincolo che permetta la lavorazione di un solo job allavolta. Le implicazioni di cui abbiamo bisogno sono le seguenti:

se i precede j ⇒ Sj ≥ Ci = Si + Pi ,se j precede i ⇒ Si ≥ Cj = Sj + Pj ,

cioe, se il job i precede il job j, allora quest’ultimo non potra iniziare prima dell’istantedi completamento del job i, e viceversa se j precede i .

Per ottenere le implicazioni possiamo definire le variabili binarie yij :

yij =

1 se i precede j ,0 se j precede i ,

1 ≤ i < j ≤ n ,

e imporre che:

y = 1 ⇒ Sj ≥ Ci ,y = 0 ⇒ Si ≥ Cj .

(35)

Le precedenti due implicazioni si traducono facilmente in vincoli lineari utilizzando lecostanti Big M, come gia visto nei paragrafi precedenti:

M yij + Si ≥ Sj + Pj ,M (1− yij) + Sj ≥ Si + Pi ,

1 ≤ i < j ≤ n . (36)

17

I vincoli di sequenziamento (36) sono detti vincoli disgiuntivi. Si noti che sia per levariabili yij, sia per tali vincoli e sufficiente considerare le coppie non ordinate di job i, j(quindi, per esempio imponendo che i < j.) In altre parole, se i < j, si utilizza solo lavariabile yij (e non yji)

7.La formulazione del problema e quindi la seguente:

min f(C1, C2, . . . , Cn)t.c.

M yij + Si ≥ Sj + Pj , 1 ≤ i < j ≤ n ,M (1− yij) + Sj ≥ Si + Pi , 1 ≤ i < j ≤ n ,yij ∈ 0, . . . , 1 , 1 ≤ i < j ≤ n .Sj, Cj ∈ R+, j ∈ 0, . . . , n ,

(37)

7Alternativamente, si possono utilizzare tante variabili booleane quante sono tutte le coppie ordinate(i, j) , e il numero totale di variabili booleane utilizzate diviene pari a n2 , (scelte non ordinate di dueelementi in un insieme di n) potendo cosı utilizzare, nei vincoli 36, M yji in luogo di M (1−yij). Avremoquindi sia yij che yji e dovra valere l’ovvia relazione:

yij + yji = 1 , ∀ i, j ∈ 1, . . . , n.

18

Esercizi svolti

Esercizio 1 - Assegnamento con costi “part transfer”.Un insieme N di n operazioni, deve essere eseguito su un insieme di m macchine M .In particolare, ogni operazione i ∈ N puo essere eseguita su una sola macchina del sot-toinsieme dato ∅ 6= Ni ⊆ M . Tra le operazioni sussistono delle relazioni di precedenza(i, j) ∈ A, con i, j ∈ N, ad esempio, in corrispondenza di una i ∈ N con |δ−(i)| > 1si ha un’operazione di assemblaggio e in corrispondenza di una i ∈ N con |δ+(i)| > 1 siha un’operazione di suddivisione di un lotto o di smontaggio di parti. Ogniqualvolta siassegnano due operazioni i e j, per cui (i, j) ∈ A, a due macchine distinte si paga un costodi setup sij > 0 (nullo nel caso in cui i e j siano assegnate alla stessa macchina).

Formulare come PLI il problema di determinare l’assegnamento di costo minimo delleoperazioni alle macchine.N.B. Si possono assegnare piu operazioni alla stessa macchina. Le operazioni non sonointerrompibili.

Soluzione

I dati del problema sono i seguenti:

- Insieme delle operazioni da svolgere: N = 1, 2, . . . , n- Insieme delle relazioni di precedenza: A = (i, j) i, j ∈ N.- Insieme delle macchine: M = M1,M2, . . . , Mm. Per ogni macchina e definito

inoltre l’insieme delle operazioni che la macchina e in grado di svolgere: Ni ⊆ N .

Inoltre, la funzione obiettivo deve tener conto dei costi di part transfer, in cui si incorreogniqualvolta si assegna una coppia di operazioni dell’insieme A (cioe operazioni comeassemblaggi e suddivisioni, tra cui sussistono relazioni di precedenza) a due macchinedifferenti.

Per formulare i vincoli di assegnamento si possono utilizzare le variabili booleane xij :

xij =

1 se l’operazione j e assegnata alla macchina i ,0 altrimenti ,

i ∈ M, j ∈ N.

Ogni operazione j deve essere assegnata ad una sola macchina i. Se definiamo l’in-sieme Fj = i : j ∈ Ni delle macchine che possono svolgere l’operazione j, il vincolo puoessere scritto nel modo seguente:

∑

Mi ∈ Fj

xij = 1 , (38)

sommando le variabili di assegnamento xij per tutte le macchine dell’insieme Fj .

19

Per considerare il problema dei part transfers tra le operazioni dell’insieme A , sipossono definire le variabili booleane yjk:

yjk =

1 se le operazioni j e k sono assegnate a macchine diverse ,0 se le operazioni j e k sono assegnate alla stessa macchina ,

(j, k) ∈ A.

In questo modo, la funzione obiettivo sara semplicemente la somma pesata di talivariabili, che “contano” il numero di volte in cui si sono assegnate coppie di operazionidell’insieme A a macchine diverse:

F.O. min∑

(j, k) ∈ A

sjk yjk (39)

Per forzare le yjk ad assumere i valori desiderati, si puo procedere nel modo seguente.

Si consideri la variabile y(i)

jk , relativa alla macchina Mi:

y(i)

jk = xji XOR8 xki ∀ (jk) ∈ A, ∀i ∈ M. (40)

xji xki y(i)

jk

0 0 01 0 10 1 11 1 0

Come si vede dalla tabella di verita, tale variabile assume valore 1 solo in due casi:

(i) xji = 0 e xki = 1 ,(i) xji = 1 e xki = 0 ,

cioe se solo una delle operazioni j, i e assegnata alla macchina Mi . Se su almeno una dellemacchine Mi cio avviene, allora le operazioni j, k sono state assegnate a due macchinedifferenti, e si dovra forzare la variabile yjk ad assumere il valore 1:

Se ∃ i ∈ M : y(i)

jk = 1 ⇒ yjk = 1 .

Per formulare l’implicazione precedente si possono utilizzare i semplici vincoli:

yjk ≥ y(i)

jk ∀i ∈ M. (41)

8la funzione booleana XOR di n variabili booleane puo essere formulata in vari modi. Una formulazionestandard puo essere ottenuta utilizzando i mintermini (vedi paragrafo 2). Ricordiamo che un minterminee dato dalla congiunzione (AND) di variabili xi dirette o negate. Se definiamo il mintermine mi in modoche esso assuma il valore 1 quando xi e pari a 1 e tutte le altre variabili sono pari a 0, allora la funzionebooleana XOR (x1, x2, . . . , xn) si ottiene come semplice funzione OR dei mintermini m1,m2, . . . , mn. Ilnumero di vincoli lineari necessari in questo caso e pari: 2 per ciascun mintermine (e un AND di variabilibooleane), piu 2 per l’OR dei mintermini, in totale: 2n + 2.

20

Esercizio 2 - Sequenziamento.Un insieme J = 1, . . . , n di n operazioni con tempi di processamento p1, . . . , pn deveessere eseguito da un’unica macchina, che puo svolgere un’operazione alla volta, in modonon preemptivo. Per ciascuna operazione e noto un’istante di rilascio rj (release date),prima del quale non si puo iniziare a lavorare il job j. I costi di lavorazione sono funzionedel tempo di completamento, in particolare, per la generica operazione j:

Ej(Cj) =

ACj + f se Cj ≤ aj ,ACj + g se aj < cj ≤ bj ,ACj + h se cjx > bj ,

con 0 < f < g < h.

Formulare come PLI il problema di determinare il sequenziamento di costo minimodelle operazioni.

Soluzione

Scriviamo innanzitutto il vincolo sugli istanti di rilascio:

Sj ≥ rj ∀j ∈ J, (42)

dove Sj e l’istante di inizio della lavorazione del job j. In questo modo tutte le releasedate saranno rispettate. Per formulare la funzione obiettivo si procede in modo analogoa quanto visto nel paragrafo 3.2 sui costi fissi. Se definiamo due variabili binarie αj , βj

che si comportano nel modo seguente:

Cj > aj ⇒ αj = 1 ,Cj > bj ⇒ βj = 1 ,

(43)

allora le funzioni di costo possono essere riscritte cosı:

Ej(Cj) = ACj + f + (g − f) αj + (h− g)βj , (44)

e la funzione obiettivo sara semplicemente la somma di queste funzioni:

F.O. min∑

j ∈ J

Ej(Cj) (45)

I vincoli (43) possono essere scritti in forma lineare utilizzando una costante Big M :

Cj − aj ≤ Mαj ,Cj − bj ≤ Mβj ,

∀j ∈ J . (46)

2 Si noti che non ci siamo occupati del comportamento di αj per Cj < aj (e diβj per Cj < bj). In questo modo le variabili rimangono libere di assumere entrambe i

21

valori 0, 1. Tuttavia e sufficiente formulare un solo verso dell’implicazione, in quanto vale:0 < f < g < h (cioe i costi fissi sono crescenti) e, per minimizzare la funzione di costo,αj e βj saranno comunque poste pari a 0. Se cosı non fosse, sarebbe necessario formulareentrambe i versi dell’implicazione:

Cj > aj ⇔ αj = 1 ,Cj > bj ⇔ βj = 1 ,

(47)

Si consideri infatti il caso f > g : se αj non fosse vincolata, assumerebbe il valore1 anche per Cj < aj , poiche risulterebbe conveniente pagare g piuttosto che f . Con ilvincolo (47), invece, α dovrebbe assumere il valore 0, poiche Cj < aj , e si avrebbe ilvalore corretto per i costi fissi: f .

¤

I vincoli di sequenziamento che dobbiamo formulare sono i seguenti:

se i precede j ⇒ Sj ≥ Ci = Si + Pi ,se j precede i ⇒ Si ≥ Cj = Sj + Pj ,

Come in precedenza, possiamo utilizzare le variabili binarie yij :

yij =

1 se i precede j ,0 se j precede i ,

1 ≤ i < j ≤ n , (48)

M yij + Si ≥ Sj + Pj ,M (1− yij) + Sj ≥ Si + Pi ,

1 ≤ i < j ≤ n . (49)

I vincoli precedenti completano la formulazione. Per concludere, riassumiamo levariabili utilizzate:

Sj, Cj ∈ R+, j ∈ J,αj, βj ∈ 0, 1 , i, j ∈ J.

22

Esercizio 3 - Sequenziamento con 2 utenti.Due utenti (A e B) di una cella di lavorazione devono accordarsi su come utilizzare talerisorsa (la cella).

L’utente A deve processare un insieme di job JA1 , . . . , JA

m i cui tempi di processamentosono rispettivamente pA

1 , . . . , pAm. Analogamente, l’utente B deve processare un insieme di

job JB1 , . . . , JB

n i cui tempi di processamento e due date sono rispettivamente pB1 , . . . , pB

m

e dB1 , . . . , dB

m.A desidera minimizzare la somma pesata (con pesi w1, . . . , wm) dei tempi di comple-

tamento dei suoi job. B si contenta di qualunque soluzione purche non abbia piu di ` jobin ritardo (un job JB

i e in ritardo se il suo tempo di completamento eccede la due datedB

i ).Si richiede di formulare come PLI il problema di decidere gli istanti di partenza dei

job di A e B in modo da soddisfare le specifiche dei due utenti.

Soluzione

Definiamo innanzitutto gli obiettivi dei due utenti:

- l’utente A desidera minimizzare la somma pesata dei tempi di completamento deipropri job; la sua funzione obiettivo risultera dunque:

min∑

j ∈ JA

CAj wj ,

- l’utente B desidera avere, al piu, l job in ritardo, ovvero per cui risulti: CBj > dB

j .

In questo caso possiamo considerare l’obiettivo di A come funzione obiettivo del nostroproblema e l’obiettivo di B come uno dei vincoli che la soluzione ottenuta dovra soddisfare.

Per formulare il problema utilizziamo n + m variabili Sj ∈ R+:

S1, S2, ..., Sn ,︸ ︷︷ ︸Starting T ime j ∈ JA

Sn+1, Sn+2, ..., Sn+m ,︸ ︷︷ ︸Starting T ime j ∈ JB

delle quali le prime n sono relative ai tempi di inizio delle lavorazioni dei job JA, e lerestanti m ai job JB.

La funzione obiettivo sara quindi data dalla somma pesata dei tempi di completamentodei job di A (sono i primi n job), che possiamo scrivere come:

F.O. minn∑

j=1

wj(Sj + pj) (50)

I vincoli che la soluzione del problema dovra soddisfare sono:

23

- Vincoli di sequenziamento:

M yij + Si ≥ Sj + pj ,M (1− yij) + Sj ≥ Si + pi ,

1 ≤ i < j ≤ n + m, (51)

ottenuti introducendo le variabili booleane yij:

yij =

1 se i precede j ,0 se j precede i ,

1 ≤ i < j ≤ n + m .

- Vincolo sul numero di job JB in ritardo.

Per formulare tale vincolo possiamo introdurre delle variabili booleane αj che fun-zionino da contatore per il numero di job JB in ritardo:

αj =

1 se il job j e in ritardo,0 altrimenti,

n + 1 ≤ j ≤ n + m.

Affinche le variabili αj si comportino in questo modo, dovra valere:

Cj > dj ⇒ αj = 1 n + 1 ≤ j ≤ n + m,

che tradotto in vincoli lineari diventa:

Cj − dj ≤ Mαj n + 1 ≤ j ≤ n + m. (52)

Il numero di job JB in ritardo e ovviamente dato da:∑n+m

j=n+1 αj , per cui il vincoloche conclude la formulazione risultera:

n+m∑j=n+1

αj ≤ l . (53)

24

Esercizio 4 - Produzione di 2 prodotti con vincolo “best before date”.Si consideri un problema di pianificazione della produzione con T periodi; due tipi diprodotto A e B; domande date DA

t (per il prodotto A) e DBt (per il prodotto B) per tutti

gli t = 1, . . . , T ; funzioni lineari di costo di produzione e di stoccaggio del periodo t, Ct(·)e Ht(·) date per ogni t = 1, . . . , T .

Si puo produrre un solo tipo di prodotto per periodo ed esiste un vincolo di tipo “best-before-date” per cui la domanda al periodo t (quale che sia il tipo di prodotto) deve esseresoddisfatta con la produzione dello stesso periodo t o del precedente periodo t− 1.

Formulare come programmazione lineare intera il problema di determinare il piano diproduzione di costo minimo.

Soluzione

Le variabili del problema sono le seguenti:

- x it ∈ R+ , i = A,B : livello di produzione nel periodo t per il prodotto i

- s it ∈ R+ , i = A,B : livello di scorte nel periodo t per il prodotto i

Con queste variabili possiamo gia scrivere la funzione obiettivo del problema:

F.O. minT∑

t=1

∑i=A, B

[Ct(x

it ) + Ht(s

it )

], (54)

in cui abbiamo sommato, per ogni periodo t, i costi di produzione e di stoccaggio dainputare ai prodotti A e B.

Il primo vincolo che aggiungiamo e quello di continuita:

x it + s i

t−1 − s it = d i

t t = 1, ..., T , i = A,B (55)

Inoltre, dobbiamo rispettare la restrizione che impone la produzione di un solo tipo diprodotto per periodo (al piu). Si introducono quindi le seguenti variabili:

αt =

1 se produco A nel periodo t (xA

t > 0),0 altrimenti ,

t = 1, ..., T,

βt =

1 se produco B nel periodo t (xB

t > 0),0 altrimenti ,

t = 1, ..., T.

Il vincolo risultante sara quindi:

αt + βt ≤ 1 t = 1, ..., T, (56)

in modo che αt e βt non possano assumere contemporaneamente il valore 1, cioe i beni Ae B non possano essere prodotti nello stesso periodo. Si noti che l’espressione puo ancheassumere il valore 0, nel caso in cui nessun bene venga prodotto nel periodo t.

25

L’ultimo vincolo (best-before) ci obbliga a soddisfare la domanda del periodo t conla produzione del periodo stesso oppure con scorte prodotte nel periodo t − 1. Unaformulazione per tale vincolo puo essere la seguente:

s it−1 ≤ d i

t t = 1, ..., T, (57)

che, ricordando il vincolo di continuita: x it + s i

t−1− s it = d i

t , puo essere riscritto in questomodo:

s it−1 ≤ d i

t = x it + s i

t−1 − s it =⇒ x i

t ≥ s it .

In sostanza, il vincolo (57) dice che il livello di scorte accumulate in ciascun perio-do deve essere non superiore alla domanda del periodo successivo, o, se vogliamo, chetale livello di scorte non puo essere maggiore della quantita prodotta nel periodo stesso.In questo modo si assicura che tutte le scorte accumulate in un certo periodo sarannosicuramente “consumate”, al piu tardi, nel periodo successivo.

26