Esercizi di modellazione per il corso di Ricerca

Operativa 1

4 novembre 2005

2

Parte I

Esercizi

3

Modelli di programmazione

lineare

Molti problemi di interesse pratico si prestano ad essere descritti e risolti comemodelli di programmazione matematica. Un modello (o programma) e la de-scrizione di un problema che richiede di massimizzare (o minimizzare) unafunzione di costo o profitto su un certo dominio. La scrittura usuale e

max z = f(x) (oppure: min z = f(x)) (1)

soggetto a

gi(x)

≤ bi

= bi

≥ bi

i = 1, . . . , m, (2)

x = (x1, . . . , xn) ∈ X ⊆ Rn. (3)

Molti problemi di interesse pratico si prestano ad essere descritti e risolti comemodelli di programmazione matematica. Un modello (o programma) e la de-scrizione di un problema che richiede di massimizzare (o minimizzare) unafunzione di costo o profitto su un certo dominio. La scrittura usuale e

max z = f(x) (oppure: min z = f(x)) (4)

soggetto a

gi(x)

≤ bi

= bi

≥ bi

i = 1, . . . , m, (5)

x = (x1, . . . , xn) ∈ X ⊆ Rn. (6)

In un modello sono presenti:

• una serie di variabili di controllo in funzione delle quali viene formulatoogni altro elemento del modello; queste variabili, almeno in parte, cor-rispondono alle quantita agendo sulle quali la soluzione verra implemen-tata;

• una funzione obiettivo f(x) che determina un costo o profitto legato allasoluzione;

5

6

• una o piu serie di vincoli, che correlano tra loro i valori delle variabili, im-ponendo condizioni di fisica realizzabilita e/o requisiti particolari richiestialla soluzione.

Tra i modelli di programmazione matematica hanno particolare rilievo i modellidi programmazione lineare, nei quali la f(x) e le gi(x) sono espressioni lineari.

Un modello di programmazione lineare e quindi esprimibile sempre come

max z =n

∑

j=1

cjxj (7)

soggetto a

n∑

j=1

aijxj

≤ bi

= bi

≥ bi

i = 1, . . . , m, (8)

x = (x1, . . . , xn) ∈ X ⊆ Rn. (9)

I campi di esistenza delle variabili xj sono di solito di tipo continuo (spesso nonnegativo) oppure intero non negativo (xj ∈ Z+), oppure binario (xj ∈ {0, 1}) aseconda del tipo di decisione che tali variabili modellano.

La particolarita dei modelli lineari e legata alla loro maggiore semplicita,che li rende piu facilmente risolvibili rispetto ai modelli non lineari; in effettisono ormai disponibili pacchetti software commerciali in grado di risolvere inmodo efficiente programmi lineari di notevoli dimensioni (intese come quantitadi variabili e di vincoli). Questo rende spesso preferibile, per la risoluzione diun problema, lo sviluppo di un modello lineare anche quando un modello nonlineare potrebbe essere piu compatto.

Lo sviluppo di un modello di programmazione lineare parte dall’analisi di unasituazione reale (piu o meno schematizzata) e, in modo simile a quanto accadenello sviluppo di una procedura software, richiede di identificare le variabili dicontrollo ed i rispettivi domini, i vincoli e la funzione obiettivo. Non ci sonoregole rigide da seguire: il modello finale nasce spesso — in particolare nela casodi situazioni complesse — per raffinamenti successivi.

ESERCIZIO 1. Un gruppo di amici dovendo fare una gita ha deciso di metterecibi e bevande in un unico zaino da 10 Kg. Lo zaino puo essere riempito con

1. Cioccolata (confezioni da 500 g.)

2. Succhi di frutta (bottiglie da 1 l.)

3. Lattine di birra (formato da 0.33 l.)

4. Panini imbottiti (da 100 g. l’uno)

5. Acqua minerale (bottiglie da 1 l.)

6. Pacchi di biscotti (confezioni da 500 g.)

Dopo un’indagine tra i partecipanti alla gita (si poteva dare un voto da 1 a100 ad ogni prodotto) sono stati determinati i seguenti punteggi.

7

Prodotto Punti

Cioccolata 10Succhi di frutta 30Lattine di birra 6

Prodotto Punti

Panini imbottiti 20Acqua minerale 20Pacchi di biscotti 8

Per non scontentare nessuno si e deciso di portare almeno:

• 2 confezioni di cioccolata;

• 2 bottiglie di succo di frutta;

• 6 lattine di birra;

• 10 panini imbottiti;

• 2 conf. di biscotti.

Formulare il modello di Programmazione Lineare che massimizzi il punteggiorispettando il vincolo di capacita dello zaino.

ESERCIZIO 2. L’acciaieria PLASTIK deve evadere un ordine di 1000 tonnel-late di acciaio INOX. Per questa produzione servono manganese (almeno l’1%in peso), cromo (almeno il 18%) e molibdeno (almeno il 2%).

I fornitori di metalli non ferrosi vendono — per esigenze di mercato — questiprodotti in tre tipi di confezioni differenti. La prima confezione contiene 2 Kg.di manganese, 2 Kg. di cromo e 1 Kg. di molibdeno e costa 10 euro. La secondaconfezione contiene 2 Kg. di manganese, 3 Kg. di cromo e 1 Kg. di molibdenoe costa 15 euro. La terza confezione contiene 1 Kg. di manganese, 2 Kg. dicromo e 5 Kg. di molibdeno e costa 20 euro.

Formulare il modello di Programmazione Lineare per minimizzare il costo diacquisto delle confezioni.

ESERCIZIO 3. Un’azienda produce tre modelli 1, 2 e 3 di un certo prodot-to. Ciascun modello richiede due tipi di materiali grezzi (A e B) di cui sonodisponibili rispettivamente 4000 e 6000 unita. In particolare, per produrre unaunita del modello 1 sono necessarie 2 unita di A e 4 unita di B; per una unitadel modello 2 sono necessarie 3 unita di A e 2 unita di B; per una unita delmodello 3 sono necessarie 5 unita di A e 7 di B. Il modello 1 richiede, perogni unita prodotta, il doppio di forza lavoro rispetto al modello 2 e il triplorispetto al modello 3. La forza lavoro presente in azienda e in grado di produrreal massimo l’equivalente di 700 unita/giorno del modello 1. Il settore marketingdell’azienda ha reso noto che la domanda minima per ciascun modello e rispet-tivamente di 200, 200 e 150 unita. Il profitto unitario di ogni modello e di 30,20 e 50 euro, rispettivamente.

