• Non ci sono risultati.

Ricerca Operativa A.A. 2007/2008

N/A
N/A
Protected

Academic year: 2021

Condividi "Ricerca Operativa A.A. 2007/2008"

Copied!
6
0
0

Testo completo

(1)

Ricerca Operativa

A.A. 2007/2008

6. Metodo del simplesso

Metodo del simplesso: ingredienti

1. Generare una soluzione ammissibile di base di partenza

2. Verificare l’ottimalità della soluzione corrente

3. Se la soluzione non è ottima, generare una soluzione di base (“vicina”) che migliora la funzione obiettivo

4. Iterare i passi 2 e 3

(2)

2

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.3

Costi ridotti

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.4

Osservazioni

 I costi ridotti delle variabili fuori base dicono quanto varia z al variare della corrispondente variabile

 I costi ridotti delle variabili in base sono nulli Teorema

Dim:

Attenzione! Non vale ⇐ ⇐ ⇐ ⇐ (contro-esempio: soluzioni di base degeneri).

Test di ottimalità

(3)

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.5

Miglioramento della funzione obiettivo

Le altre variabili fuori base restano al valore 0

Massimo miglioramento

(4)

4

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.7

Osservazioni

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.8

Cambiamento di base

Possiamo passare da una soluzione di base ad un’altra (in

generale migliorando la funzione obiettivo): abbiamo un

(buon) metodo per esplorare lo spazio delle soluzioni di

base alla ricerca della soluzione (di base) ottima.

(5)

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.9

Algoritmo del simplesso

(forma matriciale)

Sistema in forma matriciale: tableau

(6)

6

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.11

Tableau in forma canonica

Luigi De Giovanni - Ricerca Operativa - 6. Metodo del simplesso 6.12

Operazione di Pivot

Riferimenti

Documenti correlati

Th.4.2.1 p.78, prima parte] In ciascun spazio vettoriale finitamente generato, il numero di vettori di un qualsiasi insieme linearmente indipendente ` e minore o uguale al numero

Il teorema fondamentale sulle basi afferma che ogni spazio vettoriale (finita- mente generato) possiede qualche base (finita), che si puo’ ottenere come sottin- sieme di un sistema

 Come valutare la stabilità della soluzione proposta in funzione di variazioni dei dati (rendite della produzione, risorse disponibili etc.).  Come stabilire le soluzioni ottime

ottimizzazione e produce in output la soluzione ottima del modello e informazioni ad essa collegate. Ruolo

Procediamo dunque con l’operazione di cambio base e scegliamo come variabile che entra in base, la varia- bile che corrisponde al costo ridotto negativo, ovvero x 1 (nuovamente!)

I Ogni soluzione di base ` e definita da n vincoli attivi linearmente indipendenti, che definiscono un unico punto. I quindi, diverse soluzioni di base corrispondono a diversi

Due soluzioni di base si dicono adiacenti se esistono n − 1 vincoli linearmente indipendenti che sono attivi in entrambe. Per problemi in forma standard, si dice che due basi

Si riformuli la funzione obiettivo dell’esempio 1.34 usando le matrici di permutazione x