Lezione n° 13

(1)

Lezione n° 13

Algoritmo del Simplesso:

-  Metodo delle 2 Fasi -  Esempio

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica Università degli Studi di Salerno

Prof. Cerulli – Dott.ssa Gentili – Dott. Carrabs

(2)

Metodo Delle Due Fasi

T

n

min z c x

Ax b (1) x 0 (2) x R

=

≥

∈

Dato il seguente problema di PL in forma STANDARD:

con A(m.n) e b ≥ 0. Supponiamo di volerlo risolvere utilizzando l’algoritmo del simplesso.

Ci occorre una base iniziale

(3)

Se tra le colonne di A non è presente la matrice Identità non è facile individuare m colonne di A linearmente

indipendenti.

Si modifica allora artificialmente il sistema dei vincoli:

0 ,

0

min

≥

→

≥

= +

→

=

y x

x

b y

I x

A b

x A

x c^T

con l’aggiunta di una variabile artificiale y_i ad ogni

vincolo del sistema. Nel nuovo sistema è presente una matrice identità (associata alle variabili y).

(4)

0 ,

0 min

≥

= +

∑

y x

b y

I x

A

y

i

Una soluzione (x’,y’) del nuovo sistema sarà soluzione anche del sistema di partenza se e solo se y’=0.

Per ottenere una tale soluzione (se esiste) risolviamo il seguente problema di PL.

(5)

Per risolvere tale problema possiamo utilizzare

il simplesso utilizzando come base iniziale le colonne della matrice (A,I) associate alle variabili artificiali y.

Quindi nella prima fase si risolve il problema:

0 ,

0 min

≥

= +

= ∑

y x

b y

I x

A

y g

i

i Inizialmente tutte le variab. y sono in base mentre tutte le variabili x sono fuori base.

(6)

Alla fine della prima fase possono verificarsi due casi, l’ottimo della F.O:

1)  g* >0 ⇒ Ax=b non ammette soluzione. Non si passa alla seconda fase

2) g* =0 ⇒ Ax=b ammette soluzione (a meno di soluzioni degeneri).

Si passa alla seconda fase: si risolve il problema iniziale utilizzando la base ottima della prima fase come base iniziale della seconda fase.

(7)

Metodo Delle Due Fasi: Esempio

0

4 2

1

2 min

2 1

≥

≤ +

≥ +

−

=

x

x x

z

0

4

2

1

2 min

4 2

1

3 2

1

2 1

≥

= +

+

=

− +

−

=

x

x x

x

x x

x

x x

z

Problema della Prima fase

0 ,

0

4

2

1

min

4 2

1

1 3

2 1

1

≥

= +

+

= +

− +

=

y x

x x

x

y x

x x

y g

(8)

⎥⎦

⎢ ⎤

⎣

= ⎡

0 1

0

2

1

1 0

1

- 1

1

x x

x₁ ₂ ₃ ₄ ₅

A

Matr. Identità Base Iniziale

0

4

2

1

min

4 2

1

5 3

2 1

5

≥

= +

+

= +

− +

=

x

x x

x

x x

x

Per uniformità poniamo g

y₁=x₅.

{ }^5,4 ^N {^1,2,3}

B = =

(9)

⎥⎦

⎢ ⎤

⎣

= ⎡

1 0

0 1

AB ^x^B ⁼ ^{A b}^B⁻¹ ^⇔ ^x^B ⁼ ^Ib ^⇔ ^x^B ⁼ ^b

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

=

⎥ =

⎦

⎢ ⎤

⎣

⎡

4 1 4

1 1 0

0 b 1

A^-_B¹

4

5 b

x

x x₅ = x1 , ₄ = 4

Test di Ottimalità: calcolo di z_j – c_j per j ∈N

{ }^5,4 ^N {^1,2,3}

B= =

[ ]¹⁰ ^I ₁¹ ⁰ ¹

)

( ₁ ₁ ⎥ − =

⎦

⎢ ⎤

⎣

= ⎡

z − c [ ] ⁰ ¹

2 I 1 0 1 )

( ₂ ₂ ⎥ − =

⎦

⎢ ⎤

⎣

= ⎡

z − c

[ ]¹⁰ ^I ₀¹ ⁰ ¹

)

