DOMANDE GRUPPO A
1. Date due soluzioni ammissibili x e y dei problemi
min cx max yb
Ax > b
yA = c
y > 0
si ha sempre
A) cx < yb
B)
cx > yb
C) cx = yb
2. Una soluzione di base di un problema di programmazione lineare in forma standard
min cx
Ax = b
x > 0
si dice ammissibile se e solo se
A)
xB = AB-1b >
0
B)
xN > 0
C)
xB = AB-1b >
0
3. Se x* e y* sono soluzioni ottime dei problemi
max cx min yb
Ax = b yA = c
allora
A) (c – y*A)×x* < 0
B) (c – y*A)×x* > 0
C)
(c – y*A)×x* = 0
4. Se una soluzione di base di un problema di minimizzazione in forma standard è ottima, i coefficienti di costo ridotto nella tabella canonica corrispondente a questa soluzione
A) sono minori o uguali a zero
B)
possono avere qualunque segno
C) sono maggiori o uguali a zero
DOMANDE GRUPPO B
1. Una soluzione di base di
un problema di programmazione lineare in forma standard
min cx
Ax = b
x > 0
si dice ammissibile se e
solo se
A)
xB = AB-1b > 0
B)
xB = AB-1b >
0
C)
xN > 0
2. Date due soluzioni ammissibili x e y
dei problemi
min cx max yb
Ax > b yA
= c
y > 0
si ha sempre
A)
cx > yb
B)
cx <
yb
C)
cx
= yb
3. Se una soluzione di base di un problema di
minimizzazione in forma standard è ottima, i
coefficienti di costo ridotto nella
tabella canonica corrispondente a questa soluzione
A)
possono avere qualunque segno
B)
sono
minori o uguali a zero
C)
sono
maggiori o uguali a zero
4. Se x* e y* sono soluzioni ottime
dei problemi
max cx min yb
Ax = b yA = c
allora
A)
(c – y*A)×x* = 0
B)
(c
– y*A)×x* > 0
C)
(c
– y*A)×x* < 0
DOMANDE GRUPPO C
1.
Una
soluzione di base di un problema di programmazione lineare in forma standard
min
cx
Ax = b
x > 0
si dice ammissibile se e
solo se
A)
xN > 0
B)
xB = AB-1b > 0
C)
xB = AB-1b >
0
2. Se x* e y* sono soluzioni ottime
dei problemi
max cx min
yb
Ax = b yA = c
allora
A)
(c – y*A)×x* < 0
B)
(c – y*A)×x* = 0
C)
(c
– y*A)×x* > 0
3. Se una soluzione di base
di un problema di minimizzazione in forma standard è ottima, i coefficienti di
costo ridotto nella tabella canonica corrispondente a questa soluzione
A)
sono
minori o uguali a zero
B)
sono
maggiori o uguali a zero
C)
possono avere qualunque segno
4. Date due soluzioni ammissibili x e y
dei problemi
min cx max yb
Ax > b yA = c
y > 0
si ha sempre
A)
cx
= yb
B)
cx > yb
C)
cx <
yb
DOMANDE GRUPPO D
1. Date due soluzioni ammissibili x e y
dei problemi
min cx max yb
Ax > b yA = c
y > 0
si ha sempre
A)
cx
= yb
B)
cx > yb
C)
cx <
yb
2. Se x* e y* sono soluzioni ottime
dei problemi
max cx min yb
Ax = b yA = c
allora
A)
(c
– y*A)×x* < 0
B)
(c – y*A)×x* = 0
C)
(c
– y*A)×x* > 0
3. Una soluzione di base di un problema di
programmazione lineare in forma standard
min cx
Ax = b
x
> 0
si dice ammissibile se e
solo se
A)
xB = AB-1b > 0
B)
xN > 0
C)
xB = AB-1b >
0
4. Se una soluzione di base
di un problema di minimizzazione in forma standard è ottima, i coefficienti di
costo ridotto nella tabella canonica corrispondente a questa soluzione
A)
possono avere qualunque segno
B)
sono
minori o uguali a zero
C)
sono
maggiori o uguali a zero
PROBLEMI
(Si dettaglia il procedimento relativamente ai problemi del gruppo A. Per gli
altri gruppi si indica solo la soluzione)
5. Very
Old Economy I
Indichiamo rispettivamente con x1, x2 e x3 il quantitativo di yogurt, benzina e spirito da utilizzare nella nuova formula di Madduorm. Siccome 100 grammi di yogurt forniscono 25 grammi di (2, 3)-benzodiavolopirina a e 45 grammi di b-butademoniene, x1 grammi di yogurt ne forniranno rispettivamente 0,25x1 e 0,45x1, e analogamente gli altri ingredienti. D’altra parte, essendo richiesti esattamente 4 grammi del primo principio e 4,5 del secondo, deve valere il seguente sistema di vincoli:
0,25x1 + 0,25x2 + 0,10x3 = 4,00
0,45x1 + 0,15x2 + 0,20x3 = 4,50
x1, x2, x3 > 0
L’obiettivo consiste nel minimizzare la funzione di costo
c(x1, x2, x3) = 45x1 + 15x2 + 8x3
Moltiplicando le equazioni per 100/5 = 20 si ottiene il problema di programmazione lineare
min 45x1 + 15x2 + 8x3
5x1 + 5x2 + 2x3 = 80
9x1 + 3x2 + 4x3 = 90
x1, x2, x3 > 0
che è in forma standard non canonica. Per ottenere una soluzione iniziale di base si può adottare il metodo delle variabili ausiliarie. Il problema ausiliario si scrive
min z1 + z2
5x1 + 5x2 + 2x3 + z1 = 80
9x1 + 3x2 + 4x3
+ z2 = 90
x1, x2,
x3, z1, z2
> 0
La sua tabella
0 0 0 1 1
0
5 5 2 1 0 80
9 3 4 0 1
90
viene resa canonica sottraendo le righe 1 e 2 alla riga 0:
–14 –8
–6 0 0 –170
5 5 2 1 0 80
9
3 4 0 1 90
Scegliendo il secondo elemento della riga 1 come pivot si ricava la soluzione di base precedentemente indicata
0
–10/3 2/9
0
14/9 –30
0 10/3 –2/9 1 –5/9 30
1
1/3 4/9
0
1/9 10
Operando un ulteriore pivot sul primo elemento della seconda colonna si ottiene una base ottima per il problema ausiliario:
0
0 0 1 1 0
0 1 –1/15 3/10 –1/6 9
1
0 7/15 –1/10 1/6 7
A questo punto è possibile eliminare le due colonne relative alle variabili ausiliarie, rirpistinare la funzione obiettivo originaria e ritornare al problema iniziale:
45
15 8 0
0 1 –1/15 9
1
0 7/15 7
Per portare la tabella in forma canonica si deve ora sottrarre alla riga 0 la prima riga moltiplicata per 15 e la seconda moltiplicata per 45: 1 – 21 = -20
0 0 –12 –450
0 1 –1/15 9
1
0 7/15 7
Dunque la soluzione corrente costa 450 Euro. Eseguendo un’operazione di pivot sul secondo elemento della terza colonna si ottiene ora
180/7
0 0 –270
1/7 1 0 10
15/7 0 1 15
La soluzione corrispondente (x1 = 0, x2 = 10, x3 = 15) è ottima.
Le soluzioni ottime dei gruppi B, C, D sono:
B x1 = 0 x2
= 9 x3 =
14
C x1 = 0 x2
= 9 x3 =
14
D x1 = 0 x2
= 12/5 x3 = 46/5
6. Very Old Economy II
Dal problema precedente si ricava che per produrre 100 grammi di Madduorm sono necessari 10 grammi di benzina verde e 15 di spirito di patate. Dai dati di questo problema si ha invece che produrre 100 grammi di Scetate B12 richiede 6 grammi di yogurt ai frutti di bosco, 12 grammi di benzina verde e 10 grammi di spirito di patate. D’altronde, 100 grammi di Madduorm corrispondono a 10 confezioni e quindi a un profitto di 12´10 = 120 Euro, mentre 100 grammi di Scetate B12 corrispondono a 5 confezioni e dunque a un profitto di 5´28 = 140 Euro. In conclusione, indicati rispettivamente con xm e xs il livello di produzione (in chilogrammi) di Madduorm e di Scetate B12, si può impostare il seguente problema di programmazione lineare:
max 1200xm
+ 1400xs
6xs < 1000
10xm + 12xs <
1200
15xm + 10xs =
1300
xm, xs > 0
Il vincolo di eguaglianza corrisponde alla specifica di esaurire le scorte di spirito di patate (per curiosità, questo problema ammette la soluzione ottima xm* = 45, xs* = 125/2 = 62,5).
Il duale si scrive
min 1000y1
+ 1200y2 + 1300y3
10y2 + 15y3 > 1200
6y1 + 12y2 + 10y3 > 1400
y1, y2 > 0
dove y1, y2 e y3 rappresentano i prezzi impliciti di yogurt ai frutti di bosco, benzina verde e spirito di patate.
7. Poi dice a che serve la
ricerca operativa…
Riportiamo la tabella riassuntiva del numero di crediti e del numero di libri da leggere:
Materia Crediti Libri da leggere
1. Scientologia I 7 4
2. Baccanali I 8 5
3. Culti Orfici 9 6
4. Paganesimo Applicato 5 6
5. Ricerca Operativa 2 3
Il problema si formula:
max 7x1 + 8x2 + 9x3 + 5x4 + 2x5
4x1 + 5x2 + 6x3 + 6x4 + 3x5 < 14
0 < x1, …, x5 < 1, interi
I rapporti crediti/libri sono i seguenti:
Materia Crediti/Libri
1. Scientologia I 1,75
2. Baccanali I 1,60
3. Culti Orfici 1,50
4. Paganesimo Applicato 0,83
5. Ricerca Operativa 0,67
L’algoritmo Greedy trova la soluzione (0, 1, 1, 0, 1) di valore 19 (corrispondente a scegliere Baccanali I, Culti Orfici e Ricerca Operativa). La sua modifica che tiene conto dei rapporti sopra calcolati fornisce invece la soluzione (0, 1, 1, 0, 0) di valore 17. Adottiamo quindi il valore della prima delle due soluzioni come limitazione inferiore.
Il rilassamento lineare del problema ammette la soluzione ottima (1, 1, 5/6, 0, 0) di valore 22,5. Quest’ultimo può essere assunto come limitazione superiore iniziale.
Applicando quindi uno schema di branch-and-bound a partire da tali valori si ricava che la soluzione ottima x* = (0, 1, 1, 0, 1) coincide in effetti con la soluzione greedy inizialmente adottata.
B Soluzione ottima: (1, 0, 1, 0, 1) di valore 16
Limitazioni inferiori: greedy 15, greedy modificato 15
Limitazione superiore: rilassamento lineare (1, 1, 5/6, 0, 0) di valore 19.66
C Soluzione ottima: (1, 0, 1, 0, 0) di valore 19, ,
Limitazioni inferiori: greedy 19, greedy modificato 17
Limitazione superiore: rilassamento lineare (1, 1, 0.428, 0, 0) di valore 20.85
D Soluzione ottima: (1, 1, 0, 0, 1) di valore 18,
Limitazioni inferiori: greedy 16, greedy modificato 16,
Limitazione superiore: rilassamento lineare (1, 1, 0.4, 0, 0) di valore 18.8