PL - Esercizi da Esame di Programmazione Lineare PDF

Preview

Summary

Esercizi da Esame di Programmazione Lineare...

Description

Parte II – Programmazione Matematica Capitolo 01 – Modelli di Programmazione Lineare Un modello di programmazione matematica è formato da:   

variabili decisionali 𝑥, … , 𝑥 che rappresentano le incognite, associate alle decisioni da prendere; funzione obiettivo 𝑓(𝑥, … , 𝑥 ), cioè una funzione delle variabili del problema, che riassume l’obiettivo da perseguire; vincoli 𝑔(𝑥, … , 𝑥  ) ≥ 𝑏, … , 𝑔(𝑥, … , 𝑥 ) ≥ 𝑏 che stabiliscono i valori che le variabili del problema possono assumere, e delimitano geometricamente la regione di ammissibilità.

Le variabili del problema possono essere di vario tipo:   

Variabili binarie 𝑥 ∈ {0,1}, ∀𝑖 = 1, … , 𝑛 Variabili discrete 𝑥 ∈ ℕ, ∀𝑖 = 1, … , 𝑛 Variabili continue 𝑥 ∈ ℝ , ∀𝑖 = 1, … , 𝑛

Esempio – LinDiet L’industria farmaceutica LinDiet vuole commercializzare un prodotto dietetico, che contenga la giusta miscela di due sostanze 𝑆 e 𝑆 in grado di fornire il giusto apporto di vitamine. L’obiettivo di LinDiet è scegliere la giusta miscela delle due sostanze che sia di costo minimo e garantisca le direttive sull’apporto vitaminico. La prima sostanza costa 0.50 euro all'etto e contiene all’etto 0,8 𝑚𝑔 di B1, 1 𝑚𝑔 di B2 e 0,8 𝑚𝑔 di B6. La seconda sostanza costa 0.35 euro all'etto e contiene all'etto 0,6 𝑚𝑔 di B1, 0,6 𝑚𝑔 di B2 e 0,9 𝑚𝑔 di B6. Il contenuto minimo delle tre vitamine deve essere di 2,8 𝑚𝑔 per la B1, di 9 𝑚𝑔 per la B2 e di 10 𝑚𝑔 per la B6. Definizione variabili: 𝑥 , 𝑥 ∈ ℝ rappresentano la quantità (in etti) di 𝑆 e 𝑆 . Vincoli: 0.8𝑥 + 0.6𝑥 ≥ 2.8 𝐵1 𝑥 + 0.6𝑥 ≥ 9 𝐵2 0.8𝑥 + 0.9𝑥 ≥ 10 𝐵6 Funzione obiettivo min 0.5𝑥 + 0.35𝑥

Esempio – SilComputers SilComputers è un'azienda che si occupa della produzione di notebook e pc desktop. L’azienda vuole stabilire quanti notebook e quanti pc desktop produrre al fine di massimizzare il profitto nel prossimo quadrimestre. Dobbiamo tenere conto di una serie di limiti di produzione, e del fatto che SilComputers preferisce produrre solamente lotti da 100 elementi (notebook o pc desktop). Ciascun computer ha una CPU e ne abbiamo a disposizione 1000 per il prossimo quadrimestre. Ciascun computer ha bisogno di banchi di memoria: 1 per i notebook e 2 per i pc desktop. Ne abbiamo a disposizione 1550 per il prossimo quadrimestre. Ciascun computer richiede un tempo di assemblaggio: 4 minuti per i notebook e 3 per i pc desktop. In un quadrimestre l'azienda ha a disposizione 2500 minuti per le operazioni di assemblaggio. Il profitto ottenuto per la vendita di ogni notebook è di 750 dollari, quello per la vendita dei pc desktop è di 1000 dollari. Definizione variabili: 𝑥 , 𝑥 ∈ ℕ rappresentano il numero di lotti (da 100 elementi) di notebook e pc desktop prodotti Vincoli: 𝑥 + 𝑥 ≤ 10 𝐶𝑃𝑈 𝑥 + 2𝑥 ≤ 15.5 𝑚𝑒𝑚𝑜𝑟𝑖𝑎 4𝑥 + 3𝑥 ≤ 25 𝑚𝑖𝑛𝑢𝑡𝑖 Funzione obiettivo: max 750𝑥 + 1000𝑥

