Il metodo del Simplesso

Metodo del simplesso §

Riscrive il problema di PL in una forma equivalente e comoda, in cui i vertici, che sono fondamentali come conseguenza del Teorema fondamentale della PL, assumono una forma semplice.

Def §

forma standard

$$\min c^{T}x$$ $$Ax=b$$ $$x\ge 0,b\ge 0$$

è evidente che aggiungendo opportune variabili e moltiplicando per $-1$, ogni problema di PL può essere riscritto in questa forma. Vediamo ora la proprietà fondamentale, la forma che assumono i veritici.

Teorema caratterizzazione dei vertici in forma standard §

Sia $\overline{x}$ un punto appartenente al poliedro $P$ definito in forma standard, e $rango(A)=m$ (ovviamente $m<n$). Allora $\overline{x}$ è un vertice di $P$ se e solo se le colonne di $A$ relative alle componenti positive (non nulle) di $\overline{x}$ sono linearmente indipendenti.

le uniche variabili che contano sono quelle positive

Dim §

per dimostrare questo fatto, trasformiamo la forma canonica del poliedro nella forma solita, ed imponiamo la definizione di vertice, ovvero il rango dei vincoli attivi deve essere uguale ad $n$.

$$Ax=b\to Ax\le b,-Ax\le -b$$

supponiamo che le prime $r$ variabili siano strettamente positive, le restanti $n-r$ nulle. Questo significa che $r$ vincoli di non negatività sono attivi. Quindi la definizione di vertice solita è:

$$rank\left(\begin{array}{c}A\\ -A\\ e_{r+1}^T\\ \dots \\ e_n^T\end{array}\right)=n$$

ma le righe di $A$ ed $-A$ sono ovviamente linearmenti dipendenti, rimuovendole non abbasso il rango complessivo. Riscrivo i vincoli di non negatività in forma più comoda:

$$rango\left(\begin{array}{c}A\\ 0_{(n-r)\times r}{I}_{(n-r)\times (n-r)}\end{array}\right)$$

dalla definzione di indipendenza lineare, essendo $n$ colonne:

