Prova scritta di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica

(1)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

8 giugno 2012

Compito A

Istruzioni

• Usate i fogli bianchi allegati per calcoli, ragionamenti e quanto altro reputiate necessario fare per rispondere alle 10 domande seguenti.

• Per ciascuna delle 10 domande indicare in corrispondenza di ciascuna delle affermazioni a), b), c) e d) se essa `e VERA o FALSA, apponendo un segno sul rettangolo VERO o sul rettangolo

FALSO sul foglio risposte.

• Ricordatevi di scrivere su tale foglio risposte tutte le informazioni richieste ed in particolare il vostro nome e cognome (i fogli senza nome e cognome saranno cestinati e dovrete ripetere l’esame in un’altra sessione).

• Avete un’ora esatta di tempo per svolgere gli esercizi. Al termine del tempo dovete consegnare il solo foglio risposte (potete tenere il testo delle domande e i fogli bianchi).

• Ricordatevi di segnare esattamente sui fogli che rimarranno a voi le risposte che avete dato in modo da potervi autovalutare una volta che vi verr`a fornita la soluzione.

• Scaduta l’ora rimanete seduti. Passeremo a raccogliere i fogli risposte. Chi non consegna immediatamente il foglio al nostro passaggio non avrà altra possibilità di consegna e dovrà ripetere l’esame in un altro appello.

• ATTENZIONE. Durante la prova di esame:

– Non `e possibile parlare, per nessuna ragione, con i vostri colleghi.

– Non `e possibile allontanarsi dall’aula.

– Non si possono usare telefoni cellulari

– Non si possono usare calcolatrici, palmari o simili – Non `e possibile usare dispense, libri o appunti.

Chi contravviene anche a una sola di queste regole dovr`a ripetere la prova di esame in altro appello.

Valutazione

• Per ogni affermazione VERO/FALSO correttamente individuata viene assegnato 1 punto

• Per ogni affermazione VERO/FALSO non risposta vengono assegnati 0 punti

• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti

Supera la prova chi totalizza un punteggio pari ad almeno 28 punti

(2)

1. Dire quali delle seguenti affermazioni sono corrette.

(a) L’insieme {x ∈ IR³ | 2x1+ x2− 3x3 = −1, − x1+ 7x2− x3 = 3, 2x1+ 2x2 = 11, x1≥ 0, x2≥ 0, x3≥ 0} `e un poliedro in forma standard.

(b) In IR³ l’intersezione tra una piramide e un cubo pu`o essere un poliedro.

(c) Se un poliedro `e costituito da un numero di punti distinti strettamente maggiore di 1, allora contiene infiniti punti.

(d) L’insieme delle soluzioni di un sistema lineare `e un poliedro se e solo se la matrice del sistema ha rango massimo.

(a) In IR³, la sfera {x ∈ IR | x²₁+ x²₂+ x²₃≤ 1} ha un numero finito di vertici.