Il problema dello zaino Sia dato uno zaino che possa sopportare un determinato peso 𝑊 . Siano dati inoltre un insieme 𝑁 di oggetti: ogni oggetto 𝑖 ∈ 𝑁 è caratterizzato da un peso 𝑤 e un punteggio 𝑝 . Il problema si propone di scegliere quali (e quanti) di questi oggetti mettere nello zaino per ottenere il punteggio globale maggiore senza eccedere il peso sostenibile dallo zaino stesso. Esempio – Il problema dello zaino 𝑊 = 10𝑘𝑔 Oggetto 𝑖 Cioccolata Succhi di frutta Lattine di birra Panini imbottiti Acqua minerale Pacchi di biscotti

Peso 𝑤

500𝑔 1𝑙 0. 33𝑙 100𝑔 1𝑙 500𝑔

Punteggio 𝑝 10 30 6 3 20 8

Vincoli

2 2 6 10 1 2

Definizione variabili: 𝑥 ∈ ℕ, ∀𝑖 = 1, … , 6 rappresentano il numero di prodotti di tipo 𝑖 inseriti nello zaino Vincoli: 0.5𝑥 + 𝑥 + 0.33𝑥 + 0.1𝑥 + 𝑥 + 0.5𝑥 ≤ 10 𝑐𝑎𝑝𝑎𝑐𝑖𝑡à 𝑥 ≥ 2 𝑥 ≥ 2 𝑥 ≥ 6 𝑞𝑡à 𝑚𝑖𝑛𝑖𝑚𝑒 𝑥 ≥ 10 𝑥 ≥ 1 𝑥 ≥ 2 Funzione obiettivo: max 10𝑥 + 30𝑥 + 6𝑥 + 3𝑥 + 20𝑥 + 8𝑥

Modelli min-max, max-min e min-abs Si consideri un generico modello la cui funzione obiettivo sia del tipo: min max{𝑒 , 𝑒 , … , 𝑒 } È sempre possibile trasformare i modelli min-max in modelli equivalenti di programmazione lineare nel modo seguente: si introduce una variabile fittizia 𝑦 nella funzione obiettivo da minimizzare, che diventa quindi min 𝑦 e si aggiungono all’insieme dei vincoli le disequazioni 𝑦 ≥ 𝑒 𝑦 ≥ 𝑒 … 𝑦 ≥ 𝑒 Nel modello lineare equivalente, 𝑦 rappresenta proprio il valore max{𝑒, 𝑒 , … , 𝑒 }, in quanto è vincolato dalle disequazioni introdotte ad essere non inferiore al più grande dei termini 𝑒 ed è minimizzato nella funzione obiettivo. Ciò implica, conseguentemente, che nella soluzione ottima almeno uno dei vincoli 𝑦 ≥ 𝑒 sia soddisfatto con il segno di uguaglianza (vincolo saturo). In modo analogo, si consideri un problema del tipo max min{𝑒 , 𝑒 , … , 𝑒 } Si introduce una variabile fittizia 𝑦 nella funzione obiettivo da massimizzare, che diventa quindi max 𝑦 e si aggiungono all’insieme dei vincoli le disequazioni 𝑦 ≤ 𝑒 𝑦 ≤ 𝑒 … 𝑦 ≤ 𝑒 Si consideri, infine, un modello del tipo min|𝑒| In questo caso si ha un modello min-abs, dove si cerca di minimizzare il valore assoluto di un’espressione lineare. Ricordando che |𝑒| = max{𝑒, −𝑒}, il modello min-abs viene trasformato in un modello minmax: si introduce una variabile fittizia 𝑦 nella funzione obiettivo da minimizzare, che diventa quindi min 𝑦 e si aggiungono all’insieme dei vincoli le disequazioni 𝑦≥𝑒 𝑦 ≥ −𝑒