$$\left(\begin{array}{c}{a}_i\dots a_r{a}_{r+1}\dots a_n\\ 0_{(n-r)\times r}{I}_{(n-r)\times n-r}\end{array}\right)\left(\begin{array}{c}y\\ z\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$$

implica che $(y,z)=0$. Ma la particolare forma della matrice ci sta dicendo che $z=0$, quindi rimaniamo con la condizione:

$$(a_i,\dots a_r)y=0\text{implica }y=0$$

ovvero l’indipendenza lineare delle colonne della matrice $A$ che corrispondono alle componenti positive di $\overline{x}$. $\square$

Corollario §

Segue direttamente l’ultile colorrario che $x\in P$ è un vertice allora ha almeno $n-m$ componenti nulle (potrebbe averne di più!).

Dim §

Se ne avesse meno di $n-m$, non avrebbe abbastanza colonne linermente indipendenti (meno di $n$), quindi per il teorema precedente non sarebbe un vertice.

Def SBA §

Un po’ di definizioni.

Chiamo una matrice di base una sottomatrice non singolare $B$ della matrice $A$, avendo supposto $rank(A)=m$ $B$ è una matrice $m\times m$.

Chiamo soluzione di base ammissibile (SBA) il punto $\overline{x}\in {\mathbb{R}}^n$ tale che:

$$\overline{x}=\left(\begin{array}{c}{x}_B\\ x_N\end{array}\right)x_B=B^{-1}b\ge 0,x_N=0_{n-m}$$

Che ha le proprietà:

1. è un punto ammissibile, ovvero $\overline{x}\in P$ (si verifica direttamente).
2. è un vertice. Infatti le componenti positive hanno colonne l.i (sono un sottoinsieme delle colonne di $B$ che è non singolare), (notiamo inoltre che rispetta il corollario precedente). Inoltre ad ogni vertice corrisponde una SBA. Ogni vertice ha una soluzione di base associata. La costruisco partendo dalle $r\le m$ componenti del vertice positive, posso aggiungere altre per creare la matrice $B$. Poi basta verificare che è in $P$.

Abbiamo ottenuto la seguente caratterizzazione fondamentale:

$$Vertici⟺SBA$$

Criterio di ottimalità §

Data la divisione $x=\left(\begin{array}{c}{x}_B\\ x_N\end{array}\right)$ , la funzione obbiettivo può essere riscritta come:

$$c^{T}x=c_B^T{x}_B+c_N^T{x}_N$$

ed i vincoli:

$$B{x}_B+N{x}_N=b{x}_B,x_N\ge 0$$

possiamo scrivere $x_b$ in funzione di $x_N$ e $b$, infatti essendo $B$ non singolare:

$$x_B=B^{-1}b-B^{-1}N{x}_N$$

sostituendo nella funzione obbiettivo:

$$c^{T}x=c_B^T(B^{-1}b-B^{-1}N{x}_N)+c_N^T{x}_N=c_B^T{B}^{-1}b+(c_N^T-c_B^T{B}^{-1}N)x_N=c_B^T{B}^{-1}b+{\gamma }^T{x}_N$$

dove abbiamo definito il vettore dei coefficienti di costo ridotti ${\gamma }^T$.

Teorema criterio di ottimalità §

Sia $\overline{x}$ una SBA. Se il vettore dei coefficienti di costo ridotti è non negativo, allora è una soluzione ottima.

Dim §

Lo dimostriamo facendo vedere che:

$$c^T\overline{x}\le c^{T}x$$

dove $x$ è una qualunque punto ammissibile.

Calcolare il valore della funzione obbiettivo nella SBA è facile, $x_N=0_{n-m}$:

$$c^T\overline{x}=c_B^T{x}_B=c_B{B}^{-1}b$$

ma la funzione obbiettivo in un qualunque punto ammissibile può essere scritta come:

$$c^{T}x=c_B^T{B}^{-1}b+{\gamma }^T{x}_N$$

per ipotesi $\gamma \ge 0$, e siccome anche $x_N\ge 0$ si ha che:

$$c^{T}x=c_B^T{B}^{-1}b+{\gamma }^T{x}_N\ge c_B^T{B}^{-1}b=c^T\overline{x}\square$$

Criterio di Illimitatezza §

Sia $x$ una SBA e ${\gamma }_i<0$, e la relativa colonna $(B^{-1}N{)}_i\le 0$ ovvero tutta non positiva. Allora il problema è illimitato inferiormente.

Dim §

costruttiva, troviamo delle SBA in cui la funzione obbiettivo è arbitrariamente piccola. Partiamo dalla SBA per cui si verifica l’ipotesi, e da lì scappiamo verso una direzione.

$$x(\rho )=\left(\begin{array}{c}{x}_B(\rho )\\ x_N(\rho )\end{array}\right)$$

con $x_N(\rho )=\rho e_i$ Facciamo vedere che:

1. $x(\rho )$ è ammissibile per ogni $\rho \ge 0$:
   • $x_N(\rho )\ge 0$ banalmente;
   • $x_B(\rho )=B^{-1}b-B^{-1}N{x}_N(\rho )=B^{-1}b-\rho {\gamma }_i\ge 0$, ma per ipotesi essendo una SBA $B^{-1}b\ge 0$, inoltre per i segni è sempre vera.
2. la funzione obbiettivo è arbitrariamente piccola: $$c^{T}x(\rho )=c^T{x}_B+\rho {\gamma }_i^T$$

che per $\rho \to \infty$ diventa arbitrariamente piccola. $\square$ ## Costruzione di una nuova SBA Supponiamo di avere una SBA e che i test di ottimalità ed illimitatezza siano entrambi falliti. Come scegliamo un'altra SBA (un altro vertice) in maniera _intelligente_? Come prima caso, la nuova SBA dovrà necessariamente avere una delle variabili fuori base $x_N$ positiva, infatti se ha le stesse variabili poste a zero, anche la parte in base dovrà essere uguale a prima, non abbiamo quindi una nuova SBA. Nel metodo del simplesso si costruisce una nuova SBA portando una delle variabili fuori base ad un numero positivo: $x_N' = e_h \rho$ con $\rho > 0$ (in questo caso la variabile $h$). Affinchè sia ammissibile $x_B'$ dovrà assumere la forma:

x_B’ = B^{-1}b-B^{-1}Nx_N’ = B^{-1}b-\rho (B^{-1}N)_h

e affinché sia ammissibile $x_B' \geq 0$:

B^{-1}b \geq \rho(B^{-1}N)_h

questo è un sistema di disequazioni. Siccome $B^{-1}b$ è ammissibile, è maggiore di zero, quindi se $(B^{-1}N)_{hi} \leq 0$ la disugualianza è valida per ogni $\rho$. Gli unici vincoli su $\rho$ sono quindi nel caso sia positivo, in questo caso per soddisfare l'intero sistema, basta scegliere $\rho$ come il minimo tra i rapporti:

\rho = \min_{\substack{i=1,\dots,m;\ (B^{-1}N)_{hi}>0}} \left{ \frac{(B^{-1}b)i}{(B^{-1}N){hi}} \right} = \frac{(B^{-1}b)k}{(B^{-1}N){hk}}

chiamiamo $k$ l'indice della variabile in base che il rapporto minimo. Abbiamo quindi ottenuto una nuova SBA, sapendo $\rho$ possiamo vedere che forma ha:

x_N’ = \frac{(B^{-1}b)k}{(B^{-1}N){hk}} e_h \qquad x_B’= B^{-1}b - \frac{(B^{-1}b)k}{(B^{-1}N){hk}}(B^{-1}N)_h

che succede alla compoente $k$ di $x_B'$? Il denomiatore si semplifica e quindi: $(x_B)_k = 0$ Ricordando la caratterizzazione $SBA \iff Vertice$, la nuova SBA deve avere le colonne corrispondenti alle variabili positive linearmente indipendenti. Questo insieme è appena cambiato, come abbiamo appena fatto. Dobbiamo far vedere che la colonna $A_{m+h}$ è linearmente indipendente cone la colonne $A_{1,\dots,m}\setminus A_k$. Basta far vedere che $A_{m+h}$ è una combinazione lineare delle colonne di $B = A_{1,\dots,m}$ e che il coefficiente relativo alla colonna uscente $A_k$ sia diverso da zero. Ma è questo propriò il caso, infatti:

A_{m+h} = N_h = B(B^{-1}N)_h

mettendo in chiaro ($B = A_{1,\dots,m}$):

A_{m+h}= \sum_{i=1}^m (B^{-1}N)_{hi}A_i

con $(B^{-1}N)_{hk} > 0$. Quindi è davvero una nuova SBA! $\square$ ### Come scelgo h? Quale variabile fuori base faccio entrare? Siccome voglio minimizzare la funzione, conviene limitarci a SBA in cui la funzione obbiettivo non aumenta. Ma è facile vedere che basta far entrare variabili a cui corrispondono coefficienti di costo ridotto non positivo! Basta ricordare il testi di ottimalità, infatti:

c^Tx = c_B^TB^{-1}b + \gamma^Tx_N = c_B^TB^{-1}b - \gamma^T_h\rho \leq c_B^TB^{-1}b = c^T\overline x

### Altro - basi degeneri - sistema artificiale