Home

Federica EU

1/23

Paola Festa » 4.Geometria della PL

Poliedri, 1

Definizione: L’insieme $P=\{x\in {\mathbb R}^n\ \vert\ Ax\geq b\}$ , dove $A\in {\mathbb R}^{m\times n}$ e $b\in {\mathbb R}^m$ , è detto poliedro.

Dunque, la regione ammissibile S di ogni problema di PL è un poliedro, dato che può essere descritta da vincoli di disuguaglianza del tipo $Ax\geq b$ .

In particolare, un insieme del tipo $\{x\in {\mathbb R}^n\ \vert\ Ax=b,\ x\geq 0\}$ è un poliedro rappresentato in forma standard.

Un poliedro può essere limitato o illimitato:

Definizione: Un insieme $S\subset {\mathbb R}^n$ è limitato se esiste una costante k tale che

$\vert x_i\vert \leq k,\ \ \forall i=1,2,\ldots,n,\ \ \forall\ x\in S.$

Poliedri, 2

Definiremo ora alcuni poliedri speciali, data la loro semplicità.

Definizione: Sia $a\in {\mathbb R}^n$ e sia $b\in {\mathbb R}$ uno scalare.

L’insieme $\{x\in {\mathbb R}^n\ \vert\ a'x=b\}$ è detto iperpiano.
L’insieme $\{x\in {\mathbb R}^n\ \vert\ a'x\geq b\}$ è detto semispazio.

Un poliedro è dato dall’intersezione di un numero finito di semispazi e di iperpiani.

a) Un iperpiano e due semispazi. b) Un poliedro risultante dall'intersezione di cinque semispazi. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Insiemi convessi, 1

Definizione: Un insieme $S\subset {\mathbb R}^n$ è convesso se $\forall\ x,y\in S$ e $\forall\ \lambda\in [0,1]$ risulta che $\lambda x+ (1-\lambda)y=v\in S$ .

Si noti che v risulta dalla media pesata di x e y e dunque appartiene al segmento che unisce x ad y.

Infatti, si può in generale affermare che un insieme S è convesso se il segmento che unisce due punti qualunque di S è tutto contenuto in S stesso.

(a) S è un insieme convesso. (b) Q non è un insieme convesso. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Insiemi convessi, 2

La definizione di convessità si può estendere al caso di media pesata di un numero finito di vettori.

Definizione: Siano $x^1,x^2,\ldots,x^k\in {\mathbb R}^n$ e siano $\lambda_1,\lambda_2,\ldots,\lambda_k$ scalari tali che

$\lambda_i\geq 0,\ i=1,2,\ldots,k\ \ e\ \ \displaystyle{\sum_{i=1}^k \lambda_i=1}.$

Il vettore $\displaystyle{\sum_{i=1}^k \lambda_i x^i}$ è detto combinazione convessa dei vettori $x^1,x^2,\ldots,x^k$ .

Si dice inviluppo convesso dei vettori $x^1,x^2,\ldots,x^k$ l’insieme di tutti i vettori combinazione convessa di $x^1,x^2,\ldots,x^k$ e si indica con

$conv(x^1,x^2,\ldots,x^k).$

Insiemi convessi, 3

Valgono le seguenti proprietà, di cui trascuriamo in questo contesto la verifica.

Teorema

a. L’intersezione di insiemi convessi è un insieme convesso.

b. ogni poliedro è un insieme convesso.

c. La combinazione convessa di un numero finito di elementi di un insieme convesso S appartiene essa stessa all’insieme convesso S.

d. L’inviluppo convesso di un numero finito di vettori è un insieme convesso.

Inviluppo convesso di sette punti. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Punti estremi, vertici e soluzioni di base ammissibili, 1

Come già osservato, una soluzione ottima finita di un problema di PL tende ad essere in corrispondenza di uno spigolo della regione ammissibile.

Nelle seguenti slides daremo tre definizioni equivalenti di spigolo come punto estremo, vertice e soluzione di base ammissibile.

Definizione: Sia P un poliedro. Un vettore x in P è detto punto estremo di P se non esistono due vettori y e z in P (y e z diversi da x) ed uno scalare $\lambda\in [0,1]$ , tali che $x=\lambda y + (1-\lambda) z$ .

Definizione: Sia P un poliedro. Un vettore x in P è detto vertice di P se esiste un vettore c tale che c’x<c’y, per ogni y in P, y diverso da x.