Formulare il programma lineare per pianificare la produzione giornalieramassimizzando il profitto.

ESERCIZIO 4. La casa editrice ANALFABETA pubblica un quotidiano cheviene distribuito da quattro centri di smistamento S1, S2, S3, S4 che richiedonorispettivamente almeno 100000, 150000, 50000 e 75000 copie. Il giornale vienestampato in tre tipografie T1, T2, T3 che producono rispettivamente al massimo125000, 180000 e 70000 copie

I costi per la spedizione sono di 2 euro/Km. per giornale e le distanze tra letipografie ed i centri di smistamento sono rispettivamente di 20, 25, 15 e 5 Km.

8

per la prima tipografia, di 12, 14, 18 e 30 Km per la seconda, e di 19, 11, 40 e12 Km per la terza.

(a) Formulare il modello di Programmazione Lineare per pianificare le spedi-zioni a costo totale minimo.(b) Si definisca il costo di approvvigionamento di un centro di smistamentocome il costo totale delle spedizioni verso quel centro. Formulare il modello diProgrammazione Lineare che minimizza il massimo costo di approvvigionamen-

to.

ESERCIZIO 5. Un motel autostradale, dovendo garantire un servizio contin-uato 24 ore su 24, ha bisogno di un numero minimo di inservienti per ogni oradel giorno secondo la seguente tabella.

Fascia oraria Numero min.

02-06 406-10 810-14 10

Fascia oraria Numero min.

14-18 718-22 1222-02 4

Ciascun inserviente lavora 8 ore consecutive al giorno.

Formulare il modello di Programmazione Lineare per garantire la presenzarichiesta utilizzando il minor numero possibile di inservienti.

ESERCIZIO 6. Scrivere il modello in programmazione lineare del seguenteproblema. Un caporeparto di un’officina di un’azienda meccanica deve pi-anificare l’esecuzione di cinque lotti su di una macchina della durata rispet-tivamente di 5 minuti, 7 minuti, 4 minuti, 7 minuti e 10 minuti. La se-quenza di esecuzione (1, 2, 3, 4, 5) e data e non ci puo essere sovrapposizionetemporale fra i lotti. Il primo lotto ha come ora di consegna desiderata le10.32, il secondo le 10.38, il terzo le 10.42, il quarto le 10.52 ed il quintole 10.57. Sia l’errore di un lotto pari al valore assoluto della differenza trail suo tempo di fine lavorazione e l’ora di consegna. Si vuole minimizzarela somma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle8.30).

ESERCIZIO 7. Scrivere il modello in programmazione lineare del seguenteproblema. Un’azienda alimentare deve pianificare la produzione di un prodottoper i prossimi 4 mesi. Non ci sono giacenze in magazzino all’inizio del periodo enon ce ne devono essere alla fine dei 4 mesi. La domanda mensile prevista e di120 ton, 160 ton, 300 ton e 200 ton rispettivamente (ipotesi: la produzione vienestoccata e rilasciata interamente a fine mese). La capacita produttiva mensile e140 ton, 150 ton, 140 ton e 160 ton rispettivamente ad un costo di 10 euro/ton.In caso di necessita e possibile produrre in straordinario aumentando la capacitamensile di (al piu) 50 ton, 75 ton, 70 ton e 80 ton rispettivamente. La produzionestraordinaria ha un costo addizionale di 6 euro/ton. Inoltre, per garantire unaproduzione omogenea si vuole che la produzione ordinaria di ciascun mese siaalmeno pari al 10% della produzione totale dei primi tre. Le eventuali giacenzea fine mese costano 5 euro/ton. L’obiettivo e quello di pianificare la produzionedi costo minimo.

ESERCIZIO 8. Lo stato di Islandia ha quattro industrie esportatrici: ac-ciaio, motori, elettronica e plastica. Il ministro dell’economia di questo statovuole massimizzare il saldo esportazioni-importazioni. La moneta di Islandia

9

e il klutz. I prezzi in klutz sul mercato mondiale per unita di acciaio, mo-tori, elettronica e plastica sono rispettivamente 500, 1500, 300 e 1200. Laproduzione di una unita di acciaio richiede 0.02 unita di motori, 0.01 unitadi plastica, 250 klutz di materie prime acquistate sul mercato mondiale e mez-zo anno-uomo di manodopera. La produzione di una unita di motori richiede0.8 unita di acciaio, 0.15 unita di elettronica, 0.11 unita di plastica, 300 klutzdi materie prime acquistate sul mercato mondiale e un anno-uomo di manod-opera. La produzione di una unita di prodotti elettronici richiede 0.01 unitadi acciaio, 0.01 unita di motori, 0.05 unita di plastica, 50 klutz di materieprime acquistate sul mercato mondiale e mezzo anno-uomo di manodopera. Laproduzione di una unita di plastica richiede 0.03 unita di motori, 0.2 unitadi acciaio, 0.05 unita di elettronica, 300 klutz di materie prime acquistate sulmercato mondiale e due anni-uomo di manodopera. La produzione di motorie limitata a 650000 unita, quella di plastica a 60000 unita. La manodoperatotale disponibile in Islandia e di 830000 uomini per anno. Acciaio, motori,elettronica e plastica non possono essere importati, ma devono essere prodottiall’interno.

ESERCIZIO 9. Scrivere il modello in programmazione lineare del seguenteproblema.

Si consideri un territorio sul quale siano localizzati 7 punti di domanda (ades. 7 citta) indicati in tabella con 1, 2, 3, 4, 5, 6, 7. Si considerino, inoltre, 5 puntidi offerta indicati in tabella con A, B, C, D, E nei quali potrebbero essere apertidei centri vendita di un’impresa di distribuzione. Tale impresa e interessata asoddisfare la domanda sopramenzionata in modo tale che i clienti non percorranopiu di 30 minuti di auto per raggiungere almeno uno dei centri vendita. Intabella, per ogni coppia di punti di domanda e di offerta, viene indicato iltempo auto necessario.

L’impresa ha inoltre fatto sapere che accettera soluzioni che prevedano l’at-tivazione del centro vendita B solo se e gia attivo uno dei centri C o D.

L’apertura dei centri vendita costa rispettivamente (in miliardi di lire): A =310, B = 250, C = 260, D = 330, E = 280.

L’obiettivo dell’impresa e di minimizzare i costi di apertura dei centri venditagarantendo il fatto che che tutti i punti di domanda vengano serviti.

A B C D E1 41 33 24 29 582 25 12 22 58 413 21 43 34 54 184 21 42 39 26 185 11 23 24 29 536 47 23 19 16 317 37 47 51 26 19

