Lezione n°11

(1)

Lezione n

°

11 Algoritmo del Simplesso:

- Passi fondamentali

- Esempio

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica ed Informatica Applicata

Università di Salerno

(2)

Consideriamo il problema (PL) in

Forma Standard

0 min

³

=

x

b

x

A

x

c

z

T

Data una base B ammissibile, riscriviamo il problema come:

Calcolo della soluzione ottima di un problema di PL.

min z = z

₀

−

(z

_j

− c

_j

)x

_j

j∈N

∑

x

_B

_{= b −}

y

_j

x

_j

j∈N

∑

x ≥ 0

y

j

= A

B

−1

a

_j

z

_j

= c

B

T

A

_B

−1

a

_j

b = A

_B

−1

b

z

₀

= c

B

T

A

_B

−1

b

(3)

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

i

b

j

i

Î

"

£

-Î

"

³

(4)

Scelta della variabile entrante

.

Quando le condizioni di ottimalità non sono verificate

è sempre possibile scegliere una variabile fuori base

x

_k

da portare in base per migliorare l’obiettivo.

Quando esistono più alternative la scelta non preclude

il raggiungimento della soluzione ottima, ma può al

peggio aumentare il tempo necessario per la sua

ricerca.

(5)

Il metodo del gradiente

Sceglie la variabile fuori base x

_k

che localmente fa

aumentare più rapidamente l’obiettivo:

{

_j

}

N

j

k

c

z

c

z

-

=

-Î

max

(6)

Scelta della variabile uscente.

Determinata la variabile fuori base x

_k

da portare in base, si

deve scegliere la variabile uscente.

Esistono due situazioni alternative:

a)

y

_ik

£0 "i=1,...m

La soluzione del problema è illimitata

(

non esiste un

punto di ottimo

).

In questo caso facendo aumentare x

_k

il valore di nessuna

variabile di base diminuisce:

Per qualsiasi valore di x

_k

0

0 (

z

c

)

x

z

=

-

_k

-

_k

£

b)

y

_rk

>0 per almeno un r

La soluzione di base non è ottima, bisogna quindi

passare alla base successiva.

(7)

Nota

● Se una variabile di base x

_Bi

è nulla (soluzione

degenere) e y

_ik

>0, allora x

_k

entra in base con valore

nullo.

● In questo caso la soluzione non cambia, ed in

particolare rimane degenere.

● Per questa ragione la ricerca della soluzione

potrebbe rimanere bloccata generando sempre la

medesima soluzione (

cycling

).

● Il cycling è piuttosto raro e comunque esistono

(8)

L

’

algoritmo del Simplesso

INPUT

:

Problema di PL (in forma standard) e una soluzione di base ammissibile.

1.Test di ottimalità:

Se z

_j

-c

_j

≤0 "jÎN allora la soluzione corrente è ottima e l’algoritmo termina.

Altrimenti andare al passo 2.

2.Scelta della variabile entrante in base:

Scegliere una variabile fuori base x

_k

tale che z

_k

-c

_k

>0 ed andare al passo 3.

3.Test di illimitatezza:

Se y

_ik

£0 "i=1,...m, allora la soluzione del problema è illimitata (non esiste ottimo

finito), e l’algoritmo termina. Altrimenti vai al Passo 4.

4.Scelta della variabile uscente dalla base: Test dei minimi rapporti

Scegliere la variabile x

_r

tale che:

x

_r

è la variabile uscente e la variabile entrante x

_k

assume valore pari a

5.Aggiornamento della base:

Aggiornare gli indici delle variabili in base (B) e quelli delle variabili fuori base (N).

Tornare al passo 1.

rk

r

y

b

r

y

_rk

= min

1 _im

⇢

b

i

y

_ik

: y

ik

> 0

(9)

Esempio: Applicazione del Simplesso

0

5

2

1

2

2 min

2

1

2

1

2

1

2

1 ³

£

+

-³

-£

+

-=

x

z

0 ,

0

5

2

1

2

2 min

5

4

3

5

2

1

4

2

1

3

2

1

2

1 ³

³

=

+

=

+

-=

+

-=

x

z

ú

û

ù

ê

ë

é

=

1

0

1

0

1

0

1

1 -0

0

1

2 -A

B

=

{

3,4,5

}

N

=

{ }

1,2

(10)

Esempio: Applicazione del Simplesso (Cont.)

ú

û

ù

ê

ë

é

=

1

0

1

0

1 B

A

x

B

A b

B

1 x

B

Ib

x

B

b

-=

Û

=

Û

=

3 -1

4 B

5 1 0 0

1 A b

0 1 0 2

0 0 1

5 x

x

é ù

é