Punti estremi, vertici e soluzioni di base ammissibili, 2

La terza definizione equivalente di spigolo è algebrica e perciò utile ai fini algoritmici.

Per comprenderla, è necessaria un’ulteriori definizione, riportata di seguito.

Si consideri il seguente generico problema di PL:

$\[ \begin{array}{llll} \\ \mbox{{\rm min}} \ c'x & \mbox{{\rm (P)}}\\ \mbox{{\rm s.a}} \\ &a'_ix & \geq b_i & i\in M_1\\ &a'_ix & \leq b_i & i\in M_2\\ &a'_ix & = b_i & i\in M_3\\ &x_j & \geq 0 &j\in N_1\\ &x_j & \leq 0 &j\in N_2\\ &x_j & \mbox{{\rm non vincolata}} & j\in N_3 \end{array} \]</p> <p>$

Definizione: Se un vettore $x^*$ soddisfa $a'_ix = b_i$ per qualche $i\in M_1,\ M_2,\ M_3$ , allora il corrispondente vincolo si dice attivo in $x^*$ .

Punti estremi, vertici e soluzioni di base ammissibili, 3

Ora abbiamo tutti gli strumenti per definire uno spigolo di un poliedro come soluzione ammissibile che attiva n vincoli linearmente indipendenti:

Definizione: Sia P un poliedro definito da vincoli di uguaglianza e/o disuguaglianza come in (P) e sia $x^*\in {\mathbb R}^n$ .

Il vettore $x^*$ è una soluzione di base se

tutti i vincoli di uguaglianza di (P) sono attivi in $x^*$ ;

$x^*$ attiva n vincoli linearmente indipendenti.

Se $x^*$ è una soluzione di base che soddisfa tutti i vincoli, allora è detta soluzione di base ammissibile.

I punti A, B, C, D, E ed F sono tutti soluzioni di base, dato che ciascuno di loro attiva due vincoli linearmente indipendenti. Tuttavia, solo i punti C, D, E ed F sono soluzioni di base ammissibili. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Punti estremi, vertici e soluzioni di base ammissibili, 4

Esempio

$P=\{(x_1,x_2,x_3)\ \vert\ x_1+x_2+x_3=1,\ x_1,x_2,x_3\geq 0\}\subset {\mathbb R}^3$ .

I punti A, B, C e D attivano tre vincoli, mentre E attiva solo i seguenti due vincoli:

$x_1+x_2+x_3=1$ ;
$x_2=0$ .

I punti A, B, C e D attivano tre vincoli, mentre E attiva solo due vincoli. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Punti estremi, vertici e soluzioni di base ammissibili, 5

Come già anticipato, le tre differenti definizioni di spigolo di un poliedro sono perfettamente equivalenti fra loro:

Teorema

Sia P un poliedro non vuoto e sia x in P. Le seguenti tre affermazioni sono equivalenti:

x è un vertice di P;

x è un punto estremo di P;

x è una soluzione di base ammissibile.

Corollario: Dato un numero finito di vincoli lineari di disequazioni e/o equazioni, può esistere solo un numero finito di soluzioni di base e soluzioni di base ammissibili.

Punti estremi, vertici e soluzioni di base ammissibili, 6

Definizione: Due distinte soluzioni di base di un poliedro P si dicono adiacenti se attivano gli stessi n-1 vincoli.

Se due soluzioni di base adiacenti sono anche ammissibili, come D e C in Figura, allora il segmento che li congiunge è detto lato del poliedro.

In Figura, ad esempio, B ed E sono entrambi adiacenti

a D, mentre A ed F sono adiacenti ad E.

B ed E sono entrambi adiacenti a D, mentre A ed F sono adiacenti ad E. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Soluzioni di base ammissibili per un poliedro in forma standard, 1

Teorema

Si considerino i vincoli $Ax=b$ e $x\geq 0$ e si assuma che $A\in {\mathbb R}^{m\times n}$ sia una matrice a righe linearmente indipendenti.

Un vettore $x^*\in {\mathbb R}^n$ è soluzione di base se e solo se

I. $Ax^*=b$ ;

II. è possibile individuare $B(1),B(2),\ldots,B(m)$ indici tali che

le colonne $A_{B(1)},A_{B(2)},\ldots,A_{B(m)}$ sono linearmente indipendenti;