ESERCIZIO 10. Una raffineria produce benzina verde e super a partire dadue tipi di greggio A e B, usando tre impianti. Il primo impianto puo pro-durre 2 barili di verde e 3 di super a partire da 4 barili di greggio tipo A e3 barili di greggio tipo B. Il secondo impianto puo produrre 4 barili di verdee 2 di super a partire da 3 barili di A e 4 barili di B. Il terzo puo produrre

10

2 barili di verde e 2 barili di super a partire da 3 barili di A e 3 barili di B.Gli impianti lavorano sempre con le proporzioni specificate. La benzina verdeviene venduta a 40$/barile, la super a 50$/barile. Sono disponibili per questomese 5000 barili di greggio A e 6000 barili di greggio B. Per esigenze legate adaltre lavorazioni, almeno uno tra gli impianti deve produrre non piu di 1000barili. Formulare il programma lineare per massimizzare il profitto legato allaproduzione mensile.

ESERCIZIO 11. Un’azienda agricola produce mais, soia e grano in tre tenuteA, B, C. La tenuta A dispone di 600 ettari di terreno e di una riserva di 8×106 m3

di acqua. La tenuta B ha 700 ettari di terreno e 5× 106 m3 di acqua. La terzadispone di 450 ettari e di 6 × 106 m3. Le produzioni di mais, soia e granogarantiscono rispettivamente profitti di 5, 7 e 6 Keuro/ettaro. I consumi diacqua sono di 20000 m3/ha per il mais,10000 m3/ha per la soia e 10000 m3/haper il grano. Le direttive della comunita europea richiedono che:

• almeno una tenuta lasci 200 ettari di terreno incolto, e

• l’estensione complessiva del terreno coltivato a soia dall’azienda non superiil 40% del totale del suolo coltivato.

Formulare il programma lineare per la massimizzazione del profitto.

ESERCIZIO 12. Una ditta ha la possibilita di attivare, per l’anno corrente,la produzione di quattro tipi di prodotti A, B, C e D. Per ogni tipo di pro-duzione, se attivata, la ditta si impegna a produrre un quantitativo minimopari rispettivamente a 1000, 1500, 3000 e 2000 unita. La produzione di A, B, Ce D richiede un costo fisso per l’attivazione delle rispettive linee di produzioneed una quantita di forza lavoro per ogni unita prodotta, ed ogni unita vendutafornisce un profitto, come specificato dalla seguente tabella (in euro).

Prodotto Costo fisso Forza lavoro unit. Profitto unit.

A 14500 10 50B 10000 15 60C 8000 5 55D 9000 14 80

La ditta dispone per l’anno in corso di 200000 unita complessive di forza lavoro.Inoltre i committenti per la quale essa lavora richiedono che nel caso vengaattivata la produzione di A venga anche prodotto almeno uno tra C o D, almenonei quantitativi minimi sopra indicati.

Formulare il programma lineare per decidere le produzioni da attivare e pi-anificarne i quantitativi al fine di massimizzare il saldo costi-profitti.

ESERCIZIO 13. Scrivere il modello in programmazione lineare del seguenteproblema. In una centrale elettrica sono a disposizione tre generatori ed ognigiorno si deve decidere quali usare solo di giorno e quali anche di notte per as-sicurare una produzione di almeno 4000 megawatts di giorno e di almeno 2800megawatts di notte. L’uso di un generatore comporta la presenza di person-ale tecnico che sorvegli il suo funzionamento; tale personale viene retribuito inmaniera differente a seconda dei turni necessari (12h/24h) e del tipo di genera-tore. Tali costi di attivazione sono riportati nella tabella che segue (in migliaiadi lire) insieme al costo per ogni megawatt prodotta.

11

Costo attivazione Costo algiorno giorno/notte megawatt

Generatore A 800 1200 4Generatore B 700 1000 6Generatore C 900 1400 7

Il generatore A ha una capacita produttiva di 2500 megawatts al giorno maquesta capacita scende a 2000 megawatts se il generatore viene utilizzato sia digiorno che di notte. Analogamente, il generatore B ha una capacita produttivadi 2000 megawatts al giorno ma questa capacita scende a 1500 megawatts se ilgeneratore viene utilizzato sia di giorno che di notte. Infine, il generatore C hauna capacita produttiva di 3000 megawatts al giorno ma questa capacita scendea 2500 megawatts se il generatore viene utilizzato sia di giorno che di notte. Sivuole minimizzare il costo complessivo.

ESERCIZIO 14. Scrivere il modello in programmazione lineare del seguenteproblema. Un caporeparto di un’officina di un’azienda meccanica deve piani-ficare l’esecuzione di cinque lotti su di una macchina della durata rispettiva-mente di 5 minuti, 7 minuti, 4 minuti, 7 minuti e 10 minuti. Non ci puo esseresovrapposizione temporale fra i lotti. Il primo lotto ha come ora di consegnadesiderata le 10.32, il secondo le 10.38, il terzo le 10.42, il quarto le 10.52 ed ilquinto le 10.57. Sia l’errore di un lotto pari al valore assoluto della differenzatra il suo tempo di fine lavorazione e l’ora di consegna. Si vuole minimizzare lasomma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle 8.30).

ESERCIZIO 15. Una ditta che si occupa di riparazioni deve pianificare leassunzioni per i prossimi 5 mesi. All’inizio la ditta dispone di 20 operai es-perti; ogni operaio esperto fornisce 150 ore di lavoro al mese e percepisce unostipendio mensile di 1000 euro. Un operaio neoassunto, durante il primo mesedi servizio percepisce uno stipendio di 500 euro e non fornisce in pratica lavoroutile; per questo primo mese gli viene invece affiancato un lavoratore espertoper insegnargli il mestiere. Ogni lavoratore esperto che svolge affiancamentorende per 70 ore di lavoro al mese (anziche 150). Dopo il mese di apprendistatoi lavoratori neoassunti diventano esperti, con pari abilita lavorativa e stipen-dio. Le quantita di ore/lavoro da coprire per i prossimi 5 mesi sono rispetti-vamente di 2000, 4000, 7000, 3000, 3500 ore. Infine, se si assumono almeno10 persone nel corso dei primi due mesi, l’azienda puo incassare un contributostatale di 100000 euro. Formulare il programma lineare che consente di pianifi-care le assunzioni riducendo al minimo i costi del personale nei prossimi cinquemesi.

ESERCIZIO 16. L’azienda PC4All produce pc e deve acquistare le scorte dimaterie prime necessarie per la produzione dei case. Per produrre i case nelmese corrente sono necessari i seguenti materiali:

