Simplesso Duale Flashcards
Cosa è necessario per avviare l’algoritmo del simplesso duale?
Serve un y segnato, sol.ne duale di base ammissibile.
Come fare a capire se y segnato è una soluzione ottima di (D)?
E’ una soluzione ottima se esiste una base B associata a y segnato t.c. la sol.ne primale di base x segnato è ammissibile per P.
Cosa è il simplesso duale?
E’ una implementazione intelligente del simplesso primale applicato a (D) riscritto in formato primale.
Nel simplesso primale si parte con una base primale ammissibile
Nel simplesso duale si parte con B base duale ammissibile
Nel simplesso primale l’ammissibilità duale significa che l’algoritmo termina perchè abbiamo trovato la soluzione. La non ammissibilità ci permette di trovare l’indice uscente.
Nel simplesso duale, l’ammissibilità primale significa che abbiamo trovato la soluzione ottima. La non ammissibilità ci indica l’indice entrante.
Nel simplesso primale si cerca ad ogni iterazione una direzione di crescita.
Nel simplesso duale si cerca una soluzione di decrescita.
Nel simplesso primale, se la direzione di crescita ammette passo infinito, significa che il problema è illimitato. Se ammette un passo finito, ci permette di trovare l’indice entrante.
Nel simplesso duale, se la direzione di decrescita ammette un passo infinito, l’algoritmo si ferma. Se ammette un passo finito ci permette di trovare l’indice uscente.
Nel simplesso primale ad ogni iterazione troviamo una nuova base primale ammissibile.
Nel simplesso duale troviamo una base duale ammissibile.
Che forma ha una base duale ammissibile?
La soluzione è ammissibile se contiene il vettore c, moltiplicato con la matrice di base inversa, negli indici di base, e zero nelle altre componenti, e tutte le componenti sono maggiori o uguali a zero.
Come si verifica l’ammissibilità primale?
Dato un x che è il risultato del prodotto tra la matrice di base inversa e le componenti di base del vettore b, la sol.ne è ammissibile se il prodotto di An e x è minore o uguale a bn.
Come trovare un indice entrante nell’algoritmo del simplesso duale?
l’indice entrante è il minimo degli indici non appartenenti alla base, che violano l’ammissibilità primale. Insomma per cui Aix > b.
Quali sono le componenti di una direzione di decrescita d a partire da una direzione di crescita eta?
di è uguale a meno eta-i se l’indice appartiene alla base. E’ uguale a uno se l’indice è l’indice entrante k, ed è uguale a zero altrimenti.
Come trovare una direzione di decrescita?
Chiamiamo k l’indice entrante scelto al passo precedente, e chiamiamo eta il prodotto tra Ak e la matrice di base inversa. Le componenti della direzione di decrescita sono queste:
Se il suo indice appartiene alla base, la componente vale meno eta-i
Se il suo indice è l’indice entrante k, la componente vale 1.
Altrimenti, l’indice vale 0.
Quanto vale il passo di spostamento theta nel simplesso duale, data una direzione di decrescita?
Il passo di spostamento theta vale il massimo passo che può essere compiuto lungo d senza perdere l’ammissibilità duale, vale quindi il minimo dei rapporti tra yi e eta-i, t.c. eta-i maggiore di zero.
Come verificare se la direzione di crescita è ammissibile?
E’ ammissibile se usiamo questo metodo perché l’abbiamo dimostrato.
Nel simplesso duale, come scegliere l’indice uscente?
Se theta segnato è il massimo passo che può essere compiuto lungo d senza perdere l’ammissibilità duale, l’algoritmo fa uscire un indice h che determina tale passo. Ossia, l’indice di una componente di y(theta) che diventerebbe negativa se fosse effettuato un passo più lungo di theta.
Riassumi brevemente i passi del simplesso duale
Si parte con una base duale ammissibile. Se la soluzione primale di base è ammissibile, allora abbiamo trovato la soluzione ottima. Altrimenti, scegliamo un k tra gli indici dei vincoli non soddisfatti e non appartenenti alla base. Scegliamo il k minimo per la regola anticiclo di Bland. Calcoliamo un eta.
Se tutte le componenti sono minori o uguali a zero, allora il problema primale non ha soluzioni.
Altrimenti, scegliamo un h, indice di base che ha il minor passo theta ammissibile.
Ora sostituiamo h con k nella base e iteriamo.
