Corso di Laurea in
Ingegneria Informatica e Ingegneria Automatica Corso di RICERCA OPERATIVA
PROVA di AUTOVALUTAZIONE N.8
ESERCIZI
1. Dopo aver verificato che `e possibile applicare direttamente la fase II del metodo del simplesso, risolvere i seguenti problemi di Programmazione Lineare:
(a)
min −5x1− 7x2− 12x3+ x4
2x1+ 3x2+ 2x3+ x4 ≤ 38 3x1+ 2x2+ 4x3− x4 ≤ 55 x1 ≥ 0, x2 ≥ 0, x3≥ 0, x4 ≥ 0 (b)
max 5x1+ 3x2+ 2x3
4x1+ 5x2+ 2x3+ x4≤ 20 3x1+ 4x2− x3+ x4≤ 30 x1≥ 0, x2≥ 0, x3 ≥ 0, x4 ≥ 0 (c)
min −x1− 2x2+ x3− x4− 4x5+ 2x6 x1+ x2+ x3+ x4+ x5+ x6+ x7 = 6 2x1− x2− 2x3+ x4+ x8= 4
x3+ x4+ 2x5+ x6+ x9 = 4 x ≥ 0
2. Applicare la fase I del metodo del simplesso al seguente problema di Programmazione Lineare e deter- minare se il problema `e ammissibile; in caso affermativo determinare la forma canonica iniziale della fase II:
min −x1+ x2
−2x1+ x2≤ 2
−x1+ 2x2≥ 8 x1+ x2≤ 6 x1 ≥ 0, x2 ≥ 0.
3. Alla fine della fase I del metodo del simplesso si ottiene la seguente forma canonica (riferita, quindi, alla base ottima):
min α1+ α2+ α3
α1
x1
α2
+
0 −1 −1 0
2 6 4 2
0 −4 0 −2
x2 α3
x3 x4
=
2 10
0
.
Determinare se il problema originario dal quale `e stato costruito il problema ausiliario `e ammissibile e in caso affermativo determinare la forma canonica iniziale della fase II.
4. Applicando il metodo del simplesso risolvere i seguenti problemi di Programmazione Lineare:
(a)
min −x1− 3x2− 2x4+ 2x5 x1+ 2x2+ x3− x5= 1 x2+ x4 = 2
2x1+ x2+ x3− x4= 6 x ≥ 0
(b)
min x1+ x2− x3 x1− x2+ x3 = 2 x1+ 2x2− x3− x4= 2 x ≥ 0
QUESTIONARIO
1. Dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione ottima del problema artificiale che si risolve nella fase I del metodo del simplesso `e sempre degenere.
(b) Il problema artificiale che si risolve nella fase I del metodo del simplesso pu`o avere una SBA con valore della funzione obiettivo negativo.
(c) Il problema artificiale che si risolve nella fase I del metodo del simplesso non pu`o essere illimitato inferiormente.
(d) Se una SBA del problema artificiale che si risolve nella fase I del metodo del simplesso ha valore della funzione obiettivo pari a zero, allora `e ottima.
2. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (x2, α2, α3, x3)T, xN = (x1, x4, α4, α1)T,
B−1N =
5 6 −1 0
0 −1 6 3
0 0 5 2
1 0 2 1
, B−1b =
3 0 0 5
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario non `e ammissibile.
(b) `E presente un vincolo ridondante.
(c) Una base ammissibile per il problema originario da cui far partire la fase II `e data da xB = (x2, x4, x3)T
(d) La matrice dei vincoli del problema originario ha rango pieno.