• viti: 15000 unita;

• plastica: 1300 kg.;

• acciaio: 2900 kg.

12

Per effettuare gli acquisti l’azienda si puo appoggiare a quattro fornitori, iquali le forniscono le materie prime in lotti contenenti le seguenti quantita dimateriale:

viti plastica acciaioF1 50 3 5F2 30 4 7F3 25 1 3F4 10 8 1

Nell’ottica di gestire al meglio il proprio magazzino, la PC4All intende avere,alla fine del mese, la minor quantita di materiale non utilizzato possibile e, a talfine, e disposta anche a comprare una quantita di materie prime inferiore alleproprie necessita. Il costo per lo stockaggio o per il mancato acquisto di unaunita di materiale e il seguente:

Viti 0.2 euro/pezzoPlastica 1 euro/kg.Acciaio 3 euro/kg.

Per motivi commerciali l’azienda, se acquista dei lotti di materiale dal fornitoreF1, e impossibilitata a rifornirsi dai fornitori F2 ed F4.

Formulare il modello di programmazione lineare che minimizzi i costi derivan-ti dallo scostamento tra le quantita di materiali acquistate e quelle necessarie,tenendo conto che non e possibile comprare porzioni di lotto di materiali.

Parte II

Soluzioni

13

Modelli di programmazione

lineare

1. Le variabili di controllo determinano la struttura della soluzione di un problema,permettendone la realizzazione. Quindi in questo caso e naturale definire levariabili

x1, x2, x3, x4, x5, x6,

con il significato

xi = unita di alimento (i) caricate nello zaino.

Con questa scelta di variabili si puo ottenere il seguente modello, nel qualecompaiono due serie di vincoli: (1) un vincolo relativo alla capacita dello zaino,che non puo essere superata, e (2) vincoli relativi ai quantitativi minimi dialimenti da caricare.

max 10x1 + 30x2 + 6x3 + 20x4 + 20x5 + 8x6

soggetto a

1

2x1 + x2 +

1

3x3 +

1

10x4 + x5 +

1

2x6 ≤ 10 (1.1)

x1 ≥ 2, x2 ≥ 2, x3 ≥ 6,

x4 ≥ 10, x6 ≥ 2,(1.2)

x1, . . . , x6 ∈ Z+.

2. Le variabili piu naturali sono x1, x2, x3, dove xi = numero di confezioni ditipo i acquistato. A volte puo non essere evidente quale sia la scelta di vari-abili “piu naturale”. Una buona regola euristica e spesso la seguente: unadefinizione di variabili e soddisfacente quando essa permette di scrivere in modosemplice la funzione obiettivo (o comunque i vincoli piu significativi) del mod-ello. Ad esempio, in questo caso usare variabili che rappresentano le quantita dimateriali (manganese, cromo, molibdeno) acquistate anziche le confezioni nonsarebbe soddisfacente, in quanto la funzione obiettivo risulterebbe molto difficileda esprimere.

Con la scelta di variabili indicata invece, si ottiene il modello

min 10x1 + 15x2 + 20x3

15

16

soggetto a

2x1 + 2x2 + x3 ≥ 10000 (2.1)

2x1 + 3x2 + 2x3 ≥ 180000 (2.2)

x1 + x2 + 5x3 ≥ 20000 (2.3)

x1, x2, x3 ∈ Z+,

dove i vincoli (2.1), (2.2) e (2.3) rappresentano i quantitativi minimi di man-ganese, cromo e molibdeno da garantire, rispettivamente.

3. Le variabili x1, x2, x3 sono sufficienti a modellare il problema, con xi = numerodi unita di tipo i prodotte. Quindi si ha

max 30x1 + 20x2 + 50x3

soggetto a

2x1 + 3x2 + 5x3 ≤ 4000

4x1 + 2x2 + 7x3 ≤ 6000(3.1)

x1 +1

2x2 +

1

3x3 ≤ 700 (3.2)

x1 ≥ 200, , x2 ≥ 200, x3 ≥ 150 (3.3)

x1, x2, x3 ∈ Z+,

con i vinvoli (3.1), (3.2) e (3.3) che rappersentano i vincoli sulla disponibilita dimaterie prime, sulla forza lavoro disponibile e sui requisiti minimi di produzionestabiliti dal marketing, rispettivamente.

4. (a) Per come sono specificati i costi di spedizione, la scelta “naturale” per ladefinizione delle variabili di controllo e la seguente:

xij = numero di copie spedite da Ti a Sj .

In questo modo il modello diventa

max

3∑

i=1

4∑

j=1

cijxij

soggetto a

x11 + x12 + x13 + x14 ≤ 125000

x21 + x22 + x23 + x24 ≤ 180000

x31 + x32 + x33 + x34 ≤ 70000

(4.1)

x11 + x21 + x31 ≥ 100000

x12 + x22 + x32 ≥ 150000

x13 + x23 + x33 ≥ 50000

x14 + x24 + x34 ≥ 75000

(4.2)

xij ∈ Z+, ∀ i, j.

17

I vincoli (4.1) e (4.2) impongono che ogni tipografia spedisca non piu giornalidi quanti ne stampa (per la realizzabilita “fisica” della soluzione) e che ognicentro ne riceva una quantita pari almeno al proprio fabbisogno. I costi cij

sono ricavati dalla matrice delle distanze indicata dal testo: cij = 2×(distanzaTi-Sj).(b) L’obiettivo specificato pone la necessita di scrivere un programma di minimocon una funzione obiettivo del tipo

maxj

{

3∑

i=1

cijxij

}

.

Tale espressione e pero non lineare e quindi proibita nel tipo di modelli quitrattato. Per conservare la linearita del modello, occorre introdurre una variabileausiliaria ed una serie di vincoli come segue.

min y

soggetto a

x11 + x12 + x13 + x14 ≤ 125000

x21 + x22 + x23 + x24 ≤ 180000

x31 + x32 + x33 + x34 ≤ 70000

(4.1′)

x11 + x21 + x31 ≥ 100000

x12 + x22 + x32 ≥ 150000

x13 + x23 + x33 ≥ 50000

x14 + x24 + x34 ≥ 75000

(4.2′)

3∑

i=1

cijxij ≤ y j = 1, . . . , 4 (4.3)

xij ∈ Z+, ∀ i, j, y ≥ 0

La variabile ausiliaria y ed i vincoli (4.3) permettono di gestire l’obiettivo“min / max” conservando la linearita del modello: in ogni soluzione ottima

