Algoritmo del Simplesso

uni
Questo è l’algoritmo pre trovare la soluzione ottima di un Problema di Programmazione Lineare (PL), facendo uso della Teoria della Dualità.
Dato un problema PL in primale standard: $(P)\{\begin{array}{l}max{c}^T\cdot x\\ Ax\le b\end{array}$
Ne trovo il duale complementare $(P)\{\begin{array}{l}min{b}^T\cdot y\\ A^{T}y=c\\ \forall k,y_k\ge 0\end{array}$
Parto da una soluzione di base ammissibile del primale, ovvero un vertice.
Data la sua base $B$, ne calcolo la soluzione nel duale, secondo le modalità descritte nella Teoria della Dualità, se la soluzione duale è ammissibile (tutte $y_B\ge 0$) questo vertice è soluzione, altrimenti devo fare un Passo del Simplesso.
Se parto da una base con soluzione non ammissibile nel primale, che è invece soluzione ammissibile nel duale, devo fare un Passo del Simplesso Duale.

Passo del Simplesso

1. Determino l’indice uscente $h$: il minore indice (di base) la cui $y_h\le 0$.
   si prende sempre il minore per la Regola Anticiclo di Blend.
   $y_B=((A_B{)}^T{)}^{-1}$ e $y_N=(0,0,...,0)$
2. Determino $W=-A_B^{-1}$ e $W^l$ è una colonna di $W$ determinata dalla $l$-esima riga di $A$, in particolare considero $W^h$, ovvero la colonna di $W$ determinata dalla $h$-esima (con $h$ indice uscente) riga di $A$.
3. Calcolo per ogni indice $i$ non di base il prodotto scalare $A_i{W}^h$ e scarto gli indici per cui tale rapporto è negativo
4. Rimpiazzo $h$ con l’indice $i$ non di base che produce il minimo del seguente prodotto:

$$r_i=\frac{b_i-A_i\overline{x}}{A_i{W}^h}$$

• se due indici hanno lo stesso $r$ scelgo l’indice minore.
• se tutti gli indici $i$ portano ad $A_i{W}^h\le 0$ allora la soluzione è illimitata.

Passo del Simplesso Duale

In questo caso partiamo da un Formato Duale Standard, prendiamo un vertice, scopriamo che non è ammissibile nel primale e quindi dobbiamo applicare il Simplesso Duale.

$$(D)=\{\begin{array}{l}min{b}^T\cdot y\\ y^{T}A=c^T\\ y\ge 0\end{array}$$

1. data una base $B$, trovo la soluzione di base ${\overline{y}}_B^T=c^T{A}_B^{-1}$ e scopriamo che è ammissibile (tutte componenti di $\overline{y}\ge 0$ )
2. Trovo quindi la complementare $\overline{x}=A_B^{-1}\cdot b_B$, se trovo che questa $\overline{x}$ non è ammissibile nel primale (non rispetta tutti i vincoli, quindi $A_N\cdot \overline{x}\ge b_N$ ) allora sappiamo che la nostra $\overline{y}$ non è Ottimo (fallisce il Test di Ottimalità del degli Scarti Complementari).
3. Allora $\exists j\in N:A_j\cdot \overline{x}>b_j$ (esiste almeno una riga violata), sia $k$ la prima riga violata (indice minore - Regole Anticiclo di Blend), l’indice entrante.
4. Calcoliamo $W=-A_B^{-1}$
5. Calcoliamo $A_k{W}^i$ con $i\in B$ e elimino gli indici per i quali viene positivo (se tutti gli indici portano a prodotto positivo il minimo è $=-\infty$ )
6. Costruisco i rapporti $r_i=\frac{-y_i}{A_k{W}^i}$ con $i\in B$ e prendo l’indice che porta al rapporto minore, e lo chiamo $h$, indice uscente e questo viene rimpiazzato da $k$ (se due $r$ sono uguali prendo l’indice minore).

Algoritmo verifica Poliedro Vuoto

Questo algoritmo serve per sapere se il poliedro è vuoto o meno:

1. Costruisco il suo Duale Ausiliario (DA)
   partendo da un problema in duale std

$$(D)=\{\begin{array}{l}min{y}^{T}b\\ A^{T}y=c\\ y\ge 0\end{array}$$

costruisco il suo Duale Associato + tante epsilon quante sono le righe del duale moltiplicandole per l'identità $( i )$ 

$$(D_{aux})=\{\begin{array}{l}min{\sum }_{i=0}^n{ϵ}_i\\ y^{T}A+{ϵ}^T=c^T\\ y\ge 0\\ ϵ\ge 0\end{array}$$

che equivale a prendere il poliedro nella sua forma $A^{T}y=c$ ed aggiungere ad ogni riga di $A^{T}y$ una $ϵ$, quindi le $ϵ$ sono tante quante lo sono le righe di $A^T$ (ovvero numero di colonne di $A$).

2. Cerco il Valore Ottimo del $(D_{aux})$ (VO) tramite il Passo del Simplesso Duale (mi aspetto che le due epsilon escano)
3. Controllo il segno di VO:
   • se $VO>0$ allora poliedro del duale (D) è vuoto
   • se $VO=0$ allora $(D)$ non è vuoto, e una base ammissibile per $(D)$ si costruisce a partire da una base ottima per $(D_{aux})$.