se $j\not= B(1),B(2),\ldots,B(m)$ , allora $x^*_j=0$ .

Soluzioni di base ammissibili per un poliedro in forma standard, 2

Grazie alla validità del teorema appena enunciato, tutte le soluzioni di base di un poliedro descritto in forma standard possono essere ottenute applicando la semplice procedura riportata di seguito

$\centerline{\fbox{\begin{minipage}[h]{11cm} \normalsize{{\bf Passo 1.}\\\hspace*{0.5truecm} Scegliere $m$ colonne di $A$ linearmente indipendenti.\\\hspace*{0.5truecm} Siano $A_{B(1)},A_{B(2)},\ldots,A_{B(m)}$ dette colonne.\\{\bf Passo 2.}\\\hspace*{0.5truecm} Porre $x_j=0$, per ogni $j\not= B(1),B(2),\ldots,B(m)$.\\{\bf Passo 3.}\\\hspace*{0.5truecm} Risolvere il sistema ad $m$ equazioni $Ax=b$ nelle $m$ incognite\\\hspace*{0.5truecm} $x_{B(1)},x_{B(2)},\ldots,x_{B(m)}$. }\end{minipage}}}\centerline{}$

Sia $\hat x$ una soluzione di base ottenuta applicando la procedura appena descritta.

Se $\hat x\geq 0$ , allora $\hat x$ è detta soluzione di base ammissibile.

Viceversa, dal momento che ogni soluzione ammissibile di base $\hat x$ è una soluzione di base, essa può essere ottenuta attraverso la semplice procedura sopra descritta.

Soluzioni di base: definizioni

Sia $\hat x$ una soluzione di base,

le variabili $\hat x_{B(1)},\hat x_{B(2)},\ldots,\hat x_{B(m)}$ sono dette variabili di base, mentre le restanti n-m variabili di decisione $x_j,\ j\not= B(1),B(2),\ldots,B(m)$ sono dette variabili non di base;

le colonne $A_{B(1)},A_{B(2)},\ldots,A_{B(m)}$ sono dette colonne di base e formano una base di ${\mathbb R}^m$ ;

è sempre possibile riordinare le colonne della matrice A, affinchè le colonne $A_{B(1)},A_{B(2)},\ldots,A_{B(m)}$ siano le prime m colonne, così ottenendo una sottomatrice quadrata $B\in {\mathbb R}^{m\times m}$ , detta matrice di base.

Le m variabili di base $x_B$ sono determinate risolvendo il sistema di m equazioni in m incognite $Bx_B=b$ , la cui unica soluzione è data da

$x_B=B^{-1}b.$

Soluzioni di base: esempio, 1

Sia P il poliedro in forma standard descritto dai seguenti vincoli di uguaglianza lineari:

$\begin{array}{llllllll}x_1+&x_2+&2x_3+&x_4& & & & = 8\\&x_2+&6x_3+& &x_5 & & & = 12\\x_1+& & & & &x_6 & & = 4\\&x_2+& && & &x_7 & = 6\end{array}$

La matrice dei coefficienti tecnologici A ed il vettore dei termini noti b sono i seguenti:

$\begin{displaymath}A = \left[ \begin{array}{ccccccc}1&1&2&1&0&0&0\\ 0&1&6&0&1&0&0\\1&0&0&0&0&1&0\\ 0&1&0&0&0&0&1\end{array} \right], \qquad b = \left[ \begin{array}{c}8\\ 12\\ 4\\ 6\end{array}\right].\end{displaymath}$

Soluzioni di base: esempio, 2

Se scegliamo le colonne

$B=[A_4\ A_5\ A_6\ A_7] ,$

si ottiene la soluzione di base:

$x_B=[x_4\ x_5\ x_6\ x_7]=[8\ 12\ 4\ 6]$

$x_N=[x_1\ x_2\ x_3]=[0\ 0\ 0]$ .

Dal momento che tale soluzione è non negativa, essa è una soluzione di base ammissibile.

Un’altra possibile scelta è $B=[A_3\ A_5\ A_6\ A_7]$ .

La soluzione di base corrispondente è $x_B=[x_3\ x_5\ x_6\ x_7]=[4\ -12\ 4\ 6]$ e $x_N=[x_1\ x_2\ x_4]=[0\ 0\ 0]$ .