di questo programma lineare, il valore assunto da y coincide esattamente conmaxj{

∑ni=1 cijxij}. I vincoli (4.1′) e (4.2′) hanno il ruolo gia noto.

5. Questo problema richiede, per essere modellato in modo semplice, una definizioneaccorta di variabili. Occorre tener presente che: (1) esiste una soluzione ottimadove ogni inserviente comincia lavorare all’inizio di una fascia oraria e ne copreesattamente due; (2) ogni inserviente ha (naturalmente) un unico orario di inizioturno. Quindi e possibile definire:

xi = numero di inservienti che cominciano il turno nella fascia i (i = 1, . . . , 6).

Con queste variabili si ottiene il modello

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

18

soggetto a

x1 + x6 ≥ 4 (5.1)

x1 + x2 ≥ 8 (5.2)

x2 + x3 ≥ 10 (5.3)

x3 + x4 ≥ 7 (5.4)

x4 + x5 ≥ 12 (5.5)

x5 + x6 ≥ 4 (5.6)

x1, . . . , x6 ∈ Z+.

Poiche ogni inserviente che comincia il turno nella fascia i copre le fasce i edi+1 (modulo 6), i vincoli (5.1)–(5.6) garantiscono la copertura richiesta in ognifascia. La funzione obiettivo rappresenta esattamente il numero di inservientinecessari.

6. Il problema richiede di scrivere un modello in grado di determinare gli istantidi inizio lavirazione dei lotti in esame; si puo assumere come “zero” del tempol’ora delle 8:30, per cui i lotti hanno date di scadenza (espresse in minuti) di122, 128, 132, 142 e 147. Una serie di variabili e necessaria per rappresentare itempi di inizio lavorazione:

ti = istante di lavorazione (in minuti dalle 8:30) del lotto i.

Inoltre l’errore del lotto i e dato da ∆i = |ti + pi − di|, dove pi e di indicanorispettivamente il tempo di lavorazione e la scadenza del lotto. La funzioneobiettivo e quindi del tipo

5∑

i=1

|ti + pi − di|.

Questo genere di funzione e non lineare quindi occorre nuovamente ricorrere adun espediente per rappresentare i valori assoluti in un modello lineare. Ricor-dando che |x| = max(x,−x), si puo pensare di utilizzare la stessa tecnica usataper obiettivi di tipo “min / max”. Si introducono quindi le variabili

∆i = errore del lotto i.

Il modello e il seguente.

min ∆1 + ∆2 + ∆3 + ∆4 + ∆5

19

soggetto a

t1 + 5 ≤ t2 (1 → 2)

t2 + 7 ≤ t3 (2 → 3)

t3 + 4 ≤ t4 (3 → 4)

t4 + 7 ≤ t5 (4 → 5)

(6.1)

∆1 ≥ t1 + 5− 122

∆1 ≥ −(t1 + 5− 122)

∆2 ≥ t2 + 7− 128

∆2 ≥ −(t2 + 7− 128)

∆3 ≥ t3 + 4− 132

∆3 ≥ −(t3 + 4− 132)

∆4 ≥ t4 + 7− 142

∆4 ≥ −(t4 + 7− 142)

∆1 ≥ t5 + 10− 147

∆1 ≥ −(t5 + 10− 147)

(6.2)

ti ≥ 0, ∆i ≥ 0, i = 1, . . . , 5.

I vincoli (6.1) garantiscono il rispetto della sequenza di lavorazione che, secondoil testo, e predeterminata, mentre i vincoli (6.2) vincolano i ∆i ad assumere ilvalore assoluto di ti + pi − di.

7. Il problema richiede in piu, rispetto ad altri problemi di produzione gia risolti,la gestione di scorte di magazzino in un certo numero di periodi di tempo (mesi,in questo caso). Questi problemi, comuni nel settore della pianificazione dellaproduzione, vengono detti multiperiodali. In questi casi e utile (anche se nonsempre indispensabile) disporre di un insieme di variabili che rappresentanoesplicitamente il livello delle giacenze da gestire alla fine (o all’inizio) di ogniperiodo. Il problema in esame puo essere modellato utilizzando le seguentivariabili.

xi = produzione ordinaria (in ton.) per il mese i = 1 . . . , 4,

si = produzione straordinaria (in ton.) per il mese i = 1, . . . , 4,

yi = giacenze in magazzino alla fine del mese i = 1, . . . , 3.

Una y4 non e stata definita, in quanto e esplicitamente richiesto che essa valgazero in ogni soluzione ammissibile. Occorre modellare l’uso della produzioneordinaria e straordinaria, rispettarne i limiti e correlarle alla domanda mensile(che deve essere soddisfatta) ed alle giacenze in magazzino. In base alle variabilispecificate, un modello possibile e

min 10

4∑

i=1

xi + 16

4∑

i=1

si + 5

3∑

i=1

yi

20

soggetto a

x1 + s1 = 120 + y1

x2 + s2 + y1 = 160 + y2

x3 + s3 + y2 = 300 + y3

x4 + s4 + y3 = 200

(7.1)

xi ≥ 0.13

∑

i=1

(xi + si) i = 1, . . . , 4 (7.2)

x1 ≤ 140, x2 ≤ 150, x3 ≤ 140, x4 ≤ 160, (7.3)

s1 ≤ 50, s2 ≤ 75, s3 ≤ 70, s4 ≤ 80, (7.4)

xi, si, yi ≥ 0, i = 1, . . . , 4.

I vincoli (7.1) svolgono il compito fondamentale di correlare la produzione diogni mese con livelli di giacenze e domanda, esprimendo il bilancio

(produzione mensile)+(giacenze a mese precedente)

= (domanda mese)+(giacenze a fine mese).

Le serie successive di vincoli sono piuttosto semplici ed esprimono il requisito suilivelli di produzione ordinaria minimi mensili (10% del totale sui primi tre mesi)e sulle capacita produttive massime (ordinaria e straordinaria) per i quattromesi.

8. Indicando i prodotti con A, M , E, P (Acciaio, Motori, Elettronica, Plastica)si possono riassumere i requisiti per la produzione nella seguente tabella.

A M E P Anni uomo Mat. prime

A 0.02 0.01 0.5 250M 0.8 0.15 0.11 1.0 300E 0.01 0.01 0.05 0.5 50P 0.2 0.03 0.05 2.0 300

Poiche acciaio, motori, elettronica e plastica vanno prodotti internamente e nonacquistati, e conveniente scorporare la produzione per uso interno da quella peresportazioni, definendo le variabili

xA, xM , xE , xP ,yA, yM , yE, yP ,

dove

xi = unita di prodotto i realizzate per esportazione, i ∈ {A, M, E, P},

