Ricerca Operativa a.a. 2015-2016: I appello
(Prof. Fasano Giovanni)
Università Ca’Foscari Venezia - Sede di via Torino
14 gennaio 2016
Regole per l’esame: la violazione delle seguenti regole comporta il
ritiro dell’elaborato e l’allontanamento dello studente dall’aula
∙ È necessario rispondere alle domande e risolvere gli esercizi usando esclusivamente i fogli
distribuiti dal docente.
∙ Ogni risposta/calcolo deve essere opportunamente motivata/o dallo studente.
∙ È necessario scrivere Nome-Cognome-Matricola sul presente foglio e su ciascun foglio contenente le risposte dello studente (i fogli privi di tale informazione saranno cestinati e non
considerati per la valutazione). In aggiunta, è necessario indicare (SI/NO) se il voto della
Prova Intermedia (20 Novembre 2015) deve essere considerato dal docente.
∙ Il tempo complessivo per la prova è di
– 1h 20’ : per gli studenti che hanno superato la Prova Intermedia;
– 3h 05’ : per gli studenti che NON hanno superato la Prova Intermedia.
∙ È necessario risolvere gli esercizi e rispondere alle domande, secondo le seguenti modalità:
– gli studenti che hanno superato la Prova Intermedia devono risolvere/rispondere solo
gli/alle esercizi/domande con (***);
– gli studenti che NON hanno superato la Prova Intermedia devono risolvere/rispondere
tutti gli/le esercizi/domande;
∙ È vietato parlare durante la prova.
∙ È vietato usare durante la prova: testi, appunti, note, dispense, dispositivi cellulari, tablets,
palmari, calcolatori/calcolatrici programmabili.
∙ Durante la prova non è possibile allontanarsi dall’aula.
Nome: . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cognome: . . . . . . . . . . . . . . . . . . . . . . . . .
Matricola: . . . . . . . . . . . .
Considerare la Prova Intermedia:
SI
NO
Esercizio 1
Un’impresa edile deve pianificare il lavoro per l’intera settimana corrente, provvedendo a chiamare
in ciascun giorno un numero di manovali specifico. La settimana lavorativa consiste di 6 giorni (Lun,
Mar, Mer, Gio, Ven, Sab). Il costo giornaliero per chiamare un manovale è riportato nella seguente
tabella, per ogni giorno della settimana lavorativa
Costo giornaliero (Euro) per manovale
Lun
55
Mar
55
Mer
70
Gio
65
Ven
60
Sab
90
Per esigenze contrattuali, se vengono chiamati manovali in uno specifico giorno, per quel giorno deve
essere pagato anche un costo addizionale come da tabella seguente
Costo addizionale (Euro)
Lun
150
Mar
170
Mer
140
Gio
150
Ven
155
Sab
250
Si formuli un modello di PL/PLI che minimizzi i costi di chiamata dei manovali, nell’arco della
settimana lavorativa corrente, tenendo conto dei seguenti vincoli:
1. il numero di manovali chiamati complessivamente nei primi tre giorni (Lun, Mar e Mer) deve
essere non inferiore al numero di manovali chiamato complessivamente nei rimanenti giorni;
2. il numero di manovali occupati in ciascun giorno deve essere non inferiore al numero dei
manovali chiamati nel giorno successivo;
3. per esigenze contrattuali il numero di manovali che lavora Mer deve superare rispettivamente
di almeno 2 e 5 unità, il numero di manovali chiamati Gio e Ven;
4. per note regole di sicurezza sul lavoro, Sab non possono lavorare più del 30% dei manovali che
hanno lavorato Gio.
In aggiunta, la regione nella quale verranno svolti i lavori di edilizia richiede che almeno uno dei
seguenti vincoli sia soddisfatto
∙ bisogna chiamare almeno 12 manovali il Gio;
∙ la somma dei manovali chiamati complessivamente Lun e Mar deve essere almeno di 25 unità.
SOLUZIONE:
Per la scelta delle variabili possiamo usare la seguente:
=
numero di manovali assunti nel giorno 𝑖-simo, 𝑖 = 𝐿𝑢𝑛, 𝑀 𝑎𝑟, 𝑀 𝑒𝑟, 𝐺𝑖𝑜, 𝑉 𝑒𝑛, 𝑆𝑎𝑏
𝑦𝑖
=
{
𝛼, 𝛽
∈
{0, 1},
𝑥𝑖
1
0
se 𝑥𝑖 > 0, 𝑖 = 𝐿𝑢𝑛, 𝑀 𝑎𝑟, 𝑀 𝑒𝑟, 𝐺𝑖𝑜, 𝑉 𝑒𝑛, 𝑆𝑎𝑏,
altrimenti
mentre per i vincoli e la funzione obiettivo risulta:
min (55𝑥1 + 55𝑥2 + 70𝑥3 + 65𝑥4 + 60𝑥5 + 90𝑥6 ) +
(150𝑦1 + 170𝑦2 + 140𝑦3 + 150𝑦4 + 155𝑦5 + 250𝑦6)
𝑥1 + 𝑥2 + 𝑥3 ≥ 𝑥4 + 𝑥5 + 𝑥6
(ridondante !!!)
𝑥𝑖 ≥ 𝑥𝑖+1 ,
𝑖 = 𝐿𝑢𝑛, . . . , 𝑉 𝑒𝑛
𝑥3 ≥ 𝑥4 + 2
𝑥3 ≥ 𝑥5 + 5
𝑥6 ≤ 0.3𝑥4
12 − 𝑥4 ≤ 𝛼𝑀 ,
𝑀 ≫1
25 − 𝑥1 − 𝑥2 ≤ 𝛽𝑀 ,
𝑀 ≫1
𝛼+𝛽 ≤1
𝑥𝑖
,
𝑖 = 𝐿𝑢𝑛, . . . , 𝑆𝑎𝑏
𝑦𝑖 ≥
𝑀
𝑥𝑖 ≥ 0, intera,
𝑖 = 𝐿𝑢𝑛, . . . , 𝑆𝑎𝑏
Esercizio 2 (***)
Si dica (motivandolo) se i vincoli del seguente problema di PL sono in forma canonica. In quest’ultimo
caso, a partire dalla soluzione di base ammissibile corrente si applichino (al più) le prime 2 iterazioni
della fase II del Metodo del Simplesso.
max 3𝑥1 + 4𝑥2 − 𝑥6 + 2𝑥7 − 𝑥8
2𝑥1 − 2𝑥2 + 𝑥3 + 𝑥4 − 𝑥8 = 7
−𝑥1 + 𝑥2 − 𝑥5 + 𝑥6 = 5
𝑥≥0
SOLUZIONE:
Il problema ha i vincoli senz’altro in forma canonica, essendo equivalente a l problema
max 3𝑥1
2𝑥1
−𝑥1
𝑥≥0
+4𝑥2
−2𝑥2
+𝑥2
+0𝑥3
+𝑥3
+0𝑥4
+𝑥4
+0𝑥5
−𝑥6
−𝑥5
+𝑥6
+2𝑥7
−𝑥8
−𝑥8
=
=
7
5
in cui 𝑥3 ed 𝑥6 (oppure 𝑥4 ed 𝑥6 ) sono in base, e tutte le altre variabili sono fuori base. Inoltre è
⎛
⎞
⎛ ⎞
2 −2 +1 +1
0
0 0 −1
7
⎠,
𝑟𝑘(𝐴) = 𝑟𝑘 ⎝
𝑏 = ⎝ ⎠ ≥ 0.
−1 +1
0
0 −1 +1 0
0
5
Applicandoo quindi direttamente la Fase II del Metodo del Simplesso si ottiene alla prima iterazione
⎞
⎛
(∗)
(∗)
⎜ 2 −2 +1 +1 0
0
0 −1
7 ⎟
⎟,
⎜
⎝ −1 +1 0
0 −1 +1 0
0
5 ⎠
−2 −5 0
0 +1 0 −2 +1 −5
essendo il vettore dei guadagni ridotti (cambiato di segno) pari a
−𝛾 𝑇 = (−2 − 5 0 0 + 1 0 − 2 + 1).
Si osservi ora che la colonna della matrice 𝐵 −1 𝑁 relativa alla variabile fuori base 𝑥7 risulta essere
⎛
⎞
0
⎝
⎠ ≤ 0,
0
ed essendo il corrispondente coefficiente di guadagno ridotto pari a +2 (i.e. -2 cambiato di segno),
il problema risulterà illimitato superiormente.
Per ispezione visiva si poteva già desumere quest’ultimo risultato, osservando che la variabile
𝑥7 compare solo nella funzione obiettivo (con coefficiente positivo) e nei vincoli di non-negatività.
Pertanto, rendendo comunque grande la variabile 𝑥7 si rimane nella regione ammissibile e si aumenta
a piacere il valore della funzione obiettivo.
Esercizio 3
Si determini in IR4 il numero massimo (possibile) di vertici del seguente poliedro. Successivamente,
si determinino tali vertici (se esistono).
⎧

 −𝑥2 ≤ 10


⎨ 𝑥2 − 𝑥3 ≥ −2
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 2


−2𝑥2 + 𝑥4 ≤ 7


⎩
𝑥1 + 2𝑥4 ≥ 1
SOLUZIONE:
Essendo 𝑛 = 4 ed 𝑚 = 5, il massimo numero possibile di vertici del poliedro sarà non superiore a
5!
𝑚!
=
= 5.
𝑛!(𝑚 − 𝑛)!
4!
Basterà pertanto considerare i seguenti 5 sistemi di uguaglianze:
(I) in cui
che fornisce il punto
⎧
−𝑥2 = 10


⎨
𝑥2 − 𝑥3 = −2
𝑥

1 + 𝑥2 + 𝑥3 + 𝑥4 = 2

⎩
−2𝑥2 + 𝑥4 = 7
⎞
33
⎜ −10 ⎟
⎟
𝑃1 = ⎜
⎝ −8 ⎠ ,
−13
⎛
il quale soddisfa anche il quinto vincolo e si ha
0 −1 0
0 1 −1
1 1
1
0 −2 0
0
0
1
1
Pertanto il punto 𝑃1 è un vertice del poliedro.
= 1 ∕= 0.
(II) in cui
che fornisce il punto
⎧
−𝑥2 = 10


⎨
𝑥2 − 𝑥3 = −2
𝑥

1 + 𝑥2 + 𝑥3 + 𝑥4 = 2

⎩
𝑥1 + 2𝑥4 = 1
⎛
⎞
39
⎜ −10 ⎟
⎟
𝑃2 = ⎜
⎝ −8 ⎠ ,
−19
il quale soddisfa anche il quinto vincolo e si ha
0 −1 0
0 1 −1
1 1
1
1 0
0
0
0
1
2
Pertanto il punto 𝑃2 è un vertice del poliedro.
= 1 ∕= 0.
(III) in cui
che fornisce il punto
⎧
⎨ −𝑥2 = 10
𝑥2 − 𝑥3 = −2
⎩
−2𝑥2 + 𝑥4 = 7𝑥1 + 2𝑥4 = 1
⎞
27
⎜ −10 ⎟
⎟
𝑃3 = ⎜
⎝ −8 ⎠ ,
−13
⎛
il quale NON soddisfa anche il terzo vincolo. Pertanto il punto 𝑃3 NON è un vertice del
poliedro.
(IV) in cui
che fornisce il punto
⎧
⎨ −𝑥2 = 10
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 2
⎩
−2𝑥2 + 𝑥4 = 7𝑥1 + 2𝑥4 = 1
⎛
⎞
27
⎜ −10 ⎟
⎟
𝑃4 = ⎜
⎝ −2 ⎠ ,
−13
il quale NON soddisfa anche il secondo vincolo. Pertanto il punto 𝑃4 NON è un vertice
del poliedro.
(V) in cui
⎧
⎨ 𝑥2 − 𝑥3 = −2
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 2
⎩
−2𝑥2 + 𝑥4 = 7𝑥1 + 2𝑥4 = 1
che risulta un sistema lineare incompatibile (i.e. non ammette soluzione). Pertanto dal caso
(V) non possono esserci ulteriori vertici.
Esercizio 4 (***)
Dato il seguente grafo: verificare se il vettore di flusso è ammissibile, calcolare il massimo valore del
flusso per il nodo ‘s’, ed indicare un taglio a capacità minima del grafo.
SOLUZIONE:
Dopo una facile verifica il vettore di flusso corrente soddisfa sia i vincoli di capacità che i vincoli di
conservazione, pertanto è ammissibile. Inoltre il valore del flusso iniziale è
𝑓0 = 5.
È possibile considerare i seguenti cammini aumentanti ed i relativi valori del flusso corrispondenti:
∙ 𝑃1 = {𝑠, 1, 6, 𝑡}, con 𝛿 = 2, da cui 𝑓1 = 𝑓0 + 𝛿 = 7
∙ 𝑃2 = {𝑠, 2, 6, 𝑡}, con 𝛿 = 3, da cui 𝑓2 = 𝑓1 + 𝛿 = 10
∙ 𝑃3 = {𝑠, 1, 2, 6, 5, 𝑡}, con 𝛿 = 2, da cui 𝑓3 = 𝑓2 + 𝛿 = 12
∙ 𝑃4 = {𝑠, 2, 6, 5, 𝑡}, con 𝛿 = 1, da cui 𝑓4 = 𝑓3 + 𝛿 = 13
∙ 𝑃5 = {𝑠, 2, 4, 𝑡}, con 𝛿 = 1, da cui 𝑓5 = 𝑓4 + 𝛿 = 14
∙ 𝑃6 = {𝑠, 4, 𝑡}, con 𝛿 = 5, da cui 𝑓6 = 𝑓5 + 𝛿 = 19.
Inoltre un taglio a capacià minima è dato dal seguente:
𝑊 = {𝑠},
¯ = {1, 2, 3, 4, 5, 6, 𝑡},
𝑊
che da un facile controllo soddisfa la condizione
¯ ) = 𝐶(𝑊, 𝑊
¯ ).
𝐹 (𝑊, 𝑊
Domanda Scritta 1
Dato il problema di minimizzazione
min 𝑓 (𝑥)
𝑥∈𝐶
𝑛
con 𝐶 convesso ed 𝑓 : IR → IR, convessa su 𝐶, allora ogni minimo locale del problema è anche un
minimo globale.
Domanda Scritta 2 (***)
Si enunci il Teorema Fondamentale della PL per il problema di massimizzazione
max 𝑐𝑇 𝑥
𝐴𝑥 = 𝑏
𝑥 ≥ 0,
inoltre supponendo che (𝑥𝐵 , 𝑥𝑁 ) sia una soluzione di base ammissibile, ed in corrispondenza si abbia
.
𝐴 = (𝐵 .. 𝑁 ) e 𝑐 = (𝑐 , 𝑐 ), mostrare/dimostrare il criterio di illimitatezza.
𝐵
𝑁