ù é ù

ê ú

₌

ê

ú ê ú

ê ú

ê

ú ê ú

ê ú

ê

_ë

ú ê ú

_{û ë û}

ë û

5 ,

2 ,

1 ₄

₅

3 =

x

=

x

=

x

[

]

0

5

2

1

0

0 =

ú

û

ù

ê

ë

é

=

z

5

4

3 x

x

b

A

c

z

₀

=

T

_B

-

1

(11)

Esempio: Applicazione del Simplesso (Cont.)

Test di Ottimalità: calcolo di z

_j

– c

_j

per j ÎN

[

]

(

1 )

0

1

2 I

0

0 )

(

₁

-

=

+

=

ú

û

ù

ê

ë

é

-=

- c

z

[

]

(

2 )

0

2

1

1 I

0

0 )

(

₂

-

=

+

=

ú

û

ù

ê

ë

é

=

- c

z

{

3,4,5

}

N

{ }

1,2

B

=

N

j

c

a

A

c

-z

_j

=

T

_B

-1

_j

-

_j

"

Î

(12)

Esempio: Applicazione del Simplesso (Cont.)

{

}

max

_{{ }}

{

(

),

(

)

}

max

)

(

₁

₂

2 ,

1

2

2 c

z

c

z

c

z

c

z

j

N

j

-

Û

-

-=

-Î

Î

{ }

1 ,

2

2 max

)

(

z

₂

- c

₂

=

x

₂

entra in base

Quale variabile esce dalla base?

Regola del minimo rapporto:

j

B

j

A

a

y

=

-

1 b

A

b

=

_B

-

1 b

_r

y

_rk

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

(13)

Esempio: Applicazione del Simplesso (Cont.)

-1

2 B

2

1

1 A a I 1

1

1 y

é ù é ù

ê ú ê ú

=

_{ê ú ê ú}

=

ê ú ê ú

ë û ë û

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

5

2

1

3

2

1

5

4

3 b

b

x

₃

esce dalla base; x

₂

entra in base con valore 1

Nuova base:

_B

=

{

_2,4,5

}

_N

=

{ }

_1,3

x

₂

=

b

1 y

₁₂

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

) x

2 = 1 = min

⇢

1

1 ,

2

1 ,

5

1

(14)

Esempio: Applicazione del Simplesso (Cont.)

ú

û

ù

ê

ë

é

=

1

0

1

0

1

0

1 B

A

Calcoliamo

A

_B

-

1

5

4

2 x

x

ú

û

ù

ê

ë

é

=

-1

0

1 -0

1

1 -0

0

1

1 B

A

(15)

Esempio: Applicazione del Simplesso (Cont.)

1 B

B

x

=

A b

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

-4

1

5

2

1

0

1 -0

1

1 -0

0

1

5

4

2 b

A

x

B

[

]

[

]

2

5

2

1

0

2 -5

2

1

0

1 -0

1

1 -0

0

1

0

2 -0

=

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

z

b

A

c

z

₀

=

T

_B

-

1

(16)

Esempio: Applicazione del Simplesso (Cont.)

Test di Ottimalità: calcolo di z

_j

– c

_j

per j ÎN

{

2,4,5

}

N

{ }

1,3

B

=

[

]

[

]

1

5

1

2

0

2 -)

1 (

1

2

1

0

1 -0

1

1 -0

0

1

0

2 -)

(

₁

+

=

ú

û

ù

ê

ë

é

-=

-ú

ú

û

ù

ê

ë

é

-ú

ú

û

ù

ê

ë

é

=

- c

z

[

]

[

]

0

2

0

1

0

2 -0

0

1

0

1 -0

1

1 -0

0

1

0

2 -)

(

₃

-

=

-ú

ú

û

ù

ê

ë

é

=

-ú

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

- c

z

N

j

c

a

A

c

-z

_j

=

T

_B

-1

_j

-

_j

"

Î

(17)

Esempio: Applicazione del Simplesso (Cont.)

z

_j

– c

_j

> 0 per j=1

x

₁

entra in base

Quale variabile esce dalla base?

Regola del minimo rapporto:

j

B

j

A

a

y

=

-

1 b

A

b

=

_B

-

1 b

_r

y

_rk

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

(18)

Esempio: Applicazione del Simplesso (Cont.)

-1

1 B

1 1 0 0

-2

A a

-1 1 0 -1

1 -1 0 1

1

3 y

é

ù é ù é ù

ê

ú ê ú ê ú

=

_ê

_{ú ê ú ê ú}

=

ê

ú ê ú ê ú

ë

û ë û ë û

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

4

1

3

2

1

5

4

2 b

b

x

₄

esce dalla base; x

₁

entra in base con valore 1

Nuova base:

_B

=

{

_2,1,5

}

_N

=

{ }

_4,3

x

₁

=

b

2 y

₂₁

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

) x

