Ottimizzazione Discreta – Esercizi I
Problemi di Programmazione Lineare e forma standard A.A. 2014/2015
Esercizio 1
Si dica quali dei seguenti problemi di ottimizzazione sono, nella forma in cui sono scritti, programmi lineari:
(a) min 3x1+ 6x2+ 8x3 s.a 7x1+ 4x2− 2x3 ≤ 5
5x1− 2x2+ 6x3 ≥ 3 x3 > 0
(c) max 2x + 7y− 4z s.a 5x + 4y + 6z = 3
3y/2− 2z ≥ 1
(e) min 2x + 7y− 4z s.a 5x + 4y + 6z = 3
3y/z− 2z ≥ 1 z≥ 2
(b) min cos(1) x1+ 2x2− 5x3
s.a 7x1+ 4x2− 2x3 ≤ 5 5x1− 2x2+ 6x3 ≥ 3 x3 ≥ 0
(d) max 2x + 7y− 4z s.a 5x + 4y + 6z = 3
3y2− 2z ≥ 1
(f) max 2x + 7y− 4z s.a 5x + 4y + 6z = 3
7x− 3y + 5z ̸= 0 3y− 2z ≥ 1 Esercizio 2
Una ditta di materiali per l’edilizia pu`o produrre quattro tipi di mattoni, con un profitto rispettivamente di 8, 14, 30, 50 euro per ogni lotto di mattoni prodotto.
Ogni tipo di mattone deve essere sottoposto a quattro processi: mescolamento del calcestruzzo, stampaggio, ispezione, asciugatura. I tempi richiesti (in ore per lotto) sono riportati nella tabella sottostante:
Tipo 1 Tipo 2 Tipo 3 Tipo 4
Mescolamento 1 2 10 16
Stampaggio 1.5 2 4 5
Ispezione 1.5 2 3 5
Asciugatura 3 3 4 3.5
Il direttore della ditta vuole decidere quanto produrre di ciascun tipo di mattoni, in modo da massimizzare il profitto nel prossimo mese, durante il quale
1
vi saranno 800 ore macchina disponibili per il mescolamento, 1000 ore per lo stampaggio e 340 ore per l’ispezione. Il tempo disponibile per l’asciugatura non
`e vincolato. Si formuli il problema come programma lineare.
Esercizio 3
Si vogliono pianificare i turni dei lavoratori di un certo reparto. I turni devo- no ripetersi identici ogni settimana, quindi sar`a sufficiente pianificarli per una singola settimana. In base ad accordi sindacali, ogni turno deve essere formato da una sequenza di cinque giorni di lavoro consecutivi, seguiti da due giorni di riposo (sono dunque possibili sette tipi di turno diversi). Il numero di lavora- tori necessari al corretto funzionamento del reparto varia a seconda del giorno della settimana ed `e indicato da un vettore b con 7 componenti. Si chiede di pianificare i turni in modo che ogni giorno sia garantito il numero minimo di lavoratori necessari, minimizzando il numero di lavoratori complessivamente in servizio.
Esercizio 4
Ogni giorno tre citt`a (A, B e C) producono rispettivamente 500, 400 e 650 ton- nellate di rifiuti, che vengono trasportati verso due impianti per lo smaltimento.
La tabella seguente riporta i costi per il trattamento di una tonnellata di rifiuti presso ciascun impianto, la massima quantit`a trattabile in un giorno (capacit`a) ed il peso dei residui prodotti dallo smaltimento, espresso come percentuale del peso iniziale dei rifiuti trattati.
Costo (euro/t) Capacit`a (t) Residui
Impianto 1 40 850 15%
Impianto 2 30 800 20%
I residui vengono poi trasferiti ed interrati presso due siti, che possono accogliere rispettivamente un massimo di 120 e 200 tonnellate di residui al giorno.
Il trasporto di una tonnellata di rifiuti o residui ha un costo che viene stimato in 3 euro per chilometro. Le distanze (in chilometri) tra le citt`a e gli impianti di smaltimento e tra gli impianti e i siti destinati all’interramento dei residui sono le seguenti:
Impianto 1 Impianto 2
Citt`a A 30 5
Citt`a B 36 42
Citt`a C 25 30
Sito 1 Sito 2
Impianto 1 5 9
Impianto 2 8 6
Si formuli come programma lineare il problema di decidere come gestire lo smaltimento dei rifiuti delle tre citt`a in modo da minimizzare i costi.
Esercizio 5
Ricordiamo che, dato un vettore v∈ Rm, la norma–infinito di v `e definita come
∥v∥∞= max
i=1,...,m|vi|.
2
Siano dati una matrice A di dimensioni m×n ed un vettore b ∈ Rm. Se non abbiamo la garanzia che il sistema Ax = b ammetta soluzioni, possiamo essere interessati a determinare un vettore x∈ Rnche sia una soluzione approssimata dal sitema, cio`e tale che il vettore Ax sia il pi`u vicino possibile al vettore dato b.
Un possibile modo di formalizzare questa richiesta `e cercare un vettore x∈ Rn che minimizzi∥Ax−b∥∞. Scritta pi`u esplicitamente, l’espressione che vogliamo minimizzare `e
i=1,...,mmax ∑n
j=1
aijxj− bi
,
dunque vogliamo trovare una soluzione ottima del problema di ottimizzazione (non vincolata)
xmin∈Rn max
i=1,...,m
∑n
j=1
aijxj− bi
. (1)
(a) Si spieghi perch´e tale problema, scritto nella forma (1), non `e un problema di programmazione lineare.
(b) Si scriva un programma lineare la cui soluzione ottima fornisca una solu- zione ottima del problema (1).
Esercizio 6
Si scriva un programma lineare in forma standard che sia equivalente al seguen- te:
min 2x1+ 5x2 s.a 7x1+ 4x2≥ 2
5x1− 2x2= 3 4x1− 3x2≤ 9 x2≥ 0
3
