Esercizi di modellazione per il corso di Ricerca Operativa 1

4 novembre 2005

2

Parte I

Esercizi

3

Modelli di programmazione lineareMolti problemi di interesse pratico si prestano ad essere descritti e risolti come modelli di programmazione matematica. Un modello (o programma) ` la dee scrizione di un problema che richiede di massimizzare (o minimizzare) una funzione di costo o protto su un certo dominio. La scrittura usuale ` e max z = f (x) soggetto a bi gi (x) = bi bi (oppure: min z = f (x)) (1)

i = 1, . . . , m,

(2) (3)

x = (x1 , . . . , xn ) X Rn .

Molti problemi di interesse pratico si prestano ad essere descritti e risolti come modelli di programmazione matematica. Un modello (o programma) ` la dee scrizione di un problema che richiede di massimizzare (o minimizzare) una funzione di costo o protto su un certo dominio. La scrittura usuale ` e max z = f (x) soggetto a bi gi (x) = bi bi (oppure: min z = f (x)) (4)

i = 1, . . . , m,

(5) (6)

x = (x1 , . . . , xn ) X Rn .

In un modello sono presenti: una serie di variabili di controllo in funzione delle quali viene formulato ogni altro elemento del modello; queste variabili, almeno in parte, corrispondono alle quantit` agendo sulle quali la soluzione verr` implemena a tata; una funzione obiettivo f (x) che determina un costo o protto legato alla soluzione; 5

6 una o pi` serie di vincoli, che correlano tra loro i valori delle variabili, imu ponendo condizioni di sica realizzabilit` e/o requisiti particolari richiesti a alla soluzione. Tra i modelli di programmazione matematica hanno particolare rilievo i modelli di programmazione lineare, nei quali la f (x) e le gi (x) sono espressioni lineari. Un modello di programmazione lineare ` quindi esprimibile sempre come en

max z =j=1

c j xj

(7)

soggetto a b i aij xj = bi j=1 bin

i = 1, . . . , m,

(8) (9)

x = (x1 , . . . , xn ) X Rn .

I campi di esistenza delle variabili xj sono di solito di tipo continuo (spesso non negativo) oppure intero non negativo (xj Z+ ), oppure binario (xj {0, 1}) a seconda del tipo di decisione che tali variabili modellano. La particolarit` dei modelli lineari ` legata alla loro maggiore semplicit`, a e a che li rende pi` facilmente risolvibili rispetto ai modelli non lineari; in eetti u sono ormai disponibili pacchetti software commerciali in grado di risolvere in modo eciente programmi lineari di notevoli dimensioni (intese come quantit` a di variabili e di vincoli). Questo rende spesso preferibile, per la risoluzione di un problema, lo sviluppo di un modello lineare anche quando un modello non lineare potrebbe essere pi` compatto. u Lo sviluppo di un modello di programmazione lineare parte dallanalisi di una situazione reale (pi` o meno schematizzata) e, in modo simile a quanto accade u nello sviluppo di una procedura software, richiede di identicare le variabili di controllo ed i rispettivi domini, i vincoli e la funzione obiettivo. Non ci sono regole rigide da seguire: il modello nale nasce spesso in particolare nela caso di situazioni complesse per ranamenti successivi.ESERCIZIO 1. Un gruppo di amici dovendo fare una gita ha deciso di mettere cibi e bevande in un unico zaino da 10 Kg. Lo zaino pu` essere riempito con o

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. luno) 5. Acqua minerale (bottiglie da 1 l.) 6. Pacchi di biscotti (confezioni da 500 g.) Dopo unindagine tra i partecipanti alla gita (si poteva dare un voto da 1 a 100 ad ogni prodotto) sono stati determinati i seguenti punteggi.

7 Prodotto Cioccolata Succhi di frutta Lattine di birra Punti 10 30 6 Prodotto Panini imbottiti Acqua minerale Pacchi di biscotti Punti 20 20 8

Per non scontentare nessuno si ` deciso di portare almeno: e 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 punteggio rispettando il vincolo di capacit` dello zaino. aESERCIZIO 2. Lacciaieria PLASTIK deve evadere un ordine di 1000 tonnellate di acciaio INOX. Per questa produzione servono manganese (almeno l1% in peso), cromo (almeno il 18%) e molibdeno (almeno il 2%). I fornitori di metalli non ferrosi vendono per esigenze di mercato questi prodotti in tre tipi di confezioni dierenti. La prima confezione contiene 2 Kg. di manganese, 2 Kg. di cromo e 1 Kg. di molibdeno e costa 10 euro. La seconda confezione contiene 2 Kg. di manganese, 3 Kg. di cromo e 1 Kg. di molibdeno e costa 15 euro. La terza confezione contiene 1 Kg. di manganese, 2 Kg. di cromo e 5 Kg. di molibdeno e costa 20 euro. Formulare il modello di Programmazione Lineare per minimizzare il costo di acquisto delle confezioni. ESERCIZIO 3. Unazienda produce tre modelli 1, 2 e 3 di un certo prodotto. Ciascun modello richiede due tipi di materiali grezzi (A e B) di cui sono disponibili rispettivamente 4000 e 6000 unit`. In particolare, per produrre una a unit` del modello 1 sono necessarie 2 unit` di A e 4 unit` di B; per una unit` a a a a del modello 2 sono necessarie 3 unit` di A e 2 unit` di B; per una unit` del a a a modello 3 sono necessarie 5 unit` di A e 7 di B. Il modello 1 richiede, per a ogni unit` prodotta, il doppio di forza lavoro rispetto al modello 2 e il triplo a rispetto al modello 3. La forza lavoro presente in azienda ` in grado di produrre e al massimo lequivalente di 700 unit`/giorno del modello 1. Il settore marketing a dellazienda ha reso noto che la domanda minima per ciascun modello ` rispete tivamente di 200, 200 e 150 unit`. Il protto unitario di ogni modello ` di 30, a e 20 e 50 euro, rispettivamente. Formulare il programma lineare per pianicare la produzione giornaliera massimizzando il protto.