Modelli con vincoli di tipo logico In questi casi, le variabili decisionali del problema sono soggette ad ulteriori relazioni di tipo logico. Queste relazioni possono sia fare riferimento alla singola variabile in questione, sia collegare logicamente due o più variabili. Un esempio del primo tipo si ha in presenza di variabili il cui costo sia determinato, oltre che dal coefficiente di costo unitario, anche da un ulteriore costo fisso, che viene attivato solo se la variabile ha valore > 0 nella soluzione. Si consideri di rappresentare una certa attività con la variabile 𝑥 ≥ 0, avente coefficiente di costo unitario 𝑐 e costo fisso 𝑓 . Il costo di quell’attività sarebbe dunque 𝑐 𝑥 + 𝑓 se l’attività in questione venisse svolta (𝑥 > 0) e nullo in caso contrario (𝑥 = 0). Sia 𝑀 un limite superiore noto al valore della variabile 𝑥 . È possibile modellizzare un caso di questo genere introducendo una variabile binaria 𝑦 ∈ {0,1} che indichi se 𝑥 > 0 oppure 𝑥 = 0. L’implicazione logica dovrà essere del tipo 𝐼𝐹 𝑥 > 0 𝑇𝐻𝐸𝑁 𝑦 = 1 𝐸𝐿𝑆𝐸 𝑦 = 0 e il costo di quell’attività sarà 𝑐 𝑥 + 𝑓 𝑦 e l’implicazione logica verrà garantita introducendo il vincolo 𝑥 ≤ 𝑀𝑦 Un tipico esempio di vincoli logici che legano più variabili è invece il seguente. Supponiamo che le variabili 𝑥 ≥ 0 ed 𝑥 ≥ 0 rappresentino due attività incompatibili tra loro. L’implicazione logica risulta essere 𝐼𝐹 𝑥 > 0 𝑇𝐻𝐸𝑁 𝑥 = 0 𝐴𝑁𝐷 𝐼𝐹 𝑥 > 0 𝑇𝐻𝐸𝑁 𝑥 = 0 Sia 𝑀 un limite superiore noto ai valori delle variabili 𝑥 e 𝑥 . È possibile modellizzare un caso di questo genere introducendo due variabili binarie 𝑦 , 𝑦 ∈ {0,1} ed i seguenti vincoli 𝑥 ≤ 𝑀𝑦 𝑥 ≤ 𝑀𝑦 𝑦 + 𝑦 ≤ 1 I primi due vincoli servono, come al caso precedente, a mettere in relazione ciascuna variabile reale con la variabile binaria corrispondete, mentre il terzo vincolo serve ad impedire che entrambe le variabili 𝑥 e 𝑥 possano essere contemporaneamente diverse da 0.

Problema di mix – L’acciaieria Plastik L’acciaieria Plastik deve evadere un ordine di 1000 tonnellate di acciaio INOX. Per questa produzione servono manganese (almeno l’1%), 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 𝐾𝑔 di manganese, 2 𝐾𝑔 di cromo e 1 𝐾𝑔 di molibdeno e costa 10 euro. La seconda confezione contiene 2 𝐾𝑔 di manganese, 3 𝐾𝑔 di cromo e 1 𝐾𝑔 di molibdeno e costa 15 euro. La terza confezione contiene 1 𝐾𝑔 di manganese, 2 𝐾𝑔 di cromo e 5𝐾𝑔 di molibdeno e costa 20 euro. Formulare il modello di programmazione lineare che minimizzi il costo di acquisto delle confezioni. Definizione variabili: 𝑥 ∈ ℕ, ∀𝑖 = 1, … ,3 rappresentano il numero di confezioni di tipo 𝑖 da acquistare Vincoli: 2𝑥 + 2𝑥 + 𝑥 ≥ 0.01 ∙ 10 𝑀𝑛 2𝑥 + 3𝑥 + 2𝑥 ≥ 0.18 ∙ 10 𝐶𝑟 𝑥 + 𝑥 + 5𝑥 ≥ 0.02 ∙ 10 𝑀𝑜 Funzione obiettivo: min 10𝑥 + 15𝑥 + 20𝑥