yi = unita di prodotto i realizzate per uso interno, i ∈ {A, M, E, P}.

Dall’analisi del testo, occorre garantire che:

• la produzione interna di ogni prodotto sia sufficiente a supportare laproduzione totale;

• le quantita di motori e plastica prodotte non eccedano i limiti imposti;

21

• il piano produttivo non ecceda il monte-ore diponibile.

Con le variabili precedentemente definite, il modello risulta come segue.

max 500xA + 1500xB + 300xE + 1200xP

−[250(xA + yA) + 300(xM + yM ) + 50(xE + yE) + 300(xP + yP )]

soggetto a

yA ≥ 0.8(xM + yM ) + 0.01(xE + yE) + 0.2(xP + yP )

yM ≥ 0.02(xA + yA) + 0.01(xE + yE) + 0.03(xP + yP )

yE ≥ 0.15(xM + yM ) + 0.05(xP + yP )

yP ≥ 0.01(xA + yA) + 0.11(xM + yM ) + 0.05(xE + yE)

(8.1)

xM + yM ≤ 650000

xP + yP ≤ 600000(8.2)

0.5(xA + yA) + (xM + yM ) + 0.5(xE + yE) + 2(xP + yP ) ≤ 830000 (8.3)

xA, xM , xE , xP ≥ 0,

yA, yM , yE , yP ≥ 0.

La funzione obiettivo rappresenta il saldo esportazioni-importazioni; i vincoli (8.1)impongono che la produzione interna di ogni prodotto sia in grado di supportarela produzione totale; i vincoli (8.2) impongono i limiti richiesti alle produzioni dimotori e plastica, ed infine il vincolo (8.3) impone di non eccedere il monte-oredisponibile.

9. L’apertura di un centro e una decisione che differisce da quelle modellate finoa questo momento, per il fatto di essere puramente binaria (un centro vieneaperto oppure no, non esistono casi intermedi). Per modellare questo genere didecisioni, e possibile inserire nei programmi lineari variabili binarie, cioe intericon valori limitati all’insieme {0, 1}. E da notare che queste variabili, a parte illoro campo di esistenza, non hanno alcun ruolo privilegiato rispetto alle altre;in particolare, non sono disponibili i consueti operatori logici (tipo and, or,not) comuni nei linguaggi di programmazione, che vanno quindi “emulati” permezzo di esperessioni lineari puramente algebriche. Inoltre, non e consentitoin alcun modo introdurre prodotti del tipo (variabile logica)×(altre variabili),errore sorprendentemente comune.

Il problema in esame si puo modellare con cinque variabili binarie A, B, C,D, E che rappresentano l’apertura (variabile= 1) o la non-apertura (variabile=0) del rispettivo centro.

min 310A + 250B + 260C + 330D + 280E

22

soggetto a

C + D ≥ 1 (9.1)

A + B + C ≥ 1 (9.2)

A + E ≥ 1 (9.3)

A + D + E ≥ 1 (9.4)

A + B + C + D ≥ 1 (9.5)

B + C + D ≥ 1 (9.6)

D + E ≥ 1 (9.7)

B ≤ C + D (9.8)

I vincoli (9.1)–(9.7) modellano operatori logici di tipo or: in base ai tempi dipercorrenza dati, per servire il punto 1 occorre aprire C oppure D; per servire ilpunto 2 occorre aprire A oppure B oppure C, e cosı via. Il vincolo (9.8) modellaun’implicazione logica

B =⇒ C ∨ D

(il requisito “B apre solo se . . . ” specificato dal testo: confrontare con la tabelladi verita dell’operatore logico).

Si noti anche che nell’insieme di vincoli (9.1)–(9.8) esistono vincoli ridon-

danti : ad esempio, (9.1) implica (9.5), (9.6) e (9.8); questi tre vincoli potreb-bero quindi essere rimossi dal modello. Questa operazione non e strettamentenecessaria ai fini della correttezza del modello, ma e desiderabile in ambitoapplicativo, in quanto semplifica la risoluzione del modello.

10. La definizione di variabili che porta a realizzare il modello piu conciso e prob-abilmente la seguente:

xi = numero di lavorazioni svolte all’impianto i = 1, 2, 3.

yi =

