Lezione n
°
10
Algoritmo del Simplesso: - Coefficienti di costo ridotto - Condizioni di ottimalità
- Test dei minimi rapporti - Cambio di base
R. Cerulli
–
F. CarrabsLezioni di Ricerca Operativa
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.
𝐴!𝑥! + 𝐴"𝑥" = 𝑏 ⟹ 𝐴!𝑥! = 𝑏 − 𝐴"𝑥" ⟹ 𝑥! = 𝐴#$! 𝑏 − 𝐴!#$𝐴"𝑥" 𝑚𝑖𝑛 𝑧 = 𝑐%𝑥
A𝑥 = 𝑏 𝑥 ≥ 0
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 è:
𝑥
!= 𝐴
!"#𝑏 − 𝐴
!"#𝐴
$𝑥
$ (2)z = 𝑐
!%𝐴
"#!𝑏 −𝑐
!%𝐴
"#!𝐴
$𝑥
$+𝑐
$%𝑥
$otteniamo: (3)
Le relazioni (2) e (3) esprimono rispettivamente i vincoli e la funzione obiettivo in funzione delle variabili fuori base.
Indichiamo con 0𝑏 = 𝐴!#$𝑏 e poichè 𝐴"𝑥" = ∑&∈" 𝑎&𝑥& otteniamo:
dove aj è la colonna di A che moltiplica la variabile fuori base xj. 𝑧 = 𝑐!% 0𝑏 − 3 &∈" 𝑐!%𝐴!#$𝑎&𝑥& + 3 &∈" 𝑐&𝑥& 𝑥! = 0𝑏 − 3 &∈" 𝐴!#$𝑎&𝑥& 𝑧 = 𝑐!%𝐴!#$𝑏 − 𝑐!%𝐴!#$𝐴"𝑥" + 𝑐"%𝑥" 𝑥! = 𝐴!#$𝑏 − 𝐴#$! 𝐴"𝑥"
Se 𝑧( = 𝑐!% 0𝑏 e 𝑧& = 𝑐!%𝐴!#$𝑎& la funzione obiettivo diventa: 𝑧 = 𝑐!% 0𝑏 − 3 &∈" 𝑐!%𝐴#$! 𝑎&𝑥& + 3 &∈" 𝑐&𝑥& 𝑧 = 𝑧( − 3 &∈" 𝑧&𝑥& + 3 &∈" 𝑐&𝑥& = 𝑧( − 3 &∈"
(𝑧& − 𝑐&)𝑥&
𝑥! = 0𝑏 − 3
&∈"
𝐴!#$𝑎&𝑥& = 0𝑏 − 3
&∈"
𝑦&𝑥&
Infine fissato 𝑦& = 𝐴#$! 𝑎& i vincoli diventano:
Consideriamo il problema (PL) in Forma Standard
Data una base B ammissibile, riscriviamo il problema in funzione di B come segue: y j = AB −1 aj zj = cB T AB−1aj b = AB−1b z0 = cTBAB−1b Forma canonica in funzione di una base B
𝑚𝑖𝑛 𝑧 = 𝑧( − 3
&∈"
(𝑧& − 𝑐&)𝑥&
𝑥! = 0𝑏 − 3 &∈" 𝑦&𝑥& 𝑥 ≥ 0 𝑚𝑖𝑛 𝑧 = 𝑐%𝑥 A𝑥 = 𝑏 𝑥 ≥ 0
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 xk che è attualmente nulla.
La funzione obiettivo migliora !
Supponiamo che esista un coefficiente k
Î
N tale che:𝑚𝑖𝑛 𝑧 = 𝑧( − 3
&∈"
(𝑧& − 𝑐&)𝑥&
𝑧) − 𝑐) > 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)
𝑏* ≥ 0 i=1…,m (ammissibile)1
X
6 -3 -2 -1 1 (1) (2) (3) A B C Forma Standard Verificare analiticamente se la soluzione di base associata al punto A soddisfa il test diBA={1,3,4} NA={2,5} x1 x3 x4 z2 − c2 = cB T AB−1a2 − c2 = (3, 0, 0)AB−1 −1 1 −1 " # $ $ $ % & ' ' '−1 = (0, 0, 3 2) −1 1 −1 " # $ $ $ % & ' ' '−1 = − 3 2 −1= − 5 2 z5 − c5 = cB T AB−1a5 − c5 = (3, 0, 0)AB−1 0 0 −1 " # $ $ $ % & ' ' '− 0 = (0, 0, 3 2) 0 0 −1 " # $ $ $ % & ' ' '− 0 = − 3 2 − 0 = − 3 2 x1 x2 x3 x4 x5 A = 2 4 1 2 1 1 0 0 1 1 0 1 0 2 1 0 0 1 3 5 ABA = 2 4 1 2 1 0 1 0 1 2 0 0 3 5 ABA1 = 2 40 0 1 2 1 0 14 0 1 12 3 5 𝑐!"=[3,0,0] 𝑧𝑗 − 𝑐𝑗 = 𝑐!"𝐴!#$𝑎𝑗 − 𝑐𝑗
Ø Poichè incrementando il valore della variabile fuori base xk il valore della funzione obiettivo migliora, si potrebbe pensare di aumentare indefinitivamente xk.
Ø Tuttavia, aumentando xk anche il vettore delle variabili in base xB viene modificato in accordo all’equazione dei vincoli.
𝑚𝑖𝑛 𝑧 = 𝑧( − 3
&∈"
(𝑧& − 𝑐&)𝑥&
𝑥! = 0𝑏 − 3
&∈"
𝑦&𝑥& 𝑥 ≥ 0
Dal momento che le xj sono uguali a zero, per 𝑗 ∈ 𝑁\{𝑘}, la relazione: diventa:
𝑥
!= &𝑏 − (
&∈$𝑦
&𝑥
&𝑥
!= &𝑏 − 𝑦
(𝑥
(In forma vettoriale:
Se
y
ik£
0
∀
i
∈
B
allora x
Bicresce al crescere di x
ke così x
Bicontinua a essere non
negativo. (
ottimo illimitato
)
Se esiste una componente i tale che yik > 0 allora xBi decresce al crescere di xk.
Il valore di xk verrà incrementato finché una delle variabili in base assumerà valore zero. Infatti noi vogliamo che:
La variabile xBi che si azzererà per prima verrà tolta dalle variabili di base e sarà rimpiazzata dalla variabile xk.
𝑥
!+= 𝑏
1− 𝑦
#(𝑥
(≥ 0
𝑥
!,= 𝑏
2− 𝑦
)(𝑥
(≥ 0
𝑥
!-= 𝑏
𝑚− 𝑦
*(𝑥
(≥ 0
………...……
………...……
………...………
………...………
Possiamo scrivere:
Dobbiamo considerare solo i rapporti in cui
𝑦
+( > 0≤0 >0 >0
𝑥
!+= 𝑏
1− 𝑦
#(𝑥
(≥ 0 ⟺ sempre
𝑥
!,= 𝑏
2− 𝑦
)(𝑥
(≥ 0 ⟺ 𝑥
(≤
,% -,.𝑥
!-= 𝑏
𝑚− 𝑦
*(𝑥
(≥ 0 ⟺ 𝑥
(≤
,& --.Quindi, considerando i rapporti in cui yik >0, il valore assunto dalla
variabile xk sarà:
Il precedente test viene chiamato test dei minimi rapporti ed è utilizzato per individuare la variabile in base xBr che si azzererà per prima, al crescere di xk, e che quindi uscirà dalla base.
x
k=
b
ry
rk= min
1im⇢
b
iy
ik: y
ik> 0
𝑥!' = 𝑏1 − 𝑦$)𝑥) ≥ 0 ⟺ 𝑏1 − 𝑦$) 𝑏𝑟 𝑦/) ≥ 0 𝑥!( = 𝑏𝑟 − 𝑦/)𝑥) ≥ 0 ⟺ 𝑏𝑟 − 𝑦/) 𝑏𝑟 𝑦/) ≥ 0 𝑥!) = 𝑏𝑚 − 𝑦0)𝑥) ≥ 0 ⟺ 𝑏𝑚 − 𝑦0) 𝑏𝑟 𝑦/) ≥ 0 ………...……… ………...………Riassumendo:
• Fare assumere ad xk un valore positivo significa portare la variabile
xk in base.
• Nello stesso tempo il valore delle variabili di base: Ø Cresce se yik < 0;
Ø Decresce se yik > 0;
Ø Non cambia se yik=0.
• Il valore che assume xk in base è calcolato tramite il test dei minimi rapporti:
• La variabile xBr esce dalla base.
x
k=
b
ry
rk= min
1im⇢
b
iIl coefficiente yrk è 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 xk.
La nuova soluzione di base Le nuove variabili fuori base
𝑥
!1= 𝑏
𝑖− 𝑦
+(𝑏
𝑟𝑦
.(𝑥
&= 0 ∀𝑗 ∈ 𝑁′ 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
k.
La nuova soluzione di base (a meno di casi degeneri) ha migliorato il valore della funzione obiettivo:
>0 >0
𝑧 = 𝑧( − (𝑧) − 𝑐)) 𝑏𝑟
𝑦𝑟𝑘 < 𝑧0