Problema del trasporto – La casa editrice Analfabeta La casa editrice Analfabeta pubblica un quotidiano che viene distribuito da quattro centri di smistamento A, B, C e D che richiedono rispettivamente 100000, 150000, 50000 e 75000 copie. Il giornale viene stampato in tre tipografie T1, T2 e T3 con capacità produttiva rispettivamente di 125000, 180000 e 70000 copie. I costi per la spedizione sono di dieci centesimi per Km per ciascun giornale e le distanze tra le tipografie ed i centri di smistamento sono rispettivamente di 20, 25, 15 e 5 𝐾𝑚 per la prima tipografia, 12, 14, 18 e 30 𝐾𝑚. per la seconda tipografia e 19, 11, 40 e 12 𝐾𝑚 per la terza tipografia. Formulare il modello di programmazione lineare che permetta alla casa editrice di pianificare le sue spedizioni giornaliere minimizzando i costi di spedizione. Definizione variabili: 𝑥, ∈ ℕ, ∀𝑖 ∈ 𝑇 ∧ ∀𝑗 ∈ 𝑆 rappresentano la quantità di giornali da inviare a partire dalla tipografia 𝑖 al centro di smistamento 𝑗 Vincoli: 𝑥, + 𝑥, + 𝑥, ≥ 100𝑘 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑐𝑒𝑛𝑡𝑟𝑜 𝐴 𝑥, + 𝑥, + 𝑥, ≥ 150𝑘 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑐𝑒𝑛𝑡𝑟𝑜 𝐵 𝑥, + 𝑥, + 𝑥, ≥ 50𝑘 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑐𝑒𝑛𝑡𝑟𝑜 𝐶 𝑥, + 𝑥, + 𝑥, ≥ 70𝑘 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑐𝑒𝑛𝑡𝑟𝑜 𝐷 𝑥, + 𝑥, + 𝑥, + 𝑥, ≤ 125𝑘 𝑐𝑎𝑝𝑎𝑐𝑖𝑡à 𝑡𝑖𝑝𝑜𝑔𝑟𝑎𝑓𝑖𝑎 1 𝑥, + 𝑥, + 𝑥, + 𝑥, ≤ 180𝑘 𝑐𝑎𝑝𝑎𝑐𝑖𝑡à 𝑡𝑖𝑝𝑜𝑔𝑟𝑎𝑓𝑖𝑎 2 𝑥, + 𝑥, + 𝑥, + 𝑥, ≤ 70𝑘 𝑐𝑎𝑝𝑎𝑐𝑖𝑡à 𝑡𝑖𝑝𝑜𝑔𝑟𝑎𝑓𝑖𝑎 3 Funzione obiettivo: min 20𝑥, + 25𝑥, + 15𝑥, + 5𝑥, + 12𝑥, + 14𝑥, + 18𝑥, + 30𝑥, + 19𝑥, + 11𝑥, + 40𝑥, + 12𝑥, 0.10 min ∑ ∑ 𝑘, 𝑥,

(𝑣𝑎𝑟𝑖𝑎𝑛𝑡𝑒 𝑟𝑖𝑑𝑜𝑡𝑡𝑎)

Problema di mix – Il ranch Little Dixie Il proprietario del ranch Little Dixie sta facendo dei test per determinare la mescola corretta per due alimenti contenenti in percentuali differenti quattro diversi tipi di ingredienti essenziali. L’alimento 1 ha un costo unitario di 5 dollari ed è formato per il 40% dall’ingrediente 1, per il 10% dall’ingrediente 2, per il 20% dall’ingrediente 3 e per il 30% dall’ingrediente 4. L’alimento 2 ha un costo unitario di 3 dollari ed è formato per il 20% dall’ingrediente 1, per il 30% dall’ingrediente 2, per il 40% dall’ingrediente 3 e per il 10% dall’ingrediente 4. Sapendo che devono essere impiegate come minimo 400 unità dell'ingrediente 1, 200 unità dell'ingrediente 2, 300 unità dell'ingrediente 3 e 600 unità dell'ingrediente 4, si vuole formulare il modello di programmazione lineare per determinare la mescola di costo minimo. Definizione variabili: 𝑥 , 𝑥 ∈ ℝ rappresentano le unità dell’alimento 1 e dell’alimento 2 che vanno mescolate Vincoli: 0.40𝑥 + 0.20𝑥 0.10𝑥 + 0.30𝑥 0.20𝑥 + 0.40𝑥 0.30𝑥 + 0.10𝑥 Funzione obiettivo: min 5𝑥 + 3𝑥

≥ 400 ≥ 200 ≥ 300 ≥ 600

𝑖𝑛𝑔𝑟𝑒𝑑𝑖𝑒𝑛𝑡𝑒 1 𝑖𝑛𝑔𝑟𝑒𝑑𝑖𝑒𝑛𝑡𝑒 2 𝑖𝑛𝑔𝑟𝑒𝑑𝑖𝑒𝑛𝑡𝑒 3 𝑖𝑛𝑔𝑟𝑒𝑑𝑖𝑒𝑛𝑡𝑒 4

