I spostamento su una base adiacente

Il metodo del simplesso

I condizione sufficiente di ottimalit` a

I spostamento su una base adiacente

rif. Fi 3.2;

Ricapitolando

Sin qui abbiamo un algoritmo enumerativo applicabile quando P ` e un politopo, che calcola una soluzione ottima in al pi` u

 _n

m



= _m!(n−m)! ^n! passi enumerando le sba.

Vogliamo migliorarlo mediante:

I un criterio di arresto che riconosca una sba ottima

I uno spostamento da una sba ad un’altra migliorativa

I l’estensione al caso generale

Valore di una soluzione

Rappresentiamo il sistema Ax = b rispetto ad una base ammissibile B:

x B = B ⁻¹ b − B ⁻¹ Fx F

ricaviamo l’espressione del costo:

c ^T x = [c ^T _B , c ^T _F ]

 x _B x F



= [c ^T _B , c ^T _F ]

 B ⁻¹ b − B ⁻¹ Fx _F x F



cio` e

c ^T x = c ^T _B B ⁻¹ b + (c ^T _F − c ^T _B B ⁻¹ F)x F = cost + ¯ cx

Costi ridotti

Definizione Il vettore

¯

c ^T = c ^T − c ^T _B B ⁻¹ A = [c ^T _B − c ^T _B B ⁻¹ B, c ^T _F − c ^T _B B ⁻¹ F] =

= [0, c ^T _F − c ^T _B B ⁻¹ F]

si dice vettore dei costi ridotti rispetto alla base B

Possiamo dimostrare un risultato che ci permette di stabilire

l’ottimalit` a di una base: Dato un problema in forma standard

{min c ^T x : x ∈ P }, con P = {x ∈ R ⁿ : Ax = b, x ≥ 0} vale il

seguente

Condizione di ottimalit` a

Teorema

Sia x ^∗ una sba associata alla base B. Se ¯ c ^T = c ^T − c ^T _B B ⁻¹ A ≥ 0 allora x ^∗ ` e una soluzione ottima

Dimostrazione

Il costo di una soluzione x ∈ P ` e c ^T x = c ^T _B B ⁻¹ b + ¯ c ^T x essendo per ipotesi ¯ c ≥ 0 risulta

c ^T x ≥ c ^T _B B ⁻¹ b per ogni x ≥ 0, cio` e per ogni x ∈ P ma

c ^T _B B ⁻¹ b = [c ^T _B , c ^T _F ] h _B

b 0

i

= c ^T x ^∗

Ottimalit` a e degenerazione

la condizione diventa anche necessaria nel caso non degenere:

Teorema

Sia x ^∗ una sba associata alla base B, con B non degenere. Allora:

I se ¯ c ≥ 0 allora x ^∗ ` e ottima

I se x ^∗ ` e ottima allora ¯ c ≥ 0

Al contrario, nel caso degenere esiste la possibilit` a che una sba sia

ottima ma qualche variabile (fuori base) abbia costo ridotto

negativo

Esempio (cont.)

− min −5x ₁ − 4x ₂ x ₁ + 3x ₂ + x ₃ = 4 4x ₁ + x ₂ + x ₄ = 3 x 1 , x 2 , x 3 , x 4 ≥0

x₁ = 0

x₃ = 0

x₄ = 0 A

B

x₁ = 0

x₂ = 0

x₄ = 0

C D

B = [A

, A

] =

 1 1 4 0



, B

=

 0 1/4 1 −1/4



c

B

F = [−5 0]

 0 1/4 1 −1/4

  3 0 1 1



= [−5/4, −5/4]

c

− c

B

F = [−4, 0] − [−5/4, −5/4] =⇒ ¯ c

= [0, −11/4, 0, 5/4]

=⇒ x = (3/4, 0, 13/4, 0) ` e sba NON ottima (vertice C)

Esempio (cont.)

B = [A

, A

] =

 1 3 4 1



, B

=

 −1/11 3/11 4/11 −1/11



c

B

F = [−5 − 4]

 −1/11 3/11 4/11 −1/11

  1 0 0 1



= [−1, −1]

c

− c

B

F = [0, 0] − [−1, −1] =⇒ ¯ c

