Capitolo 1
Modelli di programmazione lineare
Molti problemi di interesse pratico si prestano ad essere descritti e risolti come modelli di programmazione matematica. Un modello (o programma) `e la de- scrizione di un problema che richiede di massimizzare (o minimizzare) una funzione di costo o profitto su un certo dominio. La scrittura usuale `e
max z = f (x) (oppure: min z = f (x)) (1.1)
soggetto a
gi(x)
≤ bi
= bi
≥ bi
i = 1, . . . , m, (1.2)
x = (x1, . . . , xn) ∈ X ⊆ Rn. (1.3)
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, cor- rispondono alle quantit`a agendo sulle quali la soluzione verr`a implemen- tata;
• una funzione obiettivo f (x) che determina un costo o profitto legato alla soluzione;
• una o pi`u serie di vincoli, che correlano tra loro i valori delle variabili, im- ponendo condizioni di fisica realizzabilit`a e/o requisiti particolari richiesti 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 `e quindi esprimibile sempre come max z =
n
X
j=1
cjxj (1.4)
1
soggetto a
n
X
j=1
aijxj
≤ bi
= bi
≥ bi
i = 1, . . . , m, (1.5)
x = (x1, . . . , xn) ∈ X ⊆ Rn. (1.6)
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`a dei modelli lineari `e legata alla loro maggiore semplicit`a, che li rende pi`u facilmente risolvibili rispetto ai modelli non lineari; in effetti sono ormai disponibili pacchetti software commerciali in grado di risolvere in modo efficiente 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`u compatto.
Lo sviluppo di un modello di programmazione lineare parte dall’analisi di una situazione reale (pi`u o meno schematizzata) e, in modo simile a quanto accade nello sviluppo di una procedura software, richiede di identificare le variabili di controllo ed i rispettivi domini, i vincoli e la funzione obiettivo. Non ci sono regole rigide da seguire: il modello finale nasce spesso — in particolare nela caso di situazioni complesse — per raffinamenti successivi.
ESERCIZIO 1.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`o 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 a 100 ad ogni prodotto) sono stati determinati i seguenti punteggi.
Prodotto Punti
Cioccolata 10
Succhi di frutta 30 Lattine di birra 6
Prodotto Punti Panini imbottiti 20 Acqua minerale 20 Pacchi di biscotti 8 Per non scontentare nessuno si `e deciso di portare almeno:
• 2 confezioni di cioccolata;
• 2 bottiglie di succo di frutta;
3
• 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`a dello zaino.
ESERCIZIO 1.2. L’acciaieria PLASTIK deve evadere un ordine di 1000 ton- nellate 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 — questi prodotti 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 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.
ESERCIZIO1.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 sono disponibili rispettivamente 4000 e 6000 unit`a. In particolare, per produrre una unit`a del modello 1 sono necessarie 2 unit`a di A e 4 unit`a di B; per una unit`a del modello 2 sono necessarie 3 unit`a di A e 2 unit`a di B; per una unit`a del modello 3 sono necessarie 5 unit`a di A e 7 di B. Il modello 1 richiede, per ogni unit`a prodotta, il doppio di forza lavoro rispetto al modello 2 e il triplo rispetto al modello 3. La forza lavoro presente in azienda `e in grado di produrre al massimo l’equivalente di 700 unit`a/giorno del modello 1. Il settore marketing dell’azienda ha reso noto che la domanda minima per ciascun modello `e rispet- tivamente di 200, 200 e 150 unit`a. Il profitto unitario di ogni modello `e di 30, 20 e 50 euro, rispettivamente.
Formulare il programma lineare per pianificare la produzione giornaliera massimizzando il profitto.
ESERCIZIO1.4. La casa editrice ANALFABETA pubblica un quotidiano che viene distribuito da quattro centri di smistamento S1, S2, S3, S4che richiedono rispettivamente almeno 100000, 150000, 50000 e 75000 copie. Il giornale viene stampato in tre tipografie T1, T2, T3che 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 tipografie ed i centri di smistamento sono rispettivamente di 20, 25, 15 e 5 Km.
per la prima tipografia, 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 pianificare le spedi- zioni a costo totale minimo.
(b) Si definisca 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 approvvigionamen- to.
ESERCIZIO 1.5. Un motel autostradale, dovendo garantire un servizio con- tinuato 24 ore su 24, ha bisogno di un numero minimo di inservienti per ogni ora del giorno secondo la seguente tabella.
Fascia oraria Numero min.
02-06 4
06-10 8
10-14 10
Fascia oraria Numero min.
14-18 7
18-22 12
22-02 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.
ESERCIZIO 1.6. Scrivere il modello in programmazione lineare del seguente problema. 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 pu`o essere 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 l’errore di un lotto pari al valore assoluto della differenza tra il suo tempo di fine lavorazione e l’ora di consegna. Si vuole minimizzare la somma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle 8.30).
ESERCIZIO 1.7. Scrivere il modello in programmazione lineare del seguente problema. Un’azienda alimentare deve pianificare la produzione di un prodotto per i prossimi 4 mesi. Non ci sono giacenze in magazzino all’inizio del periodo e non ce ne devono essere alla fine dei 4 mesi. La domanda mensile prevista `e di 120 ton, 160 ton, 300 ton e 200 ton rispettivamente (ipotesi: la produzione viene stoccata e rilasciata interamente a fine mese). La capacit`a produttiva mensile `e 140 ton, 150 ton, 140 ton e 160 ton rispettivamente ad un costo di 10 euro/ton.
In caso di necessit`a `e possibile produrre in straordinario aumentando la capacit`a mensile di (al pi`u) 50 ton, 75 ton, 70 ton e 80 ton rispettivamente. La produzione 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 fine mese costano 5 euro/ton. L’obiettivo `e quello di pianificare la produzione di costo minimo.
ESERCIZIO 1.8. Lo stato di Islandia ha quattro industrie esportatrici: ac- ciaio, motori, elettronica e plastica. Il ministro dell’economia di questo stato vuole massimizzare il saldo esportazioni-importazioni. La moneta di Islandia
`e il klutz. I prezzi in klutz sul mercato mondiale per unit`a di acciaio, mo- tori, elettronica e plastica sono rispettivamente 500, 1500, 300 e 1200. La produzione di una unit`a di acciaio richiede 0.02 unit`a di motori, 0.01 unit`a di plastica, 250 klutz di materie prime acquistate sul mercato mondiale e mez- zo anno-uomo di manodopera. La produzione di una unit`a di motori richiede 0.8 unit`a di acciaio, 0.15 unit`a di elettronica, 0.11 unit`a di plastica, 300 klutz di materie prime acquistate sul mercato mondiale e un anno-uomo di manod- opera. La produzione di una unit`a di prodotti elettronici richiede 0.01 unit`a di acciaio, 0.01 unit`a di motori, 0.05 unit`a di plastica, 50 klutz di materie
5 prime acquistate sul mercato mondiale e mezzo anno-uomo di manodopera. La produzione di una unit`a di plastica richiede 0.03 unit`a di motori, 0.2 unit`a di acciaio, 0.05 unit`a di elettronica, 300 klutz di materie prime acquistate sul mercato mondiale e due anni-uomo di manodopera. La produzione di motori
`e limitata a 650000 unit`a, quella di plastica a 60000 unit`a. La manodopera totale disponibile in Islandia `e di 830000 uomini per anno. Acciaio, motori, elettronica e plastica non possono essere importati, ma devono essere prodotti all’interno.
ESERCIZIO 1.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`a) indicati in tabella con 1, 2, 3, 4, 5, 6, 7. Si considerino, inoltre, 5 punti di offerta indicati in tabella con A, B, C, D, E nei quali potrebbero essere aperti dei centri vendita di un’impresa di distribuzione. Tale impresa `e interessata a soddisfare la domanda sopramenzionata in modo tale che i clienti non percorrano pi`u di 30 minuti di auto per raggiungere almeno uno dei centri vendita. In tabella, per ogni coppia di punti di domanda e di offerta, viene indicato il tempo auto necessario.
L’impresa ha inoltre fatto sapere che accetter`a soluzioni che prevedano l’at- tivazione del centro vendita B solo se `e gi`a 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 vendita garantendo il fatto che che tutti i punti di domanda vengano serviti.
A B C D E
1 41 33 24 29 58 2 25 12 22 58 41 3 21 43 34 54 18 4 21 42 39 26 18 5 11 23 24 29 53 6 47 23 19 16 31 7 37 47 51 26 19
ESERCIZIO 1.10. Una raffineria produce benzina verde e super a partire da due tipi di greggio A e B, usando tre impianti. Il primo impianto pu`o produrre 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`o produrre 4 barili di verde e 2 di super a partire da 3 barili di A e 4 barili di B. Il terzo pu`o produrre 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 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`u di 1000 barili. Formulare il programma lineare per massimizzare il profitto legato alla produzione mensile.
ESERCIZIO 1.11. Un’azienda 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 8 × 106 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 profitti 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`a europea richiedono che:
• almeno una tenuta lasci 200 ettari di terreno incolto, e
• l’estensione complessiva del terreno coltivato a soia dall’azienda non superi il 40% del totale del suolo coltivato.
Formulare il programma lineare per la massimizzazione del profitto.
ESERCIZIO 1.12. Una ditta ha la possibilit`a di attivare, per l’anno cor- rente, 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`a. La produzione di A, B, C e D richiede un costo fisso per l’attivazione delle rispettive linee di produzione ed una quantit`a di forza lavoro per ogni unit`a prodotta, ed ogni unit`a venduta fornisce un profitto, come specificato dalla seguente tabella (in euro).
Prodotto Costo fisso Forza lavoro unit. Profitto unit.
A 14500 10 50
B 10000 15 60
C 8000 5 55
D 9000 14 80
La ditta dispone per l’anno in corso di 200000 unit`a complessive di forza lavoro.
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 pi- anificarne i quantitativi al fine di massimizzare il saldo costi-profitti.
ESERCIZIO1.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 as- sicurare una produzione di almeno 4000 megawatts di giorno e di almeno 2800 megawatts di notte. L’uso di un generatore comporta la presenza di person- ale tecnico che sorvegli il suo funzionamento; tale personale viene retribuito in maniera 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 migliaia di lire) insieme al costo per ogni megawatt prodotta.
Costo attivazione Costo al giorno giorno/notte megawatt
Generatore A 800 1200 4
Generatore B 700 1000 6
Generatore C 900 1400 7
Il generatore A ha una capacit`a produttiva di 2500 megawatts al giorno (o notte) ma questa capacit`a scende a 2000 megawatts se il generatore viene
7 utilizzato sia di giorno che di notte. Analogamente, il generatore B ha una ca- pacit`a produttiva di 2000 megawatts al giorno ma questa capacit`a scende a 1500 megawatts se il generatore viene utilizzato sia di giorno che di notte. Infine, il generatore C ha una capacit`a produttiva di 3000 megawatts al giorno ma ques- ta capacit`a scende a 2500 megawatts se il generatore viene utilizzato sia di giorno che di notte. Si vuole minimizzare il costo complessivo.
ESERCIZIO1.14. Scrivere il modello in programmazione lineare del seguente problema. 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 pu`o essere 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 l’errore di un lotto pari al valore assoluto della differenza tra il suo tempo di fine lavorazione e l’ora di consegna. Si vuole minimiz- zare la somma degli errori dei lotti (ipotesi: il reperto comincia a lavorare alle 8.30).
ESERCIZIO 1.15. Una ditta che si occupa di riparazioni deve pianificare le assunzioni 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 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 affiancato un lavoratore esperto per insegnargli il mestiere. Ogni lavoratore esperto che svolge affiancamento rende per 70 ore di lavoro al mese (anzich´e 150). Dopo il mese di apprendistato i lavoratori neoassunti diventano esperti, con pari abilit`a lavorativa e stipen- dio. Le quantit`a di ore/lavoro da coprire per i prossimi 5 mesi sono rispetti- vamente di 2000, 4000, 7000, 3000, 3500 ore. Infine, se si assumono almeno 10 persone nel corso dei primi due mesi, l’azienda pu´o incassare un contributo statale di 100000 euro. Formulare il programma lineare che consente di pianifi- care le assunzioni riducendo al minimo i costi del personale nei prossimi cinque mesi.
ESERCIZIO 1.16. L’azienda 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.
Per effettuare gli acquisti l’azienda si pu`o appoggiare a quattro fornitori, i quali le forniscono le materie prime in lotti contenenti le seguenti quantit`a di materiale:
viti plastica acciaio
F1 50 3 5
F2 30 4 7
F3 25 1 3
F4 10 8 1
Nell’ottica di gestire al meglio il proprio magazzino, la PC4All intende avere, alla fine del mese, la minor quantit`a di materiale non utilizzato possibile e, a tal fine, `e disposta anche a comprare una quantit`a di materie prime inferiore alle proprie necessit`a. Il costo per lo stockaggio o per il mancato acquisto di una unit`a di materiale `e il seguente:
Viti 0.2 euro/pezzo Plastica 1 euro/kg.
Acciaio 3 euro/kg.
Per motivi commerciali l’azienda, se acquista dei lotti di materiale dal fornitore F1, `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 quantit`a di materiali acquistate e quelle necessarie, tenendo conto che non `e possibile comprare porzioni di lotto di materiali.
Capitolo 1
Modelli di programmazione lineare
1.1. Le variabili di controllo determinano la struttura della soluzione di un problema, permettendone la realizzazione. Quindi in questo caso `e naturale definire le variabili
x1, x2, x3, x4, x5, x6, con il significato
xi= unit`a di alimento (i) caricate nello zaino.
Con questa scelta di variabili si pu`o ottenere il seguente modello, nel quale compaiono due serie di vincoli: (1) un vincolo relativo alla capacit`a dello zaino, che non pu`o essere superata, e (2) vincoli relativi ai quantitativi minimi di alimenti da caricare.
max 10x1+ 30x2+ 6x3+ 20x4+ 20x5+ 8x6
soggetto a 1
2x1+ x2+1 3x3+ 1
10x4+ x5+1
2x6≤ 10 (1.1.1)
x1≥ 2, x2≥ 2, x3≥ 6,
x4≥ 10, x6≥ 2, (1.1.2)
x1, . . . , x6∈ Z+.
1.2. Le variabili pi`u naturali sono x1, x2, x3, dove xi = numero di confezioni di tipo i acquistato. A volte pu`o non essere evidente quale sia la scelta di vari- abili “pi`u naturale”. Una buona regola euristica `e spesso la seguente: una definizione di variabili `e soddisfacente quando essa permette di scrivere in modo semplice la funzione obiettivo (o comunque i vincoli pi`u significativi) del mod- ello. Ad esempio, in questo caso usare variabili che rappresentano le quantit`a di materiali (manganese, cromo, molibdeno) acquistate anzich`e le confezioni non
29
sarebbe soddisfacente, in quanto la funzione obiettivo risulterebbe molto difficile da esprimere.
Con la scelta di variabili indicata invece, si ottiene il modello min 10x1+ 15x2+ 20x3
soggetto a
2x1+ 2x2+ x3≥ 10000 (1.2.1)
2x1+ 3x2+ 2x3≥ 180000 (1.2.2)
x1+ x2+ 5x3≥ 20000 (1.2.3)
x1, x2, x3∈ Z+,
dove i vincoli (1.2.1), (1.2.2) e (1.2.3) rappresentano i quantitativi minimi di manganese, cromo e molibdeno da garantire, rispettivamente.
1.3. Le variabili x1, x2, x3sono sufficienti a modellare il problema, con xi= numero di unit`a di tipo i prodotte. Quindi si ha
max 30x1+ 20x2+ 50x3
soggetto a
2x1+ 3x2+ 5x3≤ 4000
4x1+ 2x2+ 7x3≤ 6000 (1.3.1)
x1+1 2x2+1
3x3≤ 700 (1.3.2)
x1≥ 200, , x2≥ 200, x3≥ 150 (1.3.3)
x1, x2, x3∈ Z+,
con i vinvoli (1.3.1), (1.3.2) e (1.3.3) che rappersentano i vincoli sulla disponi- bilit`a di materie prime, sulla forza lavoro disponibile e sui requisiti minimi di produzione stabiliti dal marketing, rispettivamente.
1.4. (a) Per come sono specificati i costi di spedizione, la scelta “naturale” per la definizione delle variabili di controllo `e la seguente:
xij = numero di copie spedite da Ti a Sj. In questo modo il modello diventa
max
3
X
i=1 4
X
j=1
cijxij
31
soggetto a
x11+ x12+ x13+ x14≤ 125000 x21+ x22+ x23+ x24≤ 180000 x31+ x32+ x33+ x34≤ 70000
(1.4.1)
x11+ x21+ x31≥ 100000 x12+ x22+ x32≥ 150000 x13+ x23+ x33≥ 50000 x14+ x24+ x34≥ 75000
(1.4.2)
xij∈ Z+, ∀ i, j.
I vincoli (1.4.1) e (1.4.2) impongono che ogni tipografia spedisca non pi`u giornali di quanti ne stampa (per la realizzabilit`a “fisica” della soluzione) e che ogni centro ne riceva una quantit`a pari almeno al proprio fabbisogno. I costi cij
sono ricavati dalla matrice delle distanze indicata dal testo: cij = 2×(distanza Ti-Sj).
(b) L’obiettivo specificato pone la necessit`a di scrivere un programma di minimo con una funzione obiettivo del tipo
maxj
3
X
i=1
cijxij .
Tale espressione `e per`o non lineare e quindi proibita nel tipo di modelli qui trattato. Per conservare la linearit`a del modello, occorre introdurre una variabile 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
(1.4.10)
x11+ x21+ x31≥ 100000 x12+ x22+ x32≥ 150000 x13+ x23+ x33≥ 50000 x14+ x24+ x34≥ 75000
(1.4.20)
3
X
i=1
cijxij≤ y j = 1, . . . , 4 (1.4.3)
xij∈ Z+, ∀ i, j, y ≥ 0
La variabile ausiliaria y ed i vincoli (1.4.3) permettono di gestire l’obiettivo
“min / max” conservando la linearit`a del modello: in ogni soluzione ottima di questo programma lineare, il valore assunto da y coincide esattamente con maxj{Pn
i=1cijxij}. I vincoli (1.4.10) e (1.4.20) hanno il ruolo gi`a noto.
1.5. Questo problema richiede, per essere modellato in modo semplice, una definizione accorta di variabili. Occorre tener presente che: (1) esiste una soluzione ottima dove ogni inserviente comincia lavorare all’inizio di una fascia oraria e ne copre esattamente due; (2) ogni inserviente ha (naturalmente) un unico orario di inizio turno. 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
soggetto a
x1+ x6≥ 4 (1.5.1)
x1+ x2≥ 8 (1.5.2)
x2+ x3≥ 10 (1.5.3)
x3+ x4≥ 7 (1.5.4)
x4+ x5≥ 12 (1.5.5)
x5+ x6≥ 4 (1.5.6)
x1, . . . , x6∈ Z+.
Poich´e ogni inserviente che comincia il turno nella fascia i copre le fasce i ed i+1 (modulo 6), i vincoli (1.5.1)–(1.5.6) garantiscono la copertura richiesta in ogni fascia. La funzione obiettivo rappresenta esattamente il numero di inservienti necessari.
1.6. Il problema richiede di scrivere un modello in grado di determinare gli istanti di inizio lavirazione dei lotti in esame; si pu`o assumere come “zero” del tempo l’ora 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 `e necessaria per rappresentare i tempi 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 indicano rispettivamente il tempo di lavorazione e la scadenza del lotto. La funzione obiettivo `e quindi del tipo
5
X
i=1
|ti+ pi− di|.
Questo genere di funzione `e non lineare quindi occorre nuovamente ricorrere ad un espediente per rappresentare i valori assoluti in un modello lineare. Ricor- dando che |x| = max(x, −x), si pu`o pensare di utilizzare la stessa tecnica usata per 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
33 soggetto a
t1+ 5 ≤ t2 (1 → 2) t2+ 7 ≤ t3 (2 → 3) t3+ 4 ≤ t4 (3 → 4) t4+ 7 ≤ t5 (4 → 5)
(1.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)
(1.6.2)
ti≥ 0, ∆i≥ 0, i = 1, . . . , 5.
I vincoli (1.6.1) garantiscono il rispetto della sequenza di lavorazione che, secon- do il testo, `e predeterminata, mentre i vincoli (1.6.2) vincolano i ∆iad assumere il valore assoluto di ti+ pi− di.
1.7. Il problema richiede in pi`u, rispetto ad altri problemi di produzione gi`a 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 della produzione, vengono detti multiperiodali. In questi casi `e utile (anche se non sempre indispensabile) disporre di un insieme di variabili che rappresentano esplicitamente il livello delle giacenze da gestire alla fine (o all’inizio) di ogni periodo. Il problema in esame pu`o essere modellato utilizzando le seguenti variabili.
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 valga zero in ogni soluzione ammissibile. Occorre modellare l’uso 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 specificate, un modello possibile `e
min 10
4
X
i=1
xi+ 16
4
X
i=1
si+ 5
3
X
i=1
yi
soggetto a
x1+ s1 = 120 + y1
x2+ s2+ y1= 160 + y2
x3+ s3+ y2= 300 + y3
x4+ s4+ y3= 200
(1.7.1)
xi≥ 0.1
3
X
i=1
(xi+ si) i = 1, . . . , 4 (1.7.2)
x1≤ 140, x2≤ 150, x3≤ 140, x4≤ 160, (1.7.3) s1≤ 50, s2≤ 75, s3≤ 70, s4≤ 80, (1.7.4) xi, si, yi≥ 0, i = 1, . . . , 4.
I vincoli (1.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 fine 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`a produttive massime (ordinaria e straordinaria) per i quattro mesi.
1.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 250
M 0.8 0.15 0.11 1.0 300
E 0.01 0.01 0.05 0.5 50
P 0.2 0.03 0.05 2.0 300
Poich´e acciaio, motori, elettronica e plastica vanno prodotti internamente e non acquistati, `e conveniente scorporare la produzione per uso interno da quella per esportazioni, definendo le variabili
xA, xM, xE, xP, yA, yM, yE, yP, dove
xi= unit`a di prodotto i realizzate per esportazione, i ∈ {A, M, E, P }, yi= unit`a 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 la produzione totale;
• le quantit`a di motori e plastica prodotte non eccedano i limiti imposti;
35
• 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)
(1.8.1)
xM + yM ≤ 650000
xP+ yP ≤ 600000 (1.8.2)
0.5(xA+ yA) + (xM + yM) + 0.5(xE+ yE) + 2(xP + yP) ≤ 830000 (1.8.3) xA, xM, xE, xP ≥ 0,
yA, yM, yE, yP ≥ 0.
La funzione obiettivo rappresenta il saldo esportazioni-importazioni; i vincoli (1.8.1) impongono che la produzione interna di ogni prodotto sia in grado di support- are la produzione totale; i vincoli (1.8.2) impongono i limiti richiesti alle pro- duzioni di motori e plastica, ed infine il vincolo (1.8.3) impone di non eccedere il monte-ore disponibile.
1.9. L’apertura di un centro `e una decisione che differisce da quelle modellate fino 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, `e possibile inserire nei programmi lineari variabili binarie, cio`e interi con valori limitati all’insieme {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 `e consentito in alcun modo introdurre prodotti del tipo (variabile logica)×(altre variabili), errore sorprendentemente comune.
Il problema in esame si pu`o 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
soggetto a
C + D ≥ 1 (1.9.1)
A + B + C ≥ 1 (1.9.2)
A + E ≥ 1 (1.9.3)
A + D + E ≥ 1 (1.9.4)
A + B + C + D ≥ 1 (1.9.5)
B + C + D ≥ 1 (1.9.6)
D + E ≥ 1 (1.9.7)
B ≤ C + D (1.9.8)
I vincoli (1.9.1)–(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 (1.9.8) modella un’implicazione logica
B =⇒ C ∨ D
(il requisito “B apre solo se . . . ” specificato dal testo: confrontare con la tabella di verit`a dell’operatore logico).
Si noti anche che nell’insieme di vincoli (1.9.1)–(1.9.8) esistono vincoli ri- dondanti: ad esempio, (1.9.1) implica (1.9.5), (1.9.6) e (1.9.8); questi tre vincoli potrebbero quindi essere rimossi dal modello. Questa operazione non `e stret- tamente necessaria ai fini della correttezza del modello, ma `e desiderabile in ambito applicativo, in quanto semplifica la risoluzione del modello.
1.10. La definizione di variabili che porta a realizzare il modello pi`u 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 xipermette di gestire il funzionamento degli impianti con le proporzioni specificate, 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 (1.10.1)
y1+ y2+ y3≥ 1 (1.10.2)
5x1≤ 1000y1+ M (1 − y1) 6x2≤ 1000y2+ M (1 − y2) 4x3≤ 1000y3+ M (1 − y3)
(1.10.3)
xi≥ 0, yi∈ {0, 1}, i = 1, 2, 3.
37 I vincoli (1.10.1) sono relativi al magazzino disponibile per i due tipi di greggio, che limita la produzione. Il vincolo (1.10.2) impone che almeno un impianto sia limitato a 1000 barili. I vincoli (1.10.3) svolgono l’importante funzione di collegare i 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 primo vincolo di questa serie implica:
y1= 1 =⇒ 5x1≤ 1000,
y1= 0 =⇒ 5x1≤ M (cio`e 5x1 non vincolato).
Questa tecnica del “big-M” `e comunemente usata per correlare variabili binarie e variabili di altro tipo.
1.11. `E necessario scorporare il prodotto sia per tipologia che per tenuta, altrimenti non `e possibile gestire le estensioni coltivate e le riserve d’acqua. Sono quindi 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`a 200 ettari incolti (yj = 1 iff la tenuta j lascia 200 ettari incolti). Il modello `e il 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
(1.11.1)
20000xM A+ 10000xSA+ 10000xGA≤ 8 · 106 20000xM B+ 10000xSB+ 10000xGB ≤ 5 · 106 20000xM C+ 10000xSC+ 10000xGC≤ 6 · 106
(1.11.2)
xSA+ xSB+ xSC≤ 0.4 X
i=M,S,G
X
j=A,B,C
xij (1.11.3)
yA+ yB+ yC≥ 1 (1.11.3)
xij≥ 0, yj∈ {0, 1}, i = M, S, G, j = A, B, C.
I vincoli (1.11.1) impediscono di coltivare in una tenuta pi`u del totale del suolo disponibile; i vincoli (1.11.2) impediscono di coltivare pi`u di quanto si possa irrigare con le scorte d’acqua delle varie tenute; il vincolo (1.11.3) stabilisce che non pi`u del 40% del suolo coltivato in totale pu`o essere messo a soia, ed il vincolo (1.11.3) impone che almeno una tenuta lasci 200 ha di suolo incolto.
Si noti che in 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 (1.11.1).
1.12. Il problema proposto riguarda la pianificazione di certi tipi di produzione con costi fissi imputabili alla preparazione degli impianti produttivi e costi variabili legati alle quantit`a prodotte. La decisione di attivare o meno la produzione di A, B, C o D `e di tipo vero/falso, e quindi si pu`o 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 unit`a di tipo i prodotte, i ∈ {A, B, C, D}.
Tenuto conto dei dati su quantitativi minimi, profitti 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
(1.12.1)
xA≤ M yA
xB≤ M yB
xC≤ M yC
xD≤ M yD
(1.12.2)
10xA+ 15xB+ 5xC+ 14xD≤ 2000000 (1.12.3)
yA≤ yC+ yD (1.12.4)
xi∈ Z+, yi∈ {0, 1}, i ∈ {A, B, C, D}.
I vincoli (1.12.1) impongono il rispetto dei quantitativi minimi qualora un tipo di produzione venga attivato, mentre i vincoli (1.12.2) assicurano che non vengano pianificati quantitativi per produzioni non attivate. Il vincolo (1.12.3) impone di non eccedere la quantit`a di forza lavoro disponibile; il vincolo (1.12.4) modella l’implicazione logica
yA =⇒ yC∨ yD, come richiesto dal testo.
1.13. Assumendo i turni possibili specificati dal testo, si possono definire due serie di 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.
39 Inoltre, essendoci un costo/MW, occorrono variabili in grado di specificare 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 (800x1+ 1200y1) + (700x2+ 1000y2) + (900x3+ 1400x3) + 4(WA+ ZA) + 6(WB+ ZB) + 7(WC+ ZC)
soggetto a x1+ y1≤ 1 x2+ y2≤ 1 x3+ y3≤ 1
(1.13.1)
WA≤ 2500xA, ZA≤ 2000yA
WB≤ 2000xB, ZB≤ 1500yB
WC≤ 3000xC, ZC≤ 2500yC
(1.13.2)
WA+ WB+ WC+ ZA+ ZB+ ZC≥ 4000
ZA+ ZB+ ZC≥ 2800 (1.13.3)
Wi, Zi≥ 0, xi, yi∈ {0, 1}, i = A, B, C.
I vincoli (1.13.1) impongono che ogni generatore funzioni secondo al pi`u un tipo di turno. I vincoli (1.13.2) fissano i limiti dell’erogazione di potenza come da turno per ogni generatore; si noti anche qui l’uso di tecniche in stile big-M: ad esempio, il primo vincolo di questa serie implica
x1= 1 =⇒ WA≤ 2500,
x1= 0 =⇒ WA= 0.
Infine, i vincoli (1.13.3) impongono il soddisfacimento delle potenze minime per il giorno e per la notte.
1.14. In questo problema `e importante notare che la sequenza delle lavorazioni non `e predeterminata; essa deve essere quindi determinata dalla soluzione del modello.
Rispetto all’esercizio 1.6, occorre una serie di variabili in pi`u: la sequenza `e determinata quando, per ogni coppia (non ordinata) {i, j} di lotti si `e in grado di determinare se i viene lavorato prima di j (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 1.6. Il valore delle variabili xij
deve poi essere correlato alle variabili ti mediante una serie di vincoli di tipo