La casa editrice ANALFABETA pubblica un quotidiano che viene distribuito da quattro centri di smistamento S1 , S2 , S3 , S4 che richiedono rispettivamente almeno 100000, 150000, 50000 e 75000 copie. Il giornale viene stampato in tre tipograe T1 , T2 , T3 che producono rispettivamente al massimo 125000, 180000 e 70000 copie I costi per la spedizione sono di 2 euro/Km. per giornale e le distanze tra le tipograe ed i centri di smistamento sono rispettivamente di 20, 25, 15 e 5 Km.ESERCIZIO 4.

8 per la prima tipograa, di 12, 14, 18 e 30 Km per la seconda, e di 19, 11, 40 e 12 Km per la terza. (a) Formulare il modello di Programmazione Lineare per pianicare le spedizioni a costo totale minimo. (b) Si denisca il costo di approvvigionamento di un centro di smistamento come il costo totale delle spedizioni verso quel centro. Formulare il modello di Programmazione Lineare che minimizza il massimo costo di approvvigionamento.ESERCIZIO 5. Un motel autostradale, dovendo garantire un servizio continuato 24 ore su 24, ha bisogno di un numero minimo di inservienti per ogni ora del giorno secondo la seguente tabella.

Fascia oraria 02-06 06-10 10-14

Numero min. 4 8 10

Fascia oraria 14-18 18-22 22-02

Numero min. 7 12 4

Ciascun inserviente lavora 8 ore consecutive al giorno. Formulare il modello di Programmazione Lineare per garantire la presenza richiesta utilizzando il minor numero possibile di inservienti. Scrivere il modello in programmazione lineare del seguente problema. Un caporeparto di unocina di unazienda meccanica deve pianicare lesecuzione di cinque lotti su di una macchina della durata rispettivamente di 5 minuti, 7 minuti, 4 minuti, 7 minuti e 10 minuti. La sequenza di esecuzione (1, 2, 3, 4, 5) ` data e non ci pu` essere sovrapposizione e o temporale fra i lotti. Il primo lotto ha come ora di consegna desiderata le 10.32, il secondo le 10.38, il terzo le 10.42, il quarto le 10.52 ed il quinto le 10.57. Sia lerrore di un lotto pari al valore assoluto della dierenza tra il suo tempo di ne lavorazione e lora di consegna. Si vuole minimizzare la somma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle 8.30).ESERCIZIO 6. ESERCIZIO 7.

Scrivere il modello in programmazione lineare del seguente problema. Unazienda alimentare deve pianicare la produzione di un prodotto per i prossimi 4 mesi. Non ci sono giacenze in magazzino allinizio del periodo e non ce ne devono essere alla ne dei 4 mesi. La domanda mensile prevista ` di e 120 ton, 160 ton, 300 ton e 200 ton rispettivamente (ipotesi: la produzione viene stoccata e rilasciata interamente a ne mese). La capacit` produttiva mensile ` a e 140 ton, 150 ton, 140 ton e 160 ton rispettivamente ad un costo di 10 euro/ton. In caso di necessit` ` possibile produrre in straordinario aumentando la capacit` ae a mensile di (al pi`) 50 ton, 75 ton, 70 ton e 80 ton rispettivamente. La produzione u straordinaria ha un costo addizionale di 6 euro/ton. Inoltre, per garantire una produzione omogenea si vuole che la produzione ordinaria di ciascun mese sia almeno pari al 10% della produzione totale dei primi tre. Le eventuali giacenze a ne mese costano 5 euro/ton. Lobiettivo ` quello di pianicare la produzione e di costo minimo. Lo stato di Islandia ha quattro industrie esportatrici: acciaio, motori, elettronica e plastica. Il ministro delleconomia di questo stato vuole massimizzare il saldo esportazioni-importazioni. La moneta di IslandiaESERCIZIO 8.

9 ` il klutz. I prezzi in klutz sul mercato mondiale per unit` di acciaio, moe a tori, elettronica e plastica sono rispettivamente 500, 1500, 300 e 1200. La produzione di una unit` di acciaio richiede 0.02 unit` di motori, 0.01 unit` a a a di plastica, 250 klutz di materie prime acquistate sul mercato mondiale e mezzo anno-uomo di manodopera. La produzione di una unit` di motori richiede a 0.8 unit` di acciaio, 0.15 unit` di elettronica, 0.11 unit` di plastica, 300 klutz a a a di materie prime acquistate sul mercato mondiale e un anno-uomo di manodopera. La produzione di una unit` di prodotti elettronici richiede 0.01 unit` a a di acciaio, 0.01 unit` di motori, 0.05 unit` di plastica, 50 klutz di materie a a prime acquistate sul mercato mondiale e mezzo anno-uomo di manodopera. La produzione di una unit` di plastica richiede 0.03 unit` di motori, 0.2 unit` a a a di acciaio, 0.05 unit` di elettronica, 300 klutz di materie prime acquistate sul a mercato mondiale e due anni-uomo di manodopera. La produzione di motori ` limitata a 650000 unit`, quella di plastica a 60000 unit`. La manodopera e a a totale disponibile in Islandia ` di 830000 uomini per anno. Acciaio, motori, e elettronica e plastica non possono essere importati, ma devono essere prodotti allinterno.ESERCIZIO 9.

Scrivere il modello in programmazione lineare del seguente problema. Si consideri un territorio sul quale siano localizzati 7 punti di domanda (ad es. 7 citt`) indicati in tabella con 1, 2, 3, 4, 5, 6, 7. Si considerino, inoltre, 5 punti a di oerta indicati in tabella con A, B, C, D, E nei quali potrebbero essere aperti dei centri vendita di unimpresa di distribuzione. Tale impresa ` interessata a e soddisfare la domanda sopramenzionata in modo tale che i clienti non percorrano pi` di 30 minuti di auto per raggiungere almeno uno dei centri vendita. In u tabella, per ogni coppia di punti di domanda e di oerta, viene indicato il tempo auto necessario. Limpresa ha inoltre fatto sapere che accetter` soluzioni che prevedano lata tivazione del centro vendita B solo se ` gi` attivo uno dei centri C o D. e a Lapertura dei centri vendita costa rispettivamente (in miliardi di lire): A = 310, B = 250, C = 260, D = 330, E = 280. Lobiettivo dellimpresa ` di minimizzare i costi di apertura dei centri vendita e garantendo il fatto che che tutti i punti di domanda vengano serviti. A 41 25 21 21 11 47 37 B 33 12 43 42 23 23 47 C 24 22 34 39 24 19 51 D 29 58 54 26 29 16 26 E 58 41 18 18 53 31 19

