Il metodo del simplesso. Ammissibilità delle soluzioni. Esempi

Abbiamo visto nell‘articolo precedente 
che:
L’insieme dei vertici di S_a coincide con l’insieme delle soluzioni di base ammissibili del problema di PL.
In pratica, vertici e di soluzioni di base ammissibili sono la stessa cosa vista da due punti di vista diversi: quello geometrico (i vertici) e quello algebrico (le soluzioni di base ammissibili).

Un conseguenza immediata del precedente teorema è il seguente corollario:

Sia x un punto appartenente al poliedro P . Se x è un vertice di P allora almeno n − m componenti di x sono nulle.

Esempio

Consideriamo il sistema:

e il punto x = (2, 1, 1, 1, 0, 0)^T . Si verifica facilmente per sostituzione che il punto x è una soluzione ammissibile del sistema considerato, ma non è un suo vertice. Infatti le colonne di A relative alle componenti di x positive

non sono linearmente indipendenti.

Esempio

Consideriamo il poliedro P definito dal seguente sistema:

e i due punti (1, 1, 0, 0)^T e (0, 0, 0, 1)^T . Si verifica immediatamente che i due punti sono ammissibili o, in altri termini, appartengono al poliedro P. Inoltre, si può constatare che i due punti sono vertici di P. Nel primo caso infatti:

e quindi l’insieme costituito dalla prima e seconda colonna, corrispondenti alle componenti del punto maggiori di 0, è linearmente indipendente. Nel secondo caso il risultato è ancora più ovvio perchè l’insieme costituito dalla sola quarta colonna (diversa da zero) è banalmente linearmente indipendente.
Notiamo che per tutti e due i punti il numero di componenti maggiore di zero è minore o uguale a m = 2.

Esempio

Sia dato il seguente sistema:

Consideriamo la sottomatrice di A:

 

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

I_B = {j₁ = 2, j₂ = 5, j₃ = 4}

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

Esempio

Considerando ancora il sistema precedente,la sottomatrice di A

ottenuta considerando nell’ordine la sesta, prima e quarta colonna della matrice A del sistema. In questo caso
I_B = {j₁ = 6, j₂ = 1, j₃ = 4},

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.

 

Esempio

Consideriamo il sistema dell’esempio precedente e la prima delle basi ivi presa in considerazione.

con
I_B = {j₁ = 6, j₂ = 1, j₃ = 4},

Sappiamo già che B è una matrice di base, verifichiamo se è una matrice di base ammissibile. Risulta:

Quindi B è una base ammissibile. La soluzione di base ammissibile associata è:

Ricordiamo che:

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:

 x_B = B⁻¹b,
 x_N = 0_n−m

Consideriamo ora una matrice di base diversa, pi`u precisamente:

corrispondente a

I_B = {j₁ = 1, j₂ = 2, j₃ = 6}.

E facile verificare che B è una matrice di base (il suo determinante è diverso da 0), e che la soluzione di base ad essa associata è

che, ovviamente, non è ammissibile perchè la prima e seconda componente sono negative.

(81)

PubblicitàPubblicità