Appunti di Ricerca operativa, anno 2022/2023

B N

seguente maniera:

∑ ∑

+ =b

a x a x

ji ji ji ji

∈I ∈I

i i

B N x e x

Utilizzando i sotto vettori il sistema può essere posto nella forma:

B N

+ =b

B x N x

B N

Oppure anche;

−1 −1

+ =B

x B N x b

B N

Oss: un problema di PL in forma standard può essere scritto in tanti modi quante sono

le matrici di base di A.

Tale riformulazione ci permette di osservare che il sistema Ax=b può essere risolto

x x x

esprimendo in funzione di . La soluzione che si ottiene annullando

B N N

viene definita nel modo seguente:

Def: x

un vettore è detto soluzione di base del sistema Ax=b se i suoi sotto vettori

x́ B

x

e sono tali che:

N −1

=B

x́ b

B =0

x́ N n−m −1

Inoltre se la matrice di base B è ammissibile ( ovvero se ) allora il vettore

B b ≥ 0 m

è detto soluzione di base ammissibile ( SBA ).

x́

Che relazione ci sono tra SBA e vertici?

Teorema: 6.2.2

Il punto ,appartenente a P, è vertice se e solo se è una SBA.

x́

Dai risultati noti è intuibile che il numero di vertici è pari al più al numero di possibili

modi diversi di prendere m colonne di A fra tutte le sue n.

Il numero di SBA, e quindi di vertici, può anche essere inferiore per via del fatto che

e m colonne potrebbero non essere linearmente indipendenti o anche che la soluzione

( )

n

potrebbe non essere ammissibile. Ovvero è pari al più ad .

m

Perciò segue che una soluzione è SBA se e solo se le colonne di A corrispondenti

x́

alle componenti di positive sono linearmente indipendenti.

x́

Ciò per dire che concettualmente il vertice di P e SBA sono equivalenti.

Oss: la corrispondenza tra basi ammissibili e soluzioni di base ammissibili non è

biunivoca; infatti una soluzione può essere stata generata da più di una base

ammissibile diversa. Tale anomalia è legata al fatto che nel vettore ci possano

−1

B b

essere degli zeri.

In questi casi stiamo osservando una soluzione di base ammissibile degenere per

x́

via del fatto che il numero di componenti positive di è minore di m.

x́

Nel caso in cui una soluzione è non degenere allora ogni componente di è

−1

B b

strettamente positiva e vi sarà una corrispondenza biunivoca tra SBA e basi

ammissibili come mostrato dal seguente teorema:

Teorema: 6.2.4

Se una soluzione di base ammissibile è non degenere allora esiste una ed una

x́

sola base ammissibile B tale che: −1

=B

x́ b

B =0

x́ N n−m

CAPITOLO 6B Introduzione al metodo del simplesso

Il metodo del simplesso permette di risolvere problemi di PL in forma standard. Per

risolvere sfrutta il teorema fondamentale andando a cercare la soluzione tra i vertici

del poliedro che rappresenta l’insieme ammissibile.

Tre sono gli elementi che caratterizzano questo metodo:

- Selezione efficiente dei vertici.

- Passaggio tra vertici diversi senza inversioni di matrice.

- Individuazione del vertice ottimo grazie ha semplici criteri.

Tali caratteristiche sono ottenute grazie alle basi ammissibili della matrice A, che

hanno senso di esistere solo nel momento in cui il poliedro è non vuoto e con A che

ha rango massimo.

Per verificare che un problema di PL sia ammissibile esistono diversi metodi. Nel

seguito si descrive una particolare realizzazione in due fasi:

I fase:

vengono eliminati i vincoli di uguaglianza linearmente dipendenti, viene identificata

una base ammissibile B e calcolati e .

−1 −1

B N B b

II fase:

risoluzione del problema attraverso degli step.

- Calcolo della SBA associata a B.

- Controllo del criterio sufficiente di ottimalità.

- Controllo del criterio sufficiente di illimitatezza.

- Nel caso in cui entrambi i criteri non sono soddisfatti si procede a determinare

~

una nuova base ammissibile .

B

Si ripete tale fase fino a che non si determina una soluzione ottima o si conclude che

il problema è illimitato inferiormente.

Essendo l’algoritmo della fase II essenziale nella risoluzione della fase I si procede ad

illustrare la seconda fase: la fase II del metodo del simplesso

Assunto che l’insieme ammissibile sia non vuoto e che il rango di A sia pari ad m

possiamo riscrivere il problema in una forma equivalente:

x

Esplicitando dal vincolo e sostituendo nella funzione obiettivo posso riformulare

b

il problema:

Oss: il problema è in forma canonica rispetto alla base B ed il vettore

T

( )

−1 è detto vettore dei costi ridotti.

=C −

γ B N C

N B x

Eliminando la variabile si ottiene un’ennesima riformulazione del problema:

b

A sua volta chiamato problema ridotto.

Un vettore è una soluzione ammissibile del problema scritto in forma standard se

^

x ^

x

e solo se il vettore è una soluzione ammissibile del problema ridotto e

N

−1 −1 . Per di più il valore della funzione obiettivo coincide nei due

^ ^

=B

x b−B N x

B N

problemi. Criterio di ottimalità