1 2 3 4 5 6 7

ESERCIZIO 10. Una raneria produce benzina verde e super a partire da due tipi di greggio A e B, usando tre impianti. Il primo impianto pu` proo durre 2 barili di verde e 3 di super a partire da 4 barili di greggio tipo A e 3 barili di greggio tipo B. Il secondo impianto pu` produrre 4 barili di verde o e 2 di super a partire da 3 barili di A e 4 barili di B. Il terzo pu` produrre o

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 specicate. La benzina verde viene venduta a 40$/barile, la super a 50$/barile. Sono disponibili per questo mese 5000 barili di greggio A e 6000 barili di greggio B. Per esigenze legate ad altre lavorazioni, almeno uno tra gli impianti deve produrre non pi` di 1000 u barili. Formulare il programma lineare per massimizzare il protto legato alla produzione mensile. Unazienda agricola produce mais, soia e grano in tre tenute A, B, C. La tenuta A dispone di 600 ettari di terreno e di una riserva di 8106 m3 di acqua. La tenuta B ha 700 ettari di terreno e 5 106 m3 di acqua. La terza dispone di 450 ettari e di 6 106 m3 . Le produzioni di mais, soia e grano garantiscono rispettivamente protti di 5, 7 e 6 Keuro/ettaro. I consumi di acqua sono di 20000 m3 /ha per il mais,10000 m3 /ha per la soia e 10000 m3 /ha per il grano. Le direttive della comunit` europea richiedono che: aESERCIZIO 11.

almeno una tenuta lasci 200 ettari di terreno incolto, e lestensione complessiva del terreno coltivato a soia dallazienda non superi il 40% del totale del suolo coltivato. Formulare il programma lineare per la massimizzazione del protto.ESERCIZIO 12. Una ditta ha la possibilit` di attivare, per lanno corrente, a la produzione di quattro tipi di prodotti A, B, C e D. Per ogni tipo di produzione, se attivata, la ditta si impegna a produrre un quantitativo minimo pari rispettivamente a 1000, 1500, 3000 e 2000 unit`. La produzione di A, B, C a e D richiede un costo sso per lattivazione delle rispettive linee di produzione ed una quantit` di forza lavoro per ogni unit` prodotta, ed ogni unit` venduta a a a fornisce un protto, come specicato dalla seguente tabella (in euro).

