Lezione n° 11
Algoritmo del Simplesso:
- Coefficienti di costo ridotto - Condizioni di ottimalità
- Test dei minimi rapporti - Cambio di base
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata Università di Salerno
Prof. Cerulli – Dott.ssa Gentili
–
Dott. CarrabsConsideriamo il problema (PL) in Forma Standard
0
min
≥
=
=
xb x
A x c z T
A=[ A
B| A
N] x x x m componenti
n m componenti
B
= ⎡
N⎣ ⎢ ⎤
⎦ ⎥ −
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
AB xB + AN xN = b à AB xB = b - AN xN à xB = A-1Bb - A-1BAN xN
Calcolo della soluzione ottima di un problema di PL.
Calcolo della soluzione ottima di un problema di PL.
Riscriviamo anche la funzione obiettivo come:
[ ]
TB B TN N(1)
N T B
N T
B
T
c x c x
x c x
c x
c
z ⎥ = +
⎦
⎢ ⎤
⎣
= ⎡
=
Sostituiamo in (1) l’espressione delle variabili di base:
N
(2)
N B
B
A
Bb A A x x =
−1−
−1(3)
ottenendo:
z = c
TBA
B−1b − c
TBA
B−1A
Nx
N+ c
TNx
NIl valore della funzione obiettivo corrispondente alla base B è:
b A
c
z =
TB B−1Le relazioni (2) e (3) esprimono rispettivamente i vincoli e la funzione obiettivo in funzione delle variabili fuori base.
(4)
Le (4) sono m+1 equazioni.
N N
B B
B
A b A A x
x =
−1−
−1N T
N N
N B
T B B
T
B
A b c A A x c x
c
z =
−1−
−1+
Indicando con:
b A
b =
B−1Otteniamo:
N T
N N N
B T
B T
B N
T N N N
B T B B
T
B A b c A A x c x z c b c A A x c x
c
z
=
−1−
−1+ ⇔ = −
−1+
N N B
B N
N B
B
B
A b A A x x b A A x
x =
−1−
−1⇔ = −
−1dove a
jè la colonna di N che moltiplica la j-esima variabile fuori base.
Inoltre essendo:
∑
∈=
N j
j j N
N
x a x
A
Abbiamo
∑
∑
∈ ∈−
− + ⇔ = − +
−
=
N j
j j N
j
j j B
T B T
B N
T N N
N B
T B T
Bb c A A x c x z c b c A a x c x
c
z 1 1
j j N
j N B
N
B
b A
BA x b A a x
x ∑
∈
−
−
⇔ −
−
=
1 1Dove le y
jsono termini noti e x
jvariabili.
Infine ponendo: A
B−1a
j= y
jOtteniamo: ∑ ∑
∈
∈
−
⇔ = −
−
=
N j
j j j B
j N
j
B
b A
Ba x x b y x
x
1La nostra funzione obiettivo diventa:
∑
∑
∑
∑
∈ ∈ ∈ ∈− + ⇔ = − +
−
=
N j
j j N
j
j j T
B T
B N
j
j j N
j
j j B
T B T
Bb c A a x c x z c b c y x c x
c
z 1
Poniamo: c
TBb = z
0e c
TBy
j= z
jla nostra F.O. diventa:
⇔ +
−
=
⇔ +
−
=
∑ ∑ ∑ ∑
∈
∈
∈
∈ j N
j j N
j
j j N
j
j j N
j
j j T
B T
Bb c y x c x z z z x c x
c
z min 0
min
I coefficienti z −
jc
jvengono detti coefficienti di costo ridotto.
∑
∈−
−
=
⇔
N j
j j
j c x
z z
z
( )
min
0Verifichiamo se la soluzione di Base corrente è ottima o può essere migliorata
Consideriamo l’obiettivo: ∑
∈
−
−
=
N j
j j
j
c x
z z
z ( )
min
0e consideriamo come varia l’obiettivo facendo diventare positiva la variabile fuori base x
k, attualmente nulla.
k k
k
c x
z z
z =
0− ( − )
>0
>0
L’obiettivo migliora ! Supponiamo che esista un coefficiente k∈N tale che
> 0
−
kk
c
z
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à.
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 le equazioni (5) corrispondenti ai vincoli variano, modificando i valori delle variabili di base:
0
0
≥
≥
−
= ∑
∈
x
x y b
x
N j
j j
B
(5)
Dal momento che per j
∈N le x
jsono uguali a zero per j ≠ k la relazione
∑
∈−
=
N j
j j
B
b y x
x
Diventa
k k
B
b y x
x = −
In forma vettoriale:
k
mk rk
k k
m r
B B B B
x
y y y y
b b b b
x x x x
m r
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎦
⎤
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎣
⎡
−
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎦
⎤
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎣
⎡
=
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎥ ⎥
⎦
⎤
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎣
⎡
2 1 2
1
2 1
Se yik ≤0 per ogni i
allora xBi cresce al crescere di xk e così xBi continua a essere non negativo.
k k
B
b y x
x = −
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 che costituiscono la soluzione di base assumerà valore zero. Infatti noi
vogliamo che:
0 0 0
2 2 1 1
2 1
≥
−
=
≥
−
=
≥
−
=
k m mk
B
k k B
k k B
x y
b x
x y
b x
x y
b x
m
la variabile che si azzererà per prima verrà tolta dalle variabili di base e sarà sostituita da xk.
mk m k
k m mk
B
k k
k k B
k k B
y x b
x y
b x
y x b
x y
b x
sempre x
y b
x
m
= − ≥ ⇔ ≤
≤
⇔
≥
−
=
⇔
≥
−
=
0
0
0
2 2 2 2
1 1
2 1
Possiamo scrivere:
Dobbiamo considerare solo i rapporti in cui
y
ik> 0
≤0
>0
>0
Quindi considerando quei rapporti in cui yjk >0 la variabile xk assumerà il seguente valore:
⎪⎭
⎪ ⎬
⎫
⎪⎩
⎪ ⎨
⎧ >
=
= min
∈:
jk0
jk j B
rk j r
k
y
y b y
x b
Così:
0 0
0 0
0 0 1 1
1 1
1
≥
−
⇔
≥
−
=
=
−
⇔
≥
−
=
≥
−
⇔
≥
−
=
rk r m mk
k m mk
B
rk r r rk
k r rk
B
rk r k
k k B
y y b
b x
y b
x
y y b
b x
y b
x
y y b
b x
y b
x
m r
Fare assumere ad x
kun valore positivo significa portare la variabile x
kin base.
Nello stesso tempo il valore delle altre variabili di base per cui y
ik>0 diminuisce.
⎪⎭
⎪ ⎬
⎫
⎪⎩
⎪ ⎨
⎧ >
=
= min
∈:
jk0
jk j B
rk j r
k
y
y b y
x b
Il valore che x
kassume in base è quello corrispondente
all’annullamento della prima variabile di base, cioè
La variabile x
kentra in base con tale valore, ed in corrispondenza la variabile x
Bresce di base.
Il coefficiente y
rkè 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
k.
rk r
k
y
x = b
rk r i ik
B
y
y b b
x
i= −
La nuova soluzione di base
{ }
, 0con
0 ∀ ∈ ' ' = ∪ − =
= r Br
j j N N B N k x
x Le nuove variabili
fuori base
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.
xBr
La nuova soluzione di base ha migliorato il valore della funzione obiettivo:
0
0
( ) z
y c b
z z
z
rk r k
k
− ≤
−
=
>0
>0
E’ possibile iterare il procedimento fino a che esiste qualche variabile fuori base che può migliorare l’obiettivo se portata in base.
5. Teorema (Condizione di ottimalità)
Una soluzione di base non degenere di un problema di PL è ottima se e solo se:
le) migliorabi (non
0 2)
le) (ammissibi
0
1)
N j
c z
b
j j
i