Problema di mix – Esercizio A: Un problema di produzione Un’azienda 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 unità del modello 1 sono necessarie 2 unità di A e 4 unità di B; per una unità del modello 2 sono necessarie 3 unità di A e 2 unità di B; per una unità del modello 3 sono necessarie 5 unità di A e 7 di B. Il modello 1 richiede, per ogni unità prodotta, il doppio di forza lavoro rispetto al modello 2 e il triplo rispetto al modello 3. La forza lavoro presente in azienda è in grado di produrre al massimo l'equivalente di 700 unità/giorno del modello 1. Il settore marketing dell'azienda ha reso noto che la domanda minima per ciascun modello è rispettivamente di 200, 200 e 150 unità. Il profitto unitario di ogni modello è di 30, 20 e 50 Euro, rispettivamente. Si richiede di pianificare la produzione giornaliera massimizzando il profitto. Definizione variabili: 𝑥 ∈ ℕ, ∀𝑖 = 1, … ,3 rappresentano la quantità di unità prodotte per il modello 𝑖 Vincoli: 𝑥 ≥ 200 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑚𝑜𝑑𝑒𝑙𝑙𝑜 1 𝑥 ≥ 200 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑚𝑜𝑑𝑒𝑙𝑙𝑜 2 𝑥 ≥ 150 𝑑𝑜𝑚𝑎𝑛𝑑𝑎 𝑚𝑜𝑑𝑒𝑙𝑙𝑜 3 



𝑥 + 𝑥 + 𝑥 ≤ 700  

𝑥 = 2𝑥 𝑥 = 3𝑥

𝑐𝑎𝑝𝑎𝑐𝑖𝑡à 𝑓𝑜𝑟𝑧𝑎 𝑙𝑎𝑣𝑜𝑟𝑜

𝑟𝑎𝑝𝑝𝑜𝑟𝑡𝑜 𝑓𝑜𝑟𝑧𝑎 𝑙𝑎𝑣𝑜𝑟𝑜 1 − 2 𝑟𝑎𝑝𝑝𝑜𝑟𝑡𝑜 𝑓𝑜𝑟𝑧𝑎 𝑙𝑎𝑣𝑜𝑟𝑜 1 − 3

2𝑥 + 3𝑥 + 5𝑥 ≤ 4000 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑖𝑙𝑖𝑡à 𝐴 4𝑥 + 2𝑥 + 7𝑥 ≤ 6000 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑖𝑙𝑖𝑡à 𝐵 Funzione obiettivo: max 30𝑥 + 20𝑥 + 50𝑥

Problema multiperiodale – Esercizio B La società CHAOS vuole pianificare la produzione per i prossimi quattro mesi del suo prodotto principale che consiste in rotoli di lamiera. La società CHAOS conosce la domanda di prodotto per i prossimi mesi. Non ci sono giacenze in magazzino all'inizio del periodo e non ci devono essere alla fine dei quattro mesi. Si richiede il programma lineare per l’identificazione di un piano di produzione al costo minimo. Sono noti i dati riportati in tabella. Vendite 20 30 50 40

Mese 1 2 3 4

Capacità produttiva 40 50 30 50

Costo produzione 34 36 32 38

Costo magazzino 2 3 2 3

Definizione variabili: 𝑥 ∈ ℕ, ∀𝑖 = 1, … ,4 rappresentano le unità prodotte al mese 𝑖 𝑤 ∈ ℕ, ∀𝑖 = 1, … ,3 rappresentano le unità a magazzino alla fine del mese 𝑖 (al mese 4 devono essere uguali a zero) Vincoli: 20 + 𝑤 = 𝑥 30 + 𝑤 = 𝑥 + 𝑤 50 + 𝑤 = 𝑥 + 𝑤 40 = 𝑥 + 𝑤

𝑥 ≤ 40 𝑚𝑒𝑠𝑒 1 𝑥 ≤ 50 𝑚𝑒𝑠𝑒 2 𝑥 ≤ 30 𝑚𝑒𝑠𝑒 3 𝑥 ≤ 50 𝑚𝑒𝑠𝑒 4

Funzione obiettivo: min 30𝑥 + 36𝑥 + 32𝑥 + 38𝑥 + 2𝑤 + 3𝑤 + 2𝑤