Prodotto Costo sso Forza lavoro unit. Protto unit. A 14500 10 50 B 10000 15 60 C 8000 5 55 D 9000 14 80 La ditta dispone per lanno in corso di 200000 unit` complessive di forza lavoro. a Inoltre i committenti per la quale essa lavora richiedono che nel caso venga attivata la produzione di A venga anche prodotto almeno uno tra C o D, almeno nei quantitativi minimi sopra indicati. Formulare il programma lineare per decidere le produzioni da attivare e pianicarne i quantitativi al ne di massimizzare il saldo costi-protti.ESERCIZIO 13. Scrivere il modello in programmazione lineare del seguente problema. In una centrale elettrica sono a disposizione tre generatori ed ogni giorno si deve decidere quali usare solo di giorno e quali anche di notte per assicurare una produzione di almeno 4000 megawatts di giorno e di almeno 2800 megawatts di notte. Luso di un generatore comporta la presenza di personale tecnico che sorvegli il suo funzionamento; tale personale viene retribuito in maniera dierente a seconda dei turni necessari (12h/24h) e del tipo di generatore. Tali costi di attivazione sono riportati nella tabella che segue (in migliaia di lire) insieme al costo per ogni megawatt prodotta.

11 Costo attivazione giorno giorno/notte 800 1200 700 1000 900 1400 Costo al megawatt 4 6 7

Generatore A Generatore B Generatore C

Il generatore A ha una capacit` produttiva di 2500 megawatts al giorno ma a questa capacit` scende a 2000 megawatts se il generatore viene utilizzato sia di a giorno che di notte. Analogamente, il generatore B ha una capacit` produttiva a di 2000 megawatts al giorno ma questa capacit` scende a 1500 megawatts se il a generatore viene utilizzato sia di giorno che di notte. Inne, il generatore C ha una capacit` produttiva di 3000 megawatts al giorno ma questa capacit` scende a a a 2500 megawatts se il generatore viene utilizzato sia di giorno che di notte. Si vuole minimizzare il costo complessivo.ESERCIZIO 14. Scrivere il modello in programmazione lineare del seguente problema. Un caporeparto di unocina di unazienda meccanica deve pianicare lesecuzione di cinque lotti su di una macchina della durata rispettivamente di 5 minuti, 7 minuti, 4 minuti, 7 minuti e 10 minuti. Non ci pu` essere o sovrapposizione temporale fra i lotti. Il primo lotto ha come ora di consegna desiderata le 10.32, il secondo le 10.38, il terzo le 10.42, il quarto le 10.52 ed il quinto le 10.57. Sia lerrore di un lotto pari al valore assoluto della dierenza tra il suo tempo di ne lavorazione e lora di consegna. Si vuole minimizzare la somma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle 8.30). ESERCIZIO 15. Una ditta che si occupa di riparazioni deve pianicare le assunzioni per i prossimi 5 mesi. Allinizio la ditta dispone di 20 operai esperti; ogni operaio esperto fornisce 150 ore di lavoro al mese e percepisce uno stipendio mensile di 1000 euro. Un operaio neoassunto, durante il primo mese di servizio percepisce uno stipendio di 500 euro e non fornisce in pratica lavoro utile; per questo primo mese gli viene invece aancato un lavoratore esperto per insegnargli il mestiere. Ogni lavoratore esperto che svolge aancamento rende per 70 ore di lavoro al mese (anzich 150). Dopo il mese di apprendistato e i lavoratori neoassunti diventano esperti, con pari abilit` lavorativa e stipena dio. Le quantit` di ore/lavoro da coprire per i prossimi 5 mesi sono rispettia vamente di 2000, 4000, 7000, 3000, 3500 ore. Inne, se si assumono almeno 10 persone nel corso dei primi due mesi, lazienda pu incassare un contributo o statale di 100000 euro. Formulare il programma lineare che consente di pianicare le assunzioni riducendo al minimo i costi del personale nei prossimi cinque mesi. ESERCIZIO 16. Lazienda PC4All produce pc e deve acquistare le scorte di materie prime necessarie per la produzione dei case. Per produrre i case nel mese corrente sono necessari i seguenti materiali:

viti: 15000 unit`; a plastica: 1300 kg.; acciaio: 2900 kg.

12 Per eettuare gli acquisti lazienda si pu` appoggiare a quattro fornitori, i o quali le forniscono le materie prime in lotti contenenti le seguenti quantit` di a materiale: F1 F2 F3 F4 viti 50 30 25 10 plastica 3 4 1 8 acciaio 5 7 3 1

Nellottica di gestire al meglio il proprio magazzino, la PC4All intende avere, alla ne del mese, la minor quantit` di materiale non utilizzato possibile e, a tal a ne, ` disposta anche a comprare una quantit` di materie prime inferiore alle e a proprie necessit`. Il costo per lo stockaggio o per il mancato acquisto di una a unit` di materiale ` il seguente: a e Viti Plastica Acciaio 0.2 euro/pezzo 1 euro/kg. 3 euro/kg.

Per motivi commerciali lazienda, se acquista dei lotti di materiale dal fornitore F1, ` impossibilitata a rifornirsi dai fornitori F2 ed F4. e Formulare il modello di programmazione lineare che minimizzi i costi derivanti dallo scostamento tra le quantit` di materiali acquistate e quelle necessarie, a tenendo conto che non ` possibile comprare porzioni di lotto di materiali. e

Parte II

Soluzioni

13