Il primo passo del metodo del simplesso è capire se la base ammissibile data è una

soluzione ottima del problema. A questo scopo introduciamo il criterio di ottimalità.

Teorema 6.4.1

Data una base ammissibile B della matrice A del problema in forma standard. Se il

vettore dei costi ridotti è non negativo

T

( )

−1

=C −

γ B N C ≥ 0 −m

N B n

Allora la SBA associata alla base B è ottima per il problema in forma standard.

x́

Inoltre possiamo affermare che, se il vettore dei costi ridotti è strettamente positivo,

allora la SBA associata alla base B è l’unica soluzione ottima.

x́

Essendo un criterio sufficiente non è in grado di determinare il fatto che una

soluzione è ottima. Criterio di illimitatezza

Nel caso in cui il criterio di ottimalità non è rispettato si cerca di capire se il problema

è illimitato inferiormente attraverso il criterio di illimitatezza.

Oss: il fatto che il criterio di ottimalità non sia rispettato implica che

{ }

{ }

ⅈ ∈ ∅

<0

1, … , n−m : γ ≠

i

Teorema 6.4.2

Data una matrice ammissibile B della matrice A del problema in forma standard. Se

abbiamo che:

{ }

per qualche indice ⅈ ∈ 1 , … , n−m

- <

γ 0 .

i

- La colonna i esima della matrice è tutta non positiva.

−1

B N

Allora il problema è illimitato inferiormente.

Determinazione di una nuova base ammissibile

Nel caso in cui i criteri di ottimalità ed illimitatezza non siano soddisfatti il metodo

del simplesso cerca di determinare una nuova SBA. { }

π , … , π

Oss: le colonne della matrice saranno indicate da .

−1

B N 1 n−m ~

Quindi il metodo del simplesso cerca di costruire una nuova soluzione che deve

x

~

x

avere almeno una componente del vettore diversa da zero.

N x

L’idea è quella di modificare una sola componente di , ad esempio l’h esima,

N

portandola da zero ad un valore positivo .

ρ

Formalmente:

e

In cui è l’h esimo vettore unitario con n -m componenti.

h

Definito genericamente questo nuovo punto dobbiamo risolvere due questioni:

- come scegliere h?

- quanto vale ?

ρ Scelta dell’indice h

Per capire quale variabile fuori base modificare, il metodo del simplesso determina

dei nuovi punti in cui la funzione obiettivo non sia aumentata.

Teorema 6.4.3

Sia data una matrice di base ammissibile B del problema in forma standard.

~

Sia la SBA associata e sia il vettore dei coefficienti ridotti.

x γ

γ ≤ 0

Se l’indice h è tale per cui h

Allora, il punto ha un valore della funzione obiettivo non superiore a quello di

( )

x ρ

~ , cioè

x ~

T T

( )

c x ρ ≤ c x ~

<0

γ T T

Oss: nel caso in cui allora .

( ) <

c x ρ c x

h Scelta del valore dello scalare ρ

Nello scegliere il valore di ρ si deve prima di tutto tener conto della ammissibilità del

punto prodotto x(ρ). Il passo successivo è quello di far vedere che esiste un valore

che permette di identificare un punto x( che è una soluzione di base

¿

ρ́ ρ́

ammissibile del problema. Il teorema che segue riporta la scelta di sulla base del

ρ́

criterio del rapporto minimo.

Teorema 6.4.4

Oss: l’interpretazione del problema è la seguente: supposto di avere una base

ammissibile B e supposto che non sia soddisfatto il criterio di ottimalità né quello di

illimitatezza. ~

Allora, se si considera una nuova soluzione di base corrispondente alla base B

ottenuta facendo entrare nella base B una qualunque variabile alla quale è associato

un costo ridotto negativo e facendo uscire una variabile scelta secondo il criterio del

rapporto minimo, questa nuova soluzione è ammissibile e ha un valore

della funzione obiettivo non superiore a quello della soluzione di base precedente.

Oss: il minimo può essere raggiunto in corrispondenza a più di un indice. In questo

caso si può fare uscire dalla base una qualunque delle variabili in corrispondenza alle

quali si è raggiunto il minimo.

Oss: dal criterio del rapporto minimo si deduce che è nullo se e solo se

ρ́

( )

−1 =0

B b k ( )

−1

Condizione necessaria affinché sia nulla è che risulti per qualche

ρ́ =0

B b i

indice i , ovvero che la soluzione associata alla base sia degenere. Pertanto il nuovo

vettore coincide con quello di partenza anche se la base ammissibile è diversa.

Non è una condizione sufficiente perché è possibile che sia diverso da zero in

ρ́

corrispondenza di una soluzione degenere. Si verifica tale situazione se e solo se ogni

componente nulla del vettore corrisponde una componente non positiva di

−1

B b

π .

h ~ ~

Calcolo della nuova matrice e del nuovo vettore : operazione di pivot

−1 −1

B N B b

~ ~ ~

Possiamo a questo punto calcolare da capo e anche e che sono

−1 −1 −1

B B N B b

le quantità necessarie per il calcolo del nuovo vertice.

Questo problema è equivalente a passare dalla forma canonica rispetto a B del

problema ~

Alla forma canoni