{

1 iff l’impianto i e limitato a 1000 barili,

0 altrimenti,i = 1, 2, 3.

La definizione suggerita di xi permette di gestire il funzionamento degli impianticon le proporzioni specificate, senza ricorrere a vincoli addizionali. Il modellorisulta

max 40(2x1 + 4x2 + 2x3) + 50(3x1 + 2x2 + 2x3)

soggetto a

4x1 + 3x2 + 3x3 ≤ 5000

3x1 + 4x2 + 3x3 ≤ 6000(10.1)

y1 + y2 + y3 ≥ 1 (10.2)

5x1 ≤ 1000y1 + M(1− y1)

6x2 ≤ 1000y2 + M(1− y2)

4x3 ≤ 1000y3 + M(1− y3)

(10.3)

xi ≥ 0, yi ∈ {0, 1}, i = 1, 2, 3.

23

I vincoli (10.1) sono relativi al magazzino disponibile per i due tipi di greggio,che limita la produzione. Il vincolo (10.2) impone che almeno un impianto sialimitato a 1000 barili. I vincoli (10.3) svolgono l’importante funzione di collegarei valori delle variabili binarie yi con i valori delle xi; la costante M (detta spesso“big-M”) e una costante estremamente grande. Si noti che ad esempio il primovincolo di questa serie implica:

y1 = 1 =⇒ 5x1 ≤ 1000,

y1 = 0 =⇒ 5x1 ≤ M (cioe 5x1 non vincolato).

Questa tecnica del “big-M” e comunemente usata per correlare variabili binariee variabili di altro tipo.

11. E necessario scorporare il prodotto sia per tipologia che per tenuta, altrimentinon e possibile gestire le estensioni coltivate e le riserve d’acqua. Sono quindinecessarie le variabili

xij = ettari della tenuta j coltivati a coltura i,

con i ∈ {M, S, G} (Mais, Soia e Grano) e j ∈ {A, B, C}. Inoltre tre variabilibinarie yA, yB ed yC verranno usate per determinare quale tenuta lascera 200ettari incolti (yj = 1 iff la tenuta j lascia 200 ettari incolti). Il modello e ilseguente.

max5(xMA + xMB + xMC) + 7(xSA + xSB + xSC) + 6(xGA + xGB + xGC)

soggetto a

xMA + xSA + xGA ≤ 600− 200yA

xMB + xSB + xGB ≤ 700− 200yB

xMC + xSC + xGC ≤ 450− 200yC

(11.1)

20000xMA + 10000xSA + 10000xGA ≤ 8 · 106

20000xMB + 10000xSB + 10000xGB ≤ 5 · 106

20000xMC + 10000xSC + 10000xGC ≤ 6 · 106

(11.2)

xSA + xSB + xSC ≤ 0.4∑

i=M,S,G

∑

j=A,B,C

xij (11.3)

yA + yB + yC ≥ 1 (11.3)

xij ≥ 0, yj ∈ {0, 1}, i = M, S, G, j = A, B, C.

I vincoli (11.1) impediscono di coltivare in una tenuta piu del totale del suolodisponibile; i vincoli (11.2) impediscono di coltivare piu di quanto si possa irri-gare con le scorte d’acqua delle varie tenute; il vincolo (11.3) stabilisce che nonpiu del 40% del suolo coltivato in totale puo essere messo a soia, ed il vinco-lo (11.3) impone che almeno una tenuta lasci 200 ha di suolo incolto. Si noti chein questo caso non e necessario introdurre un big-M per collegare le yj con le xij :e sufficiente definire nel modo opportuno i secondi membri dei vincoli (11.1).

24

12. Il problema proposto riguarda la pianificazione di certi tipi di produzione concosti fissi imputabili alla preparazione degli impianti produttivi e costi variabililegati alle quantita prodotte. La decisione di attivare o meno la produzione diA, B, C o D e di tipo vero/falso, e quindi si puo modellare con variabii binarie

yi = 1 iff si attiva la produzione di i ∈ {A, B, C, D}.

Occorre poi determinare anche i volumi prodotti, rappresentabili mediante un’al-tra serie di variabili

xi = numero di unita di tipo i prodotte, i ∈ {A, B, C, D}.

Tenuto conto dei dati su quantitativi minimi, profitti unitari e forza lavoro datidal testo il modello risulta come segue.

max 50xA + 60xB + 55xC + 80xD

− (14500yA + 10000yB + 8000yC + 9000yD)

soggetto a

xA ≥ 1000yA

xB ≥ 1500yB

xC ≥ 3000yC

xD ≥ 2000yD

(12.1)

xA ≤ MyA

xB ≤ MyB

xC ≤ MyC

xD ≤ MyD

(12.2)

10xA + 15xB + 5xC + 14xD ≤ 2000000 (12.3)

yA ≤ yC + yD (12.4)

xi ∈ Z+, yi ∈ {0, 1}, i ∈ {A, B, C, D}.

I vincoli (12.1) impongono il rispetto dei quantitativi minimi qualora un tipo diproduzione venga attivato, mentre i vincoli (12.2) assicurano che non venganopianificati quantitativi per produzioni non attivate. Il vincolo (12.3) impone dinon eccedere la quantita di forza lavoro disponibile; il vincolo (12.4) modellal’implicazione logica

yA =⇒ yC ∨ yD,

come richiesto dal testo.

13. Assumendo i turni possibili specificati dal testo, si possono definire due seriedi variabili binarie:

xi =1 iff il generatore i e utilizzato di giorno, i = A, B, C,

yi =1 iff il generatore i e utilizzato sia di giorno che di notte, i = A, B, C.

25

Inoltre, essendoci un costo/MW, occorrono variabili in grado di specificare ilnumero di MW prodotti dai generatori. Per mantenere distinte la produzionediurna da quella notturna, si usano nuovamente due serie di variabili:

Wi =MW prodotti dal generatore i se usato nel turno di giorno, i = A, B, C,

Zi =MW prodotti dal generatore i se usato nel turno giorno/notte, i = A, B, C.

Il modello risulta

min (800xA + 1200yA) + (700xB + 1000yB) + (900xC + 1400xC)

+ 4(WA + ZA) + 6(WB + ZB) + 7(WC + ZC)

soggetto a

xA + yA ≤ 1

xB + yB ≤ 1

xC + yC ≤ 1

(13.1)

WA ≤ 2500xA, ZA ≤ 2000yA

WB ≤ 2000xB, ZB ≤ 1500yB

WC ≤ 3000xC, ZC ≤ 2500yC

(13.2)

WA + WB + WC + ZA + ZB + ZC ≥ 4000

ZA + ZB + ZC ≥ 2800(13.3)

Wi, Zi ≥ 0, xi, yi ∈ {0, 1}, i = A, B, C.

I vincoli (13.1) impongono che ogni generatore funzioni secondo al piu un tipodi turno. I vincoli (13.2) fissano i limiti dell’erogazione di potenza come daturno per ogni generatore; si noti anche qui l’uso di tecniche in stile big-M: adesempio, il primo vincolo di questa serie implica

xA = 1 =⇒ WA ≤ 2500,

xA = 0 =⇒ WA = 0.

Infine, i vincoli (13.3) impongono il soddisfacimento delle potenze minime peril giorno e per la notte.

14. In questo problema e importante notare che la sequenza delle lavorazioni non

e predeterminata; essa deve essere quindi determinata dalla soluzione del mod-ello. Rispetto all’esercizio 6, occorre una serie di variabili in piu. Vengono quiproposte due soluzioni possibili.(a) Una sequenza di lavorazione e determinata quando, per ogni coppia (nonordinata) {i, j} di lotti si e in grado di determinare se i viene lavorato prima dij (i → j) o viceversa. Si possono quindi usare le variabili binarie

xij = 1 iff i → j, i < j.

Si usano inoltre tutte le variabili dell’esercizio 6. Il valore delle variabili xij devepoi essere correlato alle variabili ti mediante una serie di vincoli di tipo big-M.

26

Nel seguito, pi e di rappresentano tempo di lavorazione e scadenza (in minutidalle 8:30) del lotto i.

min5

∑

i=1

∆i

soggetto a

∆i ≥ ti + pi − di i = 1, . . . , 5

∆i ≥ −(ti + pi − di) i = 1, . . . , 5(14.1)

ti + pi ≤ tj + M(1− xij) i < j, i = 1, . . . , 5

tj + pj ≤ ti + Mxij i < j, i = 1, . . . , 5(14.2)

ti ≥ 0, xij ∈ {0, 1}, i, j = 1, . . . , 5, i < j.

I vincoli (14.1) sono del tipo usato per gestire i valori assoluti; le serie divincoli (14.2) correlano i valori delle xij con le ti:

xij = 1 =⇒ ti + pi ≤ tj (i → j),

xij = 0 =⇒ tj + pj ≤ ti (j → i).

(b) Alternativamente, si puo osservare che una sequenza di lavorazione e determi-nata quando ogni lotto e assegnato ad una e una sola delle posizioni 1, 2, . . . , 5disponibili nell’ordine di lavorazione. Si possono allora utilizzare le seguentivariabili.

xij = 1 se il lotto i e in posizione j, 0 altrimenti, i, j = 1, . . . , 5;

∆[j] = errore del lotto in posizione j, j = 1, . . . , 5;

t[j] = tempo di inizio lavorazione del lotto in posizione j, j = 1, . . . , 5.

Siano pi e di i tempi di lavorazione e le scadenze espresse in minuti per ognilotto i (nota: questi sono dati). Con le variabili definite sopra si puo scrivere ilseguente modello.

min∑

j=1

∆[j]

27

soggetto a

5∑

j=1

xij = 1 i = 1, . . . , 5

5∑

i=1

xij = 1 j = 1, . . . , 5

(14.1)

t[j] +

5∑

i=1

pixij ≤ t[j+1] j = 1, . . . , 4 (14.2)

∆[j] ≥ t[j] +

5∑

i=1

pixij −

5∑

i=1

dixij j = 1, . . . , 5

∆[j] ≥ −

(

t[j] +

5∑

i=1

pixij −

5∑

i=1

dixij

)

j = 1, . . . , 5

(14.3)

xi,j ∈ {0, 1}, i, j ∈ {1, . . . , 5}, t[j], ∆[j] ≥ 0, j ∈ {1, . . . , 5}.

La funzione delle coppie di vincoli (14.1) e cruciale: essi impongono che (1) ognilotto sia assegnato ad esattamente una posizione della sequenza di lavorazione,e (2) che ogni posizione ospiti esattamente lotto. I vincoli (14.2) impongono lacorretta temporizzazione della sequenza (senza sovrapposizioni), ma si noti chesia le t[j] che le ∆[j] sono indicizzate qui rispetto alla posizione nella sequenza, enon rispetto ai lotti: questi vincoli funzionano correttamente grazie alle (14.1):si noti che grazie a questi si ha

5∑

i=1

pixij = tempo di lavorazione del j-esimo lotto della sequenza.

I vincoli (14.3) gestiscono i valori assoluti, sempre tenendo conto dell’asseg-nazione lotti-posizioni; analogamente a prima, si ha

5∑

i=1

dixij = scadenza del lotto in posizione j.

15. Il problema richiede in pratica di gestire un pool di assunti/neoassunti chevaria di mese in mese: e un problema multiperiodale. Una soluzione e un“piano di assunzioni” che permetta di coprire comunque il monte-ore richiestonei vari mesi compatibilmente con lo svolgimento dell’affiancamento da partedegli esperti. Possiamo modellare la situazione con dieci variabili:

y1, y2, y3, y4, y5,

x1, x2, x3, x4, x5,

dove yi = disponibilita di esperti al mese i e xi = numero di persone assunteal mese i. Modelliamo con una variabile logica z la scelta di ottenere o nonottenere il contributo statale. Come ulteriore considerazione, si noti che la x5

e superflua in quanto assumere all’ultimo mese e un costo, non fornisce forza

28

lavoro sfruttabile entro l’orizzonte temporale coperto dal modello e non influiscesulla possibilita di ottenere il contributo statale. In ogni soluzione ottima si avrax5 = 0.

In base alle variabili definite il costo del personale (assunzioni e stipendi)totale nei cinque mesi e:

f(x) = 500(x1 +x2 +x3 +x4 +x5)+1000(y1 + y2 + y3 + y4 + y5)− 100000z.

Il modello complessivo risulta essere:

min 500(x1 + x2 + x3 + x4 + x5) + 1000(y1 + y2 + y3 + y4 + y5) − 100000z

soggetto a(Mese 1)

y1 = 20

x1 ≤ y1

150(y1 − x1) + 70x1 ≥ 2000

(Mese 2)

y2 = y1 + x1

x2 ≤ y2

150(y2 − x2) + 70x2 ≥ 4000

(Mese 3)

y3 = y2 + x2

x3 ≤ y3

150(y3 − x3) + 70x3 ≥ 7000

(Mese 4)

y4 = y3 + x3

x4 ≤ y4

150(y4 − x4) + 70x4 ≥ 3000

(Mese 5)

y5 = y4 + x4

x5 ≤ y5

150(y5 − x5) + 70x5 ≥ 3500

(Vincolo logico)

x1 + x2 ≥ 10z

xi, yi ∈ Z+ ∀i, z ∈ {0, 1}

16. L’azienda in questione, a detta del testo, paga un costo sia per lo stoccaggioche per il mancato acquisto di materiali. Quindi, tenuto conto dei quantitativi

29

richiesti e del fatto che si puo anche comprare meno del fabbisogno, una funzoneobiettivo possibile e:

0.2|V − 15000|+ |P − 1300|+ 3|A − 2900|,

dove V , P , A sono rispettivamente i quantitativi totali di viti, plastica e ac-ciaio acquistati. I valori assoluti introducono caratteristiche di non linearita nelmodello che devono essere opportunamente gestite.

Siccome i fornitori hanno a disposizione lotti dai contenuti standard, unascelta naturale di variabili per descrivere il “piano di approvvigionamento” e:

x1, x2, x3, x4,

dove xi = numero di lotti acquistati dal fornitore Fi. Per gestire i valori as-soluti sono necessarie tre variabili ausiliarie yV , yP , yA. Si noti che |X | =max(X,−X), quindi i valori assoluti si gestiscono con tecniche simili a quelleusate per i problemi min / max. La scelta tra i fornitori F2+F4 e F1 e modellatacon una variabile logica z1; z1 = 1 iff l’azienda si rifornisce presso F1.

Il modello e il seguente:

min 0.2yV + yP + 3yA

soggetto a(Vincoli per gestire i valori assoluti)

50x1 + 30x2 + 25x3 + 10x4 − 15000 ≤ yV

−50x1 − 30x2 − 25x3 − 10x4 + 15000 ≤ yV

3x1 + 4x2 + x3 + 8x4 − 1300 ≤ yP

−3x1 − 4x2 − x3 − 8x4 + 1300 ≤ yP

5x1 + 7x2 + 3x3 + x4 − 2900 ≤ yA

−5x1 − 7x2 − 3x3 − x4 + 2900 ≤ yA

(Vincolo logico — grande M)

x2 + x4 ≤ M(1 − z1)

x1 ≤ Mz1

x1, x2, x3, x4 ∈ Z+, yV , yP , yA ∈ Z+, z1 ∈ {0, 1}