RICERCA OPERATIVA

Esercizio del 20 marzo 2003

Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Matricola: |__|__|__|__|__|__|

1. Formulare il duale D del seguente problema

P) min 2x₁ + x₂ + 5x₃

x₁ + 3x₃ > 6

x₁ + x₂ + 2x₃ = 3

x₁, x₂ > 0

2. Riscrivere il problema D in forma standard, determinarne una soluzione di base ammissibile e riportarla tra le parentesi seguenti: ( )

3. Risolvere il problema D con il metodo del simplesso. Cosa possiamo dire del problema P?

(A) E’ illimitato inferiormente.

(B) Non ammette soluzione.

(C) Ammette una soluzione ottima finita.

Risoluzione

1. Il duale del problema P si scrive

D) max 6y₁ + 3y₂

y₁ + y₂ < 2

y₂ < 1

3y₁ + 2y₂ = 5

y₁ > 0

e in forma standard

D’) max 6y₁ + 3y₂

y₁ + u₂ – v₂ + w₁ = 2

u₂ – v₂ + w₂ = 1

3y₁ + 2u₂ – 2v₂ = 5

y₁, u₂, v₂ > 0

2. Per determinare una soluzione di base ammissibile del problema D’ consideriamo il problema ausiliario A ottenuto aggiungendo una variabile ausiliaria non negativa w₃ al terzo vincolo:

A) min w₃

y₁ + u₂ – v₂ + w₁ = 2

u₂ – v₂ + w₂ = 1

3y₁ + 2u₂ – 2v₂ + w₃ = 5

y₁, u₂, v_2, w₁, w₂, w₃ > 0

y₁ u₂ v₂ w₁ w₂ w₃

0 0 0 0 0 1 0

1 1 -1 1 0 0 2

0 1 -1 0 1 0 1

3 2 -2 0 0 1 5

y₁ u₂ v₂ w₁ w₂ w₃

-3 -2 2 0 0 0 -5

1 1 -1 1 0 0 2

0 1 -1 0 1 0 1

3 2 -2 0 0 1 5

y₁ u₂ v₂ w₁ w₂ w₃

0 0 0 0 0 1 0

0 1/3 -1/3 1 0 -1/3 1/3

0 1 -1 0 1 0 1

1 2/3 -2/3 0 0 1/3 5/3

La soluzione di base ottenuta è: (5/3, 0, 0, 1/3, 1, 0)

3. A partire dalla tabella ottima del problema A costruiamo una tabella canonica per il problema D:

y₁ u₂ v₂ w₁ w₂

6 3 0 0 0 0

0 1/3 -1/3 1 0 1/3

0 1 -1 0 1 1

1 2/3 -2/3 0 0 5/3

Portiamo la tabella in forma canonica moltiplicando l’ultima riga per 6 e sottraendola alla riga 0:

y₁ u₂ v₂ w₁ w₂

0 -1 4 0 0 -10

0 1/3 -1/3 1 0 1/3

0 1 -1 0 1 1

1 2/3 -2/3 0 0 5/3

Poiché la colonna v₂ ha costo ridotto positivo e gli altri tre elementi negativi, il problema D è illimitato superiormente. Dunque il problema P

(A) E’ illimitato inferiormente.

(B) Non ammette soluzione.

(C) Ammette una soluzione ottima finita.