Lezione n°10

Lezione n°10

Algoritmo del Simplesso:

- Coefficienti di costo ridotto - Condizioni di ottimalità

- Test dei minimi rapporti - Cambio di base

R. Cerulli – F. Carrabs

Lezioni di Ricerca Operativa

Università degli Studi di Salerno

Consideriamo il problema (PL) in Forma Standard

Data una base B ammissibile, partizioniamo sia la matrice A che il vettore delle incognite x come segue:

Il sistema di equazioni lineari Ax=b si può riscrivere come

Calcolo della soluzione ottima di un problema di PL.

Calcolo della soluzione ottima di un problema di PL.

Riscriviamo anche la funzione obiettivo come:

(1) Sostituendo in (1) l’espressione delle variabili di base:

Il valore della funzione obiettivo corrispondente alla base B è:

�

=  �

� −  �

�

�

⁽²⁾

otteniamo: z + (3)

z

Le relazioni (2) e (3) esprimono rispettivamente i vincoli e la funzione obiettivo in funzione delle variabili fuori base.

Indichiamo con e poichè otteniamo:

dove a

è la colonna di A che moltiplica la variabile fuori base x

.

�=� _� ^� ´�− ∑

�∈ �

� _� ^� � ⁻¹ _� � _� � _� + ∑

� ∈�

� _� � _�

� _� = ´ �− ∑

�∈ �

� ^{− 1} _� � _� � _�

Se e la funzione obiettivo diventa:

�=� _� ^� ´�− ∑

�∈�

� _� ^� � ⁻¹ _� � _� � _� + ∑

� ∈�

� _� � _�

�=� ₀ − ∑

� ∈ �

� _� � _� + ∑

�∈ �

� _� � _� = � ₀ − ∑

�∈ �

( � _� − � _� ) � _�

� _� = ´ �− ∑

�∈ �

� ⁻¹ _� � _� � _� = ´ �− ∑

� ∈�

� _� � _�

Infine fissato i vincoli diventano:

I coefficienti vengono detti coefficienti di costo ridotto

Consideriamo il problema (PL) in Forma Standard

Data una base B ammissibile, riscriviamo il problema in funzione di B come segue:

Forma canonica in funzione di una base B

y

= A

a

z

= c

A

a

b= A

b

z

= c

A

b

Verifichiamo se la soluzione di base corrente è ottima o può essere migliorata

Consideriamo la funzione obiettivo:

Verifichiamo come cambia il valore della funzione obiettivo incrementando la variabile fuori base x

che è attualmente nulla.

La funzione obiettivo migliora !

Supponiamo che esista un coefficiente k  N tale che:

����=� ₀ − ∑

�∈ �

( � _� − � _� ) � _�

�

− �

> 0

�

� = �₀ − (¿ ¿ � − �_�)�_�

¿

¿ 0

¿ 0

Teorema (Condizione di ottimalità)

Una soluzione di base non degenere di un problema di PL è ottima se e solo se:

 Nel caso di soluzione degenere possono esistere soluzioni ottime in cui il punto (2) del teorema non è soddisfatto.

 Tuttavia, se un problema ammette una soluzione ottima finita allora ammette una soluzione di base ottima che soddisfa le condizioni (1) e (2) del teorema.

1) i=1…,m (ammissibile)

2) (non migliorabile)

1

X

6

-3 -2

-1 1 (1)

(3) (2)

A B

C

Forma Standard

Verificare analiticamente se la soluzione di base associata al punto A soddisfa il test di

ottimalità.

B_A={1,3,4} N_A={2,5}

x₁ x₃ x₄ x₁ x₂ x₃ x₄ x₅

=[3,0,0]

� �−��=�

�

� �−��

z₂ - c₂ = c^T_BA_B^-1a₂ - c₂ = (3, 0, 0)A_B^-1 -1 1

-1 æ è çç ç

ö ø

÷÷

÷-1 = (0, 0, 32) -1 1

-1 æ è çç ç

ö ø

÷÷

÷-1= - 32 -1 = -5 2

z₅ - c₅ = c^T_BA_B^-1a₅ - c₅ = (3, 0, 0)A_B^-1 0 0 -1 æ è çç ç

ö ø

÷÷

÷- 0 = (0, 0, 32) 0 0 -1 æ è çç ç

ö ø

÷÷

÷- 0 = - 32 - 0 = -3 2

 Poichè incrementando il valore della variabile fuori base x

il valore della funzione obiettivo migliora, si potrebbe pensare di aumentare indefinitivamente x

.

 Tuttavia, aumentando x

anche il vettore delle variabili in base x

viene modificato in accordo all’equazione dei vincoli.

Dal momento che le x

sono uguali a zero, per , la relazione:

diventa:

In forma vettoriale:

Se y

 0 ∀i B ∈

allora x

cresce al crescere di x

e così x

continua a essere non

negativo. (ottimo illimitato)

Se esiste una componente i tale che y

> 0 allora x

decresce al crescere di x

.

Il valore di x

verrà incrementato finché una delle variabili in base assumerà valore zero. Infatti noi vogliamo che:

La variabile x

che si azzererà per prima verrà tolta dalle variabili di base e sarà rimpiazzata dalla variabile x

.

� _�

1

= �1− � _{1 �} � _� ≥ 0

� _�

2

= �2− � _2� � _� ≥ 0

� _�

�

= ��− � _�� � _� ≥ 0

………...……

………...……

………...………

………...………

Possiamo scrivere:

Dobbiamo considerare solo i rapporti in cui

≤0

>0

>0

sempre

Quindi, considerando i rapporti in cui y

>0, il valore assunto dalla variabile x

sarà:

Il precedente test viene chiamato test dei minimi rapporti ed è utilizzato per individuare la variabile in base x

che si azzererà per prima, al crescere di x

, e che quindi uscirà dalla base.

�

= �1 − �

�

≥ 0 ⟺ �1 − �

��

�

≥ 0

�

= �� − �

�

≥ 0 ⟺ �� − �

��

�

≥ 0

�

= ��− �

�

≥ 0 ⟺ ��− �

��

�

≥ 0

………...………

………...………

Riassumendo:

• Fare assumere ad x

un valore positivo significa portare la variabile x

in base.

• Nello stesso tempo il valore delle variabili di base:

 Cresce se y

< 0;

 Decresce se y

> 0;

 Non cambia se y

=0.

• Il valore che assume x

in base è calcolato tramite il test dei minimi rapporti:

• La variabile x

esce dalla base.

Il coefficiente y

è detto Pivot, (l’aggiornamento della base si dice Pivoting) e viene usato per aggiornare i valori delle variabili in base dopo l’ingresso in base di x

.

La nuova soluzione di base

Le nuove variabili fuori base

� _�

�

= ��− � _{� �} ��

� _{� �}

con N\{k}

� _� = � �

� _{� �}

Con il cambio delle variabili in base, la nuova matrice di base risulta composta delle stesse colonne della vecchia base ad eccezione del fatto che la colonna associata a è stata sostituita dalla colonna associata a x

.

x _Br

La nuova soluzione di base (a meno di casi degeneri) ha migliorato il valore della funzione obiettivo:

>0

>0

�=�

−( �

− �

) ��

� �� < � 0

>0