Problema di approvvigionamento e produzione – Esercizio 1 Un mobilificio possiede due stabilimenti: A e B. Nello stabilimento A vengono prodotti letti e armadi. I primi richiedono 0.2 𝑚 di legno ed i secondi 0.6 𝑚 di legno oltre a 3 e 5 ore di lavoro rispettivamente. Nello stabilimento B vengono prodotti tavoli e scrivanie che richiedono 0.3 e 0.5 𝑚 di legno rispettivamente e 4 ore di lavoro ciascuno. La disponibilità di manodopera è di 4000 ore di lavoro mensili per stabilimento. Il legno è prodotto lontano dagli stabilimenti. La direzione centrale sa di avere mensilmente la disponibilità di 15000 unità di capacità di trasporto con i propri mezzi e che ogni 𝑚 di legno spedito allo stabilimento A assorbe 5 unità e ogni 𝑚 di legno spedito allo stabilimento B assorbe 3 unità. La direzione dispone questo mese di 50000 𝑚 di legno. I costi unitari del legno sono di 10 𝐸𝑢𝑟𝑜/𝑚 e per il trasporto di 20 𝐸𝑢𝑟𝑜/𝑢𝑛𝑖𝑡à di capacità. Sapendo che i ricavi unitari sono di Euro 150 per i letti, di Euro 80 per gli armadi, di Euro 100 per i tavoli e di Euro 110 per le scrivanie, si vuole ottimizzare la produzione (ricavi-costi) nel mese corrente. Definizione variabili: 𝐿, 𝑇, 𝐴, 𝑆 ∈ ℕ rappresentano le unità prodotte di ogni tipo di mobile Vincoli: 0.2𝐿 + 0.6𝐴 + 0.3𝑇 + 0.5𝑆 ≤ 50𝑘 3𝐿 + 5𝐴 ≤ 4𝑘 4𝑇 + 4𝑆 ≤ 4𝑘

𝑚 𝑑𝑖 𝑙𝑒𝑔𝑛𝑜

𝑜𝑟𝑒 𝑑𝑖 𝑙𝑎𝑣𝑜𝑟𝑜 𝑟𝑖𝑐ℎ𝑖𝑒𝑠𝑡𝑒

5(0.2𝐿 + 0.6𝐴) + 3(0.3𝑇 + 0.5𝑆) ≤ 15𝑘

𝑚 𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑖

Funzione obiettivo: max 150𝐿 + 80𝐴 + 100𝑇 + 110𝑆 − {10(0.2𝐿 + 0.6𝐴 + 0.3𝑇 + 0.5𝑆) + 20[5(0.2𝐿 + 0.6𝐴) + 3(0.3𝑇 + 0.5𝑆)]}

Problema di mix – Un problema di dieta Sia data la seguente tavola di valori nutrizionali che riporta il tipo di alimento, il costo unitario, le unità di sostanze (proteine, carboidrati, grassi, vitamine, calcio) per unità di alimento: Alimento Costo Proteine Carboidrati Grassi Vitamine Calcio 1 0. 15 0 0.7 0. 1 0.1 0 2 0. 23 0.1 0 0. 3 0.1 0.4 3 0. 79 0.5 0 0. 4 0 0.1 4 0. 47 0.2 0.2 0. 1 0.3 0 5 0. 52 0 0.3 0 0.2 0.1 Formulare un problema di PLI che permetta di trovare una dieta di costo minimo sapendo che si devono assumere almeno 3 unità di proteine, 10 unità di carboidrati, 2 unità di grasso, 3 unità di vitamine e 2 unità di calcio e sapendo che se è presente l’alimento 1 la dieta non può contenere l’alimento 5. Definizione variabili: 𝑥 ∈ ℝ , ∀𝑖 = 1, … ,5 rappresentano le unità di alimento 𝑖 nella dieta 1 𝑠𝑒 𝑚𝑒𝑡𝑡𝑜 𝑗 𝑛𝑒𝑙𝑙𝑎 𝑑𝑖𝑒𝑡𝑎 𝑎 ∈ 󰇥 , ∀𝑗 = 1, 5 rappresentano la condizione booleana di presenza 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 dell’alimento 𝑗 nella dieta Vincoli logici: 𝑎 + 𝑎 ≤ 1

𝑐𝑜𝑛𝑑𝑖𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝑁𝐴𝑁𝐷 (𝑜 1, 𝑜 5, 𝑜 𝑛𝑒𝑠𝑠𝑢𝑛𝑜 𝑑𝑒𝑖 𝑑𝑢𝑒)