1 = 1 = min

⇢

1

1 ,

4

3

(19)

Esempio: Applicazione del Simplesso (Cont.)

ú

û

ù

ê

ë

é

=

1

0

1

0

2

1 -A

_B

ú

û

ù

ê

ë

é

=

-1

3

2

0

1

1 -

0

2

1 -

1 B

A

Calcoliamo

A

_B

-

1

5

1

2 x

x

(20)

Esempio: Applicazione del Simplesso (Cont.)

1 B

B

x

=

A b

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

-1

1

3

5

2

1

3

2

0

1

1 -

0

2

1 -

1

5

1

2 b

A

x

B

[

]

[

]

7

5

2

1

0

5

3

5

2

1

3

2

0

1

1 -

0

2

1 -

0

1

2 -0

=

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

z

b

A

c

z

₀

=

T

_B

-

1

(21)

Esempio: Applicazione del Simplesso (Cont.)

Test di Ottimalità: calcolo di z

_j

– c

_j

per j ÎN

{

2,1,5

}

N

{ }

4,3

B

=

[

]

[

]

0

3

0

1

0

5

3

0

1

3

2

0

1

1 -

0

2

1 -

0

1

2 -)

(

₃

-

=

ú

û

ù

ê

ë

é

=

-ú

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

- c

z

[

]

[

]

0

5

0

1

0

5

3

0

1

0

1

3

2

0

1

1 -

0

2

1 -

0

1

2 -)

(

₄

-

=

-ú

ú

û

ù

ê

ë

é

=

-ú

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

- c

z

N

j

c

a

A

c

-z

_j

=

T

_B

-1

_j

-

_j

"

Î

(22)

Esempio: Applicazione del Simplesso (Cont.)

z

_j

– c

_j

> 0 per j=3

x

₃

entra in base

Quale variabile esce dalla base?

Regola del minimo rapporto:

j

B

j

A

a

y

=

-

1 b

A

b

=

_B

-

1 b

_r

y

_rk

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

(23)

Esempio: Applicazione del Simplesso (Cont.)

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

2

1 -1

-0

0

1

3

2

0

2

1 -0

1

1 -a

A

-

_B

1 ₃

3 y

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

1

3

1

3

2

1

5

1

2 b

b

x

₅

esce dalla base; x

₃

entra in base con valore 1/2

Nuova base:

_B

=

{

_2,1,3

}

_N

=

{ }

_4,5

x

₃

=

b

3 y

₃₃

= min

1 _im

⇢

b

_i

y

_ik

: y

ik

> 0

) x

3 =

1

2 = min

⇢

1

2

(24)

Esempio: Applicazione del Simplesso (Cont.)

ú

û

ù

ê

ë

é

=

0

1

0

1

2

1 B

A

ú

û

ù

ê

ë

é

=

-2

1

2

3

1

2

1

2

1

0

2

1

2

1

0

1 B

A

Calcoliamo

A

_B

-

1

3

1

2 x

x

(25)

Esempio: Applicazione del Simplesso (Cont.)

1 B

B

x

=

A b

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

-2

1

2

3

2

7

5

2

1

2

1

2

3

1

2

1

2

1

0

2

1

2

1

0

1

3

1

2 b

A

x

B

[

]

[

]

2

17

5

2

1

2

3

2

1

0

5

2

1

2

1

2

3

1

2

1

2

1

0

2

1

2

1

0

1

2 -0

=

-ú

ú

û

ù

ê

ë

é

=

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

z

b

A

c

z

₀

=

T

_B

-

1

(26)

Esempio: Applicazione del Simplesso (Cont.)

Test di Ottimalità: calcolo di z

_j

– c

_j

per j ÎN

{

2,1,3

}

N

{ }

4,5

B

=

[

]

[

]

2

1

0

1

0

2

3

2

1

0

1

0

2

1

2

3

1

2

1

2

1

0

2

1

2

1

0

1

2 -)

(

₄

-

=

-ú

ú

û

ù

ê

ë

é

=

-ú

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

- c

z

[

]

[

]

2

3

0

1

0

2

3

2

1

0

1

0

2

1

2

3

1

2

1

2

1

0

2

1

2

1

0

1

2 -)

(

₅

-

=

-ú

ú

û

ù

ê

ë

é

=

-ú

ú

û

ù

ê

ë

é

ú

û

ù

ê

ë

é

=

- c

z

N

j

c

a

A

c

-z

_j

=

T

_B

-1

_j

-

_j

"

Î