Modelli di programmazione lineare1. Le variabili di controllo determinano la struttura della soluzione di un problema, permettendone la realizzazione. Quindi in questo caso ` naturale denire le e variabili x1 , x 2 , x 3 , x 4 , x 5 , x 6 , con il signicato xi = unit` di alimento (i) caricate nello zaino. a Con questa scelta di variabili si pu` ottenere il seguente modello, nel quale o compaiono due serie di vincoli: (1) un vincolo relativo alla capacit` dello zaino, a che non pu` essere superata, e (2) vincoli relativi ai quantitativi minimi di o alimenti da caricare. max 10x1 + 30x2 + 6x3 + 20x4 + 20x5 + 8x6 soggetto a 1 1 1 1 x1 + x2 + x3 + x4 + x5 + x6 10 2 3 10 2 x1 2, x2 2, x3 6, x4 10, x6 2, x1 , . . . , x 6 Z + . 2. Le variabili pi` naturali sono x1 , x2 , x3 , dove xi = numero di confezioni di u tipo i acquistato. A volte pu` non essere evidente quale sia la scelta di vario abili pi` naturale. Una buona regola euristica ` spesso la seguente: una u e denizione di variabili ` soddisfacente quando essa permette di scrivere in modo e semplice la funzione obiettivo (o comunque i vincoli pi` signicativi) del modu ello. Ad esempio, in questo caso usare variabili che rappresentano le quantit` di a materiali (manganese, cromo, molibdeno) acquistate anzich` le confezioni non e sarebbe soddisfacente, in quanto la funzione obiettivo risulterebbe molto dicile da esprimere. Con la scelta di variabili indicata invece, si ottiene il modello min 10x1 + 15x2 + 20x3 15 (1.1) (1.2)

16 soggetto a 2x1 + 2x2 + x3 10000 2x1 + 3x2 + 2x3 180000 x1 + x2 + 5x3 20000 x1 , x 2 , x 3 Z + , dove i vincoli (2.1), (2.2) e (2.3) rappresentano i quantitativi minimi di manganese, cromo e molibdeno da garantire, rispettivamente. 3. Le variabili x1 , x2 , x3 sono sucienti a modellare il problema, con xi = numero di unit` di tipo i prodotte. Quindi si ha a max 30x1 + 20x2 + 50x3 soggetto a 2x1 + 3x2 + 5x3 4000 4x1 + 2x2 + 7x3 6000 1 1 x1 + x2 + x3 700 2 3 x1 200, , x2 200, x1 , x 2 , x 3 Z + , (3.1) (3.2) x3 150 (3.3) (2.1) (2.2) (2.3)

con i vinvoli (3.1), (3.2) e (3.3) che rappersentano i vincoli sulla disponibilit` di a materie prime, sulla forza lavoro disponibile e sui requisiti minimi di produzione stabiliti dal marketing, rispettivamente. 4. (a) Per come sono specicati i costi di spedizione, la scelta naturale per la denizione delle variabili di controllo ` la seguente: e xij = numero di copie spedite da Ti a Sj . In questo modo il modello diventa3 4

maxi=1 j=1

cij xij

soggetto a x11 + x12 + x13 + x14 125000 x21 + x22 + x23 + x24 180000 x31 + x32 + x33 + x34 70000 x11 + x21 + x31 100000 x12 + x22 + x32 150000 x13 + x23 + x33 50000 x14 + x24 + x34 75000 xij Z+ , i, j. (4.2)

(4.1)

17 I vincoli (4.1) e (4.2) impongono che ogni tipograa spedisca non pi` giornali u di quanti ne stampa (per la realizzabilit` sica della soluzione) e che ogni a centro ne riceva una quantit` pari almeno al proprio fabbisogno. I costi cij a sono ricavati dalla matrice delle distanze indicata dal testo: cij = 2(distanza Ti -Sj ). (b) Lobiettivo specicato pone la necessit` di scrivere un programma di minimo a con una funzione obiettivo del tipo3

maxj i=1

cij xij .

Tale espressione ` per` non lineare e quindi proibita nel tipo di modelli qui e o trattato. Per conservare la linearit` del modello, occorre introdurre una variabile a ausiliaria 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 x11 + x21 + x31 100000 x12 + x22 + x32 150000 x13 + x23 + x33 50000 x14 + x24 + x34 750003

(4.1 )

(4.2 )

cij xij yi=1

j = 1, . . . , 4 y0

(4.3)

xij Z+ , i, j,

La variabile ausiliaria y ed i vincoli (4.3) permettono di gestire lobiettivo min / max conservando la linearit` del modello: in ogni soluzione ottima a di questo programma lineare, il valore assunto da y coincide esattamente con maxj { n cij xij }. I vincoli (4.1 ) e (4.2 ) hanno il ruolo gi` noto. a i=1 5. Questo problema richiede, per essere modellato in modo semplice, una denizione accorta di variabili. Occorre tener presente che: (1) esiste una soluzione ottima dove ogni inserviente comincia lavorare allinizio di una fascia oraria e ne copre esattamente due; (2) ogni inserviente ha (naturalmente) un unico orario di inizio turno. Quindi ` possibile denire: e 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 + x 6 4 x1 + x 2 8 x2 + x3 10 x3 + x 4 7 x4 + x5 12 x5 + x 6 4 x1 , . . . , x 6 Z + .

(5.1) (5.2) (5.3) (5.4) (5.5) (5.6)

Poich ogni inserviente che comincia il turno nella fascia i copre le fasce i ed e i + 1 (modulo 6), i vincoli (5.1)(5.6) garantiscono la copertura richiesta in ogni fascia. La funzione obiettivo rappresenta esattamente il numero di inservienti necessari. 6. Il problema richiede di scrivere un modello in grado di determinare gli istanti di inizio lavirazione dei lotti in esame; si pu` assumere come zero del tempo o lora delle 8:30, per cui i lotti hanno date di scadenza (espresse in minuti) di 122, 128, 132, 142 e 147. Una serie di variabili ` necessaria per rappresentare i e tempi di inizio lavorazione: ti = istante di lavorazione (in minuti dalle 8:30) del lotto i. Inoltre lerrore del lotto i ` dato da i = |ti + pi di |, dove pi e di indicano e rispettivamente il tempo di lavorazione e la scadenza del lotto. La funzione obiettivo ` quindi del tipo e5

|ti + pi di |.i=1

Questo genere di funzione ` non lineare quindi occorre nuovamente ricorrere ad e un espediente per rappresentare i valori assoluti in un modello lineare. Ricordando che |x| = max(x, x), si pu` pensare di utilizzare la stessa tecnica usata o per obiettivi di tipo min / max. Si introducono quindi le variabili i = errore del lotto i. Il modello ` il seguente. e min 1 + 2 + 3 + 4 + 5

19 soggetto a t1 + 5 t 2 t2 + 7 t 3 t3 + 4 t 4 t4 + 7 t 5 (1 2) (2 3) (3 4) (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) ti 0, i 0, i = 1, . . . , 5. (6.2)

I vincoli (6.1) garantiscono il rispetto della sequenza di lavorazione che, secondo il testo, ` predeterminata, mentre i vincoli (6.2) vincolano i i ad assumere il e valore assoluto di ti + pi di . 7. Il problema richiede in pi`, rispetto ad altri problemi di produzione gi` risolti, u a la gestione di scorte di magazzino in un certo numero di periodi di tempo (mesi, in questo caso). Questi problemi, comuni nel settore della pianicazione della produzione, vengono detti multiperiodali. In questi casi ` utile (anche se non e sempre indispensabile) disporre di un insieme di variabili che rappresentano esplicitamente il livello delle giacenze da gestire alla ne (o allinizio) di ogni periodo. Il problema in esame pu` essere modellato utilizzando le seguenti o variabili. xi = si = yi = produzione ordinaria (in ton.) per il mese i = 1 . . . , 4, produzione straordinaria (in ton.) per il mese i = 1, . . . , 4, giacenze in magazzino alla ne del mese i = 1, . . . , 3.