Vincoli di Big-M: 𝑥 ≤ 𝑀𝑎 𝑥 ≤ 𝑀𝑎

𝑝𝑟𝑒𝑠𝑒𝑛𝑧𝑎 𝑑𝑖 1 𝑝𝑟𝑒𝑠𝑒𝑛𝑧𝑎 𝑑𝑖 5

Vincoli: 0.1𝑥 + 0.5𝑥 + 0.2𝑥 ≥ 3 0.7𝑥 + 0.2𝑥 + 0.3𝑥 ≥ 10 0.1𝑥 + 0.3𝑥 + 0.4𝑥 + 0.1𝑥 ≥ 2 0.1𝑥 + 0.1𝑥 + 0.3𝑥 + 0.2𝑥 ≥ 3 0.4𝑥 + 0.1𝑥 + 0.1𝑥 ≥ 2

𝑝𝑟𝑜𝑡𝑒𝑖𝑛𝑒 𝑐𝑎𝑟𝑏𝑜𝑖𝑑𝑟𝑎𝑡𝑖 𝑔𝑟𝑎𝑠𝑠𝑖 𝑣𝑖𝑡𝑎𝑚𝑖𝑛𝑒 𝑐𝑎𝑙𝑐𝑖𝑜

Funzione obiettivo: min 0.15𝑥 + 0.23𝑥 + 0.79𝑥 + 0.47𝑥 + 0.52𝑥

Esercizio 3 Una ditta ha la possibilità di attivare, per l’anno corrente, 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 e D richiede un costo fisso per l’attivazione delle rispettive linee di produzione ed una quantità di forza lavoro per ogni unità prodotta, ed ogni unità venduta fornisce un profitto, come specificato dalla seguente tabella (in euro). Prodotto Costo fisso Forza lavoro unità Ricavi 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à 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 pianificarne i quantitativi al fine di massimizzare il profitto (Ricavi - Costi). Definizione variabili: 𝑥 ∈ ℕ, ∀𝑖 = 𝐴, … , 𝐷 rappresentano la quantità di modello 𝑖 da produrre 1 𝑠𝑒 𝑎𝑡𝑡𝑖𝑣𝑜 𝑙𝑎 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝑖 , ∀𝑖 = 𝐴, … , 𝐷 rappresentano la condizione booleana di 𝑦 ∈ 󰇥 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 attivazione della produzione di 𝑖 Vincoli logici: 𝑥 ≥ 1000𝑦 𝑥 ≥ 1500𝑦 𝑥 ≥ 3000𝑦 𝑥 ≥ 2000𝑦 𝑦 ≤ 𝑦 + 𝑦

𝑠𝑒 𝐴 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜, 𝑣𝑒𝑛𝑔𝑜𝑛𝑜 𝑝𝑟𝑜𝑑𝑜𝑡𝑡𝑒 𝑎𝑙𝑚𝑒𝑛𝑜 1000 𝑢𝑛𝑖𝑡à, 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 0 𝑠𝑒 𝐵 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜, 𝑣𝑒𝑛𝑔𝑜𝑛𝑜 𝑝𝑟𝑜𝑑𝑜𝑡𝑡𝑒 𝑎𝑙𝑚𝑒𝑛𝑜 1500 𝑢𝑛𝑖𝑡à, 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 0 𝑠𝑒 𝐶 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜, 𝑣𝑒𝑛𝑔𝑜𝑛𝑜 𝑝𝑟𝑜𝑑𝑜𝑡𝑡𝑒 𝑎𝑙𝑚𝑒𝑛𝑜 3000 𝑢𝑛𝑖𝑡à, 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 0 𝑠𝑒 𝐷 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜, 𝑣𝑒𝑛𝑔𝑜𝑛𝑜 𝑝𝑟𝑜𝑑𝑜𝑡𝑡𝑒 𝑎𝑙𝑚𝑒𝑛𝑜 2000 𝑢𝑛𝑖𝑡à, 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 0 𝑠𝑒 𝐴 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜, 𝑣𝑖𝑒𝑛𝑒 𝑎𝑡𝑡𝑖𝑣𝑎𝑡𝑜 𝑎𝑙𝑚𝑒𝑛𝑜 𝑢𝑛𝑜 𝑡𝑟𝑎 𝐶 𝑒 𝐷

