Il metodo del simplesso. Base di un problema di PL

I problemi di PL in forma standard

Abbiamo precedentemente visto  che i problemi di PL in forma standard hanno la seguente formulazione:

Osservazione
Ogni problema di PL in forma canonica può essere trasformato in uno equivalente in forma standard.

esempio

Si trasformi il seguente problema di PL in forma generica in un problema di PL in forma standard:

Ipotesi aggiuntiva

Si richiede che la matrice dei vincoli A ∈ R^{m × n} abbia rango pari a m, il numero delle sue righe, il che equivale a
richiedere che:

• non ci sono righe di A ottenibili come combinazioni lineari di altre righe di A;
• esistono m colonne della matrice A che formano una matrice quadrata invertibile.

NB:

Si può dimostrare che anche questa non è una condizione restrittiva e che ci si può sempre ricondurre ad essa.

Esempi:

Base di un problema di PL

Si definisce base di un problema di PL in forma standard un
sottinsieme:
B ={x_i1 , . . . , x_im}

di m delle n variabili del problema di PL con la proprietà che la matrice A_B ∈ R^m×m ottenuta considerando le sole
colonne di A relative alle variabili x_ik , k = 1, . . . , m, sia invertibile.

Le variabili dell’insieme B verranno dette variabili in base, quelle al di fuori di B verranno raggruppate nell’insieme:

B ={x_im+1 , . . . , x_in}

e verranno dette variabili fuori base.

Esempio

Dato:

B1 = {x1, x2} → non è una base. Infatti:

non è invertibile.

Invece, B2 = {x1, x3} è una base in quanto:

è invertibile.

Matrice invertibile

Secondo il teorema di esistenza della matrice inversa, una matrice è invertibile se e soltanto se il suo determinante è diverso da zero.

Riformulazione rispetto alla base B

Data una base B, indichiamo con:

x_B ∈ R^m il vettore delle variabili in base

x_N ∈ R^n−m il vettore delle variabili fuori base

c_B ∈ R^m il vettore dei costi relativi alle variabili in base

c_N ∈ R^n−m il vettore dei costi relativi alle variabili fuori base

A_N ∈ R^m×(n−m) la matrice ottenuta daA considerando le sole colonne relative alle variabili fuori base.

Nell’esempio

Con la base
B = {x₁, x₃} abbiamo:

Riscrittura della riformulazione

Possiamo ora riscrivere il problema di PL in forma standard nella seguente forma equivalente:

Tornando all’esempio:

Moltiplichiamo ora i vincoli di uguaglianza per A⁻¹ _B :

Questo equivale a risolvere il sistema dato dai vincoli di uguaglianza considerando la variabili in base come incognite del sistema e quelle fuori base come parametri.

Nell’esempio:

Infine, sostituendo x_B nell’obiettivo:

Questa riformulazione viene detta riformulazione del problema di PL rispetto alla base B.
NB:

Tale riformulazione è del tutto equivalente al problema originario di PL.

Nell’ esempio:

Riformulazione rispetto alla base B = {x₁, x₃}:

[elementor-template id=”14302″]
[no_toc]

(265)

PubblicitàPubblicità