Una y4 non ` stata denita, in quanto ` esplicitamente richiesto che essa valga e e zero in ogni soluzione ammissibile. Occorre modellare luso della produzione ordinaria e straordinaria, rispettarne i limiti e correlarle alla domanda mensile (che deve essere soddisfatta) ed alle giacenze in magazzino. In base alle variabili specicate, un modello possibile ` e4 4 3

min 10i=1

xi + 16i=1

si + 5i=1

yi

20 soggetto a x1 + s 1 = 120 + y1 (7.1)

x2 + s2 + y1 = 160 + y2 x3 + s3 + y2 = 300 + y3 x4 + s4 + y3 = 2003

xi 0.1i=1

(xi + si )

i = 1, . . . , 4

(7.2) (7.3) (7.4)

x1 140, x2 150, x3 140, x4 160, s1 50, s2 75, s3 70, s4 80, xi , si , yi 0, i = 1, . . . , 4.

I vincoli (7.1) svolgono il compito fondamentale di correlare la produzione di ogni mese con livelli di giacenze e domanda, esprimendo il bilancio (produzione mensile)+(giacenze a mese precedente) = (domanda mese)+(giacenze a ne mese). Le serie successive di vincoli sono piuttosto semplici ed esprimono il requisito sui livelli di produzione ordinaria minimi mensili (10% del totale sui primi tre mesi) e sulle capacit` produttive massime (ordinaria e straordinaria) per i quattro a mesi. 8. Indicando i prodotti con A, M , E, P (Acciaio, Motori, Elettronica, Plastica) si possono riassumere i requisiti per la produzione nella seguente tabella. P Anni uomo Mat. prime 0.01 0.5 250 0.8 0.15 0.11 1.0 300 0.01 0.01 0.05 0.5 50 0.2 0.03 0.05 2.0 300 A M 0.02 E

A M E P

Poich acciaio, motori, elettronica e plastica vanno prodotti internamente e non e acquistati, ` conveniente scorporare la produzione per uso interno da quella per e esportazioni, denendo le variabili xA , x M , x E , x P , yA , yM , yE , yP , dove xi = unit` di prodotto i realizzate per esportazione, i {A, M, E, P }, a yi = unit` di prodotto i realizzate per uso interno, i {A, M, E, P }. a Dallanalisi del testo, occorre garantire che: la produzione interna di ogni prodotto sia suciente a supportare la produzione totale; le quantit` di motori e plastica prodotte non eccedano i limiti imposti; a

21 il piano produttivo non ecceda il monte-ore diponibile. Con le variabili precedentemente denite, 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 ) xM + yM 650000 xP + yP 600000 (8.1)