Vincoli di Big-M: 𝑥 ≤ 𝑀𝑦 𝑥 ≤ 𝑀𝑦 𝑥 ≤ 𝑀𝑦 𝑥 ≤ 𝑀𝑦

𝑎𝑡𝑡𝑖𝑣𝑎𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝐴 𝑎𝑡𝑡𝑖𝑣𝑎𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝐵 𝑎𝑡𝑡𝑖𝑣𝑎𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝐶 𝑎𝑡𝑡𝑖𝑣𝑎𝑧𝑖𝑜𝑛𝑒 𝑑𝑖 𝐷

Vincoli: 10𝑥 + 15𝑥 + 5𝑥 + 14𝑥 ≤ 200000

𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑖𝑙𝑖𝑡à 𝑓𝑜𝑟𝑧𝑎 𝑙𝑎𝑣𝑜𝑟𝑜

Funzione obiettivo: max 50𝑥 + 60𝑥 + 55𝑥 + 80𝑥 − (14500𝑦 + 10000𝑦 + 8000𝑦 + 9000𝑦 )

Problema di trasporto – Esercizio 4: approvvigionamento energetico Un amministratore deve pianificare il rifornimento di gasolio da riscaldamento per quattro condomini 1, 2, 3 e 4, che necessitano per i mesi invernali di almeno 1200, 2000, 2500 e 5000 litri rispettivamente. Sono stati selezionati sul mercato tre fornitori di gasolio A, B e C, che dispongono di combustibile in quantità praticamente illimitata. Il fornitore A vende il gasolio a 10 𝑒𝑢𝑟𝑜/𝑙𝑖𝑡𝑟𝑜, ma per ragioni di trasporto non è in grado di rifornire contemporaneamente i condomini 1 e 4. Il fornitore B applica il prezzo di 8 𝑒𝑢𝑟𝑜/𝑙𝑖𝑡𝑟𝑜. Il fornitore C vende a 12 𝑒𝑢𝑟𝑜/𝑙𝑖𝑡𝑟𝑜. Per non legarsi ad un solo fornitore, l'amministratore decide che ognuno dei tre fornirà almeno il 15% della commessa totale. Formulare il programma lineare per pianificare l'approvvigionamento a costo minimo alle suddette condizioni. Definizione variabili: 𝑥, ∈ ℝ , ∀𝑖 = 𝐴, … , 𝐶 ∧ ∀𝑗 = 1, … , 4 rappresentano i litri di gasolio da inviare a dal fornitore 𝑖 al condominio 𝑗 1 𝑠𝑒 𝐴 𝑓𝑜𝑟𝑛𝑖𝑠𝑐𝑒 𝑐𝑜𝑛𝑑𝑜𝑚𝑖𝑛𝑖𝑜 𝑗 , ∀𝑗 = 1, 4 rappresentano la condizione booleana su 𝑦 ∈ 󰇥 0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 quale condominio deve essere rifornito dal fornitore A Vincoli logici: 𝑦 + 𝑦 ≤ 1

𝐴 𝑝𝑢ò 𝑓𝑜𝑟𝑛𝑖𝑟𝑒 𝑜 𝑖𝑙 𝑐𝑜𝑛𝑑𝑜𝑚𝑖𝑛𝑖𝑜 1 𝑜 𝑖𝑙 𝑐𝑜𝑛𝑑𝑜𝑚𝑖𝑛𝑖𝑜 4

Vincoli di Big-M: 𝑥, ≤ 𝑀𝑦 𝑥, ≤ 𝑀𝑦

𝑓𝑜𝑟𝑛𝑖𝑡𝑢𝑟𝑎 𝑑𝑖 1 𝑓𝑜𝑟𝑛𝑖𝑡𝑢𝑟𝑎 𝑑𝑖 4

Vincoli: ∑ 𝑥, ≥ 1200 ∑ 𝑥, ≥ 2000 ∑ 𝑥, ≥ 2500 ∑ 𝑥, ≥ 5000

𝑓𝑜𝑟𝑛𝑖𝑡𝑢𝑟𝑎 𝑚𝑖𝑛𝑖𝑚𝑎 𝑝𝑒𝑟 𝑖𝑙 𝑐𝑜𝑛𝑑𝑜𝑚𝑖𝑛𝑖𝑜 1

𝑓𝑜𝑟𝑛𝑖𝑡𝑢𝑟𝑎 𝑚𝑖𝑛𝑖𝑚𝑎 𝑝...