= [0, 0, 1, 1]

=⇒ x = (5/11, 13/11, 0, 0) ` e sba ottima (vertice B)

Passando dal vertice C al vertice B la variabile x 2 entra in base e passa da 0 a 13/11; ci` o fa diminuire il valore della f.o. in quanto

¯

c ₂ = −11/4 < 0 (ricordate che c ^T x = cost + ¯ c ^T x).

Quindi, i costi ridotti individuano le variabili candidate ad entrare

in base, cio` e quelle che riducono il valore della f.o.

Spostamento su una base adiacente

Sia B = [A _B(1) , . . . , A _B(m) ] una base ammissibile di A,

x = (B ⁻¹ b, 0) la corrispondente sba e c ^T x = c ^T _B B ⁻¹ b + ¯ c ^T x il suo valore.

Data una variabile x h , h 6∈ B(1), . . . , B(m), per cui ¯ c h < 0, vogliamo individuare una base adiacente a B che includa la colonna A _h (in modo che x _h entri in base)

Quindi rilasciamo la variabile x h e teniamo fissate a zero tutte le

altre fuori base.

Spostamento su una base adiacente

il sistema

x B = B ⁻¹ b − B ⁻¹ Fx F

diventa:

x _B = B ⁻¹ b − B ⁻¹ F















 0

.. . x _h

.. . 0

















= B ⁻¹ b − B ⁻¹ A _h x _h = ¯ b − ¯ A _h x _h

NB. essendo B una base ammissibile risulta b ≥ 0 ¯

Spostamento su una base adiacente



 

 



 

 



x _B(1) = ¯ b 1 − ¯ a 1h x h ≥ 0 x _B(2) = ¯ b 2 − ¯ a _2h x _h ≥ 0 .. .

x _B(m) = ¯ b m − ¯ a _mh x _h ≥ 0

=⇒



 

 



 

 



¯

a 1h x h ≤ ¯b ₁

¯

a _2h x _h ≤ ¯b ₂ .. .

¯

a _mh x _h ≤ ¯b _m Per ciascuna condizione i si hanno due possibilit` a:

I ¯ a _ih ≤ 0 =⇒ nessun vincolo per x _h ≥ 0

I ¯ a _ih > 0 =⇒ x _h ≤ ¯b _i /¯ a _ih

quindi, il valore massimo che pu` o assumere x <sub>h</sub> ` e

θ = min{b i /a _ih : 1 = 1, . . . , m, ¯ a _ih > 0}

Conseguenze

I quando x _h assume il valore limite θ la f.o. diminuisce della quantit` a |¯ c h |θ

I se esiste un qualche i per cui ¯ b i = 0 (caso degenere) e

¯

a _ih > 0, allora θ = 0 e non si ha miglioramento della f.o. (si rimane sullo stesso vertice!)

I se ¯ a _ih ≤ 0 per i = 1, . . . , m allora x _h pu` o assumere un valore

grande a piacere ed il problema ` e illimitato

Nuova base

sia t una riga per cui ¯ a _th > 0 tale che θ = b _t /a _th . Aumentando x _h in modo che x _h = θ si ottiene:

x _B(t) = ¯ b t − θ¯ a _th = 0

cio` e x <sub>h</sub> ”esce dalla base”: la colonna A <sub>B(t)</sub> ` e stata scambiata con la colonna ”migliorativa” A _h

B = [A _B(1) , . . . , A _B(t) , . . . , A _B(m) ]

↓

B = [A ˜ _B(1) , . . . , A _B(t−1) , A _B(h) , A _B(t+1) , . . . , A _B(m) ]

Nuova base

` E facile dimostrare che ˜ B ` e ancora una base:

B ⁻¹ B = ˜

























1 0 . . . a ¯ _1h . . . 0 0 0 1 . . . a ¯ 2h . . . 0 0

.. .

0 0 . . . ¯ a _th . . . 0 0 .. .

0 0 . . . ¯ a _m−1,h . . . 1 0 0 0 . . . ¯ a _mh . . . 0 1























 quindi,

det(B ⁻¹ B) = (−1) ˜ ^t−h ¯ a _th 6= 0 =⇒ det( ˜ B) 6= 0