( ₃ ₃ ⎥ − = −

⎦

⎢ ⎤

⎣

= ⎡−

z − c

(10)

x₂ entra in base Quale variabile esce dalla base?

Regola del minimo rapporto:

-1 B 2 2

1 1

A a I

2 2

y ⎡ ⎤ ⎡ ⎤

= = ⎢ ⎥ = ⎢ ⎥

⎣ ⎦ ⎣ ⎦

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥ =

⎦

⎢ ⎤

⎣

⎡

4 1

4

5 b

x x

{ }¹^,²

min 1

0 :

min ₂

1 1

2 ⇒ = =

⎪⎭

⎪⎬

⎫

⎪⎩

⎪⎨

⎧ >

=

= ∈ y x

y b y

x b _jk

jk j B

k j

x₅ esce dalla base; x₂ entra in base con valore 1

{ }^2,4 ^N {^1,5,3}

B = =

Nuova base:

(11)

⎥⎦

⎢ ⎤

⎣

= ⎡

1 2

0 1

AB ⎥

⎦

⎢ ⎤

⎣

= ⎡

−

1 2 -

0 1

1 AB

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

=

⎥ =

⎦

⎢ ⎤

⎣

⎡

2 1 4

1 1 2 -

0 1 b

A^-_B¹

4

2 b

x x

{ }^2,4 ^N {^1,5,3}

B= =

[ ]⁰⁰ ^A ₀¹ ⁰ ⁰

)

( ₃ ₃ ^-_B¹ ⎥ − =

⎦

⎢ ⎤

⎣

= ⎡−

z − c

[ ]⁰⁰ ^A ₁¹ ⁰ ⁰

)

( ₁ ₁ ^-_B¹ ⎥ − =

⎦

⎢ ⎤

⎣

= ⎡

z − c

[ ]⁰⁰ ^A ¹₀ ¹ ¹

)

( ₅ ₅ ^-_B¹ ⎥ − = −

⎦

⎢ ⎤

⎣

= ⎡

z − c

(12)

Soluzione Ottima della Prima fase

b A

c b

c

g* = _B ⇔ _B _B⁻¹

[⁰⁰] _-¹₂⁰₁ ¹₄ ⁰

* ⎥ =

⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

g Si può passare

alla seconda fase Si risolve il problema iniziale:

utilizzando come base di partenza:

0

4

2

1

2 min

4 2

1

3 2

1

2 1

≥

= +

+

=

− +

−

=

x

x x

x

x x

x

x x

z

{ }^2,4 ^N { }^1,3

B = =

(13)

⎥⎦

⎢ ⎤

⎣

= ⎡

1 2

0 1

AB ⎥

⎦

⎢ ⎤

⎣

= ⎡

−

1 2 -

0 1

1 AB

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

=

⎥ =

⎦

⎢ ⎤

⎣

⎡

2 1 4

1 1 2 -

0 1 b

A^-_B¹

4

2 b

x x

{ }^2,4 ^N { }^1,3

B = =

[ ] ⁽ ¹⁾ ¹

1 1 1

2 -

0 1 0

2 - )

( ₁ ₁ ⎥ − − = −

⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

z − c

[^-²⁰] _-¹₂⁰₁ ₀¹ ⁰ ²

)

( ₃ ₃ ⎥ − =

⎦

⎢ ⎤

⎣

⎥ ⎡−

⎦

⎢ ⎤

⎣

= ⎡

z − c

(14)

x₃ entra in base Quale variabile esce dalla base?

Regola del minimo rapporto:

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

= 2

1 - 0

1 - 1

2 -

0 1 a

A^-_B¹ ₃ y3

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥ =

⎦

⎢ ⎤

⎣

⎡

2 1

4

2 b

x x

{}¹

min 1

0 :

min ₃

2 2

3 ⇒ = =

⎪⎭

⎪⎬

⎫

⎪⎩

⎪⎨

⎧ >

=

= ∈ y x

y b y

x b _jk

jk j B

k j

x₄ esce dalla base; x₃ entra in base con valore 1 Nuova base: ^B ⁼{ }^2,3 ^N ⁼ { }^1,4

(15)

⎥⎦

⎢ ⎤

⎣

= ⎡

0 2

1 - 1

AB ⎥

⎦

⎢ ⎤

⎣

= ⎡

−

1/2

1 -

1/2

0

1 AB

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

=

⎥ =

⎦

⎢ ⎤

⎣

⎡

1 2 4

1 1/2

1 -

1/2

0 b

A^-_B¹

3

2 b

x x

{ }^2,3 ^N { }^1,4

B = =

[^-²⁰] _-₁⁰^1/2_1/2 ₁¹ ⁽ ¹⁾ ¹ ¹ ⁰

)

( ₁ ₁ ⎥ − − = − + =

⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

z − c

[^-²⁰] _-₁⁰^1/2_1/2 ₁⁰ ⁰ ¹

)

( ₄ ₄ ⎥ − = −

⎦

⎢ ⎤

⎣

⎥ ⎡

⎦

⎢ ⎤

⎣

= ⎡

z − c

(16)

Metodo Del Big M

Si modifica artificialmente il sistema dei vincoli:

0 ,

0

min

≥

→

≥

= +

→

=

y x

x

b y

I x

A b

x A

x c^T

con l’aggiunta di una variabile artificiale y_i ad ogni

vincolo del sistema. Nel nuovo sistema è presente una matrice identità (associata alle variabili y).

Alla funzione obiettivo originale vengono sommate (nel caso di un problema di minimo) le variabili artificiali

moltiplicate per un coefficiente M molto grande.

y M

x

c^T 1^T

min +