Il metodo del simplesso. la forma standard

La forma standard

Fino ad ora abbiamo scritto un generico problema di Programmazione Lineare nella forma

Un problema di Programmazione Lineare in questa forma viene detto problema in forma generale. Il Metodo del Simplesso assume che il problema di Programmazione Lineare sia nella forma

che viene chiamata forma standard. Come vedremo un problema scritto in forma standard presenta importanti proprietà che possono essere sfruttate nella risoluzione di un problema di PL. Ad un problema in forma standard si applica sempre il Teorema Fondamentale della Programmazione Lineare. Inoltre, la struttura dell’insieme ammissibile di un problema in forma standard permette di caratterizzare i vertici dell’insieme ammissibile stesso.

Preliminarmente dimostriamo che assumere che un problema di Programmazione Lineare sia in forma standard non fa perdere di generalità in quanto qualunque problema di PL può essere trasformato in un problema equivalente in forma standard. Infatti se si ha un problema di Programmazione Lineare nella forma (1) si può passare ad un problema equivalente con soli vincoli di uguaglianza introducendo un vettore u ∈ R^m, u ≥ 0, e riscrivendo il problema nella forma

Le variabili u vengono chiamate variabili di surplus e rappresentano la differenza non negativa tra il primo e il secondo membro dei vincoli di disuguaglianza.

Analogamente per un problema del tipo:

sarà sempre possibile ricondurlo alla forma standard:

Infatti sarà sufficiente introdurre un vettore w ∈ R^m, w ≥ 0, e riscrivere il problema nella forma:

Le variabili w vengono chiamate variabili di slack.

Esempio

Si consideri il problema

Questo problema può essere trasformato in un problema equivalente con vincoli di sola uguaglianza mediante l’introduzione di una variabile di surplus x₄ e una variabile di slack x₅ e scrivendo il problema

Matrici di Base

Ipotesi:
A matrice m × n
P ≠ ∅
rango(A) = m

Definizione
Una sottomatrice B di A tale che:
B ha dimensione m × m;
det(B) ≠ 0, cioè B è invertibile è detta matrice di base di A.

Esempio

B = {x₂, x₄, x₅} insieme delle variabili in base
N = {x₁, x₃} insieme delle variabili fuori base
I_B = {2, 4, 5} insieme degli indici in base
I_N = {1, 3} insieme degli indici fuori base
E possibile scrivere (in caso, riordinando le variabili):

Un problema di PL in forma standard può essere scritto nella forma equivalente( 2 ) in tanti modi diversi quante sono le matrici di base di A.

I sistemi (2) mettono in evidenza che il sistema Ax = b può essere risolto esprimendo il vettore delle variabili base x_B in funzione del vettore delle variabili fuori base. La particolare soluzione del sistema Ax = b che si ottiene annullando il vettore delle variabili fuori base viene caratterizzata dalla seguente definizione:

Definizione 

Data una matrice di base B di A. Un vettore x  è detto Soluzione di Base del sistema Ax = b se i suoi sottovettori x_B e x_N sono tali che:

Utilizzando delle particolari matrici di base del sistema Ax = b è possibile caratterizzare delle particolari soluzioni ammissibili del problema in forma standard ( 2), a questo scopo sono necessarie altre due definizioni.

Definizione

Dato un problema in forma standard, una matrice di base B di A è detta matrice di base ammissibile se risulta

B⁻¹b ≥ 0_m.

Definizione

Dato un problema in forma standard  e data una matrice di base ammissibile B di A. Un vettore x è detto Soluzione di Base Ammissibile (SBA) del problema se i suoi sottovettori x_B e x_N sono tali che:

Esempio

Sia dato il seguente sistema:

Consideriamo la sottomatrice di A

ottenuta considerando nell’ordine la sesta, prima e quarta colonna della matrice A del sistema. In questo caso

e, poichè si verifica facilmente che det B = −3, abbiamo che B è una matrice di base di A, le colonne a₆, a₁ e a₄ sono colonne di base e gli indici 6, 1 e 4 sono indici di base.
Consideriamo ora, invece, la sottomatrice di A

ottenuta considerando nell’ordine la seconda, quinta e quarta colonna della matrice A del sistema. In questo caso

e, poichè si verifica facilmente che det B = 0, abbiamo che B non una matrice di base di A.

(688)

PubblicitàPubblicità