Test di ottimalit` a

Il metodo del simplesso

I

implementazione matriciale

I

implementazione ”tableau”

rif. Fi 3.2;

Test di ottimalit` a

Test Opt Input: B

Output: ¯ c, opt ∈ {true, f alse}

Init. opt := f alse u

= c

B

¯

c

:= c

− u

F

Test if ¯ c

= 0 then opt := true

Test di illimitatezza

Test Illim

Input: B

, indice h fuori base

Output: A ¯

= B

A

, illim ∈ {true, f alse}

Init. illim := f alse calcola ¯ A

= B

A

Test if ¯ a

≤ 0, i ∈ {1, . . . , m} then illim := true

Metodo del Simplesso (forma matriciale)

Input: A, b, c, B = [A

, . . . , A

] Output: x sol. ottima OR illim = true Init. illim := f alse, opt := f alse

Main Loop while (illim = f alse and opt = f alse) calcola B

Test Opt(B

) → ¯ c, opt if (opt = true) then return h

B

x_F

i

= h

i

var. in else scegli h 6∈ {B(1), . . . , B(m)} con ¯ c

< 0 Test Illim(B

, h) → ¯ A

, illim

if (illim = true) then ”STOP: prob. illimitato”

else

var. out calcola t := arg min

{¯b

/¯ a

: ¯ a

> 0}

Update B B(t) := h

End Loop end while

Esempio

min −3x

+ 2x

+ 4x

s.t.

−x

− x

+ 2x

+ x

= 1 x

− 2x

+ x

+ x

= −1 x

, x

, x

, x

, x

≥ 0

Base iniziale:

B(1) = 2, B(2) = 3 B = [A

, A

] =

 −1 2

−2 1



Iter 1.

B

=

 1/3 −2/3 2/3 −1/3



Esempio

Test Opt u

= [2 4]

 1/3 −2/3 2/3 −1/3



= [10/3 − 8/3]

¯

c

= −3 − [10/3 − 8/3] h

1

i

= 3

¯

c

= 0 − [10/3 − 8/3] h

0

i

= −10/3

¯

c

= 0 − [10/3 − 8/3] h

1

i

= 8/3 opt = f alse =⇒ sceglie var. entrante x

Test Illim b = ¯

 1/3 −2/3 2/3 −1/3

 h

−1

i = h

1

i , ¯ A

=

 1/3 −2/3 2/3 −1/3

 h

0

i = h

2/3

i illim = f alse =⇒ sceglie var. uscente x

(

¯ a₁₄

= 3

¯b2

¯

a₂₄

= 3/2 = θ =⇒ t = 2, x

= x

var. uscente

Esempio

nuova base B = [A

, A

]

 −1 1

−2 0



Iter 2.

B

=

 0 −1/2 1 −1/2



Test Opt u

= [2 0] =

 0 −1/2 1 −1/2



= [0 − 1]

¯

c

= −3 − [0 − 1] h

1

i

= −2

¯

c

= 4 − [0 − 1] h

1

i

= 5

¯

c

= 0 − [0 − 1] h

1

i

= 1

opt = f alse =⇒ sceglie var. entrante x

Esempio

Test Illim b = ¯

 0 −1/2 1 −1/2

 h

−1

i

= h

3/2

i ,

A ¯

=

 0 −1/2 1 −1/2

 h

1

i

= h

−3/2

i

illim = true =⇒ STOP: problema illimitato

Questioni da definire

I

correttezza e convergenza del Metodo del Simplesso

I

individuazione della base iniziale

I

implementazioni efficienti

Il tableau del Simplesso

rappresentiamo il problema risp. ad una base:

c

c

0

B F b

premoltiplichiamo per B

c

c

0

I B

F B

b

Il tableau del Simplesso

sottraiamo alla riga 0 la matrice premoltiplicata per c

c

− c

c

− c

B

F −c

B

b

I B

F B

b

cio` e

0

c

− c

B

F −c

B

b

I B

F B

b

rappresentazione in forma canonica rispetto alla base B

Implementazione Tableau

Input: A, b, c, B = [A

, . . . , A

] Output: x sol. ottima OR illim = true Init. illim := f alse, opt := f alse

costruisce il tableau iniziale in forma canonica Main Loop while (illimitato := f alse and opt := f alse) Row 0 if (¯ c

≥ 0, j ∈ F ) then return h

B

xF

i = h

i

var. in else scegli h 6∈ {B(1), . . . , B(m)} con ¯ c

< 0

Col h if (¯ a

≤ 0, i = 1, . . . , m) then ”STOP: prob. illimitato”

else

var. out calcola t := arg min

{¯b

/¯ a

: ¯ a

> 0}

Update B P IV OT (t, h)

B(t) := h

End Loop end while

Esempio

min −2x

− 5x

− x

s.t.

x

+ 3x

+ x

= 4 5x

+ x

+ x

= 5 2x

+ 4x

+ x

+ x

= 6 x

, x

, x

, x

, x

, x

≥ 0

- 2 - 5 - 1 0 0 0 0

1 3 0 1 0 0 4 x

0 5 1 0 1 0 5 x

2 4 1 0 0 1 6 x

tableau gi` a in forma canonica

Esempio

iter 1

- 2 - 5 - 1 0 0 0 0

1 3 0 1 0 0 4 x

0 5 1 0 1 0 5 x

2 4 1 0 0 1 6 x

var entrante x

t = arg min{4/3, 1, 6/4} = 2

=⇒ var uscente x

P IV OT (t = 2, h = 2): ricavare x

dalla riga t ”di pivot” e sostituirla nelle altre:

I

normalizzare la riga di pivot t = 2

I

sommare alla riga 1 la riga di pivot moltiplicata per −3

I

sommare alla riga 3 la riga di pivot moltiplicata per −4

I

sommare alla riga 0 la riga di pivot moltiplicata per 5

Esempio

iter 2

- 2 0 0 0 1 0 5

1 0 -3/5 1 -3/5 0 1 x

0 1 1/5 0 1/5 0 1 x

2 0 1/5 0 -4/5 1 2 x

var entrante x

t = arg min{1, 2/2} = 3

=⇒ var uscente x

P IV OT (t = 3, h = 1): ricavare x

dalla riga 3 ”di pivot” e sostituirla nelle altre

iter 3

0 0 1/5 0 1/5 1 7

0 0 -7/10 1 -1/5 -1/2 0 x

0 1 1/5 0 1/5 0 1 x

1 0 1/10 0 -2/5 1/2 1 x

¯

c ≥ 0 =⇒ x

=

 1 1 0 0 0 0 

soluzione ottima di valore −7