In tal caso la soluzione di base ottenuta non è ammissibile, perchè $x_5=-12<0$ .

Soluzioni di base degeneri, 1

Definizione: Una soluzione di base $x^*\in {\mathbb R}^n$ è detta degenere se attiva più di n vincoli.

Osservazioni:

in ${\mathbb R}^2$ l’intersezione di 3 o più rette dà luogo ad una soluzione di base degenere;
in ${\mathbb R}^3$ una soluzione degenere è in corrispondenza dell’intersezione di 4 o più piani.

Esempi di soluzioni di base degeneri sono illustrati in Figura.

I punti A e C sono soluzioni di base ammissibili degeneri. I punti B ed E sono soluzioni di base ammissibili non degeneri. Il punto D è una soluzione di base non ammissibile degenere

Soluzioni di base degeneri, 2

Osservazione:

Qualunque soluzione di base per poliedri in forma standard deve necessariamente attivare tutti gli m vincoli di uguaglianza. Dunque, l’unico modo per attivare più di n vincoli è che più di n-m variabili di decisione valgano 0. Infatti, vale la seguente definizione.

Definizione: Sia $P=\{x\in {\mathbb R}^n\ \vert\ Ax=b,\ x\geq 0\}$ un poliedro in forma standard e sia $x^*$ una soluzione di base.

Sia m il numero di righe di A, allora $x^*$ è detta soluzione di base degenere se più di n-m componenti di $x^*$ sono nulle.

I punti A e C sono soluzioni di base ammissibili degeneri. I punti B ed E sono soluzioni di base ammissibili non degeneri. Il punto D è una soluzione di base non ammissibile degenere. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Esistenza di punti estremi, 1

Come già osservato, una soluzione ottima finita di un problema di PL tende ad essere in corrispondenza di un punto estremo della regione ammissibile.

E’ chiaro che non tutti i poliedri hanno sempre almeno un punto estremo.

Un semispazio in ${\mathbb R}^n,\ n>1$ , ad esempio, pur essendo un poliedro non ha punti estremi.

L’esistenza di almeno un punto estremo per un poliedro P dipende dalla presenza o meno in P di una retta:

Definizione: Un poliedro $P\subset {\mathbb R}^n$ contiene una retta se esiste un vettore $x\in P$ ed un vettore non nullo $d\in {\mathbb R}^n$ tale che

$x+\lambda d\in P,\ \ \forall\ \lambda\ \mbox{scalare}.$

Esistenza di punti estremi, 2

Teorema

Sia $P=\{x\in {\mathbb R}^n\ \vert\ a'_ix\geq b_i,\ i=1,2,\ldots,m\}$ un poliedro non vuoto.

Le seguenti affermazioni sono equivalenti fra loro:

a. $P$ ha almeno un punto estremo;

b. $P$ non contiene una retta.

Corollario

Ogni poliedro limitato non vuoto ed ogni poliedro non vuoto descritto in forma standard ha almeno un punto estremo e, dunque, almeno una soluzione di base ammissibile.

Ottimalità di punti estremi, 1

Teorema

Si consideri il problema di PL consistente nel minimizzare c’x su un poliedro P che abbia almeno un punto estremo.

Allora, o il valore della soluzione ottima è $-\infty$ oppure esiste un punto estremo di P che è soluzione ottima finita al problema.

Nel caso di problemi di PL generici, il Teorema non si applica direttamente se la regione ammissibile non ha punti estremi.

Tuttavia, sappiamo che un qualunque problema di PL può essere trasformato in un problema di PL equivalente formulato in forma standard, cui il Teorema invece si applica.

Ottimalità di punti estremi, 2

Corollario

Si consideri il problema di PL consistente nel minimizzare c’x su un poliedro P non vuoto.

Allora, o il valore della soluzione ottima è $-\infty$ oppure esiste una soluzione ottima finita al problema.

Il Metodo del Simplesso si basa sui risultati teorici appena enunciati e cerca una soluzione ottima al problema muovendosi da una soluzione ammissibile di base ad una adiacente sempre nella direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo.

Nel momento in cui viene raggiunta una soluzione ammissibile di base a partire dalla quale non è possibile intraprendere più alcuna direzione migliorativa del valore corrente della funzione obiettivo, la soluzione ammissibile di base corrente è ottima e l’algoritmo termina.