(b) Sia P poliedro P = {x ∈ IRⁿ | Ax = b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, con P 6= ∅. Allora P ammette sempre vertici.

(c) Il poliedro {x ∈ IRⁿ | Ax ≥ b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, non pu`o in nessun caso ammettere l’origine come vertice.

(d) Sia dato un poliedro P = {x ∈ IRⁿ | Ax ≥ b}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m. P pu`o ammette vertici solamente se m ≥ n.

3. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta x_B = (x₁, α₂, α₃, x₄)^T, x_N = (x₃, α₄, α₁, x₂)^T,

B⁻¹N =







0 −1 1 0

−1 0 1 2

0 1 3 0

9 1 2 8







, B⁻¹b =





 7 0 0 2





 .

Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema originario non `e ammissibile.

(b) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.

(c) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)^T.

(d) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x2, x4)^T.

4. Si consideri il poliedro descritto dal seguente sistema x1− x2+ 2x3+ 2x4 = 3

2x1+ 4x3− x4 = 6 3x₁+ x₂+ 6x₃+ x₄ = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto (1, 0, 1, 0)^T `e vertice del poliedro.

(b) L’origine degli assi `e vertice del poliedro.

(c) Il poliedro non ammette vertici.

(3)

(d) Il punto (3, 0, 0, 0)^T `e vertice del poliedro.

5. Sia P un problema di Programmazione Lineare in forma standard e tale che l’insieme ammissibile `e non vuoto. Dire quali delle seguenti affermazioni sono corrette.

(a) La Fase II del metodo del simplesso in un numero finito di iterazioni determina una soluzione ottima del problema P.

(b) Al problema P si può applicare direttamente la Fase II del metodo del simplesso perché il problema è in forma standard ed inoltre si è assunto che l’insieme ammissibile sia non vuoto.

(c) L’insieme ammissibile del problema P contiene sicuramente un vertice.

(d) L’insieme ammissibile del problema P `e un politopo.

6. Si consideri il seguente poliedro definito da

x1+ αx2+ 2x3 ≥ 3 4x1+ βx2+ 8x3 ≥ 12

x₁ ≥ 0 x2 ≥ 0 x₃ ≥ 1

con α ∈ IR, β ∈ IR. Dire quali delle seguenti affermazioni sono corrette.

(a) Posto α = 0, il punto (1, 0, 1)^T `e vertice del poliedro per ogni valore di β.

(b) Il punto (1, 1, 1)^T appartiene al poliedro per ogni valore di α e β.

(c) Per α = β = 0 il poliedro `e vuoto.

(d) Il punto (2, 0, 1/2)^T `e vertice del poliedro per ogni valore di α e β.

7. Sia dato un problema di Programmazione Lineare in forma standard con A =

2 0 3 1 1 2

3 1 1 1 0 1

, c = (1, − 1, 2, 3, 0, 1)^T, b = (1, 0)^T

(a) Per poter risolvere questo problema con il metodo del simplesso è indispensabile effet- tuare prima la Fase I perché il problema non è in forma canonica.

(b) Se si considera la base formata dalla 5âe dalla 6âcolonna, la soluzione di base ammissibile (SBA) associata non soddisfa il criterio di ottimalità.

(c) La SBA associata alla base formata dalla 5â e dalla 2â colonna e la SBA associata alla base formata dalla 5â e dalla 6â colonna coincidono.

(d) Il criterio di illimitatezza è soddisfatto in corrispondenza della base formata dalla 5â e dalla 2â colonna.

8. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x1, x6, x8, x3)^T e xN = (x2, x5, x4, x7)^T, ed inoltre risulta γ = (1, −2, 0, −1)^T.

(4)

B⁻¹N =







9 0 −9 1

2 1 11 0

−1 −3 −3 1

−7 1 −1 1







, B⁻¹b =





 0 2 1 1





 .

(a) Supponiamo che x5sia la variabile entrante. Allora risulta ¯ρ = 0.

(b) Supponiamo che x₇ sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.

(c) Supponiamo che x₅sia la variabile entrante. Allora la variabile uscente deve essere x₃. (d) Supponiamo che x₇ sia la variabile entrante. Allora la variabile uscente pu`o essere x₈

oppure x₃.

9. Si considerino i seguenti due problemi

(A)







min c^Tx Ax ≥ b

x ≥ 0, x intero

(B)







min c^Tx Ax ≥ b x ≥ 0,

(a) Se x^∗è soluzione ottima di (A) e y^∗è soluzione ottima di (B) allora risulta c^Ty^∗≤ c^Tx^∗. (b) Se una soluzione ottima di (B) è intera, allora essa è soluzione ottima di (A).

(c) Se x^∗`e una soluzione ottima di (B) e ¯x una soluzione ammissibile per (A) tale che risulti c^Tx^∗= c^Tx allora ¯¯ x `e una soluzione ottima di (A).

(d) Sia P una formulazione lineare del problema (A). Se b `e intero e A totalmente unimo- dulare, allora P ha tutti vertici interi.

10. Si consideri il seguente problema di Programmazione Lineare (P):

min c^Tx Ax ≤ b Dire quali delle seguenti affermazioni sono corrette.

(a) Il suo problema duale `e

min b^Tu

−A^Tu = c u ≥ 0.

(b) Il suo problema duale `e

max b^Tu A^Tu ≤ −c

(c) Se il problema (P ) `e inammissibile, allora anche il suo duale `e inammissibile.

(d) Il problema duale di un problema di Programmazione Lineare presenta tante varibili vincolate in segno quanti sono i vincoli di disuguaglianza del problema primale.

(5)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

8 giugno 2012

Compito B

Istruzioni

Valutazione

(6)

2x1+ 4x3− x4 = 6 3x1+ x2+ 6x3+ x4 = 9

x_i≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(a) Il poliedro non ammette vertici.

(b) Il punto (1, 0, 1, 0)^T `e vertice del poliedro.

(c) L’origine degli assi `e vertice del poliedro.

(d) Il punto (3, 0, 0, 0)^T `e vertice del poliedro.

2 0 3 1 1 2

3 1 1 1 0 1

, c = (1, − 1, 2, 3, 0, 1)^T, b = (1, 0)^T Dire quali delle seguenti affermazioni sono corrette.

(a) La SBA associata alla base formata dalla 5â e dalla 2â colonna e la SBA associata alla base formata dalla 5â e dalla 6â colonna coincidono.

(b) Il criterio di illimitatezza è soddisfatto in corrispondenza della base formata dalla 5â e dalla 2â colonna.

(c) Per poter risolvere questo problema con il metodo del simplesso è indispensabile effet- tuare prima la Fase I perché il problema non è in forma canonica.

(d) Se si considera la base formata dalla 5âe dalla 6âcolonna, la soluzione di base ammissibile (SBA) associata non soddisfa il criterio di ottimalità.

(a) Al problema P si può applicare direttamente la Fase II del metodo del simplesso perché il problema è in forma standard ed inoltre si è assunto che l’insieme ammissibile sia non vuoto.

(b) L’insieme ammissibile del problema P contiene sicuramente un vertice.

(c) La Fase II del metodo del simplesso in un numero finito di iterazioni determina una soluzione ottima del problema P.

4. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha x_B= (x₁, x₆, x₈, x₃)^T e x_N = (x₂, x₅, x₄, x₇)^T, ed inoltre risulta γ = (1, −2, 0, −1)^T.

B⁻¹N =







9 0 −9 1

2 1 11 0

−1 −3 −3 1

−7 1 −1 1







, B⁻¹b =





 0 2 1 1





 .

(7)

(a) Supponiamo che x₇ sia la variabile entrante. Allora la variabile uscente pu`o essere x₈ oppure x₃.

(b) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.

(c) Supponiamo che x₅sia la variabile entrante. Allora risulta ¯ρ = 0.

(d) Supponiamo che x5sia la variabile entrante. Allora la variabile uscente deve essere x3. 5. Si consideri il seguente poliedro definito da

x₁+ αx₂+ 2x₃ ≥ 3 4x1+ βx2+ 8x3 ≥ 12

x₁ ≥ 0 x2 ≥ 0 x3 ≥ 1

(a) Il punto (1, 1, 1)^T appartiene al poliedro per ogni valore di α e β.

(b) Il punto (2, 0, 1/2)^T `e vertice del poliedro per ogni valore di α e β.

(c) Per α = β = 0 il poliedro `e vuoto.

(d) Posto α = 0, il punto (1, 0, 1)^T `e vertice del poliedro per ogni valore di β.

6. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (x1, α2, α3, x4)^T, xN = (x3, α4, α1, x2)^T,

B⁻¹N =







0 −1 1 0

−1 0 1 2

0 1 3 0

9 1 2 8







, B⁻¹b =





 7 0 0 2





 .

(a) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)^T.

(b) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.

(d) Il problema originario non `e ammissibile.

(A)







min c^Tx Ax ≥ b

x ≥ 0, x intero

(B)







(8)

(a) In IR³ l’intersezione tra una piramide e un cubo pu`o essere un poliedro.

(b) L’insieme {x ∈ IR³ | 2x1+ x₂− 3x3 = −1, − x₁+ 7x₂− x3 = 3, 2x₁+ 2x₂ = 11, x₁≥ 0, x2≥ 0, x3≥ 0} `e un poliedro in forma standard.

(c) L’insieme delle soluzioni di un sistema lineare `e un poliedro se e solo se la matrice del sistema ha rango massimo.

(d) Se un poliedro `e costituito da un numero di punti distinti strettamente maggiore di 1, allora contiene infiniti punti.

max b^Tu A^Tu ≤ −c (b) Il suo problema duale `e

min b^Tu

−A^Tu = c u ≥ 0.

(c) Il problema duale di un problema di Programmazione Lineare presenta tante varibili vincolate in segno quanti sono i vincoli di disuguaglianza del problema primale.

(d) Se il problema (P ) `e inammissibile, allora anche il suo duale `e inammissibile.

(a) Il poliedro {x ∈ IRⁿ | Ax ≥ b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, non pu`o in nessun caso ammettere l’origine come vertice.

(b) Sia dato un poliedro P = {x ∈ IRⁿ | Ax ≥ b}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m. P pu`o ammette vertici solamente se m ≥ n.

(c) In IR³, la sfera {x ∈ IR | x²₁+ x²₂+ x²₃≤ 1} ha un numero finito di vertici.

(d) Sia P poliedro P = {x ∈ IRⁿ | Ax = b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, con P 6= ∅. Allora P ammette sempre vertici.

(9)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

8 giugno 2012

Compito C

Istruzioni

Valutazione

(10)

(a) In IR³, la sfera {x ∈ IR | x²₁+ x²₂+ x²₃≤ 1} ha un numero finito di vertici.

(b) Sia dato un poliedro P = {x ∈ IRⁿ | Ax ≥ b}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m. P pu`o ammette vertici solamente se m ≥ n.

(c) Sia P poliedro P = {x ∈ IRⁿ | Ax = b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, con P 6= ∅. Allora P ammette sempre vertici.

(d) Il poliedro {x ∈ IRⁿ | Ax ≥ b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, non pu`o in nessun caso ammettere l’origine come vertice.

2 0 3 1 1 2

3 1 1 1 0 1

(a) Il criterio di illimitatezza è soddisfatto in corrispondenza della base formata dalla 5â e dalla 2â colonna.

(b) Se si considera la base formata dalla 5âe dalla 6âcolonna, la soluzione di base ammissibile (SBA) associata non soddisfa il criterio di ottimalità.

(c) Per poter risolvere questo problema con il metodo del simplesso è indispensabile effet- tuare prima la Fase I perché il problema non è in forma canonica.

(d) La SBA associata alla base formata dalla 5â e dalla 2â colonna e la SBA associata alla base formata dalla 5â e dalla 6â colonna coincidono.

2x₁+ 4x₃− x4 = 6 3x1+ x2+ 6x3+ x4 = 9

x_i≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto (3, 0, 0, 0)^T `e vertice del poliedro.

(c) Il poliedro non ammette vertici.

(d) L’origine degli assi `e vertice del poliedro.

(a) L’insieme {x ∈ IR³ | 2x1+ x2− 3x3 = −1, − x1+ 7x2− x3 = 3, 2x1+ 2x2 = 11, x1≥ 0, x2≥ 0, x3≥ 0} `e un poliedro in forma standard.

(b) L’insieme delle soluzioni di un sistema lineare `e un poliedro se e solo se la matrice del sistema ha rango massimo.

(c) Se un poliedro `e costituito da un numero di punti distinti strettamente maggiore di 1, allora contiene infiniti punti.

(d) In IR³ l’intersezione tra una piramide e un cubo pu`o essere un poliedro.

(11)

(b) L’insieme ammissibile del problema P contiene sicuramente un vertice.

(c) La Fase II del metodo del simplesso in un numero finito di iterazioni determina una soluzione ottima del problema P.

6. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (x1, α2, α3, x4)^T, xN = (x3, α4, α1, x2)^T,

B⁻¹N =







0 −1 1 0

−1 0 1 2

0 1 3 0

9 1 2 8







, B⁻¹b =





 7 0 0 2





 .

(a) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)^T.

(b) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x2, x4)^T.

(c) Il problema originario non `e ammissibile.

(d) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.

(a) Se il problema (P ) `e inammissibile, allora anche il suo duale `e inammissibile.

(b) Il suo problema duale `e

max b^Tu A^Tu ≤ −c

(d) Il suo problema duale `e

min b^Tu

−A^Tu = c u ≥ 0.

(12)

8. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha x_B= (x₁, x₆, x₈, x₃)^T e x_N = (x₂, x₅, x₄, x₇)^T, ed inoltre risulta γ = (1, −2, 0, −1)^T.

B⁻¹N =







9 0 −9 1

2 1 11 0

−1 −3 −3 1

−7 1 −1 1







, B⁻¹b =





 0 2 1 1





 .

(a) Supponiamo che x7 sia la variabile entrante. Allora la variabile uscente pu`o essere x8

oppure x3.

(b) Supponiamo che x5sia la variabile entrante. Allora la variabile uscente deve essere x3. (c) Supponiamo che x5sia la variabile entrante. Allora risulta ¯ρ = 0.

(d) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.

x1+ αx2+ 2x3 ≥ 3 4x₁+ βx₂+ 8x₃ ≥ 12

x1 ≥ 0 x2 ≥ 0 x3 ≥ 1

(a) Posto α = 0, il punto (1, 0, 1)^T `e vertice del poliedro per ogni valore di β.

(b) Per α = β = 0 il poliedro `e vuoto.

(c) Il punto (1, 1, 1)^T appartiene al poliedro per ogni valore di α e β.

(d) Il punto (2, 0, 1/2)^T `e vertice del poliedro per ogni valore di α e β.

(A)







min c^Tx Ax ≥ b

x ≥ 0, x intero

(B)







(13)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

8 giugno 2012

Compito D

Istruzioni

Valutazione

(14)

x1+ αx2+ 2x3 ≥ 3 4x1+ βx2+ 8x3 ≥ 12

x1 ≥ 0 x₂ ≥ 0 x3 ≥ 1

(a) Il punto (2, 0, 1/2)^T `e vertice del poliedro per ogni valore di α e β.

(b) Posto α = 0, il punto (1, 0, 1)^T `e vertice del poliedro per ogni valore di β.

(c) Il punto (1, 1, 1)^T appartiene al poliedro per ogni valore di α e β.

(d) Per α = β = 0 il poliedro `e vuoto.

(A)







min c^Tx Ax ≥ b

x ≥ 0, x intero

(B)







2 0 3 1 1 2

3 1 1 1 0 1

(a) Se si considera la base formata dalla 5âe dalla 6âcolonna, la soluzione di base ammissibile (SBA) associata non soddisfa il criterio di ottimalità.

(b) Per poter risolvere questo problema con il metodo del simplesso è indispensabile effet- tuare prima la Fase I perché il problema non è in forma canonica.

(c) Il criterio di illimitatezza è soddisfatto in corrispondenza della base formata dalla 5â e dalla 2â colonna.

(d) La SBA associata alla base formata dalla 5â e dalla 2â colonna e la SBA associata alla base formata dalla 5â e dalla 6â colonna coincidono.

(15)

max b^Tu A^Tu ≤ −c (b) Il suo problema duale `e

min b^Tu

−A^Tu = c u ≥ 0.

(d) Se il problema (P ) `e inammissibile, allora anche il suo duale `e inammissibile.

5. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x1, x6, x8, x3)^T e xN = (x2, x5, x4, x7)^T, ed inoltre risulta γ = (1, −2, 0, −1)^T.

B⁻¹N =







9 0 −9 1

2 1 11 0

−1 −3 −3 1

−7 1 −1 1







, B⁻¹b =





 0 2 1 1





 .

(a) Supponiamo che x7 sia la variabile entrante. Allora la variabile uscente pu`o essere x8

oppure x3.

(b) Supponiamo che x₇ sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.

(c) Supponiamo che x₅sia la variabile entrante. Allora la variabile uscente deve essere x₃. (d) Supponiamo che x5sia la variabile entrante. Allora risulta ¯ρ = 0.

(a) Se un poliedro `e costituito da un numero di punti distinti strettamente maggiore di 1, allora contiene infiniti punti.

(b) L’insieme delle soluzioni di un sistema lineare `e un poliedro se e solo se la matrice del sistema ha rango massimo.

(c) In IR³ l’intersezione tra una piramide e un cubo pu`o essere un poliedro.

(d) L’insieme {x ∈ IR³ | 2x1+ x2− 3x3 = −1, − x1+ 7x2− x3 = 3, 2x1+ 2x2 = 11, x1≥ 0, x2≥ 0, x3≥ 0} `e un poliedro in forma standard.

7. Si consideri il poliedro descritto dal seguente sistema x₁− x2+ 2x₃+ 2x₄ = 3

2x1+ 4x3− x4 = 6 3x₁+ x₂+ 6x₃+ x₄ = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(16)

(a) L’origine degli assi `e vertice del poliedro.

(c) Il punto (3, 0, 0, 0)^T `e vertice del poliedro.

(d) Il poliedro non ammette vertici.

8. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta x_B = (x₁, α₂, α₃, x₄)^T, x_N = (x₃, α₄, α₁, x₂)^T,

B⁻¹N =







0 −1 1 0

−1 0 1 2

0 1 3 0

9 1 2 8







, B⁻¹b =





 7 0 0 2





 .

(a) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.

(b) Il problema originario non `e ammissibile.

(d) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)^T.

(b) La Fase II del metodo del simplesso in un numero finito di iterazioni determina una soluzione ottima del problema P.

(c) L’insieme ammissibile del problema P `e un politopo.

(d) L’insieme ammissibile del problema P contiene sicuramente un vertice.

(a) Sia P poliedro P = {x ∈ IRⁿ | Ax = b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, con P 6= ∅. Allora P ammette sempre vertici.

(b) In IR³, la sfera {x ∈ IR | x²₁+ x²₂+ x²₃≤ 1} ha un numero finito di vertici.

(c) Sia dato un poliedro P = {x ∈ IRⁿ | Ax ≥ b}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m. P pu`o ammette vertici solamente se m ≥ n.

(d) Il poliedro {x ∈ IRⁿ | Ax ≥ b, x ≥ 0}, con A matrice m × n, x ∈ IRⁿ, b ∈ IR^m, non pu`o in nessun caso ammettere l’origine come vertice.