(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 supportare la produzione totale; i vincoli (8.2) impongono i limiti richiesti alle produzioni di motori e plastica, ed inne il vincolo (8.3) impone di non eccedere il monte-ore disponibile. 9. Lapertura di un centro ` una decisione che dierisce da quelle modellate no e a questo momento, per il fatto di essere puramente binaria (un centro viene aperto oppure no, non esistono casi intermedi). Per modellare questo genere di decisioni, ` possibile inserire nei programmi lineari variabili binarie, cio` interi e e ` con valori limitati allinsieme {0, 1}. E da notare che queste variabili, a parte il loro 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 per mezzo di esperessioni lineari puramente algebriche. Inoltre, non ` consentito e in alcun modo introdurre prodotti del tipo (variabile logica)(altre variabili), errore sorprendentemente comune. Il problema in esame si pu` modellare con cinque variabili binarie A, B, C, o D, E che rappresentano lapertura (variabile= 1) o la non-apertura (variabile= 0) del rispettivo centro. min 310A + 250B + 260C + 330D + 280E

22 soggetto a C +D 1 A+B+C 1 A+E 1 A+D+E 1 A+B+C +D 1 B+C +D 1 D+E 1 B C +D (9.1) (9.2) (9.3) (9.4) (9.5) (9.6) (9.7) (9.8)

I vincoli (9.1)(9.7) modellano operatori logici di tipo or: in base ai tempi di percorrenza dati, per servire il punto 1 occorre aprire C oppure D; per servire il punto 2 occorre aprire A oppure B oppure C, e cos` via. Il vincolo (9.8) modella unimplicazione logica B = C D (il requisito B apre solo se . . . specicato dal testo: confrontare con la tabella di verit` delloperatore logico). a Si noti anche che nellinsieme di vincoli (9.1)(9.8) esistono vincoli ridondanti: ad esempio, (9.1) implica (9.5), (9.6) e (9.8); questi tre vincoli potrebbero quindi essere rimossi dal modello. Questa operazione non ` strettamente e necessaria ai ni della correttezza del modello, ma ` desiderabile in ambito e applicativo, in quanto semplica la risoluzione del modello. 10. La denizione di variabili che porta a realizzare il modello pi` conciso ` probu e abilmente la seguente: xi = yi = numero di lavorazioni svolte allimpianto i = 1, 2, 3. 1 i limpianto i ` limitato a 1000 barili, e 0 altrimenti, i = 1, 2, 3.

La denizione suggerita di xi permette di gestire il funzionamento degli impianti con le proporzioni specicate, senza ricorrere a vincoli addizionali. Il modello risulta max 40(2x1 + 4x2 + 2x3 ) + 50(3x1 + 2x2 + 2x3 ) soggetto a 4x1 + 3x2 + 3x3 5000 3x1 + 4x2 + 3x3 6000 y1 + y 2 + y 3 1 5x1 1000y1 + M (1 y1 ) 6x2 1000y2 + M (1 y2 ) 4x3 1000y3 + M (1 y3 ) xi 0, yi {0, 1}, i = 1, 2, 3. (10.3) (10.1) (10.2)

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 sia limitato a 1000 barili. I vincoli (10.3) svolgono limportante funzione di collegare i valori delle variabili binarie yi con i valori delle xi ; la costante M (detta spesso big-M) ` una costante estremamente grande. Si noti che ad esempio il primo e vincolo di questa serie implica: y1 = 1 = y1 = 0 = 5x1 1000, 5x1 M (cio` 5x1 non vincolato). e

Questa tecnica del big-M ` comunemente usata per correlare variabili binarie e e variabili di altro tipo. ` 11. E necessario scorporare il prodotto sia per tipologia che per tenuta, altrimenti non ` possibile gestire le estensioni coltivate e le riserve dacqua. Sono quindi e necessarie 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 variabili binarie yA , yB ed yC verranno usate per determinare quale tenuta lascer` 200 a ettari incolti (yj = 1 i la tenuta j lascia 200 ettari incolti). Il modello ` il e seguente. max 5(xM A + xM B + xM C ) + 7(xSA + xSB + xSC ) + 6(xGA + xGB + xGC ) soggetto a xM A + xSA + xGA 600 200yA xM B + xSB + xGB 700 200yB xM C + xSC + xGC 450 200yC 20000xM A + 10000xSA + 10000xGA 8 106 20000xM B + 10000xSB + 10000xGB 5 106 20000xM C + 10000xSC + 10000xGC 6 10 xSA + xSB + xSC 0.4i=M,S,G j=A,B,C 6

(11.1)

(11.2)

xij

(11.3) (11.3)

yA + y B + y C 1 xij 0, yj {0, 1}, i = M, S, G, j = A, B, C.

I vincoli (11.1) impediscono di coltivare in una tenuta pi` del totale del suolo u disponibile; i vincoli (11.2) impediscono di coltivare pi` di quanto si possa irriu gare con le scorte dacqua delle varie tenute; il vincolo (11.3) stabilisce che non pi` del 40% del suolo coltivato in totale pu` essere messo a soia, ed il vincou o lo (11.3) impone che almeno una tenuta lasci 200 ha di suolo incolto. Si noti che in questo caso non ` necessario introdurre un big-M per collegare le yj con le xij : e ` suciente denire nel modo opportuno i secondi membri dei vincoli (11.1). e

24 12. Il problema proposto riguarda la pianicazione di certi tipi di produzione con costi ssi imputabili alla preparazione degli impianti produttivi e costi variabili legati alle quantit` prodotte. La decisione di attivare o meno la produzione di a A, B, C o D ` di tipo vero/falso, e quindi si pu` modellare con variabii binarie e o yi = 1 i si attiva la produzione di i {A, B, C, D}.

Occorre poi determinare anche i volumi prodotti, rappresentabili mediante unaltra serie di variabili xi = numero di unit` di tipo i prodotte, i {A, B, C, D}. a

Tenuto conto dei dati su quantitativi minimi, protti unitari e forza lavoro dati dal 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 xA M y A xB M y B xC M y C xD M y D 10xA + 15xB + 5xC + 14xD 2000000 yA y C + y D xi Z+ , yi {0, 1}, i {A, B, C, D}.

(12.1)

(12.2)

(12.3) (12.4)

I vincoli (12.1) impongono il rispetto dei quantitativi minimi qualora un tipo di produzione venga attivato, mentre i vincoli (12.2) assicurano che non vengano pianicati quantitativi per produzioni non attivate. Il vincolo (12.3) impone di non eccedere la quantit` di forza lavoro disponibile; il vincolo (12.4) modella a limplicazione logica yA = yC yD , come richiesto dal testo. 13. Assumendo i turni possibili specicati dal testo, si possono denire due serie di variabili binarie: xi =1 i il generatore i ` utilizzato di giorno, i = A, B, C, e yi =1 i il generatore i ` utilizzato sia di giorno che di notte, i = A, B, C. e

25 Inoltre, essendoci un costo/MW, occorrono variabili in grado di specicare il numero di MW prodotti dai generatori. Per mantenere distinte la produzione diurna 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 + y A 1 xB + y B 1 xC + y C 1 WA 2500xA , WB 2000xB , WC 3000xC , ZA 2000yA ZB 1500yB ZC 2500yC (13.3) (13.1)

(13.2)

WA + WB + WC + ZA + ZB + ZC 4000 ZA + ZB + ZC 2800 Wi , Zi 0, xi , yi {0, 1}, i = A, B, C.

I vincoli (13.1) impongono che ogni generatore funzioni secondo al pi` un tipo u di turno. I vincoli (13.2) ssano i limiti dellerogazione di potenza come da turno per ogni generatore; si noti anche qui luso di tecniche in stile big-M: ad esempio, il primo vincolo di questa serie implica xA = 1 = xA = 0 = WA 2500, WA = 0.

Inne, i vincoli (13.3) impongono il soddisfacimento delle potenze minime per il giorno e per la notte. 14. In questo problema ` importante notare che la sequenza delle lavorazioni non e ` predeterminata; essa deve essere quindi determinata dalla soluzione del mode ello. Rispetto allesercizio 6, occorre una serie di variabili in pi`. Vengono qui u proposte due soluzioni possibili. (a) Una sequenza di lavorazione ` determinata quando, per ogni coppia (non e ordinata) {i, j} di lotti si ` in grado di determinare se i viene lavorato prima di e j (i j) o viceversa. Si possono quindi usare le variabili binarie xij = 1 i i j, i < j. Si usano inoltre tutte le variabili dellesercizio 6. Il valore delle variabili xij deve poi 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 minuti dalle 8:30) del lotto i.

5

mini=1

i

soggetto a

i t i + p i d i i (ti + pi di )

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

(14.1)

ti + pi tj + M (1 xij ) tj + pj ti + M xij

i < j, i = 1, . . . , 5 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 di vincoli (14.2) correlano i valori delle xij con le ti :

xij = 1 = xij = 0 =

t i + p i tj t j + p j ti

(i j), (j i).

(b) Alternativamente, si pu` osservare che una sequenza di lavorazione ` determio e nata quando ogni lotto ` assegnato ad una e una sola delle posizioni 1, 2, . . . , 5 e disponibili nellordine di lavorazione. Si possono allora utilizzare le seguenti variabili. xij = 1 se il lotto i ` in posizione j, 0 altrimenti, i, j = 1, . . . , 5; e [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 ogni lotto i (nota: questi sono dati). Con le variabili denite sopra si pu` scrivere il o seguente modello.

minj=1

[j]

27 soggetto a5

xij = 1j=1 5

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

xij = 1i=1 5

j = 1, . . . , 5

t[j] +i=1

pi xij t[j+1]5

j = 1, . . . , 45

(14.2)

[j]

t[j] +i=1 5

pi xij i=1 5

di xij di xiji=1

j = 1, . . . , 5 (14.3) j = 1, . . . , 5

[j] t[j] +i=1

pi xij

xi,j {0, 1}, i, j {1, . . . , 5},

t[j] , [j] 0, j {1, . . . , 5}.

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

pi xij = tempo di lavorazione del j-esimo lotto della sequenza.i=1

I vincoli (14.3) gestiscono i valori assoluti, sempre tenendo conto dellassegnazione lotti-posizioni; analogamente a prima, si ha5

di xij = scadenza del lotto in posizione j.i=1

15. Il problema richiede in pratica di gestire un pool di assunti/neoassunti che varia di mese in mese: ` un problema multiperiodale. Una soluzione ` un e e piano di assunzioni che permetta di coprire comunque il monte-ore richiesto nei vari mesi compatibilmente con lo svolgimento dellaancamento da parte degli esperti. Possiamo modellare la situazione con dieci variabili: y1 , y2 , y3 , y4 , y5 , x1 , x 2 , x 3 , x 4 , x 5 , dove yi = disponibilit` di esperti al mese i e xi = numero di persone assunte a al mese i. Modelliamo con una variabile logica z la scelta di ottenere o non ottenere il contributo statale. Come ulteriore considerazione, si noti che la x5 ` superua in quanto assumere allultimo mese ` un costo, non fornisce forza e e

28 lavoro sfruttabile entro lorizzonte temporale coperto dal modello e non inuisce sulla possibilit` di ottenere il contributo statale. In ogni soluzione ottima si avr` a a x5 = 0. In base alle variabili denite 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 y 1 150(y1 x1 ) + 70x1 2000 (Mese 2) y2 = y 1 + x1 x2 y 2 150(y2 x2 ) + 70x2 4000 (Mese 3) y3 = y 2 + x2 x3 y 3 150(y3 x3 ) + 70x3 7000 (Mese 4) y4 = y 3 + x3 x4 y 4 150(y4 x4 ) + 70x4 3000 (Mese 5) y5 = y 4 + x4 x5 y 5 150(y5 x5 ) + 70x5 3500 (Vincolo logico) x1 + x2 10z xi , yi Z + i, z {0, 1}

16. Lazienda in questione, a detta del testo, paga un costo sia per lo stoccaggio che per il mancato acquisto di materiali. Quindi, tenuto conto dei quantitativi

29 richiesti e del fatto che si pu` anche comprare meno del fabbisogno, una funzone o obiettivo possibile `: e 0.2|V 15000| + |P 1300| + 3|A 2900|, dove V , P , A sono rispettivamente i quantitativi totali di viti, plastica e acciaio acquistati. I valori assoluti introducono caratteristiche di non linearit` nel a modello che devono essere opportunamente gestite. Siccome i fornitori hanno a disposizione lotti dai contenuti standard, una scelta naturale di variabili per descrivere il piano di approvvigionamento `: e x1 , x 2 , x 3 , x 4 , dove xi = numero di lotti acquistati dal fornitore Fi . Per gestire i valori assoluti 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 quelle usate per i problemi min / max. La scelta tra i fornitori F2 +F4 e F1 ` modellata e con una variabile logica z1 ; z1 = 1 i lazienda si rifornisce presso F1 . Il modello ` il seguente: e 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 M z 1 x1 , x 2 , x 3 , x 4 Z + , yV , yP , yA Z + , z1 {0, 1}